| <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"> |
| <html><head> |
| |
| |
| |
| <meta http-equiv="Content-Language" content="en-us"> |
| <meta http-equiv="Content-Type" content="text/html; charset=windows-1252"><title>Voronoi Builder</title></head><body> |
| <table style="margin: 0pt; padding: 0pt; width: 100%;" border="0" cellpadding="0" cellspacing="0"> |
| <tbody> |
| <tr> |
| <td style="background-color: rgb(238, 238, 238);" nowrap="1" valign="top"> |
| <div style="padding: 5px;" align="center"> <img src="images/boost.png" border="0" height="86" width="277"><a title="www.boost.org home page" tabindex="2" style="border: medium none ;" href="http://www.boost.org/"> </a></div> |
| <div style="margin: 5px;"> |
| <h3 class="navbar">Contents</h3> |
| <ul> |
| <li><a href="index.htm">Boost.Polygon Main Page</a></li> |
| <li><a href="gtl_design_overview.htm">Design Overview</a></li> |
| <li><a href="gtl_isotropy.htm">Isotropy</a></li> |
| <li><a href="gtl_coordinate_concept.htm">Coordinate Concept</a></li> |
| <li><a href="gtl_interval_concept.htm">Interval Concept</a></li> |
| <li><a href="gtl_point_concept.htm">Point Concept</a></li> |
| <li><a href="gtl_segment_concept.htm">Segment Concept</a></li> |
| <li><a href="gtl_rectangle_concept.htm">Rectangle Concept</a></li> |
| <li><a href="gtl_polygon_90_concept.htm">Polygon 90 Concept</a></li> |
| <li><a href="gtl_polygon_90_with_holes_concept.htm">Polygon 90 |
| With Holes Concept</a></li> |
| <li><a href="gtl_polygon_45_concept.htm">Polygon 45 Concept</a></li> |
| <li><a href="gtl_polygon_45_with_holes_concept.htm">Polygon 45 |
| With Holes Concept</a></li> |
| <li><a href="gtl_polygon_concept.htm">Polygon Concept</a></li> |
| <li><a href="gtl_polygon_with_holes_concept.htm">Polygon With |
| Holes Concept</a></li> |
| <li><a href="gtl_polygon_90_set_concept.htm">Polygon 90 Set |
| Concept</a></li> |
| <li><a href="gtl_polygon_45_set_concept.htm">Polygon 45 Set |
| Concept</a></li> |
| <li><a href="gtl_polygon_set_concept.htm">Polygon Set Concept</a></li> |
| <li><a href="gtl_connectivity_extraction_90.htm">Connectivity |
| Extraction 90</a></li> |
| <li><a href="gtl_connectivity_extraction_45.htm">Connectivity |
| Extraction 45</a></li> |
| <li><a href="gtl_connectivity_extraction.htm">Connectivity |
| Extraction</a></li> |
| <li><a href="gtl_property_merge_90.htm">Property Merge 90</a></li> |
| <li><a href="gtl_property_merge_45.htm">Property Merge 45</a></li> |
| <li><a href="gtl_property_merge.htm">Property Merge</a></li> |
| <li><a href="voronoi_main.htm">Voronoi Main Page </a></li> |
| <li><a href="voronoi_benchmark.htm">Voronoi Benchmark</a> </li> |
| <li>Voronoi Builder</li> |
| <li><a href="voronoi_diagram.htm">Voronoi Diagram</a></li> |
| </ul> |
| <h3 class="navbar">Other Resources</h3> |
| <ul> |
| <li><a href="GTL_boostcon2009.pdf">GTL Boostcon 2009 Paper</a></li> |
| <li><a href="GTL_boostcon_draft03.pdf">GTL Boostcon 2009 |
| Presentation</a></li> |
| <li><a href="analysis.htm">Performance Analysis</a></li> |
| <li><a href="gtl_tutorial.htm">Layout Versus Schematic Tutorial</a></li> |
| <li><a href="gtl_minkowski_tutorial.htm">Minkowski Sum Tutorial</a></li> |
| <li><a href="voronoi_basic_tutorial.htm">Voronoi Basic Tutorial</a></li> |
| <li><a href="voronoi_advanced_tutorial.htm">Voronoi Advanced |
| Tutorial</a></li> |
| </ul> |
| </div> |
| <h3 class="navbar">Polygon Sponsor</h3> |
| <div style="padding: 5px;" align="center"> <img src="images/intlogo.gif" border="0" height="51" width="127"><a title="www.adobe.com home page" tabindex="2" style="border: medium none ;" href="http://www.adobe.com/"> </a></div> |
| </td> |
| <td style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;" valign="top" width="100%"><!-- End Header --> <br> |
| <h1>Voronoi Builder </h1> |
| The Voronoi builder is the event generator structure, that implements |
| the <a href="http://en.wikipedia.org/wiki/Sweep_line_algorithm">sweepline |
| algorithm</a>, |
| scanning 2D space and spawning the two types of events: <a href="http://www.ams.org/samplings/feature-column/fcarc-voronoi">site |
| events and circle events</a>. Each event is reported to the output data |
| structure builder. |
| The structure shares Voronoi name, as the events generated by it |
| provide |
| enough information to construct the Voronoi diagram of a set of points |
| and linear segments. The requirements for the coordinate type of |
| the input/output geometries, configured through the coordinate type |
| traits template argument, are the following:<br> |
| <ul> |
| <li>The input coordinate type (for input points and enpoints of |
| the input segments) is not required to be integral |
| (while it |
| still should be an integer type)</li> |
| <li>The output coordinate type (for |
| Voronoi vertices) is required to be IEEE-754 floating point type</li> |
| </ul> |
| <h2>Important</h2> |
| The users are encouraged to use the default static methods defined in |
| the <a href="../../../boost/polygon/voronoi.hpp">voronoi.hpp</a> |
| header for the Voronoi diagram construction. However it's also possible |
| to |
| use Voronoi builder explicitly, especially if the user wants to drop |
| the external dependencies such as MPL (metaprogramming library). The |
| following include set doesn't depend on any external headers |
| (except STL and boost/cstdint.hpp), even |
| the Boost.Polygon library:<br> |
| <br> |
| <span style="font-family: Courier New,Courier,monospace;">#include |
| <voronoi_builder.hpp></span><br style="font-family: Courier New,Courier,monospace;"> |
| <span style="font-family: Courier New,Courier,monospace;">#include |
| <voronoi_diagram.hpp></span><br> |
| <h2>Declaration</h2> |
| Header: <a href="../../../boost/polygon/voronoi_builder.hpp">boost/polygon/voronoi_builder.hpp</a><br> |
| <br> |
| <font face="Courier New"> <span style="font-family: 'Courier New',Courier,monospace;">template |
| <typename T,</span><br style="font-family: 'Courier New',Courier,monospace;"> |
| <span style="font-family: 'Courier New',Courier,monospace;"> |
| typename CTT = detail::voronoi_ctype_traits<T>,</span><br style="font-family: 'Courier New',Courier,monospace;"> |
| <span style="font-family: 'Courier New',Courier,monospace;"> |
| typename VP = detail::voronoi_predicates<CTT> ></span><br style="font-family: 'Courier New',Courier,monospace;"> |
| <span style="font-family: 'Courier New',Courier,monospace;">class |
| voronoi_builder;</span><br> |
| <br> |
| <span style="font-family: 'Courier New',Courier,monospace;">T</span></font> |
| - specifies the coordinate type of the input geometries (points and |
| segments).<br> |
| <font face="Courier New"> <span style="font-family: 'Courier New',Courier,monospace;">CTT</span></font> |
| - defines the input/output coordinate type traits used by the Voronoi |
| predicates (VP).<br> |
| <font face="Courier New"> <span style="font-family: 'Courier New',Courier,monospace;">VP</span></font> |
| - the predicate kernel, that contains robust and |
| efficient predicates and functors.<br> |
| The Voronoi builder data structure is ready to use from the box with |
| 32-bit signed integer input coordinate type. The user may extend the |
| input coordinate range to the other integer types (e.g. 64-bit |
| integer), however this will also require manual setup of the |
| coordinate type traits. Default predicate kernel provides correct and |
| efficient predicates as long as types |
| defined by the coordinate type traits satisfy the requirements |
| explained at the end of this page. In case |
| those |
| requirements are not satisfied,<font face="Courier New"><span style="font-family: 'Courier New',Courier,monospace;"></span></font> |
| the proper predicate kernel |
| implementation is required.<span style="font-family: Courier New,Courier,monospace;"></span><br> |
| <h2>Member Functions</h2> |
| <table style="text-align: left; width: 100%;" border="1" cellpadding="2" cellspacing="2"> |
| <tbody> |
| <tr> |
| <td style="font-family: 'Courier New',Courier,monospace;"><span style="font-weight: bold;">voronoi_builder</span>()</td> |
| <td width="693">Default |
| constructor.</td> |
| </tr> |
| <tr> |
| <td><span style="font-family: Courier New,Courier,monospace;">size_t <span style="font-weight: bold;">insert_point</span>(const int_type& x,<br> |
| |
| const int_type& y)</span> </td> |
| <td>Inserts a point object with |
| the specified coordinates into the Voronoi builder.<br> |
| Returns index of the inserted point. </td> |
| </tr> |
| <tr> |
| <td><span style="font-family: Courier New,Courier,monospace;">size_t <span style="font-weight: bold;">insert_segment</span>(const int_type& |
| x1,<br> |
| |
| const int_type& y1,<br> |
| |
| const int_type& x2,<br> |
| |
| const int_type& y2)</span> </td> |
| <td>Inserts a segment object |
| with the specified coordinates into the Voronoi builder.<br> |
| Returns index of the inserted segment. </td> |
| </tr> |
| <tr> |
| <td style="font-family: 'Courier New',Courier,monospace;">template |
| <typename OUTPUT><br> |
| void <span style="font-weight: bold;">construct</span>(OUTPUT* output) |
| </td> |
| <td width="693">Runs the sweepline |
| algorithm over the set of inserted geometries and generates site and |
| circle events to the OUTPUT data structure. It's the responsibility of |
| the |
| output data structure to process them.<br> |
| Complexity: O(N * log N), where N is the total number of input points and segments.<br> |
| </td> |
| </tr> |
| <tr> |
| <td style="font-family: 'Courier New',Courier,monospace;">void |
| <span style="font-weight: bold;">clear</span>() </td> |
| <td width="693">Clears the |
| list of the inserted geometries. Sets the input geometry index to |
| zero. </td> |
| </tr> |
| </tbody> |
| </table> |
| <h1>Voronoi Coordinate Type Traits</h1> |
| <p>The library provides the default coordinate type traits |
| specialization for the |
| 32-bit signed integer type:</p> |
| <font style="font-family: 'Courier New',Courier,monospace;" face="Courier New"> |
| <p>template <typename T><br> |
| struct voronoi_ctype_traits;<br> |
| <br> |
| template <><br> |
| struct voronoi_ctype_traits<int32> {<br> |
| typedef int32 int_type;<br> |
| typedef int64 int_x2_type;<br> |
| typedef uint64 uint_x2_type;<br> |
| typedef extended_int<128> big_int_type;<br> |
| typedef fpt64 fpt_type;<br> |
| typedef extended_exponent_fpt<fpt_type> |
| efpt_type;<br> |
| typedef ulp_comparison<fpt_type> ulp_cmp_type;<br> |
| typedef type_converter_fpt to_fpt_converter_type;<br> |
| typedef type_converter_efpt to_efpt_converter_type;<br> |
| };</p> |
| </font> One |
| of the most important features of the library is that Voronoi builder |
| output geometries are constructed within defined relative error (64 |
| machine epsilons). That means, the more mantissa bits the user provided |
| fpt_type has, the better precision of the output geometries will be. In |
| order for the user defined traits to be consistent with the default |
| Voronoi builder predicate kernel user should define the following set |
| of traits (the assumption is made that input geometries have |
| X-bit signed integer coordinate type):<br> |
| <br> |
| <table style="text-align: left; width: 100%;" border="1" cellpadding="2" cellspacing="2"> |
| <tbody> |
| <tr> |
| <td style="font-family: 'Courier New',Courier,monospace; font-weight: bold;">int_type |
| </td> |
| <td style="vertical-align: top;">At least X-bit signed |
| integer type. </td> |
| </tr> |
| <tr> |
| <td style="vertical-align: top; font-family: 'Courier New',Courier,monospace; font-weight: bold;">int_x2_type |
| </td> |
| <td style="vertical-align: top;">At least 2X-bit signed |
| integer type. </td> |
| </tr> |
| <tr> |
| <td style="vertical-align: top; font-family: 'Courier New',Courier,monospace; font-weight: bold;">uint_x2_type |
| </td> |
| <td style="vertical-align: top;">At least 2X-bit unsigned |
| integer type. </td> |
| </tr> |
| <tr> |
| <td style="vertical-align: top; font-family: 'Courier New',Courier,monospace; font-weight: bold;">big_int_type |
| </td> |
| <td style="vertical-align: top;">At least 8X-bit signed |
| integer type if input dataset contains only points.<br> |
| At least 64X-bit signed integer type if input dataset contains |
| segments. </td> |
| </tr> |
| <tr> |
| <td style="vertical-align: top; font-family: 'Courier New',Courier,monospace; font-weight: bold;">fpt_type |
| </td> |
| <td style="vertical-align: top;">IEEE-754 floating point |
| type, with mantissa at least (X+16) bits and exponent able to handle |
| 32X-bit unsigned integer type. </td> |
| </tr> |
| <tr> |
| <td style="vertical-align: top; font-family: 'Courier New',Courier,monospace; font-weight: bold;">efpt_type |
| </td> |
| <td style="vertical-align: top;">IEEE-754 floating point |
| type, with mantissa at least (X+16) bits and exponent able to handle |
| 64X-bit unsigned integer type. </td> |
| </tr> |
| <tr> |
| <td style="vertical-align: top; font-family: 'Courier New',Courier,monospace; font-weight: bold;">ulp_cmp_type |
| </td> |
| <td style="vertical-align: top;">Ulp comparison structure, |
| that checks if two fpt_type values are within the given ulp range |
| (relative error range). </td> |
| </tr> |
| <tr> |
| <td style="vertical-align: top; font-family: 'Courier New',Courier,monospace; font-weight: bold;">to_fpt_converter_type |
| </td> |
| <td style="vertical-align: top;">Type converter structure, |
| that converts any of the integer types above plus efpt_type to the |
| fpt_type using operator(). </td> |
| </tr> |
| <tr> |
| <td style="vertical-align: top; font-family: 'Courier New',Courier,monospace; font-weight: bold;">to_efpt_converter_type |
| </td> |
| <td style="vertical-align: top;">Type converter structure, |
| that converts any of the integer types above to the efpt_type using |
| operator(). </td> |
| </tr> |
| </tbody> |
| </table> |
| <p>Notes:</p> |
| <ul> |
| <li>Four different integer types are used (instead of a single |
| big_int_type) to slightly improve algorithm performance and memory |
| usage.</li> |
| <li>As the maximum required size of the big_int_type is known |
| in advance, it's possible to use fixed, stack allocated, multiprecision |
| integer type.</li> |
| <li>Two separate floating-point types are defined, because for |
| the input geometries |
| with |
| 32-bit signed integer coordinates, double type won't be able to handle |
| 2048-bit (64 chunks of 32 bits each) integers, as they will |
| overflow its exponent. On the |
| gcc compiler it's possible to use 80-bit long doubles for both fpt |
| types, however this is not supported by the MSVC compiler.</li> |
| <li>efpt_type and to_efpt_converter_type are not used to |
| construct the Voronoi diagram of a set of points (mock implementation |
| will work).</li> |
| <li>For an example of the user defined coordinate type traits |
| check the <a href="voronoi_advanced_tutorial.htm">advanced Voronoi |
| tutorial</a>.</li> |
| </ul> |
| </td> |
| </tr> |
| <tr> |
| <td style="background-color: rgb(238, 238, 238);" nowrap="1"> </td> |
| <td style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;" valign="top" width="100%"> |
| <table class="docinfo" id="table2" frame="void" rules="none"> |
| <colgroup> <col class="docinfo-name"><col class="docinfo-content"> </colgroup> <tbody valign="top"> |
| <tr> |
| <th class="docinfo-name">Copyright:</th> |
| <td>Copyright © Andrii Sydorchuk 2010-2013.</td> |
| </tr> |
| <tr class="field"> |
| <th class="docinfo-name">License:</th> |
| <td class="field-body">Distributed under the Boost Software |
| License, Version 1.0. (See accompanying file <tt class="literal"><span class="pre">LICENSE_1_0.txt</span></tt> or copy at <a class="reference" target="_top" href="http://www.boost.org/LICENSE_1_0.txt"> |
| http://www.boost.org/LICENSE_1_0.txt</a>)</td> |
| </tr> |
| </tbody> |
| </table> |
| </td> |
| </tr> |
| </tbody> |
| </table> |
| |
| </body></html> |
