|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r77897 - sandbox/gtl/doc
From: sydorchuk.andriy_at_[hidden]
Date: 2012-04-10 16:18:11
Author: asydorchuk
Date: 2012-04-10 16:18:10 EDT (Tue, 10 Apr 2012)
New Revision: 77897
URL: http://svn.boost.org/trac/boost/changeset/77897
Log:
Updating documentation.
Text files modified:
sandbox/gtl/doc/index.htm | 15 ++--
sandbox/gtl/doc/voronoi_main.htm | 109 ++++++++++++++++++++-------------------
2 files changed, 64 insertions(+), 60 deletions(-)
Modified: sandbox/gtl/doc/index.htm
==============================================================================
--- sandbox/gtl/doc/index.htm (original)
+++ sandbox/gtl/doc/index.htm 2012-04-10 16:18:10 EDT (Tue, 10 Apr 2012)
@@ -1,5 +1,6 @@
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
-<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en"><head><!--
+<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en"><head>
+<!--
Copyright 2009-2010 Intel Corporation
license banner
--><title>Boost Polygon Library: Main Page</title>
@@ -102,16 +103,16 @@
geometry in its scope, and provides a set of capabilities for working with
coordinates, points, intervals and rectangles that are needed to support
implementing and interacting with polygon data structures and algorithms. </p><img src="images/hand.png" border="0" height="277" width="837" /><p>
-One of important features of the library is the implementation of
-generic sweepline algorithm to construct Voronoi diagrams of points and linear segments in 2D (developed
-as part of GSoC 2010 program). Voronoi diagram data structure has
+One of the important features of the library is the implementation of
+the generic sweepline algorithm to construct Voronoi diagrams of points and linear segments in 2D (developed
+as part of the GSoC 2010 program). Voronoi diagram data structure has
applications in image segmentation, optical character recognition,
-nearest neighbor queries execution. It is closely related with other
+nearest neighbor queries execution. It is closely related with the other
computational geometry concepts: Delaunay triangulation, medial axis,
straight skeleton, the largest empty circle. The Boost.Polygon library
-provides interface to construct Voronoi diagrams of points figure a and
+provides interface to construct Voronoi diagram of points figure a and
line segments figure b (the last could be used to discretize any
-two-dimensional curve). Figure c contains example of the medial axis of the
+two-dimensional curve). Figure c contains the example of the medial axis of the
non-convex polygon. The implementation outperforms most of the known
commercial and non-commercial libraries in both efficiency and
numerical robustness aspects. You may find more details on the topic at the Voronoi main page.<br />
Modified: sandbox/gtl/doc/voronoi_main.htm
==============================================================================
--- sandbox/gtl/doc/voronoi_main.htm (original)
+++ sandbox/gtl/doc/voronoi_main.htm 2012-04-10 16:18:10 EDT (Tue, 10 Apr 2012)
@@ -1,11 +1,12 @@
<!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=windows-1252"><title>Voronoi Main</title>
+
@@ -15,9 +16,7 @@
<meta http-equiv="content-type" content="text/html; charset=utf-8">
- <meta http-equiv="content-type" content="text/html; charset=utf-8">
-
-</head><body>
+ <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>
@@ -90,7 +89,7 @@
<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 diagrams
+The Boost.Polygon Voronoi library provides functionality to construct Voronoi diagram
of a set of points and linear segments in 2D space with the following
set of
limitations:<br>
@@ -102,20 +101,19 @@
except their endpoints.</li>
</ul>
While the first restriction is permanent (it
-allows to give warranties for algorithm output precision and
-execution),
-the second one may be resolved using Boost.Polygon functionality.
+allows to give warranties about the output precision and
+algorithm execution),
+the second one may be resolved using the Boost.Polygon functionality.
Strong sides of the
-library and main benefits comparing to other implementations are
+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:
-application segfaults randomly, the algorithm output contains
-degeneracies for some inputs, the algorithm produces wrong output for
-some inputs (e.g. point is considered to be outside of the polygon,
+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,
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
@@ -123,17 +121,17 @@
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
-first type of issues using pure STL data structure, thus you won't find
+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
resolved using multiprecision <a href="voronoi_predicates.htm">geometric
predicates</a>.
Even for commercial implementations usage of such predicates usually
-results in huge performance slowdown. Here is another strong side of
+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 <a href="voronoi_robust_fpt.htm">relative
+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>
<h2>Precision of the Output Structures<br>
@@ -143,11 +141,11 @@
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 IEEE-754 floating-point type).<br>
+coordinate type is the IEEE-754 floating-point type).<br>
<br>
Voronoi implementation guaranties that the relative error of the
coordinates of the output
-geometries is always not higher then 64 machine epsilons (6
+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
@@ -164,23 +162,23 @@
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 absolute and relative errors try this article.<br>
+master of the absolute and relative error try this article.<br>
<br>
-During finalization step library unites Voronoi vertices whose both
-coordinates are situated within relative error range equal to 128
+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 algorithm output
-topology and the precise one. Now lets see what is the practical
+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
-approximately 2^42 meters, and we are going to snap it to the integer
-grid of [-2^42; 2^42] x [-2^42; 2^42]. Lets choose long double
-(64 bit mantissa) output coordinate type, then maximum absolute error
-for output geometries within our solar system will be on its boundary
-and equal to 2^-64 * 2^42 * 2^6 = 2^-18. In the output we are going to
-consider vertices with both coordinates that are within 2^-17 meters (8
-micrometers) distance to be equal. Come on that distance is equal to
-the size of bacteria. Can you even see those?<br>
+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
+(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
+the size of a bacteria. Can you even see those?<br>
<h2>Fully Functional with Segment Inputs</h2>
There are not many implementations of the Voronoi diagram construction
algorithm that could
@@ -206,7 +204,7 @@
static inline void construct_voronoi_points(<br>
const PC &points, VD *output)<br>
</td>
- <td style="vertical-align: top;">Constructs the Voronoi
+ <td style="vertical-align: top;">Constructs Voronoi
diagram of a set of points into the output data structure.<br>
Coordinates of the input geometries should belong to the [-2^31,
2^31-1] integer range.<br>
@@ -219,7 +217,7 @@
static inline void construct_voronoi_segments(<br>
const SC &segments, VD *output)<br>
</td>
- <td style="vertical-align: top;">Constructs the Voronoi
+ <td style="vertical-align: top;">Constructs Voronoi
diagram of a set of segments into the output data structure.<br>
Coordinates of the input geometries should belong to the [-2^31,
2^31-1] integer range.<br>
@@ -235,7 +233,7 @@
const PC &points, const SC &segments, VD
*output)<br>
</td>
- <td style="vertical-align: top;">Constructs the Voronoi
+ <td style="vertical-align: top;">Constructs Voronoi
diagram of a set of points and segments into the output data structure.<br>
Coordinates of the input geometries should belong to the [-2^31,
2^31-1] integer range.<br>
@@ -255,27 +253,26 @@
segments, &vd);</span><br>
<br>
Isn't that simple? The library also provides the clear interfaces to
-associate user data with the output geometries, efficiently traverse Voronoi graph and utilities to
+ associate user data with the output geometries, efficiently traverse Voronoi graph and utilities to
<a href="voronoi_utils.htm">visualize output primitives</a> (e.g.
discretization of the parabolic edges, clipping of the linear edges).
-More details on those is covered in the basic Voronoi tutorial.
-Advanced usage of the library with the configuration of the coordinate
+More details on those are covered in the basic Voronoi tutorial. 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>.<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 Boost library: boost/cstdint.hpp.
+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 8 headers (4 public
and 4 private) it is easy to compile it within a minute after download.<br>
- <h2>Extensible for User Provided Coordinate Types</h2>
+ <h2>Extensible for the User Provided Coordinate Types</h2>
Our implementation is coordinate type agnostic. That means that as soon
-as the user provided types satisfy set of restrictions of the Voronoi builder coordinate type traits
-and implement the library required methods no changes are required
+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
neither
-from algorithm, nor from the implementation of the predicates. So it's
+from the algorithm, nor from the implementation of the predicates. So it's
possible to
construct Voronoi diagram for the 256-bit integer input coordinate type
and
@@ -299,23 +296,30 @@
The main point
of this data structure is to automatically filter Voronoi edges that
belong to those areas.</li>
- <li>Implementing data structure built on top of Voronoi diagram
-that allows to execute nearest neighbor queries in O(log N) time.<br>
+ <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>
+</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>
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
-points and segments from Voronoi builder once the Voronoi diagram is
+points and segments from the Voronoi builder once the Voronoi diagram is
constructed in O(N) time.<br>
</li>
<li>Closer integration with the interfaces and functionality of
-Boost Polygon Library.<br>
+the Boost Polygon Library.<br>
</li>
</ul>
High-priority tasks to be considered:<br>
<ul>
- <li>Dropping restriction on the non-intersecting input
+ <li>Dropping the restriction on the non-intersecting input
geometries.</li>
- <li>Integration of Voronoi diagram structure with BGL (Boost
+ <li>Integration of the Voronoi diagram 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>
@@ -323,17 +327,16 @@
</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
-the strong mathematical research in the field of algorithms, data
+strong mathematical research in the field of algorithms, data
structures,
relative error arithmetic and numerical robustness. Nowadays one can
-often read scientific article that contains non-practical theoretical
+often read a scientific article that contains non-practical theoretical
results or implementation with
benchmarks nobody else can reproduce. The opposite story is with
-the Boolst.Polygon Voronoi library. We provide pure implementation and
+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 realization. The
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