Boost logo

Boost-Commit :

Subject: [Boost-commit] svn:boost r77956 - in sandbox/gtl: boost/polygon doc
From: sydorchuk.andriy_at_[hidden]
Date: 2012-04-13 18:01:43


Author: asydorchuk
Date: 2012-04-13 18:01:42 EDT (Fri, 13 Apr 2012)
New Revision: 77956
URL: http://svn.boost.org/trac/boost/changeset/77956

Log:
Updating Voronoi diagram documentation page.

Text files modified:
   sandbox/gtl/boost/polygon/voronoi_diagram.hpp | 7
   sandbox/gtl/doc/voronoi_builder.htm | 7
   sandbox/gtl/doc/voronoi_diagram.htm | 282 ++++++++++++++++++++++++++++++++++-----
   3 files changed, 254 insertions(+), 42 deletions(-)

Modified: sandbox/gtl/boost/polygon/voronoi_diagram.hpp
==============================================================================
--- sandbox/gtl/boost/polygon/voronoi_diagram.hpp (original)
+++ sandbox/gtl/boost/polygon/voronoi_diagram.hpp 2012-04-13 18:01:42 EDT (Fri, 13 Apr 2012)
@@ -262,13 +262,10 @@
 class voronoi_diagram {
 public:
   typedef typename TRAITS::coordinate_type coordinate_type;
- typedef typename TRAITS::ctype_converter_type ctype_converter_type;
   typedef typename TRAITS::point_type point_type;
   typedef typename TRAITS::cell_type cell_type;
   typedef typename TRAITS::vertex_type vertex_type;
   typedef typename TRAITS::edge_type edge_type;
- typedef typename TRAITS::vertex_equality_predicate_type
- vertex_equality_predicate_type;
 
   typedef std::vector<cell_type> cell_container_type;
   typedef typename cell_container_type::iterator cell_iterator;
@@ -369,6 +366,10 @@
   }
 
 private:
+ typedef typename TRAITS::ctype_converter_type ctype_converter_type;
+ typedef typename TRAITS::vertex_equality_predicate_type
+ vertex_equality_predicate_type;
+
   friend class voronoi_diagram_builder;
 
   void reserve(int num_sites) {

Modified: sandbox/gtl/doc/voronoi_builder.htm
==============================================================================
--- sandbox/gtl/doc/voronoi_builder.htm (original)
+++ sandbox/gtl/doc/voronoi_builder.htm 2012-04-13 18:01:42 EDT (Fri, 13 Apr 2012)
@@ -2,6 +2,7 @@
 <html><head>
 
 
+
   
   <meta http-equiv="Content-Language" content="en-us">
 
@@ -79,13 +80,15 @@
       </h1>
 
 Voronoi builder is the event generator structure. It implements the <a href="http://www.ams.org/samplings/feature-column/fcarc-voronoi">sweepline
-algorithm</a> that scans a 2D space and generates two types of events:
+algorithm</a>
+that scans a 2D space and generates two types of 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, 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
+and&nbsp; linear 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

Modified: sandbox/gtl/doc/voronoi_diagram.htm
==============================================================================
--- sandbox/gtl/doc/voronoi_diagram.htm (original)
+++ sandbox/gtl/doc/voronoi_diagram.htm 2012-04-13 18:01:42 EDT (Fri, 13 Apr 2012)
@@ -1,6 +1,7 @@
 <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
 <html><head>
 
+
   
   <meta http-equiv="Content-Language" content="en-us">
 
@@ -96,7 +97,7 @@
 (one dimensional curves containing points equidistant from the two
 closest input sites). Each of the primitives (cell, vertex, edge)
 contains pointers to the other linked primitives, so that it's always
-possible to efficiently traverse the Voronoi graph. Picture below shows
+possible to efficiently traverse 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 its
@@ -105,10 +106,11 @@
 simplify representation of the Voronoi diagram.<br>
       <br>
       <img style="border: 1px solid ; width: 300px; height: 300px;" alt="" src="images/voronoi2.png"><br>
- <br>
-Voronoi diagram declaration and list of the member functions is
-following:<br>
- <br>
+ <h2>Declaration<br>
+ </h2>
+
+
+
       <span style="font-family: Courier New,Courier,monospace;">template
 &lt;typename T, typename TRAITS = voronoi_diagram_traits&lt;T&gt; &gt;</span><br style="font-family: Courier New,Courier,monospace;">
       <span style="font-family: Courier New,Courier,monospace;">class
@@ -116,9 +118,12 @@
       <br>
 </span><font face="Courier New"><span style="font-family: 'Courier New',Courier,monospace;">T</span></font>
 - specifies coordinate type of the output geometries: input sites (points / segments), Voronoi vertices.<br>
- <span style="font-family: Courier New,Courier,monospace;">TRAITS - </span>Voronoi diagram traits (explained in the end of this chapter).<br>
+ <span style="font-family: Courier New,Courier,monospace;">TRAITS</span><font face="Courier New"><span style="font-family: 'Courier New',Courier,monospace;"></span></font>
+- Voronoi diagram traits (explained in the end of this chapter).<br>
+ <h2>Member Functions</h2>
+
       <span style="font-family: Courier New,Courier,monospace;">
- <br>
+
       </span>
       <table style="text-align: left; width: 100%;" border="1" cellpadding="2" cellspacing="2">
         <tbody>
@@ -189,16 +194,116 @@
           </tr>
         </tbody>
       </table>
+
+ <h2>Member Types</h2>
+ <table style="text-align: left; width: 100%;" border="1" cellpadding="2" cellspacing="2">
+ <tbody>
+ <tr>
+ <td style="vertical-align: top;">coordinate_type<br>
+ </td>
+ <td style="vertical-align: top;">Coordinate type.<br>
+ </td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top;">point_type<br>
+ </td>
+ <td style="vertical-align: top;">2D point.<br>
+ </td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top;">cell_type<br>
+ </td>
+ <td style="vertical-align: top;">Voronoi cell.<br>
+ </td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top;">vertex_type<br>
+ </td>
+ <td style="vertical-align: top;">Voronoi vertex.<br>
+ </td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top;">edge_type<br>
+ </td>
+ <td style="vertical-align: top;">Voronoi edge.<br>
+ </td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top;">cell_container_type<br>
+ </td>
+ <td style="vertical-align: top;">Container of Voronoi cells.<br>
+ </td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top;">cell_iterator<br>
+ </td>
+ <td style="vertical-align: top;">Cell container iterator.<br>
+ </td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top;">const_cell_iterator<br>
+ </td>
+ <td style="vertical-align: top;">Const cell container iterator.<br>
+ </td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top;">vertex_container_type<br>
+ </td>
+ <td style="vertical-align: top;">Container of Voronoi vertices.<br>
+ </td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top;">vertex_iterator<br>
+ </td>
+ <td style="vertical-align: top;">Vertex container iterator.<br>
+ </td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top;">const_vertex_iterator<br>
+ </td>
+ <td style="vertical-align: top;">Const vertex container iterator.<br>
+ </td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top;">edge_container_type<br>
+ </td>
+ <td style="vertical-align: top;">Container of Voronoi edges.<br>
+ </td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top;">edge_iterator<br>
+ </td>
+ <td style="vertical-align: top;">Edge container iterator.<br>
+ </td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top;">const_edge_iterator<br>
+ </td>
+ <td style="vertical-align: top;">Const edge container iterator.<br>
+ </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 the member functions is
-following:<br>
- <br>
+data structure.<br>
+ <h2>Declaration</h2>
+
+
+
       <span style="font-family: Courier New,Courier,monospace;">template
 &lt;typename T&gt;</span><br style="font-family: Courier New,Courier,monospace;">
       <span style="font-family: Courier New,Courier,monospace;">class
 voronoi_edge;<br>
       <br>
+T</span> - coordinate type. While Voronoi edge doesn't contain coordinates itself, it stores pointers to Voronoi cell and vertex.<br>
+ <h2>Member Functions</h2>
+
+ <span style="font-family: Courier New,Courier,monospace;">
+
       </span>
       <table style="text-align: left; width: 100%;" border="1" cellpadding="2" cellspacing="2">
         <tbody>
@@ -239,7 +344,7 @@
             </td>
             <td style="vertical-align: top;">Returns the pointer to the
 start point of the edge.<br>
-If edge is infinite in that direction returns NULL.<br>
+If the edge is infinite in that direction returns NULL.<br>
             </td>
           </tr>
           <tr>
@@ -247,8 +352,8 @@
 voronoi_vertex_type *vertex0() const<br>
             </td>
             <td style="vertical-align: top;">Returns the const pointer
-to the start point of the edge.<br>
-If edge is infinite in that direction returns NULL.<br>
+to the point vertex of the edge.<br>
+If the edge is infinite in that direction returns NULL.<br>
             </td>
           </tr>
           <tr>
@@ -281,7 +386,7 @@
             <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">void
 vertex1(voronoi_vertex_type *v)<br>
             </td>
- <td style="vertical-align: top;">Sets the endpoint pointer
+ <td style="vertical-align: top;">Sets the end point pointer
 of the edge.<br>
             </td>
           </tr>
@@ -315,7 +420,7 @@
             </td>
             <td style="vertical-align: top;">Returns the pointer to the
 CCW next edge within the corresponding Voronoi cell.<br>
-Edges not necessarily share a common vertex.<br>
+Edges not necessarily share a common vertex (e.g. infinite edges).<br>
             </td>
           </tr>
           <tr>
@@ -324,7 +429,7 @@
             </td>
             <td style="vertical-align: top;">Returns the const pointer
 to the CCW next edge within the corresponding Voronoi cell.<br>
-Edges not necessarily share a common vertex.<br>
+Edges not necessarily share a common vertex (e.g. infinite edges).<br>
             </td>
           </tr>
           <tr>
@@ -341,7 +446,7 @@
             </td>
             <td style="vertical-align: top;">Returns the pointer to the
 CCW prev edge within the corresponding Voronoi cell.<br>
-Edges not necessarily share a common vertex.<br>
+Edges not necessarily share a common vertex (e.g. infinite edges).<br>
             </td>
           </tr>
           <tr>
@@ -350,7 +455,7 @@
             </td>
             <td style="vertical-align: top;">Returns the const pointer
 to the CCW prev edge within the corresponding Voronoi cell.<br>
-Edges not necessarily share a common vertex.<br>
+Edges not necessarily share a common vertex (e.g. infinite edges).<br>
             </td>
           </tr>
           <tr>
@@ -417,7 +522,7 @@
 is_finite() const<br>
             </td>
             <td style="vertical-align: top;">Returns true if the both
-endpoints of the edge are finite, else false.<br>
+end points of the edge are finite, else false.<br>
             </td>
           </tr>
           <tr>
@@ -441,7 +546,7 @@
 is_primary() const<br>
             </td>
             <td style="vertical-align: top;">Returns false if the edge
-goes through the endpoint of the segment, else true.<br>
+goes through the endpoint of the segment site, else true.<br>
             </td>
           </tr>
         </tbody>
@@ -449,16 +554,53 @@
       <span style="font-family: Courier New,Courier,monospace;"><br>
       </span>All the above methods have O(1) complexity. The size of
 the Voronoi edge structure is equal to: 6 * sizeof(void *).<br>
+ <h2>Member Types</h2>
+
+ <table style="text-align: left; width: 100%;" border="1" cellpadding="2" cellspacing="2">
+ <tbody>
+ <tr>
+ <td style="vertical-align: top;">coordinate_type<br>
+ </td>
+ <td style="vertical-align: top;">Coordinate type.<br>
+ </td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top;">voronoi_cell_type<br>
+ </td>
+ <td style="vertical-align: top;">Voronoi cell type.<br>
+ </td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top;">voronoi_vertex_type<br>
+ </td>
+ <td style="vertical-align: top;">Voronoi vertex type.<br>
+ </td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top;">voronoi_edge_type<br>
+ </td>
+ <td style="vertical-align: top;">Voronoi edge type.<br>
+ </td>
+ </tr>
+ </tbody>
+ </table>
+
       <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 the member functions
-is
-following:<br>
- <br>
+to the incident edge.<br>
+ <h2>Declaration</h2>
+
+
+
       <span style="font-family: Courier New,Courier,monospace;">template
 &lt;typename T&gt;<br>
 class voronoi_cell;<br>
       <br>
+</span><span style="font-family: Courier New,Courier,monospace;">T</span> - coordinate type.<br>
+ <h2>Member Functions</h2>
+
+ <span style="font-family: Courier New,Courier,monospace;">
+
       </span>
       <table style="text-align: left; width: 100%;" border="1" cellpadding="2" cellspacing="2">
         <tbody>
@@ -568,7 +710,33 @@
       </span>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).<br>
- <br>
+ <h2>Member Types</h2>
+
+
+
+ <table style="text-align: left; width: 100%;" border="1" cellpadding="2" cellspacing="2">
+ <tbody>
+ <tr>
+ <td style="vertical-align: top;">coordinate_type<br>
+ </td>
+ <td style="vertical-align: top;">Coordinate type.<br>
+ </td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top;">point_type</td>
+ <td style="vertical-align: top;">Point type.<br>
+ </td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top;">voronoi_edge_type<br>
+ </td>
+ <td style="vertical-align: top;">Voronoi edge type.<br>
+ </td>
+ </tr>
+ </tbody>
+ </table>
+ <h2>Miscellaneous</h2>
+
 Following code snippet effectively traverses Voronoi edges around the
 Voronoi cell:<br>
       <br>
@@ -583,15 +751,21 @@
 (edge != cell-&gt;incident_edge());</span><br>
       <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 the
-member
-functions is following:<br>
- <br>
+and a pointer to the incident edge.<br>
+ <h2>Declaration</h2>
+
+
+
       <span style="font-family: Courier New,Courier,monospace;">template
 &lt;typename T&gt;</span><br style="font-family: Courier New,Courier,monospace;">
       <span style="font-family: Courier New,Courier,monospace;">class
 voronoi_vertex;<br>
       <br>
+</span><span style="font-family: Courier New,Courier,monospace;">T</span> - coordinate type.<br>
+ <h2>Member Functions</h2>
+
+ <span style="font-family: Courier New,Courier,monospace;">
+
       </span>
       <table style="text-align: left; width: 100%;" border="1" cellpadding="2" cellspacing="2">
         <tbody>
@@ -656,8 +830,35 @@
       </span>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).<br>
- <br>
-Following code snipped effectively traverses Voronoi edges around the
+ <h2>Member Types</h2>
+ <table style="text-align: left; width: 100%;" border="1" cellpadding="2" cellspacing="2">
+ <tbody>
+ <tr>
+ <td style="vertical-align: top;">coordinate_type<br>
+ </td>
+ <td style="vertical-align: top;">Coordainte type.<br>
+ </td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top;">point_type<br>
+ </td>
+ <td style="vertical-align: top;">Point type.<br>
+ </td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top;">voronoi_edge_type<br>
+ </td>
+ <td style="vertical-align: top;">Voronoi edge type.<br>
+ </td>
+ </tr>
+ </tbody>
+ </table>
+
+ <h2>Miscellaneous</h2>
+
+
+
+Following code snippet effectively traverses Voronoi edges around the
 Voronoi vertex:<br>
       <br>
       <span style="font-family: Courier New,Courier,monospace;">const
@@ -671,15 +872,22 @@
 (edge != vertex-&gt;incident_edge());</span><br>
       <h1>Voronoi Diagram Traits<br>
       </h1>
-Voronoi diagram traits are used to configure the Voronoi diagram data
-structure. The declaration and list of the required type definitions is
-following:<br>
- <br>
+Voronoi diagram traits are used to configure Voronoi diagram data
+structure.<br>
+ <h2>Declaration</h2>
+
+
+
       <span style="font-family: Courier New,Courier,monospace;">template
 &lt;typename T&gt;</span><br style="font-family: Courier New,Courier,monospace;">
       <span style="font-family: Courier New,Courier,monospace;">struct
 voronoi_diagram_traits;<br>
       <br>
+</span><span style="font-family: Courier New,Courier,monospace;">T</span> - coordinate type.<br>
+ <h2>Member Types</h2>
+
+ <span style="font-family: Courier New,Courier,monospace;">
+
       </span>
       <table style="text-align: left; width: 100%;" border="1" cellpadding="2" cellspacing="2">
         <tbody>
@@ -687,7 +895,7 @@
             <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">coordinate_type<br>
             </td>
             <td style="vertical-align: top;">The main coordinate type
-of the Voronoi diagram internal structures.<br>
+of the Voronoi diagram primitives.<br>
             </td>
           </tr>
           <tr>
@@ -695,7 +903,7 @@
             </td>
             <td style="vertical-align: top;">Coordinate type converter
 structure.<br>
-Converts the coordinates provided by the Voronoi builder to the
+Converts coordinates provided by the Voronoi builder to the
 internal coordinate type.<br>
             </td>
           </tr>


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