|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r83513 - trunk/libs/polygon/doc
From: sydorchuk.andriy_at_[hidden]
Date: 2013-03-21 19:08:58
Author: asydorchuk
Date: 2013-03-21 19:08:57 EDT (Thu, 21 Mar 2013)
New Revision: 83513
URL: http://svn.boost.org/trac/boost/changeset/83513
Log:
Polygon: updated Voronoi Main documentation page.
Text files modified:
trunk/libs/polygon/doc/voronoi_main.htm | 469 +++++++++++++++++++++++----------------
1 files changed, 270 insertions(+), 199 deletions(-)
Modified: trunk/libs/polygon/doc/voronoi_main.htm
Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk
==============================================================================
--- trunk/libs/polygon/doc/voronoi_main.htm (original)
+++ trunk/libs/polygon/doc/voronoi_main.htm 2013-03-21 19:08:57 EDT (Thu, 21 Mar 2013)
@@ -1,44 +1,26 @@
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
-<html><head>
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
+<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=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">
-
+ <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>
+ <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>
@@ -49,7 +31,6 @@
<li>Interval Concept</li>
<li>Point Concept</li>
<li>Segment Concept</li>
-
<li>Rectangle Concept</li>
<li>Polygon 90 Concept</li>
<li><a href="gtl_polygon_90_with_holes_concept.htm">Polygon 90
@@ -83,7 +64,6 @@
<li>Voronoi Predicates</li>
<li>Voronoi Robust FPT<br>
</li>
-
</ul>
<h3 class="navbar">Other Resources</h3>
<ul>
@@ -99,14 +79,20 @@
</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>
+ <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>
-
+ <td
+ style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;"
+ valign="top" width="100%"><!-- End Header --> <br>
<h1>THE BOOST.POLYGON VORONOI LIBRARY<br>
</h1>
- <img style="width: 900px; height: 300px;" alt="" src="images/voronoi3.png"><br>
-The Boost.Polygon Voronoi library provides functionality to construct the Voronoi diagram
+ <img style="width: 900px; height: 300px;" alt=""
+ src="images/voronoi3.png"><br>
+The Boost.Polygon Voronoi library provides functionality to construct
+the Voronoi diagram
of a set of points and linear segments in 2D space with the following
set of
limitations:<br>
@@ -120,223 +106,295 @@
While the first restriction is permanent (it
allows to give the exact warranties about the output precision and
algorithm execution),
-the second one may be resolved using the Boost.Polygon functionality.
+the second one may be resolved using the Boost.Polygon functionality (<a
+ href="gtl_segment_concept.htm">segment utils</a>).
The strong sides of the
library and main benefits comparing to the other implementations are
discussed in the following paragraphs.<span style="font-weight: bold;"></span><br>
<h2>Robustness and Efficiency</h2>
-Let's explain a bit those terms. The efficiency is simply measured by
-the time it takes the algorithm to execute. The robustness is a bit
-more harder to explain. But those of you who had the experience with
-the following situations would understand what it doesn't mean: application segfaults randomly, algorithm output contains
-degeneracies or is completely invalid (e.g. a point is considered to be outside of the polygon,
-while should be inside). In other words robust implementation doesn't
-fail and produces expected output in 100% of cases, thus user can rely
-on
-it. Robustness is a weak place of the most non-commercial
-implementations of any complex geometric algorithm. The main issues could be divided onto two main categories: memory management
-issues, numeric stability issues. Our implementation avoids the
-first type of issues using pure STL data structures, thus you won't find
-any operator new in the code. The second category of problems is
+Robustness issues can be divided onto two main categories: memory
+management
+issues and numeric stability issues. Our implementation avoids the
+first type of issues using pure STL data structures, thus there is no
+presence of the new operator in the code. The second category of
+problems is
resolved using multiprecision <a href="voronoi_predicates.htm">geometric
predicates</a>.
-Even for commercial implementations usage of such predicates usually
-results in a huge performance slowdown. Here is another strong side of
-the Boost.Polygon
-Voronoi library: we avoid multiprecision computations in 95% of cases
-using
-extremely fast floating-point predicates. Yes, those are not always
-exact, but we developed the <a href="voronoi_robust_fpt.htm">relative
-error arithmetic apparatus</a> to identify them and switch to the
-higher precision predicates when required.<br>
+Even for commercial implementations, usage of such predicates usually
+results in a vast performance slowdown. Boost.Polygon
+Voronoi implementation overcomes this by avoiding multiprecision
+computations in 95% of the cases and
+uses efficient, floating-point based predicates. Such preciates don't
+produce the correct result always, however the library embeds <a
+ href="voronoi_robust_fpt.htm">relative
+error arithmetic apparatus</a> 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 benchmarks).<br>
<h2>Precision of the Output Structures<br>
</h2>
-One of the extremely important results of using two types of predicates
-is that library efficiently computes relatively precise coordinates of
-the output geometries. Here we will explain a bit what exactly
-"relatively precise" means and how the received output may differ from
-the theoretically correct one (here and after we assume that output
-coordinate type is the IEEE-754 floating-point type).<br>
- <br>
-Voronoi implementation guaranties that the relative error of the
+Voronoi implementation guaranties, that the relative error of the
coordinates of the output
-geometries is always not higher than 64 machine epsilons (6
-bits of mantissa), while in many cases it is slightly less. That also
-means that using floating-point type with the larger mantissa will
-produce more precise output. Let's consider
-the following example: the output Voronoi
-vertex has double (53-bit mantissa) x-coordinate equal to 1.0, then the
-absolute error is at most 2^-53 * 2^6 = 2^-47 and the exact value of
-x-coordinate lies in the range [1.0 - 2^-47, 1.0 + 2^-47]. For
-x-coordinate equal to 2^31, the absolute error will be at most 2^-53 *
-2^31 * 2^6 = 2^-16 and the exact value of x-coordinate lies in the
-range
-[2^31 - 2^-16, 2^31 + 2^16]. For the output Voronoi vertex with long
-double
-(64-bit mantissa) x-coordinate equal to 2^31, the absolute error will
-be at most 2^-64 * 2 ^31 * 2^6 = 2^-27 and the exact value of
-x-coordinate
-lies in the range [2^31-2^-27, 2^31+2^-27]. If you'd like to become
-master of the absolute and relative error try this article.<br>
+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 precision of the output
+geometries can be increased simply by using 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<br>
+ </td>
+ <td style="vertical-align: top;">Output Coordinate Value<br>
+ </td>
+ <td style="vertical-align: top;">Max Absolute Error<br>
+ </td>
+ <td style="vertical-align: top;">Precise Value Range<br>
+ </td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top;">double (53 bit mantissa)<br>
+ </td>
+ <td style="vertical-align: top;">1<br>
+ </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)<br>
+ </td>
+ <td style="vertical-align: top;">2<sup>31</sup><br>
+ </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)<br>
+ </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
+During the finalization step the implementation unites Voronoi vertices
+whose both
coordinates are situated within the relative error range equal to 128
-machine epsilons and removes any Voronoi edges between them. That is
-the only case that might cause differences between the algorithm output
-topology and theoretically precise one. Now let's see what is the practical
-impact of this. Consider the following example: we are going to construct the
-Voronoi diagram of our Solar System. The radius of our Solar System is
-approximately 2^42 metres, and we are going to snap it to the integer
-grid of [-2^42; 2^42] x [-2^42; 2^42]. Let's choose the long double
-(64 bit mantissa) output coordinate type, then the maximum absolute error
-for the output geometries within our Solar System will be on its boundaries
-and equal to 2^-64 * 2^42 * 2^6 = 2^-18 metres. In the output we are going to
-consider vertices with both coordinates that are within 2^-17 metres (8
-micrometres) distance to be equal. That distance is equal to
-the size of a bacteria and is relative to the Solar System size.<br>
+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 the 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 the bacteria) are going to be considered
+equal.<br>
<h2>Fully Functional with Segments</h2>
-There are not many implementations of the Voronoi diagram construction
-algorithm that could
-handle linear segment inputs, even considering the commercial libraries.
+There are just a few implementations of the Voronoi diagram
+construction
+algorithm that can
+handle linear segment inputs, even considering the commercial
+libraries.
Support of the
-segments allows to discretize any input geometry (circle, ellipse,
-parabola). Of course as the result those might have floating-point
-coordinates, but that is resolved using scaling and snapping to the
-integer grid. This functionality is very handy as it allows to compute
-the medial axis transform of the arbitrary set of input geometries. So
-one may start
-using it for the next generation pattern recognition or computer vision
-project.<br>
- <h2>Basic and Advanced Usage Cases</h2>
-The main library header <span style="font-family: Courier New,Courier,monospace;">voronoi.hpp</span>
-defines the following static functions to integrate the Voronoi library functionality with the Boost.Polygon interfaces:<br>
+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 pattern recognition and computer vision
+projects.<br>
+ <h2>Simple Interface<br>
+ </h2>
+The main library header <span
+ style="font-family: Courier New,Courier,monospace;">voronoi.hpp</span>
+defines the following static functions to integrate the Voronoi library
+functionality with the Boost.Polygon interfaces:<br>
<br>
- <table style="text-align: left; width: 100%;" border="1" cellpadding="2" cellspacing="2">
+ <table style="text-align: left; width: 100%;" border="1"
+ cellpadding="2" cellspacing="2">
<tbody>
<tr>
- <td style="font-family: Courier New,Courier,monospace;">template <typename Point, typename VB><br>
-size_t <span style="font-weight: bold;">insert</span>(const Point &point, VB *vb)<br>
+ <td style="font-family: Courier New,Courier,monospace;">template
+<typename Point, typename VB><br>
+size_t <span style="font-weight: bold;">insert</span>(const Point
+&point, VB *vb)<br>
</td>
<td>Inserts a point into the Voronoi builder data structure.<br>
Point type should model the point concept.<br>
-
Returns index number of the inserted site.<br>
</td>
</tr>
<tr>
- <td style="font-family: Courier New,Courier,monospace;">template <typename PointIterator, typename VB><br>
-void <span style="font-weight: bold;">insert</span>(PointIterator first, <br>
- PointIterator last,<br>
- VB *vb)<br>
+ <td style="font-family: Courier New,Courier,monospace;">template
+<typename PointIterator, typename VB><br>
+void <span style="font-weight: bold;">insert</span>(PointIterator
+first, <br>
+
+PointIterator last,<br>
+ VB
+*vb)<br>
</td>
- <td>Inserts an iterator range of points into the Voronoi builder data structure.<br>
+ <td>Inserts an iterator range of points into the Voronoi
+builder data structure.<br>
Corresponding point type should model the point concept.<br>
</td>
</tr>
<tr>
- <td style="font-family: Courier New,Courier,monospace;">template <typename Segment, typename VB><br>
-size_t <span style="font-weight: bold;">insert</span>(const Segment &segment, VB *vb)<br>
+ <td style="font-family: Courier New,Courier,monospace;">template
+<typename Segment, typename VB><br>
+size_t <span style="font-weight: bold;">insert</span>(const Segment
+&segment, VB *vb)<br>
</td>
- <td>Inserts a segment into the Voronoi builder data structure.<br>
+ <td>Inserts a segment into the Voronoi builder data
+structure.<br>
Segment type should model the segment concept.<br>
-
Returns index number of the inserted site.<br>
</td>
</tr>
<tr>
- <td style="font-family: Courier New,Courier,monospace;">template <typename SegmentIterator, typename VB><br>
-void <span style="font-weight: bold;">insert</span>(SegmentIterator first,<br>
- SegmentIterator last,<br>
- VB *vb)<br>
+ <td style="font-family: Courier New,Courier,monospace;">template
+<typename SegmentIterator, typename VB><br>
+void <span style="font-weight: bold;">insert</span>(SegmentIterator
+first,<br>
+
+SegmentIterator last,<br>
+ VB
+*vb)<br>
</td>
- <td>Inserts an iterator range of segments into the Voronoi builder data structure.<br>
+ <td>Inserts an iterator range of segments into the Voronoi
+builder data structure.<br>
Corresponding segment type should model the segment concept.<br>
</td>
</tr>
-<tr>
- <td style="font-family: Courier New,Courier,monospace;">template <typename PointIterator, typename VD><br>
-void <span style="font-weight: bold;">construct_voronoi</span>(PointIterator first,<br>
+ <tr>
+ <td style="font-family: Courier New,Courier,monospace;">template
+<typename PointIterator, typename VD><br>
+void <span style="font-weight: bold;">construct_voronoi</span>(PointIterator
+first,<br>
+
PointIterator last,<br>
VD *vd)<br>
</td>
- <td>Constructs Voronoi diagram of a set of points.<br>Corresponding point type should model the point concept.<br>
+ <td>Constructs Voronoi diagram of a set of points.<br>
+Corresponding point type should model the point concept.<br>
</td>
</tr>
<tr>
- <td style="font-family: Courier New,Courier,monospace;">template <typename SegmentIterator, typename VD><br>
-void <span style="font-weight: bold;">construct_voronoi</span>(SegmentIterator first,<br>
+ <td style="font-family: Courier New,Courier,monospace;">template
+<typename SegmentIterator, typename VD><br>
+void <span style="font-weight: bold;">construct_voronoi</span>(SegmentIterator
+first,<br>
SegmentIterator last,<br>
VD *vd)<br>
</td>
- <td>Constructs Voronoi diagram of a set of segments.<br>Corresponding segment type should model the segment concept.<br>
+ <td>Constructs Voronoi diagram of a set of segments.<br>
+Corresponding segment type should model the segment concept.<br>
</td>
</tr>
<tr>
- <td style="font-family: Courier New,Courier,monospace;">template <typename PointIterator,<br>
- typename SegmentIterator,<br>
- typename VD><br>void <span style="font-weight: bold;">construct_voronoi</span>(PointIterator p_first,<br>
+ <td style="font-family: Courier New,Courier,monospace;">template
+<typename PointIterator,<br>
+ typename
+SegmentIterator,<br>
+ typename VD><br>
+void <span style="font-weight: bold;">construct_voronoi</span>(PointIterator
+p_first,<br>
+
+PointIterator p_last,<br>
-PointIterator p_last,<br>
SegmentIterator s_first,<br>
-SegmentIterator s_last,<br>
+SegmentIterator s_last,<br>
+
VD *vd)<br>
</td>
<td>Constructs Voronoi
-diagram of a set of points and segments.<br>Corresponding point type should model the point concept.<br>
+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>
</td>
</tr>
</tbody>
</table>
- <br>This
-means that it's possible to construct the Voronoi diagram with the
-following two lines of code (if corresponding input types satisfy the Boost.Polygon concept model):<br>
+ <br>
+The
+following two lines of code construct Voronoi diagram of points (as
+long as 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<double>
vd;</span><br style="font-family: Courier New,Courier,monospace;">
- <span style="font-family: Courier New,Courier,monospace;">construct_voronoi(points.begin(), points.end(), &vd);</span><br>
- <br>The library also provides the clear interfaces to
- associate user data with the output geometries and efficiently traverse Voronoi graph.
-More details on those are covered in the basic Voronoi tutorial. Advanced usage of the library with the configuration of the coordinate
+ <span style="font-family: Courier New,Courier,monospace;">construct_voronoi(points.begin(),
+points.end(), &vd);</span><br>
+ <br>
+The library also provides the clear interfaces to <a
+ href="voronoi_basic_tutorial.htm">associate user data</a> with the
+output geometries and efficiently <a href="voronoi_diagram.htm">traverse
+Voronoi graph</a>.
+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 also allows users to implement their own Voronoi diagram /
-Delaunay triangulation construction routines based on the Voronoi builder API.<br>
+The library allows users to implement their own Voronoi diagram /
+Delaunay triangulation construction structures based on the <a
+ href="voronoi_builder.htm">Voronoi builder API</a>.<br>
<h2>No Third Party Dependencies<br>
- </h2>Yes,
-the library doesn't depend on any 3rd party code. Even more than that
-there is only one dependency on the Boost libraries: boost/cstdint.hpp.
-All the required multiprecision types functionality is implemented as
-part of the library and is not exposed to the user. Considering the
-fact that Voronoi implementation consists of just 7 headers (3 public
-and 4 private) it is easy to compile it within a minute after download.
-On the other hand voronoi.hpp header provides integration routines with
-the Boost.Polygon concepts and models with a drawback of additional
-dependencies. <h2>Extensible for the User Provided Coordinate Types</h2>
-Our implementation is coordinate type agnostic. That means that as soon
-as user provided types satisfy the set of restrictions of the Voronoi builder coordinate type traits
-and implement methods required by the library, no changes are required
-neither to the algorithm, nor to the implementation of the predicates. So it's
+ </h2>
+The Boost.Polygon Voronoi 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 it's components and
+is clearly modularized from the rest of the Boost.Polygon library, with
+the optional integration via 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 soon
+as user provided types satisfy the set of restrictions of the <a
+ href="voronoi_builder.htm">Voronoi builder</a> coordinate type traits
+and implement methods required by the library, no additional changes
+are required
+neither to the algorithm, nor to the implementation of the predicates.
+Thus it's
possible to
construct Voronoi diagram for the 256-bit integer input coordinate type
and
512-bit output floating-point type without making any changes to the
internal code.<br>
- <h2>Bright Future<br>
+ <h2>Future Development<br>
</h2>
Below one may find the list of the main directions for the future
development of the library.<br>
High-priority tasks that already have approximate implementation plan
-are the following (some of those may be proposed as future GSoC projects):<br>
+are the following (some of those may be proposed as future GSoC
+projects):<br>
<ul>
- <li>Implementing Delaunay triangulation data structure.<br>
+ <li>Implement Delaunay triangulation data structure.<br>
Note: only data structure needs to be implemented that properly
processes events provided by the Voronoi builder.</li>
- <li>Implementing medial axis transform data structure.<br>
+ <li>Implement medial axis transform data structure.<br>
Note: in general case the Voronoi diagram has completely the same
geometry
as the medial axis (they are 100% equal), however for many applications
@@ -348,26 +406,28 @@
diagram data structure could be used to find K nearest neighbors of N
sites in O(N*K*log(K) + N*log(N)) time. The return value would be a
list of the k nearest neighbors for each site.<br>
-</li>
+ </li>
<li>Using the r-tree data structure built on top of the
bounding rectangles around the Voronoi cells to answer the nearest
-neighbor queries in log(N) time, where N is the number of the Voronoi cells.<br>
+neighbor queries in log(N) time, where N is the number of the Voronoi
+cells.<br>
Note: there should be r-tree data structure available soon as part of
the Boost libraries.</li>
-
- <li>Providing interface to retrieve the convex hull of a set of
-points and segments from the Voronoi builder once the Voronoi diagram is
-constructed in O(N) time.</li>
- <li>Providing serialization utilities for the Voronoi diagram data structure.<br>
+ <li>Expose O(N) interface to retrieve the convex hull of a set
+of
+points and segments from the Voronoi builder, once the Voronoi diagram
+is
+constructed.</li>
+ <li>Provide serialization utilities for the Voronoi diagram
+data structure.<br>
</li>
-
-
</ul>
High-priority tasks to be considered:<br>
<ul>
- <li>Dropping the restriction on the non-intersecting input
+ <li>Drop the restriction on the non-intersecting input
geometries.</li>
- <li>Integration of the Voronoi diagram data structure with the BGL (Boost
+ <li>Integrate of the Voronoi diagram data structure with the
+BGL (Boost
Graph Library).</li>
<li>Support of the other types of distance metrics.</li>
<li>Construction of the constrained Delaunay triangulation.</li>
@@ -375,9 +435,10 @@
</ul>
Based on the community suggestions priorities may be changed.<br>
<h2>Theoretical Research<br>
- </h2>Voronoi
+ </h2>
+Voronoi
was developed as part of the Google Summer of Code 2010. The
-library was actively maintained for the last two years and involved
+library was actively maintained for the last three years and involved
strong mathematical research in the field of algorithms, data
structures,
relative error arithmetic and numerical robustness. Nowadays one can
@@ -387,17 +448,25 @@
the Boost.Polygon Voronoi library. We provide pure implementation and
benchmarks one may run on
his PC. In case community finds it useful we will incrementally
-add more documentation on the theoretical side of our implementation. The
-authors would like to acknowledge the Steven Fortune's article <span style="font-family: Arial,Helvetica,sans-serif;"><span style="font-weight: bold;"></span></span>"<a href="http://dl.acm.org/citation.cfm?id=10549">A Sweepline algorithm
+add more documentation on the theoretical side of our implementation.
+The
+authors would like to acknowledge the Steven Fortune's article <span
+ style="font-family: Arial,Helvetica,sans-serif;"><span
+ style="font-weight: bold;"></span></span>"<a
+ href="http://dl.acm.org/citation.cfm?id=10549">A Sweepline algorithm
for Voronoi diagrams</a>", that contains the fundamental ideas of the
current implementation.<br>
</td>
</tr>
<tr>
- <td style="background-color: rgb(238, 238, 238);" nowrap="1" valign="top"> </td>
- <td style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;" valign="top" width="100%">
+ <td style="background-color: rgb(238, 238, 238);" nowrap="1"
+ valign="top"> </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">
+ <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-2012.</td>
@@ -405,7 +474,10 @@
<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">
+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>)</td>
</tr>
</tbody>
@@ -414,6 +486,5 @@
</tr>
</tbody>
</table>
-
-
-</body></html>
\ No newline at end of file
+</body>
+</html>