ceph/src/boost/libs/polygon/doc/voronoi_builder.htm

   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 &lt;voronoi_builder.hpp&gt;</span><br style="font-family: Courier New,Courier,monospace;">
 103       <span style="font-family: Courier New,Courier,monospace;">#include
 104 &lt;voronoi_diagram.hpp&gt;</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 &lt;typename T,</span><br style="font-family: 'Courier New',Courier,monospace;">
 110       <span style="font-family: 'Courier New',Courier,monospace;">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
 111 typename CTT = detail::voronoi_ctype_traits&lt;T&gt;,</span><br style="font-family: 'Courier New',Courier,monospace;">
 112       <span style="font-family: 'Courier New',Courier,monospace;">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
 113 typename VP = detail::voronoi_predicates&lt;CTT&gt; &gt;</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&amp; x,<br>
 148 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
 149 const int_type&amp; 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&amp;
 156 x1,<br>
 157 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
 158 const int_type&amp; y1,<br>
 159 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
 160 const int_type&amp; x2,<br>
 161 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
 162 const int_type&amp; 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 &lt;typename OUTPUT&gt;<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 &lt;typename T&gt;<br>
 195 struct voronoi_ctype_traits;<br>
 196       <br>
 197 template &lt;&gt;<br>
 198 struct voronoi_ctype_traits&lt;int32&gt; {<br>
 199 &nbsp;&nbsp;&nbsp; typedef int32 int_type;<br>
 200 &nbsp;&nbsp;&nbsp; typedef int64 int_x2_type;<br>
 201 &nbsp;&nbsp;&nbsp; typedef uint64 uint_x2_type;<br>
 202 &nbsp;&nbsp;&nbsp; typedef extended_int&lt;128&gt; big_int_type;<br>
 203 &nbsp;&nbsp;&nbsp; typedef fpt64 fpt_type;<br>
 204 &nbsp;&nbsp;&nbsp; typedef extended_exponent_fpt&lt;fpt_type&gt;
 205 efpt_type;<br>
 206 &nbsp;&nbsp;&nbsp; typedef ulp_comparison&lt;fpt_type&gt; ulp_cmp_type;<br>
 207 &nbsp;&nbsp;&nbsp; typedef type_converter_fpt to_fpt_converter_type;<br>
 208 &nbsp;&nbsp;&nbsp; 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">&nbsp;</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             <td>Copyright © Andrii Sydorchuk 2010-2013.</td>
 318           </tr>
 319           <tr class="field">
 320             <th class="docinfo-name">License:</th>
 321             <td class="field-body">Distributed under the Boost Software
 322 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">
 323 http://www.boost.org/LICENSE_1_0.txt</a>)</td>
 324           </tr>
 325         </tbody>
 326       </table>
 327       </td>
 328     </tr>
 329   </tbody>
 330 </table>
 331
 332 </body></html>