Boost-Commit :

Date view	Thread view	Subject view	Author view

Subject: [Boost-commit] svn:boost r77507 - sandbox/gtl/doc
From: sydorchuk.andriy_at_[hidden]
Date: 2012-03-23 15:47:24

Next message: sydorchuk.andriy_at_[hidden]: "[Boost-commit] svn:boost r77508 - sandbox/gtl/doc"
Previous message: jewillco_at_[hidden]: "[Boost-commit] svn:boost r77506 - in trunk: boost/property_map libs/property_map/doc libs/property_map/test"

Author: asydorchuk
Date: 2012-03-23 15:47:23 EDT (Fri, 23 Mar 2012)
New Revision: 77507
URL: http://svn.boost.org/trac/boost/changeset/77507

Log:
Updating voronoi documentation. Finished voronoi main page.

Text files modified:
   sandbox/gtl/doc/voronoi_diagram.htm | 75 ++++++++++++++++++++++++++-------------
   sandbox/gtl/doc/voronoi_main.htm | 62 ++++++++++++++++++++++++++++----
   2 files changed, 103 insertions(+), 34 deletions(-)

Modified: sandbox/gtl/doc/voronoi_diagram.htm
==============================================================================
--- sandbox/gtl/doc/voronoi_diagram.htm (original)
+++ sandbox/gtl/doc/voronoi_diagram.htm 2012-03-23 15:47:23 EDT (Fri, 23 Mar 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>

@@ -98,20 +99,22 @@
 <td style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;" valign="top" width="100%">
 
 
- <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. Boost.Polygon provides implementation of
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
+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 dimensonal 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
-voronoi vertices in red, voronoi edges in black, input sites that
-correspond to the voroni cells in blue (it is considered that each
+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). 
 
@@ -126,44 +129,44 @@
 <table style="text-align: left; width: 100%;" border="1" cellpadding="2" cellspacing="2">
 <tbody>
 <tr>
- <td style="vertical-align: top;">voronoi_diagram() 
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">voronoi_diagram() 
 </td>
 <td style="vertical-align: top;">Default constructor. 
 </td>
 </tr>
 <tr>
- <td style="vertical-align: top;">void clear() 
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">void clear() 
 </td>
 <td style="vertical-align: top;">Clears diagram. 
 </td>
 </tr>
 <tr>
- <td style="vertical-align: top;">const cell_container_type &cells() const 
+ <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>
 </tr>
 <tr>
- <td style="vertical-align: top;">const vertex_container_type &vertices() const 
+ <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>
 </tr>
 <tr>
- <td style="vertical-align: top;">const edge_container_type &edges() const 
+ <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>
 </tr>
 <tr>
- <td style="vertical-align: top;">unsigned int num_cells() const 
+ <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>
 </tr>
 <tr>
- <td style="vertical-align: top;">unsigned int num_edges() const 
+ <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. 
@@ -171,7 +174,7 @@
 </td>
 </tr>
 <tr>
- <td style="vertical-align: top;">unsigned int num_vertices() const 
+ <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. 
@@ -197,19 +200,19 @@
 <tr>
 <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">voronoi_cell_type *cell() 
 </td>
- <td style="vertical-align: top;">Retruns pointer to the voronoi cell that edge belongs to. 
+ <td style="vertical-align: top;">Retruns 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 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 Voronoi cell pointer for the cell current edge belongs to. 
 </td>
 </tr>
 <tr>
@@ -273,14 +276,14 @@
 <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 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 const pointer to the CCW next edge within the corresponding Voronoi cell. 
Edges not necessarily share a common vertex. 
 </td>
 </tr>
@@ -293,14 +296,14 @@
 <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 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 const pointer to the CCW prev edge within the corresponding Voronoi cell. 
Edges not necessarily share a common vertex. 
 </td>
 </tr>
@@ -397,7 +400,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 Voronoi cell from the given point site and pointer to the one of boundary edges. 
 </td>
 </tr>
 <tr>
@@ -405,7 +408,7 @@
             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 Voronoi cell from the given segment site and pointer to one of boundary edges. 
 </td>
 </tr>
 <tr>
@@ -473,6 +476,14 @@
 All the above methods have O(1) complexity. The size of
the Voronoi cell structure is equal to: 2 * sizeof(void *) + 4 *
sizeof(coordinate_type). 
+ 
+Following code snipped effectively traverses Voronoi edges around the Voronoi cell: 
+ 
+ const voronoi_edge<double> *edge = cell->incident_edge(); 
+ do { 
+   edge = edge->next(); 
+   // Do smth. with edge. 
+ } 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
@@ -487,7 +498,7 @@
 <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 Voronoi vertex that corresponds to the give point and incident edge. 
 </td>
 </tr>
 <tr>
@@ -533,6 +544,18 @@
 
 All the above methods have O(1) complexity. The size of the Voronoi vertex structure is equal to: 2 * sizeof(void *) + 2 *
sizeof(coordinate_type). 
+ 
+Following code snipped effectively traverses Voronoi edges around the Voronoi vertex: 
+ 
+ const voronoi_edge<double> *edge = vertex->incident_edge(); 
+
+ do { 
+
+   edge = edge->next(); 
+
+   // Do smth. with edge. 
+
+ } while (edge != vertex->incident_edge()); 
 <h1>Voronoi Diagram Traits 
 </h1>

@@ -549,7 +572,7 @@
 <tr>
 <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">coordinate_type 
 </td>
- <td style="vertical-align: top;">The main coordinate type of the voronoi diagram internal structures. 
+ <td style="vertical-align: top;">The main coordinate type of the Voronoi diagram internal structures. 
 </td>
 </tr>
 <tr>
@@ -587,7 +610,7 @@
 <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">vertex_equality_predicate_type 
 </td>
 <td style="vertical-align: top;">Predicate that returns true if two points are considered to be equal. 
-This is used to unite nearby voronoi vertices. 
+This is used to unite nearby Voronoi vertices. 
 </td>
 </tr>
 </tbody>

Modified: sandbox/gtl/doc/voronoi_main.htm
==============================================================================
--- sandbox/gtl/doc/voronoi_main.htm (original)
+++ sandbox/gtl/doc/voronoi_main.htm 2012-03-23 15:47:23 EDT (Fri, 23 Mar 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>

@@ -133,13 +134,13 @@
exact, but we developed relative error arithmetic apparatus to identify them and switch to higher precision predicates when required. 
 <h1>Precision of output structures 
 </h1>
-
One of the extremely important results of using two types of predicates
is that library efficiently computes relatively precise coordinates of
-the output geometries. Here we will explain a bit what exactly
+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
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
bits of mantissa), while in many cases it is slightly less. That also
@@ -153,7 +154,8 @@
[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]. 
+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
machine epsilons and removes any voronoi edges between them. That is
@@ -168,8 +170,7 @@
and equal to 2^-64 * 2^42 * 2^6 = 2^-18. In the output we are going to
consider vertices with both coordinates that are within 2^-17 meters (8
micrometers) distance to be equal. Come on that distance is equal to
-the size of bacteria. Can you even see those? I hope such overview
-convinced most pessimistic readers to give a try to our library. 
+the size of bacteria. Can you even see those? 
 <h1>Fully functional with segment inputs</h1>
There are not many implementations of Voronoi diagrams that could
handle segment inputs, even considering commercial ones. Support of
@@ -180,7 +181,52 @@
medial axis transform of the arbitrary input geometry. So one may start
using it for the next generation pattern recognition or computer vision
project. 
- <h1>Basic and advanced usage cases</h1>
+ <h1>Basic and advanced usage cases</h1>The main library header voronoi.hpp defines following static functions: 
+ 
+ <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;">template <typename PC, typename VD> 
+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. 
+PC is a container of points that supports forward iterator. 
+ </td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">template <typename SC, typename VD> 
+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. 
+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>
+ </tr>
+ <tr>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">template <typename PC, typename SC, typename VD> 
+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>
+ </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
+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. 
+
 <h1>Extendable for user provided coordinate types</h1>
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 requied neither
@@ -209,12 +255,12 @@
constructed in O(N) time.</li>
 <li>Dropping restriction on non-intersecting input geometries. 
Note: this means that library will also compute segment intersections if such exist.</li>
- <li>Closer integration with interfaces and functionality of Boost Polygon. 
+ <li>Closer integration with interfaces and functionality of Boost Polygon Library. 
 </li>
 </ul>
High-priority tasks to be considered: 
 <ul>
- <li>Integration of Voronoi diagram structure with BGL library.</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>

Next message: sydorchuk.andriy_at_[hidden]: "[Boost-commit] svn:boost r77508 - sandbox/gtl/doc"
Previous message: jewillco_at_[hidden]: "[Boost-commit] svn:boost r77506 - in trunk: boost/property_map libs/property_map/doc libs/property_map/test"

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