1 <!DOCTYPE HTML PUBLIC
"-//W3C//DTD HTML 4.01 Transitional//EN">
6 <meta http-equiv=
"Content-Language" content=
"en-us">
7 <meta http-equiv=
"Content-Type" content=
"text/html; charset=windows-1252"><title>Voronoi Builder
</title></head><body>
8 <table style=
"margin: 0pt; padding: 0pt; width: 100%;" border=
"0" cellpadding=
"0" cellspacing=
"0">
11 <td style=
"background-color: rgb(238, 238, 238);" nowrap=
"1" valign=
"top">
12 <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>
13 <div style=
"margin: 5px;">
14 <h3 class=
"navbar">Contents
</h3>
16 <li><a href=
"index.htm">Boost.Polygon Main Page
</a></li>
17 <li><a href=
"gtl_design_overview.htm">Design Overview
</a></li>
18 <li><a href=
"gtl_isotropy.htm">Isotropy
</a></li>
19 <li><a href=
"gtl_coordinate_concept.htm">Coordinate Concept
</a></li>
20 <li><a href=
"gtl_interval_concept.htm">Interval Concept
</a></li>
21 <li><a href=
"gtl_point_concept.htm">Point Concept
</a></li>
22 <li><a href=
"gtl_segment_concept.htm">Segment Concept
</a></li>
23 <li><a href=
"gtl_rectangle_concept.htm">Rectangle Concept
</a></li>
24 <li><a href=
"gtl_polygon_90_concept.htm">Polygon
90 Concept
</a></li>
25 <li><a href=
"gtl_polygon_90_with_holes_concept.htm">Polygon
90
26 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
29 With Holes Concept
</a></li>
30 <li><a href=
"gtl_polygon_concept.htm">Polygon Concept
</a></li>
31 <li><a href=
"gtl_polygon_with_holes_concept.htm">Polygon With
32 Holes Concept
</a></li>
33 <li><a href=
"gtl_polygon_90_set_concept.htm">Polygon
90 Set
35 <li><a href=
"gtl_polygon_45_set_concept.htm">Polygon
45 Set
37 <li><a href=
"gtl_polygon_set_concept.htm">Polygon Set Concept
</a></li>
38 <li><a href=
"gtl_connectivity_extraction_90.htm">Connectivity
39 Extraction
90</a></li>
40 <li><a href=
"gtl_connectivity_extraction_45.htm">Connectivity
41 Extraction
45</a></li>
42 <li><a href=
"gtl_connectivity_extraction.htm">Connectivity
44 <li><a href=
"gtl_property_merge_90.htm">Property Merge
90</a></li>
45 <li><a href=
"gtl_property_merge_45.htm">Property Merge
45</a></li>
46 <li><a href=
"gtl_property_merge.htm">Property Merge
</a></li>
47 <li><a href=
"voronoi_main.htm">Voronoi Main Page
</a></li>
48 <li><a href=
"voronoi_benchmark.htm">Voronoi Benchmark
</a> </li>
49 <li>Voronoi Builder
</li>
50 <li><a href=
"voronoi_diagram.htm">Voronoi Diagram
</a></li>
52 <h3 class=
"navbar">Other Resources
</h3>
54 <li><a href=
"GTL_boostcon2009.pdf">GTL Boostcon
2009 Paper
</a></li>
55 <li><a href=
"GTL_boostcon_draft03.pdf">GTL Boostcon
2009
57 <li><a href=
"analysis.htm">Performance Analysis
</a></li>
58 <li><a href=
"gtl_tutorial.htm">Layout Versus Schematic Tutorial
</a></li>
59 <li><a href=
"gtl_minkowski_tutorial.htm">Minkowski Sum Tutorial
</a></li>
60 <li><a href=
"voronoi_basic_tutorial.htm">Voronoi Basic Tutorial
</a></li>
61 <li><a href=
"voronoi_advanced_tutorial.htm">Voronoi Advanced
65 <h3 class=
"navbar">Polygon Sponsor
</h3>
66 <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>
68 <td style=
"padding-left: 10px; padding-right: 10px; padding-bottom: 10px;" valign=
"top" width=
"100%"><!-- End Header --> <br>
69 <h1>Voronoi Builder
</h1>
70 The Voronoi builder is the event generator structure, that implements
71 the
<a href=
"http://en.wikipedia.org/wiki/Sweep_line_algorithm">sweepline
73 scanning
2D space and spawning the two types of events:
<a href=
"http://www.ams.org/samplings/feature-column/fcarc-voronoi">site
74 events and circle events
</a>. Each event is reported to the output data
76 The structure shares Voronoi name, as the events generated by it
78 enough information to construct the Voronoi diagram of a set of points
79 and linear segments. The requirements for the coordinate type of
80 the input/output geometries, configured through the coordinate type
81 traits template argument, are the following:
<br>
83 <li>The input coordinate type (for input points and enpoints of
84 the input segments) is not required to be integral
86 still should be an integer type)
</li>
87 <li>The output coordinate type (for
88 Voronoi vertices) is required to be IEEE-
754 floating point type
</li>
91 The users are encouraged to use the default static methods defined in
92 the
<a href=
"../../../boost/polygon/voronoi.hpp">voronoi.hpp
</a>
93 header for the Voronoi diagram construction. However it's also possible
95 use Voronoi builder explicitly, especially if the user wants to drop
96 the external dependencies such as MPL (metaprogramming library). The
97 following include set doesn't depend on any external headers
98 (except STL and boost/cstdint.hpp), even
99 the Boost.Polygon library:
<br>
101 <span style=
"font-family: Courier New,Courier,monospace;">#include
102 <voronoi_builder.hpp
></span><br style=
"font-family: Courier New,Courier,monospace;">
103 <span style=
"font-family: Courier New,Courier,monospace;">#include
104 <voronoi_diagram.hpp
></span><br>
106 Header:
<a href=
"../../../boost/polygon/voronoi_builder.hpp">boost/polygon/voronoi_builder.hpp
</a><br>
108 <font face=
"Courier New"> <span style=
"font-family: 'Courier New',Courier,monospace;">template
109 <typename T,
</span><br style=
"font-family: 'Courier New',Courier,monospace;">
110 <span style=
"font-family: 'Courier New',Courier,monospace;">
111 typename CTT = detail::voronoi_ctype_traits
<T
>,
</span><br style=
"font-family: 'Courier New',Courier,monospace;">
112 <span style=
"font-family: 'Courier New',Courier,monospace;">
113 typename VP = detail::voronoi_predicates
<CTT
> ></span><br style=
"font-family: 'Courier New',Courier,monospace;">
114 <span style=
"font-family: 'Courier New',Courier,monospace;">class
115 voronoi_builder;
</span><br>
117 <span style=
"font-family: 'Courier New',Courier,monospace;">T
</span></font>
118 - specifies the coordinate type of the input geometries (points and
120 <font face=
"Courier New"> <span style=
"font-family: 'Courier New',Courier,monospace;">CTT
</span></font>
121 - defines the input/output coordinate type traits used by the Voronoi
123 <font face=
"Courier New"> <span style=
"font-family: 'Courier New',Courier,monospace;">VP
</span></font>
124 - the predicate kernel, that contains robust and
125 efficient predicates and functors.
<br>
126 The Voronoi builder data structure is ready to use from the box with
127 32-bit signed integer input coordinate type. The user may extend the
128 input coordinate range to the other integer types (e.g.
64-bit
129 integer), however this will also require manual setup of the
130 coordinate type traits. Default predicate kernel provides correct and
131 efficient predicates as long as types
132 defined by the coordinate type traits satisfy the requirements
133 explained at the end of this page. In case
135 requirements are not satisfied,
<font face=
"Courier New"><span style=
"font-family: 'Courier New',Courier,monospace;"></span></font>
136 the proper predicate kernel
137 implementation is required.
<span style=
"font-family: Courier New,Courier,monospace;"></span><br>
138 <h2>Member Functions
</h2>
139 <table style=
"text-align: left; width: 100%;" border=
"1" cellpadding=
"2" cellspacing=
"2">
142 <td style=
"font-family: 'Courier New',Courier,monospace;"><span style=
"font-weight: bold;">voronoi_builder
</span>()
</td>
143 <td width=
"693">Default
147 <td><span style=
"font-family: Courier New,Courier,monospace;">size_t
<span style=
"font-weight: bold;">insert_point
</span>(const int_type
& x,
<br>
148
149 const int_type
& y)
</span> </td>
150 <td>Inserts a point object with
151 the specified coordinates into the Voronoi builder.
<br>
152 Returns index of the inserted point.
</td>
155 <td><span style=
"font-family: Courier New,Courier,monospace;">size_t
<span style=
"font-weight: bold;">insert_segment
</span>(const int_type
&
157
158 const int_type
& y1,
<br>
159
160 const int_type
& x2,
<br>
161
162 const int_type
& y2)
</span> </td>
163 <td>Inserts a segment object
164 with the specified coordinates into the Voronoi builder.
<br>
165 Returns index of the inserted segment.
</td>
168 <td style=
"font-family: 'Courier New',Courier,monospace;">template
169 <typename OUTPUT
><br>
170 void
<span style=
"font-weight: bold;">construct
</span>(OUTPUT* output)
172 <td width=
"693">Runs the sweepline
173 algorithm over the set of inserted geometries and generates site and
174 circle events to the OUTPUT data structure. It's the responsibility of
176 output data structure to process them.
<br>
177 Complexity: O(N * log N), where N is the total number of input points and segments.
<br>
181 <td style=
"font-family: 'Courier New',Courier,monospace;">void
182 <span style=
"font-weight: bold;">clear
</span>()
</td>
183 <td width=
"693">Clears the
184 list of the inserted geometries. Sets the input geometry index to
189 <h1>Voronoi Coordinate Type Traits
</h1>
190 <p>The library provides the default coordinate type traits
191 specialization for the
192 32-bit signed integer type:
</p>
193 <font style=
"font-family: 'Courier New',Courier,monospace;" face=
"Courier New">
194 <p>template
<typename T
><br>
195 struct voronoi_ctype_traits;
<br>
197 template
<><br>
198 struct voronoi_ctype_traits
<int32
> {
<br>
199 typedef int32 int_type;
<br>
200 typedef int64 int_x2_type;
<br>
201 typedef uint64 uint_x2_type;
<br>
202 typedef extended_int
<128> big_int_type;
<br>
203 typedef fpt64 fpt_type;
<br>
204 typedef extended_exponent_fpt
<fpt_type
>
206 typedef ulp_comparison
<fpt_type
> ulp_cmp_type;
<br>
207 typedef type_converter_fpt to_fpt_converter_type;
<br>
208 typedef type_converter_efpt to_efpt_converter_type;
<br>
211 of the most important features of the library is that Voronoi builder
212 output geometries are constructed within defined relative error (
64
213 machine epsilons). That means, the more mantissa bits the user provided
214 fpt_type has, the better precision of the output geometries will be. In
215 order for the user defined traits to be consistent with the default
216 Voronoi builder predicate kernel user should define the following set
217 of traits (the assumption is made that input geometries have
218 X-bit signed integer coordinate type):
<br>
220 <table style=
"text-align: left; width: 100%;" border=
"1" cellpadding=
"2" cellspacing=
"2">
223 <td style=
"font-family: 'Courier New',Courier,monospace; font-weight: bold;">int_type
225 <td style=
"vertical-align: top;">At least X-bit signed
229 <td style=
"vertical-align: top; font-family: 'Courier New',Courier,monospace; font-weight: bold;">int_x2_type
231 <td style=
"vertical-align: top;">At least
2X-bit signed
235 <td style=
"vertical-align: top; font-family: 'Courier New',Courier,monospace; font-weight: bold;">uint_x2_type
237 <td style=
"vertical-align: top;">At least
2X-bit unsigned
241 <td style=
"vertical-align: top; font-family: 'Courier New',Courier,monospace; font-weight: bold;">big_int_type
243 <td style=
"vertical-align: top;">At least
8X-bit signed
244 integer type if input dataset contains only points.
<br>
245 At least
64X-bit signed integer type if input dataset contains
249 <td style=
"vertical-align: top; font-family: 'Courier New',Courier,monospace; font-weight: bold;">fpt_type
251 <td style=
"vertical-align: top;">IEEE-
754 floating point
252 type, with mantissa at least (X+
16) bits and exponent able to handle
253 32X-bit unsigned integer type.
</td>
256 <td style=
"vertical-align: top; font-family: 'Courier New',Courier,monospace; font-weight: bold;">efpt_type
258 <td style=
"vertical-align: top;">IEEE-
754 floating point
259 type, with mantissa at least (X+
16) bits and exponent able to handle
260 64X-bit unsigned integer type.
</td>
263 <td style=
"vertical-align: top; font-family: 'Courier New',Courier,monospace; font-weight: bold;">ulp_cmp_type
265 <td style=
"vertical-align: top;">Ulp comparison structure,
266 that checks if two fpt_type values are within the given ulp range
267 (relative error range).
</td>
270 <td style=
"vertical-align: top; font-family: 'Courier New',Courier,monospace; font-weight: bold;">to_fpt_converter_type
272 <td style=
"vertical-align: top;">Type converter structure,
273 that converts any of the integer types above plus efpt_type to the
274 fpt_type using operator().
</td>
277 <td style=
"vertical-align: top; font-family: 'Courier New',Courier,monospace; font-weight: bold;">to_efpt_converter_type
279 <td style=
"vertical-align: top;">Type converter structure,
280 that converts any of the integer types above to the efpt_type using
287 <li>Four different integer types are used (instead of a single
288 big_int_type) to slightly improve algorithm performance and memory
290 <li>As the maximum required size of the big_int_type is known
291 in advance, it's possible to use fixed, stack allocated, multiprecision
293 <li>Two separate floating-point types are defined, because for
296 32-bit signed integer coordinates, double type won't be able to handle
297 2048-bit (
64 chunks of
32 bits each) integers, as they will
298 overflow its exponent. On the
299 gcc compiler it's possible to use
80-bit long doubles for both fpt
300 types, however this is not supported by the MSVC compiler.
</li>
301 <li>efpt_type and to_efpt_converter_type are not used to
302 construct the Voronoi diagram of a set of points (mock implementation
304 <li>For an example of the user defined coordinate type traits
305 check the
<a href=
"voronoi_advanced_tutorial.htm">advanced Voronoi
311 <td style=
"background-color: rgb(238, 238, 238);" nowrap=
"1"> </td>
312 <td style=
"padding-left: 10px; padding-right: 10px; padding-bottom: 10px;" valign=
"top" width=
"100%">
313 <table class=
"docinfo" id=
"table2" frame=
"void" rules=
"none">
314 <colgroup> <col class=
"docinfo-name"><col class=
"docinfo-content"> </colgroup> <tbody valign=
"top">
316 <th class=
"docinfo-name">Copyright:
</th>
317 <td>Copyright © Andrii Sydorchuk
2010-
2013.
</td>
320 <th class=
"docinfo-name">License:
</th>
321 <td class=
"field-body">Distributed under the Boost Software
322 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">
323 http://www.boost.org/LICENSE_1_0.txt
</a>)
</td>