332 lines
17 KiB
HTML
332 lines
17 KiB
HTML
<!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 <20> 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> |