123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332 |
- <!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>
|