Boost logo

Boost-Commit :

Date view Thread view Subject view Author view

Subject: [Boost-commit] svn:boost r77881 - sandbox/gtl/doc
From: sydorchuk.andriy_at_[hidden]
Date: 2012-04-10 03:15:06

Author: asydorchuk
Date: 2012-04-10 03:15:05 EDT (Tue, 10 Apr 2012)
New Revision: 77881
URL: http://svn.boost.org/trac/boost/changeset/77881

Log:
Trying to work not working documentation pages as HTML.

Added:
   sandbox/gtl/doc/voronoi_predicates.htm (contents, props changed)
   sandbox/gtl/doc/voronoi_robust_fpt.htm (contents, props changed)

Added: sandbox/gtl/doc/voronoi_predicates.htm
==============================================================================
--- (empty file)
+++ sandbox/gtl/doc/voronoi_predicates.htm 2012-04-10 03:15:05 EDT (Tue, 10 Apr 2012)
@@ -0,0 +1,244 @@
+<!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>Voronoi Predicates</title>
+
+
+
+
+ <meta http-equiv="content-type" content="text/html; charset=utf-8">
+
+
+ <meta http-equiv="content-type" content="text/html; charset=utf-8"></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_main.htm">Voronoi Main Page<br>
+ </a></li>
+ <li>Voronoi Benchmark</li>
+ <li>Voronoi Builder<br>
+ </li>
+ <li>Voronoi Diagram</li>
+ <li>Voronoi Predicates</li>
+ <li>Voronoi Robust FPT<br>
+ </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><a href="voronoi_advanced_tutorial.htm">Voronoi Advanced
+Tutorial</a></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>
+
+
+ <h1>Voronoi Predicates<br>
+ </h1>
+
+In mathematical theory predicate is an operator which returns true
+or false (e.g. it may answer a question: "is it sunny today?").<br>
+
+The Voronoi predicates contain implementation of a set of the geometric
+predicates used by the Voronoi builder.
+Except of those it also provides
+functors that allow to compute the coordinates of the centers of the
+inscribed
+circles (those correspond to the Voronoi vertices) within the given
+relative error precision range (64 machine epsilons). This means that
+the more mantissa bits
+your floating point type has the better precision of the output
+geometries you'll get. This
+is a very handy functionality as it allows to improve output precision
+simply providing 3rd party IEEE-754 like floating-point types.<br>
+
+
+ <h2>Geometric Predicates</h2>
+
+The main issues with the implementation of any complex geometric
+algorithm arise when dealing with the robustness of the geometric
+predicates.
+Usually this
+is also the point where the commercial projects stand strong against
+noncommercial implementations (it's not the case with our
+implementation).
+For the short example let's consider the following code snippet, that
+could
+be used to compute orientation of the three points:<br>
+
+ <br>
+
+ <span style="font-family: Courier New,Courier,monospace;">double
+cross_product(double dx1, double dy1, double dx2, double dy2) {</span><br style="font-family: Courier New,Courier,monospace;">
+
+ <span style="font-family: Courier New,Courier,monospace;">&nbsp;
+return dx1 * dy2 - dx2 * dy1;</span><br style="font-family: Courier New,Courier,monospace;">
+
+ <span style="font-family: Courier New,Courier,monospace;">}<br>
+ <br>
+int main() {<br>
+&nbsp; int v = 1 &lt;&lt; 30;&nbsp; // 2 ^ 30<br>
+&nbsp; double result = </span><span style="font-family: Courier New,Courier,monospace;">cross_product</span><span style="font-family: Courier New,Courier,monospace;">(v, v - 1, v + 1,
+v);<br>
+&nbsp; printf("%.3f", result);<br>
+&nbsp; return 0;<br>
+}<br>
+ <br>
+ </span>The
+output of this simple program will be "0.000", while
+the correct one is "1.000". In terms of the orientation test this means
+that points are collinear instead of being CCW oriented. This is one of
+the basic predicates used in any geometric algorithm and taking wrong
+output from it may influence the further algorithm execution:
+corrupting algorithm underlying structures or producing completely
+invalid output. Voronoi uses
+slightly more complex predicates. To insure that they are robust and
+efficient the approach that combines two known techniques (lazy
+arithmetic and multiple
+precision computations) is used.<br>
+
+
+ <h2>Lazy Arithmetic</h2>
+
+Lazy
+arithmetic is based on the usage of IEEE-754 floating-point types to
+quickly evaluate the result of the expression. While this approach has
+a good speed
+performance it doesn't produce reliable results all the time (as in the
+example above). The way to solve the issue is apart from computing
+result of the expression compute the relative error of it also. This
+will
+give us the range of values the evaluated result belongs to and based
+on that we can
+come up with two decisions: 1) output the value; 2) recompute the
+expression using multiprecision type. The way relative errors are
+evaluated is explained in the <a href="voronoi_robust_fpt.htm">Voronoi
+Robust FPT</a> section.<br>
+
+
+ <h2>Multiple Precision Arithmetic</h2>
+
+In the vast majority of cases
+the lazy arithmetic approach produces correct result thus further
+processing is not required. In other cases the Voronoi library defined
+or user
+provided multiple precision types are used to produce correct result.
+However even that doesn't solve all the cases. Multiprecision geometric
+predicates could be divided onto two categories:<br>
+
+ <br>
+
+1) mathematical transformation of the predicate exists that evaluates
+exact result:<span style="font-family: Courier New,Courier,monospace;"><br>
+ <br>
+Predicate: A/B + C/D ?&lt; 0;<br>
+After math. transform: (A*D + B*C) / (B * D) ?&lt; 0;<br>
+ <br>
+Predicate: sqrt(A) ?&lt; 1.2;<br>
+After math. transform: A ?&lt; 1.44;<br>
+ <br>
+ </span>2) the correct result could be produced only by increasing
+precision of the multiprecision type 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) ?&lt; 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) ?&lt; 0.57;<br>
+Relative error of sin function should be known;<br>
+ <br>
+ </span>The Voronoi of points could be completely
+implemented using predicates of the first type, however the Voronoi of
+segments could not.
+The predicate that doesn't fall into the first category is responsible
+for comparison of the Voronoi circle events. However it appears that
+properly used
+this predicate can't corrupt algorithm internal structures and produces
+output technically the same as produced in case this predicate fell in
+the first category.&nbsp; The main reasons for this are: 1) algorithm
+operates with integer coordinate type of the input geometries; 2)
+closely
+situated Voronoi vertices are considered to be the same in the output
+data structure (this won't influence main targets algorithm is used
+for).<span style="font-family: Courier New,Courier,monospace;"></span><span style="font-family: Courier New,Courier,monospace;"></span><br>
+</td>
+ </tr>
+ <tr>
+ <td style="background-color: rgb(238, 238, 238);" nowrap="1" valign="top">&nbsp;</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>

Added: sandbox/gtl/doc/voronoi_robust_fpt.htm
==============================================================================
--- (empty file)
+++ sandbox/gtl/doc/voronoi_robust_fpt.htm 2012-04-10 03:15:05 EDT (Tue, 10 Apr 2012)
@@ -0,0 +1,211 @@
+<!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>Voronoi Robust FPT</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_main.htm">Voronoi Main Page<br>
+ </a></li>
+ <li>Voronoi Benchmark</li>
+ <li>Voronoi Builder<br>
+ </li>
+ <li>Voronoi Diagram</li>
+ <li>Voronoi Predicates</li>
+ <li>Voronoi Robust FPT<br>
+ </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><a href="voronoi_advanced_tutorial.htm">Voronoi Advanced
+Tutorial</a></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>
+
+ <h1>Voronoi Robust FPT</h1>
+The Voronoi
+robust floating-point types are the set of classes and tools that
+allow to estimate relative error of the arithmetic expressions. It is
+assumed that the other Boost libraries may find this unit functionality
+extremely useful, as it can be use d to implement robust and efficient
+arithmetic predicates or functors that compute values within known
+relative error.<br>
+ <h2>Robust Fpt Type</h2>
+The robust
+fpt type (robust floating-point type)
+- represents the IEEE-754 floating-point type wrapper that also
+contains
+information about the relative error of the underlying value. The
+implementation overloads 5 standard operations: +, -, *, /, sqrt and
+apart from the evaluating value of the expression also computes its
+relative
+error. Let's consider two values A and B; C - rounding error, re(X)
+- relative error of the X expression, then following rules apply:<br>
+ <br>
+ <span style="font-family: Courier New,Courier,monospace;">re(A+B)
+&lt;= max(re(A), re(B)) + C, if A * B &gt;= 0;</span><br style="font-family: Courier New,Courier,monospace;">
+ <span style="font-family: Courier New,Courier,monospace;">re(A-B)
+&lt;= (B * re(A) + A * re(B)) / |A - B| + C, if A * B &lt; 0;</span><br style="font-family: Courier New,Courier,monospace;">
+ <span style="font-family: Courier New,Courier,monospace;">re(A*B)
+&lt;= 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)
+&lt;= 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))
+&lt;= re(A) * 0.5 + C;<br>
+ <br>
+ </span>The constant C is equal to the rounding error,
+which for the above set of arithmetic operations in the IEEE-754
+floating-point implementation should be equal to 1 machine epsilon. <br>
+ <h2>Robust Difference Type</h2>
+The robust
+difference type -
+represents expression wrapper that holds the positive and negative
+partial
+sums of the expression in a separate values in order to avoid
+the cancellation errors before evaluating the final difference.
+Following
+arithmetic operators are overloaded for the robust difference type: +,
+-, *, / (division operator is not overloaded for the case were both
+arguments have robust difference type).<br>
+Looking at the relative error formulas above one may notice a few facts
+about them:<br>
+1) all of the formulas evaluate upper bound of the relative error, the
+actual value could be a lot smaller;<br>
+2) relative error estimate for the expression depends on the order
+operations are executed;<br>
+3) relative error of&nbsp; the difference of two positive numbers may
+be
+extremely large in case their values are close to each other (this is
+also known as the cancellation error).<br>
+To explain this a bit consider the following expression (~ - stands for
+almost equal, &lt;&lt; - many times larger than):<br>
+ <br>
+ <span style="font-family: Courier New,Courier,monospace;">A - B +
+C, where A ~ B and C &lt;&lt; B;</span><br>
+ <br>
+Computing the 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) = (B * re(A) + A * re(B)) / 0 = INF;<br>
+ <br>
+ </span>While doing this from right to left will keep the 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>
+ <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
+it splits expression onto positive and negative partial sums and
+evaluates the
+difference only when the result is required. And did I mention that
+positive and negative values might be of the robust fpt type, that's
+why
+the relative error is always known for the expression result.<br>
+ <h2>Robust Sqrt Expression Structure</h2>
+The robust square root expression structure allows to compute the
+result of
+the expression that contains square roots within defined relative
+error.
+As an example consider the following expression:<br>
+ <br>
+ <span style="font-family: Courier New,Courier,monospace;">A *
+sqrt(a) - B * sqrt(b), A * B &gt; 0, a &gt;= 0, b &gt;= 0;</span><br>
+ <br>
+Computing this expressions directly may apply huge cancellation error,
+however it may be transformed to the next equivalent expression:<br>
+ <span style="font-family: Courier New,Courier,monospace;"><br>
+(A * A * a - B * B * b) / (A * sqrt(a) + B * sqrt(b));</span><br>
+ <br>
+The numerator and denominator of this expression could be computed
+directly as those won't lead to the cancellation errors.<br>
+ <br>
+In general case the robust sqrt expression structure allows to evaluate
+the following set of expressions:<br>
+ <span style="font-family: Courier New,Courier,monospace;"><br>
+sum(A[i] * sqrt(a[i]), i = 1 .. N), N &lt;= 4;</span><br>
+ <br>
+This appears to be enough for the Boost.Polygon Voronoi.<br>
+ </td>
+ </tr>
+ <tr>
+ <td style="background-color: rgb(238, 238, 238);" nowrap="1" valign="top">&nbsp;</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

Date view Thread view Subject view Author view

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