]>
Commit | Line | Data |
---|---|---|
1 | <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"> | |
2 | <html> | |
3 | <head> | |
4 | <meta http-equiv="Content-Language" content="en-us"> | |
5 | <meta http-equiv="Content-Type" | |
6 | content="text/html; charset=windows-1252"> | |
7 | <title>Voronoi Diagram</title> | |
8 | <meta http-equiv="content-type" content="text/html; charset=utf-8"> | |
9 | <meta http-equiv="content-type" content="text/html; charset=utf-8"> | |
10 | </head> | |
11 | <body> | |
12 | <table style="margin: 0pt; padding: 0pt; width: 100%;" border="0" | |
13 | cellpadding="0" cellspacing="0"> | |
14 | <tbody> | |
15 | <tr> | |
16 | <td style="background-color: rgb(238, 238, 238);" nowrap="1" | |
17 | valign="top"> | |
18 | <div style="padding: 5px;" align="center"> <img | |
19 | src="images/boost.png" border="0" height="86" width="277"><a | |
20 | title="www.boost.org home page" tabindex="2" | |
21 | style="border: medium none ;" href="http://www.boost.org/"> </a></div> | |
22 | <div style="margin: 5px;"> | |
23 | <h3 class="navbar">Contents</h3> | |
24 | <ul> | |
25 | <li><a href="index.htm">Boost.Polygon Main Page</a></li> | |
26 | <li><a href="gtl_design_overview.htm">Design Overview</a></li> | |
27 | <li><a href="gtl_isotropy.htm">Isotropy</a></li> | |
28 | <li><a href="gtl_coordinate_concept.htm">Coordinate Concept</a></li> | |
29 | <li><a href="gtl_interval_concept.htm">Interval Concept</a></li> | |
30 | <li><a href="gtl_point_concept.htm">Point Concept</a></li> | |
31 | <li><a href="gtl_segment_concept.htm">Segment Concept</a></li> | |
32 | <li><a href="gtl_rectangle_concept.htm">Rectangle Concept</a></li> | |
33 | <li><a href="gtl_polygon_90_concept.htm">Polygon 90 Concept</a></li> | |
34 | <li><a href="gtl_polygon_90_with_holes_concept.htm">Polygon 90 | |
35 | With Holes Concept</a></li> | |
36 | <li><a href="gtl_polygon_45_concept.htm">Polygon 45 Concept</a></li> | |
37 | <li><a href="gtl_polygon_45_with_holes_concept.htm">Polygon 45 | |
38 | With Holes Concept</a></li> | |
39 | <li><a href="gtl_polygon_concept.htm">Polygon Concept</a></li> | |
40 | <li><a href="gtl_polygon_with_holes_concept.htm">Polygon With | |
41 | Holes Concept</a></li> | |
42 | <li><a href="gtl_polygon_90_set_concept.htm">Polygon 90 Set | |
43 | Concept</a></li> | |
44 | <li><a href="gtl_polygon_45_set_concept.htm">Polygon 45 Set | |
45 | Concept</a></li> | |
46 | <li><a href="gtl_polygon_set_concept.htm">Polygon Set Concept</a></li> | |
47 | <li><a href="gtl_connectivity_extraction_90.htm">Connectivity | |
48 | Extraction 90</a></li> | |
49 | <li><a href="gtl_connectivity_extraction_45.htm">Connectivity | |
50 | Extraction 45</a></li> | |
51 | <li><a href="gtl_connectivity_extraction.htm">Connectivity | |
52 | Extraction</a></li> | |
53 | <li><a href="gtl_property_merge_90.htm">Property Merge 90</a></li> | |
54 | <li><a href="gtl_property_merge_45.htm">Property Merge 45</a></li> | |
55 | <li><a href="gtl_property_merge.htm">Property Merge</a></li> | |
56 | <li><a href="voronoi_main.htm">Voronoi Main Page </a></li> | |
57 | <li><a href="voronoi_benchmark.htm">Voronoi Benchmark</a></li> | |
58 | <li><a href="voronoi_builder.htm">Voronoi Builder</a> </li> | |
59 | <li>Voronoi Diagram</li> | |
60 | </ul> | |
61 | <h3 class="navbar">Other Resources</h3> | |
62 | <ul> | |
63 | <li><a href="GTL_boostcon2009.pdf">GTL Boostcon 2009 Paper</a></li> | |
64 | <li><a href="GTL_boostcon_draft03.pdf">GTL Boostcon 2009 | |
65 | Presentation</a></li> | |
66 | <li><a href="analysis.htm">Performance Analysis</a></li> | |
67 | <li><a href="gtl_tutorial.htm">Layout Versus Schematic Tutorial</a></li> | |
68 | <li><a href="gtl_minkowski_tutorial.htm">Minkowski Sum Tutorial</a></li> | |
69 | <li><a href="voronoi_basic_tutorial.htm">Voronoi Basic Tutorial</a></li> | |
70 | <li><a href="voronoi_advanced_tutorial.htm">Voronoi Advanced | |
71 | Tutorial</a></li> | |
72 | </ul> | |
73 | </div> | |
74 | <h3 class="navbar">Polygon Sponsor</h3> | |
75 | <div style="padding: 5px;" align="center"> <img | |
76 | src="images/intlogo.gif" border="0" height="51" width="127"><a | |
77 | title="www.adobe.com home page" tabindex="2" | |
78 | style="border: medium none ;" href="http://www.adobe.com/"> </a></div> | |
79 | </td> | |
80 | <td | |
81 | style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;" | |
82 | valign="top" width="100%"><!-- End Header --> <br> | |
83 | <h1>Voronoi Diagram</h1> | |
84 | A Voronoi | |
85 | diagram is the computational geometry concept that represents partition | |
86 | of the given space onto regions, with bounds determined by distances to | |
87 | a | |
88 | specified family of objects. The application area of this concept | |
89 | varies <a | |
90 | href="http://www.ics.uci.edu/%7Eeppstein/gina/scot.drysdale.html">from | |
91 | Archaeology to Zoology</a>. The Boost.Polygon Voronoi extension | |
92 | provides | |
93 | implementation of | |
94 | the Voronoi diagram data structure in the 2D space. The internal | |
95 | representation | |
96 | consists of the three arrays, that respectively contain: Voronoi cells | |
97 | (represent the area around the input sites bounded by the Voronoi | |
98 | edges), Voronoi vertices | |
99 | (points where three or more Voronoi edges intersect), Voronoi edges | |
100 | (one dimensional curves containing points equidistant from the two | |
101 | closest input sites). Each of the primitives (cell, vertex, edge) | |
102 | contains pointers to the other linked primitives, so that it's always | |
103 | possible to efficiently traverse the Voronoi graph. The picture below | |
104 | shows | |
105 | the Voronoi vertices in red, Voronoi edges in black, input sites that | |
106 | correspond to the Voronoi cells in blue. It is considered, that each | |
107 | input segment consists of the three sites: segment itself and its | |
108 | endpoints. As the result, two additional Voronoi edges are constructed | |
109 | per each input segment. This is made to | |
110 | simplify the representation of the Voronoi diagram and Voronoi edges in | |
111 | particular.<br> | |
112 | <br> | |
113 | <img src="images/voronoi2.png" alt="" | |
114 | style="width: 600px; height: 600px;"><br> | |
115 | <h2>Important</h2> | |
116 | All | |
117 | the Voronoi primitive data structures (edge, vertex, cell) contain | |
118 | mutable color member. Color type is equivalent to the std::size_t type, | |
119 | except that the upper five bits are reserved for the internal usage. | |
120 | That means, that the maximum supported value by the color member is 32 | |
121 | times less than the one supported by std::size_t.<br> | |
122 | <h2>Declaration</h2> | |
123 | Header: <a href="../../../boost/polygon/voronoi_diagram.hpp">boost/polygon/voronoi_diagram.hpp</a><br> | |
124 | <br> | |
125 | <span style="font-family: Courier New,Courier,monospace;">template | |
126 | <typename T, typename TRAITS = voronoi_diagram_traits<T> ></span><br | |
127 | style="font-family: Courier New,Courier,monospace;"> | |
128 | <span style="font-family: Courier New,Courier,monospace;">class | |
129 | voronoi_diagram;<br> | |
130 | </span><font face="Courier New"><span | |
131 | style="font-family: 'Courier New',Courier,monospace;"><br> | |
132 | T</span></font> | |
133 | - the coordinate type of the Voronoi vertices.<br> | |
134 | <span style="font-family: Courier New,Courier,monospace;">TRAITS</span><font | |
135 | face="Courier New"><span | |
136 | style="font-family: 'Courier New',Courier,monospace;"></span></font> | |
137 | - the Voronoi diagram traits.<br> | |
138 | <h2>Member Functions</h2> | |
139 | <span style="font-family: Courier New,Courier,monospace;"> </span> | |
140 | <table style="text-align: left; width: 100%;" border="1" | |
141 | cellpadding="2" cellspacing="2"> | |
142 | <tbody> | |
143 | <tr> | |
144 | <td style="font-family: Courier New,Courier,monospace;"><span | |
145 | style="font-weight: bold;">voronoi_diagram</span>() </td> | |
146 | <td>Default constructor. </td> | |
147 | </tr> | |
148 | <tr> | |
149 | <td style="font-family: Courier New,Courier,monospace;">void | |
150 | <span style="font-weight: bold;">clear</span>() </td> | |
151 | <td>Removes all primitives from the Voronoi diagram. </td> | |
152 | </tr> | |
153 | <tr> | |
154 | <td style="font-family: Courier New,Courier,monospace;">const | |
155 | cell_container_type& <span style="font-weight: bold;">cells</span>() | |
156 | const </td> | |
157 | <td>Returns the const | |
158 | reference to the cell container. </td> | |
159 | </tr> | |
160 | <tr> | |
161 | <td style="font-family: Courier New,Courier,monospace;">const | |
162 | vertex_container_type& <span style="font-weight: bold;">vertices</span>() | |
163 | const </td> | |
164 | <td>Returns the const | |
165 | reference to the vertex container. </td> | |
166 | </tr> | |
167 | <tr> | |
168 | <td style="font-family: Courier New,Courier,monospace;">const | |
169 | edge_container_type& <span style="font-weight: bold;">edges</span>() | |
170 | const </td> | |
171 | <td>Returns the const | |
172 | reference to the edge container. </td> | |
173 | </tr> | |
174 | <tr> | |
175 | <td style="font-family: Courier New,Courier,monospace;">size_t | |
176 | <span style="font-weight: bold;">num_cells</span>() const </td> | |
177 | <td>Returns the number of the Voronoi | |
178 | cells in the Voronoi diagram. </td> | |
179 | </tr> | |
180 | <tr> | |
181 | <td style="font-family: Courier New,Courier,monospace;">size_t | |
182 | <span style="font-weight: bold;">num_edges</span>() const </td> | |
183 | <td>Returns the number of the | |
184 | Voronoi edges (half-edges) in the Voronoi diagram. </td> | |
185 | </tr> | |
186 | <tr> | |
187 | <td style="font-family: Courier New,Courier,monospace;">size_t | |
188 | <span style="font-weight: bold;">num_vertices</span>() | |
189 | const </td> | |
190 | <td>Returns the number of the | |
191 | Voronoi vertices in the Voronoi diagram. </td> | |
192 | </tr> | |
193 | </tbody> | |
194 | </table> | |
195 | <h2>Member Types</h2> | |
196 | <table style="text-align: left; width: 100%;" border="1" | |
197 | cellpadding="2" cellspacing="2"> | |
198 | <tbody> | |
199 | <tr> | |
200 | <td style="font-weight: bold;">coordinate_type </td> | |
201 | <td>Coordinate type. </td> | |
202 | </tr> | |
203 | <tr> | |
204 | <td style="font-weight: bold;">cell_type </td> | |
205 | <td>Voronoi cell. </td> | |
206 | </tr> | |
207 | <tr> | |
208 | <td style="font-weight: bold;">vertex_type </td> | |
209 | <td>Voronoi vertex. </td> | |
210 | </tr> | |
211 | <tr> | |
212 | <td style="font-weight: bold;">edge_type </td> | |
213 | <td>Voronoi edge. </td> | |
214 | </tr> | |
215 | <tr> | |
216 | <td style="font-weight: bold;">cell_container_type </td> | |
217 | <td>Container of the Voronoi cells. </td> | |
218 | </tr> | |
219 | <tr> | |
220 | <td style="font-weight: bold;">const_cell_iterator </td> | |
221 | <td>Const cell container iterator. </td> | |
222 | </tr> | |
223 | <tr> | |
224 | <td style="font-weight: bold;">vertex_container_type </td> | |
225 | <td>Container of the Voronoi vertices. </td> | |
226 | </tr> | |
227 | <tr> | |
228 | <td style="font-weight: bold;">const_vertex_iterator </td> | |
229 | <td>Const vertex container iterator. </td> | |
230 | </tr> | |
231 | <tr> | |
232 | <td style="font-weight: bold;">edge_container_type </td> | |
233 | <td>Container of the Voronoi edges. </td> | |
234 | </tr> | |
235 | <tr> | |
236 | <td style="font-weight: bold;">const_edge_iterator </td> | |
237 | <td>Const edge container iterator. </td> | |
238 | </tr> | |
239 | </tbody> | |
240 | </table> | |
241 | <h1>Voronoi Geometry Type</h1> | |
242 | The Voronoi | |
243 | diagram data structure doesn't embed coordinates of the input | |
244 | geometries. | |
245 | Instead it links with those via source index and source category | |
246 | methods | |
247 | of the Voronoi cell primitive. Source index is incrementally given | |
248 | (starting from zero) to each input site inserted into the <a | |
249 | href="voronoi_builder.htm">Voronoi | |
250 | builder</a>. | |
251 | Considering the fact, that each input segment is splitted onto three | |
252 | separate sites with the same index, we distinguish between those using | |
253 | source category. For more examples check the <a | |
254 | href="voronoi_basic_tutorial.htm">Voronoi basic tutorial</a>.<br> | |
255 | <h2>GeometryCategory </h2> | |
256 | Defines geometric category of the input object.<br> | |
257 | Header: <a href="../../../boost/polygon/voronoi_geometry_type.hpp">boost/polygon/</a><a | |
258 | href="../../../boost/polygon/voronoi_geometry_type.hpp">voronoi_geometry_type.hpp</a><br> | |
259 | <br> | |
260 | <span style="font-family: Courier New,Courier,monospace;">enum | |
261 | GeometryCategory {</span><br | |
262 | style="font-family: Courier New,Courier,monospace;"> | |
263 | <span style="font-family: Courier New,Courier,monospace;"> | |
264 | GEOMETRY_CATEGORY_POINT = 0x0,</span><br | |
265 | style="font-family: Courier New,Courier,monospace;"> | |
266 | <span style="font-family: Courier New,Courier,monospace;"> | |
267 | GEOMETRY_CATEGORY_SEGMENT = 0x1</span><br | |
268 | style="font-family: Courier New,Courier,monospace;"> | |
269 | <span style="font-family: Courier New,Courier,monospace;">};</span><br> | |
270 | <h2>SourceCategory</h2> | |
271 | Defines semantic category of the input site.<br> | |
272 | Header: <a href="../../../boost/polygon/voronoi_geometry_type.hpp">boost/polygon/</a><a | |
273 | href="../../../boost/polygon/voronoi_geometry_type.hpp">voronoi_geometry_type.hpp</a><br> | |
274 | <br> | |
275 | <span style="font-family: Courier New,Courier,monospace;">enum | |
276 | SourceCategory {</span><br | |
277 | style="font-family: Courier New,Courier,monospace;"> | |
278 | <span style="font-family: Courier New,Courier,monospace;"> | |
279 | // Point subtypes.</span><br | |
280 | style="font-family: Courier New,Courier,monospace;"> | |
281 | <span style="font-family: Courier New,Courier,monospace;"> | |
282 | SOURCE_CATEGORY_SINGLE_POINT = 0x0,</span><br | |
283 | style="font-family: Courier New,Courier,monospace;"> | |
284 | <span style="font-family: Courier New,Courier,monospace;"> | |
285 | SOURCE_CATEGORY_SEGMENT_START_POINT = 0x1,</span><br | |
286 | style="font-family: Courier New,Courier,monospace;"> | |
287 | <span style="font-family: Courier New,Courier,monospace;"> | |
288 | SOURCE_CATEGORY_SEGMENT_END_POINT = 0x2,</span><br | |
289 | style="font-family: Courier New,Courier,monospace;"> | |
290 | <br style="font-family: Courier New,Courier,monospace;"> | |
291 | <span style="font-family: Courier New,Courier,monospace;"> | |
292 | // Segment subtypes.</span><br | |
293 | style="font-family: Courier New,Courier,monospace;"> | |
294 | <span style="font-family: Courier New,Courier,monospace;"> | |
295 | SOURCE_CATEGORY_INITIAL_SEGMENT = 0x8,</span><br | |
296 | style="font-family: Courier New,Courier,monospace;"> | |
297 | <span style="font-family: Courier New,Courier,monospace;"> | |
298 | SOURCE_CATEGORY_REVERSE_SEGMENT = 0x9,</span><br | |
299 | style="font-family: Courier New,Courier,monospace;"> | |
300 | <br style="font-family: Courier New,Courier,monospace;"> | |
301 | <span style="font-family: Courier New,Courier,monospace;"> | |
302 | SOURCE_CATEGORY_GEOMETRY_SHIFT = 0x3,</span><br | |
303 | style="font-family: Courier New,Courier,monospace;"> | |
304 | <span style="font-family: Courier New,Courier,monospace;"> | |
305 | SOURCE_CATEGORY_BITMASK = 0x1F</span><br | |
306 | style="font-family: Courier New,Courier,monospace;"> | |
307 | <span style="font-family: Courier New,Courier,monospace;">};</span><br> | |
308 | <h2>Member Functions</h2> | |
309 | <table style="text-align: left; width: 100%;" border="1" | |
310 | cellpadding="2" cellspacing="2"> | |
311 | <tbody> | |
312 | <tr> | |
313 | <td style="vertical-align: top;"><span | |
314 | style="font-family: Courier New,Courier,monospace;">bool <span | |
315 | style="font-weight: bold;">belongs</span>(</span><br | |
316 | style="font-family: Courier New,Courier,monospace;"> | |
317 | <span style="font-family: Courier New,Courier,monospace;"> | |
318 | SourceCategory source_category,</span><br | |
319 | style="font-family: Courier New,Courier,monospace;"> | |
320 | <span style="font-family: Courier New,Courier,monospace;"> | |
321 | GeometryCategory geometry_category)</span> </td> | |
322 | <td style="vertical-align: middle;">Returns true if the | |
323 | given source | |
324 | category belongs to the given geometry category.<br> | |
325 | Returns false otherwise. </td> | |
326 | </tr> | |
327 | </tbody> | |
328 | </table> | |
329 | <h1>Voronoi Edge</h1> | |
330 | A Voronoi edge is a one-dimenstion curve, that contains points | |
331 | equidistant from the two closest input geometries. The Voronoi edge | |
332 | data structure is implemented as the enhanced classical <a | |
333 | href="http://www.flipcode.com/archives/The_Half-Edge_Data_Structure.shtml">half-edge</a> | |
334 | data structure. On the image below, the Voronoi edges are drawn as | |
335 | directed linear (e.g. AE) or curved (e.g. DE) dashed lines of either | |
336 | green (e.g. AE) or black (e.g DE) color. The green edges are considered | |
337 | to be secondary, as they are generated by an input segment and its | |
338 | endpoint (e.g. edge EA, made by segment MN and its endpoint M). All the | |
339 | other edges are considered to be primary (e.g. curved edge CD, made by | |
340 | segment KL and point N). Apart from that, each edge can be finite (e.g. | |
341 | ED) or infinite (e.g. edge starting at point B and going in the east | |
342 | direction).<br> | |
343 | <img src="images/voronoi1.png" alt="" | |
344 | style="width: 600px; height: 600px;"><br> | |
345 | Each Voronoi edge (consider directed edge BA) provides efficient access | |
346 | to the following primitives:<br> | |
347 | <ul> | |
348 | <li>Cell the edge belongs to (Voronoi cell P, with source | |
349 | segment MN)</li> | |
350 | <li>Start point of the edge (Voronoi vertex B, that is | |
351 | equidistant from the following input sites: O, L, MN)</li> | |
352 | <li>End point of the edge (Voronoi vertex A, that is | |
353 | equidistant from the following input sites: O, M, MN)</li> | |
354 | <li>Twin edge (Voronoi edge AB)</li> | |
355 | <li>CCW next edge inside the Voronoi cell, that the edge | |
356 | belongs to (green Voronoi edge AE)</li> | |
357 | <li>CCW previous edge inside the Voronoi cell, that the edge | |
358 | belongs to (Voronoi edge CB)</li> | |
359 | <li>CCW rotated next edge around the start point of the edge | |
360 | (Voronoi edge BC)</li> | |
361 | <li>CCW rotated previous edge around the start point of the | |
362 | edge (infinite Voronoi edge starting at the Voronoi vertex B and going | |
363 | in the east direction) </li> | |
364 | </ul> | |
365 | <h2>Declaration</h2> | |
366 | Header: <a href="../../../boost/polygon/voronoi_diagram.hpp">boost/polygon/voronoi_diagram.hpp</a><br> | |
367 | <br> | |
368 | <span style="font-family: Courier New,Courier,monospace;">template | |
369 | <typename T></span><br | |
370 | style="font-family: Courier New,Courier,monospace;"> | |
371 | <span style="font-family: Courier New,Courier,monospace;">class | |
372 | voronoi_edge;<br> | |
373 | <br> | |
374 | T</span> - coordinate type.<br> | |
375 | <h2>Member Functions</h2> | |
376 | <span style="font-family: Courier New,Courier,monospace;"> </span> | |
377 | <table style="text-align: left; width: 100%;" border="1" | |
378 | cellpadding="2" cellspacing="2"> | |
379 | <tbody> | |
380 | <tr> | |
381 | <td><span | |
382 | style="font-family: Courier New,Courier,monospace;"><span | |
383 | style="font-weight: bold;">voronoi_edge</span>(bool is_linear, bool | |
384 | is_primary)</span> </td> | |
385 | <td>Voronoi edge constructor. </td> | |
386 | </tr> | |
387 | <tr> | |
388 | <td style="font-family: Courier New,Courier,monospace;">voronoi_cell_type* | |
389 | <span style="font-weight: bold;">cell</span>() </td> | |
390 | <td>Returns the pointer to the | |
391 | Voronoi <span style="font-family: Courier New,Courier,monospace;"></span>cell | |
392 | that the edge belongs to. </td> | |
393 | </tr> | |
394 | <tr> | |
395 | <td style="font-family: Courier New,Courier,monospace;">const | |
396 | voronoi_cell_type* <span style="font-weight: bold;">cell</span>() | |
397 | const </td> | |
398 | <td>Returns the const pointer | |
399 | to the Voronoi cell that the edge belongs to. </td> | |
400 | </tr> | |
401 | <tr> | |
402 | <td style="font-family: Courier New,Courier,monospace;">void | |
403 | <span style="font-weight: bold;">cell</span>(voronoi_cell_type* | |
404 | c) </td> | |
405 | <td>Sets the Voronoi cell | |
406 | pointer to the cell the current edge belongs to. </td> | |
407 | </tr> | |
408 | <tr> | |
409 | <td style="font-family: Courier New,Courier,monospace;">voronoi_vertex_type* | |
410 | <span style="font-weight: bold;">vertex0</span>() </td> | |
411 | <td>Returns the pointer to the | |
412 | start point of the edge.<br> | |
413 | If the edge is infinite in that direction returns NULL. </td> | |
414 | </tr> | |
415 | <tr> | |
416 | <td style="font-family: Courier New,Courier,monospace;">const | |
417 | voronoi_vertex_type* <span style="font-weight: bold;">vertex0</span>() | |
418 | const </td> | |
419 | <td>Returns the const pointer | |
420 | to the start point vertex of the edge.<br> | |
421 | If the edge is infinite in that direction returns NULL. </td> | |
422 | </tr> | |
423 | <tr> | |
424 | <td style="font-family: Courier New,Courier,monospace;">void | |
425 | <span style="font-weight: bold;">vertex0</span>(voronoi_vertex_type* | |
426 | v) </td> | |
427 | <td>Sets the start point | |
428 | pointer of the edge. </td> | |
429 | </tr> | |
430 | <tr> | |
431 | <td style="font-family: Courier New,Courier,monospace;">voronoi_vertex_type* | |
432 | <span style="font-weight: bold;">vertex1</span>() </td> | |
433 | <td>Returns the pointer to the | |
434 | end point of the edge.<br> | |
435 | If the edge is infinite in that direction returns NULL. </td> | |
436 | </tr> | |
437 | <tr> | |
438 | <td style="font-family: Courier New,Courier,monospace;">const | |
439 | voronoi_vertex_type* <span style="font-weight: bold;">vertex1</span>() | |
440 | const </td> | |
441 | <td>Returns the const pointer | |
442 | to the end point of the edge.<br> | |
443 | If the edge is infinite in that direction returns NULL. </td> | |
444 | </tr> | |
445 | <tr> | |
446 | <td style="font-family: Courier New,Courier,monospace;">voronoi_edge_type* | |
447 | <span style="font-weight: bold;">twin</span>() </td> | |
448 | <td>Returns the pointer to the | |
449 | twin edge. </td> | |
450 | </tr> | |
451 | <tr> | |
452 | <td style="font-family: Courier New,Courier,monospace;">const | |
453 | voronoi_edge_type* <span style="font-weight: bold;">twin</span>() | |
454 | const </td> | |
455 | <td>Returns the const pointer | |
456 | to the twin edge. </td> | |
457 | </tr> | |
458 | <tr> | |
459 | <td style="font-family: Courier New,Courier,monospace;">void | |
460 | <span style="font-weight: bold;">twin</span>(voronoi_edge_type* | |
461 | e) </td> | |
462 | <td>Sets the twin edge pointer | |
463 | of the edge. </td> | |
464 | </tr> | |
465 | <tr> | |
466 | <td style="font-family: Courier New,Courier,monospace;">voronoi_edge_type* | |
467 | <span style="font-weight: bold;">next</span>() </td> | |
468 | <td>Returns the pointer to the | |
469 | CCW next edge within the corresponding Voronoi cell.<br> | |
470 | Edges not necessarily share a common vertex (e.g. infinite edges). </td> | |
471 | </tr> | |
472 | <tr> | |
473 | <td style="font-family: Courier New,Courier,monospace;">const | |
474 | voronoi_edge_type* <span style="font-weight: bold;">next</span>() | |
475 | const </td> | |
476 | <td>Returns the const pointer | |
477 | to the CCW next edge within the corresponding Voronoi cell.<br> | |
478 | Edges not necessarily share a common vertex (e.g. infinite edges). </td> | |
479 | </tr> | |
480 | <tr> | |
481 | <td style="font-family: Courier New,Courier,monospace;">void | |
482 | <span style="font-weight: bold;">next</span>(voronoi_edge_type* | |
483 | e) </td> | |
484 | <td>Sets the CCW next edge | |
485 | pointer of the edge. </td> | |
486 | </tr> | |
487 | <tr> | |
488 | <td style="font-family: Courier New,Courier,monospace;">voronoi_edge_type* | |
489 | <span style="font-weight: bold;">prev</span>() </td> | |
490 | <td>Returns the pointer to the | |
491 | CCW prev edge within the corresponding Voronoi cell.<br> | |
492 | Edges not necessarily share a common vertex (e.g. infinite edges). </td> | |
493 | </tr> | |
494 | <tr> | |
495 | <td style="font-family: Courier New,Courier,monospace;">const | |
496 | voronoi_edge_type* <span style="font-weight: bold;">prev</span>() | |
497 | const </td> | |
498 | <td>Returns the const pointer | |
499 | to the CCW prev edge within the corresponding Voronoi cell.<br> | |
500 | Edges not necessarily share a common vertex (e.g. infinite edges). </td> | |
501 | </tr> | |
502 | <tr> | |
503 | <td style="font-family: Courier New,Courier,monospace;">void | |
504 | <span style="font-weight: bold;">prev</span>(voronoi_edge_type* | |
505 | e) </td> | |
506 | <td>Sets the CCW prev edge | |
507 | pointer of the edge. </td> | |
508 | </tr> | |
509 | <tr> | |
510 | <td style="font-family: Courier New,Courier,monospace;">color_type | |
511 | <span style="font-weight: bold;">color</span>() const </td> | |
512 | <td>Returns the color value. </td> | |
513 | </tr> | |
514 | <tr> | |
515 | <td style="font-family: Courier New,Courier,monospace;">void | |
516 | <span style="font-weight: bold;">color</span>(color_type | |
517 | color) const </td> | |
518 | <td>Sets the color of | |
519 | the edge.<br> | |
520 | Allows to associate the user provided data with the primitive. </td> | |
521 | </tr> | |
522 | <tr> | |
523 | <td style="font-family: Courier New,Courier,monospace;">voronoi_edge_type* | |
524 | <span style="font-weight: bold;">rot_next</span>() </td> | |
525 | <td>Returns the pointer to the | |
526 | CCW next edge rotated around the edge start point.<br> | |
527 | Works for infinite edges as well. </td> | |
528 | </tr> | |
529 | <tr> | |
530 | <td style="font-family: Courier New,Courier,monospace;">const | |
531 | voronoi_edge_type* <span style="font-weight: bold;">rot_next</span>() | |
532 | const </td> | |
533 | <td>Returns the const pointer | |
534 | to the CCW next edge rotated around the edge start point.<br> | |
535 | Works for infinite edges as well.</td> | |
536 | </tr> | |
537 | <tr> | |
538 | <td style="font-family: Courier New,Courier,monospace;">voronoi_edge_type* | |
539 | <span style="font-weight: bold;">rot_prev</span>() </td> | |
540 | <td>Returns the pointer to the | |
541 | CCW prev edge rotated around the edge start point.<br> | |
542 | Works for infinite edges as well. </td> | |
543 | </tr> | |
544 | <tr> | |
545 | <td style="font-family: Courier New,Courier,monospace;">const | |
546 | voronoi_edge_type* <span style="font-weight: bold;">rot_prev</span>() | |
547 | const </td> | |
548 | <td>Returns the const pointer | |
549 | to the CCW prev edge rotated around the edge start point.<br> | |
550 | Works for infinite edges as well.</td> | |
551 | </tr> | |
552 | <tr> | |
553 | <td style="font-family: Courier New,Courier,monospace;">bool | |
554 | <span style="font-weight: bold;">is_finite</span>() const </td> | |
555 | <td>Returns true if the both | |
556 | end points of the edge are finite, else false. </td> | |
557 | </tr> | |
558 | <tr> | |
559 | <td style="font-family: Courier New,Courier,monospace;">bool | |
560 | <span style="font-weight: bold;">is_infinite</span>() const</td> | |
561 | <td>Returns true if one of the | |
562 | end points of the edge is infinite, else false.</td> | |
563 | </tr> | |
564 | <tr> | |
565 | <td style="font-family: Courier New,Courier,monospace;">bool | |
566 | <span style="font-weight: bold;">is_linear</span>() const </td> | |
567 | <td>Returns true if the edge | |
568 | is linear (segment, ray, line), else false. </td> | |
569 | </tr> | |
570 | <tr> | |
571 | <td style="font-family: Courier New,Courier,monospace;">bool | |
572 | <span style="font-weight: bold;">is_curved</span>() const </td> | |
573 | <td>Returns true if the edge | |
574 | is curved (parabolic arc), else false. </td> | |
575 | </tr> | |
576 | <tr> | |
577 | <td style="font-family: Courier New,Courier,monospace;">bool | |
578 | <span style="font-weight: bold;">is_primary</span>() const </td> | |
579 | <td>Returns false if the edge | |
580 | goes through the endpoint of the segment site, else true. </td> | |
581 | </tr> | |
582 | <tr> | |
583 | <td style="font-family: Courier New,Courier,monospace;">bool | |
584 | <span style="font-weight: bold;">is_secondary</span>() const</td> | |
585 | <td>Returns true if the edge | |
586 | goes through the endpoint of the segment site, else false.</td> | |
587 | </tr> | |
588 | </tbody> | |
589 | </table> | |
590 | <span style="font-family: Courier New,Courier,monospace;"> </span>All | |
591 | the above methods have O(1) complexity. The size of | |
592 | the Voronoi edge structure is equal to: 5 * sizeof(void *) + | |
593 | sizeof(size_t).<span style="font-family: Courier New,Courier,monospace;"></span><br> | |
594 | <h2>Member Types</h2> | |
595 | <table style="text-align: left; width: 100%;" border="1" | |
596 | cellpadding="2" cellspacing="2"> | |
597 | <tbody> | |
598 | <tr> | |
599 | <td style="font-weight: bold;">coordinate_type </td> | |
600 | <td>Coordinate type. </td> | |
601 | </tr> | |
602 | <tr> | |
603 | <td style="font-weight: bold;">voronoi_cell_type </td> | |
604 | <td>Voronoi cell type. </td> | |
605 | </tr> | |
606 | <tr> | |
607 | <td style="font-weight: bold;">voronoi_vertex_type </td> | |
608 | <td>Voronoi vertex type. </td> | |
609 | </tr> | |
610 | <tr> | |
611 | <td style="font-weight: bold;">voronoi_edge_type </td> | |
612 | <td>Voronoi edge type. </td> | |
613 | </tr> | |
614 | <tr> | |
615 | <td style="vertical-align: top; font-weight: bold;">color_type | |
616 | </td> | |
617 | <td style="vertical-align: top;">Color type (check the | |
618 | Important section). </td> | |
619 | </tr> | |
620 | </tbody> | |
621 | </table> | |
622 | <h1>Voronoi Cell</h1> | |
623 | A Voronoi cell represents a region of the Voronoi diagram bounded by | |
624 | the Voronoi edges. On the image below, there are 7 such regions: P, Q, | |
625 | R, S, T, U, V. Each Voronoi cell can contain a point (e.g. cells Q, S, | |
626 | T, U, V with corresponding input sources N, K, L, O, M respectively) or | |
627 | a segment | |
628 | (e.g. cells P and R with corresponding input sources MN and KL | |
629 | respectively) as its | |
630 | source. The Voronoi cell primitive doesn't contain coordinates of the | |
631 | source geometry, instead it stores the index and category of the source | |
632 | geometry. Source index corresponds to the unique id, issued to each | |
633 | input geometry (e.g. incremental counter, used by the Voronoi builder). | |
634 | Such an index uniquely identifies any input point (e.g. O), however | |
635 | doesn't make any distinction between segment (e.g. MN) and both its end | |
636 | points (e.g. M, N). In order to resolve possible ambiguity, the source | |
637 | category is used, that specifies the semantic topology of the input | |
638 | object (e.g. segment's startpoint, segment's endpoint or segment | |
639 | itself). The Voronoi cell data structure also provides access to a | |
640 | random Voronoi edge, located on the boundary of the cell (e.g. edge AE | |
641 | for | |
642 | the cell P).<br> | |
643 | <img style="width: 600px; height: 600px;" alt="" | |
644 | src="images/voronoi1.png"><br> | |
645 | <h2>Declaration</h2> | |
646 | Header: <a href="../../../boost/polygon/voronoi_diagram.hpp">boost/polygon/voronoi_diagram.hpp</a><br> | |
647 | <br> | |
648 | <span style="font-family: Courier New,Courier,monospace;">template | |
649 | <typename T><br> | |
650 | class voronoi_cell;<br> | |
651 | <br> | |
652 | </span><span style="font-family: Courier New,Courier,monospace;">T</span> | |
653 | - coordinate type.<br> | |
654 | <h2>Member Functions</h2> | |
655 | <span style="font-family: Courier New,Courier,monospace;"> </span> | |
656 | <table style="text-align: left; width: 100%;" border="1" | |
657 | cellpadding="2" cellspacing="2"> | |
658 | <tbody> | |
659 | <tr> | |
660 | <td><span | |
661 | style="font-family: Courier New,Courier,monospace;"><span | |
662 | style="font-weight: bold;">voronoi_cell</span>(source_index_type | |
663 | source_index,</span><span | |
664 | style="font-family: Courier New,Courier,monospace;"><br> | |
665 | | |
666 | source_category_type source_category)</span> </td> | |
667 | <td>Voronoi cell constructor. </td> | |
668 | </tr> | |
669 | <tr> | |
670 | <td style="font-family: Courier New,Courier,monospace;">source_index_type | |
671 | <span style="font-weight: bold;">source_index</span>() | |
672 | const </td> | |
673 | <td>Returns input site index among the other sites.<br> | |
674 | Both segment and its end points will have the same index. </td> | |
675 | </tr> | |
676 | <tr> | |
677 | <td style="font-family: Courier New,Courier,monospace;">source_category_type | |
678 | <span style="font-weight: bold;">source_category</span>() | |
679 | const </td> | |
680 | <td>Returns input site category among the other sites.<br> | |
681 | Allows to distinguish between segment site and its endpoints. </td> | |
682 | </tr> | |
683 | <tr> | |
684 | <td style="font-family: Courier New,Courier,monospace;">voronoi_edge_type* | |
685 | <span style="font-weight: bold;">incident_edge</span>() </td> | |
686 | <td>Returns the pointer to the | |
687 | one of the boundary edges. </td> | |
688 | </tr> | |
689 | <tr> | |
690 | <td style="font-family: Courier New,Courier,monospace;">const | |
691 | voronoi_edge_type* <span style="font-weight: bold;">incident_edge</span>() | |
692 | const </td> | |
693 | <td>Returns the const pointer | |
694 | to the one of the boundary edges. </td> | |
695 | </tr> | |
696 | <tr> | |
697 | <td style="font-family: Courier New,Courier,monospace;">void | |
698 | <span style="font-weight: bold;">incident_edge</span>(voronoi_edge_type* | |
699 | e) </td> | |
700 | <td>Sets the incident boundary | |
701 | edge pointer of the cell. </td> | |
702 | </tr> | |
703 | <tr> | |
704 | <td style="font-family: Courier New,Courier,monospace;">color_type | |
705 | <span style="font-weight: bold;">color</span>() const </td> | |
706 | <td>Returns the color associated with the cell.</td> | |
707 | </tr> | |
708 | <tr> | |
709 | <td style="font-family: Courier New,Courier,monospace;">void | |
710 | <span style="font-weight: bold;">color</span>(color_type | |
711 | color) const </td> | |
712 | <td>Sets the color of | |
713 | the cell.<br> | |
714 | Allows to associate the user provided data with the primitive. </td> | |
715 | </tr> | |
716 | <tr> | |
717 | <td style="font-family: Courier New,Courier,monospace;">bool | |
718 | <span style="font-weight: bold;">contains_point</span>() | |
719 | const</td> | |
720 | <td>Returns true if the cell | |
721 | contains a point site, else false.</td> | |
722 | </tr> | |
723 | <tr> | |
724 | <td style="font-family: Courier New,Courier,monospace;">bool | |
725 | <span style="font-weight: bold;">contains_segment</span>() | |
726 | const</td> | |
727 | <td>Returns true if the cell | |
728 | contains a segment site, else false.</td> | |
729 | </tr> | |
730 | <tr> | |
731 | <td style="font-family: Courier New,Courier,monospace;">bool | |
732 | <span style="font-weight: bold;">is_degenerate</span>() | |
733 | const </td> | |
734 | <td>Returns true if the cell | |
735 | doesn't have an incident edge.<br> | |
736 | Can happen if a few input segments share a common endpoint.</td> | |
737 | </tr> | |
738 | </tbody> | |
739 | </table> | |
740 | <span style="font-family: Courier New,Courier,monospace;"> </span>All | |
741 | the above methods have O(1) complexity. The size of | |
742 | the Voronoi cell structure is equal to: sizeof(void *) + 2 * | |
743 | sizeof(size_t).<span style="font-family: Courier New,Courier,monospace;"></span> | |
744 | <h2>Member Types</h2> | |
745 | <table style="text-align: left; width: 100%;" border="1" | |
746 | cellpadding="2" cellspacing="2"> | |
747 | <tbody> | |
748 | <tr> | |
749 | <td style="font-weight: bold;">coordinate_type </td> | |
750 | <td>Coordinate type. </td> | |
751 | </tr> | |
752 | <tr> | |
753 | <td style="font-weight: bold;">source_index_type</td> | |
754 | <td>Source index type. </td> | |
755 | </tr> | |
756 | <tr> | |
757 | <td style="vertical-align: top; font-weight: bold;">source_category_type | |
758 | </td> | |
759 | <td style="vertical-align: top;">Source category type. </td> | |
760 | </tr> | |
761 | <tr> | |
762 | <td style="vertical-align: top; font-weight: bold;">voronoi_edge_type | |
763 | </td> | |
764 | <td style="vertical-align: top;">Voronoi edge type. </td> | |
765 | </tr> | |
766 | <tr> | |
767 | <td style="font-weight: bold;">color_type </td> | |
768 | <td>Color type (check the Important section). </td> | |
769 | </tr> | |
770 | </tbody> | |
771 | </table> | |
772 | <h2>Miscellaneous</h2> | |
773 | The following code snippet effectively traverses the Voronoi edges | |
774 | around the | |
775 | Voronoi cell:<br> | |
776 | <br> | |
777 | <span style="font-family: Courier New,Courier,monospace;">const | |
778 | voronoi_edge<double>* edge = cell->incident_edge();</span><br> | |
779 | <span style="font-family: Courier New,Courier,monospace;">do {</span><br | |
780 | style="font-family: Courier New,Courier,monospace;"> | |
781 | <span style="font-family: Courier New,Courier,monospace;"> | |
782 | edge = edge->next();</span><br | |
783 | style="font-family: Courier New,Courier,monospace;"> | |
784 | <span style="font-family: Courier New,Courier,monospace;"> | |
785 | // Do smth. with edge.</span><br | |
786 | style="font-family: Courier New,Courier,monospace;"> | |
787 | <span style="font-family: Courier New,Courier,monospace;">} while | |
788 | (edge != cell->incident_edge());</span><br> | |
789 | <h1>Voronoi Vertex</h1> | |
790 | A Voronoi vertex represents a point, that is equidistant from the three | |
791 | or more input geometries. As a consequence, it corresponds to the point | |
792 | of the intersection of the three or more Voronoi edges. On the image | |
793 | below, there are 5 such vertices: A, B, C, D, E. The Voronoi vertex | |
794 | data structure embeds the coordinates of the underlying point and | |
795 | provides access to a random Voronoi edge originating from the vertex | |
796 | (e.g. edge | |
797 | BC for the vertex B).<br> | |
798 | <img style="width: 600px; height: 600px;" alt="" | |
799 | src="images/voronoi1.png"><br> | |
800 | <h2>Declaration</h2> | |
801 | Header: <a href="../../../boost/polygon/voronoi_diagram.hpp">boost/polygon/voronoi_diagram.hpp</a><br> | |
802 | <br> | |
803 | <span style="font-family: Courier New,Courier,monospace;">template | |
804 | <typename T></span><br | |
805 | style="font-family: Courier New,Courier,monospace;"> | |
806 | <span style="font-family: Courier New,Courier,monospace;">class | |
807 | voronoi_vertex;<br> | |
808 | <br> | |
809 | </span><span style="font-family: Courier New,Courier,monospace;">T</span> | |
810 | - coordinate type.<br> | |
811 | <h2>Member Functions</h2> | |
812 | <span style="font-family: Courier New,Courier,monospace;"> </span> | |
813 | <table style="text-align: left; width: 100%;" border="1" | |
814 | cellpadding="2" cellspacing="2"> | |
815 | <tbody> | |
816 | <tr> | |
817 | <td><span | |
818 | style="font-family: Courier New,Courier,monospace;"><span | |
819 | style="font-weight: bold;">voronoi_vertex</span>(const | |
820 | coordinate_type& x,<br> | |
821 | | |
822 | const coordinate_type& y)</span><span | |
823 | style="font-family: Courier New,Courier,monospace;"></span> </td> | |
824 | <td>Voronoi vertex constructor. </td> | |
825 | </tr> | |
826 | <tr> | |
827 | <td style="font-family: Courier New,Courier,monospace;">const | |
828 | point_type& <span style="font-weight: bold;">x</span>() const </td> | |
829 | <td>Returns the x-coordinate of the point that represents | |
830 | the vertex. </td> | |
831 | </tr> | |
832 | <tr> | |
833 | <td style="font-family: Courier New,Courier,monospace;">const | |
834 | point_type& <span style="font-weight: bold;">y</span>() const</td> | |
835 | <td>Returns the y-coordinate of the point that represents | |
836 | the vertex. </td> | |
837 | </tr> | |
838 | <tr> | |
839 | <td style="font-family: Courier New,Courier,monospace;">voronoi_edge_type* | |
840 | <span style="font-weight: bold;">incident_edge</span>() </td> | |
841 | <td>Returns the incident edge | |
842 | pointer. </td> | |
843 | </tr> | |
844 | <tr> | |
845 | <td style="font-family: Courier New,Courier,monospace;">const | |
846 | voronoi_edge_type* <span style="font-weight: bold;">incident_edge</span>() | |
847 | const </td> | |
848 | <td>Returns the const pointer | |
849 | to the incident edge. </td> | |
850 | </tr> | |
851 | <tr> | |
852 | <td style="font-family: Courier New,Courier,monospace;">void | |
853 | <span style="font-weight: bold;">incident_edge</span>(voronoi_edge_type* | |
854 | e) </td> | |
855 | <td>Sets the incident edge | |
856 | pointer. </td> | |
857 | </tr> | |
858 | <tr> | |
859 | <td style="font-family: Courier New,Courier,monospace;">color_type | |
860 | <span style="font-weight: bold;">color</span>() const </td> | |
861 | <td>Returns the color associated with the vertex.</td> | |
862 | </tr> | |
863 | <tr> | |
864 | <td style="font-family: Courier New,Courier,monospace;">void | |
865 | <span style="font-weight: bold;">color</span>(color_type | |
866 | color) const </td> | |
867 | <td>Sets the color of | |
868 | the vertex.<br> | |
869 | Allows to associate the user provided data with the primitive.</td> | |
870 | </tr> | |
871 | </tbody> | |
872 | </table> | |
873 | <span style="font-family: Courier New,Courier,monospace;"> </span>All | |
874 | the above methods have O(1) complexity. The size of | |
875 | the Voronoi vertex structure is equal to: sizeof(void *) + | |
876 | sizeof(size_t) + 2 * | |
877 | sizeof(coordinate_type).<span | |
878 | style="font-family: Courier New,Courier,monospace;"></span> | |
879 | <h2>Member Types</h2> | |
880 | <table style="text-align: left; width: 100%;" border="1" | |
881 | cellpadding="2" cellspacing="2"> | |
882 | <tbody> | |
883 | <tr> | |
884 | <td style="font-weight: bold;">coordinate_type </td> | |
885 | <td>Coordainte type. </td> | |
886 | </tr> | |
887 | <tr> | |
888 | <td style="vertical-align: top; font-weight: bold;">voronoi_edge_type | |
889 | </td> | |
890 | <td style="vertical-align: top;">Voronoi edge type. </td> | |
891 | </tr> | |
892 | <tr> | |
893 | <td style="font-weight: bold;">color_type </td> | |
894 | <td>Color type (check the Important section). </td> | |
895 | </tr> | |
896 | </tbody> | |
897 | </table> | |
898 | <h2>Miscellaneous</h2> | |
899 | The following code snippet effectively traverses the Voronoi edges | |
900 | around the | |
901 | Voronoi vertex:<br> | |
902 | <br> | |
903 | <span style="font-family: Courier New,Courier,monospace;">const | |
904 | voronoi_edge<double>* edge = vertex->incident_edge();</span><br> | |
905 | <span style="font-family: Courier New,Courier,monospace;">do {</span><br | |
906 | style="font-family: Courier New,Courier,monospace;"> | |
907 | <span style="font-family: Courier New,Courier,monospace;"> | |
908 | edge = edge->next();</span><br | |
909 | style="font-family: Courier New,Courier,monospace;"> | |
910 | <span style="font-family: Courier New,Courier,monospace;"> | |
911 | // Do smth. with edge.</span><br | |
912 | style="font-family: Courier New,Courier,monospace;"> | |
913 | <span style="font-family: Courier New,Courier,monospace;">} while | |
914 | (edge != vertex->incident_edge()); </span> | |
915 | <h1>Voronoi Diagram Traits </h1> | |
916 | The Voronoi diagram traits are used to configure the Voronoi primitive | |
917 | types and predicates, used by the Voronoi diagram | |
918 | data | |
919 | structure.<br> | |
920 | The implementation includes default traits specialization for the | |
921 | double output coordinate type.<br> | |
922 | <h2>Declaration</h2> | |
923 | Header: <a href="../../../boost/polygon/voronoi_diagram.hpp">boost/polygon/voronoi_diagram.hpp</a><br> | |
924 | <br> | |
925 | <span style="font-family: Courier New,Courier,monospace;">template | |
926 | <typename T></span><br | |
927 | style="font-family: Courier New,Courier,monospace;"> | |
928 | <span style="font-family: Courier New,Courier,monospace;">struct | |
929 | voronoi_diagram_traits;<br> | |
930 | <br> | |
931 | </span><span style="font-family: Courier New,Courier,monospace;">T</span> | |
932 | - coordinate type.<br> | |
933 | <h2>Member Types</h2> | |
934 | <span style="font-family: Courier New,Courier,monospace;"> </span> | |
935 | <table style="text-align: left; width: 100%;" border="1" | |
936 | cellpadding="2" cellspacing="2"> | |
937 | <tbody> | |
938 | <tr> | |
939 | <td | |
940 | style="font-family: Courier New,Courier,monospace; font-weight: bold;">coordinate_type | |
941 | </td> | |
942 | <td>Coordinate type | |
943 | of the Voronoi diagram primitives. </td> | |
944 | </tr> | |
945 | <tr> | |
946 | <td | |
947 | style="font-family: Courier New,Courier,monospace; font-weight: bold;">cell_type | |
948 | </td> | |
949 | <td>Voronoi cell type. </td> | |
950 | </tr> | |
951 | <tr> | |
952 | <td | |
953 | style="font-family: Courier New,Courier,monospace; font-weight: bold;">vertex_type | |
954 | </td> | |
955 | <td>Voronoi vertex type. </td> | |
956 | </tr> | |
957 | <tr> | |
958 | <td | |
959 | style="font-family: Courier New,Courier,monospace; font-weight: bold;">edge_type | |
960 | </td> | |
961 | <td>Voronoi edge type. </td> | |
962 | </tr> | |
963 | <tr> | |
964 | <td | |
965 | style="font-family: Courier New,Courier,monospace; font-weight: bold;">vertex_equality_predicate_type | |
966 | </td> | |
967 | <td>Predicate that returns | |
968 | true if the two points are considered to be equal.<br> | |
969 | False otherwise. It is used to unite nearby Voronoi vertices. </td> | |
970 | </tr> | |
971 | </tbody> | |
972 | </table> | |
973 | </td> | |
974 | </tr> | |
975 | <tr> | |
976 | <td style="background-color: rgb(238, 238, 238);" nowrap="1"> </td> | |
977 | <td | |
978 | style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;" | |
979 | valign="top" width="100%"> | |
980 | <table class="docinfo" id="table2" frame="void" rules="none"> | |
981 | <colgroup> <col class="docinfo-name"><col | |
982 | class="docinfo-content"> </colgroup> <tbody valign="top"> | |
983 | <tr> | |
984 | <th class="docinfo-name">Copyright:</th> | |
985 |