|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r77123 - sandbox/gtl/doc
From: sydorchuk.andriy_at_[hidden]
Date: 2012-02-26 17:04:19
Author: asydorchuk
Date: 2012-02-26 17:04:18 EST (Sun, 26 Feb 2012)
New Revision: 77123
URL: http://svn.boost.org/trac/boost/changeset/77123
Log:
Adding documentation page for voronoi robust fpt.
Updating documentation page for voronoi predicates.
Fixing links on index page.
Added:
sandbox/gtl/doc/voronoi_predicates.htm (contents, props changed)
sandbox/gtl/doc/voronoi_robust_fpt.htm (contents, props changed)
Text files modified:
sandbox/gtl/doc/index.htm | 12 ++++++++----
1 files changed, 8 insertions(+), 4 deletions(-)
Modified: sandbox/gtl/doc/index.htm
==============================================================================
--- sandbox/gtl/doc/index.htm (original)
+++ sandbox/gtl/doc/index.htm 2012-02-26 17:04:18 EST (Sun, 26 Feb 2012)
@@ -1,12 +1,13 @@
<!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>
+
+
<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">
<div style="padding: 5px;" align="center">
@@ -45,11 +46,14 @@
<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<br />
</li>
- <li><a href="voronoi_lazy_arithmetic.htm">Voronoi Lazy Arithmetic<br />
-</a></li>
+
+
</ul>
<h3 class="navbar">Other Resources</h3>
<ul>
Added: sandbox/gtl/doc/voronoi_predicates.htm
Added: sandbox/gtl/doc/voronoi_robust_fpt.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_predicates.htm 2012-02-26 17:04:18 EST (Sun, 26 Feb 2012)
@@ -0,0 +1,190 @@
+<!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>Voronoi Main</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 Predicates<br>
+</h1>In mathematical theory predicate is an operator which returns true or false.<br>
+Voronoi predicates contain implementation of a set of geometric
+predicates used by Voronoi builder. Except of those it also provides
+functors that allow to compute coordinates of centers of inscribed
+circles (those correspond to the voronoi vertices) within the given
+relative error precision range for both point and segment inputs. This
+is a very handy functionality as it allows to improve output precision
+simply providing 3rd party IEEE-754 like floating-point types.<br>
+ <h1>Geometric Predicates</h1>
+The main issues with implementation of any complex geometric
+algorithm arise when dealing with robustness of geometric predicates. Usually this
+is also the point where commercial projects stand strong agains noncommercial implementations (it's not the case with Voronoi).
+For the short example let's consider following code snippet, that could be used to compute orientation of 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;"> 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>
+ int v = 1 << 30; // 2 ^ 30<br>
+ 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>
+ printf("%.3f", result);<br>
+ 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 exectuion:
+corrupting algorithm underlying structures or producing completely
+invalid output. Voronoi uses
+slightly more complex predicates. To insure that they are robust and
+efficient approach that combines two known techniques is used: lazy
+arithmetic and multiple
+precision computations.<br>
+
+ <h1>Lazy Arithmetic</h1>Lazy
+arithmetic is based on usage of IEEE-754 floating-point types to
+compute expression results. 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 evaluated result belongs to and based on that we can
+come up with two decisions: 1) output the value; 2) recompute the
+expression using multi precision types. The way relative errors are
+evaluated is explained in the Voronoi Robust FPT section.<br>
+<h1>Multiple Precision arithmetic</h1>In the vast majority of cases
+lazy arithmetic approach produces correct result thus furhter
+processing is not required. In other cases Voronoi specific 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 devided onto two categories:<br>
+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>
+ <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><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.
+The predicate that doesn't fall into the first category is responsible
+for Voronoi circle comparison. 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 falt in
+the first category. The main reasons for this are: 1) algorithm
+operates with integer coordinate type of 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;"><br>
+ </span>
+</td></tr><tr><td style="background-color: rgb(238, 238, 238);" nowrap="1" valign="top"><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>
+ <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
==============================================================================
--- (empty file)
+++ sandbox/gtl/doc/voronoi_robust_fpt.htm 2012-02-26 17:04:18 EST (Sun, 26 Feb 2012)
@@ -0,0 +1,196 @@
+<!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>Voronoi Main</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 Robust FPT</h1>
+ Voronoi
+robust floating-point types represents set of classes and tools that
+allow to estimate relative error of arithmetic expressions. It is
+assumed that other Boost libraries may find this unit functionality
+extremely useful. One can use them to implement robust and efficient
+arithmetic predicates or functors that compute values with predefined
+relative error.<br>
+
+ <h1>Robust Fpt Type</h1>
+Robust
+fpt (robust floating-point type)
+- represents IEEE-754 floating-point type wrapper that also contains
+information on the current relative error of underlying value. The
+implementation overloads 5 standard operations: +, -, *, /, sqrt and
+apart from evaluating expression value also computes its relativer
+error. Let's consider two values A and B; C - rounding error; re
+- correspond to relative error, then following rules apply:<br>
+ <br>
+ <span style="font-family: Courier New,Courier,monospace;">re(A+B) <= max(re(A), re(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) <= (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>
+ <br>
+ </span>The constant C is equal to the rounding relative error
+which for the above set of arithmetic operations in the IEEE-754
+floating-point implementation should be equal to 1 machine epsilon. <br>
+
+
+ <h1>Robust Difference Type</h1>Robust difference type -
+represents expression wrapper that holds positive and negative partial
+sums of the expression in a separate values in order to avoid
+cancellation errors before evaluating final difference.<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, while it could be a lot smaller;<br>
+2) relative error estimate of the expression depends on the order operations are evaluated;<br>
+3) relative error of difference of two positive numbers may be
+exteremely large in case threir values are close to each other (this is
+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>
+ <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>
+ <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>
+ <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 the expression values onto positive and negative, partially
+overloads four arithmetic operations: +,-,*,/ and evaluates the
+diference only when the result is required. And did I mention that
+positive and negative values might be of robust fpt type, that's why
+relative error is always known for the expression result.<br>
+<h1>Robust Sqrt Expression Structure</h1>
+Robust square root expression structure allows evaluate results of
+expressions that contain square roots with predefined relative error.
+As an example consider following expression:<br>
+ <br>
+ <span style="font-family: Courier New,Courier,monospace;">A * sqrt(a) - B * sqrt(b), A * B > 0, a >= 0, b >= 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>
+Numerator and denominator of this epxression could be computed directly as those won't lead to the cancellation errors.<br>
+In general case robust sqrt expression structure allows to evaluate next set of expressions:<br>
+ <span style="font-family: Courier New,Courier,monospace;"><br>
+sum(A[i] * sqrt(a[i]), i = 1 .. N), N <= 4;</span><br>
+ <br>
+This appears to be enough for the Voronoi.<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