Boost-Commit :

Date view	Thread view	Subject view	Author view

Subject: [Boost-commit] svn:boost r77377 - in sandbox/gtl: boost/polygon doc
From: sydorchuk.andriy_at_[hidden]
Date: 2012-03-18 14:15:24

Author: asydorchuk
Date: 2012-03-18 14:15:23 EDT (Sun, 18 Mar 2012)
New Revision: 77377
URL: http://svn.boost.org/trac/boost/changeset/77377

Log:
Updating documentation.

Added:
   sandbox/gtl/doc/voronoi_diagram.htm (contents, props changed)
Text files modified:
   sandbox/gtl/boost/polygon/voronoi_utils.hpp | 7 +
   sandbox/gtl/doc/index.htm | 13 +-
   sandbox/gtl/doc/voronoi_builder.htm | 52 +++++++-----
   sandbox/gtl/doc/voronoi_predicates.htm | 38 +++++----
   sandbox/gtl/doc/voronoi_robust_fpt.htm | 40 +++++----
   sandbox/gtl/doc/voronoi_utils.htm | 156 +++++++++++++++++++++++++++++++--------
   6 files changed, 207 insertions(+), 99 deletions(-)

Modified: sandbox/gtl/boost/polygon/voronoi_utils.hpp
==============================================================================
--- sandbox/gtl/boost/polygon/voronoi_utils.hpp (original)
+++ sandbox/gtl/boost/polygon/voronoi_utils.hpp 2012-03-18 14:15:23 EDT (Sun, 18 Mar 2012)
@@ -20,7 +20,7 @@
namespace polygon {

// Bounding rectangle data structure. Contains coordinates
-// of the bottom left and upper right points of the rectangle.
+// of the bottom left and upper right corners of rectangle.
template <typename T>
class bounding_rectangle {
public:
@@ -58,7 +58,7 @@
 x_max_ = 0;
 }

- bool contains(coordinate_type x, coordinate_type y) const {
+ bool contains(coordinate_type x, coordinate_type y) {
 return x > x_min_ && x < x_max_ && y > y_min_ && y < y_max_;
 }

@@ -227,7 +227,8 @@
 point_type direction(end.x() - start.x(), end.y() - start.y());
 if (brect.contains(start.x(), start.y()))
 clipped_edge.push_back(start);
- intersect(start, direction, SEGMENT, brect, clipped_edge);
+ if (p1 != p2)
+ intersect(start, direction, SEGMENT, brect, clipped_edge);
 if (brect.contains(end.x(), end.y()))
 clipped_edge.push_back(end);
 }

Modified: sandbox/gtl/doc/index.htm
==============================================================================
--- sandbox/gtl/doc/index.htm (original)
+++ sandbox/gtl/doc/index.htm 2012-03-18 14:15:23 EDT (Sun, 18 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>
@@ -11,8 +10,10 @@

+
+
 <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);" valign="top" nowrap="1">
+<td style="background-color: rgb(238, 238, 238);" nowrap="1" valign="top">
 <div style="padding: 5px;" align="center">
 <img src="images/boost.png" border="0" height="86" width="277" /><a title="www.boost.org home page" href="http://www.boost.org/" tabindex="2" style="border: medium none ;">
 </a>
@@ -97,13 +98,13 @@
geometry in its scope, and provides a set of capabilities for working with
coordinates, points, intervals and rectangles that are needed to support
implementing and interacting with polygon data structures and algorithms.  <img src="images/hand.png" border="0" height="277" width="837" />
-One of the important features of the library is implementation of
+One of important features of the library is implementation of
generic sweepline algorithm to build Voronoi diagrams in 2D (developed
as part of GSoC 2010 program). Voronoi diagram datastructure has
applications in image segmentation, optical character recognition,
nearest neighbor queries execution. It is closely related with other
computational geometry concepts: delaunay triangulation, medial axis,
-straight skeleton, largest empty circle.  Boost.Polygon library
+straight skeleton, largest empty circle. Boost.Polygon library
provides interface to construct Voronoi diagrams of points figure a and
line segments figure b (the last could be used to discretize any
two-dimensional curve). Figure c contains example of medial axis of a
@@ -255,7 +256,7 @@

 </td></tr><tr>
-<td style="background-color: rgb(238, 238, 238);" valign="top" nowrap="1">
+<td style="background-color: rgb(238, 238, 238);" nowrap="1" valign="top">
  </td>
<td style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;" valign="top" width="100%">

Modified: sandbox/gtl/doc/voronoi_builder.htm
==============================================================================
--- sandbox/gtl/doc/voronoi_builder.htm (original)
+++ sandbox/gtl/doc/voronoi_builder.htm 2012-03-18 14:15:23 EDT (Sun, 18 Mar 2012)
@@ -4,6 +4,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>

@@ -85,8 +86,7 @@
 Voronoi builder is event generator structure. It implements
 sweepline algorithm that scans 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 datastructure
- provided to the builder through the generic interface. The structure
+ those are exactly). Each event is reported to the output datastructure builder. The structure
 shares Voronoi name as the events generated by it correspond to the
 Voronoi diagram edges and vertices and give enought information to
 construct Voronoi diagram of a set of points and segments. The
@@ -104,8 +104,7 @@
 typename CTT = detail::voronoi_ctype_traits<T>, 
          
 typename VP = detail::voronoi_predicates<CTT> > 
- class voronoi_builder
- { /* Implementation. */ }; 
+ class voronoi_builder; 
 
 T
 - specifies coordinate type of the input geometries (points and segments). 
@@ -143,9 +142,11 @@
 <td style="vertical-align: top;" width="693">Default constructor.</td>
 </tr>
 <tr>
- <td style="vertical-align: top;">void insert_point(const int_type& x, const int_type& y) 
+ <td style="vertical-align: top;">void insert_point( 
+    const int_type& x, 
+    const int_type& y) 
 </td>
- <td style="vertical-align: top;">Inserts point object with provided coordinates into Voronoi builder. 
+ <td style="vertical-align: top;">Inserts point object with specified coordinates into Voronoi builder. 
 </td>
 </tr>
 <tr>
@@ -160,7 +161,9 @@
<tr>
 <td style="font-family: 'Courier New',Courier,monospace;">
 template <typename PointIterator> 
- void insert_points(PointIterator first_point, PointIterator last_point) 
+ void insert_points( 
+    PointIterator first_point, 
+    PointIterator last_point) 
 </td>
 <td style="vertical-align: top;" width="693">Inserts point
 objects into Voronoi builder. 
@@ -169,16 +172,22 @@
 </td>
 </tr>
 <tr>
- <td style="vertical-align: top;">void insert_segment(const int_type& x1, const int_type& y1, const int_type& x2, const int_type& y2) 
+ <td style="vertical-align: top;">void insert_segment( 
+    const int_type& x1, 
+    const int_type& y1, 
+    const int_type& x2, 
+    const int_type& y2) 
 </td>
- <td style="vertical-align: top;">Insert segment object with provided coordinates into Voronoi builder. 
+ <td style="vertical-align: top;">Insert segment object with specified coordinates into Voronoi builder. 
 </td>
 </tr>
 <tr>
 <td style="vertical-align: top;">template <typename PointType> 
-void insert_segment(const PointType& point1, const PointType& point2) 
+void insert_segment( 
+    const PointType& point1, 
+    const PointType& point2) 
 </td>
- <td style="vertical-align: top;">Insert segment object with provided endpoints into Voronoi builder. 
+ <td style="vertical-align: top;">Insert segment object with specified endpoints into Voronoi builder. 
Endpoint objects should support x() and y() methods to retrieve their coordinates. 
 </td>
 </tr>
@@ -188,7 +197,7 @@
 </td>
 <td style="vertical-align: top;">Insert segment object into Voronoi builder. 
Segment object should support low() and high() methods that retrieve segment endpoints. 
-Endpoint objects should support x() and y() methods to retrieve their coordinates. 
+Endpoint object should support x() and y() methods to retrieve its coordinates. 
 </td>
 </tr>
<tr>
@@ -207,8 +216,11 @@
 <tr>
 <td style="vertical-align: top; font-family: 'Courier New',Courier,monospace;">
 template <typename PointIterator, typename SegmentIterator> 
-void insert_sites(PointIterator first_point, PointIterator last_point,
-SegmentIterator first_segment, SegmentIterator last_segment) 
+void insert_sites( 
+    PointIterator first_point, 
+    PointIterator last_point, 
+    SegmentIterator first_segment, 
+    SegmentIterator last_segment) 
 </td>
 <td style="vertical-align: top;" width="693">Inserts point and
 segment objects into Voronoi builder. 
@@ -224,14 +236,11 @@
 <td style="vertical-align: top;" width="693">Runs sweepline
 algorithm over the set of the inserted geometries, outputs site
 and circle events to the OUTPUT datastructure. It's
- responsibility of the output structure to process them. For
+ responsibility of the output structure builder to process them. For
 example both Voronoi diagram and Delaunay triangulation could be
 constructed from the Voronoi builder events, however internally
 they are different datastructures, so it's up to them to process
- properly events produced by the builder object. To make this
- possible OUTPUT type should provide a set of generic methods
- which are discussed in detail on <a href="voronoi_diagram.htm">
- Voronoi Diagram</a> page. 
+ properly events produced by the builder object. 
 </td>
 </tr>
 <tr>
@@ -360,15 +369,14 @@
 </tr>
 </tbody></table>
 Notes: 
- 1) 4 different integer types are used (instead of a single big_int_type
- for everything) to slightly improve algorithm performance and memory
+ 1) 4 different integer types are used (instead of a single big_int_type) to slightly improve algorithm performance and memory
 usage. 
 2) As maximum required size of the big_int_type is known in advance
 library provided implementation of fixed integers could be used, which
 is much faster than heap-allocated big integers. 
 3) two separate floating-point types are defined because for input with
 32-bit signed integer coordinates double won't be able to handle
- 4096-bit (128 * 32) integers as they will overflow its' exponent. On the
+ 4096-bit (128 * 32) integers as they will overflow its exponent. On the
 gcc compiler it's possible to use 80-bit long doubles for both fpt
 types, however this is not supported by msvc compiler. 
 4) efpt_type and to_efpt_converter_type are not used to construct

Added: sandbox/gtl/doc/voronoi_diagram.htm
==============================================================================
--- (empty file)
+++ sandbox/gtl/doc/voronoi_diagram.htm 2012-03-18 14:15:23 EDT (Sun, 18 Mar 2012)
@@ -0,0 +1,640 @@
+<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
+<html><head>
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+<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>
+
+<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">
+ <img src="images/boost.png" border="0" height="86" width="277"><a title="www.boost.org home page" tabindex="2" style="border: medium none ;" href="http://www.boost.org/">
+ </a></div>
+ <div style="margin: 5px;">
+ <h3 class="navbar">Contents</h3>
+ <ul>
+ <li>Boost.Polygon Main Page</li>
+ <li>Design Overview</li>
+ <li>Isotropy</li>
+ <li>Coordinate Concept</li>
+ <li>Interval Concept</li>
+ <li>Point Concept</li>
+ <li>Rectangle Concept</li>
+ <li>Polygon 90 Concept</li>
+ <li><a href="gtl_polygon_90_with_holes_concept.htm">Polygon 90
+ With Holes Concept</a></li>
+ <li>Polygon 45 Concept</li>
+ <li><a href="gtl_polygon_45_with_holes_concept.htm">Polygon 45
+ With Holes Concept</a></li>
+ <li>Polygon Concept</li>
+ <li><a href="gtl_polygon_with_holes_concept.htm">Polygon With
+ Holes Concept</a></li>
+ <li><a href="gtl_polygon_90_set_concept.htm">Polygon 90 Set
+ Concept</a></li>
+ <li><a href="gtl_polygon_45_set_concept.htm">Polygon 45 Set
+ Concept</a></li>
+ <li>Polygon Set Concept</li>
+ <li><a href="gtl_connectivity_extraction_90.htm">Connectivity
+ Extraction 90</a></li>
+ <li><a href="gtl_connectivity_extraction_45.htm">Connectivity
+ Extraction 45</a></li>
+ <li><a href="gtl_connectivity_extraction.htm">Connectivity
+ Extraction</a></li>
+ <li>Property Merge 90</li>
+ <li>Property Merge 45</li>
+ <li>Property Merge</li>
+ <li><a href="voronoi_unit.htm">Voronoi Main Page 
+</a></li>
+ <li>Voronoi Benchmark</li>
+
+ <li>Voronoi Builder 
+ </li>
+ <li>Voronoi Diagram</li>
+ <li>Voronoi Robust FPT 
+ </li>
+
+ <li>Voronoi Predicates</li>
+
+ <li>Voronoi Utils 
+ </li>
+
+
+ </ul>
+ <h3 class="navbar">Other Resources</h3>
+ <ul>
+ <li>GTL Boostcon 2009 Paper</li>
+ <li><a href="GTL_boostcon_draft03.htm">GTL Boostcon 2009
+ Presentation</a></li>
+ <li>Performance Analysis</li>
+ <li>Layout Versus Schematic Tutorial</li>
+ <li>Minkowski Sum Tutorial</li>
+ <li>Voronoi Basic Tutorial</li>
+ <li>Voronoi Advanced Tutorial</li>
+ </ul>
+ </div>
+ <h3 class="navbar">Polygon Sponsor</h3>
+ <div style="padding: 5px;" align="center">
+ <img src="images/intlogo.gif" border="0" height="51" width="127"><a title="www.adobe.com home page" tabindex="2" style="border: medium none ;" href="http://www.adobe.com/">
+ </a></div>
+ </td>
+ <td style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;" valign="top" width="100%">
+ 
+ 
+ <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
+(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
+input segment consists of three sites: segment itself and two
+endpoints). 
+ 
+ <img style="border: 1px solid ; width: 300px; height: 300px;" alt="" src="images/diagram.png"> 
+ 
+Voronoi diagram declaration and list of member fucntions is following: 
+ 
+ template <typename T, typename TRAITS = voronoi_diagram_traits<T> > 
+ class voronoi_diagram; 
+ 
+ 
+ <table style="text-align: left; width: 100%;" border="1" cellpadding="2" cellspacing="2">
+ <tbody>
+ <tr>
+ <td style="vertical-align: top;">voronoi_diagram() 
+ </td>
+ <td style="vertical-align: top;">Default constructor. 
+ </td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top;">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>
+ <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>
+ <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>
+ <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>
+ <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>
+ <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. 
+The reason is that we have two half-edges for each Voronoi edge. 
+ </td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top;">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. 
+ </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 member functions is following: 
+ 
+ template <typename T> 
+ class voronoi_edge; 
+ 
+ 
+ <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;">voronoi_edge() 
+ </td>
+ <td style="vertical-align: top;">Default constructor. 
+ </td>
+ </tr>
+ <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>
+ </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>
+ </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>
+ </tr>
+ <tr>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">voronoi_vertex_type *vertex0() 
+ </td>
+ <td style="vertical-align: top;">Returns pointer to the start point of the edge. 
+If edge is infinite in that direction returns NULL. 
+ </td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">const voronoi_vertex_type *vertex0() const 
+ </td>
+ <td style="vertical-align: top;">Returns const pointer to the start point of the edge. 
+If edge is infinite in that direction returns NULL. 
+ </td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">void vertex0(voronoi_vertex_type *v) 
+ </td>
+ <td style="vertical-align: top;">Sets start point pointer of the edge. 
+ </td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">voronoi_vertex_type *vertex1() 
+ </td>
+ <td style="vertical-align: top;">Returns pointer to the end point of the edge. 
+If edge is infinite in that direction returns NULL. 
+ </td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">const voronoi_vertex_type *vertex1() const 
+ </td>
+ <td style="vertical-align: top;">Returns const pointer to the end point of the edge. 
+If edge is infinite in that direction returns NULL. 
+ </td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">void vertex1(voronoi_vertex_type *v) 
+ </td>
+ <td style="vertical-align: top;">Sets end point pointer of the edge. 
+ </td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">voronoi_edge_type *twin() 
+ </td>
+ <td style="vertical-align: top;">Returns pointer  to the twin edge. 
+ </td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">const voronoi_edge_type *twin() const 
+ </td>
+ <td style="vertical-align: top;">Returns const pointer to the twin edge. 
+ </td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">void twin(voronoi_edge_type *e) 
+ </td>
+ <td style="vertical-align: top;">Sets twin edge pointer of the edge. 
+ </td>
+ </tr>
+ <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. 
+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. 
+Edges not necessarily share a common vertex. 
+ </td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">void next(voronoi_edge_type *e) 
+ </td>
+ <td style="vertical-align: top;">Sets CCW next edge pointer of the edge. 
+ </td>
+ </tr>
+ <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. 
+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. 
+Edges not necessarily share a common vertex. 
+ </td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">void prev(voronoi_edge_type *e) 
+ </td>
+ <td style="vertical-align: top;">Sets CCW prev edge pointer of the edge. 
+ </td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">void *data() 
+ </td>
+ <td style="vertical-align: top;">Returns pointer to the data associated with the edge. 
+ </td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">const void *data() const 
+ </td>
+ <td style="vertical-align: top;">Returns const pointer to the data associated with the edge. 
+ </td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">void data(void *d) const 
+ </td>
+ <td style="vertical-align: top;">Sets data pointer of the edge. 
+This allows user to associate any data type with the edge. 
+ </td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">voronoi_edge_type *rot_next() 
+ </td>
+ <td style="vertical-align: top;">Returns pointer to the CCW next edge rotated around the edge start point. 
+If edge is infinite in that direction returns NULL. 
+ </td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">const voronoi_edge_type *rot_next() const 
+ </td>
+ <td style="vertical-align: top;">Returns const pointer to the CCW next edge rotated around the edge start point. 
+
+If edge is infinite in that direction returns NULL.</td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">voronoi_edge_type *rot_prev() 
+ </td>
+ <td style="vertical-align: top;">Returns pointer to the CCW prev edge rotated around the edge start point. 
+If edge is infinite in that direction returns NULL. 
+ </td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">const voronoi_edge_type *rot_prev() const 
+ </td>
+ <td style="vertical-align: top;">Returns const pointer to the CCW prev edge rotated around the edge start point. 
+
+
+If edge is infinite in that direction returns NULL.</td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">bool is_finite() const 
+ </td>
+ <td style="vertical-align: top;">Returns true if both endpoints of the edge are finite, else false. 
+ </td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">bool is_linear() const 
+ </td>
+ <td style="vertical-align: top;">Returns true if edge is linear (segment, ray, line), else false. 
+ </td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">bool is_curved() const 
+ </td>
+ <td style="vertical-align: top;">Returns true if edge is curved (parabolic arc), else false. 
+ </td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">bool is_primary() const 
+ </td>
+ <td style="vertical-align: top;">Returns false if the edge goes through segment endpoint, else true. 
+ </td>
+ </tr>
+ </tbody>
+ </table>
+ 
+ All the above methods have O(1) complexity. The size of the Voronoi edge structure is equal to: 6 * sizeof(void *). 
+ <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 member functions is
+following: 
+ 
+ template <typename T> 
+class voronoi_cell; 
+ 
+ 
+ <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;">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>
+ </tr>
+ <tr>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">voronoi_cell(const point_type &p1, 
+             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>
+ </tr>
+ <tr>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">const point_type &point0() const 
+ </td>
+ <td style="vertical-align: top;">If cell contains point site returns it. 
+If cell contains segment site returns its first endpoint. 
+ </td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">const point_type &point1() const 
+ </td>
+ <td style="vertical-align: top;">If cell contains point site returns it. 
+If cell contains segment site returns its second endpoint. 
+ </td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">voronoi_edge_type *incident_edge() 
+ </td>
+ <td style="vertical-align: top;">Returns pointer to one of the boundary edges. 
+ </td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">const voronoi_edge_type *incident_edge() const 
+ </td>
+ <td style="vertical-align: top;">Returns const pointer to one of the boundary edges. 
+ </td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">void incident_edge(voronoi_edge_type *e) 
+ </td>
+ <td style="vertical-align: top;">Sets incident boundary edge pointer of the cell. 
+ </td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">void *data() 
+ </td>
+ <td style="vertical-align: top;">Returns pointer to the data associated with the cell. 
+ </td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">const void *data() const 
+ </td>
+ <td style="vertical-align: top;">Returns const pointer to the data associated with the cell.</td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">void data(void *d) const 
+ </td>
+ <td style="vertical-align: top;">Sets data pointer of the cell. 
+
+This allows user to associate any data type with the cell.</td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">bool contains_point() const</td>
+ <td style="vertical-align: top;">Returns true if cell contains point site, else false.</td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">bool contains_segment() const</td>
+ <td style="vertical-align: top;">Returns true if cell contains segment site, else false.</td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">bool is_degenerate() const </td>
+ <td style="vertical-align: top;">Returns true if cell doesn't have incident edge. 
+
+Could happen if a few input segments share a common endpoint.</td>
+ </tr>
+ </tbody>
+ </table>
+ 
+ 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). 
+ <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
+functions is following: 
+ 
+ template <typename T> 
+ class voronoi_vertex; 
+ 
+ 
+ <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;">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>
+ </tr>
+ <tr>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">const point_type &vertex() const 
+ </td>
+ <td style="vertical-align: top;">Returns point that represents vertex. 
+ </td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">voronoi_edge_type *incident_edge() 
+ </td>
+ <td style="vertical-align: top;">Returns incident edge pointer. 
+ </td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">const voronoi_edge_type *incident_edge() const 
+ </td>
+ <td style="vertical-align: top;">Returns const pointer to the incident edge. 
+ </td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">void incident_edge(voronoi_edge_type *e) 
+ </td>
+ <td style="vertical-align: top;">Sets incident edge pointer. 
+ </td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">void *data() 
+ </td>
+ <td style="vertical-align: top;">Returns pointer to the data associated with the vertex.</td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">const void *data() const 
+ </td>
+ <td style="vertical-align: top;">Returns const pointer to the data associated with the vertex.</td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">void data(void *d) const 
+ </td>
+ <td style="vertical-align: top;">Sets data pointer of the cell. 
+
+
+This allows user to associate any data type with the vertex.</td>
+ </tr>
+ </tbody>
+ </table>
+ 
+ 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). 
+ <h1>Voronoi Diagram Traits 
+ </h1>
+
+Voronoi diagram traits are used to configure Voronoi diagram data
+structure. The declaration and list of required type definitions is
+following: 
+ 
+ template <typename T> 
+ struct voronoi_diagram_traits; 
+ 
+ 
+ <table style="text-align: left; width: 100%;" border="1" cellpadding="2" cellspacing="2">
+ <tbody>
+ <tr>
+ <td style="vertical-align: top;">coordinate_type 
+ </td>
+ <td style="vertical-align: top;">The main coordinate type of the voronoi diagram internal structures. 
+ </td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top;">ctype_converter_type 
+ </td>
+ <td style="vertical-align: top;">Coordinate type converter structure. 
+Converts coordinates provided by Voronoi builder to the internal coordinate type. 
+ </td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top;">point_type 
+ </td>
+ <td style="vertical-align: top;">2D point data structure. 
+ </td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top;">cell_type 
+ </td>
+ <td style="vertical-align: top;">Voronoi cell type. 
+ </td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top;">vertex_type 
+ </td>
+ <td style="vertical-align: top;">Voronoi vertex_type. 
+ </td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top;">edge_type 
+ </td>
+ <td style="vertical-align: top;">Voronoi edge_type. 
+ </td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top;">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. 
+ </td>
+ </tr>
+ </tbody>
+ </table>
+
+
+
+
+
+</td>
+ </tr>
+ <tr>
+ <td style="background-color: rgb(238, 238, 238);" nowrap="1" valign="top"> </td>
+ <td style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;" valign="top" width="100%">
+ <table class="docinfo" id="table2" 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>
+ </td>
+ </tr>
+</tbody></table>
+
+</body></html>
\ No newline at end of file

Modified: sandbox/gtl/doc/voronoi_predicates.htm
==============================================================================
--- sandbox/gtl/doc/voronoi_predicates.htm (original)
+++ sandbox/gtl/doc/voronoi_predicates.htm 2012-03-18 14:15:23 EDT (Sun, 18 Mar 2012)
@@ -8,12 +8,13 @@

+
<meta http-equiv="Content-Language" content="en-us">
<meta http-equiv="Content-Type" content="text/html; charset=windows-1252"><title>Contents</title></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);" valign="top" nowrap="1">
+ <td style="background-color: rgb(238, 238, 238);" nowrap="1" valign="top">
 <div style="padding: 5px;" align="center">
 <img src="images/boost.png" border="0" height="86" width="277"><a title="www.boost.org home page" tabindex="2" style="border: medium none ;" href="http://www.boost.org/">
 </a></div>
@@ -87,19 +88,26 @@
 
 
 <h1>Voronoi Predicates 
-</h1>In mathematical theory predicate is an operator which returns true or false. 
+</h1>In mathematical theory predicate is an operator which returns true
+or false (e.g. it may answer a question: "is it sunny today?"). 
Voronoi predicates contain implementation of a set of geometric
predicates used by Voronoi builder. Except of those it also provides
functors that allow to compute coordinates of centers of inscribed
circles (those correspond to the voronoi vertices) within the given
-relative error precision range for both point and segment inputs. This
+relative error precision range. This means that the more mantissa bits
+your floating point type has the better precision of the output
+geometries you'll get. This
is a very handy functionality as it allows to improve output precision
simply providing 3rd party IEEE-754 like floating-point types. 
 <h1>Geometric Predicates</h1>
The main issues with implementation of any complex geometric
-algorithm arise when dealing with robustness of geometric predicates. Usually this
-is also the point where commercial projects stand strong agains noncommercial implementations (it's not the case with Voronoi).
-For the short example let's consider following code snippet, that could be used to compute orientation of three points: 
+algorithm arise when dealing with robustness of geometric predicates.
+Usually this
+is also the point where commercial projects stand strong agains
+noncommercial implementations (it's not the case with our
+implementation).
+For the short example let's consider following code snippet, that could
+be used to compute orientation of three points: 
 
 double cross_product(double dx1, double dy1, double dx2, double dy2) { 
   return dx1 * dy2 - dx2 * dy1; 
@@ -126,22 +134,21 @@
precision computations. 

 <h1>Lazy Arithmetic</h1>Lazy
-arithmetic is based on usage of IEEE-754 floating-point types to
-compute expression results. While this approach has a good speed
+arithmetic is based on usage of IEEE-754 floating-point types to evaluate an expression. While this approach has a good speed
performance it doesn't produce reliable results all the time (as in the
example above). The way to solve the issue is apart from computing
result of the expression compute the relative error of it also. This will
give us the range of values evaluated result belongs to and based on that we can
come up with two decisions: 1) output the value; 2) recompute the
-expression using multi precision types. The way relative errors are
+expression using multi precision type. The way relative errors are
evaluated is explained in the Voronoi Robust FPT section. 
<h1>Multiple Precision arithmetic</h1>In the vast majority of cases
lazy arithmetic approach produces correct result thus furhter
-processing is not required. In other cases Voronoi specific or user
+processing is not required. In other cases Voronoi defined or user
provided multiple precision types are used to produce correct result.
However even that doesn't solve all the cases. Multiprecision geometric
predicates could be devided onto two categories: 
-1) mathematical transformation of the predicate exists that evaluates exact results: 
+1) mathematical transformation of the predicate exists that evaluates exact result: 
 
Predicate: A/B + C/D ?< 0; 
After math. transform: (A*D + B*C) / (B * D) ?< 0; 
@@ -150,7 +157,7 @@
After math. transform: A ?< 1.44; 
 
 2) the correct result could be produced only by increasing
-precision of the multiprecision types and with defined relative error
+precision of the multiprecision type and with defined relative error
for the output type: 
 
 Predicate: sqrt(A) + sqrt(B) + sqrt(C) + sqrt(D) + sqrt(E) ?< 1.2; 
@@ -159,10 +166,9 @@
 Predicate: sin(x) ?< 0.57; 
Relativer error of sin function should be known; 
 
- Voronoi of points could be implemented using only the
-predicates of the first type, however Voronoi of segments could not.
+ Voronoi of points could be implemented using only predicates of the first type, however Voronoi of segments could not.
The predicate that doesn't fall into the first category is responsible
-for Voronoi circle comparison. However it appears that properly used
+for comparison of Voronoi circle events. However it appears that properly used
this predicate can't corrupt algorithm internal structures and produces
output technically the same as produced in case this predicate falt in
the first category.  The main reasons for this are: 1) algorithm
@@ -171,7 +177,7 @@
data structure (this won't influence main targets algorithm is used
for). 
 
-</td></tr><tr><td style="background-color: rgb(238, 238, 238);" valign="top" nowrap="1"> 
+</td></tr><tr><td style="background-color: rgb(238, 238, 238);" nowrap="1" valign="top"> 
</td><td style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;" valign="top" width="100%"><table class="docinfo" id="table2" frame="void" rules="none"><tbody valign="top"><tr><th class="docinfo-name">Copyright:</th>
 <td>Copyright © Intel Corporation 2008-2010.</td>
 </tr>

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-18 14:15:23 EDT (Sun, 18 Mar 2012)
@@ -9,12 +9,13 @@

+
<meta http-equiv="Content-Language" content="en-us">
<meta http-equiv="Content-Type" content="text/html; charset=windows-1252"><title>Contents</title></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);" valign="top" nowrap="1">
+ <td style="background-color: rgb(238, 238, 238);" nowrap="1" valign="top">
 <div style="padding: 5px;" align="center">
 <img src="images/boost.png" border="0" height="86" width="277"><a title="www.boost.org home page" tabindex="2" style="border: medium none ;" href="http://www.boost.org/">
 </a></div>
@@ -90,25 +91,25 @@
 
 <h1>Voronoi Robust FPT</h1>
 Voronoi
-robust floating-point types represents set of classes and tools that
+robust floating-point types are set of classes and tools that
allow to estimate relative error of arithmetic expressions. It is
assumed that other Boost libraries may find this unit functionality
extremely useful. One can use them to implement robust and efficient
-arithmetic predicates or functors that compute values with predefined
+arithmetic predicates or functors that compute values with known
relative error. 

 <h1>Robust Fpt Type</h1>
Robust
fpt (robust floating-point type)
- represents IEEE-754 floating-point type wrapper that also contains
-information on the current relative error of underlying value. The
+information about relative error of the underlying value. The
implementation overloads 5 standard operations: +, -, *, /, sqrt and
-apart from evaluating expression value also computes its relativer
+apart from evaluating value of the expression also computes its relativer
error. Let's consider two values A and B; C - rounding error; re
- correspond to relative error, then following rules apply: 
 
 re(A+B) <= max(re(A), re(B)) + C, if A * B >= 0; 
- re(A-B) <= (B * re(A) + A * re(B)) / |A-B| + C, if A * B < 0; 
+ re(A-B) <= (B * re(A) + A * re(B)) / |A - B| + C, if A * B < 0; 
 re(A*B) <= re(A) + re(B) + C; 
 re(A/B) <= re(A) + re(B) + C; 
 re(sqrt(A)) <= re(A) * 0.5 + C; 
@@ -118,15 +119,19 @@
floating-point implementation should be equal to 1 machine epsilon. 

- <h1>Robust Difference Type</h1>Robust difference type -
+ <h1>Robust Difference Type</h1>Robust
+difference type -
represents expression wrapper that holds positive and negative partial
sums of the expression in a separate values in order to avoid
-cancellation errors before evaluating final difference. 
+cancellation errors before evaluating final difference. Following
+arithmetic operators are overloaded for the robust difference type: +,
+-, *, / (division operator is not overloaded for the case were both
+arguments have robust difference type). 
Looking at the relative error formulas above one may notice a few facts about them: 
-1) all of the formulas evaluate upper bound of the relative error, while it could be a lot smaller; 
-2) relative error estimate of the expression depends on the order operations are evaluated; 
+1) all of the formulas evaluate upper bound of the relative error, while it could be a lot lower; 
+2) relative error of the expression depends on the order operations are evaluated; 
3) relative error of difference of two positive numbers may be
-exteremely large in case threir values are close to each other (this is
+exteremely large in case their values are close to each other (this is
also called cancellation error). 
To explain this a bit consider following experssion (~ - stands for almost equal, << - many times larger than): 
 
@@ -134,7 +139,7 @@
 
Computing relative error of this expression from left to right will produce extremely large relative error: 
 
- re(A-B+C) = max(re(A-B), re(C)) = re(A-B) = INF; 
+ re(A-B+C) = max(re(A-B), re(C)) = re(A-B) = (B * re(A) + A * re(B)) / 0 = INF; 
 
 While doing this from right to left will keep relative error value small: 
 
@@ -142,14 +147,13 @@
 
 While both estimates are valid (they define upper bound of the relative error), of course the second one is preferable. 
Here is the place where robust difference type comes useful. Basically
-it splits the expression values onto positive and negative, partially
-overloads four arithmetic operations: +,-,*,/ and evaluates the
+it splits expression onto positive and negative partial sums and evaluates the
diference only when the result is required. And did I mention that
positive and negative values might be of robust fpt type, that's why
relative error is always known for the expression result. 
<h1>Robust Sqrt Expression Structure</h1>
-Robust square root expression structure allows evaluate results of
-expressions that contain square roots with predefined relative error.
+Robust square root expression structure allows to compute results of
+expression that contains square roots with predefined relative error.
As an example consider following expression: 
 
 A * sqrt(a) - B * sqrt(b), A * B > 0, a >= 0, b >= 0; 
@@ -160,7 +164,7 @@
(A * A * a - B * B * b) / (A * sqrt(a) + B * sqrt(b)); 
 
Numerator and denominator of this epxression could be computed directly as those won't lead to the cancellation errors. 
-In general case robust sqrt expression structure allows to evaluate next set of expressions: 
+In general case robust sqrt expression structure allows to evaluate following set of expressions: 
 
sum(A[i] * sqrt(a[i]), i = 1 .. N), N <= 4; 
 
@@ -171,7 +175,7 @@
</td>
 </tr>
 <tr>
- <td style="background-color: rgb(238, 238, 238);" valign="top" nowrap="1"> </td>
+ <td style="background-color: rgb(238, 238, 238);" nowrap="1" valign="top"> </td>
 <td style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;" valign="top" width="100%">
 <table class="docinfo" id="table2" frame="void" rules="none">
 <colgroup>

Modified: sandbox/gtl/doc/voronoi_utils.htm
==============================================================================
--- sandbox/gtl/doc/voronoi_utils.htm (original)
+++ sandbox/gtl/doc/voronoi_utils.htm 2012-03-18 14:15:23 EDT (Sun, 18 Mar 2012)
@@ -14,6 +14,8 @@

+
+
<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>

@@ -96,8 +98,8 @@
 <h1>Voronoi Utils</h1>Voronoi
utilities imlements a set of tools that users may find useful
especially for
-the visualization of Voronoi diagrams or interpolation of the parabolic
-edges. All the methods within the utilities class are static. Class
+the visualization of Voronoi diagrams or discretization of parabolic
+edges. Keep in mind that there are no robustness warranties to the methods of the utils class. Class
declaration is following: 
 
template <typename T, typename TRAITS = voronoi_utils_traits<T> > 
@@ -105,55 +107,141 @@
 
 T - output coordinate type used by the utilities. 
 TRAITS - output geometries type traits (see definition below). 
-<h2 style="color: rgb(0, 0, 0); font-family: 'Times New Roman'; font-style: normal; font-variant: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px;">EdgeType</h2>EdgeType
-enumerator is used to categorise straight linear primitive based on the
-finity of its endpoints. There are three possible values: segment, ray,
-line. 
- 
- enum EdgeType { SEGMENT = 0, RAY = 1, LINE = 2 }; 
+
<h2 style="color: rgb(0, 0, 0); font-family: 'Times New Roman'; font-style: normal; font-variant: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px;">Member Functions</h2>

 <table style="text-align: left; width: 100%;" border="1" cellpadding="2" cellspacing="2">
 <tbody>
 <tr>
 <td style="vertical-align: top;">template <typename CT> 
- static brect_type scale(const bounding_rectangle<CT> &brect, fpt_type factor = 1.0) 
+ static brect_type scale_bounding_rectangle( 
+    const bounding_rectangle<CT> &brect, 
+    fpt_type factor = 1.0) 
 </td>
- <td style="vertical-align: top;">Returns scaled bounding rectangle. The center of transformation corresponds to the center of the input rectangle. 
+ <td style="vertical-align: top;">Returns scaled bounding rectangle. 
+The center of transformation corresponds to the center of the input rectangle. 
 </td>
 </tr>
 <tr>
- <td style="vertical-align: top;">template <typename CT> 
- static void discretize(const voronoi_edge<CT> *edge, const bounding_rectangle<CT> &brect, fpt_type max_error, point_set_type &interpolation) 
+ <td style="vertical-align: top;">template <typename CT> 
+static void discretize_finite_edge( 
+    const voronoi_edge<CT> &edge, 
+    coordinate_type max_error, 
+    point_set_type &discretization) 
+ </td>
+ <td style="vertical-align: top;">Provides point discretization of the input voronoi edge. 
+If the edge is infinite (ray, line) doesn't fill output point set. 
+Max error specifies maximum distance that is allowed between original parabolic arc and its approximation. 
+
 </td>
- <td style="vertical-align: top;">Provides point discretization of the input voronoi edge. 
-Finite edges are not clipped at all. Infinite edges (at least one of
-the endpoints is not finite) are clipped by the bounding rectangle. 
-For linear edges fills output set with edge endpoints. 
-For parabolic edges fills output set with edge discretization
-satisfying max distance requirement equal to max_error *
-brect.min_len(). 
+ </tr>
+ <tr>
+ <td style="vertical-align: top;">template <typename CT> 
+static void clip_linear_edge( 
+    const voronoi_edge<CT> &edge, 
+    const brect_type &brect, 
+    point_set_type &clipped_edge) 
+ </td>
+ <td style="vertical-align: top;">Clips the input voronoi edges with specified rectangle. 
+If the edge is a parabolic arc doesn't fill output point set. 
+ </td>
+ </tr><tr>
+ <td style="vertical-align: top;">template <typename PointType> 
+ static void clip_linear_edge( 
+    const PointType &p1, 
+    const PointType &p2, 
+    const brect_type &brect, 
+    point_set_type &clipped_edge) 
+ </td>
+ <td style="vertical-align: top;">Clips the input linear edge with specified rectangle. 
+Edge is defined by its endpoints. 
+ </td>
+ </tr>

+ </tbody>
+ </table><h1>Bounding Rectangle</h1>The module provides implementation of a simple bounding rectangle structure with following declaration: 
+ 
+ template <typename T> 
+ class bounding_rectangle; 
+ 
+T - coordinate type rectangle operates with. 
+ <h2 style="color: rgb(0, 0, 0); font-family: 'Times New Roman'; font-style: normal; font-variant: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px;">Member Functions</h2>
+ <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;">bounding_rectangle() 
+ </td>
+ <td style="vertical-align: top;">Default constructor. Initializes empty bounding rectangle. 
+ </td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">bounding_rectangle( 
+    coordinate_type x1, 
+    coordinate_type y1, 
+    coordinate_type x2, 
+    coordinate_type y2) 
+ </td>
+ <td style="vertical-align: top;">Constructs bounding rectangle with given coordinates. 
+ </td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">void update( 
+    coordinate_type x, 
+    coordinate_type y) 
+ </td>
+ <td style="vertical-align: top;">Extends bounding rectangle with a specified point defined by its coordinates. 
+If the rectangle is empty sets coordinates of the bottom left and top right corners. 
+ </td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">bool is_empty() const 
+ </td>
+ <td style="vertical-align: top;">Returns true if rectangle is empty (there were no updates), else false. 
+ </td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">void clear() 
+ </td>
+ <td style="vertical-align: top;">Sets rectangle to an empty state. 
+ </td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">bool contains( 
+   coordinate_type x, 
+   coordinate_type y) const 
+ </td>
+ <td style="vertical-align: top;">Retruns true if rectangle contains giveт point defined by its coordinates, else false. 
 </td>
 </tr>
 <tr>
- <td style="vertical-align: top;">static
-void intersect(const point_type &origin, const point_type
-&direction, EdgeType edge_type, const brect_type &brect,
-point_set_type &intersections) 
- </td>
- <td style="vertical-align: top;">Fills
-the output structure with the intersection points of input linear
-primitive and bounding rectangle. Based on the EdgeType origin and
-direction mean following: 
-SEGMENT: origin - start-point, direction - vector going from start-point to endpoint; 
-RAY: origin - start-point, direction - ray vector; 
-LINE: origin - point on a line, direction - line vector. 
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">coordinate_type x_min() const 
+ </td>
+ <td style="vertical-align: top;">Returns x coordinate of the bottom left corner of rectangle. 
+ </td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">coordinate_type y_min() const 
+ </td>
+ <td style="vertical-align: top;">Returns y coordinate of the bottom left corner of rectangle. 
+ </td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">coordinate_type x_max() const 
+ </td>
+ <td style="vertical-align: top;">Returns x coordinate of the top right corner of rectangle. 
+ </td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">coordinate_type y_max() const 
+ </td>
+ <td style="vertical-align: top;">Returns y coordinate of the top right corner of rectangle. 
 </td>
 </tr>
 </tbody>
- </table><h1>Voronoi Utils Traits 
-</h1>Below is shown the default voronoi utilities traits: 
+ </table>
+ <h1>Voronoi Utils Traits 
+ </h1>
+Below is shown the default voronoi utilities traits: 
 
 template <typename fpt_> 
 struct voronoi_utils_traits; 
@@ -174,7 +262,7 @@
 
 Most of the types define output geometries.
ctype_converter_type is used to cast coordinate type of the input
-primitives to the one used by the utilities. 
+primitives to the one used internally.

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