devn00b
/
EQ2EMu


			
				
					
						
						
							123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365
							<!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 Main</title>
  <meta http-equiv="content-type" content="text/html; charset=utf-8">
  <meta http-equiv="content-type" content="text/html; charset=utf-8">
  <meta http-equiv="content-type" content="text/html; charset=utf-8">
  <meta http-equiv="content-type" content="text/html; charset=utf-8"></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>Voronoi Main Page </li>
        <li><a href="voronoi_benchmark.htm">Voronoi Benchmark</a></li>
        <li><a href="voronoi_builder.htm">Voronoi Builder</a> </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>THE BOOST POLYGON VORONOI EXTENSIONS</h1>
      <img style="width: 900px; height: 300px;" alt="" src="images/voronoi3.png"><br>
The Voronoi extensions of the Boost Polygon library provide functionality to
construct a <a href="voronoi_diagram.htm">Voronoi diagram</a> of a set of points
and linear segments in 2D space with the following set of limitations:<br>
      <ul>
        <li>Coordinates of the input points and endpoints of the input segments should have integral type. The int32 data type is supported by the default implementation. Support for the other data types (e.g. int64) could be achieved through the configuration of the coordinate type traits (<a href="voronoi_advanced_tutorial.htm">Voronoi Advanced tutorial</a>).</li>
        <li>Input points and segments should not overlap except their endpoints. This means that input point should not lie inside the input segment and input segments should not intersect except their endpoints.</li>
      </ul>
While the first restriction is permanent (it
allows to give the exact warranties about the output precision and
algorithm execution flow),
the second one may be resolved using the Boost.Polygon <a href="gtl_segment_concept.htm">segment utils</a>.
The strong sides of the
library and the main benefits comparing to the other implementations are
discussed in the following paragraphs.<br>
<h2>Fully Functional with Segments</h2>
There are just a few implementations of the Voronoi diagram
construction
algorithm that can
handle input data sets that contain linear segments, even considering
the commercial
libraries.
Support of the
segments allows to discretize any input geometry (sampled
floating-point coordinates can be scaled and snapped to the integer
grid): circle, ellipse,
parabola. This functionality allows to compute
the medial axis transform of the arbitrary set of input geometries,
with direct applications in the computer vision
projects.
      <h2>Robustness and Efficiency</h2>
Robustness issues can be divided onto the two main categories: memory
management
issues and numeric stability issues. The implementation avoids the
first type of the issues using pure STL data structures, thus there is
no
presence of the new operator in the code. The second category of
the problems is
resolved using the multiprecision geometric
predicates.
Even for the commercial libraries, usage of such predicates
results in a vast performance slowdown. The library implementation
overcomes this by avoiding the multiprecision
computations in the 95% of the cases by
using the efficient, floating-point based predicates. Such predicates
don't
produce the correct result always, however the library embeds the
relative
error arithmetic apparatus to identify such situations and switch
to the
higher precision predicates when appropriate. As the result, the
implementation has a solid performance comparing to the other known
libraries (more details in the <a href="voronoi_benchmark.htm">benchmarks</a>).<br>
      <h2>Precision of the Output Structures </h2>
The implementation guaranties, that the relative error of the
coordinates of the output
geometries is at most 64 machine epsilons (6
bits of mantissa, for the IEEE-754 floating-point type), while on
average it's slightly lower. This means, that the precision of the
output
geometries can be increased simply by using a floating-point type with
the larger mantissa. The practical point of this statements is
explained in the following table:<br>
      <table style="text-align: left; width: 100%;" border="1" cellpadding="2" cellspacing="2">
        <tbody>
          <tr>
            <td style="vertical-align: top;">Output Coordinate Type </td>
            <td style="vertical-align: top;">Output Coordinate Value </td>
            <td style="vertical-align: top;">Max Absolute Error </td>
            <td style="vertical-align: top;">Precise Value Range </td>
          </tr>
          <tr>
            <td style="vertical-align: top;">double (53 bit mantissa) </td>
            <td style="vertical-align: top;">1 </td>
            <td style="vertical-align: top;">2<sup>-53</sup> * 2<sup>6</sup>
= 2<sup>-47</sup></td>
            <td style="vertical-align: top;">1 ± 2<sup>-47</sup></td>
          </tr>
          <tr>
            <td style="vertical-align: top;">double (53 bit mantissa) </td>
            <td style="vertical-align: top;">2<sup>31</sup> </td>
            <td style="vertical-align: top;">2<sup>-53</sup> * 2<sup>31</sup>
* 2<sup>6</sup> = 2<sup>-16</sup></td>
            <td style="vertical-align: top;">2<sup>31</sup> ± 2<sup>-16</sup></td>
          </tr>
          <tr>
            <td style="vertical-align: top;">long double (64 bit
mantissa)</td>
            <td style="vertical-align: top;">1 </td>
            <td style="vertical-align: top;">2<sup>-64</sup> * 2<sup>6</sup>
= 2<sup>-58</sup></td>
            <td style="vertical-align: top;">1 ± 2<sup>-58</sup></td>
          </tr>
          <tr>
            <td style="vertical-align: top;">long double (64 bit
mantissa) </td>
            <td style="vertical-align: top;">2<sup>31</sup></td>
            <td style="vertical-align: top;">2<sup>-64</sup> * 2<sup>31</sup>
* 2<sup>6</sup> = 2<sup>-27</sup></td>
            <td style="vertical-align: top;">2<sup>31</sup> ± 2<sup>-27</sup></td>
          </tr>
        </tbody>
      </table>
Detailed description of the absolute and relative errors evaluation can
be found in the article: <a href="http://docs.oracle.com/cd/E19957-01/806-3568/ncg_goldberg.html">"What
Every Computer Scientist Should Know About Floating-Point Arithmetic"</a><a href="http://docs.oracle.com/cd/E19957-01/806-3568/ncg_goldberg.html"></a>.<br>
      <br>
During the finalization step the implementation unites Voronoi vertices whose both
coordinates are located within the relative error range equal to 128
machine epsilons and removes any Voronoi edges between those. This is
the only case, that might cause differences between the algorithm output
topology and theoretically precise one, and practically means the
following: for a Voronoi diagram of a set of solid bodies inside the
Solar System (radius 2<sup>42</sup> metres) and the long double (64 bit
mantissa) output coordinate type the maximum absolute error within the
Solar System rectangle will be equal to 2<sup>-64</sup> * 2<sup>42</sup>
* 2<sup>6</sup> = 2<sup>-18</sup> metres; as the result, vertices with
both coordinates that are within 2<sup>-18</sup> metres (8
micrometres or the size of a bacteria) will be considered
equal and united.<br>
      <h2>Simple Interface </h2>
The <a href="../../../boost/polygon/voronoi.hpp">boost/polygon/</a><a href="../../../boost/polygon/voronoi.hpp">voronoi.hpp</a>
library header defines the following static functions to integrate the
Voronoi extensions functionality with the Boost.Polygon interfaces:<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;">template
&lt;typename Point, typename VB&gt;<br>
size_t <span style="font-weight: bold;">insert</span>(const Point
&amp;point, VB *vb) </td>
            <td>Inserts a point into a Voronoi builder data structure.<br>
Point type should model the point concept.<br>
Returns index of the inserted site. </td>
          </tr>
          <tr>
            <td style="font-family: Courier New,Courier,monospace;">template
&lt;typename PointIterator, typename VB&gt;<br>
void <span style="font-weight: bold;">insert</span>(PointIterator
first, <br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
PointIterator last,<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; VB
*vb) </td>
            <td>Inserts an iterator range of points into a Voronoi
builder data structure.<br>
Corresponding point type should model the point concept. </td>
          </tr>
          <tr>
            <td style="font-family: Courier New,Courier,monospace;">template
&lt;typename Segment, typename VB&gt;<br>
size_t <span style="font-weight: bold;">insert</span>(const Segment
&amp;segment, VB *vb) </td>
            <td>Inserts a segment into a Voronoi builder data
structure.<br>
Segment type should model the segment concept.<br>
Returns index of the inserted site. </td>
          </tr>
          <tr>
            <td style="font-family: Courier New,Courier,monospace;">template
&lt;typename SegmentIterator, typename VB&gt;<br>
void <span style="font-weight: bold;">insert</span>(SegmentIterator
first,<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
SegmentIterator last,<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; VB
*vb) </td>
            <td>Inserts an iterator range of segments into a Voronoi
builder data structure.<br>
Corresponding segment type should model the segment concept. </td>
          </tr>
          <tr>
            <td style="font-family: Courier New,Courier,monospace;">template
&lt;typename PointIterator, typename VD&gt;<br>
void <span style="font-weight: bold;">construct_voronoi</span>(PointIterator
first,<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
PointIterator last,<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
VD *vd) </td>
            <td>Constructs a Voronoi diagram of a set of points.<br>
Corresponding point type should model the point concept.<br>
Complexity: O(N * log N), memory usage: O(N), where N is the total number of input points.<br>
 </td>
          </tr>
          <tr>
            <td style="font-family: Courier New,Courier,monospace;">template
&lt;typename SegmentIterator, typename VD&gt;<br>
void <span style="font-weight: bold;">construct_voronoi</span>(SegmentIterator
first,<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
SegmentIterator last,<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
VD *vd) </td>
            <td>Constructs a Voronoi diagram of a set of segments.<br>
Corresponding segment type should model the segment concept.<br>
Complexity: O(N * log N), memory usage: O(N), where N is the total number of input segments.<br>
 </td>
          </tr>
          <tr>
            <td style="font-family: Courier New,Courier,monospace;">template
&lt;typename PointIterator,<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; typename
SegmentIterator,<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; typename VD&gt;<br>
void <span style="font-weight: bold;">construct_voronoi</span>(PointIterator
p_first,<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
PointIterator p_last,<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
SegmentIterator s_first,<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
SegmentIterator s_last,<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
VD *vd) </td>
            <td>
              Constructs a Voronoi diagram of a set of points and segments.<br>
              Corresponding point type should model the point concept.<br>
              Corresponding segment type should model the segment concept.<br>
              Complexity: O(N* log N), memory usage: O(N), where N is the total number of input points and segments.<br>
            </td>
          </tr>
        </tbody>
      </table>
      <br>
The following two lines of code construct a Voronoi diagram of a set of
points (as long as the corresponding input geometry type satisfies the
Boost.Polygon <a href="gtl_design_overview.htm">concept model</a>):<br>
      <br>
      <span style="font-family: Courier New,Courier,monospace;">voronoi_diagram&lt;double&gt;
vd;</span><br style="font-family: Courier New,Courier,monospace;">
      <span style="font-family: Courier New,Courier,monospace;">construct_voronoi(points.begin(),
points.end(), &amp;vd);</span><br>
      <br>
The library provides the clear interfaces to associate the user data
with the
output geometries and efficiently traverse
the
Voronoi graph.
More details on those topics are covered in the <a href="voronoi_basic_tutorial.htm">basic Voronoi tutorial</a>. Advanced
usage of the library with the configuration of the coordinate
types is explained in the <a href="voronoi_advanced_tutorial.htm">advanced
Voronoi tutorial</a>.
The library allows users to implement their own Voronoi diagram /
Delaunay triangulation construction routines based on the <a href="voronoi_builder.htm">Voronoi builder API</a>.<br>
      <h2>No Third Party Dependencies </h2>
The Voronoi extensions of the Boost Polygon library doesn't depend on
any 3rd party code
and contains single dependency on the Boost libraries:
boost/cstdint.hpp.
All the required multiprecision types and related functionality are
encapsulated as
part of the implementation. The library is fast to compile (3 public
and 4 private heades), has strong cohesion between its components and
is clearly modularized from the rest of the Boost Polygon library, with
the optional integration through the <a href="../../../boost/polygon/voronoi.hpp">voronoi.hpp</a> header.<br>
      <h2>Extensible for the User Provided Coordinate Types</h2>
The implementation is coordinate type agnostic. As long
as the user provided types satisfy the set of the requirements of the <a href="voronoi_builder.htm">Voronoi builder</a> coordinate type traits, no additional changes are required
neither to the algorithm, nor to the implementation of the predicates.
For example, it's possible to
construct the Voronoi diagram with the 256-bit integer input coordinate
type and 512-bit output floating-point type without making any changes to the
library.<br>
      <h2>Future Development </h2>
      Below one may find the list of the possible directions for the future
      development of the library.<br>
      <ul>
        <li>Delaunay triangulation data structure implementation.</li>
        <li>Medial axis data structure implementation.</li>
        <li>Serialization utilities for the Voronoi diagram data structure.</li>
        <li>Drop the restriction on the non-intersecting input geometries.</li>
        <li>Support for the different types of the distance metrics.</li>
      </ul>
      <h2>Theoretical Research </h2>
The Voronoi extensions were developed as part of the Google Summer of Code 2010.
The library was actively maintained for the last three years and involved deep
mathematical research in the field of algorithms, data structures, relative
error arithmetic and numerical robustness. Upon the community request,
more details on the theoretical aspects of the implementation will be published.
The authors would like to acknowledge the Steven Fortune's article
"<a href="http://dl.acm.org/citation.cfm?id=10549">A Sweepline algorithm for Voronoi diagrams</a>",
that covers fundamental ideas of the current implementation. </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>
            <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>