Boost-Commit :

Date view	Thread view	Subject view	Author view

Subject: [Boost-commit] svn:boost r77856 - in sandbox/gtl: doc libs/polygon/example
From: sydorchuk.andriy_at_[hidden]
Date: 2012-04-09 14:47:21

Next message: vicente.botet_at_[hidden]: "[Boost-commit] svn:boost r77857 - trunk/libs/thread/test"
Previous message: antoshkka_at_[hidden]: "[Boost-commit] svn:boost r77855 - trunk/status"

Author: asydorchuk
Date: 2012-04-09 14:47:19 EDT (Mon, 09 Apr 2012)
New Revision: 77856
URL: http://svn.boost.org/trac/boost/changeset/77856

Log:
Finalizing Voronoi documentation.

Text files modified:
   sandbox/gtl/doc/index.htm | 21 ++--
   sandbox/gtl/doc/voronoi_advanced_tutorial.htm | 108 ++++++++++++------------
   sandbox/gtl/doc/voronoi_basic_tutorial.htm | 79 ++++++++---------
   sandbox/gtl/doc/voronoi_benchmark.htm | 32 +++----
   sandbox/gtl/doc/voronoi_builder.htm | 96 +++++++++++----------
   sandbox/gtl/doc/voronoi_diagram.htm | 171 +++++++++++++++++++--------------------
   sandbox/gtl/doc/voronoi_main.htm | 124 +++++++++++++++-------------
   sandbox/gtl/doc/voronoi_predicates.htm | 66 ++++++++++-----
   sandbox/gtl/doc/voronoi_robust_fpt.htm | 73 +++++++---------
   sandbox/gtl/doc/voronoi_utils.htm | 54 ++++++------
   sandbox/gtl/libs/polygon/example/voronoi_basic_tutorial.cpp | 2
   11 files changed, 422 insertions(+), 404 deletions(-)

Modified: sandbox/gtl/doc/index.htm
==============================================================================
--- sandbox/gtl/doc/index.htm (original)
+++ sandbox/gtl/doc/index.htm 2012-04-09 14:47:19 EDT (Mon, 09 Apr 2012)
@@ -1,6 +1,5 @@
<!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>
-<title>Boost Polygon Library: Main Page</title>
@@ -15,6 +14,8 @@

+
+
 <meta http-equiv="content-type" content="text/html;charset=ISO-8859-1" /></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">
@@ -101,19 +102,19 @@
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.  <img src="images/hand.png" border="0" height="277" width="837" />
-One of important features of the library is implementation of
-generic sweepline algorithm to build Voronoi diagrams in 2D (developed
+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
applications in image segmentation, optical character recognition,
nearest neighbor queries execution. It is closely related with other
computational geometry concepts: Delaunay triangulation, medial axis,
-straight skeleton, largest empty circle. Boost.Polygon library
+straight skeleton, the largest empty circle. The Boost.Polygon library
provides interface to construct Voronoi diagrams 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 medial axis of a
+two-dimensional curve). Figure c contains 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 Voronoi main page. 
+numerical robustness aspects. You may find more details on the topic at the Voronoi main page. 


<img src="images/voronoi.png" border="0" height="300" width="900" />
@@ -238,10 +239,10 @@
 <li>Minkowski Sum Learn how to
 apply Boost.Polygon capabilities to implement Minkowski sum of polygon sets</li>
 <li>Voronoi Basic Tutorial Learn how
- to construct, traverse, visualize, associate data with Voronoi diagrams without digging into library details.</li>
+ to construct, traverse, visualize, associate data with Voronoi diagrams without digging into the library details.</li>
 <li>Voronoi Advanced Tutorial
- Learn how to configure Voronoi builder and Voronoi diagram
- data structure with user provided coordinate types. </li>
+ Learn how to configure the Voronoi builder and Voronoi diagram
+ data structure with the user provided coordinate types. </li>
</ul>

</li></ul>

Modified: sandbox/gtl/doc/voronoi_advanced_tutorial.htm
==============================================================================
--- sandbox/gtl/doc/voronoi_advanced_tutorial.htm (original)
+++ sandbox/gtl/doc/voronoi_advanced_tutorial.htm 2012-04-09 14:47:19 EDT (Mon, 09 Apr 2012)
@@ -12,6 +12,7 @@

+
<meta http-equiv="Content-Type" content="text/html; charset=windows-1252"><title>Polygon Usage</title></head><body>

<h1>Voronoi Advanced Tutorial 
@@ -59,17 +60,17 @@
<h3>Discretization of input geometries</h3>

-To show how good is default input coordinate type provided by Voronoi
-we would discretize the whole area of Mars. That would be approximately
+To show how good is the default input coordinate type provided by the Voronoi library
+we will discretize the whole area of Mars. That will be approximately
1.44 *  10^8  square kilometres that is equal to 1.44 * 
10^18  square centimetres, which could be snapped to the integer
-grid with a side of 1.2 * 10^9 centimetres.  To make Voronoi graph
+grid with a side of 1.2 * 10^9 centimetres.  To make the Voronoi graph
precise on the boundaries of that grid we will replicate input map 9
-times (3x3), thus Voronoi diagram within a central  piece will
+times (3x3), thus Voronoi diagram within a central piece will
provide us with a correct connectivity graph. This step will increase
the size of our grid to 3.6 * 10^9 centimetres that is less than 2^32.
-So we are able to discretize Red planet surface within a 1 centimetre
-precision using default input coordinate type (signed 32 bit integer). That would imply maximum absolute error to be
+So we are able to discretize the Red Planet's surface within a 1 centimetre
+precision using the default input coordinate type (signed 32-bit integer). That would imply maximum absolute error to be
equal up to 0.5 centimetres per coordinate. Considering the radius of our robot to be
0.3 metres and for security reasons avoiding any large enough obstacles
that are within 1 metre distance from it that error would be irrelevant. 
@@ -81,14 +82,14 @@
<h3>Output analysis</h3>

-Estimates of the resulting Voronoi diagram precision were already discussed here.
+Estimates of the resulting Voronoi diagram precision were already explained here.
So to avoid those computations again we will simply state that the
maximum absolute error of the output geometries will be on the grid
boundaries and will be equal to 2^-16 centimetres, which is
approximately equal to 150 nanometres and is 100 times larger than
-radius of a complex molecule.
+a radius of a complex molecule.

-We would like to notice that the absolute error of a discretization step is much higher than the one
+We would like to notice that the absolute error of the discretization step is much higher than the one
produced by the Voronoi diagram construction algorithm. <h2>VLSI Design</h2>

@@ -104,24 +105,24 @@
integrated circuit manufactured, designers often spend large amounts of
time analyzing their layouts to avoid costly mistakes. One of the
common static analysis checks is minimum distance requirement between
-the components of integrated circuit (distance should be not less than
+the components of an integrated circuit (distance should be not less than
specified value). 

<h3>Application of Voronoi diagram</h3>

-It appears that the minimal distance between components of the input
-set of points and segments corresponds to one of the Voronoi
+It appears that the minimum distance between components of the input
+set of points and segments corresponds to the one of the Voronoi
diagram edges. This means that we can iterate through each edge of
-Voronoi graph, extract pair of input geometries that form it and find
-distance between those. As the total amount of such edges is O(N) value
-(N - is the number of input geometries) minimal distance could be
-efficiently find in linear time once we construct the diagram. 
+the Voronoi graph, extract the pair of input geometries that form it and find
+the distance between those. As the total amount of such edges is O(N) value
+(N - is the number of input geometries) the minimum distance could be
+efficiently find in a linear time once we construct the diagram. 

<h3>Discretization of input geometries</h3>

The average size of the modern CPUs is around 2.5 x 2.5 centimetres.
-Snapping this to the 32 bit integer grid will give discretization
+Snapping this to the 32-bit integer grid will give discretization
precision of 2.5 / 2^33 centimetres or 3 picometres that is 10 times
smaller value than radius of an atom. That would be probably good
enough precision even for a few next generations of processors. 
@@ -130,8 +131,8 @@

The maximum absolute error of the output geometries will be 2.5 / 2^47
centimetres or 0.2 femtometres that is 10 times smaller value than
-radius of an electron. However in this particular case we are not
-interested in the precision, rather in topology. As it was noticed on
+the radius of an electron. However in this particular case we are not
+interested in the precision of the output, rather in its topology. As it was noticed on
the Voronoi main page very small edges
are removed from the Voronoi diagram. However user should not worry
because the edge that correspond to the minimal distance won't be among
@@ -144,45 +145,43 @@

-<h2>Conclusions</h2>
-Above two examples show usage of the default Voronoi coordinate types
+<h2>Conclusions</h2>The above two examples show usage of the default Voronoi coordinate types
in the macro and micro world. The main point of those was to give user
-understanding of a scale default coordinate types provide. There are
+understanding of a scale the default coordinate types provides. There are
two main points we didn't mention before, but that would be relevant to
the most real world problems: 
<ul>
- <li>The absolute error of coordinates of output Voronoi diagram
+ <li>The absolute error of the coordinates of the output Voronoi diagram
inside the 32-bit integer discretization grid is slightly smaller than
-absolute error of discretization itself, thus could be neglected at all.</li>
+the absolute error of discretization itself, thus could be neglected at all.</li>
<li>In both problems above we didn't consider error of measurement.
-For example: is it possible to construct map of the Mars within 0.5
+For example: is it possible to construct a map of the Mars within the 0.5
centimetres precision, or to get coordinates of the circuit parts
-withing subatomic precision. I guess the answer for both questions
-would be "No". And that actually means that error of discretization
-step could be neglected comparing to the error produced by measuring
+withing the subatomic precision? I guess the answer for both questions
+would be "No". And that actually means that the error of the discretization
+step could be neglected comparing to the error produced by the measuring
devices. 
</li>
</ul>
The second statement means that there is actually no point to provide
implementation that operates with floating-point input coordinates,
because those always could be snapped to the integer grid. In case you
-are not satisfied with the precision that the 32 bit integer grid
-provides or would like to receive output geometries within smaller
-relative error, follow next paragraph. 
+are not satisfied with the precision that the 32-bit integer grid
+provides or would like to retrieve coordinates of the output geometries within a smaller
+relative error, follow the next paragraph. 

-<h2>Voronoi Coordinate Types Configuration</h2>In the following
-tutorial we are going to extend input coordinate type to 48 bit signed
-integer and output coordinate type to 80 bit IEEE floating-point type
-(long double). The code for this chapter is available in voroni_advanced_tutorial.cpp.
-While it won't be possible to compile it using MSVC (MSVC doesn't
-support 80 bit long double type; ieee754.h header is required), it
-should give clear understanding of how the library supports user
+<h2>Voronoi Coordinate Types Configuration</h2>In the following chapter we are going to extend input coordinate type to the 48-bit signed
+integer and output coordinate type to the 80-bit IEEE floating-point type
+(long double). The code for this chapter is available in voroni_advanced_tutorial.cpp.
+While it won't be possible to compile it using the MSVC compiler (it doesn't
+support 80-bit long double type; ieee754.h header is required), it
+should give a clear understanding of how the library supports the user
provided coordinate types. 
 
-So the main step would be to declare voronoi coordinate type traits that satisfy set of restrictions explained here: 
+So the main step would be to declare the voronoi coordinate type traits that satisfy set of restrictions explained here: 
 
struct my_voronoi_ctype_traits { 
  typedef boost::int64_t int_type; 
@@ -197,18 +196,18 @@
}; 
 
It is always better to use C++ built-in types wherever it's
-possible. That's why we use 64 bit signed integer type to handle our
+possible. That's why we use the 64-bit signed integer type to handle our
input coordinates. int_x2_type and uint_x2_type
-is required to handle 96 bit signed/unsigned integers. As there is no
+is required to handle 96-bit signed/unsigned integers. As there is no
such built-in type we use library provided efficient fixed integer type.
-Big int type should be capable to handle 48 * 64 bit integers, that is
+The big integer type should be capable to handle 48 * 64 bit integers, that is
less than 32 * 128, and so far we are good with extended_int<128> type. We use the same floating point type for both fpt_type and efpt_type
as it has enough exponent bits to represent both 48 * 32 bit and 48 *
64 bit integers (that is also the reason we don't need two
floating-point converter structures). The ulp_cmp_type
-structure checks weather two IEEE floating-point values are within
+structure checks weather two IEEE floating-point values are within the
given signed integer ulp range (we won't analyze corresponding code
-here as it requires deep understanding of floating-point architecture and its usage to compare floating-point values), but to notice declaration is following: 
+here as it requires deep understanding of the floating-point architecture and its usage to compare floating-point values), but just to mention the declaration is following: 
 
struct my_ulp_comparison { 
  enum Result { 
@@ -219,7 +218,7 @@
  Result operator()(fpt80 a, fpt80 b, unsigned int maxUlps) const; 
}; 
 
-The last step would be to declare my_fpt_converter structure (converts integer types to floating-point type): 
+The last step would be to declare the my_fpt_converter structure (converts the integer types to the floating-point type): 
 
struct my_fpt_converter { 
  template <typename T> 
@@ -240,7 +239,7 @@
}; 
 
At this point we are done with declaration of the Voronoi
-coordinate type traits. The next step is to declare Voronoi diagram
+coordinate type traits. The next step is to declare the Voronoi diagram
traits: 
 
struct my_voronoi_diagram_traits { 
@@ -268,10 +267,9 @@
  } vertex_equality_predicate_type; 
}; 

- 
-We simply declared Voronoi primitive types, type converter and vertex
-equality predicate using new coordinate type and corresponding ulp
-comparison structure. As we are done with declaration of coordinate
+ Above we simply declared the Voronoi primitive types, type converter and vertex
+equality predicate using the new coordinate type and corresponding ulp
+comparison structure. As we are done with the declaration of the coordinate
type specific structures we are ready to proceed to the construction
step itself. The first step would be to initialize voronoi_builder
structure with a set of random points: 
@@ -288,19 +286,19 @@
  vb.insert_point(x, y); 
} 
 
-The second step would be to generate Voronoi diagram and this is done with two lines of code: 
+The second step would be to generate the Voronoi diagram and this is done as before with the two lines of code: 
 
// Declaring and configuring Voronoi diagram structure with the new coordinate type traits. 
voronoi_diagram<fpt80, my_voronoi_diagram_traits> vd; 
vb.construct(&vd); 
 
-From this point user can operate with Voronoi diagram structure
+From this point the user can operate with the Voronoi diagram data structure
and in our tutorial we output some simple stats of the resulting
Voronoi graph. Probably the hardest part of this tutorial is
-declaration of the ulp comparison structure. The library provides
-efficient well-commented cross-platform implementation for 64 bit
+the declaration of the ulp comparison structure. The library provides
+efficient well-commented cross-platform implementation for 64-bit
floating-point type (double). So the best advice would be to follow
-that implementation, but before doing that really consider if default
+that implementation, but before doing that really consider if  the default
coordinate types are not capable to solve your problem. 
 
<table class="docinfo" id="table1" frame="void" rules="none">

Modified: sandbox/gtl/doc/voronoi_basic_tutorial.htm
==============================================================================
--- sandbox/gtl/doc/voronoi_basic_tutorial.htm (original)
+++ sandbox/gtl/doc/voronoi_basic_tutorial.htm 2012-04-09 14:47:19 EDT (Mon, 09 Apr 2012)
@@ -8,36 +8,36 @@

+
<meta http-equiv="Content-Type" content="text/html; charset=windows-1252"><title>Polygon Usage</title></head><body>

<h1>Voronoi Basic Tutorial 
</h1>
-In this tutorial we will cover basic usage of the Boost.Polygon
-Voronoi library. In most cases this should cover all you need from the
-library. Below we will discuss following topics: 
+In this tutorial we will cover the basic usage of the Boost.Polygon
+Voronoi library that should be enough for 95% of cases. Below we will discuss the following topics: 

<ul>
 <li>preparing input geometries; 
 </li>
 <li>construction of the Voronoi diagram;</li>
- <li>traversing Voronoi graph; 
+ <li>Voronoi graph traversal; 
 </li>
- <li>associating user data with Voronoi primitives;</li>
- <li>rendering Voronoi diagram.</li>
-</ul>In the example that goes through this tutorial (voronoi_basic_tutorial.cpp)
+ <li>associating the user data with the Voronoi primitives;</li>
+ <li>Voronoi diagram discretization and rendering.</li>
+</ul>In the example that goes through this tutorial (voronoi_basic_tutorial.cpp)
we
-are going to construct Voronoi diagram of a few points and segments.
-On the image below one may see rendered diagram. Primary Voronoi edges
+are going to construct the Voronoi diagram of a few points and segments.
+On the image below one may see the corresponding rendered Voronoi graph. Primary Voronoi edges
are marked with
-black, non-primary with green, input geometries have blue color. In
-case you forgot we split each input segment onto three sites (segment
+the black color, non-primary with green, input geometries have blue color. In
+case you forgot, we split each input segment onto three sites (segment
itself and both endpoints), edges that go between those sites are
considered to be non-primary. 
 
<img style="border: 2px solid ; width: 300px; height: 300px;" alt="" src="images/voronoi4.png"> 
 

-And before you start don't forget to: 
+And before you proceed don't forget to: 
 
#include "boost/polygon/voronoi.hpp" 
using boost::polygon; 
@@ -56,7 +56,7 @@
  int y() const { return y_; } 
 
private: 
-  // Don't forget should be cast to the signed int32 type! 
+  // Should be castable to the signed int32 type! 
  int x_; 
  int y_; 
}; 
@@ -75,7 +75,7 @@
  Point p1_; 
}; 
 
-Once declared we can create sample input: 
+Once those are declared we can create the sample input: 
 
std::vector<Point> points; 
points.push_back(Point(0, 0)); 
@@ -90,18 +90,17 @@

-Now let's construct Voronoi diagram of the input set of points and segments: 
+Now let's construct the Voronoi diagram of the input set of points and segments: 
 
voronoi_diagram<double> vd; 
construct_voronoi(points, segments, &vd); 
 
So brief, isn't that awesome! 
-<h2>Traversing Voronoi Graph</h2>
-
-At the next step we are going to traverse Voronoi graph and count the
-number of visited edges. There are three ways to do that and we are going to cover all of them: 
+<h2>Traversing Voronoi Graph</h2>Voronoi graph traversal is the basic
+operation one would like to do once the Voronoi diagram is constructed.
+There are three ways to do that and we are going to cover all of them: 
<ul>
- <li>simply iterating over Voronoi edges (counts each edge twice): 
+ <li>simply iterating over the Voronoi edges (counts each edge twice): 
 int iterate_primary_edges1(const voronoi_diagram<double> &vd) { 
  int result = 0; 
  for (voronoi_diagram<double>::const_edge_iterator it = vd.edges().begin(); 
@@ -113,7 +112,7 @@
} 
   
 </li>
- <li>iterating over Voronoi cell and then traversing edges around that cell (counts each edge twice): 
+ <li>iterating over the Voronoi cells and then traversing edges around each cell (counts each edge twice): 
 
 int iterate_primary_edges2(const voronoi_diagram<double> &vd) { 
  int result = 0; 
@@ -133,8 +132,8 @@
 
 </li>

- <li>iterating over Voronoi
-vertices and then traversing edges around that vertex (number of
+ <li>iterating over the Voronoi
+vertices and then traversing edges around each vertex (number of
iterations through each edge is equal to the number of finite endpoints
of the edge): 
 int iterate_primary_edges3(const voronoi_diagram<double> &vd) { 
@@ -166,8 +165,8 @@
 <li>associating color with each edge;</li>
 <li>using DFS or BFS on the Voronoi graph requires to mark visited edges/vertices/cells.</li>
</ul>
-We will consider first example and will try to associate total number of incident edges with each cell. 
-Note: Each Voronoi primitive contains mutable pointer to void* type, that enables to associate any type of data with it. 
+We will consider the first example and will associate the total number of incident edges with each cell. 
+Note: Each Voronoi primitive contains mutable pointer to void* type, that allows to associate any type of data with it. 
 
std::vector<int> counts; 
// This is required as reallocation of underlying vector will invalidate all the pointers. 
@@ -185,9 +184,9 @@
  cell.data(&counts.back()); 
} 
 
-Note: In the example above we could not simply use count variable
+Note: In the example above we could not use count variable
without a vector, because pointer to it will become invalid as soon as
-we leave the scope of enclosing for-loop. 
+we leave the scope of the enclosing for-loop. 
<h2>Rendering Voronoi Diagram</h2>

There are two main issues that don't allow to strictly render resulting
@@ -199,9 +198,10 @@
</ul>Note: This would be the issues not only for rendering tools.
Basically every task that requires diagram to be represented as a set
of finite segments will fall into this category. 
-All this functionality is already implemented in the Voronoi utils.
-Before clipping edges we should define clipping rectangle. It is
-usually handy to choose it so that it wraps all the input geometries
+ All the above functionality is already implemented in the Voronoi
+utils.
+Before clipping an edge we are going to define the clipping rectangle.
+It is practical to choose it so that it wraps all the input geometries
plus some offset. 
 
bounding_rectangle<double> bbox; 
@@ -213,12 +213,11 @@
} 
// Add 10% offset to the bounding rectangle. 
bbox = voronoi_utils<double>::scale(bbox, 1.1); 
- 
-Lets consider that we have 3rd party library function that draws segments using following prototype: 
+ Now lets consider that we have the 3rd party library function that draws segments using the following prototype: 
 
void draw_segment(double x1, double y1, double x2, double y2); 
 
-Then function that renders our diagram edges will have following implementation: 
+Then the function that renders our diagram edges will have the following implementation: 
 
void render_diagram(const voronoi_diagram<double> &vd, 
                   
@@ -236,8 +235,7 @@
    else 
      // Parabolic edges are always finite. 
      voronoi_utils<double>::discretize(*it, 1E-1, polyline); 
-    // Note: discretized edges may also lie outside of the bbox. 
-    // So user might do additional clipping before rendering each such edge.  
+    // Note: discretized edge segments may also lie outside of the bbox. 
    for (int i = 1; i < polyline.size(); ++i) 
      draw_segment(polyline[i-1].x(), polyline[i-1].y(), 
                  
@@ -245,20 +243,19 @@
  } 
} 
 
-voronoi_visualizer.cpp
+voronoi_visualizer.cpp
contains a simple fully featured implementation of the Voronoi diagram
renderer using Qt libraries. It was used to generate all the .png
-drawings under voronoi_example directory. 
+drawings under ./libs/polygon/example directory. 

 
-I hope the reader managed to get to this point and found the
-Basic tutorial to be useful (in the end it's not so basic). Worth
+I hope the reader managed to get to this point and found the basic tutorial to be useful (in the end it's not so basic). Worth
to notice that construction of the Voronoi diagram takes only two lines
of code, everything else is about initializing input data structures,
traversing Voronoi graph, associating data with diagram primitives and
using Voronoi utilities. In
-default mode Voronoi diagram operates with signed int (32 bit) input
-coordinate type and double (64 bit) output coordinate type. In Voronoi Advanced Tutorial we explain why this is enough in 95% of problems and how to configure algorithm coordinate types for the other 5%. 
+default mode Voronoi diagram operates with signed int (32-bit) input
+coordinate type and double (64-bit) output coordinate type. In Voronoi Advanced Tutorial we explain why this is enough for 95% of problems and how to expand the algorithm coordinate types for the other 5% of cases. 
 
<table class="docinfo" id="table1" frame="void" rules="none">
 <colgroup>

Modified: sandbox/gtl/doc/voronoi_benchmark.htm
==============================================================================
--- sandbox/gtl/doc/voronoi_benchmark.htm (original)
+++ sandbox/gtl/doc/voronoi_benchmark.htm 2012-04-09 14:47:19 EDT (Mon, 09 Apr 2012)
@@ -19,6 +19,7 @@

+
<meta http-equiv="Content-Language" content="en-us">
<meta http-equiv="Content-Type" content="text/html; charset=windows-1252"><title>Contents</title></head><body>

@@ -82,8 +83,7 @@
 <li>Layout Versus Schematic Tutorial</li>
 <li>Minkowski Sum Tutorial</li>
 <li>Voronoi Basic Tutorial</li>
- <li><a href="voronoi_diagram_advanced_tutorial.htm">Voronoi
- Diagram Advanced Tutorial</a></li>
+ <li>Voronoi Advanced Tutorial</li>
 </ul>
 </div>
 <h3 class="navbar">Polygon Sponsor</h3>
@@ -97,7 +97,7 @@
 <h1>Voronoi Benchmark</h1>There are not many known Voronoi libraries that are capable to satisfy following set of conditions: 
 <ul>
 <li>could handle both point and segment input geometries;</li>
- <li>give exact warranties about algorithm robustness and output topology; 
+ <li>give exact warranties about the algorithm robustness and output topology; 
 </li>
 <li>compute output geometries within precision of the output coordinate type.</li>
 </ul>
@@ -105,7 +105,7 @@
(it is clearly defined in CGAL documentation that it's capable to
handle the first two items, however there are no warranties on the
output geometries precision). Taking into account that CGAL is
-well-known in
+well-known in the
computational geometry area it should be clear why it is the main
target of this benchmark comparison. Other libraries (OpenVoronoi, QHull, Triangle), that at least
partially satisfy above requirements would be added to this benchmark
@@ -113,7 +113,7 @@
 <h2>Important 
 </h2>
While results of this benchmark show complete dominance of
-Boost.Polygon over CGAL implementation, we would like to make it clear
+the Boost.Polygon Voronoi over the CGAL Delaunay Graph implementation, we would like to make it clear
that both libraries use different approach to construct Voronoi
diagram. Thus there are problems were CGAL incremental approach would
be still more vital than sweepline approach (e.g. input sites are inserted as a live stream
@@ -123,15 +123,14 @@

 </h2>

-The benchmark consists of two parts. The first one constructs Voronoi diagram of a set of random points (voronoi_benchmark_points.cpp), the second one constructs Voronoi diagram of a set of random segments (voronoi_benchmark_segments.cpp).
-Below we list important details about benchmark, Boost and CGAL
-implementation that should be considered while reviewing benchmark
-details: 
+The benchmark consists of the two parts. The first one constructs the Voronoi diagram of a set of random points (voronoi_benchmark_points.cpp), the second one constructs the Voronoi diagram of a set of random segments (voronoi_benchmark_segments.cpp).
+Below we list important details about the benchmark, Boost and CGAL
+implementation that should be considered while reviewing benchmark results: 
 <ul>
- <li>we ensure that input data sets are the same for both libraries by initializing random generator with the same seed;</li>
- <li>we ensure that input data sets that consist of segments don't contain intersections; 
+ <li>We ensure that input data sets are the same for both libraries by initializing random generator with the same seed;</li>
+ <li>We ensure that input data sets that consist of segments don't contain intersections using Boost.Polygon functionality; 
 </li>
- <li>there is no Voronoi diagram data structure in CGAL at the
+ <li>There is no Voronoi diagram data structure in CGAL at the
moment. That's why we use Segment Delaunay Graph which is topologically
dual to Voronoi diagram;</li>
 <li>CGAL
@@ -141,13 +140,10 @@
storage required for those in our benchmarks. Thus one may expect
Boost.Polygon Voronoi to be even more faster in comparison with CGAL. 
 </li>
- <li>Boost and CGAL library use completely different approaches
-to construct Voronoi diagram: sweepline and incremental algorithms
-respectively; 
- </li>
- <li>Boost and CGAL implementation consider each input segment
+
+ <li>The Boost and CGAL implementation process each input segment
as 3 input objects (segment itself and its endpoints), thus the running
-time and memory usage for Voronoi of segments would be at least 3 times
+time and memory usage for Voronoi of segments would be approximately at least 3 times
slower than for Voronoi of points; 
 </li>
 </ul>

Modified: sandbox/gtl/doc/voronoi_builder.htm
==============================================================================
--- sandbox/gtl/doc/voronoi_builder.htm (original)
+++ sandbox/gtl/doc/voronoi_builder.htm 2012-04-09 14:47:19 EDT (Mon, 09 Apr 2012)
@@ -14,6 +14,7 @@

+
<meta http-equiv="Content-Language" content="en-us">
<meta http-equiv="Content-Type" content="text/html; charset=windows-1252"><title>Contents</title></head><body>

@@ -56,7 +57,7 @@
 <li>Property Merge 90</li>
 <li>Property Merge 45</li>
 <li>Property Merge</li>
- <li><a href="voronoi_main.hpp">Voronoi Main Page 
+ <li><a href="voronoi_main.htm">Voronoi Main Page 
</a></li>
 <li>Voronoi Benchmark 
 </li>
@@ -77,8 +78,7 @@
 <li>Layout Versus Schematic Tutorial</li>
 <li>Minkowski Sum Tutorial</li>
 <li>Voronoi Basic Tutorial</li>
- <li><a href="voronoi_diagram_advanced_tutorial.htm">Voronoi
- Diagram Advanced Tutorial</a></li>
+ <li>Voronoi Advanced Tutorial</li>
 </ul>
 </div>
 <h3 class="navbar">Polygon Sponsor</h3>
@@ -96,9 +96,9 @@
 events: site events and circle events (we won't go into details what
 those are exactly). Each event is reported to the output data structure builder. The structure
 shares Voronoi name as the events generated by it correspond to the
- Voronoi diagram edges and vertices and give enough information to
- construct Voronoi diagram of a set of points and segments. The
- requirements for the input / output coordinate types of the builder
+ Voronoi diagram edges and vertices, thus giving enough information to
+ construct the Voronoi diagram of a set of points and segments. The
+ requirements for the input/output coordinate types of the builder
 geometries are not the same as for the rest of the Boost.Polygon library.
 The main differences are in the following: 1) The input coordinate type
 is not required to be integral (while it still should be integer type);
@@ -118,20 +118,20 @@
 - specifies coordinate type of the input geometries (points and segments). 
 
 CTT
- - defines input / output coordinate types used by VP. 
+ - defines input/output coordinate types used by VP. 
 
 VP
- - predicates kernel, that provides builder with robust and efficient
+ - predicates kernel, that provides builder with the robust and efficient
 predicates. 
 The Voronoi builder data structure is ready to use from the box with
- 32-bit signed integer input coordinate type. The user may extend input
- coordinate range to other integer types (e.g. 64-bit integer), however
- this will also require manual set up of coordinate type traits. Default
+ 32-bit signed integer input coordinate type. The user may extend the input
+ coordinate range to the other integer types (e.g. 64-bit integer), however
+ this will also require manual set up of the coordinate type traits. Default
 voronoi_predicates<CTT>
- implementation provides correct predicates as soon as
+ structure provides correct predicates as soon as
 
 CTT
- types satisfy requirements explained below. In case those requirements
+ types satisfy the requirements explained below. In case those requirements
 are not satisfied for the user provided 
 CTT,
 proper 
@@ -156,14 +156,14 @@
    const int_type& x, 
    const int_type& y) 
 </td>
- <td style="vertical-align: top;">Inserts point object with specified coordinates into Voronoi builder. 
+ <td style="vertical-align: top;">Inserts point object with the specified coordinates into the Voronoi builder. 
 </td>
 </tr>
 <tr>
 <td style="vertical-align: top;">template <typename PointType> 
 void insert_point(const PointType& point) 
 </td>
- <td style="vertical-align: top;">Inserts point object into Voronoi builder. 
+ <td style="vertical-align: top;">Inserts point object into the Voronoi builder. 

 Point object should support x() and y() methods to retrieve its coordinates. 
 </td>
@@ -176,7 +176,7 @@
    PointIterator last_point) 
 </td>
 <td style="vertical-align: top;" width="693">Inserts point
- objects into Voronoi builder. 
+ objects into the Voronoi builder. 
 Point objects should support x() and y() methods to retrieve
 their coordinates. 
 </td>
@@ -188,7 +188,7 @@
    const int_type& x2, 
    const int_type& y2) 
 </td>
- <td style="vertical-align: top;">Insert segment object with specified coordinates into Voronoi builder. 
+ <td style="vertical-align: top;">Inserts segment object with the specified coordinates into the Voronoi builder. 
 </td>
 </tr>
 <tr>
@@ -197,16 +197,16 @@
    const PointType& point1, 
    const PointType& point2) 
 </td>
- <td style="vertical-align: top;">Insert segment object with specified endpoints into Voronoi builder. 
-Endpoint objects should support x() and y() methods to retrieve their coordinates. 
+ <td style="vertical-align: top;">Inserts segment object with the specified endpoints into the Voronoi builder. 
+Endpoint object should support x() and y() methods to retrieve its coordinates. 
 </td>
 </tr>
 <tr>
 <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">template <typename SegmentType> 
void insert_segment(const SegmentType& segment) 
 </td>
- <td style="vertical-align: top;">Insert segment object into Voronoi builder. 
-Segment object should support low() and high() methods that retrieve segment endpoints. 
+ <td style="vertical-align: top;">Inserts segment object into the Voronoi builder. 
+Segment object should support low() and high() methods to retrieve its endpoints. 
Endpoint object should support x() and y() methods to retrieve its coordinates. 
 </td>
 </tr>
@@ -216,11 +216,10 @@
 void insert_segments(SegmentIterator first_segment, SegmentIterator last_segment) 
 </td>
 <td style="vertical-align: top;" width="693">Inserts segment
- objects into Voronoi builder. 
- Segment objects should support low() and high() methods to
- retrieve segment endpoints. 
- Endpoint objects should support x() and y() methods to
- retrieve their coordinates. 
+ objects into the Voronoi builder. 
+Segment object should support low() and high() methods to retrieve its endpoints. 
+ Endpoint object should support x() and y() methods to
+ retrieve its coordinates. 
 </td>
 </tr>
 <tr>
@@ -234,7 +233,7 @@
 </td>
 <td style="vertical-align: top;" width="693">Inserts point and
 segment objects into Voronoi builder. 
- Requirements for the point and segment objects interface are
+ Requirements for the point and segment object interface are
 given above. 
 </td>
 </tr>
@@ -246,7 +245,7 @@
 <td style="vertical-align: top;" width="693">Runs sweepline
 algorithm over the set of the inserted geometries, outputs site
 and circle events to the OUTPUT data structure. It's
- responsibility of the output structure builder to process them. For
+ responsibility of the output structure builder object to process them. For
 example both Voronoi diagram and Delaunay triangulation could be
 constructed from the Voronoi builder events, however internally
 they are different data structures, so it's up to them to process
@@ -263,7 +262,7 @@
 </tr>
 </tbody></table>
 <h1>Voronoi Coordinate Type Traits</h1>
- The library provides default builder coordinate type traits for the
+ The library provides default coordinate type traits for the
 32-bit signed integer type:
 
 template <typename T> 
@@ -282,13 +281,15 @@
    typedef type_converter_efpt to_efpt_converter_type; 
 };
 
- One of the most important features of the library is that Voronoi
- builder output geometries are constructed with defined relative error.
- That means the more mantissa bits the user provided fpt_type has the
- better precision of the output geometries will be. In order for the user
- defined traits to be consistent with default Voronoi builder predicates
- implementation user should provide following set of coordinate types (assumption
- is made that input geometries have X-bit signed integer coordinate type): 
+ One
+of the most important features of the library is that Voronoi builder
+output geometries are constructed within defined relative error (64
+machine epsilons). That means the more mantissa bits the user provided
+fpt_type has the better precision of the output geometries will be. In
+order for the user defined traits to be consistent with the default
+Voronoi builder predicates user should define following set of
+coordinate types (the assumption is made that input geometries have
+X-bit signed integer coordinate type): 
 
 <table style="text-align: left; width: 100%;" border="1" cellpadding="2" cellspacing="2">
 <tbody><tr>
@@ -345,7 +346,7 @@
 ulp_cmp_type 
 </td>
 <td style="vertical-align: top;">Ulp comparison structure that
- checks if two fpt_type values are withing given ulp range
+ checks if two fpt_type values are withing the given ulp range
 (relative error range). 
 </td>
 </tr>
@@ -370,19 +371,20 @@

 </tbody></table>
 Notes: 
- 1) 4 different integer types are used (instead of a single big_int_type) to slightly improve algorithm performance and memory
- usage. 
- 2) As maximum required size of the big_int_type is known in advance
- library provided implementation of fixed integers could be used, which
- is much faster than heap-allocated big integers. 
-3) two separate floating-point types are defined because for input with
+1) Four different integer types are used (instead of a single
+big_int_type) to slightly improve algorithm performance and memory
+usage. 
+ 2) As the maximum required size of the big_int_type is known in advance
+ (based on the size of the integer type), library provided implementation of a fixed integer could be used (it
+ is much faster than heap-allocated big integers). 
+3) Two separate floating-point types are defined because for the input with
32-bit signed integer coordinates double won't be able to handle
2048-bit (64 * 32) integers as they will overflow its exponent. On the
gcc compiler it's possible to use 80-bit long doubles for both fpt
-types, however this is not supported by msvc compiler. 
- 4) efpt_type and to_efpt_converter_type are not used to construct
- Voronoi of points (mocks will work fine). 
- 5) for an example of the user defined builder coordinate type traits see
+types, however this is not supported by MSVC compiler. 
+ 4) efpt_type and to_efpt_converter_type are not used to construct the
+ Voronoi diagram of points (mocks will work fine). 
+ 5) For an example of the user defined builder coordinate type traits see
 <a href="voronoi_advanced_tutorial.htm">advanced Voronoi tutorial</a>.</td>
 </tr>
 <tr>

Modified: sandbox/gtl/doc/voronoi_diagram.htm
==============================================================================
--- sandbox/gtl/doc/voronoi_diagram.htm (original)
+++ sandbox/gtl/doc/voronoi_diagram.htm 2012-04-09 14:47:19 EDT (Mon, 09 Apr 2012)
@@ -24,6 +24,7 @@

+
<meta http-equiv="Content-Language" content="en-us">
<meta http-equiv="Content-Type" content="text/html; charset=windows-1252"><title>Contents</title><meta http-equiv="content-type" content="text/html; charset=utf-8"><meta http-equiv="content-type" content="text/html; charset=utf-8"></head><body>

@@ -94,7 +95,7 @@
 <li>Layout Versus Schematic Tutorial</li>
 <li>Minkowski Sum Tutorial</li>
 <li>Voronoi Basic Tutorial</li>
- <li>Voronoi Advanced Tutorial</li>
+ <li>Voronoi Advanced Tutorial</li>
 </ul>
 </div>
 <h3 class="navbar">Polygon Sponsor</h3>
@@ -106,30 +107,28 @@
 
 

- <h1>Voronoi Diagram</h1>
-Voronoi
+ <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
specified family of objects. The application area of this concept vary from Archaeology to Zoology. Boost.Polygon provides implementation of
-Voronoi diagram data structure in 2D space. Internal representation
+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
(points where three or more Voronoi edges intersect), Voronoi edges
(one dimensional curves containing points equidistant from the two
closest input sites). Each of the primitives (cell, vertex, edge)
-contains pointers to other linked primitives, so that it's always
-possible to efficiently traverse Voronoi diagram. Picture below shows
+contains pointers to the other linked primitives, so that it's always
+possible to efficiently traverse the Voronoi graph. Picture below shows
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 two
-endpoints). As one may notice each segment is split onto segment
-site itself and both its endpoints. As the result two additional
+correspond to the Voronoi cells in blue. It is considered that each
+input segment consists of 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. 
 
 <img style="border: 1px solid ; width: 300px; height: 300px;" alt="" src="images/voronoi2.png"> 
 
-Voronoi diagram declaration and list of member functions is following: 
+Voronoi diagram declaration and list of the member functions is following: 
 
 template <typename T, typename TRAITS = voronoi_diagram_traits<T> > 
 class voronoi_diagram; 
@@ -152,47 +151,47 @@
 <tr>
 <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">const cell_container_type &cells() const 
 </td>
- <td style="vertical-align: top;">Returns const reference to Voronoi cells container. 
+ <td style="vertical-align: top;">Returns the const reference to the cell container. 
 </td>
 </tr>
 <tr>
 <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">const vertex_container_type &vertices() const 
 </td>
- <td style="vertical-align: top;">Returns const reference to Voronoi vertices container. 
+ <td style="vertical-align: top;">Returns the const reference to the vertex container. 
 </td>
 </tr>
 <tr>
 <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">const edge_container_type &edges() const 
 </td>
- <td style="vertical-align: top;">Returns const reference to Voronoi edges container. 
+ <td style="vertical-align: top;">Returns the const reference to the edge container. 
 </td>
 </tr>
 <tr>
 <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">unsigned int num_cells() const 
 </td>
- <td style="vertical-align: top;">Returns number of cells in the Voronoi diagram. 
-This value should be the same as the size of cells container. 
+ <td style="vertical-align: top;">Returns the number of the cells in the Voronoi diagram. 
+This value should be the same as the size of the cell container. 
 </td>
 </tr>
 <tr>
 <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">unsigned int num_edges() const 
 </td>
- <td style="vertical-align: top;">Returns number of edges in the Voronoi diagram. 
-This value should be twice smaller then the size of edges container. 
-The reason is that we have two half-edges for each Voronoi edge. 
+ <td style="vertical-align: top;">Returns the number of the edges in the Voronoi diagram. 
+This value should be twice smaller than the size of the edge container. 
+The reason is that two half-edges are present for each Voronoi edge. 
 </td>
 </tr>
 <tr>
 <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">unsigned int num_vertices() const 
 </td>
- <td style="vertical-align: top;">Returns number of vertices in the Voronoi diagram. 
-This value should be the same as the size of vertices container. 
+ <td style="vertical-align: top;">Returns the number of the vertices in the Voronoi diagram. 
+This value should be the same as the size of the vertex container. 
 </td>
 </tr>
 </tbody>
 </table>
 <h1>Voronoi Edge</h1>
-Voronoi edge is represented as a bit improved classical half-edge data structure. The declaration and list of member functions is following: 
+Voronoi edge is represented as a bit improved classical half-edge data structure. The declaration and list of the member functions is following: 
 
 template <typename T> 
 class voronoi_edge; 
@@ -209,184 +208,184 @@
 <tr>
 <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">voronoi_cell_type *cell() 
 </td>
- <td style="vertical-align: top;">Returns pointer to the Voronoi cell that edge belongs to. 
+ <td style="vertical-align: top;">Returns the pointer to the Voronoi cell that edge belongs to. 
 </td>
 </tr>
 <tr>
 <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">const voronoi_cell_type *cell() const 
 </td>
- <td style="vertical-align: top;">Returns const pointer to the Voronoi cell that edge belongs to. 
+ <td style="vertical-align: top;">Returns the const pointer to the Voronoi cell that edge belongs to. 
 </td>
 </tr>
 <tr>
 <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">void cell(voronoi_cell_type *c) 
 </td>
- <td style="vertical-align: top;">Sets Voronoi cell pointer for the cell current edge belongs to. 
+ <td style="vertical-align: top;">Sets the Voronoi cell pointer for the cell current edge belongs to. 
 </td>
 </tr>
 <tr>
 <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">voronoi_vertex_type *vertex0() 
 </td>
- <td style="vertical-align: top;">Returns pointer to the start point of the edge. 
+ <td style="vertical-align: top;">Returns the pointer to the start point of the edge. 
If edge is infinite in that direction returns NULL. 
 </td>
 </tr>
 <tr>
 <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">const voronoi_vertex_type *vertex0() const 
 </td>
- <td style="vertical-align: top;">Returns const pointer to the start point of the edge. 
+ <td style="vertical-align: top;">Returns the const pointer to the start point of the edge. 
If edge is infinite in that direction returns NULL. 
 </td>
 </tr>
 <tr>
 <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">void vertex0(voronoi_vertex_type *v) 
 </td>
- <td style="vertical-align: top;">Sets start point pointer of the edge. 
+ <td style="vertical-align: top;">Sets the start point pointer of the edge. 
 </td>
 </tr>
 <tr>
 <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">voronoi_vertex_type *vertex1() 
 </td>
- <td style="vertical-align: top;">Returns pointer to the end point of the edge. 
-If edge is infinite in that direction returns NULL. 
+ <td style="vertical-align: top;">Returns the pointer to the end point of the edge. 
+If the edge is infinite in that direction returns NULL. 
 </td>
 </tr>
 <tr>
 <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">const voronoi_vertex_type *vertex1() const 
 </td>
- <td style="vertical-align: top;">Returns const pointer to the end point of the edge. 
-If edge is infinite in that direction returns NULL. 
+ <td style="vertical-align: top;">Returns the const pointer to the end point of the edge. 
+If the edge is infinite in that direction returns NULL. 
 </td>
 </tr>
 <tr>
 <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">void vertex1(voronoi_vertex_type *v) 
 </td>
- <td style="vertical-align: top;">Sets end point pointer of the edge. 
+ <td style="vertical-align: top;">Sets the endpoint pointer of the edge. 
 </td>
 </tr>
 <tr>
 <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">voronoi_edge_type *twin() 
 </td>
- <td style="vertical-align: top;">Returns pointer  to the twin edge. 
+ <td style="vertical-align: top;">Returns the pointer to the twin edge. 
 </td>
 </tr>
 <tr>
 <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">const voronoi_edge_type *twin() const 
 </td>
- <td style="vertical-align: top;">Returns const pointer to the twin edge. 
+ <td style="vertical-align: top;">Returns the const pointer to the twin edge. 
 </td>
 </tr>
 <tr>
 <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">void twin(voronoi_edge_type *e) 
 </td>
- <td style="vertical-align: top;">Sets twin edge pointer of the edge. 
+ <td style="vertical-align: top;">Sets the twin edge pointer of the edge. 
 </td>
 </tr>
 <tr>
 <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">voronoi_edge_type *next() 
 </td>
- <td style="vertical-align: top;">Returns pointer to the CCW next edge within the corresponding Voronoi cell. 
+ <td style="vertical-align: top;">Returns the pointer to the CCW next edge within the corresponding Voronoi cell. 
Edges not necessarily share a common vertex. 
 </td>
 </tr>
 <tr>
 <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">const voronoi_edge_type *next() const 
 </td>
- <td style="vertical-align: top;">Returns const pointer to the CCW next edge within the corresponding Voronoi cell. 
+ <td style="vertical-align: top;">Returns the const pointer to the CCW next edge within the corresponding Voronoi cell. 
Edges not necessarily share a common vertex. 
 </td>
 </tr>
 <tr>
 <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">void next(voronoi_edge_type *e) 
 </td>
- <td style="vertical-align: top;">Sets CCW next edge pointer of the edge. 
+ <td style="vertical-align: top;">Sets the CCW next edge pointer of the edge. 
 </td>
 </tr>
 <tr>
 <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">voronoi_edge_type *prev() 
 </td>
- <td style="vertical-align: top;">Returns pointer to the CCW prev edge within the corresponding Voronoi cell. 
+ <td style="vertical-align: top;">Returns the pointer to the CCW prev edge within the corresponding Voronoi cell. 
Edges not necessarily share a common vertex. 
 </td>
 </tr>
 <tr>
 <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">const voronoi_edge_type *prev() const 
 </td>
- <td style="vertical-align: top;">Returns const pointer to the CCW prev edge within the corresponding Voronoi cell. 
+ <td style="vertical-align: top;">Returns the const pointer to the CCW prev edge within the corresponding Voronoi cell. 
Edges not necessarily share a common vertex. 
 </td>
 </tr>
 <tr>
 <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">void prev(voronoi_edge_type *e) 
 </td>
- <td style="vertical-align: top;">Sets CCW prev edge pointer of the edge. 
+ <td style="vertical-align: top;">Sets the CCW prev edge pointer of the edge. 
 </td>
 </tr>

 <tr>
 <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">void *data() const 
 </td>
- <td style="vertical-align: top;">Returns pointer to the data associated with the edge. 
+ <td style="vertical-align: top;">Returns the pointer to the data associated with the edge. 
 </td>
 </tr>
 <tr>
 <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">void data(void *d) const 
 </td>
- <td style="vertical-align: top;">Sets data pointer of the edge. 
-This allows user to associate any data type with the edge. 
+ <td style="vertical-align: top;">Sets the data pointer of the edge. 
+This allows the user to associate any data type with the edge. 
 </td>
 </tr>
 <tr>
 <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">voronoi_edge_type *rot_next() 
 </td>
- <td style="vertical-align: top;">Returns pointer to the CCW next edge rotated around the edge start point. 
-If edge is infinite in that direction returns NULL. 
+ <td style="vertical-align: top;">Returns the pointer to the CCW next edge rotated around the edge start point. 
+If the edge is infinite in that direction returns NULL. 
 </td>
 </tr>
 <tr>
 <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">const voronoi_edge_type *rot_next() const 
 </td>
- <td style="vertical-align: top;">Returns const pointer to the CCW next edge rotated around the edge start point. 
+ <td style="vertical-align: top;">Returns the const pointer to the CCW next edge rotated around the edge start point. 

-If edge is infinite in that direction returns NULL.</td>
+If the edge is infinite in that direction returns NULL.</td>
 </tr>
 <tr>
 <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">voronoi_edge_type *rot_prev() 
 </td>
- <td style="vertical-align: top;">Returns pointer to the CCW prev edge rotated around the edge start point. 
-If edge is infinite in that direction returns NULL. 
+ <td style="vertical-align: top;">Returns the pointer to the CCW prev edge rotated around the edge start point. 
+If the edge is infinite in that direction returns NULL. 
 </td>
 </tr>
 <tr>
 <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">const voronoi_edge_type *rot_prev() const 
 </td>
- <td style="vertical-align: top;">Returns const pointer to the CCW prev edge rotated around the edge start point. 
+ <td style="vertical-align: top;">Returns the const pointer to the CCW prev edge rotated around the edge start point. 

-If edge is infinite in that direction returns NULL.</td>
+If the edge is infinite in that direction returns NULL.</td>
 </tr>
 <tr>
 <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">bool is_finite() const 
 </td>
- <td style="vertical-align: top;">Returns true if both endpoints of the edge are finite, else false. 
+ <td style="vertical-align: top;">Returns true if the both endpoints of the edge are finite, else false. 
 </td>
 </tr>
 <tr>
 <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">bool is_linear() const 
 </td>
- <td style="vertical-align: top;">Returns true if edge is linear (segment, ray, line), else false. 
+ <td style="vertical-align: top;">Returns true if the edge is linear (segment, ray, line), else false. 
 </td>
 </tr>
 <tr>
 <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">bool is_curved() const 
 </td>
- <td style="vertical-align: top;">Returns true if edge is curved (parabolic arc), else false. 
+ <td style="vertical-align: top;">Returns true if the edge is curved (parabolic arc), else false. 
 </td>
 </tr>
 <tr>
 <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">bool is_primary() const 
 </td>
- <td style="vertical-align: top;">Returns false if the edge goes through segment endpoint, else true. 
+ <td style="vertical-align: top;">Returns false if the edge goes through the endpoint of the segment, else true. 
 </td>
 </tr>
 </tbody>
@@ -396,7 +395,7 @@
 <h1>Voronoi Cell</h1>

Voronoi cell is represented by a site the cell contains and a pointer
-to the incident edge. The declaration and list of member functions is
+to the incident edge. The declaration and list of the member functions is
following: 
 
 template <typename T> 
@@ -409,7 +408,7 @@
 <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">voronoi_cell(const point_type &p1, 
             voronoi_edge_type *edge) 
 </td>
- <td style="vertical-align: top;">Constructs Voronoi cell from the given point site and pointer to the one of boundary edges. 
+ <td style="vertical-align: top;">Constructs the Voronoi cell from the given point site and pointer to the one of the boundary edges. 
 </td>
 </tr>
 <tr>
@@ -417,65 +416,65 @@
             const point_type &p2, 
             voronoi_edge_type *edge) 
 </td>
- <td style="vertical-align: top;">Constructs Voronoi cell from the given segment site and pointer to one of boundary edges. 
+ <td style="vertical-align: top;">Constructs the Voronoi cell from the given segment site and pointer to the one of the boundary edges. 
 </td>
 </tr>
 <tr>
 <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">const point_type &point0() const 
 </td>
- <td style="vertical-align: top;">If cell contains point site returns it. 
-If cell contains segment site returns its first endpoint. 
+ <td style="vertical-align: top;">If the cell contains point site returns it. 
+If the cell contains segment site returns its first endpoint. 
 </td>
 </tr>
 <tr>
 <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">const point_type &point1() const 
 </td>
- <td style="vertical-align: top;">If cell contains point site returns it. 
-If cell contains segment site returns its second endpoint. 
+ <td style="vertical-align: top;">If the cell contains point site returns it. 
+If the cell contains segment site returns its second endpoint. 
 </td>
 </tr>
 <tr>
 <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">voronoi_edge_type *incident_edge() 
 </td>
- <td style="vertical-align: top;">Returns pointer to one of the boundary edges. 
+ <td style="vertical-align: top;">Returns the pointer to the one of the boundary edges. 
 </td>
 </tr>
 <tr>
 <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">const voronoi_edge_type *incident_edge() const 
 </td>
- <td style="vertical-align: top;">Returns const pointer to one of the boundary edges. 
+ <td style="vertical-align: top;">Returns the const pointer to the one of the boundary edges. 
 </td>
 </tr>
 <tr>
 <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">void incident_edge(voronoi_edge_type *e) 
 </td>
- <td style="vertical-align: top;">Sets incident boundary edge pointer of the cell. 
+ <td style="vertical-align: top;">Sets the incident boundary edge pointer of the cell. 
 </td>
 </tr>

 <tr>
 <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">void *data() const 
 </td>
- <td style="vertical-align: top;">Returns pointer to the data associated with the cell.</td>
+ <td style="vertical-align: top;">Returns the pointer to the data associated with the cell.</td>
 </tr>
 <tr>
 <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">void data(void *d) const 
 </td>
- <td style="vertical-align: top;">Sets data pointer of the cell. 
+ <td style="vertical-align: top;">Sets the data pointer of the cell. 

-This allows user to associate any data type with the cell.</td>
+This allows the user to associate any data type with the cell.</td>
 </tr>
 <tr>
 <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">bool contains_point() const</td>
- <td style="vertical-align: top;">Returns true if cell contains point site, else false.</td>
+ <td style="vertical-align: top;">Returns true if the cell contains a point site, else false.</td>
 </tr>
 <tr>
 <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">bool contains_segment() const</td>
- <td style="vertical-align: top;">Returns true if cell contains segment site, else false.</td>
+ <td style="vertical-align: top;">Returns true if the cell contains a segment site, else false.</td>
 </tr>
 <tr>
 <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">bool is_degenerate() const </td>
- <td style="vertical-align: top;">Returns true if cell doesn't have incident edge. 
+ <td style="vertical-align: top;">Returns true if the cell doesn't have an incident edge. 

Could happen if a few input segments share a common endpoint.</td>
 </tr>
@@ -486,7 +485,7 @@
the Voronoi cell structure is equal to: 2 * sizeof(void *) + 4 *
sizeof(coordinate_type). 
 
-Following code snipped effectively traverses Voronoi edges around the Voronoi cell: 
+Following code snippet effectively traverses Voronoi edges around the Voronoi cell: 
 
 const voronoi_edge<double> *edge = cell->incident_edge(); 
 do { 
@@ -495,7 +494,7 @@
 } while (edge != cell->incident_edge()); 
 <h1>Voronoi Vertex</h1>
Voronoi vertex is represented by a point that corresponds to the vertex
-and a pointer to the incident edge. The declaration and list of member
+and a pointer to the incident edge. The declaration and list of the member
functions is following: 
 
 template <typename T> 
@@ -507,46 +506,46 @@
 <tr>
 <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">voronoi_vertex(const point_type &vertex, voronoi_edge_type *edge) 
 </td>
- <td style="vertical-align: top;">Constructs Voronoi vertex that corresponds to the give point and incident edge. 
+ <td style="vertical-align: top;">Constructs the Voronoi vertex that corresponds to the give point and incident edge. 
 </td>
 </tr>
 <tr>
 <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">const point_type &vertex() const 
 </td>
- <td style="vertical-align: top;">Returns point that represents vertex. 
+ <td style="vertical-align: top;">Returns the point that represents vertex. 
 </td>
 </tr>
 <tr>
 <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">voronoi_edge_type *incident_edge() 
 </td>
- <td style="vertical-align: top;">Returns incident edge pointer. 
+ <td style="vertical-align: top;">Returns the incident edge pointer. 
 </td>
 </tr>
 <tr>
 <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">const voronoi_edge_type *incident_edge() const 
 </td>
- <td style="vertical-align: top;">Returns const pointer to the incident edge. 
+ <td style="vertical-align: top;">Returns the const pointer to the incident edge. 
 </td>
 </tr>
 <tr>
 <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">void incident_edge(voronoi_edge_type *e) 
 </td>
- <td style="vertical-align: top;">Sets incident edge pointer. 
+ <td style="vertical-align: top;">Sets the incident edge pointer. 
 </td>
 </tr>
 <tr>
 <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">void *data() const 
 </td>
- <td style="vertical-align: top;">Returns pointer to the data associated with the vertex.</td>
+ <td style="vertical-align: top;">Returns the pointer to the data associated with the vertex.</td>
 </tr>

 <tr>
 <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">void data(void *d) const 
 </td>
- <td style="vertical-align: top;">Sets data pointer of the cell. 
+ <td style="vertical-align: top;">Sets the data pointer of the cell. 

-This allows user to associate any data type with the vertex.</td>
+This allows the user to associate any data type with the vertex.</td>
 </tr>
 </tbody>
 </table>
@@ -568,8 +567,8 @@
 <h1>Voronoi Diagram Traits 
 </h1>

-Voronoi diagram traits are used to configure Voronoi diagram data
-structure. The declaration and list of required type definitions is
+Voronoi diagram traits are used to configure the Voronoi diagram data
+structure. The declaration and list of the required type definitions is
following: 
 
 template <typename T> 
@@ -588,7 +587,7 @@
 <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">ctype_converter_type 
 </td>
 <td style="vertical-align: top;">Coordinate type converter structure. 
-Converts coordinates provided by Voronoi builder to the internal coordinate type. 
+Converts the coordinates provided by the Voronoi builder to the internal coordinate type. 
 </td>
 </tr>
 <tr>

Modified: sandbox/gtl/doc/voronoi_main.htm
==============================================================================
--- sandbox/gtl/doc/voronoi_main.htm (original)
+++ sandbox/gtl/doc/voronoi_main.htm 2012-04-09 14:47:19 EDT (Mon, 09 Apr 2012)
@@ -35,6 +35,7 @@

+
<meta http-equiv="Content-Language" content="en-us">
<meta http-equiv="Content-Type" content="text/html; charset=windows-1252"><title>Contents</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"></head><body>

@@ -120,10 +121,10 @@
 <h1>THE BOOST.POLYGON VORONOI LIBRARY 
</h1><img style="width: 900px; height: 300px;" alt="" src="images/voronoi3.png"> 
The Boost.Polygon Voronoi library provides functionality to construct Voronoi diagrams
-of a set of points and segments in 2D space with the following set of
+of a set of points and linear segments in 2D space with the following set of
limitations: 
 <ul>
- <li>coordinates of input points and endpoints of segments
+ <li>coordinates of the input points and endpoints of the segments
should be of integer type;</li>
 <li>input segments should not intersect
except their endpoints.</li>
@@ -146,45 +147,51 @@
degeneracies for some inputs, the algorithm produces wrong output for
some inputs (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 valid output in 100% of cases, thus user can rely on
+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
implementations of any complex geometric algorithm. The main issues of
that could be divided onto two main categories: memory management
-issues, numeric stability issues. Voronoi implementation avoids the
+issues, numeric stability issues. Our implementation avoids the
first type of issues using pure STL data structure, thus you won't find
any operator new in the code. The second category of problems is
resolved using multiprecision geometric predicates.
Even for commercial implementations usage of such predicates usually
-results in huge performance slowdown. Here is another strong side of
-Voronoi: we avoid multiprecision computations in 95% of cases using
+results in 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 relative error arithmetic apparatus to identify them and switch to higher precision predicates when required. 
+exact, but we developed relative error arithmetic apparatus to identify them and switch to the higher precision predicates when required. 

- <h2>Precision of Output Structures 
+ <h2>Precision of the Output Structures 

 </h2>

One of the extremely important results of using two types of predicates
is that library efficiently computes relatively precise coordinates of
-output geometries. Here we will explain a bit what exactly
-"relatively precise" means and how received output may differ from
-theoretically correct one (here and after we assume that output
+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). 
 
-Voronoi implementation guaranties that relative error of the output
-geometries coordinates is always not higher then 64 machine epsilons (6
+Voronoi implementation guaranties that the relative error of the
+coordinates of the output
+geometries is always not higher then 64 machine epsilons (6
bits of mantissa), while in many cases it is slightly less. That also
-means that using floating-point type with larger mantissa will produce
-more precise output. Lets consider following example: output Voronoi
-vertex has double (53 bit mantissa) x-coordinate equal to 1.0, then
-absolute error is at most 2^-53 * 2^6 = 2^-47 and exact value of
+means that using floating-point type with the larger mantissa will
+produce the output coordinates with more precise bits. Lets 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 exact value of x-coordinate lies in the range
-[2^31 - 2^-16, 2^31 + 2^16]. For 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 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. 
+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 absolute and relative errors try this article. 
 
During finalization step library unites Voronoi vertices whose both
coordinates are situated within relative error range equal to 128
@@ -204,13 +211,13 @@

 <h2>Fully Functional with Segment Inputs</h2>

-There are not many implementations of Voronoi diagrams that could
-handle segment inputs, even considering commercial ones. Support of
+There are not many implementations of the Voronoi diagram construction algorithm that could
+handle 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 allows to compute
-medial axis transform of the arbitrary input geometry. So one may start
+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. 

@@ -224,8 +231,8 @@
static inline void construct_voronoi_points( 
    const PC &points, VD *output) 
 </td>
- <td style="vertical-align: top;">Constructs Voronoi diagram of a set of points into the output data structure. 
-Coordinates of the input geometries should belong to [-2^31, 2^31-1] integer range. 
+ <td style="vertical-align: top;">Constructs the Voronoi diagram of a set of points into the output data structure. 
+Coordinates of the input geometries should belong to the [-2^31, 2^31-1] integer range. 
PC is a container of points that supports forward iterator. 
 </td>
 </tr>
@@ -234,8 +241,8 @@
static inline void construct_voronoi_segments( 
    const SC &segments, VD *output) 
 </td>
- <td style="vertical-align: top;">Constructs Voronoi diagram of a set of segments into the output data structure. 
-Coordinates of the input geometries should belong to [-2^31, 2^31-1] integer range. 
+ <td style="vertical-align: top;">Constructs the Voronoi diagram of a set of segments into the output data structure. 
+Coordinates of the input geometries should belong to the [-2^31, 2^31-1] integer range. 
SC is a container of segments that supports forward iterator. 
Segment object should provide low(), high() public methods to retrieve endpoints of a segment. 
 </td>
@@ -245,22 +252,22 @@
static inline void construct_voronoi( 
    const PC &points, const SC &segments, VD *output) 
 </td>
- <td style="vertical-align: top;">Constructs Voronoi diagram of a set of points and segments into the output data structure. 
-Coordinates of the input geometries should belong to [-2^31, 2^31-1] integer range. 
+ <td style="vertical-align: top;">Constructs the Voronoi diagram of a set of points and segments into the output data structure. 
+Coordinates of the input geometries should belong to the [-2^31, 2^31-1] integer range. 
 </td>
 </tr>
 </tbody>
 </table>
 
-For users that don't want to go into the details of the library this
-means that it's possible to construct Voronoi diagram with the
+For the users that don't want to go into the details of the library this
+means that it's possible to construct the Voronoi diagram with the
following two lines of code: 
 
 voronoi_diagram<double> vd; 
 construct_voronoi(points, segments, &vd); 
 
-Isn't that simple? The library also provides clear interfaces to associate user data with output geometries, efficiently traverse Voronoi graph and utilities to visualize output primitives (e.g. discretization of parabolic edges, clipping of linear edges). More details on those is covered in the basic Voronoi tutorial.  Advanced usage of the library with configuration of the coordinate types is explained in the advanced Voronoi tutorial. 
- 
+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 visualize output primitives (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 types is explained in the advanced Voronoi tutorial. 
 <h2>No Third Party Dependencies 
 </h2>
Yes, the library doesn't depend on any 3rd party code. Even more than
@@ -272,46 +279,49 @@


 <h2>Extensible for User Provided Coordinate Types</h2>
-
-Voronoi implementation is coordinate type agnostic. That means that as soon as user provided types satisfy set of Voronoi builder coordinate type traits restrictions
-and implement library required methods no changes are required neither
-from algorithm, nor from predicates implementation. So it's possible to
-construct Voronoi diagram for 256 bit integer input coordinate type and
-512 bit output floating-point type without changing any internal code. 
+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 neither
+from 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
+512-bit output floating-point type without making any changes to the internal code. 


 <h2>Bright Future 

 </h2>

-Below one may find list of main directions for the future development of the library. 
-High-priority tasks that already have approximate implementation plan (some of those may be proposed as future GSoC projects): 
+Below one may find the list of the main directions for the future development of the library. 
+High-priority tasks that already have approximate implementation plan
+are following (some of those may be proposed as future GSoC projects): 
 <ul>
 <li>Implementing Delaunay triangulation data structure. 
-Note: only data structure needs to be implemented that properly processes events provided by Voronoi builder.</li>
+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. 
-Note: in general case Voronoi diagram has completely the same geometry
-as medial axis (they are 100% equal), however for many applications
-user is not interested in diagram inside hole regions. The main point
+Note: in general case the Voronoi diagram has completely the same geometry
+as the medial axis (they are 100% equal), however for many applications
+user is not interested in the Voronoi edges inside the hole regions. 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. 
-Note: there should be r-tree data structure available soon in the Boost libraries.</li>
+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
constructed in O(N) time. 
</li>
- <li>Closer integration with interfaces and functionality of Boost Polygon Library. 
+ <li>Closer integration with the interfaces and functionality of Boost Polygon Library. 
 </li>
 </ul>
High-priority tasks to be considered: 
 <ul>
+ <li>Dropping restriction on the non-intersecting input geometries.</li>
 <li>Integration of Voronoi diagram structure with BGL (Boost Graph Library).</li>
- <li>Support of other types of distance metrics.</li>
- <li>Construction of constrained Delaunay triangulation.</li>
- <li>Support of circle input geometries.</li>
- <li>Dropping restriction on non-intersecting input geometries.</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>
+

 </ul>
Based on the community suggestions priorities may be changed. 
@@ -319,17 +329,17 @@
 <h2>Theoretical Research 

 </h2>Voronoi
-was developed as part of Google Summer of Code 2010. The
+was developed as part of the Google Summer of Code 2010. The
library was actively maintained for the last two years and involved
-strong math research in the field of algorithms, data structures,
+the 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
results or implementation with
benchmarks nobody else can reproduce. The opposite story is with
-Voronoi. We provide pure implementation and benchmarks one may run on
+the Boolst.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
-authors would like to acknowledge Steven Fortune's article "A Sweepline algorithm for Voronoi diagrams", that contains fundamental ideas of the current implementation. 
+authors would like to acknowledge Steven Fortune's article "A Sweepline algorithm for Voronoi diagrams", that contains the fundamental ideas of the current implementation.

Modified: sandbox/gtl/doc/voronoi_predicates.htm
==============================================================================
--- sandbox/gtl/doc/voronoi_predicates.htm (original)
+++ sandbox/gtl/doc/voronoi_predicates.htm 2012-04-09 14:47:19 EDT (Mon, 09 Apr 2012)
@@ -14,6 +14,7 @@

+
<meta http-equiv="Content-Language" content="en-us">
<meta http-equiv="Content-Type" content="text/html; charset=windows-1252"><title>Contents</title></head><body>

@@ -84,7 +85,7 @@
 <li>Layout Versus Schematic Tutorial</li>
 <li>Minkowski Sum Tutorial</li>
 <li>Voronoi Basic Tutorial</li>
- <li>Voronoi Advanced Tutorial</li>
+ <li>Voronoi Advanced Tutorial</li>
 </ul>
 </div>
 <h3 class="navbar">Polygon Sponsor</h3>
@@ -97,12 +98,11 @@
 
 <h1>Voronoi Predicates 
</h1>In mathematical theory predicate is an operator which returns true
-or false (e.g. it may answer a question: "is it sunny today?"). 
-Voronoi predicates contain implementation of a set of geometric
-predicates used by Voronoi builder. Except of those it also provides
-functors that allow to compute coordinates of centers of inscribed
+or false (e.g. it may answer a question: "is it sunny today?"). The Voronoi predicates contain implementation of a set of the geometric
+predicates used by the Voronoi builder. Except of those it also provides
+functors that allow to compute the coordinates of the centers of the inscribed
circles (those correspond to the Voronoi vertices) within the given
-relative error precision range. This means that the more mantissa bits
+relative error precision range (64 machine epsilons). This means that the more mantissa bits
your floating point type has the better precision of the output
geometries you'll get. This
is a very handy functionality as it allows to improve output precision
@@ -110,14 +110,14 @@

 <h2>Geometric Predicates</h2>

-The main issues with implementation of any complex geometric
-algorithm arise when dealing with robustness of geometric predicates.
+The main issues with the implementation of any complex geometric
+algorithm arise when dealing with the robustness of the geometric predicates.
Usually this
-is also the point where commercial projects stand strong against
+is also the point where the commercial projects stand strong against
noncommercial implementations (it's not the case with our
implementation).
-For the short example let's consider following code snippet, that could
-be used to compute orientation of three points: 
+For the short example let's consider the following code snippet, that could
+be used to compute orientation of the three points: 
 
 double cross_product(double dx1, double dy1, double dx2, double dy2) { 
   return dx1 * dy2 - dx2 * dy1; 
@@ -139,53 +139,73 @@
corrupting algorithm underlying structures or producing completely
invalid output. Voronoi uses
slightly more complex predicates. To insure that they are robust and
-efficient approach that combines two known techniques is used: lazy
+efficient the approach that combines two known techniques (lazy
arithmetic and multiple
-precision computations. 
+precision computations) is used. 


 <h2>Lazy Arithmetic</h2>
Lazy
-arithmetic is based on usage of IEEE-754 floating-point types to evaluate an expression. While this approach has a good speed
+arithmetic is based on the usage of IEEE-754 floating-point types to
+quickly evaluate the result of the expression. While this approach has
+a good speed
performance it doesn't produce reliable results all the time (as in the
example above). The way to solve the issue is apart from computing
-result of the expression compute the relative error of it also. This will
-give us the range of values evaluated result belongs to and based on that we can
+result of the expression compute the relative error of it also. This
+will
+give us the range of values the evaluated result belongs to and based
+on that we can
come up with two decisions: 1) output the value; 2) recompute the
-expression using multiprecision precision type. The way relative errors are
+expression using multiprecision type. The way relative errors are
evaluated is explained in the Voronoi Robust FPT section. 
 <h2>Multiple Precision Arithmetic</h2>
In the vast majority of cases
-lazy arithmetic approach produces correct result thus further
-processing is not required. In other cases Voronoi defined or user
+the lazy arithmetic approach produces correct result thus further
+processing is not required. In other cases the Voronoi library defined or user
provided multiple precision types are used to produce correct result.
However even that doesn't solve all the cases. Multiprecision geometric
-predicates could be divided onto two categories: 
+predicates could be divided onto two categories: 
1) mathematical transformation of the predicate exists that evaluates exact result: 
+
 
+
Predicate: A/B + C/D ?< 0; 
+
After math. transform: (A*D + B*C) / (B * D) ?< 0; 
+
 
+
Predicate: sqrt(A) ?< 1.2; 
+
After math. transform: A ?< 1.44; 
+
 
+
 2) the correct result could be produced only by increasing
precision of the multiprecision type and with defined relative error
for the output type: 
 
 Predicate: sqrt(A) + sqrt(B) + sqrt(C) + sqrt(D) + sqrt(E) ?< 1.2; 
+
Imagine that value of the expression to the left is very close to 1.2; 
+
 
 Predicate: sin(x) ?< 0.57; 
+
Relative error of sin function should be known; 
+
 
- Voronoi of points could be implemented using only predicates of the first type, however Voronoi of segments could not.
+ The Voronoi of points could be completely
+implemented using predicates of the first type, however the Voronoi of
+segments could not.
The predicate that doesn't fall into the first category is responsible
-for comparison of Voronoi circle events. However it appears that properly used
+for comparison of the Voronoi circle events. However it appears that
+properly used
this predicate can't corrupt algorithm internal structures and produces
output technically the same as produced in case this predicate fell in
the first category.  The main reasons for this are: 1) algorithm
-operates with integer coordinate type of input geometries; 2) closely
+operates with integer coordinate type of the input geometries; 2)
+closely
situated Voronoi vertices are considered to be the same in the output
data structure (this won't influence main targets algorithm is used
for).

Modified: sandbox/gtl/doc/voronoi_robust_fpt.htm
==============================================================================
--- sandbox/gtl/doc/voronoi_robust_fpt.htm (original)
+++ sandbox/gtl/doc/voronoi_robust_fpt.htm 2012-04-09 14:47:19 EDT (Mon, 09 Apr 2012)
@@ -13,6 +13,7 @@

+
<meta http-equiv="Content-Language" content="en-us">
<meta http-equiv="Content-Type" content="text/html; charset=windows-1252"><title>Contents</title></head><body>

@@ -83,7 +84,7 @@
 <li>Layout Versus Schematic Tutorial</li>
 <li>Minkowski Sum Tutorial</li>
 <li>Voronoi Basic Tutorial</li>
- <li>Voronoi Advanced Tutorial</li>
+ <li>Voronoi Advanced Tutorial</li>
 </ul>
 </div>
 <h3 class="navbar">Polygon Sponsor</h3>
@@ -94,26 +95,25 @@
 <td style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;" valign="top" width="100%">
 
 
- <h1>Voronoi Robust FPT</h1>
- Voronoi
-robust floating-point types are set of classes and tools that
-allow to estimate relative error of arithmetic expressions. It is
-assumed that other Boost libraries may find this unit functionality
-extremely useful. One can use them to implement robust and efficient
-arithmetic predicates or functors that compute values with known
+ <h1>Voronoi Robust FPT</h1>The Voronoi
+robust floating-point types are the set of classes and tools that
+allow to estimate relative error of the arithmetic expressions. It is
+assumed that the other Boost libraries may find this unit functionality
+extremely useful, as it can be use d to implement robust and efficient
+arithmetic predicates or functors that compute values within known
relative error. 


 <h2>Robust Fpt Type</h2>

-Robust
-fpt (robust floating-point type)
-- represents IEEE-754 floating-point type wrapper that also contains
-information about relative error of the underlying value. The
+The robust
+fpt type (robust floating-point type)
+- represents the IEEE-754 floating-point type wrapper that also contains
+information about the relative error of the underlying value. The
implementation overloads 5 standard operations: +, -, *, /, sqrt and
-apart from evaluating value of the expression also computes its relative
-error. Let's consider two values A and B; C - rounding error; re
-- correspond to relative error, then following rules apply: 
+apart from the evaluating value of the expression also computes its relative
+error. Let's consider two values A and B; C - rounding error, re(X)
+- relative error of the X expression, then following rules apply: 
 
 re(A+B) <= max(re(A), re(B)) + C, if A * B >= 0; 
 re(A-B) <= (B * re(A) + A * re(B)) / |A - B| + C, if A * B < 0; 
@@ -121,36 +121,34 @@
 re(A/B) <= re(A) + re(B) + C; 
 re(sqrt(A)) <= re(A) * 0.5 + C; 
 
- The constant C is equal to the rounding relative error
+ The constant C is equal to the rounding error,
which for the above set of arithmetic operations in the IEEE-754
floating-point implementation should be equal to 1 machine epsilon. 


- <h2>Robust Difference Type</h2>
-Robust
+ <h2>Robust Difference Type</h2>The robust
difference type -
-represents expression wrapper that holds positive and negative partial
+represents expression wrapper that holds the positive and negative partial
sums of the expression in a separate values in order to avoid
-cancellation errors before evaluating final difference. Following
+the cancellation errors before evaluating the final difference. Following
arithmetic operators are overloaded for the robust difference type: +,
-, *, / (division operator is not overloaded for the case were both
arguments have robust difference type). 
Looking at the relative error formulas above one may notice a few facts about them: 
-1) all of the formulas evaluate upper bound of the relative error, while it could be a lot lower; 
-2) relative error of the expression depends on the order operations are evaluated; 
-3) relative error of difference of two positive numbers may be
-extremely large in case their values are close to each other (this is
-also called cancellation error). 
-To explain this a bit consider following expression (~ - stands for almost equal, << - many times larger than): 
+1) all of the formulas evaluate upper bound of the relative error, the actual value could be a lot smaller; 
+2) relative error estimate for the expression depends on the order operations are executed; 
+3) relative error of  the difference of two positive numbers may be
+extremely large in case their values are close to each other (this is also known as the cancellation error). 
+To explain this a bit consider the following expression (~ - stands for almost equal, << - many times larger than): 
 
 A - B + C, where A ~ B and C << B; 
 
-Computing relative error of this expression from left to right will produce extremely large relative error: 
+Computing the relative error of this expression from left to right will produce extremely large relative error: 
 
 re(A-B+C) = max(re(A-B), re(C)) = re(A-B) = (B * re(A) + A * re(B)) / 0 = INF; 
 
- While doing this from right to left will keep relative error value small: 
+ While doing this from right to left will keep the relative error value small: 
 
 re(A-B+C) = re(C-B+A) = max(re(C-B), re(A)) = max(re(A), re(B)); 
 
@@ -158,13 +156,11 @@
Here is the place where robust difference type comes useful. Basically
it splits expression onto positive and negative partial sums and evaluates the
difference only when the result is required. And did I mention that
-positive and negative values might be of robust fpt type, that's why
-relative error is always known for the expression result. 
- <h2>Robust Sqrt Expression Structure</h2>
-
-Robust square root expression structure allows to compute results of
-expression that contains square roots with predefined relative error.
-As an example consider following expression: 
+positive and negative values might be of the robust fpt type, that's why
+the relative error is always known for the expression result. 
+ <h2>Robust Sqrt Expression Structure</h2>The robust square root expression structure allows to compute the result of
+the expression that contains square roots within defined relative error.
+As an example consider the following expression: 
 
 A * sqrt(a) - B * sqrt(b), A * B > 0, a >= 0, b >= 0; 
 
@@ -172,13 +168,12 @@
however it may be transformed to the next equivalent expression: 
 
(A * A * a - B * B * b) / (A * sqrt(a) + B * sqrt(b)); 
- 
-Numerator and denominator of this expression could be computed directly as those won't lead to the cancellation errors. 
-In general case robust sqrt expression structure allows to evaluate following set of expressions: 
+ The numerator and denominator of this expression could be computed directly as those won't lead to the cancellation errors. 
+In general case the robust sqrt expression structure allows to evaluate the following set of expressions: 
 
sum(A[i] * sqrt(a[i]), i = 1 .. N), N <= 4; 
 
-This appears to be enough for the Voronoi. 
+This appears to be enough for the Boost.Polygon Voronoi.

Modified: sandbox/gtl/doc/voronoi_utils.htm
==============================================================================
--- sandbox/gtl/doc/voronoi_utils.htm (original)
+++ sandbox/gtl/doc/voronoi_utils.htm 2012-04-09 14:47:19 EDT (Mon, 09 Apr 2012)
@@ -19,6 +19,7 @@

+
<meta http-equiv="Content-Language" content="en-us">
<meta http-equiv="Content-Type" content="text/html; charset=windows-1252"><title>Contents</title><meta http-equiv="content-type" content="text/html; charset=utf-8"><meta http-equiv="content-type" content="text/html; charset=utf-8"></head><body>

@@ -89,7 +90,7 @@
 <li>Layout Versus Schematic Tutorial</li>
 <li>Minkowski Sum Tutorial</li>
 <li>Voronoi Basic Tutorial</li>
- <li>Voronoi Advanced Tutorial</li>
+ <li>Voronoi Advanced Tutorial</li>
 </ul>
 </div>
 <h3 class="navbar">Polygon Sponsor</h3>
@@ -103,12 +104,12 @@
 <h1>Voronoi Utils</h1>Voronoi
utilities implements a set of tools that users may find useful
especially for
-the visualization of Voronoi diagrams or discretization of parabolic
+the visualization of the Voronoi diagrams or discretization of the parabolic
edges. Keep in mind that there are no warranties about precision of the
-output structures produces by utils class. This is mostly because input
+output structures produces by the utilities class. This is mostly because input
coordinate type utilities operate with
is double. Any degeneracies may be reported, however those are of low
-priority to be fixed. Class
+priority to be fixed. The class
declaration is following: 
 
template <typename T, typename TRAITS = voronoi_utils_traits<T> > 
@@ -127,8 +128,8 @@
    const bounding_rectangle<CT> &brect, 
    fpt_type factor = 1.0) 
 </td>
- <td style="vertical-align: top;">Returns scaled bounding rectangle. 
-The center of transformation corresponds to the center of the input rectangle. 
+ <td style="vertical-align: top;">Returns the scaled bounding rectangle. 
+The center of the transformation corresponds to the center of the input rectangle. 
 </td>
 </tr>
 <tr>
@@ -138,9 +139,9 @@
    coordinate_type max_error, 
    point_set_type &discretization) 
 </td>
- <td style="vertical-align: top;">Provides point discretization of the input voronoi edge. 
+ <td style="vertical-align: top;">Provides the point discretization of the input voronoi edge. 
If the edge is infinite (ray, line) doesn't fill output point set. 
-Max error specifies maximum distance that is allowed between original parabolic arc and its approximation. 
+Max error specifies the maximum absolute value of the approximation. 

 </td>
 </tr>
@@ -151,8 +152,8 @@
    const brect_type &brect, 
    point_set_type &clipped_edge) 
 </td>
- <td style="vertical-align: top;">Clips the input Voronoi edges with specified rectangle. 
-If the edge is a parabolic arc doesn't fill output point set. 
+ <td style="vertical-align: top;">Clips the input Voronoi edges with the specified rectangle. 
+If the edge is a parabolic arc doesn't fill the output point set. 
 </td>
 </tr><tr>
 <td style="vertical-align: top;">template <typename PointType> 
@@ -162,25 +163,24 @@
    const brect_type &brect, 
    point_set_type &clipped_edge) 
 </td>
- <td style="vertical-align: top;">Clips the input linear edge with specified rectangle. 
-Edge is defined by its endpoints. 
+ <td style="vertical-align: top;">Clips the input linear edge with the specified rectangle. The edge is defined by its endpoints. 
 </td>
 </tr>

 </tbody>
- </table><h1>Bounding Rectangle</h1>The module provides implementation of a simple bounding rectangle structure with following declaration: 
+ </table><h1>Bounding Rectangle</h1>The module provides implementation of a simple bounding rectangle structure with the following declaration: 
 
 template <typename T> 
 class bounding_rectangle; 
 
-T - coordinate type rectangle operates with. 
+T - coordinate type the rectangle operates with. 
 <h2 style="color: rgb(0, 0, 0); font-family: 'Times New Roman'; font-style: normal; font-variant: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px;">Member Functions</h2>
 <table style="text-align: left; width: 100%;" border="1" cellpadding="2" cellspacing="2">
 <tbody>
 <tr>
 <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">bounding_rectangle() 
 </td>
- <td style="vertical-align: top;">Default constructor. Initializes empty bounding rectangle. 
+ <td style="vertical-align: top;">Default constructor. Initializes the empty bounding rectangle. 
 </td>
 </tr>
 <tr>
@@ -190,7 +190,7 @@
    coordinate_type x2, 
    coordinate_type y2) 
 </td>
- <td style="vertical-align: top;">Constructs bounding rectangle with given coordinates. 
+ <td style="vertical-align: top;">Constructs the bounding rectangle with the given coordinates. 
 </td>
 </tr>
 <tr>
@@ -198,14 +198,14 @@
    coordinate_type x, 
    coordinate_type y) 
 </td>
- <td style="vertical-align: top;">Extends bounding rectangle with a specified point defined by its coordinates. 
-If the rectangle is empty sets coordinates of the bottom left and top right corners. 
+ <td style="vertical-align: top;">Extends the bounding rectangle with the specified point defined by its coordinates. 
+If the rectangle is not initialized, initialized it with the specifed point. 
 </td>
 </tr>
 <tr>
 <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">bool is_empty() const 
 </td>
- <td style="vertical-align: top;">Returns true if rectangle is empty (there were no updates), else false. 
+ <td style="vertical-align: top;">Returns true if the rectangle is empty (uninitialized), else false. 
 </td>
 </tr>
 <tr>
@@ -219,38 +219,38 @@
   coordinate_type x, 
   coordinate_type y) const 
 </td>
- <td style="vertical-align: top;">Returns true if rectangle contains given point defined by its coordinates, else false. 
+ <td style="vertical-align: top;">Returns true if the rectangle contains the given point defined by its coordinates, else false. 
 </td>
 </tr>
 <tr>
 <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">coordinate_type x_min() const 
 </td>
- <td style="vertical-align: top;">Returns x coordinate of the bottom left corner of rectangle. 
+ <td style="vertical-align: top;">Returns the x coordinate of the bottom left corner of the rectangle. 
 </td>
 </tr>
 <tr>
 <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">coordinate_type y_min() const 
 </td>
- <td style="vertical-align: top;">Returns y coordinate of the bottom left corner of rectangle. 
+ <td style="vertical-align: top;">Returns the y coordinate of the bottom left corner of the rectangle. 
 </td>
 </tr>
 <tr>
 <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">coordinate_type x_max() const 
 </td>
- <td style="vertical-align: top;">Returns x coordinate of the top right corner of rectangle. 
+ <td style="vertical-align: top;">Returns the x coordinate of the top right corner of the rectangle. 
 </td>
 </tr>
 <tr>
 <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">coordinate_type y_max() const 
 </td>
- <td style="vertical-align: top;">Returns y coordinate of the top right corner of rectangle. 
+ <td style="vertical-align: top;">Returns the y coordinate of the top right corner of the rectangle. 
 </td>
 </tr>
 </tbody>
 </table>
 <h1>Voronoi Utils Traits 
 </h1>
-Below is shown the default Voronoi utilities traits: 
+Below is shown the default Voronoi utilities traits declaration: 
 
 template <typename fpt_> 
 struct voronoi_utils_traits; 
@@ -270,8 +270,8 @@
 }; 
 
 Most of the types define output geometries.
-ctype_converter_type is used to cast coordinate type of the input
-primitives to the one used by utils internally. 
+ctype_converter_type is used to cast the coordinate type of the input
+primitives to the one used by the utililities internally.

Modified: sandbox/gtl/libs/polygon/example/voronoi_basic_tutorial.cpp
==============================================================================
--- sandbox/gtl/libs/polygon/example/voronoi_basic_tutorial.cpp (original)
+++ sandbox/gtl/libs/polygon/example/voronoi_basic_tutorial.cpp 2012-04-09 14:47:19 EDT (Mon, 09 Apr 2012)
@@ -24,7 +24,7 @@
   int y() const { return y_; }

private:
- // Don't forget should be castable to the signed int32 type!
+ // Should be castable to the signed int32 type!
   int x_;
   int y_;
};

Next message: vicente.botet_at_[hidden]: "[Boost-commit] svn:boost r77857 - trunk/libs/thread/test"
Previous message: antoshkka_at_[hidden]: "[Boost-commit] svn:boost r77855 - trunk/status"

Date view	Thread view	Subject view	Author view

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