|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r77173 - sandbox/gtl/doc
From: sydorchuk.andriy_at_[hidden]
Date: 2012-03-03 07:09:02
Author: asydorchuk
Date: 2012-03-03 07:09:02 EST (Sat, 03 Mar 2012)
New Revision: 77173
URL: http://svn.boost.org/trac/boost/changeset/77173
Log:
Updating docs.
Added:
sandbox/gtl/doc/voronoi_utils.htm (contents, props changed)
Text files modified:
sandbox/gtl/doc/index.htm | 19 ++++++++++++-------
sandbox/gtl/doc/voronoi_builder.htm | 26 +++++++++++++++-----------
sandbox/gtl/doc/voronoi_predicates.htm | 20 +++++++++++---------
sandbox/gtl/doc/voronoi_robust_fpt.htm | 21 ++++++++++++---------
4 files changed, 50 insertions(+), 36 deletions(-)
Modified: sandbox/gtl/doc/index.htm
==============================================================================
--- sandbox/gtl/doc/index.htm (original)
+++ sandbox/gtl/doc/index.htm 2012-03-03 07:09:02 EST (Sat, 03 Mar 2012)
@@ -1,5 +1,6 @@
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
-<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en"><head><!--
+<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en"><head>
+<!--
Copyright 2009-2010 Intel Corporation
license banner
--><title>Boost Polygon Library: Main Page</title>
@@ -8,8 +9,10 @@
+
+
<meta http-equiv="content-type" content="text/html;charset=ISO-8859-1" /><!-- <link type="text/css" rel="stylesheet" href="adobe_source.css"> --></head><body><table style="margin: 0pt; padding: 0pt; width: 100%;" border="0" cellpadding="0" cellspacing="0"><tbody><tr>
-<td style="background-color: rgb(238, 238, 238);" nowrap="1" valign="top">
+<td style="background-color: rgb(238, 238, 238);" valign="top" nowrap="1">
<div style="padding: 5px;" align="center">
<img src="images/boost.png" border="0" height="86" width="277" /><a title="www.boost.org home page" href="http://www.boost.org/" tabindex="2" style="border: medium none ;">
</a>
@@ -39,7 +42,8 @@
<li>Property Merge 90</li>
<li>Property Merge 45</li>
<li>Property Merge</li>
- <li>Voronoi Main</li>
+ <li><a href="voronoi_main.hpp">Voronoi Main Page<br />
+</a></li>
<li>Voronoi Benchmark<br />
</li>
@@ -47,7 +51,7 @@
<li><a href="voronoi_diagram_datastructure.htm">Voronoi Diagram<br />
</a></li>
<li>Voronoi Predicates</li>
- <li>Voronoi Robust FPT<br />
+ <li>Voronoi Robust FPT<br />
</li>
<li>Voronoi Utils<br />
</li>
@@ -103,9 +107,10 @@
provides interface to construct Voronoi diagrams of points figure a and
line segments figure b (the last could be used to discretize any
two-dimensional curve). Figure c contains example of medial axis of a
-non-convex polygon. The implementation outperforms most of the known
+non-convex polygon. The implementation outperforms most of the known
commercial and non-commercial libraries in both efficiency and
-numerical robustness aspects.
+numerical robustness aspects. You may find more details on the topic at Voronoi main page.<br />
+
</p>
<p><img src="images/voronoi.png" border="0" height="300" width="900" /></p>
<p>The coordinate data type is a template parameter of all data types
@@ -250,7 +255,7 @@
</td></tr><tr>
-<td style="background-color: rgb(238, 238, 238);" nowrap="1" valign="top">
+<td style="background-color: rgb(238, 238, 238);" valign="top" nowrap="1">
</td>
<td style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;" valign="top" width="100%">
Modified: sandbox/gtl/doc/voronoi_builder.htm
==============================================================================
--- sandbox/gtl/doc/voronoi_builder.htm (original)
+++ sandbox/gtl/doc/voronoi_builder.htm 2012-03-03 07:09:02 EST (Sat, 03 Mar 2012)
@@ -2,12 +2,13 @@
<html><head>
+
<meta http-equiv="Content-Language" content="en-us">
<meta http-equiv="Content-Type" content="text/html; charset=windows-1252"><title>Contents</title></head><body>
<table style="margin: 0pt; padding: 0pt; width: 100%;" border="0" cellpadding="0" cellspacing="0">
<tbody><tr>
- <td style="background-color: rgb(238, 238, 238);" nowrap="1" valign="top">
+ <td style="background-color: rgb(238, 238, 238);" valign="top" nowrap="1">
<div style="padding: 5px;" align="center">
<img src="images/boost.png" border="0" height="86" width="277"><a title="www.boost.org home page" tabindex="2" style="border: medium none ;" href="http://www.boost.org/">
</a></div>
@@ -44,15 +45,18 @@
<li>Property Merge 90</li>
<li>Property Merge 45</li>
<li>Property Merge</li>
- <li>Voronoi Main Page<br>
- </li>
- <li>Voronoi Builder<br>
- </li>
- <li><a href="voronoi_diagram_datastructure.htm">Voronoi Diagram
- Datastructure</a></li>
- <li><a href="voronoi_lazy_arithmetic_concept.htm">Voronoi Lazy
- Arithmetic Concept</a></li>
- </ul>
+ <li><a href="voronoi_main.hpp">Voronoi Main Page<br>
+</a></li>
+ <li>Voronoi Benchmark<br>
+ </li>
+ <li>Voronoi Builder</li>
+ <li><a href="voronoi_diagram_datastructure.htm">Voronoi Diagram<br>
+</a></li>
+ <li>Voronoi Predicates</li>
+ <li>Voronoi Robust FPT<br>
+ </li>
+ <li>Voronoi Utils</li>
+</ul>
<h3 class="navbar">Other Resources</h3>
<ul>
<li>GTL Boostcon 2009 Paper</li>
@@ -374,7 +378,7 @@
Tutorial</a>.</p></td>
</tr>
<tr>
- <td style="background-color: rgb(238, 238, 238);" nowrap="1" valign="top"> </td>
+ <td style="background-color: rgb(238, 238, 238);" valign="top" nowrap="1"> </td>
<td style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;" valign="top" width="100%">
<table class="docinfo" id="table2" frame="void" rules="none">
<colgroup>
Modified: sandbox/gtl/doc/voronoi_predicates.htm
==============================================================================
--- sandbox/gtl/doc/voronoi_predicates.htm (original)
+++ sandbox/gtl/doc/voronoi_predicates.htm 2012-03-03 07:09:02 EST (Sat, 03 Mar 2012)
@@ -6,12 +6,14 @@
+
+
<meta http-equiv="Content-Language" content="en-us">
<meta http-equiv="Content-Type" content="text/html; charset=windows-1252"><title>Contents</title></head><body>
<table style="margin: 0pt; padding: 0pt; width: 100%;" border="0" cellpadding="0" cellspacing="0">
<tbody><tr>
- <td style="background-color: rgb(238, 238, 238);" nowrap="1" valign="top">
+ <td style="background-color: rgb(238, 238, 238);" valign="top" nowrap="1">
<div style="padding: 5px;" align="center">
<img src="images/boost.png" border="0" height="86" width="277"><a title="www.boost.org home page" tabindex="2" style="border: medium none ;" href="http://www.boost.org/">
</a></div>
@@ -142,20 +144,20 @@
1) mathematical transformation of the predicate exists that evaluates exact results:<span style="font-family: Courier New,Courier,monospace;"><br>
<br>
Predicate: A/B + C/D ?< 0;<br>
-After math. transform: (A*D + B*C) / (B * D) ?< 0.<br>
+After math. transform: (A*D + B*C) / (B * D) ?< 0;<br>
<br>
-Predicate: sqrt(A) < 1.2;<br>
-After math. transform: A ?< 1.44.<br>
+Predicate: sqrt(A) ?< 1.2;<br>
+After math. transform: A ?< 1.44;<br>
<br>
</span>2) the correct result could be produced only by increasing
precision of the multiprecision types and with defined relative error
for the output type:<br>
<br>
- <span style="font-family: Courier New,Courier,monospace;">Predicate: sqrt(A) + sqrt(B) + sqrt(C) + sqrt(D) + sqrt(E) < 1.2;<br>
-Imagine that value of the expression to the left is very close to 1.2.<br>
+ <span style="font-family: Courier New,Courier,monospace;">Predicate: sqrt(A) + sqrt(B) + sqrt(C) + sqrt(D) + sqrt(E) ?< 1.2;<br>
+Imagine that value of the expression to the left is very close to 1.2;<br>
</span><br>
- <span style="font-family: Courier New,Courier,monospace;">Predicate: sin(x) < 0.57;<br>
-Relativer error of sin function should be known.<br>
+ <span style="font-family: Courier New,Courier,monospace;">Predicate: sin(x) ?< 0.57;<br>
+Relativer error of sin function should be known;<br>
<br>
</span>Voronoi of points could be implemented using only the
predicates of the first type, however Voronoi of segments could not.
@@ -169,7 +171,7 @@
data structure (this won't influence main targets algorithm is used
for).<span style="font-family: Courier New,Courier,monospace;"><br>
</span>
-</td></tr><tr><td style="background-color: rgb(238, 238, 238);" nowrap="1" valign="top"><br>
+</td></tr><tr><td style="background-color: rgb(238, 238, 238);" valign="top" nowrap="1"><br>
</td><td style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;" valign="top" width="100%"><table class="docinfo" id="table2" frame="void" rules="none"><tbody valign="top"><tr><th class="docinfo-name">Copyright:</th>
<td>Copyright © Intel Corporation 2008-2010.</td>
</tr>
Modified: sandbox/gtl/doc/voronoi_robust_fpt.htm
==============================================================================
--- sandbox/gtl/doc/voronoi_robust_fpt.htm (original)
+++ sandbox/gtl/doc/voronoi_robust_fpt.htm 2012-03-03 07:09:02 EST (Sat, 03 Mar 2012)
@@ -7,12 +7,14 @@
+
+
<meta http-equiv="Content-Language" content="en-us">
<meta http-equiv="Content-Type" content="text/html; charset=windows-1252"><title>Contents</title></head><body>
<table style="margin: 0pt; padding: 0pt; width: 100%;" border="0" cellpadding="0" cellspacing="0">
<tbody><tr>
- <td style="background-color: rgb(238, 238, 238);" nowrap="1" valign="top">
+ <td style="background-color: rgb(238, 238, 238);" valign="top" nowrap="1">
<div style="padding: 5px;" align="center">
<img src="images/boost.png" border="0" height="86" width="277"><a title="www.boost.org home page" tabindex="2" style="border: medium none ;" href="http://www.boost.org/">
</a></div>
@@ -49,16 +51,17 @@
<li>Property Merge 90</li>
<li>Property Merge 45</li>
<li>Property Merge</li>
- <li>Voronoi Main</li>
+ <li><a href="voronoi_unit.htm">Voronoi Main Page<br>
+</a></li>
<li>Voronoi Benchmark</li>
<li>Voronoi Builder<br>
</li>
<li>Voronoi Diagram</li>
- <li>Voronoi Robust FPT<br>
+ <li>Voronoi Robust FPT<br>
</li>
- <li>Voronoi Predicates</li>
+ <li>Voronoi Predicates</li>
<li>Voronoi Utils<br>
</li>
@@ -108,7 +111,7 @@
<span style="font-family: Courier New,Courier,monospace;">re(A-B) <= (B * re(A) + A * re(B)) / |A-B| + C, if A * B < 0;</span><br style="font-family: Courier New,Courier,monospace;">
<span style="font-family: Courier New,Courier,monospace;">re(A*B) <= re(A) + re(B) + C;</span><br style="font-family: Courier New,Courier,monospace;">
<span style="font-family: Courier New,Courier,monospace;">re(A/B) <= re(A) + re(B) + C;</span><br style="font-family: Courier New,Courier,monospace;">
- <span style="font-family: Courier New,Courier,monospace;">re(sqrt(A)) <= re(A) * 0.5 + C.<br>
+ <span style="font-family: Courier New,Courier,monospace;">re(sqrt(A)) <= re(A) * 0.5 + C;<br>
<br>
</span>The constant C is equal to the rounding relative error
which for the above set of arithmetic operations in the IEEE-754
@@ -127,15 +130,15 @@
also called cancellation error).<br>
To explain this a bit consider following experssion (~ - stands for almost equal, << - many times larger than):<br>
<br>
- <span style="font-family: Courier New,Courier,monospace;">A - B + C, where A ~ B and C << B.</span><br>
+ <span style="font-family: Courier New,Courier,monospace;">A - B + C, where A ~ B and C << B;</span><br>
<br>
Computing relative error of this expression from left to right will produce extremely large relative error:<br>
<br>
- <span style="font-family: Courier New,Courier,monospace;">re(A-B+C) = max(re(A-B), re(C)) = re(A-B) = INF.<br>
+ <span style="font-family: Courier New,Courier,monospace;">re(A-B+C) = max(re(A-B), re(C)) = re(A-B) = INF;<br>
<br>
</span>While doing this from right to left will keep relative error value small:<br>
<br>
- <span style="font-family: Courier New,Courier,monospace;">re(A-B+C) = re(C-B+A) = max(re(C-B), re(A)) = max(re(A), re(B)).<br>
+ <span style="font-family: Courier New,Courier,monospace;">re(A-B+C) = re(C-B+A) = max(re(C-B), re(A)) = max(re(A), re(B));<br>
<br>
</span>While both estimates are valid (they define upper bound of the relative error), of course the second one is preferable.<br>
Here is the place where robust difference type comes useful. Basically
@@ -168,7 +171,7 @@
</td>
</tr>
<tr>
- <td style="background-color: rgb(238, 238, 238);" nowrap="1" valign="top"> </td>
+ <td style="background-color: rgb(238, 238, 238);" valign="top" nowrap="1"> </td>
<td style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;" valign="top" width="100%">
<table class="docinfo" id="table2" frame="void" rules="none">
<colgroup>
Added: sandbox/gtl/doc/voronoi_utils.htm
Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk
==============================================================================
--- (empty file)
+++ sandbox/gtl/doc/voronoi_utils.htm 2012-03-03 07:09:02 EST (Sat, 03 Mar 2012)
@@ -0,0 +1,171 @@
+<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
+<html><head>
+
+
+
+
+
+
+
+
+
+
+
+<meta http-equiv="Content-Language" content="en-us">
+<meta http-equiv="Content-Type" content="text/html; charset=windows-1252"><title>Contents</title></head><body>
+
+<table style="margin: 0pt; padding: 0pt; width: 100%;" border="0" cellpadding="0" cellspacing="0">
+ <tbody><tr>
+ <td style="background-color: rgb(238, 238, 238);" nowrap="1" valign="top">
+ <div style="padding: 5px;" align="center">
+ <img src="images/boost.png" border="0" height="86" width="277"><a title="www.boost.org home page" tabindex="2" style="border: medium none ;" href="http://www.boost.org/">
+ </a></div>
+ <div style="margin: 5px;">
+ <h3 class="navbar">Contents</h3>
+ <ul>
+ <li>Boost.Polygon Main Page</li>
+ <li>Design Overview</li>
+ <li>Isotropy</li>
+ <li>Coordinate Concept</li>
+ <li>Interval Concept</li>
+ <li>Point Concept</li>
+ <li>Rectangle Concept</li>
+ <li>Polygon 90 Concept</li>
+ <li><a href="gtl_polygon_90_with_holes_concept.htm">Polygon 90
+ With Holes Concept</a></li>
+ <li>Polygon 45 Concept</li>
+ <li><a href="gtl_polygon_45_with_holes_concept.htm">Polygon 45
+ With Holes Concept</a></li>
+ <li>Polygon Concept</li>
+ <li><a href="gtl_polygon_with_holes_concept.htm">Polygon With
+ Holes Concept</a></li>
+ <li><a href="gtl_polygon_90_set_concept.htm">Polygon 90 Set
+ Concept</a></li>
+ <li><a href="gtl_polygon_45_set_concept.htm">Polygon 45 Set
+ Concept</a></li>
+ <li>Polygon Set Concept</li>
+ <li><a href="gtl_connectivity_extraction_90.htm">Connectivity
+ Extraction 90</a></li>
+ <li><a href="gtl_connectivity_extraction_45.htm">Connectivity
+ Extraction 45</a></li>
+ <li><a href="gtl_connectivity_extraction.htm">Connectivity
+ Extraction</a></li>
+ <li>Property Merge 90</li>
+ <li>Property Merge 45</li>
+ <li>Property Merge</li>
+ <li><a href="voronoi_unit.htm">Voronoi Main Page<br>
+</a></li>
+ <li>Voronoi Benchmark</li>
+
+ <li>Voronoi Builder<br>
+ </li>
+ <li>Voronoi Diagram</li>
+ <li>Voronoi Robust FPT<br>
+ </li>
+
+ <li>Voronoi Predicates</li>
+
+ <li>Voronoi Utils<br>
+ </li>
+
+
+ </ul>
+ <h3 class="navbar">Other Resources</h3>
+ <ul>
+ <li>GTL Boostcon 2009 Paper</li>
+ <li><a href="GTL_boostcon_draft03.htm">GTL Boostcon 2009
+ Presentation</a></li>
+ <li>Performance Analysis</li>
+ <li>Layout Versus Schematic Tutorial</li>
+ <li>Minkowski Sum Tutorial</li>
+ <li>Voronoi Basic Tutorial</li>
+ <li>Voronoi Advanced Tutorial</li>
+ </ul>
+ </div>
+ <h3 class="navbar">Polygon Sponsor</h3>
+ <div style="padding: 5px;" align="center">
+ <img src="images/intlogo.gif" border="0" height="51" width="127"><a title="www.adobe.com home page" tabindex="2" style="border: medium none ;" href="http://www.adobe.com/">
+ </a></div>
+ </td>
+ <td style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;" valign="top" width="100%"><!-- End Header -->
+ <br>
+ <p></p>
+ <h1>Voronoi Utils</h1>Voronoi
+utilities are set of tools that users may find useful especially for
+the visualization of the Voronoi diagrams or parabolic edges
+interpoliation.<br>
+All the methods within the utilities class are static. Class definition follows:<br>
+ <br><span style="font-family: Courier New,Courier,monospace;">
+template <typename T, typename TRAITS = voronoi_utils_traits<T> ></span><br style="font-family: Courier New,Courier,monospace;"><span style="font-family: Courier New,Courier,monospace;">
+class voronoi_utils;<br>
+ <br>
+ </span><span style="font-family: Courier New,Courier,monospace;">T - </span>coordinate type utilities methods operate with.<br>
+ <span style="font-family: Courier New,Courier,monospace;">TRAITS - </span><span style="font-family: Courier New,Courier,monospace;"></span> contain utilities coordinate and geometry traits.<br>
+ <br>
+ <table style="text-align: left; width: 100%;" border="1" cellpadding="2" cellspacing="2">
+ <tbody>
+ <tr>
+ <td style="vertical-align: top;"><span style="font-family: Courier New,Courier,monospace;">template <typename CT></span><br style="font-family: Courier New,Courier,monospace;">
+ <span style="font-family: Courier New,Courier,monospace;">static brect_type get_view_rectangle(const bounding_rectangle<CT> &brect, fpt_type scale = 1.0)</span><br>
+ </td>
+ <td style="vertical-align: top;">Returns scaled homothetic bounding rectangle. The center of homotethy corresponds to the center of the input rectangle.<br>
+ </td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top;"><span style="font-family: Courier New,Courier,monospace;">template <typename CT></span><br style="font-family: Courier New,Courier,monospace;">
+ <span style="font-family: Courier New,Courier,monospace;">static point_set_type get_point_interpolation(</span><span style="font-family: Courier New,Courier,monospace;">const voronoi_edge<CT> *edge,</span><span style="font-family: Courier New,Courier,monospace;"> const bounding_rectangle<CT> &brect,</span><span style="font-family: Courier New,Courier,monospace;"> fpt_type max_error)</span><br>
+ </td>
+ <td style="vertical-align: top;">Interpolates Voronoi edge.
+For linear edges fills output set with edge endpoints. For parabolic
+edges fills output set with points that interpolate Voronoi edge.
+Additional clipping is done for infinite edges using input bounding
+rectangle.<br>
+ </td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top;"><span style="font-family: Courier New,Courier,monospace;">static
+void find_intersections(const point_type &origin, const point_type
+&direction, kEdgeType edge_type, const brect_type &brect,
+point_set_type &intersections)</span><br>
+ </td>
+ <td style="vertical-align: top;"><br>
+ </td>
+ </tr>
+ </tbody>
+ </table>
+
+
+ <h1>Voronoi Utils Traits<br>
+</h1><br>
+
+
+
+</td>
+ </tr>
+ <tr>
+ <td style="background-color: rgb(238, 238, 238);" nowrap="1" valign="top"> </td>
+ <td style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;" valign="top" width="100%">
+ <table class="docinfo" id="table2" frame="void" rules="none">
+ <colgroup>
+ <col class="docinfo-name"><col class="docinfo-content">
+ </colgroup>
+ <tbody valign="top">
+ <tr>
+ <th class="docinfo-name">Copyright:</th>
+ <td>Copyright © Intel Corporation 2008-2010.</td>
+ </tr>
+ <tr class="field">
+ <th class="docinfo-name">License:</th>
+ <td class="field-body">Distributed under the Boost Software
+ License, Version 1.0. (See accompanying file
+ <tt class="literal"><span class="pre">LICENSE_1_0.txt</span></tt>
+ or copy at
+ <a class="reference" target="_top" href="http://www.boost.org/LICENSE_1_0.txt">
+ http://www.boost.org/LICENSE_1_0.txt>)</td>
+ </tr>
+ </tbody></table>
+ </td>
+ </tr>
+</tbody></table>
+
+</body></html>
\ No newline at end of file