]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"> |
2 | <html><head> | |
3 | ||
4 | ||
5 | ||
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"> | |
9 | <tbody> | |
10 | <tr> | |
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> | |
15 | <ul> | |
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 | |
34 | Concept</a></li> | |
35 | <li><a href="gtl_polygon_45_set_concept.htm">Polygon 45 Set | |
36 | Concept</a></li> | |
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 | |
43 | Extraction</a></li> | |
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> | |
51 | </ul> | |
52 | <h3 class="navbar">Other Resources</h3> | |
53 | <ul> | |
54 | <li><a href="GTL_boostcon2009.pdf">GTL Boostcon 2009 Paper</a></li> | |
55 | <li><a href="GTL_boostcon_draft03.pdf">GTL Boostcon 2009 | |
56 | Presentation</a></li> | |
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 | |
62 | Tutorial</a></li> | |
63 | </ul> | |
64 | </div> | |
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> | |
67 | </td> | |
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 | |
72 | algorithm</a>, | |
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 | |
75 | structure builder. | |
76 | The structure shares Voronoi name, as the events generated by it | |
77 | provide | |
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> | |
82 | <ul> | |
83 | <li>The input coordinate type (for input points and enpoints of | |
84 | the input segments) is not required to be integral | |
85 | (while it | |
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> | |
89 | </ul> | |
90 | <h2>Important</h2> | |
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 | |
94 | to | |
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> | |
100 | <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> | |
105 | <h2>Declaration</h2> | |
106 | Header: <a href="../../../boost/polygon/voronoi_builder.hpp">boost/polygon/voronoi_builder.hpp</a><br> | |
107 | <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> | |
116 | <br> | |
117 | <span style="font-family: 'Courier New',Courier,monospace;">T</span></font> | |
118 | - specifies the coordinate type of the input geometries (points and | |
119 | segments).<br> | |
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 | |
122 | predicates (VP).<br> | |
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 | |
134 | those | |
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"> | |
140 | <tbody> | |
141 | <tr> | |
142 | <td style="font-family: 'Courier New',Courier,monospace;"><span style="font-weight: bold;">voronoi_builder</span>()</td> | |
143 | <td width="693">Default | |
144 | constructor.</td> | |
145 | </tr> | |
146 | <tr> | |
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> | |
153 | </tr> | |
154 | <tr> | |
155 | <td><span style="font-family: Courier New,Courier,monospace;">size_t <span style="font-weight: bold;">insert_segment</span>(const int_type& | |
156 | x1,<br> | |
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> | |
166 | </tr> | |
167 | <tr> | |
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) | |
171 | </td> | |
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 | |
175 | the | |
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> | |
178 | </td> | |
179 | </tr> | |
180 | <tr> | |
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 | |
185 | zero. </td> | |
186 | </tr> | |
187 | </tbody> | |
188 | </table> | |
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> | |
196 | <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> | |
205 | efpt_type;<br> | |
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> | |
209 | };</p> | |
210 | </font> One | |
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> | |
219 | <br> | |
220 | <table style="text-align: left; width: 100%;" border="1" cellpadding="2" cellspacing="2"> | |
221 | <tbody> | |
222 | <tr> | |
223 | <td style="font-family: 'Courier New',Courier,monospace; font-weight: bold;">int_type | |
224 | </td> | |
225 | <td style="vertical-align: top;">At least X-bit signed | |
226 | integer type. </td> | |
227 | </tr> | |
228 | <tr> | |
229 | <td style="vertical-align: top; font-family: 'Courier New',Courier,monospace; font-weight: bold;">int_x2_type | |
230 | </td> | |
231 | <td style="vertical-align: top;">At least 2X-bit signed | |
232 | integer type. </td> | |
233 | </tr> | |
234 | <tr> | |
235 | <td style="vertical-align: top; font-family: 'Courier New',Courier,monospace; font-weight: bold;">uint_x2_type | |
236 | </td> | |
237 | <td style="vertical-align: top;">At least 2X-bit unsigned | |
238 | integer type. </td> | |
239 | </tr> | |
240 | <tr> | |
241 | <td style="vertical-align: top; font-family: 'Courier New',Courier,monospace; font-weight: bold;">big_int_type | |
242 | </td> | |
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 | |
246 | segments. </td> | |
247 | </tr> | |
248 | <tr> | |
249 | <td style="vertical-align: top; font-family: 'Courier New',Courier,monospace; font-weight: bold;">fpt_type | |
250 | </td> | |
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> | |
254 | </tr> | |
255 | <tr> | |
256 | <td style="vertical-align: top; font-family: 'Courier New',Courier,monospace; font-weight: bold;">efpt_type | |
257 | </td> | |
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> | |
261 | </tr> | |
262 | <tr> | |
263 | <td style="vertical-align: top; font-family: 'Courier New',Courier,monospace; font-weight: bold;">ulp_cmp_type | |
264 | </td> | |
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> | |
268 | </tr> | |
269 | <tr> | |
270 | <td style="vertical-align: top; font-family: 'Courier New',Courier,monospace; font-weight: bold;">to_fpt_converter_type | |
271 | </td> | |
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> | |
275 | </tr> | |
276 | <tr> | |
277 | <td style="vertical-align: top; font-family: 'Courier New',Courier,monospace; font-weight: bold;">to_efpt_converter_type | |
278 | </td> | |
279 | <td style="vertical-align: top;">Type converter structure, | |
280 | that converts any of the integer types above to the efpt_type using | |
281 | operator(). </td> | |
282 | </tr> | |
283 | </tbody> | |
284 | </table> | |
285 | <p>Notes:</p> | |
286 | <ul> | |
287 | <li>Four different integer types are used (instead of a single | |
288 | big_int_type) to slightly improve algorithm performance and memory | |
289 | usage.</li> | |
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 | |
292 | integer type.</li> | |
293 | <li>Two separate floating-point types are defined, because for | |
294 | the input geometries | |
295 | with | |
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 | |
303 | will work).</li> | |
304 | <li>For an example of the user defined coordinate type traits | |
305 | check the <a href="voronoi_advanced_tutorial.htm">advanced Voronoi | |
306 | tutorial</a>.</li> | |
307 | </ul> | |
308 | </td> | |
309 | </tr> | |
310 | <tr> | |
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"> | |
315 | <tr> | |
316 | <th class="docinfo-name">Copyright:</th> | |
317 |