Boost-Commit :

Date view	Thread view	Subject view	Author view

Subject: [Boost-commit] svn:boost r80482 - in trunk: boost/polygon libs/polygon/doc libs/polygon/example libs/polygon/test
From: sydorchuk.andriy_at_[hidden]
Date: 2012-09-10 16:39:17

Next message: guwi17_at_[hidden]: "[Boost-commit] svn:boost r80483 - in trunk: boost/numeric/ublas libs/numeric/ublas/test"
Previous message: sydorchuk.andriy_at_[hidden]: "[Boost-commit] svn:boost r80481 - trunk/libs/polygon/doc"

Author: asydorchuk
Date: 2012-09-10 16:39:16 EDT (Mon, 10 Sep 2012)
New Revision: 80482
URL: http://svn.boost.org/trac/boost/changeset/80482

Log:
Polygon: Updating Voronoi diagram page documentation. Updating Voronoi basic tutorial.

Text files modified:
   trunk/boost/polygon/voronoi_diagram.hpp | 10
   trunk/boost/polygon/voronoi_geometry_type.hpp | 4
   trunk/libs/polygon/doc/voronoi_basic_tutorial.htm | 46 +++++
   trunk/libs/polygon/doc/voronoi_diagram.htm | 306 ++++++++++++++++++++-------------------
   trunk/libs/polygon/example/voronoi_basic_tutorial.cpp | 35 ++++
   trunk/libs/polygon/test/voronoi_builder_test.cpp | 30 +-
   trunk/libs/polygon/test/voronoi_diagram_test.cpp | 1
   7 files changed, 255 insertions(+), 177 deletions(-)

Modified: trunk/boost/polygon/voronoi_diagram.hpp
==============================================================================
--- trunk/boost/polygon/voronoi_diagram.hpp (original)
+++ trunk/boost/polygon/voronoi_diagram.hpp 2012-09-10 16:39:16 EDT (Mon, 10 Sep 2012)
@@ -75,7 +75,7 @@
 void incident_edge(voronoi_edge_type* e) { incident_edge_ = e; }

 color_type color() const { return color_ >> BITS_SHIFT; }
- void color(const color_type& color) const {
+ void color(color_type color) const {
 color_ &= BITS_MASK;
 color_ |= color << BITS_SHIFT;
 }
@@ -122,7 +122,7 @@
 void incident_edge(voronoi_edge_type* e) { incident_edge_ = e; }

 color_type color() const { return color_ >> BITS_SHIFT; }
- void color(const color_type& color) const {
+ void color(color_type color) const {
 color_ &= BITS_MASK;
 color_ |= color << BITS_SHIFT;
 }
@@ -246,7 +246,7 @@
 }

 color_type color() const { return color_ >> BITS_SHIFT; }
- void color(const color_type& color) const {
+ void color(color_type color) const {
 color_ &= BITS_MASK;
 color_ |= color << BITS_SHIFT;
 }
@@ -336,10 +336,6 @@
 }

 std::size_t num_edges() const {
- return edges_.size() >> 1;
- }
-
- std::size_t num_half_edges() const {
 return edges_.size();
 }

Modified: trunk/boost/polygon/voronoi_geometry_type.hpp
==============================================================================
--- trunk/boost/polygon/voronoi_geometry_type.hpp (original)
+++ trunk/boost/polygon/voronoi_geometry_type.hpp 2012-09-10 16:39:16 EDT (Mon, 10 Sep 2012)
@@ -34,8 +34,8 @@
};

bool belongs(
- const SourceCategory& source_category,
- const GeometryCategory& geometry_category) {
+ SourceCategory source_category,
+ GeometryCategory geometry_category) {
 return (static_cast<std::size_t>(source_category) >>
 SOURCE_CATEGORY_GEOMETRY_SHIFT) ==
 static_cast<std::size_t>(geometry_category);

Modified: trunk/libs/polygon/doc/voronoi_basic_tutorial.htm
==============================================================================
--- trunk/libs/polygon/doc/voronoi_basic_tutorial.htm (original)
+++ trunk/libs/polygon/doc/voronoi_basic_tutorial.htm 2012-09-10 16:39:16 EDT (Mon, 10 Sep 2012)
@@ -10,6 +10,7 @@

+

 <meta http-equiv="Content-Type" content="text/html; charset=windows-1252"><title>Voronoi Basic Tutorial</title><meta http-equiv="content-type" content="text/html; charset=utf-8"></head><body>
<h1>Voronoi Basic Tutorial 
@@ -30,6 +31,10 @@
 </li>

 <li>associating the user data with the Voronoi primitives</li>
+ <li>accessing input site inside the Voronoi cell</li>
+ <li>Voronoi diagram rendering 
+ </li>
+

</ul>

@@ -236,7 +241,46 @@
  printf("\n"); 
} 

-<h2>Rendering Voronoi Diagram</h2>
+<h2>Accessing Input Site inside the Voronoi Cell</h2>
+As explained in the Voronoi diagram
+section, Voronoi cells don't contain coordinates of the input
+geometries directly. Instead they contains source index and source
+category that uniquely identify input site. The below routines
+traverses over the all Voronoi cells, fetches input geometry
+corresponding to the Voronoi cell and prints coordinates of the input
+site. 
+ 
+unsigned int cell_index = 0; 
+for (voronoi_diagram<double>::const_cell_iterator it = vd.cells().begin(); 
+     it != vd.cells().end(); ++it) { 
+  if (it->contains_point()) { 
+    std::size_t index = it->source_index(); 
+    Point p = points[index]; 
+    printf("Cell #%ud contains a point: (%d, %d).\n", 
+           cell_index, x(p), y(p)); 
+  } else { 
+    std::size_t index = it->source_index() - points.size(); 
+    Point p0 = low(segments[index]); 
+    Point p1 = high(segments[index]); 
+    if (it->source_category() == 
+        boost::polygon::SOURCE_CATEGORY_SEGMENT_START_POINT) { 
+      printf("Cell #%ud contains segment start point: (%d, %d).\n", 
+             cell_index, x(p0), y(p0)); 
+    } else if (it->source_category() == 
+              
+boost::polygon::SOURCE_CATEGORY_SEGMENT_END_POINT) { 
+      printf("Cell #%ud contains segment end point: (%d, %d).\n", 
+             cell_index, x(p0), y(p0)); 
+    } else { 
+      printf("Cell #%ud contains a segment: ((%d, %d), (%d, %d)). \n", 
+             cell_index, x(p0), y(p0), x(p1), y(p1)); 
+    } 
+  } 
+  ++cell_index; 
+} 
+<h2>Voronoi Diagram Rendering 
+</h2>
+

There are two main issues that don't allow to strictly render the resulting
Voronoi diagram using such rendering tools as OpenGL or DirectX.

Modified: trunk/libs/polygon/doc/voronoi_diagram.htm
==============================================================================
--- trunk/libs/polygon/doc/voronoi_diagram.htm (original)
+++ trunk/libs/polygon/doc/voronoi_diagram.htm 2012-09-10 16:39:16 EDT (Mon, 10 Sep 2012)
@@ -9,6 +9,7 @@

+

 <meta http-equiv="Content-Language" content="en-us">

@@ -93,14 +94,14 @@
 <td style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;" valign="top" width="100%"> 

 <h1>Voronoi Diagram</h1>
-A Voronoi
+Voronoi
diagram is the computational geometry concept that represents partition
of the given space onto regions, with bounds determined by distances to a
specified family of objects. The application area of this concept vary <a href="http://www.ics.uci.edu/%7Eeppstein/gina/scot.drysdale.html">from
Archaeology to Zoology</a>. The Boost.Polygon library provides implementation of
the Voronoi diagram data structure in 2D space. The internal representation
consists of the three arrays, that respectively contain: Voronoi cells
-(represents the area around input site bounded by the Voronoi edges), Voronoi vertices
+(represent the area around the input sites bounded by the Voronoi edges), Voronoi vertices
(points where three or more Voronoi edges intersect), Voronoi edges
(the one dimensional curves containing points equidistant from the two
closest input sites). Each of the primitives (cell, vertex, edge)
@@ -113,11 +114,14 @@
Voronoi edges are constructed per each input segment. This is made to
simplify the representation of the Voronoi diagram. 
 
+
+
 <img style="border: 1px solid ; width: 300px; height: 300px;" alt="" src="images/voronoi2.png"> 
 <h2>Declaration 
 </h2>

+

 template
<typename T, typename TRAITS = voronoi_diagram_traits<T> > 
@@ -125,7 +129,7 @@
voronoi_diagram; 
 
T
-- specifies the coordinate type of the output geometries: input sites (points / segments), Voronoi vertices. 
+- specifies the coordinate type of the Voronoi vertices. 
 TRAITS
- Voronoi diagram traits (explained in the end of this chapter). 
 <h2>Member Functions</h2>
@@ -150,7 +154,7 @@
 </tr>
 <tr>
 <td style="font-family: Courier New,Courier,monospace;">const
-cell_container_type &cells() const 
+cell_container_type& cells() const 
 </td>
 <td>Returns the const
reference to the cell container. 
@@ -158,7 +162,7 @@
 </tr>
 <tr>
 <td style="font-family: Courier New,Courier,monospace;">const
-vertex_container_type &vertices() const 
+vertex_container_type& vertices() const 
 </td>
 <td>Returns the const
reference to the vertex container. 
@@ -166,15 +170,14 @@
 </tr>
 <tr>
 <td style="font-family: Courier New,Courier,monospace;">const
-edge_container_type &edges() const 
+edge_container_type& edges() const 
 </td>
 <td>Returns the const
reference to the edge container. 
 </td>
 </tr>
 <tr>
- <td style="font-family: Courier New,Courier,monospace;">unsigned
-int num_cells() const 
+ <td style="font-family: Courier New,Courier,monospace;">std::size_t num_cells() const 
 </td>
 <td>Returns the number of the
cells in the Voronoi diagram. 
@@ -182,18 +185,14 @@
 </td>
 </tr>
 <tr>
- <td style="font-family: Courier New,Courier,monospace;">unsigned
-int num_edges() const 
+ <td style="font-family: Courier New,Courier,monospace;">std::size_t num_edges() const 
 </td>
 <td>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. 
+edges (half-edges) in the Voronoi diagram. This value should be the same as the size of the edge container. 
 </td>
 </tr>
 <tr>
- <td style="font-family: Courier New,Courier,monospace;">unsigned
-int num_vertices() const 
+ <td style="font-family: Courier New,Courier,monospace;">std::size_t num_vertices() const 
 </td>
 <td>Returns the number of the
vertices in the Voronoi diagram. 
@@ -212,12 +211,7 @@
 <td>Coordinate type. 
 </td>
 </tr>
- <tr>
- <td>point_type 
- </td>
- <td>2D point. 
- </td>
- </tr>
+
 <tr>
 <td>cell_type 
 </td>
@@ -294,9 +288,62 @@
 </table>

+
+ <h1>Voronoi Geometry Type 
+ </h1>
+ <h2>GeometryCategory 
+ </h2>
+Defines geometry type of the input objects. 
+ 
+ enum GeometryCategory { 
+   GEOMETRY_CATEGORY_POINT = 0x0, 
+   GEOMETRY_CATEGORY_SEGMENT = 0x1 
+ }; 
+ <h2>SourceCategory</h2>
+
+Defines category of the input site that forms Voronoi cell. 
+ 
+ enum SourceCategory { 
+   // Point subtypes. 
+   SOURCE_CATEGORY_SINGLE_POINT = 0x0, 
+   SOURCE_CATEGORY_SEGMENT_START_POINT = 0x1, 
+   SOURCE_CATEGORY_SEGMENT_END_POINT = 0x2, 
+ 
+   // Segment subtypes. 
+   SOURCE_CATEGORY_INITIAL_SEGMENT = 0x8, 
+   SOURCE_CATEGORY_REVERSE_SEGMENT = 0x9, 
+ 
+   SOURCE_CATEGORY_GEOMETRY_SHIFT = 0x3, 
+   SOURCE_CATEGORY_BITMASK = 0x1F 
+ }; 
+ 
+Voronoi
+diagram data structure doesn't store coordinates of the input
+geometries.
+Instead it links with those via source index and source category method
+of the Voronoi cell primitive. Source index is incrementally given
+(starting from zero) to each input site inserted into Voronoi builder.
+Considering the fact that each input segment is splitted onto three
+separate sites with the same index, we distinguish between them using
+SourceCategory. For the example see Voronoi basic tutorial. 
+ <h2>Member Functions</h2>
+ <table style="text-align: left; width: 100%;" border="1" cellpadding="2" cellspacing="2">
+ <tbody>
+ <tr>
+ <td style="vertical-align: top;">bool belongs( 
+     SourceCategory source_category, 
+     GeometryCategory geometry_category) 
+ </td>
+ <td style="vertical-align: middle;">Returns true if source category belongs to the given geometry category. 
+Returns false else. 
+ </td>
+ </tr>
+ </tbody>
+ </table>
 <h1>Voronoi Edge</h1>

-Voronoi edge is represented as a bit improved classical half-edge
+
+Voronoi edge is represented as enhanced classical half-edge
data structure. 
 <h2>Declaration</h2>

@@ -307,7 +354,7 @@
 class
voronoi_edge; 
 
-T - coordinate type. While Voronoi edge doesn't contain coordinates itself, it stores pointers to the Voronoi cell and vertex. 
+T - coordinate type. 
 <h2>Member Functions</h2>

 
@@ -315,15 +362,9 @@
 
 <table style="text-align: left; width: 100%;" border="1" cellpadding="2" cellspacing="2">
 <tbody>
+
 <tr>
- <td style="font-family: Courier New,Courier,monospace;">voronoi_edge() 
- </td>
- <td>Default constructor. 
- </td>
- </tr>
- <tr>
- <td style="font-family: Courier New,Courier,monospace;">voronoi_cell_type
-*cell() 
+ <td style="font-family: Courier New,Courier,monospace;">voronoi_cell_type* cell() 
 </td>
 <td>Returns the pointer to the
Voronoi cell
@@ -332,7 +373,7 @@
 </tr>
 <tr>
 <td style="font-family: Courier New,Courier,monospace;">const
-voronoi_cell_type *cell() const 
+voronoi_cell_type* cell() const 
 </td>
 <td>Returns the const pointer
to the Voronoi cell that edge belongs to. 
@@ -340,15 +381,14 @@
 </tr>
 <tr>
 <td style="font-family: Courier New,Courier,monospace;">void
-cell(voronoi_cell_type *c) 
+cell(voronoi_cell_type* c) 
 </td>
 <td>Sets the Voronoi cell
pointer for the cell current edge belongs to. 
 </td>
 </tr>
 <tr>
- <td style="font-family: Courier New,Courier,monospace;">voronoi_vertex_type
-*vertex0() 
+ <td style="font-family: Courier New,Courier,monospace;">voronoi_vertex_type* vertex0() 
 </td>
 <td>Returns the pointer to the
start point of the edge. 
@@ -357,7 +397,7 @@
 </tr>
 <tr>
 <td style="font-family: Courier New,Courier,monospace;">const
-voronoi_vertex_type *vertex0() const 
+voronoi_vertex_type* vertex0() const 
 </td>
 <td>Returns the const pointer
to the point vertex of the edge. 
@@ -366,15 +406,14 @@
 </tr>
 <tr>
 <td style="font-family: Courier New,Courier,monospace;">void
-vertex0(voronoi_vertex_type *v) 
+vertex0(voronoi_vertex_type* v) 
 </td>
 <td>Sets the start point
pointer of the edge. 
 </td>
 </tr>
 <tr>
- <td style="font-family: Courier New,Courier,monospace;">voronoi_vertex_type
-*vertex1() 
+ <td style="font-family: Courier New,Courier,monospace;">voronoi_vertex_type* vertex1() 
 </td>
 <td>Returns the pointer to the
end point of the edge. 
@@ -383,7 +422,7 @@
 </tr>
 <tr>
 <td style="font-family: Courier New,Courier,monospace;">const
-voronoi_vertex_type *vertex1() const 
+voronoi_vertex_type* vertex1() const 
 </td>
 <td>Returns the const pointer
to the end point of the edge. 
@@ -392,15 +431,14 @@
 </tr>
 <tr>
 <td style="font-family: Courier New,Courier,monospace;">void
-vertex1(voronoi_vertex_type *v) 
+vertex1(voronoi_vertex_type* v) 
 </td>
 <td>Sets the end point pointer
of the edge. 
 </td>
 </tr>
 <tr>
- <td style="font-family: Courier New,Courier,monospace;">voronoi_edge_type
-*twin() 
+ <td style="font-family: Courier New,Courier,monospace;">voronoi_edge_type* twin() 
 </td>
 <td>Returns the pointer to the
twin edge. 
@@ -408,7 +446,7 @@
 </tr>
 <tr>
 <td style="font-family: Courier New,Courier,monospace;">const
-voronoi_edge_type *twin() const 
+voronoi_edge_type* twin() const 
 </td>
 <td>Returns the const pointer
to the twin edge. 
@@ -416,15 +454,14 @@
 </tr>
 <tr>
 <td style="font-family: Courier New,Courier,monospace;">void
-twin(voronoi_edge_type *e) 
+twin(voronoi_edge_type* e) 
 </td>
 <td>Sets the twin edge pointer
of the edge. 
 </td>
 </tr>
 <tr>
- <td style="font-family: Courier New,Courier,monospace;">voronoi_edge_type
-*next() 
+ <td style="font-family: Courier New,Courier,monospace;">voronoi_edge_type* next() 
 </td>
 <td>Returns the pointer to the
CCW next edge within the corresponding Voronoi cell. 
@@ -433,7 +470,7 @@
 </tr>
 <tr>
 <td style="font-family: Courier New,Courier,monospace;">const
-voronoi_edge_type *next() const 
+voronoi_edge_type* next() const 
 </td>
 <td>Returns the const pointer
to the CCW next edge within the corresponding Voronoi cell. 
@@ -442,15 +479,14 @@
 </tr>
 <tr>
 <td style="font-family: Courier New,Courier,monospace;">void
-next(voronoi_edge_type *e) 
+next(voronoi_edge_type* e) 
 </td>
 <td>Sets the CCW next edge
pointer of the edge. 
 </td>
 </tr>
 <tr>
- <td style="font-family: Courier New,Courier,monospace;">voronoi_edge_type
-*prev() 
+ <td style="font-family: Courier New,Courier,monospace;">voronoi_edge_type* prev() 
 </td>
 <td>Returns the pointer to the
CCW prev edge within the corresponding Voronoi cell. 
@@ -459,7 +495,7 @@
 </tr>
 <tr>
 <td style="font-family: Courier New,Courier,monospace;">const
-voronoi_edge_type *prev() const 
+voronoi_edge_type* prev() const 
 </td>
 <td>Returns the const pointer
to the CCW prev edge within the corresponding Voronoi cell. 
@@ -468,60 +504,53 @@
 </tr>
 <tr>
 <td style="font-family: Courier New,Courier,monospace;">void
-prev(voronoi_edge_type *e) 
+prev(voronoi_edge_type* e) 
 </td>
 <td>Sets the CCW prev edge
pointer of the edge. 
 </td>
 </tr>
 <tr>
- <td style="font-family: Courier New,Courier,monospace;">size_t color() const 
+ <td style="font-family: Courier New,Courier,monospace;">color_type color() const 
 </td>
 <td>Returns the color value. 
 </td>
 </tr>
 <tr>
- <td style="font-family: Courier New,Courier,monospace;">void
-data(size_t color) const 
+ <td style="font-family: Courier New,Courier,monospace;">void color(color_type color) const 
 </td>
 <td>Sets the color of
the edge. 
-Allows to execut graph algorithms and associate data. 
+Allows to execute graph algorithms and associate data. 
 </td>
 </tr>
 <tr>
- <td style="font-family: Courier New,Courier,monospace;">voronoi_edge_type
-*rot_next() 
+ <td style="font-family: Courier New,Courier,monospace;">voronoi_edge_type* rot_next() 
 </td>
 <td>Returns the pointer to the
-CCW next edge rotated around the edge start point. 
-If the edge is infinite in that direction returns NULL. 
+CCW next edge rotated around the edge start point. Works for infinite edges as weel. 
 </td>
 </tr>
 <tr>
 <td style="font-family: Courier New,Courier,monospace;">const
-voronoi_edge_type *rot_next() const 
+voronoi_edge_type* rot_next() const 
 </td>
 <td>Returns the const pointer
-to the CCW next edge rotated around the edge start point. 
-If the edge is infinite in that direction returns NULL.</td>
+to the CCW next edge rotated around the edge start point. Works for infinite edges as weel.</td>
 </tr>
 <tr>
- <td style="font-family: Courier New,Courier,monospace;">voronoi_edge_type
-*rot_prev() 
+ <td style="font-family: Courier New,Courier,monospace;">voronoi_edge_type* rot_prev() 
 </td>
 <td>Returns the pointer to the
-CCW prev edge rotated around the edge start point. 
-If the edge is infinite in that direction returns NULL. 
+CCW prev edge rotated around the edge start point. Works for infinite edges as weel. 
 </td>
 </tr>
 <tr>
 <td style="font-family: Courier New,Courier,monospace;">const
-voronoi_edge_type *rot_prev() const 
+voronoi_edge_type* rot_prev() const 
 </td>
 <td>Returns the const pointer
-to the CCW prev edge rotated around the edge start point. 
-If the edge is infinite in that direction returns NULL.</td>
+to the CCW prev edge rotated around the edge start point. Works for infinite edges as weel.</td>
 </tr>
 <tr>
 <td style="font-family: Courier New,Courier,monospace;">bool
@@ -532,6 +561,12 @@
 </td>
 </tr>
 <tr>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">bool
+is_infinite() const</td>
+ <td style="vertical-align: top;">Returns true if one of the
+end points of the edge is infinite, else false.</td>
+ </tr>
+<tr>
 <td style="font-family: Courier New,Courier,monospace;">bool
is_linear() const 
 </td>
@@ -554,7 +589,13 @@
 <td>Returns false if the edge
goes through the endpoint of the segment site, else true. 
 </td>
+ </tr><tr>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">bool
+is_secondary() const</td>
+ <td style="vertical-align: top;">Returns true if the edge
+goes through the endpoint of the segment site, else false.</td>
 </tr>
+
 </tbody>
 </table>
 
@@ -617,51 +658,25 @@
 
 <table style="text-align: left; width: 100%;" border="1" cellpadding="2" cellspacing="2">
 <tbody>
+
+
 <tr>
- <td style="font-family: Courier New,Courier,monospace;">voronoi_cell(const
-point_type &p1, 
-            
-voronoi_edge_type *edge) 
+ <td style="font-family: Courier New,Courier,monospace;">source_index_type source_index() const 
 </td>
- <td>Constructs the Voronoi
-cell from the given point site and pointer to the one of the boundary
-edges. 
+ <td>Returns input site index among the other sites. 
+Both segment endpoints and segment itself will have the same index. 
 </td>
 </tr>
 <tr>
- <td style="font-family: Courier New,Courier,monospace;">voronoi_cell(const
-point_type &p1, 
-            
-const point_type &p2, 
-            
-voronoi_edge_type *edge) 
- </td>
- <td>Constructs the Voronoi
-cell from the given segment site and pointer to the one of the boundary
-edges. 
- </td>
- </tr>
- <tr>
- <td style="font-family: Courier New,Courier,monospace;">const
-point_type &point0() const 
- </td>
- <td>If the cell contains point
-site returns it. 
-If the cell contains segment site returns its first endpoint. 
+ <td style="font-family: Courier New,Courier,monospace;">source_index_type source_category() const 
 </td>
- </tr>
- <tr>
- <td style="font-family: Courier New,Courier,monospace;">const
-point_type &point1() const 
- </td>
- <td>If the cell contains point
-site returns it. 
-If the cell contains segment site returns its second endpoint. 
+ <td>Retruns input site category among the other sites. 
+Allows to distinguish between segment site and its endpoints. 
+
 </td>
 </tr>
 <tr>
- <td style="font-family: Courier New,Courier,monospace;">voronoi_edge_type
-*incident_edge() 
+ <td style="font-family: Courier New,Courier,monospace;">voronoi_edge_type* incident_edge() 
 </td>
 <td>Returns the pointer to the
one of the boundary edges. 
@@ -669,7 +684,7 @@
 </tr>
 <tr>
 <td style="font-family: Courier New,Courier,monospace;">const
-voronoi_edge_type *incident_edge() const 
+voronoi_edge_type* incident_edge() const 
 </td>
 <td>Returns the const pointer
to the one of the boundary edges. 
@@ -677,24 +692,24 @@
 </tr>
 <tr>
 <td style="font-family: Courier New,Courier,monospace;">void
-incident_edge(voronoi_edge_type *e) 
+incident_edge(voronoi_edge_type* e) 
 </td>
 <td>Sets the incident boundary
edge pointer of the cell. 
 </td>
 </tr>
 <tr>
- <td style="font-family: Courier New,Courier,monospace;">size_t color() const 
+ <td style="font-family: Courier New,Courier,monospace;">color_type color() const 
 </td>
 <td>Returns the color associated with the cell.</td>
 </tr>
 <tr>
- <td style="font-family: Courier New,Courier,monospace;">void color(size_t color) const 
+ <td style="font-family: Courier New,Courier,monospace;">void color(color_type color) const 
 </td>
 <td>Sets the color of
the cell. 

-Allows to execut graph algorithms and associate data. 
+Allows to execute graph algorithms and associate data. 
</td>
 </tr>
 <tr>
@@ -720,7 +735,7 @@
 </table>
 
 All the above methods have O(1) complexity. The size of
-the Voronoi cell structure is equal to: sizeof(void *) + sizeof(size_t) + 4 * sizeof(coordinate_type).
+the Voronoi cell structure is equal to: sizeof(void *) + 2 * sizeof(size_t).
 <h2>Member Types</h2>

@@ -734,11 +749,17 @@
 </td>
 </tr>
 <tr>
- <td>point_type</td>
- <td>Point type. 
+ <td>source_index_type</td>
+ <td>Source index type. 
 </td>
 </tr>
 <tr>
+ <td style="vertical-align: top;">source_category_type 
+ </td>
+ <td style="vertical-align: top;">Source category type. 
+ </td>
+ </tr>
+<tr>
 <td style="vertical-align: top;">color_type 
 </td>
 <td style="vertical-align: top;">Color type. 
@@ -758,7 +779,7 @@
Voronoi cell: 
 
 const
-voronoi_edge<double> *edge = cell->incident_edge(); 
+voronoi_edge<double>* edge = cell->incident_edge(); 
 do { 
  
edge = edge->next(); 
@@ -786,26 +807,22 @@
 
 <table style="text-align: left; width: 100%;" border="1" cellpadding="2" cellspacing="2">
 <tbody>
+
 <tr>
- <td style="font-family: Courier New,Courier,monospace;">voronoi_vertex(const
-point_type &vertex, 
-               voronoi_edge_type *edge) 
+ <td style="font-family: Courier New,Courier,monospace;">const
+point_type& x() const 
 </td>
- <td>Constructs the Voronoi
-vertex that corresponds to the give point and incident edge. 
+ <td>Returns the x-coordinate of the point that represents the vertex. 
 </td>
 </tr>
 <tr>
- <td style="font-family: Courier New,Courier,monospace;">const
-point_type &vertex() const 
- </td>
- <td>Returns the point that
-represents vertex. 
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">const
+point_type& y() const</td>
+ <td style="vertical-align: top;">Returns the y-coordinate of the point that represents the vertex. 
 </td>
 </tr>
- <tr>
- <td style="font-family: Courier New,Courier,monospace;">voronoi_edge_type
-*incident_edge() 
+<tr>
+ <td style="font-family: Courier New,Courier,monospace;">voronoi_edge_type* incident_edge() 
 </td>
 <td>Returns the incident edge
pointer. 
@@ -813,7 +830,7 @@
 </tr>
 <tr>
 <td style="font-family: Courier New,Courier,monospace;">const
-voronoi_edge_type *incident_edge() const 
+voronoi_edge_type* incident_edge() const 
 </td>
 <td>Returns the const pointer
to the incident edge. 
@@ -821,23 +838,23 @@
 </tr>
 <tr>
 <td style="font-family: Courier New,Courier,monospace;">void
-incident_edge(voronoi_edge_type *e) 
+incident_edge(voronoi_edge_type* e) 
 </td>
 <td>Sets the incident edge
pointer. 
 </td>
 </tr>
 <tr>
- <td style="font-family: Courier New,Courier,monospace;">size_t color() const 
+ <td style="font-family: Courier New,Courier,monospace;">color_type color() const 
 </td>
 <td>Returns the color associated with the vertex.</td>
 </tr>
 <tr>
- <td style="font-family: Courier New,Courier,monospace;">void color(size_t color) const 
+ <td style="font-family: Courier New,Courier,monospace;">void color(color_type color) const 
 </td>
 <td>Sets the color of
-the cell. 
-Allows to execut graph algorithms and associate data.</td>
+the vertex. 
+Allows to executegraph algorithms and associate data.</td>
 </tr>
 </tbody>
 </table>
@@ -854,12 +871,7 @@
 <td>Coordainte type. 
 </td>
 </tr>
- <tr>
- <td>point_type 
- </td>
- <td>Point type. 
- </td>
- </tr>
+
 <tr>
 <td style="vertical-align: top;">color_type 
 </td>
@@ -879,7 +891,7 @@
Voronoi vertex: 
 
 const
-voronoi_edge<double> *edge = vertex->incident_edge(); 
+voronoi_edge<double>* edge = vertex->incident_edge(); 
 do { 
  
edge = edge->next(); 
@@ -916,15 +928,7 @@
of the Voronoi diagram primitives. 
 </td>
 </tr>
- <tr>
- <td style="font-family: Courier New,Courier,monospace;">ctype_converter_type 
- </td>
- <td>Coordinate type converter
-structure. 
-Converts coordinates provided by the Voronoi builder to the
-internal coordinate type. 
- </td>
- </tr>
+
 <tr>
 <td style="font-family: Courier New,Courier,monospace;">point_type 
 </td>

Modified: trunk/libs/polygon/example/voronoi_basic_tutorial.cpp
==============================================================================
--- trunk/libs/polygon/example/voronoi_basic_tutorial.cpp (original)
+++ trunk/libs/polygon/example/voronoi_basic_tutorial.cpp 2012-09-10 16:39:16 EDT (Mon, 10 Sep 2012)
@@ -13,6 +13,10 @@
#include <boost/polygon/voronoi.hpp>
using boost::polygon::voronoi_builder;
using boost::polygon::voronoi_diagram;
+using boost::polygon::x;
+using boost::polygon::y;
+using boost::polygon::low;
+using boost::polygon::high;

#include "voronoi_visual_utils.hpp"

@@ -154,5 +158,36 @@
 printf("\n");
 printf("\n");
 }
+
+ // Linking Voronoi cells with input geometries.
+ {
+ unsigned int cell_index = 0;
+ for (voronoi_diagram<double>::const_cell_iterator it = vd.cells().begin();
+ it != vd.cells().end(); ++it) {
+ if (it->contains_point()) {
+ std::size_t index = it->source_index();
+ Point p = points[index];
+ printf("Cell #%ud contains a point: (%d, %d).\n",
+ cell_index, x(p), y(p));
+ } else {
+ std::size_t index = it->source_index() - points.size();
+ Point p0 = low(segments[index]);
+ Point p1 = high(segments[index]);
+ if (it->source_category() ==
+ boost::polygon::SOURCE_CATEGORY_SEGMENT_START_POINT) {
+ printf("Cell #%ud contains segment start point: (%d, %d).\n",
+ cell_index, x(p0), y(p0));
+ } else if (it->source_category() ==
+ boost::polygon::SOURCE_CATEGORY_SEGMENT_END_POINT) {
+ printf("Cell #%ud contains segment end point: (%d, %d).\n",
+ cell_index, x(p0), y(p0));
+ } else {
+ printf("Cell #%ud contains a segment: ((%d, %d), (%d, %d)). \n",
+ cell_index, x(p0), y(p0), x(p1), y(p1));
+ }
+ }
+ ++cell_index;
+ }
+ }
 return 0;
}

Modified: trunk/libs/polygon/test/voronoi_builder_test.cpp
==============================================================================
--- trunk/libs/polygon/test/voronoi_builder_test.cpp (original)
+++ trunk/libs/polygon/test/voronoi_builder_test.cpp 2012-09-10 16:39:16 EDT (Mon, 10 Sep 2012)
@@ -70,7 +70,7 @@
 vd_type test_output;
 construct_voronoi(points.begin(), points.end(), &test_output);
 VERIFY_OUTPUT(test_output);
- CHECK_OUTPUT_SIZE(test_output, 2, 0, 1);
+ CHECK_OUTPUT_SIZE(test_output, 2, 0, 2);

 const_cell_iterator cell_it = test_output.cells().begin();
 cell_it++;
@@ -101,7 +101,7 @@
 vd_type test_output;
 construct_voronoi(points.begin(), points.end(), &test_output);
 VERIFY_OUTPUT(test_output);
- CHECK_OUTPUT_SIZE(test_output, 3, 0, 2);
+ CHECK_OUTPUT_SIZE(test_output, 3, 0, 4);

 const_cell_iterator cell_it = test_output.cells().begin();
 const voronoi_edge_type* edge1_1 = cell_it->incident_edge();
@@ -140,7 +140,7 @@
 vd_type test_output;
 construct_voronoi(points.begin(), points.end(), &test_output);
 VERIFY_OUTPUT(test_output);
- CHECK_OUTPUT_SIZE(test_output, 3, 1, 3);
+ CHECK_OUTPUT_SIZE(test_output, 3, 1, 6);

 const_vertex_iterator it = test_output.vertices().begin();
 BOOST_CHECK_EQUAL(it->x(), 0.25);
@@ -194,7 +194,7 @@
 vd_type test_output;
 construct_voronoi(points.begin(), points.end(), &test_output);
 VERIFY_OUTPUT(test_output);
- CHECK_OUTPUT_SIZE(test_output, 3, 1, 3);
+ CHECK_OUTPUT_SIZE(test_output, 3, 1, 6);

 const_vertex_iterator it = test_output.vertices().begin();
 BOOST_CHECK_EQUAL(it->x(), 1.75);
@@ -250,7 +250,7 @@
 vd_type test_output;
 construct_voronoi(points.begin(), points.end(), &test_output);
 VERIFY_OUTPUT(test_output);
- CHECK_OUTPUT_SIZE(test_output, 4, 1, 4);
+ CHECK_OUTPUT_SIZE(test_output, 4, 1, 8);

 // Check voronoi vertex.
 const_vertex_iterator it = test_output.vertices().begin();
@@ -329,7 +329,7 @@
 VERIFY_OUTPUT(test_output_large);
 unsigned int num_cells = grid_size[k] * grid_size[k];
 unsigned int num_vertices = num_cells - 2 * grid_size[k] + 1;
- unsigned int num_edges = 2 * num_cells - 2 * grid_size[k];
+ unsigned int num_edges = 4 * num_cells - 4 * grid_size[k];
 CHECK_OUTPUT_SIZE(test_output_small, num_cells, num_vertices, num_edges);
 CHECK_OUTPUT_SIZE(test_output_large, num_cells, num_vertices, num_edges);
 }
@@ -378,7 +378,7 @@
 point_data<T> point2(1, 1);
 segments.push_back(segment_data<T>(point1, point2));
 construct_voronoi(segments.begin(), segments.end(), &test_output);
- CHECK_OUTPUT_SIZE(test_output, 3, 0, 2);
+ CHECK_OUTPUT_SIZE(test_output, 3, 0, 4);
 VERIFY_NO_HALF_EDGE_INTERSECTIONS(test_output);
}

@@ -394,7 +394,7 @@
 points.push_back(point3);
 points.push_back(point4);
 construct_voronoi(points.begin(), points.end(), segments.begin(), segments.end(), &test_output);
- CHECK_OUTPUT_SIZE(test_output, 5, 4, 8);
+ CHECK_OUTPUT_SIZE(test_output, 5, 4, 16);
 VERIFY_NO_HALF_EDGE_INTERSECTIONS(test_output);
}

@@ -410,7 +410,7 @@
 points.push_back(point3);
 points.push_back(point4);
 construct_voronoi(points.begin(), points.end(), segments.begin(), segments.end(), &test_output);
- CHECK_OUTPUT_SIZE(test_output, 5, 4, 8);
+ CHECK_OUTPUT_SIZE(test_output, 5, 4, 16);
 VERIFY_NO_HALF_EDGE_INTERSECTIONS(test_output);
}

@@ -426,7 +426,7 @@
 points.push_back(point3);
 points.push_back(point4);
 construct_voronoi(points.begin(), points.end(), segments.begin(), segments.end(), &test_output);
- CHECK_OUTPUT_SIZE(test_output, 5, 3, 7);
+ CHECK_OUTPUT_SIZE(test_output, 5, 3, 14);
 VERIFY_NO_HALF_EDGE_INTERSECTIONS(test_output);
}

@@ -444,7 +444,7 @@
 points.push_back(point4);
 points.push_back(point5);
 construct_voronoi(points.begin(), points.end(), segments.begin(), segments.end(), &test_output);
- CHECK_OUTPUT_SIZE(test_output, 6, 4, 9);
+ CHECK_OUTPUT_SIZE(test_output, 6, 4, 18);
 VERIFY_NO_HALF_EDGE_INTERSECTIONS(test_output);
}

@@ -458,7 +458,7 @@
 segments.push_back(segment_data<T>(point2, point3));
 points.push_back(point1);
 construct_voronoi(points.begin(), points.end(), segments.begin(), segments.end(), &test_output);
- CHECK_OUTPUT_SIZE(test_output, 4, 2, 5);
+ CHECK_OUTPUT_SIZE(test_output, 4, 2, 10);
 VERIFY_NO_HALF_EDGE_INTERSECTIONS(test_output);
}

@@ -473,7 +473,7 @@
 segments.push_back(segment_data<T>(point2, point3));
 segments.push_back(segment_data<T>(point3, point4));
 construct_voronoi(segments.begin(), segments.end(), &test_output);
- CHECK_OUTPUT_SIZE(test_output, 7, 6, 12);
+ CHECK_OUTPUT_SIZE(test_output, 7, 6, 24);
 VERIFY_NO_HALF_EDGE_INTERSECTIONS(test_output);
}

@@ -489,7 +489,7 @@
 segments.push_back(segment_data<T>(point3, point4));
 segments.push_back(segment_data<T>(point4, point1));
 construct_voronoi(segments.begin(), segments.end(), &test_output);
- CHECK_OUTPUT_SIZE(test_output, 8, 5, 12);
+ CHECK_OUTPUT_SIZE(test_output, 8, 5, 24);
 VERIFY_NO_HALF_EDGE_INTERSECTIONS(test_output);
}

@@ -502,7 +502,7 @@
 segments.push_back(segment_data<T>(point1, point2));
 segments.push_back(segment_data<T>(point2, point3));
 construct_voronoi(segments.begin(), segments.end(), &test_output);
- CHECK_OUTPUT_SIZE(test_output, 5, 0, 4);
+ CHECK_OUTPUT_SIZE(test_output, 5, 0, 8);
 VERIFY_NO_HALF_EDGE_INTERSECTIONS(test_output);
}

Modified: trunk/libs/polygon/test/voronoi_diagram_test.cpp
==============================================================================
--- trunk/libs/polygon/test/voronoi_diagram_test.cpp (original)
+++ trunk/libs/polygon/test/voronoi_diagram_test.cpp 2012-09-10 16:39:16 EDT (Mon, 10 Sep 2012)
@@ -107,6 +107,5 @@
   BOOST_CHECK(vd.num_cells() == 0);
   BOOST_CHECK(vd.num_vertices() == 0);
   BOOST_CHECK(vd.num_edges() == 0);
- BOOST_CHECK(vd.num_half_edges() == 0);
   vd.clear();
}

Next message: guwi17_at_[hidden]: "[Boost-commit] svn:boost r80483 - in trunk: boost/numeric/ublas libs/numeric/ublas/test"
Previous message: sydorchuk.andriy_at_[hidden]: "[Boost-commit] svn:boost r80481 - trunk/libs/polygon/doc"

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