[ceph.git] / ceph / src / boost / libs / polygon / doc / voronoi_builder.htm

<!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
&lt;voronoi_builder.hpp&gt;</span><br style="font-family: Courier New,Courier,monospace;">
      <span style="font-family: Courier New,Courier,monospace;">#include
&lt;voronoi_diagram.hpp&gt;</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
&lt;typename T,</span><br style="font-family: 'Courier New',Courier,monospace;">
      <span style="font-family: 'Courier New',Courier,monospace;">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
typename CTT = detail::voronoi_ctype_traits&lt;T&gt;,</span><br style="font-family: 'Courier New',Courier,monospace;">
      <span style="font-family: 'Courier New',Courier,monospace;">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
typename VP = detail::voronoi_predicates&lt;CTT&gt; &gt;</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&amp; x,<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
const int_type&amp; 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&amp;
x1,<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
const int_type&amp; y1,<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
const int_type&amp; x2,<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
const int_type&amp; 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
&lt;typename OUTPUT&gt;<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 &lt;typename T&gt;<br>
struct voronoi_ctype_traits;<br>
      <br>
template &lt;&gt;<br>
struct voronoi_ctype_traits&lt;int32&gt; {<br>
&nbsp;&nbsp;&nbsp; typedef int32 int_type;<br>
&nbsp;&nbsp;&nbsp; typedef int64 int_x2_type;<br>
&nbsp;&nbsp;&nbsp; typedef uint64 uint_x2_type;<br>
&nbsp;&nbsp;&nbsp; typedef extended_int&lt;128&gt; big_int_type;<br>
&nbsp;&nbsp;&nbsp; typedef fpt64 fpt_type;<br>
&nbsp;&nbsp;&nbsp; typedef extended_exponent_fpt&lt;fpt_type&gt;
efpt_type;<br>
&nbsp;&nbsp;&nbsp; typedef ulp_comparison&lt;fpt_type&gt; ulp_cmp_type;<br>
&nbsp;&nbsp;&nbsp; typedef type_converter_fpt to_fpt_converter_type;<br>
&nbsp;&nbsp;&nbsp; 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">&nbsp;</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>
Commit	Line	Data
7c673cae FG	1	<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
	2	<html><head>
	3
	4
	5
	6	<meta http-equiv="Content-Language" content="en-us">
	7	<meta http-equiv="Content-Type" content="text/html; charset=windows-1252"><title>Voronoi Builder</title></head><body>
	8	<table style="margin: 0pt; padding: 0pt; width: 100%;" border="0" cellpadding="0" cellspacing="0">
	9	<tbody>
	10	<tr>
	11	<td style="background-color: rgb(238, 238, 238);" nowrap="1" valign="top">
	12	<div style="padding: 5px;" align="center"> <img src="images/boost.png" border="0" height="86" width="277"><a title="www.boost.org home page" tabindex="2" style="border: medium none ;" href="http://www.boost.org/"> </a></div>
	13	<div style="margin: 5px;">
	14	<h3 class="navbar">Contents</h3>
	15	<ul>
	16	<li><a href="index.htm">Boost.Polygon Main Page</a></li>
	17	<li><a href="gtl_design_overview.htm">Design Overview</a></li>
	18	<li><a href="gtl_isotropy.htm">Isotropy</a></li>
	19	<li><a href="gtl_coordinate_concept.htm">Coordinate Concept</a></li>
	20	<li><a href="gtl_interval_concept.htm">Interval Concept</a></li>
	21	<li><a href="gtl_point_concept.htm">Point Concept</a></li>
	22	<li><a href="gtl_segment_concept.htm">Segment Concept</a></li>
	23	<li><a href="gtl_rectangle_concept.htm">Rectangle Concept</a></li>
	24	<li><a href="gtl_polygon_90_concept.htm">Polygon 90 Concept</a></li>
	25	<li><a href="gtl_polygon_90_with_holes_concept.htm">Polygon 90
	26	With Holes Concept</a></li>
	27	<li><a href="gtl_polygon_45_concept.htm">Polygon 45 Concept</a></li>
	28	<li><a href="gtl_polygon_45_with_holes_concept.htm">Polygon 45
	29	With Holes Concept</a></li>
	30	<li><a href="gtl_polygon_concept.htm">Polygon Concept</a></li>
	31	<li><a href="gtl_polygon_with_holes_concept.htm">Polygon With
	32	Holes Concept</a></li>
	33	<li><a href="gtl_polygon_90_set_concept.htm">Polygon 90 Set
	34	Concept</a></li>
	35	<li><a href="gtl_polygon_45_set_concept.htm">Polygon 45 Set
	36	Concept</a></li>
	37	<li><a href="gtl_polygon_set_concept.htm">Polygon Set Concept</a></li>
	38	<li><a href="gtl_connectivity_extraction_90.htm">Connectivity
	39	Extraction 90</a></li>
	40	<li><a href="gtl_connectivity_extraction_45.htm">Connectivity
	41	Extraction 45</a></li>
	42	<li><a href="gtl_connectivity_extraction.htm">Connectivity
	43	Extraction</a></li>
	44	<li><a href="gtl_property_merge_90.htm">Property Merge 90</a></li>
	45	<li><a href="gtl_property_merge_45.htm">Property Merge 45</a></li>
	46	<li><a href="gtl_property_merge.htm">Property Merge</a></li>
	47	<li><a href="voronoi_main.htm">Voronoi Main Page </a></li>
	48	<li><a href="voronoi_benchmark.htm">Voronoi Benchmark</a> </li>
	49	<li>Voronoi Builder</li>
	50	<li><a href="voronoi_diagram.htm">Voronoi Diagram</a></li>
	51	</ul>
	52	<h3 class="navbar">Other Resources</h3>
	53	<ul>
	54	<li><a href="GTL_boostcon2009.pdf">GTL Boostcon 2009 Paper</a></li>
	55	<li><a href="GTL_boostcon_draft03.pdf">GTL Boostcon 2009
	56	Presentation</a></li>
	57	<li><a href="analysis.htm">Performance Analysis</a></li>
	58	<li><a href="gtl_tutorial.htm">Layout Versus Schematic Tutorial</a></li>
	59	<li><a href="gtl_minkowski_tutorial.htm">Minkowski Sum Tutorial</a></li>
	60	<li><a href="voronoi_basic_tutorial.htm">Voronoi Basic Tutorial</a></li>
	61	<li><a href="voronoi_advanced_tutorial.htm">Voronoi Advanced
	62	Tutorial</a></li>
	63	</ul>
	64	</div>
65	<h3 class="navbar">Polygon Sponsor</h3>
66	<div style="padding: 5px;" align="center"> <img src="images/intlogo.gif" border="0" height="51" width="127"><a title="www.adobe.com home page" tabindex="2" style="border: medium none ;" href="http://www.adobe.com/"> </a></div>
67	</td>
68	<td style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;" valign="top" width="100%"><!-- End Header --> <br>
69	<h1>Voronoi Builder </h1>
70	The Voronoi builder is the event generator structure, that implements
71	the <a href="http://en.wikipedia.org/wiki/Sweep_line_algorithm">sweepline
72	algorithm</a>,
73	scanning 2D space and spawning the two types of events: <a href="http://www.ams.org/samplings/feature-column/fcarc-voronoi">site
74	events and circle events</a>. Each event is reported to the output data
75	structure builder.
76	The structure shares Voronoi name, as the events generated by it
77	provide
78	enough information to construct the Voronoi diagram of a set of points
79	and linear segments. The requirements for the coordinate type of
80	the input/output geometries, configured through the coordinate type
81	traits template argument, are the following:<br>
82	<ul>
83	<li>The input coordinate type (for input points and enpoints of
84	the input segments) is not required to be integral
85	(while it
86	still should be an integer type)</li>
87	<li>The output coordinate type (for
88	Voronoi vertices) is required to be IEEE-754 floating point type</li>
89	</ul>
90	<h2>Important</h2>
91	The users are encouraged to use the default static methods defined in
92	the <a href="../../../boost/polygon/voronoi.hpp">voronoi.hpp</a>
93	header for the Voronoi diagram construction. However it's also possible
94	to
95	use Voronoi builder explicitly, especially if the user wants to drop
96	the external dependencies such as MPL (metaprogramming library). The
97	following include set doesn't depend on any external headers
98	(except STL and boost/cstdint.hpp), even
99	the Boost.Polygon library:<br>
100	<br>
101	<span style="font-family: Courier New,Courier,monospace;">#include
102	<voronoi_builder.hpp></span><br style="font-family: Courier New,Courier,monospace;">
103	<span style="font-family: Courier New,Courier,monospace;">#include
104	<voronoi_diagram.hpp></span><br>
105	<h2>Declaration</h2>
106	Header: <a href="../../../boost/polygon/voronoi_builder.hpp">boost/polygon/voronoi_builder.hpp</a><br>
107	<br>
108	<font face="Courier New"> <span style="font-family: 'Courier New',Courier,monospace;">template
109	<typename T,</span><br style="font-family: 'Courier New',Courier,monospace;">
110	<span style="font-family: 'Courier New',Courier,monospace;">
111	typename CTT = detail::voronoi_ctype_traits<T>,</span><br style="font-family: 'Courier New',Courier,monospace;">
112	<span style="font-family: 'Courier New',Courier,monospace;">
113	typename VP = detail::voronoi_predicates<CTT> ></span><br style="font-family: 'Courier New',Courier,monospace;">
114	<span style="font-family: 'Courier New',Courier,monospace;">class
115	voronoi_builder;</span><br>
116	<br>
117	<span style="font-family: 'Courier New',Courier,monospace;">T</span></font>
118	- specifies the coordinate type of the input geometries (points and
119	segments).<br>
120	<font face="Courier New"> <span style="font-family: 'Courier New',Courier,monospace;">CTT</span></font>
121	- defines the input/output coordinate type traits used by the Voronoi
122	predicates (VP).<br>
123	<font face="Courier New"> <span style="font-family: 'Courier New',Courier,monospace;">VP</span></font>
124	- the predicate kernel, that contains robust and
125	efficient predicates and functors.<br>
126	The Voronoi builder data structure is ready to use from the box with
127	32-bit signed integer input coordinate type. The user may extend the
128	input coordinate range to the other integer types (e.g. 64-bit
129	integer), however this will also require manual setup of the
130	coordinate type traits. Default predicate kernel provides correct and
131	efficient predicates as long as types
132	defined by the coordinate type traits satisfy the requirements
133	explained at the end of this page. In case
134	those
135	requirements are not satisfied,<font face="Courier New"><span style="font-family: 'Courier New',Courier,monospace;"></span></font>
136	the proper predicate kernel
137	implementation is required.<span style="font-family: Courier New,Courier,monospace;"></span><br>
138	<h2>Member Functions</h2>
139	<table style="text-align: left; width: 100%;" border="1" cellpadding="2" cellspacing="2">
140	<tbody>
141	<tr>
142	<td style="font-family: 'Courier New',Courier,monospace;"><span style="font-weight: bold;">voronoi_builder</span>()</td>
143	<td width="693">Default
144	constructor.</td>
145	</tr>
146	<tr>
147	<td><span style="font-family: Courier New,Courier,monospace;">size_t <span style="font-weight: bold;">insert_point</span>(const int_type& x,<br>
148
149	const int_type& y)</span> </td>
150	<td>Inserts a point object with
151	the specified coordinates into the Voronoi builder.<br>
152	Returns index of the inserted point. </td>
153	</tr>
154	<tr>
155	<td><span style="font-family: Courier New,Courier,monospace;">size_t <span style="font-weight: bold;">insert_segment</span>(const int_type&
156	x1,<br>
157
158	const int_type& y1,<br>
159
160	const int_type& x2,<br>
161
162	const int_type& y2)</span> </td>
163	<td>Inserts a segment object
164	with the specified coordinates into the Voronoi builder.<br>
165	Returns index of the inserted segment. </td>
166	</tr>
167	<tr>
168	<td style="font-family: 'Courier New',Courier,monospace;">template
169	<typename OUTPUT><br>
170	void <span style="font-weight: bold;">construct</span>(OUTPUT* output)
171	</td>
172	<td width="693">Runs the sweepline
173	algorithm over the set of inserted geometries and generates site and
174	circle events to the OUTPUT data structure. It's the responsibility of
175	the
176	output data structure to process them.<br>
177	Complexity: O(N * log N), where N is the total number of input points and segments.<br>
178	</td>
179	</tr>
180	<tr>
181	<td style="font-family: 'Courier New',Courier,monospace;">void
182	<span style="font-weight: bold;">clear</span>() </td>
183	<td width="693">Clears the
184	list of the inserted geometries. Sets the input geometry index to
185	zero. </td>
186	</tr>
187	</tbody>
188	</table>
189	<h1>Voronoi Coordinate Type Traits</h1>
190	<p>The library provides the default coordinate type traits
191	specialization for the
192	32-bit signed integer type:</p>
193	<font style="font-family: 'Courier New',Courier,monospace;" face="Courier New">
194	<p>template <typename T><br>
195	struct voronoi_ctype_traits;<br>
196	<br>
197	template <><br>
198	struct voronoi_ctype_traits<int32> {<br>
199	typedef int32 int_type;<br>
200	typedef int64 int_x2_type;<br>
201	typedef uint64 uint_x2_type;<br>
202	typedef extended_int<128> big_int_type;<br>
203	typedef fpt64 fpt_type;<br>
204	typedef extended_exponent_fpt<fpt_type>
205	efpt_type;<br>
206	typedef ulp_comparison<fpt_type> ulp_cmp_type;<br>
207	typedef type_converter_fpt to_fpt_converter_type;<br>
208	typedef type_converter_efpt to_efpt_converter_type;<br>
209	};</p>
210	</font> One
211	of the most important features of the library is that Voronoi builder
212	output geometries are constructed within defined relative error (64
213	machine epsilons). That means, the more mantissa bits the user provided
214	fpt_type has, the better precision of the output geometries will be. In
215	order for the user defined traits to be consistent with the default
216	Voronoi builder predicate kernel user should define the following set
217	of traits (the assumption is made that input geometries have
218	X-bit signed integer coordinate type):<br>
219	<br>
220	<table style="text-align: left; width: 100%;" border="1" cellpadding="2" cellspacing="2">
221	<tbody>
222	<tr>
223	<td style="font-family: 'Courier New',Courier,monospace; font-weight: bold;">int_type
224	</td>
225	<td style="vertical-align: top;">At least X-bit signed
226	integer type. </td>
227	</tr>
228	<tr>
229	<td style="vertical-align: top; font-family: 'Courier New',Courier,monospace; font-weight: bold;">int_x2_type
230	</td>
231	<td style="vertical-align: top;">At least 2X-bit signed
232	integer type. </td>
233	</tr>
234	<tr>
235	<td style="vertical-align: top; font-family: 'Courier New',Courier,monospace; font-weight: bold;">uint_x2_type
236	</td>
237	<td style="vertical-align: top;">At least 2X-bit unsigned
238	integer type. </td>
239	</tr>
240	<tr>
241	<td style="vertical-align: top; font-family: 'Courier New',Courier,monospace; font-weight: bold;">big_int_type
242	</td>
243	<td style="vertical-align: top;">At least 8X-bit signed
244	integer type if input dataset contains only points.<br>
245	At least 64X-bit signed integer type if input dataset contains
246	segments. </td>
247	</tr>
248	<tr>
249	<td style="vertical-align: top; font-family: 'Courier New',Courier,monospace; font-weight: bold;">fpt_type
250	</td>
251	<td style="vertical-align: top;">IEEE-754 floating point
252	type, with mantissa at least (X+16) bits and exponent able to handle
253	32X-bit unsigned integer type. </td>
254	</tr>
255	<tr>
256	<td style="vertical-align: top; font-family: 'Courier New',Courier,monospace; font-weight: bold;">efpt_type
257	</td>
258	<td style="vertical-align: top;">IEEE-754 floating point
259	type, with mantissa at least (X+16) bits and exponent able to handle
260	64X-bit unsigned integer type. </td>
261	</tr>
262	<tr>
263	<td style="vertical-align: top; font-family: 'Courier New',Courier,monospace; font-weight: bold;">ulp_cmp_type
264	</td>
265	<td style="vertical-align: top;">Ulp comparison structure,
266	that checks if two fpt_type values are within the given ulp range
267	(relative error range). </td>
268	</tr>
269	<tr>
270	<td style="vertical-align: top; font-family: 'Courier New',Courier,monospace; font-weight: bold;">to_fpt_converter_type
271	</td>
272	<td style="vertical-align: top;">Type converter structure,
273	that converts any of the integer types above plus efpt_type to the
274	fpt_type using operator(). </td>
275	</tr>
276	<tr>
277	<td style="vertical-align: top; font-family: 'Courier New',Courier,monospace; font-weight: bold;">to_efpt_converter_type
278	</td>
279	<td style="vertical-align: top;">Type converter structure,
280	that converts any of the integer types above to the efpt_type using
281	operator(). </td>
282	</tr>
283	</tbody>
284	</table>
285	<p>Notes:</p>
286	<ul>
287	<li>Four different integer types are used (instead of a single
288	big_int_type) to slightly improve algorithm performance and memory
289	usage.</li>
290	<li>As the maximum required size of the big_int_type is known
291	in advance, it's possible to use fixed, stack allocated, multiprecision
292	integer type.</li>
293	<li>Two separate floating-point types are defined, because for
294	the input geometries
295	with
296	32-bit signed integer coordinates, double type won't be able to handle
297	2048-bit (64 chunks of 32 bits each) integers, as they will
298	overflow its exponent. On the
299	gcc compiler it's possible to use 80-bit long doubles for both fpt
300	types, however this is not supported by the MSVC compiler.</li>
301	<li>efpt_type and to_efpt_converter_type are not used to
302	construct the Voronoi diagram of a set of points (mock implementation
303	will work).</li>
304	<li>For an example of the user defined coordinate type traits
305	check the <a href="voronoi_advanced_tutorial.htm">advanced Voronoi
306	tutorial</a>.</li>
307	</ul>
308	</td>
309	</tr>
310	<tr>
311	<td style="background-color: rgb(238, 238, 238);" nowrap="1"> </td>
312	<td style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;" valign="top" width="100%">
313	<table class="docinfo" id="table2" frame="void" rules="none">
314	<colgroup> <col class="docinfo-name"><col class="docinfo-content"> </colgroup> <tbody valign="top">
315	<tr>
316	<th class="docinfo-name">Copyright:</th>
317