|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r77489 - in sandbox/gtl: boost/polygon/detail doc
From: sydorchuk.andriy_at_[hidden]
Date: 2012-03-22 19:15:07
Author: asydorchuk
Date: 2012-03-22 19:15:06 EDT (Thu, 22 Mar 2012)
New Revision: 77489
URL: http://svn.boost.org/trac/boost/changeset/77489
Log:
Adding voronoi main page documentation.
Added:
sandbox/gtl/doc/voronoi_main.htm (contents, props changed)
Text files modified:
sandbox/gtl/boost/polygon/detail/voronoi_predicates.hpp | 14 ++++----------
sandbox/gtl/doc/voronoi_builder.htm | 18 +++++++++---------
sandbox/gtl/doc/voronoi_diagram.htm | 15 ++++++++-------
3 files changed, 21 insertions(+), 26 deletions(-)
Modified: sandbox/gtl/boost/polygon/detail/voronoi_predicates.hpp
==============================================================================
--- sandbox/gtl/boost/polygon/detail/voronoi_predicates.hpp (original)
+++ sandbox/gtl/boost/polygon/detail/voronoi_predicates.hpp 2012-03-22 19:15:06 EDT (Thu, 22 Mar 2012)
@@ -1015,9 +1015,9 @@
c_y -= robust_fpt_type(dif_x1 * sum_x1 * dif_x2, 2.0);
c_y -= robust_fpt_type(dif_y1 * sum_y1 * dif_x2, 2.0);
robust_dif_type lower_x(c_x);
- lower_x -= robust_fpt_type(get_sqrt(sqr_distance(dif_x1, dif_y1) *
- sqr_distance(dif_x2, dif_y2) *
- sqr_distance(dif_x3, dif_y3)), 5.0);
+ lower_x -= robust_fpt_type(get_sqrt((dif_x1 * dif_x1 + dif_y1 * dif_y1) *
+ (dif_x2 * dif_x2 + dif_y2 * dif_y2) *
+ (dif_x3 * dif_x3 + dif_y3 * dif_y3)), 5.0);
c_event = circle_type(c_x.dif().fpv() * inv_orientation.fpv(),
c_y.dif().fpv() * inv_orientation.fpv(),
lower_x.dif().fpv() * inv_orientation.fpv());
@@ -1049,7 +1049,7 @@
to_fpt(site3.point1().y()) - to_fpt(site2.y()),
to_fpt(site2.x()) - to_fpt(site3.point1().x())), 1.0);
robust_fpt_type denom(robust_cross_product(vec_x, vec_y, line_a, line_b), 1.0);
- robust_fpt_type inv_segm_len(to_fpt(1.0) / get_sqrt(sqr_distance(line_a, line_b)), 3.0);
+ robust_fpt_type inv_segm_len(to_fpt(1.0) / get_sqrt(line_a * line_a + line_b * line_b), 3.0);
robust_dif_type t;
if (ot::eval(denom) == ot::COLLINEAR) {
t += teta / (robust_fpt_type(8.0, false) * A);
@@ -1371,12 +1371,6 @@
circle_existence_predicate_type circle_existence_predicate_;
circle_formation_functor_type circle_formation_functor_;
};
-
-private:
- template <typename T>
- static T sqr_distance(T dif_x, T dif_y) {
- return dif_x * dif_x + dif_y * dif_y;
- }
};
} // detail
} // polygon
Modified: sandbox/gtl/doc/voronoi_builder.htm
==============================================================================
--- sandbox/gtl/doc/voronoi_builder.htm (original)
+++ sandbox/gtl/doc/voronoi_builder.htm 2012-03-22 19:15:06 EDT (Thu, 22 Mar 2012)
@@ -5,6 +5,7 @@
+
<meta http-equiv="Content-Language" content="en-us">
<meta http-equiv="Content-Type" content="text/html; charset=windows-1252"><title>Contents</title></head><body>
@@ -311,7 +312,7 @@
</td>
<td style="vertical-align: top;">At least 8X-bit signed integer
type for voronoi of points.<br>
- At least 128X-bit signed integer type for voronoi of segments.<br>
+ At least 64X-bit signed integer type for voronoi of segments.<br>
</td>
</tr>
<tr>
@@ -319,7 +320,7 @@
fpt_type<br>
</td>
<td style="vertical-align: top;">IEEE-754 floating point type,
- with mantissa at least (X+20) bits and exponent able to handle
+ with mantissa at least (X+16) bits and exponent able to handle
32X-bit unsigned integer type.<br>
</td>
</tr>
@@ -328,8 +329,7 @@
efpt_type<br>
</td>
<td style="vertical-align: top;">IEEE-754 floating point type,
- with mantissa at least (X+20) bits and exponent able to handle
- 128X-bit unsigned integer type.<br>
+ with mantissa at least (X+16) bits and exponent able to handle 64X-bit unsigned integer type.<br>
</td>
</tr>
<tr>
@@ -374,11 +374,11 @@
2) As maximum required size of the big_int_type is known in advance
library provided implementation of fixed integers could be used, which
is much faster than heap-allocated big integers.<br>
- 3) two separate floating-point types are defined because for input with
- 32-bit signed integer coordinates double won't be able to handle
- 4096-bit (128 * 32) integers as they will overflow its exponent. On the
- gcc compiler it's possible to use 80-bit long doubles for both fpt
- types, however this is not supported by msvc compiler.<br>
+3) two separate floating-point types are defined because for input with
+32-bit signed integer coordinates double won't be able to handle
+2048-bit (64 * 32) integers as they will overflow its exponent. On the
+gcc compiler it's possible to use 80-bit long doubles for both fpt
+types, however this is not supported by msvc compiler.<br>
4) efpt_type and to_efpt_converter_type are not used to construct
Voronoi of points (mocks will work fine).<br>
5) for an example of the user defined builder coordinate type traits see
Modified: sandbox/gtl/doc/voronoi_diagram.htm
==============================================================================
--- sandbox/gtl/doc/voronoi_diagram.htm (original)
+++ sandbox/gtl/doc/voronoi_diagram.htm 2012-03-22 19:15:06 EDT (Thu, 22 Mar 2012)
@@ -17,6 +17,7 @@
+
<meta http-equiv="Content-Language" content="en-us">
<meta http-equiv="Content-Type" content="text/html; charset=windows-1252"><title>Contents</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>
@@ -559,44 +560,44 @@
<table style="text-align: left; width: 100%;" border="1" cellpadding="2" cellspacing="2">
<tbody>
<tr>
- <td style="vertical-align: top;">coordinate_type<br>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">coordinate_type<br>
</td>
<td style="vertical-align: top;">The main coordinate type of the voronoi diagram internal structures.<br>
</td>
</tr>
<tr>
- <td style="vertical-align: top;">ctype_converter_type<br>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">ctype_converter_type<br>
</td>
<td style="vertical-align: top;">Coordinate type converter structure.<br>
Converts coordinates provided by Voronoi builder to the internal coordinate type.<br>
</td>
</tr>
<tr>
- <td style="vertical-align: top;">point_type<br>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">point_type<br>
</td>
<td style="vertical-align: top;">2D point data structure.<br>
</td>
</tr>
<tr>
- <td style="vertical-align: top;">cell_type<br>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">cell_type<br>
</td>
<td style="vertical-align: top;">Voronoi cell type.<br>
</td>
</tr>
<tr>
- <td style="vertical-align: top;">vertex_type<br>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">vertex_type<br>
</td>
<td style="vertical-align: top;">Voronoi vertex_type.<br>
</td>
</tr>
<tr>
- <td style="vertical-align: top;">edge_type<br>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">edge_type<br>
</td>
<td style="vertical-align: top;">Voronoi edge_type.<br>
</td>
</tr>
<tr>
- <td style="vertical-align: top;">vertex_equality_predicate_type<br>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">vertex_equality_predicate_type<br>
</td>
<td style="vertical-align: top;">Predicate that returns true if two points are considered to be equal.<br>
This is used to unite nearby voronoi vertices.<br>
Added: sandbox/gtl/doc/voronoi_main.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_main.htm 2012-03-22 19:15:06 EDT (Thu, 22 Mar 2012)
@@ -0,0 +1,254 @@
+<!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><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>Voronoi Main Page<br>
+
+</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<br>
+</h1>The Boost.Polygon Voronoi library provides functionality to construct Voronoi diagrams
+of a set of points and segments in 2D space with the following set of
+limitations: 1) coordinates of input points and endpoints of segments
+should be of integer type; 2) input segments should not intersect
+except their endpoints. While the first restriction is permanent (it
+allows to give waranties for algorithm output precision and execution),
+the second one may be waved in the future releases. Strong sides of the
+library and main benefits comparing to other implementations are
+discussed in the following paragraphs.<br>
+ <h1>Robustness and efficiency</h1>
+Lets explain a bit those terms. The efficiency is simply measured by
+the time it takes the algorithm to execute. The robustness is a bit
+more harder to explain. But those of you who had experience with
+the following situations would understand what it doesn't mean:
+application segfaults randomly, the algorithm output contains
+degeneracies for some inputs, the algorithm produces wrong output for
+some inputs (e.g. point is considered to be outside of the polygon,
+while should be inside). In other words robust implementation doesn't
+fail and produces valid output in 100% of cases, thus user can rely on
+it. Robustness is the weak place of the most non-commercial
+implementations of any complex geometric algorithm. The main issues of
+that could be devided onto two main categories: memory management
+issues, numeric stability issues. Voronoi implementation avoids the
+first type of issues using pure STL data structure, thus you won't find
+any operator new in the code. The second category of problems is
+resolved using multi-precision geometric predicates.
+Even for commercial implementations usage of such predicates usually
+results in huge performance slowdown. Here is another strong side of
+Voronoi: we avoid multiprecision computations in 95% of cases using
+extremely fast floating-point predicates. Yes, those are not always
+exact, but we developed relative error arithmetic apparatus to identify them and switch to higher precision predicates when required.<br>
+ <h1>Precision of output structures<br>
+ </h1>
+
+One of the extremely important results of using two types of predicates
+is that library efficiently computes relatively precise coordinates of
+the output geometries. Here we will explain a bit what exactly
+"relatively precise" means and how received output may differ from
+theoretically correct one (here and after we assume that output
+coordinate type is IEEE-754 floating-point type).<br>
+Voronoi implementation guaranties that relative error of the output
+geometries coordinates is always not higher then 64 machine epsilons (6
+bits of mantissa), while in many cases it is slightly less. That also
+means that using floating-point type with larger mantissa will produce
+more precise output. Lets consider following example: output Voronoi
+vertex has double (53 bit mantissa) x-coordinate equal to 1.0, then
+absolute error is at most 2^-53 * 2^6 = 2^-47 and exact value of
+x-coordinate lies in the range [1.0 - 2^-47, 1.0 + 2^-47]. For
+x-coordinate equal to 2^31, the absolute error will be at most 2^-53 *
+2^31 * 2^6 = 2^-16 and exact value of x-coordinate lies in the range
+[2^31 - 2^-16, 2^31 + 2^16]. For output Voronoi vertex with long double
+(64 bit mantissa) x-coordinate equal to 2^31, the absolute error will
+be at most 2^-64 * 2 ^31 * 2^6 = 2^-27 and exact value of x-coordinate
+lies in the range [2^31-2^-27, 2^31+2^-27].<br>
+During finalization step library unites Voronoi vertices whose both
+coordinates are situated within relative error range equal to 128
+machine epsilons and removes any voronoi edges between them. That is
+the only case that might cause differences between algorithm output
+topology and the precise one. Now lets see what is the practical
+impact of this. Consider following example: we are going to construct
+Voronoi diagram of our Solar System. The radius of our solar system is
+approximately 2^42 meters, and we are going to snap it to the integer
+grid of [-2^42; 2^42] x [-2^42; 2^42]. Lets choose long double
+(64 bit mantissa) output coordinate type, then maximum absolute error
+for output geometries within our solar system will be on its boundary
+and equal to 2^-64 * 2^42 * 2^6 = 2^-18. In the output we are going to
+consider vertices with both coordinates that are within 2^-17 meters (8
+micrometers) distance to be equal. Come on that distance is equal to
+the size of bacteria. Can you even see those? I hope such overview
+convinced most pessimistic readers to give a try to our library.<br>
+ <h1>Fully functional with segment inputs</h1>
+There are not many implementations of Voronoi diagrams that could
+handle segment inputs, even considering commercial ones. Support of
+segments allows to discretize any input geometry (circle, elipse,
+parabola). Of course as the result those might have floating-point
+coordinates, but that is resolved using scaling and snapping to the
+integer grid. This functionality is very handy as allows to compute
+medial axis transform of the arbitrary input geometry. So one may start
+using it for the next generation pattern recognition or computer vision
+project.<br>
+ <h1>Basic and advanced usage cases</h1>
+ <h1>Extendable for user provided coordinate types</h1>
+Voronoi implementation is coordinate type agnostic. That means that as soon as user provided types satisfy set of Voronoi builder coordinate type traits restrictions
+and implement library required methods no changes are requied neither
+from algorithm, nor from predicates implementation. So it's possible to
+construct Voronoi diagram for 256 bit integer input coordinate type and
+512 bit output floating-pont type without changing any internal code.<br>
+
+ <h1>Bright future<br>
+ </h1>
+Below one may find list of main directions for the future development of the library.<br>
+ <br>
+High-priority tasks that already have approximate implementation plan:<br>
+ <ul>
+ <li>Implementing Delaunay triangulation data structure.<br>
+Note: only data structure needs to be implemented that properly processes events provided by Voronoi builder.</li>
+ <li>Implementing medial axis transform data structure.<br>
+Note: in general case Voronoi diagram has completely the same geometry
+as medial axis (they are 100% equal), however for many applications
+user is not interested in diagram inside hole regions. The main point
+of this data structure is to automatically filter Voronoi edges that
+belong to those areas.</li>
+ <li>Implementing data structure built on top of Voronoi diagram that allows to execute nearest neighbour queries in O(log N) time.<br>
+Note: this would be sort of kd-tree data structure built on top of bounding rectangles around Voronoi cells.</li>
+ <li>Providing interface to retrieve convex hull of a set of
+points and segments from Voronoi builder one's the Voronoi diagram is
+constructed in O(N) time.</li>
+ <li>Dropping restriction on non-intersecting input geometries.<br>
+Note: this means that library will also compute segment intersections if such exist.</li>
+ <li>Closer integration with interfaces and functionality of Boost Polygon.<br>
+ </li>
+ </ul>
+High-priority tasks to be considered:<br>
+ <ul>
+ <li>Integration of Voronoi diagram structure with BGL library.</li>
+ <li>Support of other types of distance metrics.</li>
+ <li>Construction of constrained Delaunay triangulation.</li>
+ <li>Support of circle input geometries.</li>
+ </ul>
+Based on the community suggestions priorities may be changed.<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