|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r78072 - in sandbox/gtl: boost/polygon doc
From: sydorchuk.andriy_at_[hidden]
Date: 2012-04-18 16:55:41
Author: asydorchuk
Date: 2012-04-18 16:55:39 EDT (Wed, 18 Apr 2012)
New Revision: 78072
URL: http://svn.boost.org/trac/boost/changeset/78072
Log:
Updating documentation.
Adding compiler directives to disable edge/vertex/cell data member.
Text files modified:
sandbox/gtl/boost/polygon/voronoi_diagram.hpp | 14 ++++++
sandbox/gtl/doc/voronoi_diagram.htm | 71 +++++++++++++++++++++--------------
sandbox/gtl/doc/voronoi_main.htm | 80 ++++++++++++++++++++-------------------
3 files changed, 96 insertions(+), 69 deletions(-)
Modified: sandbox/gtl/boost/polygon/voronoi_diagram.hpp
==============================================================================
--- sandbox/gtl/boost/polygon/voronoi_diagram.hpp (original)
+++ sandbox/gtl/boost/polygon/voronoi_diagram.hpp 2012-04-18 16:55:39 EDT (Wed, 18 Apr 2012)
@@ -70,14 +70,18 @@
const voronoi_edge_type *incident_edge() const { return incident_edge_; }
void incident_edge(voronoi_edge_type *e) { incident_edge_ = e; }
+#ifndef NO_VORONOI_CELL_DATA
void *data() const { return data_; }
void data(void *d) const { data_ = d; }
+#endif
private:
point_type point0_;
point_type point1_;
voronoi_edge_type *incident_edge_;
+#ifndef NO_VORONOI_CELL_DATA
mutable void *data_;
+#endif
};
// Represents Voronoi vertex.
@@ -105,13 +109,17 @@
const voronoi_edge_type *incident_edge() const { return incident_edge_; }
void incident_edge(voronoi_edge_type *e) { incident_edge_ = e; }
+#ifndef NO_VORONOI_VERTEX_DATA
void *data() const { return data_; }
void data(void *d) const { data_ = d; }
+#endif
private:
point_type vertex_;
voronoi_edge_type *incident_edge_;
+#ifndef NO_VORONOI_VERTEX_DATA
mutable void *data_;
+#endif
};
// Half-edge data structure. Represents Voronoi edge.
@@ -163,8 +171,10 @@
const voronoi_edge_type *prev() const { return prev_; }
void prev(voronoi_edge_type *e) { prev_ = e; }
+#ifndef NO_VORONOI_EDGE_DATA
void *data() const { return data_; }
void data(void *d) const { data_ = d; }
+#endif
// Returns a pointer to the rotation next edge
// over the starting point of the half-edge.
@@ -226,7 +236,9 @@
voronoi_edge_type *twin_;
voronoi_edge_type *next_;
voronoi_edge_type *prev_;
+#ifndef NO_VORONOI_EDGE_DATA
mutable void *data_;
+#endif
};
template <typename T>
@@ -280,7 +292,7 @@
typedef typename edge_container_type::const_iterator const_edge_iterator;
// This builder class is mainly used to hide from the user methods that
- // construct Voronoi diagram.
+ // construct the Voronoi diagram.
class voronoi_diagram_builder {
public:
void vd(voronoi_diagram *vd) {
Modified: sandbox/gtl/doc/voronoi_diagram.htm
==============================================================================
--- sandbox/gtl/doc/voronoi_diagram.htm (original)
+++ sandbox/gtl/doc/voronoi_diagram.htm 2012-04-18 16:55:39 EDT (Wed, 18 Apr 2012)
@@ -2,6 +2,7 @@
<html><head>
+
<meta http-equiv="Content-Language" content="en-us">
@@ -19,7 +20,7 @@
<tbody>
<tr>
- <td style="background-color: rgb(238, 238, 238);" valign="top" nowrap="1">
+ <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>
@@ -85,25 +86,25 @@
<td style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;" valign="top" width="100%"><!-- End Header --> <br>
<h1>Voronoi Diagram</h1>
-Voronoi
-diagram is a computational geometry concept that represents partition
-of a given space onto regions, with bounds determined by distances to a
+A Voronoi
+diagram is the computational geometry concept that represents partition
+of the given space onto regions, with bounds determined by distances to a
specified family of objects. The application area of this concept vary <a href="http://www.ics.uci.edu/%7Eeppstein/gina/scot.drysdale.html">from
-Archaeology to Zoology</a>. Boost.Polygon provides implementation of
-the Voronoi diagram data structure in 2D space. Internal representation
-consists of a three arrays, that respectively contain: Voronoi cells
-(area around input sites bounded by Voronoi edges), Voronoi vertices
+Archaeology to Zoology</a>. The Boost.Polygon library provides implementation of
+the Voronoi diagram data structure in 2D space. The internal representation
+consists of the three arrays, that respectively contain: Voronoi cells
+(represents the area around input site bounded by the Voronoi edges), Voronoi vertices
(points where three or more Voronoi edges intersect), Voronoi edges
-(one dimensional curves containing points equidistant from the two
+(the one dimensional curves containing points equidistant from the two
closest input sites). Each of the primitives (cell, vertex, edge)
contains pointers to the other linked primitives, so that it's always
-possible to efficiently traverse Voronoi graph. Picture below shows
-Voronoi vertices in red, Voronoi edges in black, input sites that
+possible to efficiently traverse Voronoi graph. The picture below shows
+the Voronoi vertices in red, Voronoi edges in black, input sites that
correspond to the Voronoi cells in blue. It is considered that each
-input segment consists of three sites: segment itself and its
+input segment consists of the three sites: segment itself and its
endpoints. As the result two additional
-Voronoi edges are constructed per each segment. This is made to
-simplify representation of the Voronoi diagram.<br>
+Voronoi edges are constructed per each input segment. This is made to
+simplify the representation of the Voronoi diagram.<br>
<br>
<img style="border: 1px solid ; width: 300px; height: 300px;" alt="" src="images/voronoi2.png"><br>
<h2>Declaration<br>
@@ -117,7 +118,7 @@
voronoi_diagram;<br>
<br>
</span><font face="Courier New"><span style="font-family: 'Courier New',Courier,monospace;">T</span></font>
-- specifies coordinate type of the output geometries: input sites (points / segments), Voronoi vertices.<br>
+- specifies the coordinate type of the output geometries: input sites (points / segments), Voronoi vertices.<br>
<span style="font-family: Courier New,Courier,monospace;">TRAITS</span><font face="Courier New"><span style="font-family: 'Courier New',Courier,monospace;"></span></font>
- Voronoi diagram traits (explained in the end of this chapter).<br>
<h2>Member Functions</h2>
@@ -299,7 +300,7 @@
<span style="font-family: Courier New,Courier,monospace;">class
voronoi_edge;<br>
<br>
-T</span> - coordinate type. While Voronoi edge doesn't contain coordinates itself, it stores pointers to Voronoi cell and vertex.<br>
+T</span> - coordinate type. While Voronoi edge doesn't contain coordinates itself, it stores pointers to the Voronoi cell and vertex.<br>
<h2>Member Functions</h2>
<span style="font-family: Courier New,Courier,monospace;">
@@ -552,8 +553,13 @@
</tbody>
</table>
<span style="font-family: Courier New,Courier,monospace;"><br>
- </span>All the above methods have O(1) complexity. The size of
-the Voronoi edge structure is equal to: 6 * sizeof(void *).<br>
+ </span>All
+the above methods have O(1) complexity. The size of
+the Voronoi edge structure is equal to: 6 * sizeof(void *). It is
+possible to disable the data member of the Voronoi edge data structure
+during the compile time using the following directive:<br>
+ <br>
+ <span style="font-family: Courier New,Courier,monospace;">#define NO_VORONOI_EDGE_DATA</span><br>
<h2>Member Types</h2>
<table style="text-align: left; width: 100%;" border="1" cellpadding="2" cellspacing="2">
@@ -584,8 +590,8 @@
</tr>
</tbody>
</table>
-
<h1>Voronoi Cell</h1>
+
Voronoi cell is represented by a site the cell contains and a pointer
to the incident edge.<br>
<h2>Declaration</h2>
@@ -709,7 +715,12 @@
<span style="font-family: Courier New,Courier,monospace;"><br>
</span>All the above methods have O(1) complexity. The size of
the Voronoi cell structure is equal to: 2 * sizeof(void *) + 4 *
-sizeof(coordinate_type).<br>
+sizeof(coordinate_type). It is possible to disable the data member of the Voronoi cell data
+structure during the compile time using the following directive:<br>
+
+ <br>
+
+ <span style="font-family: Courier New,Courier,monospace;">#define NO_VORONOI_CELL_DATA</span>
<h2>Member Types</h2>
@@ -737,7 +748,7 @@
</table>
<h2>Miscellaneous</h2>
-Following code snippet effectively traverses Voronoi edges around the
+The following code snippet effectively traverses the Voronoi edges around the
Voronoi cell:<br>
<br>
<span style="font-family: Courier New,Courier,monospace;">const
@@ -829,7 +840,12 @@
<span style="font-family: Courier New,Courier,monospace;"><br>
</span>All the above methods have O(1) complexity. The size of
the Voronoi vertex structure is equal to: 2 * sizeof(void *) + 2 *
-sizeof(coordinate_type).<br>
+sizeof(coordinate_type). It is possible to disable the data member of the Voronoi vertex data
+structure during the compile time using the following directive:<br>
+
+ <br>
+
+ <span style="font-family: Courier New,Courier,monospace;">#define NO_VORONOI_VERTEX_DATA</span>
<h2>Member Types</h2>
<table style="text-align: left; width: 100%;" border="1" cellpadding="2" cellspacing="2">
<tbody>
@@ -854,11 +870,7 @@
</tbody>
</table>
- <h2>Miscellaneous</h2>
-
-
-
-Following code snippet effectively traverses Voronoi edges around the
+ <h2>Miscellaneous</h2>The following code snippet effectively traverses the Voronoi edges around the
Voronoi vertex:<br>
<br>
<span style="font-family: Courier New,Courier,monospace;">const
@@ -869,7 +881,8 @@
<span style="font-family: Courier New,Courier,monospace;">
// Do smth. with edge.</span><br style="font-family: Courier New,Courier,monospace;">
<span style="font-family: Courier New,Courier,monospace;">} while
-(edge != vertex->incident_edge());</span><br>
+(edge != vertex->incident_edge());<br>
+</span>
<h1>Voronoi Diagram Traits<br>
</h1>
Voronoi diagram traits are used to configure Voronoi diagram data
@@ -944,7 +957,7 @@
</td>
</tr>
<tr>
- <td style="background-color: rgb(238, 238, 238);" valign="top" nowrap="1"> </td>
+ <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">
Modified: sandbox/gtl/doc/voronoi_main.htm
==============================================================================
--- sandbox/gtl/doc/voronoi_main.htm (original)
+++ sandbox/gtl/doc/voronoi_main.htm 2012-04-18 16:55:39 EDT (Wed, 18 Apr 2012)
@@ -9,6 +9,7 @@
+
<meta http-equiv="Content-Language" content="en-us">
@@ -97,35 +98,34 @@
<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 Voronoi diagram
+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>
<ul>
<li>coordinates of the input points and endpoints of the
segments
-should be of integer type;</li>
- <li>input segments should not intersect
+should be of the integer type;</li>
+ <li>input segments should not overlap
except their endpoints.</li>
</ul>
While the first restriction is permanent (it
-allows to give warranties about the output precision and
+allows to give the exact warranties about the output precision and
algorithm execution),
the second one may be resolved using the Boost.Polygon functionality.
-Strong sides of the
+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>
Lets 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 experience with
-the following situations would understand what it doesn't mean:
-the application segfaults randomly, the algorithm output contains
-degeneracies, the algorithm produces wrong output (e.g. point is considered to be outside of the polygon,
+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 the weak place of the most non-commercial
+it. Robustness is a weak place of the most non-commercial
implementations of any complex geometric algorithm. The main issues of
that could be divided onto two main categories: memory management
issues, numeric stability issues. Our implementation avoids the
@@ -156,7 +156,7 @@
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 the output coordinates with more precise bits. Lets consider
+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
@@ -176,21 +176,21 @@
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 lets see what is the practical
-impact of this. Consider following example: we are going to construct
-Voronoi diagram of our Solar System. The radius of our solar system is
+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]. Lets choose the long double
+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. Come on that distance is equal to
+micrometres) distance to be equal. Come on, that distance is equal to
the size of a bacteria. Can you even see those?<br>
- <h2>Fully Functional with Segment Inputs</h2>
+ <h2>Fully Functional with Segments</h2>
There are not many implementations of the Voronoi diagram construction
algorithm that could
-handle segment inputs, even considering the commercial libraries.
+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
@@ -202,7 +202,7 @@
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 Voronoi library functionality with the Boost.Polygon interfaces:<br>
+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">
<tbody>
@@ -211,7 +211,7 @@
void insert(const Point &point, VB &vb)<br>
</td>
<td style="vertical-align: top;">Inserts a point into the Voronoi builder data structure.<br>
-Point type should model point concept.<br>
+Point type should model the point concept.<br>
</td>
</tr>
<tr>
@@ -219,7 +219,7 @@
void insert(PointIterator first, const PointIterator last, VB &vb)<br>
</td>
<td style="vertical-align: top;">Inserts an iterator range of points into the Voronoi builder data structure.<br>
-Corresponding point type should model point concept.<br>
+Corresponding point type should model the point concept.<br>
</td>
</tr>
<tr>
@@ -227,7 +227,7 @@
void insert(const Segment &segment, VB &vb)<br>
</td>
<td style="vertical-align: top;">Inserts a segment into the Voronoi builder data structure.<br>
-Segment type should model segment concept.<br>
+Segment type should model the segment concept.<br>
</td>
</tr>
<tr>
@@ -235,21 +235,21 @@
void insert(SegmentIterator first, SegmentIterator last, VB &vb)<br>
</td>
<td style="vertical-align: top;">Inserts an iterator range of segments into the Voronoi builder data structure.<br>
-Corresponding segment type should model segment concept.<br>
+Corresponding segment type should model the segment concept.<br>
</td>
</tr>
<tr>
<td style="vertical-align: top; font-family: Courier New,Courier,monospace;">template <typename PointIterator, typename VD><br>
void construct_voronoi(PointIterator first, PointIterator last, VD *output)<br>
</td>
- <td style="vertical-align: top;">Constructs Voronoi diagram of a set of points.<br>Corresponding point type should model point concept.<br>
+ <td style="vertical-align: top;">Constructs Voronoi diagram of a set of points.<br>Corresponding point type should model the point concept.<br>
</td>
</tr>
<tr>
<td style="vertical-align: top; font-family: Courier New,Courier,monospace;">template <typename SegmentIterator, typename VD><br>
void construct_voronoi(SegmentIterator first, SegmentIterator last, VD *output)<br>
</td>
- <td style="vertical-align: top;">Constructs Voronoi diagram of a set of segments.<br>Corresponding segment type should model segment concept.<br>
+ <td style="vertical-align: top;">Constructs Voronoi diagram of a set of segments.<br>Corresponding segment type should model the segment concept.<br>
</td>
</tr>
<tr>
@@ -260,14 +260,14 @@
VD *output)<br>
</td>
<td style="vertical-align: top;">Constructs Voronoi
-diagram of a set of points and segments.<br>Corresponding point type should model point concept.<br>
-Corresponding segment type should model segment 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 Voronoi diagram with the
+means that it's possible to construct the Voronoi diagram with the
following two lines of code (if corresponding input types satisfy Boost.Polygon concept model):<br>
<br>
<span style="font-family: Courier New,Courier,monospace;">voronoi_diagram<double>
@@ -282,7 +282,7 @@
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, that doesn't depend on any external code.<br>
+Delaunay triangulation construction routines based on the Voronoi builder API.<br>
<h2>No Third Party Dependencies<br>
</h2>Yes,
the library doesn't depend on any 3rd party code. Even more than that
@@ -295,8 +295,8 @@
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 provides types that satisfy set of restrictions of the Voronoi builder coordinate type traits
-and implements the library required methods no changes are required
+as user provides 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
from the algorithm, nor from the implementation of the predicates. So it's
possible to
@@ -325,29 +325,31 @@
<li>Voronoi
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 k nearest neighbors for each site.<br>
+list of the k nearest neighbors for each site.<br>
</li>
<li>Using the r-tree data structure built on top of the
-bounding rectangles around N Voronoi cells to answer the nearest
-neighbor queries in log(N) time.<br>
+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>
Note: there should be r-tree data structure available soon as part of
the Boost libraries.</li>
- <li>Providing interface to retrieve convex hull of a set of
+ <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.<br>
+constructed in O(N) time.</li>
+ <li>Providing 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
geometries.</li>
- <li>Integration of the Voronoi diagram structure with the BGL (Boost
+ <li>Integration 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>
- <li>Support of the circle input geometries.</li>
+ <li>Support of the circular input geometries.</li>
</ul>
Based on the community suggestions priorities may be changed.<br>
<h2>Theoretical Research<br>
@@ -364,7 +366,7 @@
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 realization. The
-authors would like to acknowledge 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
+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>
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