|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r77880 - sandbox/gtl/doc
From: sydorchuk.andriy_at_[hidden]
Date: 2012-04-10 03:13:01
Author: asydorchuk
Date: 2012-04-10 03:12:59 EDT (Tue, 10 Apr 2012)
New Revision: 77880
URL: http://svn.boost.org/trac/boost/changeset/77880
Log:
Trying to fix mime-types issue.
Removed:
sandbox/gtl/doc/voronoi_predicates.htm
sandbox/gtl/doc/voronoi_robust_fpt.htm
Deleted: sandbox/gtl/doc/voronoi_predicates.htm
Deleted: 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
==============================================================================
--- sandbox/gtl/doc/voronoi_predicates.htm 2012-04-10 03:12:59 EDT (Tue, 10 Apr 2012)
+++ (empty file)
@@ -1,244 +0,0 @@
-<!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;">
-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 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 ?< 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 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) ?< 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>
-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. 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"> </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>
==============================================================================
--- sandbox/gtl/doc/voronoi_robust_fpt.htm 2012-04-10 03:12:59 EDT (Tue, 10 Apr 2012)
+++ (empty file)
@@ -1,211 +0,0 @@
-<!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)
-<= 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 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 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, << - 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 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 > 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>
-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 <= 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"> </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