|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r80506 - in trunk: boost/polygon libs/polygon/doc libs/polygon/test
From: sydorchuk.andriy_at_[hidden]
Date: 2012-09-12 15:00:42
Author: asydorchuk
Date: 2012-09-12 15:00:40 EDT (Wed, 12 Sep 2012)
New Revision: 80506
URL: http://svn.boost.org/trac/boost/changeset/80506
Log:
Polygon: Removing redundant comments; Updating voronoi_diagram source/documentation.
Text files modified:
trunk/boost/polygon/voronoi.hpp | 16 ++------
trunk/boost/polygon/voronoi_builder.hpp | 4 +-
trunk/boost/polygon/voronoi_diagram.hpp | 45 ++++++++----------------
trunk/libs/polygon/doc/voronoi_diagram.htm | 72 ++++++++++++++++++---------------------
trunk/libs/polygon/test/voronoi_diagram_test.cpp | 14 ++++---
5 files changed, 64 insertions(+), 87 deletions(-)
Modified: trunk/boost/polygon/voronoi.hpp
==============================================================================
--- trunk/boost/polygon/voronoi.hpp (original)
+++ trunk/boost/polygon/voronoi.hpp 2012-09-12 15:00:40 EDT (Wed, 12 Sep 2012)
@@ -18,17 +18,11 @@
#include "voronoi_diagram.hpp"
// Public methods to compute Voronoi diagram.
-// PC - container of input points (should supports forward iterator).
-// SC - container of input segments (should supports forward iterator).
-// output - Voronoi output data structure to hold Voronoi diagram.
-// Segment class should provide low(), high() methods to access its endpoints.
-// The assumption is made that input doesn't contain segments that intersect
-// or points lying on the segments. Also coordinates of the points and of the
-// endpoints of the segments should belong to the signed integer range
-// [-2^31, 2^31-1]. To use wider input coordinate range use voronoi_builder
-// structure with user provided coordinate type traits.
-// Complexity - O(N*logN), memory usage - O(N),
-// where N is the total number of points and segments.
+// Coordinates of the points and of the endpoints of the segments should belong
+// to the 32-bit signed integer range [-2^31, 2^31-1]. To use wider input
+// coordinate range voronoi_builder configuration via coordinate type traits is
+// is required.
+// Complexity - O(N*logN), memory usage - O(N), N - number of input objects.
namespace boost {
namespace polygon {
Modified: trunk/boost/polygon/voronoi_builder.hpp
==============================================================================
--- trunk/boost/polygon/voronoi_builder.hpp (original)
+++ trunk/boost/polygon/voronoi_builder.hpp 2012-09-12 15:00:40 EDT (Wed, 12 Sep 2012)
@@ -39,8 +39,8 @@
// leftmost event is retrieved by comparing the current site event and the
// topmost element from the circle event queue. STL map (red-black tree)
// container was chosen to hold state of the beach line. The keys of the map
-// correspond to the neighboring sites that form a bisector and values to the
-// corresponding Voronoi edge in the output data structure.
+// correspond to the neighboring sites that form a bisector and values map to
+// the corresponding Voronoi edges in the output data structure.
template <typename T,
typename CTT = detail::voronoi_ctype_traits<T>,
typename VP = detail::voronoi_predicates<CTT> >
Modified: trunk/boost/polygon/voronoi_diagram.hpp
==============================================================================
--- trunk/boost/polygon/voronoi_diagram.hpp (original)
+++ trunk/boost/polygon/voronoi_diagram.hpp 2012-09-12 15:00:40 EDT (Wed, 12 Sep 2012)
@@ -40,11 +40,10 @@
typedef std::size_t source_index_type;
typedef SourceCategory source_category_type;
- voronoi_cell(const source_index_type& source_index,
- const source_category_type& source_category,
- voronoi_edge_type* edge) :
+ voronoi_cell(source_index_type source_index,
+ source_category_type source_category) :
source_index_(source_index),
- incident_edge_(edge),
+ incident_edge_(NULL),
color_(source_category) {}
// Returns true if the cell contains point site, false else.
@@ -104,12 +103,10 @@
typedef std::size_t color_type;
typedef voronoi_edge<coordinate_type> voronoi_edge_type;
- voronoi_vertex(const coordinate_type& x,
- const coordinate_type& y,
- voronoi_edge_type* edge) :
+ voronoi_vertex(const coordinate_type& x, const coordinate_type& y) :
x_(x),
y_(y),
- incident_edge_(edge),
+ incident_edge_(NULL),
color_(0) {}
const coordinate_type& x() const { return x_; }
@@ -181,7 +178,6 @@
voronoi_vertex_type* vertex1() { return twin_->vertex0(); }
const voronoi_vertex_type* vertex1() const { return twin_->vertex0(); }
- void vertex1(voronoi_vertex_type* v) { twin_->vertex0(v); }
voronoi_edge_type* twin() { return twin_; }
const voronoi_edge_type* twin() const { return twin_; }
@@ -197,21 +193,13 @@
// Returns a pointer to the rotation next edge
// over the starting point of the half-edge.
- voronoi_edge_type* rot_next() {
- return prev_->twin();
- }
- const voronoi_edge_type* rot_next() const {
- return prev_->twin();
- }
+ voronoi_edge_type* rot_next() { return prev_->twin(); }
+ const voronoi_edge_type* rot_next() const { return prev_->twin(); }
// Returns a pointer to the rotation prev edge
// over the starting point of the half-edge.
- voronoi_edge_type* rot_prev() {
- return twin_->next();
- }
- const voronoi_edge_type* rot_prev() const {
- return twin_->next();
- }
+ voronoi_edge_type* rot_prev() { return twin_->next(); }
+ const voronoi_edge_type* rot_prev() const { return twin_->next(); }
// Returns true if the edge is finite (segment, parabolic arc).
// Returns false if the edge is infinite (ray, line).
@@ -300,15 +288,12 @@
typedef typename TRAITS::edge_type edge_type;
typedef std::vector<cell_type> cell_container_type;
- typedef typename cell_container_type::iterator cell_iterator;
typedef typename cell_container_type::const_iterator const_cell_iterator;
typedef std::vector<vertex_type> vertex_container_type;
- typedef typename vertex_container_type::iterator vertex_iterator;
typedef typename vertex_container_type::const_iterator const_vertex_iterator;
typedef std::vector<edge_type> edge_container_type;
- typedef typename edge_container_type::iterator edge_iterator;
typedef typename edge_container_type::const_iterator const_edge_iterator;
voronoi_diagram() {}
@@ -351,8 +336,7 @@
template <typename CT>
void _process_single_site(const detail::site_event<CT>& site) {
- cells_.push_back(cell_type(
- site.initial_index(), site.source_category(), NULL));
+ cells_.push_back(cell_type(site.initial_index(), site.source_category()));
}
// Insert a new half-edge into the output data structure.
@@ -380,13 +364,13 @@
// Add the initial cell during the first edge insertion.
if (cells_.empty()) {
cells_.push_back(cell_type(
- site1.initial_index(), site1.source_category(), NULL));
+ site1.initial_index(), site1.source_category()));
}
// The second site represents a new site during site event
// processing. Add a new cell to the cell records.
cells_.push_back(cell_type(
- site2.initial_index(), site2.source_category(), NULL));
+ site2.initial_index(), site2.source_category()));
// Set up pointers to cells.
edge1.cell(&cells_[site_index1]);
@@ -416,7 +400,7 @@
edge_type* edge23 = static_cast<edge_type*>(data23);
// Add a new Voronoi vertex.
- vertices_.push_back(vertex_type(circle.x(), circle.y(), NULL));
+ vertices_.push_back(vertex_type(circle.x(), circle.y()));
vertex_type& new_vertex = vertices_.back();
// Update vertex pointers of the old edges.
@@ -566,6 +550,9 @@
}
private:
+ typedef typename cell_container_type::iterator cell_iterator;
+ typedef typename vertex_container_type::iterator vertex_iterator;
+ typedef typename edge_container_type::iterator edge_iterator;
typedef typename TRAITS::vertex_equality_predicate_type
vertex_equality_predicate_type;
Modified: trunk/libs/polygon/doc/voronoi_diagram.htm
==============================================================================
--- trunk/libs/polygon/doc/voronoi_diagram.htm (original)
+++ trunk/libs/polygon/doc/voronoi_diagram.htm 2012-09-12 15:00:40 EDT (Wed, 12 Sep 2012)
@@ -11,6 +11,7 @@
+
<meta http-equiv="Content-Language" content="en-us">
@@ -244,12 +245,7 @@
<td>Container of Voronoi cells.<br>
</td>
</tr>
- <tr>
- <td style="font-weight: bold;">cell_iterator<br>
- </td>
- <td>Cell container iterator.<br>
- </td>
- </tr>
+
<tr>
<td style="font-weight: bold;">const_cell_iterator<br>
</td>
@@ -262,12 +258,7 @@
<td>Container of Voronoi vertices.<br>
</td>
</tr>
- <tr>
- <td style="font-weight: bold;">vertex_iterator<br>
- </td>
- <td>Vertex container iterator.<br>
- </td>
- </tr>
+
<tr>
<td style="font-weight: bold;">const_vertex_iterator<br>
</td>
@@ -280,12 +271,7 @@
<td>Container of Voronoi edges.<br>
</td>
</tr>
- <tr>
- <td style="font-weight: bold;">edge_iterator<br>
- </td>
- <td>Edge container iterator.<br>
- </td>
- </tr>
+
<tr>
<td style="font-weight: bold;">const_edge_iterator<br>
</td>
@@ -372,6 +358,12 @@
<tbody>
<tr>
+ <td><span style="font-family: Courier New,Courier,monospace;"><span style="font-weight: bold;">voronoi_edge</span>(bool is_linear, bool is_primary)</span><br>
+ </td>
+ <td>Voronoi edge constructor.<br>
+ </td>
+ </tr>
+<tr>
<td style="font-family: Courier New,Courier,monospace;">voronoi_cell_type* <span style="font-weight: bold;">cell</span>()<br>
</td>
<td>Returns the pointer to the
@@ -437,14 +429,7 @@
If the edge is infinite in that direction returns NULL.<br>
</td>
</tr>
- <tr>
- <td style="font-family: Courier New,Courier,monospace;">void
- <span style="font-weight: bold;">vertex1</span>(voronoi_vertex_type* v)<br>
- </td>
- <td>Sets the end point pointer
-of the edge.<br>
- </td>
- </tr>
+
<tr>
<td style="font-family: Courier New,Courier,monospace;">voronoi_edge_type* <span style="font-weight: bold;">twin</span>()<br>
</td>
@@ -570,9 +555,9 @@
</td>
</tr>
<tr>
- <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">bool
+ <td style="font-family: Courier New,Courier,monospace;">bool
<span style="font-weight: bold;">is_infinite</span>() const</td>
- <td style="vertical-align: top;">Returns true if one of the
+ <td>Returns true if one of the
end points of the edge is infinite, else false.</td>
</tr>
<tr>
@@ -599,9 +584,9 @@
goes through the endpoint of the segment site, else true.<br>
</td>
</tr><tr>
- <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">bool
+ <td style="font-family: Courier New,Courier,monospace;">bool
<span style="font-weight: bold;">is_secondary</span>() const</td>
- <td style="vertical-align: top;">Returns true if the edge
+ <td>Returns true if the edge
goes through the endpoint of the segment site, else false.</td>
</tr>
@@ -670,6 +655,13 @@
<tr>
+ <td><span style="font-family: Courier New,Courier,monospace;"><span style="font-weight: bold;">voronoi_cell</span>(source_index_type source_index,</span><span style="font-family: Courier New,Courier,monospace;"><br>
+ source_category_type source_category)</span><br>
+ </td>
+ <td>Voronoi cell constructor.<br>
+ </td>
+ </tr>
+<tr>
<td style="font-family: Courier New,Courier,monospace;">source_index_type <span style="font-weight: bold;">source_index</span>() const<br>
</td>
<td>Returns input site index among the other sites.<br>
@@ -818,6 +810,13 @@
<tbody>
<tr>
+ <td><span style="font-family: Courier New,Courier,monospace;"><span style="font-weight: bold;">voronoi_vertex</span>(const coordinate_type& x,<br>
+ const coordinate_type& y)</span><span style="font-family: Courier New,Courier,monospace;"></span><br>
+ </td>
+ <td>Voronoi vertex constructor.<br>
+ </td>
+ </tr>
+<tr>
<td style="font-family: Courier New,Courier,monospace;">const
point_type& <span style="font-weight: bold;">x</span>() const<br>
</td>
@@ -825,9 +824,9 @@
</td>
</tr>
<tr>
- <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">const
+ <td style="font-family: Courier New,Courier,monospace;">const
point_type& <span style="font-weight: bold;">y</span>() const</td>
- <td style="vertical-align: top;">Returns the y-coordinate of the point that represents the vertex.<br>
+ <td>Returns the y-coordinate of the point that represents the vertex.<br>
</td>
</tr>
<tr>
@@ -938,12 +937,7 @@
</td>
</tr>
- <tr>
- <td style="font-family: Courier New,Courier,monospace; font-weight: bold;">point_type<br>
- </td>
- <td>2D point data structure.<br>
- </td>
- </tr>
+
<tr>
<td style="font-family: Courier New,Courier,monospace; font-weight: bold;">cell_type<br>
</td>
@@ -997,4 +991,4 @@
</table>
-</body></html>
+</body></html>
\ No newline at end of file
Modified: trunk/libs/polygon/test/voronoi_diagram_test.cpp
==============================================================================
--- trunk/libs/polygon/test/voronoi_diagram_test.cpp (original)
+++ trunk/libs/polygon/test/voronoi_diagram_test.cpp 2012-09-12 15:00:40 EDT (Wed, 12 Sep 2012)
@@ -20,7 +20,7 @@
typedef voronoi_diagram<double> voronoi_diagram_type;
BOOST_AUTO_TEST_CASE(voronoi_cell_test) {
- voronoi_cell_type cell(1, SOURCE_CATEGORY_INITIAL_SEGMENT, NULL);
+ voronoi_cell_type cell(1, SOURCE_CATEGORY_INITIAL_SEGMENT);
cell.color(27);
BOOST_CHECK(!cell.contains_point());
BOOST_CHECK(cell.contains_segment());
@@ -37,7 +37,7 @@
}
BOOST_AUTO_TEST_CASE(voronoi_vertex_test) {
- voronoi_vertex_type vertex(1, 2, NULL);
+ voronoi_vertex_type vertex(1, 2);
vertex.color(27);
BOOST_CHECK(vertex.is_degenerate());
BOOST_CHECK(vertex.x() == 1);
@@ -86,17 +86,19 @@
BOOST_CHECK(edge1.rot_next() == &edge1);
BOOST_CHECK(edge1.rot_prev() == &edge1);
- voronoi_cell_type cell(1, SOURCE_CATEGORY_INITIAL_SEGMENT, NULL);
+ voronoi_cell_type cell(1, SOURCE_CATEGORY_INITIAL_SEGMENT);
edge1.cell(&cell);
BOOST_CHECK(edge1.cell() == &cell);
- voronoi_vertex_type vertex0(1, 2, NULL);
+ voronoi_vertex_type vertex0(1, 2);
edge1.vertex0(&vertex0);
BOOST_CHECK(edge1.vertex0() == &vertex0);
+ BOOST_CHECK(edge2.vertex1() == &vertex0);
- voronoi_vertex_type vertex1(2, 1, NULL);
- edge1.vertex1(&vertex1);
+ voronoi_vertex_type vertex1(2, 1);
+ edge2.vertex0(&vertex1);
BOOST_CHECK(edge1.vertex1() == &vertex1);
+ BOOST_CHECK(edge2.vertex0() == &vertex1);
BOOST_CHECK(edge1.is_finite());
BOOST_CHECK(edge2.is_finite());
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