Boost-Commit :

Date view	Thread view	Subject view	Author view

Subject: [Boost-commit] svn:boost r77596 - sandbox/gtl/doc
From: sydorchuk.andriy_at_[hidden]
Date: 2012-03-27 16:41:54

Author: asydorchuk
Date: 2012-03-27 16:41:54 EDT (Tue, 27 Mar 2012)
New Revision: 77596
URL: http://svn.boost.org/trac/boost/changeset/77596

Log:
Updating basic tutorial documentation.

Text files modified:
   sandbox/gtl/doc/voronoi_basic_tutorial.htm | 189 ++++++++++++++++++++++-----------------
   sandbox/gtl/doc/voronoi_builder.htm | 11 -
   sandbox/gtl/doc/voronoi_main.htm | 3
   3 files changed, 111 insertions(+), 92 deletions(-)

Modified: sandbox/gtl/doc/voronoi_basic_tutorial.htm
==============================================================================
--- sandbox/gtl/doc/voronoi_basic_tutorial.htm (original)
+++ sandbox/gtl/doc/voronoi_basic_tutorial.htm 2012-03-27 16:41:54 EDT (Tue, 27 Mar 2012)
@@ -3,6 +3,9 @@

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

<h1>Voronoi Basic Tutorial 
@@ -18,59 +21,65 @@
 <li>traversing Voronoi graph; 
 </li>
 <li>associating user data with Voronoi primitives;</li>
- <li>rendering Voronoi diagram. 
- </li>
-</ul>
+ <li>rendering Voronoi diagram.</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 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
+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: 
 
#include "boost/polygon/voronoi.hpp" 
using boost::polygon; 

-<h1>Preparing Input Geometries 
-</h1>
-In the example that goes through this tutorial (LINK TO THE CODE!!!) we
-are going to construct Voronoi diagram of a few points and segments.
-Before executing the algorithm lets see how the user provided types for
+<h1>Preparing Input Geometries</h1>Before executing the algorithm lets see how the user provided types for
the input geometries might look like: 
 
-class Point { 
+class Point { 
public: 
  Point() {} 
-  Point(int x, int y) { this->x = x; this->y = y; } 
+  Point(int x, int y) { x_ = x; y_ = y; } 
 
  // Those accessors are required! 
-  int x() const { return x; } 
-  int y() const { return y; } 
+  int x() const { return x_; } 
+  int y() const { return y_; } 
 
private: 
  // Don't forget should be castable to the signed int32 type! 
-  int x; 
-
-  int y; 
-}; 
+  int x_; 
+  int y_; 
+}; 
 
class Segment { 
public: 
  Segment() {} 
-  Segment(int x1, int y1, int x2, int y2) : p0(x1, y1), p1(x2, y2) {} 
+  Segment(int x1, int y1, int x2, int y2) : p0_(x1, y1), p1_(x2, y2) {} 
 
  // Those accessors are required! 
-  Point low() const { return p0; } 
-  Point high() const { return p1; } 
+  Point low() const { return p0_; } 
+  Point high() const { return p1_; } 
 
private: 
-  Point p0; 
-  Point p1; 
+  Point p0_; 
+  Point p1_; 
}; 
 
Once declared we can create sample input: 
 
-std::vector<Point> points; 
-points.push_back(Point()); 
-points.push_back(Point()); 
-std::vector<Segment> segments; 
-segments.push_back(Segment()); 
-segments.push_back(Segment()); 
+std::vector<Point> points; 
+points.push_back(Point(0, 0)); 
+points.push_back(Point(1, 6)); 
+std::vector<Segment> segments; 
+segments.push_back(Segment(-4, 5, 5, -1)); 
+segments.push_back(Segment(3, -11, 13, -1)); 

<h1>Construction of the Voronoi Diagram 
</h1>
@@ -79,82 +88,86 @@
Now let's construct Voronoi diagram of the input set of points and segments: 
 
voronoi_diagram<double> vd; 
-construct_voronoi(points, segments, vd); 
+construct_voronoi(points, segments, &vd); 
 
So brief, isn't that awesome! 
<h1>Traversing Voronoi Graph</h1>
At the next step we are going to traverse Voronoi graph and count the
-number of primary edges. In case you forgot we consider edge to be a
-primary one if it doesn't go between the segment and its endpoint. 
-There are three ways to do that and we are going to cover all of them
-(each Voronoi edge has an opposite twin edge, that's why we devide
-resulting number by two): 
+number of visited edges. There are three ways to do that and we are going to cover all of them: 
<ul>
- <li>simply iterating over Voronoi edges: 
- 
-int get_num_primary_edges1(const voronoi_diagram<double> &vd) { 
+ <li>simply iterating over 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(); 
       it != vd.edges().end(); ++it) { 
    if (it->is_primary()) 
      ++result; 
  } 
-  return result / 2; 
+  return result; 
} 
   
 </li>
- <li>iterating over Voronoi cell and then traversing edges around that cell: 
+ <li>iterating over Voronoi cell and then traversing edges around that cell (counts each edge twice): 
 
- int get_num_primary_edges2(const voronoi_diagram<double> &vd) { 
+ int iterate_primary_edges2(const voronoi_diagram<double> &vd) { 
  int result = 0; 
  for (voronoi_diagram<double>::const_cell_iterator it = vd.cells().begin(); 
       it != vd.cells().end(); ++it) { 
    const voronoi_diagram<double>::cell_type &cell = *it; 
    const voronoi_diagram<double>::edge_type *edge = cell.incident_edge(); 
-    // This is the best way to iterate edges around Voronoi cell. 
+    // This is convenient way to iterate edges around Voronoi cell. 
    do { 
-      ++result; 
+      if (edge->is_primary()) 
+        ++result; 
      edge = edge->next(); 
    } while (edge != cell.incident_edge()); 
  } 
-  return result / 2; 
+  return result; 
} 
 
 </li>
- <li>iterating over Voronoi vertices and then traversing edges around that vertex: 
- 
- int get_num_primary_edges3(const voronoi_diagram<double> &vd) { 
+
+ <li>iterating over Voronoi
+vertices and then traversing edges around that 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) { 
  int result = 0; 
  for (voronoi_diagram<double>::const_vertex_iterator it = vd.vertices().begin(); 
       it != vd.vertices().end(); ++it) { 
    const voronoi_diagram<double>::vertex_type &vertex = *it; 
    const voronoi_diagram<double>::edge_type *edge = vertex.incident_edge(); 
-    // This is the best way to iterate edges around Voronoi vertex. 
+    // This is convenient way to iterate edges around Voronoi vertex. 
    do { 
-      ++result; 
+      if (edge->is_primary()) 
+        ++result; 
      edge = edge->rot_next(); 
    } while (edge != vertex.incident_edge()); 
  } 
-  return result / 2; 
-} 
- </li>
-</ul>
-This should give a very nice idea on how to traverse Voronoi diagram. 
-<h1>Associating user data with Voronoi primitives</h1>
+  return result; 
+}</li>
+
+</ul>This should give a very nice idea on how to traverse Voronoi
+diagram. Notice that while the output from the first two methods should
+be the same, it wouldn't for the third one. The reason is that in the
+last case we will iterate only once through the edges with a single
+finite endpoint and will skip all the edges with no finite endpoints. 
+<h1>Associating User Data with Voronoi Primitives</h1>
A few simple cases of associating user data with Voronoi primitives are following: 
<ul>
 <li>associating number of incident edges with each cell, vertex;</li>
 <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 number of incident edges with each cell. 
+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. 
 
-vector<int> counts; 
-counts.reserve(vd.num_cells()); // This is required as reallocation of underlying vector will invalidate all the pointers. 
+std::vector<int> counts; 
+// This is required as reallocation of underlying vector will invalidate all the pointers. 
+counts.reserve(vd.num_cells()); 
for (voronoi_diagram<double>::const_cell_iterator it = vd.cells().begin(); 
-     it != vd.vertices().end(); ++it) { 
-  const voronoi_diagram<double>::cell_type &cell = *it; 
+     it != vd.cells().end(); ++it) { 
+  const voronoi_diagram<double>::cell_type &cell = *it; 
  const voronoi_diagram<double>::edge_type *edge = cell.incident_edge(); 
  int count = 0; 
  do { 
@@ -163,32 +176,35 @@
  } while (edge != cell.incident_edge()); 
  counts.push_back(count); 
  cell.data(&counts.back()); 
-} 
+} 
 
Note: In the example above we could not simply use count variable
without a vector, because pointer to it will become invalid as soon as
we leave the scope of enclosing for-loop. 
-<h1>Rendering Voronoi diagram</h1>
-There are two main issues that don't allow to strictly render output
-Voronoi diagram using modern rendering tools like OpenGL or DirectX.
+<h1>Rendering Voronoi Diagram</h1>
+There are two main issues that don't allow to strictly render resulting
+Voronoi diagram using such rendering tools as OpenGL or DirectX.
Those are: 
<ul>
 <li>Some of the Voronoi edges are infinite, so should be clipped;</li>
 <li>Some of the Voronoi edge are parabolic arcs, so should be discretized.</li>
-</ul>
+</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
plus some offset. 
- 
-bounding_rectangle<double> bbox; 
-for (std::vector<Point>::iterator it = points.begin(); it != points.end(); ++it) 
+ 
+bounding_rectangle<double> bbox; 
+for (std::vector<Point>::iterator it = points.begin(); it != points.end(); ++it) 
  bbox.update(it->x(), it->y()); 
for (std::vector<Segment>::iterator it = segments.begin(); it != segments.end(); ++it) { 
  bbox.update(it->low().x(), it->low().y()); 
  bbox.update(it->high().x(), it->high().y()); 
} 
-return voronoi_utils<double>::scale(bbox, 1.1); // Add 10% offset to the bounding rectangle. 
+// 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: 
 
@@ -199,33 +215,42 @@
void render_diagram(const voronoi_diagram<double> &vd, 
                   
const voronoi_utils<double>::brect_type &bbox) { 
-  for (voronoi_diagram<double>::const_edge_iterator it = vd.edges().begin(); 
+  int visited = 1; 
+  for (voronoi_diagram<double>::const_edge_iterator it = vd.edges().begin(); 
       it != vd.edges().end(); ++it) { 
-    it->data(&(*it)); // We use data pointer to mark visited edges (by pointing to itself); 
-    if (it->twin()) continue; // We don't want to draw the same edge twice; 
+    // We use data pointer to mark visited edges. 
+    it->data(&visited); 
+    // Don't render the same edge twice. 
+    if (it->twin()->data()) continue; 
    voronoi_utils<double>::point_set_type polyline; 
-    if (it->is_linear) 
+    if (it->is_linear()) 
      voronoi_utils<double>::clip(*it, bbox, polyline); 
    else 
      // Parabolic edges are always finite. 
-      voronoi_utils<double>::discretize(*it, 1E-3, polyline); 
-    // Note: discretized edges may also lie outside of the bbox. 
-    // So user might do additional clipping before rendering each such edge.   
+      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.  
    for (int i = 1; i < polyline.size(); ++i) 
-      draw_segment(polyline[i-1].x(), polyline[i-1].y(), polyline[i].x(), polyline[i].y()); 
-
-  } 
-} 
+      draw_segment(polyline[i-1].x(), polyline[i-1].y(), 
+                  
+polyline[i].x(), polyline[i].y()); 
+  } 
+} 
+ 
+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. 
+
 
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). It's worth
+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 utililities. In
+using Voronoi utililities. In
default mode Voronoi diagram operates with signed int (32 bit) input
-coordinate type and double (64 bit) output coordinate type. In case you
-are intersted in expanding those try Voronoi Advanced Tutorial. 
+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%. 
 
<table class="docinfo" id="table1" frame="void" rules="none">
 <colgroup>

Modified: sandbox/gtl/doc/voronoi_builder.htm
==============================================================================
--- sandbox/gtl/doc/voronoi_builder.htm (original)
+++ sandbox/gtl/doc/voronoi_builder.htm 2012-03-27 16:41:54 EDT (Tue, 27 Mar 2012)
@@ -8,6 +8,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>

@@ -272,7 +273,6 @@
    typedef ulp_comparison<fpt_type> ulp_cmp_type; 
    typedef type_converter_fpt to_fpt_converter_type; 
    typedef type_converter_efpt to_efpt_converter_type; 
-    enum { ULPS = 64 }; 
 };
 
 One of the most important features of the library is that Voronoi
@@ -360,14 +360,7 @@
 operator(). 
 </td>
 </tr>
- <tr>
- <td style="vertical-align: top; font-family: 'Courier New',Courier,monospace;">
- ULPS 
- </td>
- <td style="vertical-align: top;">Relative precision threshold
- that triggers multi-precision predicates. 
- </td>
- </tr>
+
 </tbody></table>
 Notes: 
 1) 4 different integer types are used (instead of a single big_int_type) to slightly improve algorithm performance and memory

Modified: sandbox/gtl/doc/voronoi_main.htm
==============================================================================
--- sandbox/gtl/doc/voronoi_main.htm (original)
+++ sandbox/gtl/doc/voronoi_main.htm 2012-03-27 16:41:54 EDT (Tue, 27 Mar 2012)
@@ -26,6 +26,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>

@@ -234,7 +235,7 @@
following two lines of code: 
 
 voronoi_diagram<double> vd; 
- construct_voronoi(points, segments, 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.

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