Boost-Commit :

Date view	Thread view	Subject view	Author view

Subject: [Boost-commit] svn:boost r77573 - sandbox/gtl/doc
From: sydorchuk.andriy_at_[hidden]
Date: 2012-03-26 18:09:53

Next message: ramey_at_[hidden]: "[Boost-commit] svn:boost r77574 - trunk/libs/serialization/vc7ide"
Previous message: sydorchuk.andriy_at_[hidden]: "[Boost-commit] svn:boost r77572 - sandbox/gtl/doc"

Author: asydorchuk
Date: 2012-03-26 18:09:50 EDT (Mon, 26 Mar 2012)
New Revision: 77573
URL: http://svn.boost.org/trac/boost/changeset/77573

Log:
Updating links. Updating basic tutorial.

Added:
   sandbox/gtl/doc/voronoi_basic_tutorial.htm (contents, props changed)
Text files modified:
   sandbox/gtl/doc/index.htm | 11 ++++++-----
   sandbox/gtl/doc/voronoi_builder.htm | 4 ++--
   sandbox/gtl/doc/voronoi_diagram.htm | 3 ++-
   sandbox/gtl/doc/voronoi_main.htm | 3 ++-
   sandbox/gtl/doc/voronoi_predicates.htm | 3 ++-
   sandbox/gtl/doc/voronoi_robust_fpt.htm | 3 ++-
   sandbox/gtl/doc/voronoi_utils.htm | 3 ++-
   7 files changed, 18 insertions(+), 12 deletions(-)

Modified: sandbox/gtl/doc/index.htm
==============================================================================
--- sandbox/gtl/doc/index.htm (original)
+++ sandbox/gtl/doc/index.htm 2012-03-26 18:09:50 EDT (Mon, 26 Mar 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>
@@ -13,6 +12,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">
@@ -235,9 +236,9 @@
 extraction application</li>
 <li>Minkowski Sum Learn how to
 apply Boost.Polygon capabilities to implement Minkowski sum of polygon sets</li>
- <li>Voronoi Basic Learn how
- to construct Voronoi diagrams without digging into library details.</li>
- <li>Voronoi Advanced
+ <li>Voronoi Basic Tutorial Learn how
+ to construct, traverse, visualize, associate data with Voronoi diagrams without digging into library details.</li>
+ <li>Voronoi Advanced Tutorial
 Learn how to configure Voronoi builder and Voronoi diagram
 datastructures to suit your requirements. </li>
</ul>

Added: sandbox/gtl/doc/voronoi_basic_tutorial.htm
==============================================================================
--- (empty file)
+++ sandbox/gtl/doc/voronoi_basic_tutorial.htm 2012-03-26 18:09:50 EDT (Mon, 26 Mar 2012)
@@ -0,0 +1,249 @@
+<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
+<html><head>
+
+
+
+<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: 
+
+<ul>
+ <li>preparing input geometries; 
+ </li>
+ <li>construction of the Voronoi diagram;</li>
+ <li>traversing Voronoi graph; 
+ </li>
+ <li>associating user data with Voronoi primitives;</li>
+ <li>rendering Voronoi diagram. 
+ </li>
+</ul>
+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
+the input geometries might look like: 
+ 
+class Point { 
+public: 
+  Point() {} 
+  Point(int x, int y) { this->x = x; this->y = y; } 
+ 
+  // Those accessors are required! 
+  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; 
+}; 
+ 
+class Segment { 
+public: 
+  Segment() {} 
+  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; } 
+ 
+private: 
+  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()); 
+
+<h1>Construction of the Voronoi Diagram 
+</h1>
+
+
+Now let's construct 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! 
+<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): 
+<ul>
+ <li>simply iterating over Voronoi edges: 
+ 
+int get_num_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; 
+} 
+   
+ </li>
+ <li>iterating over Voronoi cell and then traversing edges around that cell: 
+ 
+ int get_num_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. 
+    do { 
+      ++result; 
+      edge = edge->next(); 
+    } while (edge != cell.incident_edge()); 
+  } 
+  return result / 2; 
+} 
+ 
+ </li>
+ <li>iterating over Voronoi vertices and then traversing edges around that vertex: 
+ 
+ int get_num_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. 
+    do { 
+      ++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>
+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. 
+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. 
+for (voronoi_diagram<double>::const_cell_iterator it = vd.cells().begin(); 
+     it != vd.vertices().end(); ++it) { 
+  const voronoi_diagram<double>::cell_type &cell = *it; 
+  const voronoi_diagram<double>::edge_type *edge = cell.incident_edge(); 
+  int count = 0; 
+  do { 
+    ++count; 
+    edge = edge->next(); 
+  } 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.
+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>
+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) 
+  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. 
+ 
+Lets consider that we have 3rd party library function that draws segments using following prototype: 
+ 
+void draw_segment(double x1, double y1, double x2, double y2); 
+ 
+Then function that renders our diagram edges will have following implementation: 
+ 
+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(); 
+       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; 
+    voronoi_utils<double>::point_set_type polyline; 
+    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.   
+    for (int i = 1; i < polyline.size(); ++i) 
+      draw_segment(polyline[i-1].x(), polyline[i-1].y(), polyline[i].x(), polyline[i].y()); 
+
+  } 
+} 
+ 
+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
+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
+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. 
+ 
+<table class="docinfo" id="table1" frame="void" rules="none">
+ <colgroup>
+ <col class="docinfo-name"><col class="docinfo-content">
+ </colgroup>
+ <tbody valign="top">
+ <tr>
+ <th class="docinfo-name">Copyright:</th>
+ <td>Copyright © Intel Corporation 2008-2010.</td>
+ </tr>
+ <tr class="field">
+ <th class="docinfo-name">License:</th>
+ <td class="field-body">Distributed under the Boost Software License,
+ Version 1.0. (See accompanying file <tt class="literal">
+ LICENSE_1_0.txt</tt> or copy at
+ <a class="reference" target="_top" href="http://www.boost.org/LICENSE_1_0.txt">
+ http://www.boost.org/LICENSE_1_0.txt>)</td>
+ </tr>
+</tbody></table>
+
+</body></html>
\ No newline at end of file

Modified: sandbox/gtl/doc/voronoi_builder.htm
==============================================================================
--- sandbox/gtl/doc/voronoi_builder.htm (original)
+++ sandbox/gtl/doc/voronoi_builder.htm 2012-03-26 18:09:50 EDT (Mon, 26 Mar 2012)
@@ -7,6 +7,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>

@@ -69,8 +70,7 @@
 <li>Performance Analysis</li>
 <li>Layout Versus Schematic Tutorial</li>
 <li>Minkowski Sum Tutorial</li>
- <li><a href="voronoi_diagram_basic_tutorial.htm">Voronoi Diagram
- Basic Tutorial</a></li>
+ <li>Voronoi Basic Tutorial</li>
 <li><a href="voronoi_diagram_advanced_tutorial.htm">Voronoi
 Diagram Advanced Tutorial</a></li>
 </ul>

Modified: sandbox/gtl/doc/voronoi_diagram.htm
==============================================================================
--- sandbox/gtl/doc/voronoi_diagram.htm (original)
+++ sandbox/gtl/doc/voronoi_diagram.htm 2012-03-26 18:09:50 EDT (Mon, 26 Mar 2012)
@@ -22,6 +22,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>

@@ -91,7 +92,7 @@
 <li>Performance Analysis</li>
 <li>Layout Versus Schematic Tutorial</li>
 <li>Minkowski Sum Tutorial</li>
- <li>Voronoi Basic Tutorial</li>
+ <li>Voronoi Basic Tutorial</li>
 <li>Voronoi Advanced Tutorial</li>
 </ul>
 </div>

Modified: sandbox/gtl/doc/voronoi_main.htm
==============================================================================
--- sandbox/gtl/doc/voronoi_main.htm (original)
+++ sandbox/gtl/doc/voronoi_main.htm 2012-03-26 18:09:50 EDT (Mon, 26 Mar 2012)
@@ -25,6 +25,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>

@@ -95,7 +96,7 @@
 <li>Performance Analysis</li>
 <li>Layout Versus Schematic Tutorial</li>
 <li>Minkowski Sum Tutorial</li>
- <li>Voronoi Basic Tutorial</li>
+ <li>Voronoi Basic Tutorial</li>
 <li>Voronoi Advanced Tutorial</li>
 </ul>
 </div>

Modified: sandbox/gtl/doc/voronoi_predicates.htm
==============================================================================
--- sandbox/gtl/doc/voronoi_predicates.htm (original)
+++ sandbox/gtl/doc/voronoi_predicates.htm 2012-03-26 18:09:50 EDT (Mon, 26 Mar 2012)
@@ -11,6 +11,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>

@@ -79,7 +80,7 @@
 <li>Performance Analysis</li>
 <li>Layout Versus Schematic Tutorial</li>
 <li>Minkowski Sum Tutorial</li>
- <li>Voronoi Basic Tutorial</li>
+ <li>Voronoi Basic Tutorial</li>
 <li>Voronoi Advanced Tutorial</li>
 </ul>
 </div>

Modified: sandbox/gtl/doc/voronoi_robust_fpt.htm
==============================================================================
--- sandbox/gtl/doc/voronoi_robust_fpt.htm (original)
+++ sandbox/gtl/doc/voronoi_robust_fpt.htm 2012-03-26 18:09:50 EDT (Mon, 26 Mar 2012)
@@ -11,6 +11,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>

@@ -80,7 +81,7 @@
 <li>Performance Analysis</li>
 <li>Layout Versus Schematic Tutorial</li>
 <li>Minkowski Sum Tutorial</li>
- <li>Voronoi Basic Tutorial</li>
+ <li>Voronoi Basic Tutorial</li>
 <li>Voronoi Advanced Tutorial</li>
 </ul>
 </div>

Modified: sandbox/gtl/doc/voronoi_utils.htm
==============================================================================
--- sandbox/gtl/doc/voronoi_utils.htm (original)
+++ sandbox/gtl/doc/voronoi_utils.htm 2012-03-26 18:09:50 EDT (Mon, 26 Mar 2012)
@@ -18,6 +18,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>

@@ -87,7 +88,7 @@
 <li>Performance Analysis</li>
 <li>Layout Versus Schematic Tutorial</li>
 <li>Minkowski Sum Tutorial</li>
- <li>Voronoi Basic Tutorial</li>
+ <li>Voronoi Basic Tutorial</li>
 <li>Voronoi Advanced Tutorial</li>
 </ul>
 </div>

Next message: ramey_at_[hidden]: "[Boost-commit] svn:boost r77574 - trunk/libs/serialization/vc7ide"
Previous message: sydorchuk.andriy_at_[hidden]: "[Boost-commit] svn:boost r77572 - sandbox/gtl/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