1 <!DOCTYPE HTML PUBLIC
"-//W3C//DTD HTML 4.01 Transitional//EN">
3 <meta http-equiv=
"Content-Language" content=
"en-us">
4 <meta http-equiv=
"Content-Type" content=
"text/html; charset=windows-1252"><title>Voronoi Main
</title>
5 <meta http-equiv=
"content-type" content=
"text/html; charset=utf-8">
6 <meta http-equiv=
"content-type" content=
"text/html; charset=utf-8">
7 <meta http-equiv=
"content-type" content=
"text/html; charset=utf-8">
8 <meta http-equiv=
"content-type" content=
"text/html; charset=utf-8"></head><body>
9 <table style=
"margin: 0pt; padding: 0pt; width: 100%;" border=
"0" cellpadding=
"0" cellspacing=
"0">
12 <td style=
"background-color: rgb(238, 238, 238);" nowrap=
"1" valign=
"top">
13 <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>
14 <div style=
"margin: 5px;">
15 <h3 class=
"navbar">Contents
</h3>
17 <li><a href=
"index.htm">Boost.Polygon Main Page
</a></li>
18 <li><a href=
"gtl_design_overview.htm">Design Overview
</a></li>
19 <li><a href=
"gtl_isotropy.htm">Isotropy
</a></li>
20 <li><a href=
"gtl_coordinate_concept.htm">Coordinate Concept
</a></li>
21 <li><a href=
"gtl_interval_concept.htm">Interval Concept
</a></li>
22 <li><a href=
"gtl_point_concept.htm">Point Concept
</a></li>
23 <li><a href=
"gtl_segment_concept.htm">Segment Concept
</a></li>
24 <li><a href=
"gtl_rectangle_concept.htm">Rectangle Concept
</a></li>
25 <li><a href=
"gtl_polygon_90_concept.htm">Polygon
90 Concept
</a></li>
26 <li><a href=
"gtl_polygon_90_with_holes_concept.htm">Polygon
90 With Holes Concept
</a></li>
27 <li><a href=
"gtl_polygon_45_concept.htm">Polygon
45 Concept
</a></li>
28 <li><a href=
"gtl_polygon_45_with_holes_concept.htm">Polygon
45 With Holes Concept
</a></li>
29 <li><a href=
"gtl_polygon_concept.htm">Polygon Concept
</a></li>
30 <li><a href=
"gtl_polygon_with_holes_concept.htm">Polygon With Holes Concept
</a></li>
31 <li><a href=
"gtl_polygon_90_set_concept.htm">Polygon
90 Set Concept
</a></li>
32 <li><a href=
"gtl_polygon_45_set_concept.htm">Polygon
45 Set Concept
</a></li>
33 <li><a href=
"gtl_polygon_set_concept.htm">Polygon Set Concept
</a></li>
34 <li><a href=
"gtl_connectivity_extraction_90.htm">Connectivity Extraction
90</a></li>
35 <li><a href=
"gtl_connectivity_extraction_45.htm">Connectivity Extraction
45</a></li>
36 <li><a href=
"gtl_connectivity_extraction.htm">Connectivity Extraction
</a></li>
37 <li><a href=
"gtl_property_merge_90.htm">Property Merge
90</a></li>
38 <li><a href=
"gtl_property_merge_45.htm">Property Merge
45</a></li>
39 <li><a href=
"gtl_property_merge.htm">Property Merge
</a></li>
40 <li>Voronoi Main Page
</li>
41 <li><a href=
"voronoi_benchmark.htm">Voronoi Benchmark
</a></li>
42 <li><a href=
"voronoi_builder.htm">Voronoi Builder
</a> </li>
43 <li><a href=
"voronoi_diagram.htm">Voronoi Diagram
</a></li>
45 <h3 class=
"navbar">Other Resources
</h3>
47 <li><a href=
"GTL_boostcon2009.pdf">GTL Boostcon
2009 Paper
</a></li>
48 <li><a href=
"GTL_boostcon_draft03.pdf">GTL Boostcon
2009 Presentation
</a></li>
49 <li><a href=
"analysis.htm">Performance Analysis
</a></li>
50 <li><a href=
"gtl_tutorial.htm">Layout Versus Schematic Tutorial
</a></li>
51 <li><a href=
"gtl_minkowski_tutorial.htm">Minkowski Sum Tutorial
</a></li>
52 <li><a href=
"voronoi_basic_tutorial.htm">Voronoi Basic Tutorial
</a></li>
53 <li><a href=
"voronoi_advanced_tutorial.htm">Voronoi Advanced Tutorial
</a></li>
56 <h3 class=
"navbar">Polygon Sponsor
</h3>
57 <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>
59 <td style=
"padding-left: 10px; padding-right: 10px; padding-bottom: 10px;" valign=
"top" width=
"100%"><!-- End Header --> <br>
60 <h1>THE BOOST POLYGON VORONOI EXTENSIONS
</h1>
61 <img style=
"width: 900px; height: 300px;" alt=
"" src=
"images/voronoi3.png"><br>
62 The Voronoi extensions of the Boost Polygon library provide functionality to
63 construct a
<a href=
"voronoi_diagram.htm">Voronoi diagram
</a> of a set of points
64 and linear segments in
2D space with the following set of limitations:
<br>
66 <li>Coordinates of the input points and endpoints of the input segments should have integral type. The int32 data type is supported by the default implementation. Support for the other data types (e.g. int64) could be achieved through the configuration of the coordinate type traits (
<a href=
"voronoi_advanced_tutorial.htm">Voronoi Advanced tutorial
</a>).
</li>
67 <li>Input points and segments should not overlap except their endpoints. This means that input point should not lie inside the input segment and input segments should not intersect except their endpoints.
</li>
69 While the first restriction is permanent (it
70 allows to give the exact warranties about the output precision and
71 algorithm execution flow),
72 the second one may be resolved using the Boost.Polygon
<a href=
"gtl_segment_concept.htm">segment utils
</a>.
73 The strong sides of the
74 library and the main benefits comparing to the other implementations are
75 discussed in the following paragraphs.
<br>
76 <h2>Fully Functional with Segments
</h2>
77 There are just a few implementations of the Voronoi diagram
80 handle input data sets that contain linear segments, even considering
84 segments allows to discretize any input geometry (sampled
85 floating-point coordinates can be scaled and snapped to the integer
86 grid): circle, ellipse,
87 parabola. This functionality allows to compute
88 the medial axis transform of the arbitrary set of input geometries,
89 with direct applications in the computer vision
91 <h2>Robustness and Efficiency
</h2>
92 Robustness issues can be divided onto the two main categories: memory
94 issues and numeric stability issues. The implementation avoids the
95 first type of the issues using pure STL data structures, thus there is
97 presence of the new operator in the code. The second category of
99 resolved using the multiprecision geometric
101 Even for the commercial libraries, usage of such predicates
102 results in a vast performance slowdown. The library implementation
103 overcomes this by avoiding the multiprecision
104 computations in the
95% of the cases by
105 using the efficient, floating-point based predicates. Such predicates
107 produce the correct result always, however the library embeds the
109 error arithmetic apparatus to identify such situations and switch
111 higher precision predicates when appropriate. As the result, the
112 implementation has a solid performance comparing to the other known
113 libraries (more details in the
<a href=
"voronoi_benchmark.htm">benchmarks
</a>).
<br>
114 <h2>Precision of the Output Structures
</h2>
115 The implementation guaranties, that the relative error of the
116 coordinates of the output
117 geometries is at most
64 machine epsilons (
6
118 bits of mantissa, for the IEEE-
754 floating-point type), while on
119 average it's slightly lower. This means, that the precision of the
121 geometries can be increased simply by using a floating-point type with
122 the larger mantissa. The practical point of this statements is
123 explained in the following table:
<br>
124 <table style=
"text-align: left; width: 100%;" border=
"1" cellpadding=
"2" cellspacing=
"2">
127 <td style=
"vertical-align: top;">Output Coordinate Type
</td>
128 <td style=
"vertical-align: top;">Output Coordinate Value
</td>
129 <td style=
"vertical-align: top;">Max Absolute Error
</td>
130 <td style=
"vertical-align: top;">Precise Value Range
</td>
133 <td style=
"vertical-align: top;">double (
53 bit mantissa)
</td>
134 <td style=
"vertical-align: top;">1 </td>
135 <td style=
"vertical-align: top;">2<sup>-
53</sup> *
2<sup>6</sup>
136 =
2<sup>-
47</sup></td>
137 <td style=
"vertical-align: top;">1 ±
2<sup>-
47</sup></td>
140 <td style=
"vertical-align: top;">double (
53 bit mantissa)
</td>
141 <td style=
"vertical-align: top;">2<sup>31</sup> </td>
142 <td style=
"vertical-align: top;">2<sup>-
53</sup> *
2<sup>31</sup>
143 *
2<sup>6</sup> =
2<sup>-
16</sup></td>
144 <td style=
"vertical-align: top;">2<sup>31</sup> ±
2<sup>-
16</sup></td>
147 <td style=
"vertical-align: top;">long double (
64 bit
149 <td style=
"vertical-align: top;">1 </td>
150 <td style=
"vertical-align: top;">2<sup>-
64</sup> *
2<sup>6</sup>
151 =
2<sup>-
58</sup></td>
152 <td style=
"vertical-align: top;">1 ±
2<sup>-
58</sup></td>
155 <td style=
"vertical-align: top;">long double (
64 bit
157 <td style=
"vertical-align: top;">2<sup>31</sup></td>
158 <td style=
"vertical-align: top;">2<sup>-
64</sup> *
2<sup>31</sup>
159 *
2<sup>6</sup> =
2<sup>-
27</sup></td>
160 <td style=
"vertical-align: top;">2<sup>31</sup> ±
2<sup>-
27</sup></td>
164 Detailed description of the absolute and relative errors evaluation can
165 be found in the article:
<a href=
"http://docs.oracle.com/cd/E19957-01/806-3568/ncg_goldberg.html">"What
166 Every Computer Scientist Should Know About Floating-Point Arithmetic"</a><a href=
"http://docs.oracle.com/cd/E19957-01/806-3568/ncg_goldberg.html"></a>.
<br>
168 During the finalization step the implementation unites Voronoi vertices whose both
169 coordinates are located within the relative error range equal to
128
170 machine epsilons and removes any Voronoi edges between those. This is
171 the only case, that might cause differences between the algorithm output
172 topology and theoretically precise one, and practically means the
173 following: for a Voronoi diagram of a set of solid bodies inside the
174 Solar System (radius
2<sup>42</sup> metres) and the long double (
64 bit
175 mantissa) output coordinate type the maximum absolute error within the
176 Solar System rectangle will be equal to
2<sup>-
64</sup> *
2<sup>42</sup>
177 *
2<sup>6</sup> =
2<sup>-
18</sup> metres; as the result, vertices with
178 both coordinates that are within
2<sup>-
18</sup> metres (
8
179 micrometres or the size of a bacteria) will be considered
180 equal and united.
<br>
181 <h2>Simple Interface
</h2>
182 The
<a href=
"../../../boost/polygon/voronoi.hpp">boost/polygon/
</a><a href=
"../../../boost/polygon/voronoi.hpp">voronoi.hpp
</a>
183 library header defines the following static functions to integrate the
184 Voronoi extensions functionality with the Boost.Polygon interfaces:
<br>
186 <table style=
"text-align: left; width: 100%;" border=
"1" cellpadding=
"2" cellspacing=
"2">
189 <td style=
"font-family: Courier New,Courier,monospace;">template
190 <typename Point, typename VB
><br>
191 size_t
<span style=
"font-weight: bold;">insert
</span>(const Point
192 &point, VB *vb)
</td>
193 <td>Inserts a point into a Voronoi builder data structure.
<br>
194 Point type should model the point concept.
<br>
195 Returns index of the inserted site.
</td>
198 <td style=
"font-family: Courier New,Courier,monospace;">template
199 <typename PointIterator, typename VB
><br>
200 void
<span style=
"font-weight: bold;">insert
</span>(PointIterator
202
203 PointIterator last,
<br>
204 VB
206 <td>Inserts an iterator range of points into a Voronoi
207 builder data structure.
<br>
208 Corresponding point type should model the point concept.
</td>
211 <td style=
"font-family: Courier New,Courier,monospace;">template
212 <typename Segment, typename VB
><br>
213 size_t
<span style=
"font-weight: bold;">insert
</span>(const Segment
214 &segment, VB *vb)
</td>
215 <td>Inserts a segment into a Voronoi builder data
217 Segment type should model the segment concept.
<br>
218 Returns index of the inserted site.
</td>
221 <td style=
"font-family: Courier New,Courier,monospace;">template
222 <typename SegmentIterator, typename VB
><br>
223 void
<span style=
"font-weight: bold;">insert
</span>(SegmentIterator
225
226 SegmentIterator last,
<br>
227 VB
229 <td>Inserts an iterator range of segments into a Voronoi
230 builder data structure.
<br>
231 Corresponding segment type should model the segment concept.
</td>
234 <td style=
"font-family: Courier New,Courier,monospace;">template
235 <typename PointIterator, typename VD
><br>
236 void
<span style=
"font-weight: bold;">construct_voronoi
</span>(PointIterator
237 first,
<br>
238 PointIterator last,
<br>
239
241 <td>Constructs a Voronoi diagram of a set of points.
<br>
242 Corresponding point type should model the point concept.
<br>
243 Complexity: O(N * log N), memory usage: O(N), where N is the total number of input points.
<br>
247 <td style=
"font-family: Courier New,Courier,monospace;">template
248 <typename SegmentIterator, typename VD
><br>
249 void
<span style=
"font-weight: bold;">construct_voronoi
</span>(SegmentIterator
250 first,
<br>
251 SegmentIterator last,
<br>
252
254 <td>Constructs a Voronoi diagram of a set of segments.
<br>
255 Corresponding segment type should model the segment concept.
<br>
256 Complexity: O(N * log N), memory usage: O(N), where N is the total number of input segments.
<br>
260 <td style=
"font-family: Courier New,Courier,monospace;">template
261 <typename PointIterator,
<br>
262 typename
264 typename VD
><br>
265 void
<span style=
"font-weight: bold;">construct_voronoi
</span>(PointIterator
266 p_first,
<br>
267 PointIterator p_last,
<br>
268
269 SegmentIterator s_first,
<br>
270
271 SegmentIterator s_last,
<br>
272
275 Constructs a Voronoi diagram of a set of points and segments.
<br>
276 Corresponding point type should model the point concept.
<br>
277 Corresponding segment type should model the segment concept.
<br>
278 Complexity: O(N* log N), memory usage: O(N), where N is the total number of input points and segments.
<br>
284 The following two lines of code construct a Voronoi diagram of a set of
285 points (as long as the corresponding input geometry type satisfies the
286 Boost.Polygon
<a href=
"gtl_design_overview.htm">concept model
</a>):
<br>
288 <span style=
"font-family: Courier New,Courier,monospace;">voronoi_diagram
<double
>
289 vd;
</span><br style=
"font-family: Courier New,Courier,monospace;">
290 <span style=
"font-family: Courier New,Courier,monospace;">construct_voronoi(points.begin(),
291 points.end(),
&vd);
</span><br>
293 The library provides the clear interfaces to associate the user data
295 output geometries and efficiently traverse
298 More details on those topics are covered in the
<a href=
"voronoi_basic_tutorial.htm">basic Voronoi tutorial
</a>. Advanced
299 usage of the library with the configuration of the coordinate
300 types is explained in the
<a href=
"voronoi_advanced_tutorial.htm">advanced
301 Voronoi tutorial
</a>.
302 The library allows users to implement their own Voronoi diagram /
303 Delaunay triangulation construction routines based on the
<a href=
"voronoi_builder.htm">Voronoi builder API
</a>.
<br>
304 <h2>No Third Party Dependencies
</h2>
305 The Voronoi extensions of the Boost Polygon library doesn't depend on
307 and contains single dependency on the Boost libraries:
309 All the required multiprecision types and related functionality are
311 part of the implementation. The library is fast to compile (
3 public
312 and
4 private heades), has strong cohesion between its components and
313 is clearly modularized from the rest of the Boost Polygon library, with
314 the optional integration through the
<a href=
"../../../boost/polygon/voronoi.hpp">voronoi.hpp
</a> header.
<br>
315 <h2>Extensible for the User Provided Coordinate Types
</h2>
316 The implementation is coordinate type agnostic. As long
317 as the user provided types satisfy the set of the requirements of the
<a href=
"voronoi_builder.htm">Voronoi builder
</a> coordinate type traits, no additional changes are required
318 neither to the algorithm, nor to the implementation of the predicates.
319 For example, it's possible to
320 construct the Voronoi diagram with the
256-bit integer input coordinate
321 type and
512-bit output floating-point type without making any changes to the
323 <h2>Future Development
</h2>
324 Below one may find the list of the possible directions for the future
325 development of the library.
<br>
327 <li>Delaunay triangulation data structure implementation.
</li>
328 <li>Medial axis data structure implementation.
</li>
329 <li>Serialization utilities for the Voronoi diagram data structure.
</li>
330 <li>Drop the restriction on the non-intersecting input geometries.
</li>
331 <li>Support for the different types of the distance metrics.
</li>
333 <h2>Theoretical Research
</h2>
334 The Voronoi extensions were developed as part of the Google Summer of Code
2010.
335 The library was actively maintained for the last three years and involved deep
336 mathematical research in the field of algorithms, data structures, relative
337 error arithmetic and numerical robustness. Upon the community request,
338 more details on the theoretical aspects of the implementation will be published.
339 The authors would like to acknowledge the Steven Fortune's article
340 "<a href="http://dl.acm.org/citation.cfm?id=
10549">A Sweepline algorithm for Voronoi diagrams</a>",
341 that covers fundamental ideas of the current implementation.
</td>
344 <td style=
"background-color: rgb(238, 238, 238);" nowrap=
"1"> </td>
345 <td style=
"padding-left: 10px; padding-right: 10px; padding-bottom: 10px;" valign=
"top" width=
"100%">
346 <table class=
"docinfo" id=
"table2" frame=
"void" rules=
"none">
347 <colgroup> <col class=
"docinfo-name"><col class=
"docinfo-content"> </colgroup> <tbody valign=
"top">
349 <th class=
"docinfo-name">Copyright:
</th>
350 <td>Copyright © Andrii Sydorchuk
2010-
2013.
</td>
353 <th class=
"docinfo-name">License:
</th>
354 <td class=
"field-body">Distributed under the Boost Software
355 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">
356 http://www.boost.org/LICENSE_1_0.txt
</a>)
</td>
projects / ceph.git / blob