Subject: [Boost-commit] svn:boost r77278 - in sandbox/gtl: boost/polygon libs/polygon/test
From: sydorchuk.andriy_at_[hidden]
Date: 2012-03-08 19:01:59
Author: asydorchuk
Date: 2012-03-08 19:01:58 EST (Thu, 08 Mar 2012)
New Revision: 77278
URL: http://svn.boost.org/trac/boost/changeset/77278
Log:
Updating voronoi diagram code.
Text files modified:
sandbox/gtl/boost/polygon/voronoi_builder.hpp | 2
sandbox/gtl/boost/polygon/voronoi_diagram.hpp | 233 ++++++++++++++++-----------------------
sandbox/gtl/libs/polygon/test/voronoi_builder_test.cpp | 51 ++++----
sandbox/gtl/libs/polygon/test/voronoi_test_helper.hpp | 2
4 files changed, 123 insertions(+), 165 deletions(-)
Modified: sandbox/gtl/boost/polygon/voronoi_builder.hpp
==============================================================================
--- sandbox/gtl/boost/polygon/voronoi_builder.hpp (original)
+++ sandbox/gtl/boost/polygon/voronoi_builder.hpp 2012-03-08 19:01:58 EST (Thu, 08 Mar 2012)
@@ -164,7 +164,7 @@
beach_line_.clear();
// Clean the output (remove zero-length edges).
- output->clean();
+ output->seal();
}
void clear() {
Modified: sandbox/gtl/boost/polygon/voronoi_diagram.hpp
==============================================================================
--- sandbox/gtl/boost/polygon/voronoi_diagram.hpp (original)
+++ sandbox/gtl/boost/polygon/voronoi_diagram.hpp 2012-03-08 19:01:58 EST (Thu, 08 Mar 2012)
@@ -152,6 +152,9 @@
// Returns true if the cell contains segment site, false else.
bool contains_segment() const { return point0_ != point1_; }
+ // Degenerate cells don't have any incident edges.
+ bool is_degenerate() const { return incident_edge_ == NULL; }
+
// Returns site point in case cell contains point site,
// the first point of the segment site else.
const point_type &point0() const { return point0_; }
@@ -194,6 +197,8 @@
const point_type &vertex() const { return vertex_; }
+ bool is_degenerate() const { return incident_edge_ == NULL; }
+
voronoi_edge_type *incident_edge() { return incident_edge_; }
const voronoi_edge_type *incident_edge() const { return incident_edge_; }
void incident_edge(voronoi_edge_type *e) { incident_edge_ = e; }
@@ -387,7 +392,8 @@
voronoi_diagram() :
num_cells_(0),
num_edges_(0),
- num_vertices_(0) {}
+ num_vertices_(0),
+ sealed_(false) {}
void reserve(int num_sites) {
cells_.reserve(num_sites);
@@ -398,6 +404,8 @@
vertices_.clear();
edges_.clear();
+ sealed_ = false;
+
num_cells_ = 0;
num_edges_ = 0;
num_vertices_ = 0;
@@ -434,6 +442,8 @@
// Update the voronoi output in case of a single point input.
template <typename SEvent>
void process_single_site(const SEvent &site) {
+ if (sealed_) return;
+
// Update bounding rectangle.
point_type p = prepare_point(site.point0());
vrect_ = brect_type(p);
@@ -448,6 +458,8 @@
template <typename SEvent>
std::pair<void*, void*> insert_new_edge(
const SEvent &site1, const SEvent &site2) {
+ if (sealed_) return std::pair<void*, void*>(NULL, NULL);
+
// Get sites' indices.
int site_index1 = site1.index();
int site_index2 = site2.index();
@@ -463,7 +475,6 @@
// Add the initial cell during the first edge insertion.
if (cells_.empty()) {
process_single_site(site1);
- cells_.back().incident_edge(&edge1);
}
// Update the bounding rectangle.
@@ -473,7 +484,7 @@
// processing. Add a new cell to the cell records.
cells_.push_back(cell_type(prepare_point(site2.point0()),
prepare_point(site2.point1()),
- &edge2));
+ NULL));
// Set up pointers to cells.
edge1.cell(&cells_[site_index1]);
@@ -497,13 +508,15 @@
void *insert_new_edge(
const SEvent &site1, const SEvent &site3, const CEvent &circle,
void *data12, void *data23) {
+ if (sealed_) return NULL;
+
edge_type *edge12 = static_cast<edge_type*>(data12);
edge_type *edge23 = static_cast<edge_type*>(data23);
// Add a new voronoi vertex.
coordinate_type x = convert_(circle.x());
coordinate_type y = convert_(circle.y());
- vertices_.push_back(vertex_type(point_type(x, y), edge12));
+ vertices_.push_back(vertex_type(point_type(x, y), NULL));
vertex_type &new_vertex = vertices_.back();
// Update vertex pointers of the old edges.
@@ -539,144 +552,99 @@
return &new_edge1;
}
- // Remove zero-length edges from the voronoi output.
- void clean() {
- edge_iterator edge_it1;
- edge_iterator edge_it = edges_.begin();
- num_cells_ = cells_.size();
-
- // All the initial sites are collinear.
- if (vertices_.empty()) {
- // Update edges counter.
- num_edges_ = num_cells_ - 1;
+ void seal() {
+ if (sealed_) return;
- // Return if there are no edges.
- if (edge_it == edges_.end())
- return;
-
- // Update prev/next pointers of the edges. Those edges won't
- // have any common endpoints, cause they are infinite.
- // But still they follow each other using CCW ordering.
- edge_type *edge1 = &(*edge_it);
- edge1->next(edge1);
- edge1->prev(edge1);
- ++edge_it;
- edge1 = &(*edge_it);
- ++edge_it;
-
- while (edge_it != edges_.end()) {
- edge_type *edge2 = &(*edge_it);
- ++edge_it;
-
- edge1->next(edge2);
- edge1->prev(edge2);
- edge2->next(edge1);
- edge2->prev(edge1);
+ num_cells_ = cells_.size();
+ num_edges_ = edges_.size() >> 1;
+ num_vertices_ = vertices_.size();
- edge1 = &(*edge_it);
- ++edge_it;
+ // Remove degenerate edges.
+ for (edge_iterator it = edges_.begin(); it != edges_.end();) {
+ const vertex_type *v1 = it->vertex0();
+ const vertex_type *v2 = it->vertex1();
+ edge_iterator it_old = it;
+ std::advance(it, 2);
+ if (v1 && v2 && vertex_equality_predicate_(v1->vertex(), v2->vertex())) {
+ remove_edge(&(*it_old));
+ edges_.erase(it_old, it);
+ --num_edges_;
}
-
- edge1->next(edge1);
- edge1->prev(edge1);
- return;
}
- // Iterate over all the edges and remove degeneracies
- // (zero-length edges). Edge is considered to be zero-length
- // if both its endpoints lie within some epsilon-rectangle.
- while (edge_it != edges_.end()) {
- edge_it1 = edge_it;
- std::advance(edge_it, 2);
-
- // Degenerate edges exist only among finite edges.
- if (!edge_it1->vertex0() || !edge_it1->vertex1()) {
- ++num_edges_;
- continue;
- }
-
- const vertex_type *v1 = edge_it1->vertex0();
- const vertex_type *v2 = edge_it1->vertex1();
-
- // Make epsilon robust check.
- if (vertex_equality_predicate_(v1->vertex(), v2->vertex())) {
- // Corresponding cell incident edge pointer
- // points to the degenerate edge.
- if (edge_it1->cell()->incident_edge() == &(*edge_it1)) {
- // Update incident edge pointer.
- if (edge_it1->cell()->incident_edge() ==
- edge_it1->next()) {
- edge_it1->cell()->incident_edge(NULL);
- } else {
- edge_it1->cell()->incident_edge(edge_it1->next());
- }
- }
-
- // Cell corresponding to the twin edge
- // points to the degenerate edge.
- if (edge_it1->twin()->cell()->incident_edge() ==
- edge_it1->twin()) {
- // Update incident edge pointer.
- if (edge_it1->twin()->cell()->incident_edge() ==
- edge_it1->twin()->next()) {
- edge_it1->twin()->cell()->incident_edge(NULL);
- } else {
- edge_it1->twin()->cell()->incident_edge(
- edge_it1->twin()->next());
- }
- }
-
- remove_edge(&(*edge_it1));
-
- // Remove zero-length edge.
- edges_.erase(edge_it1, edge_it);
- } else {
- // Count not degenerate edge.
- ++num_edges_;
+ // Set up incident edge pointers for cells and vertices.
+ for (edge_iterator it = edges_.begin(); it != edges_.end(); ++it) {
+ it->cell()->incident_edge(&(*it));
+ if (it->vertex0()) {
+ it->vertex0()->incident_edge(&(*it));
}
}
- // Remove degenerate voronoi vertices with zero incident edges.
- for (vertex_iterator vertex_it =
- vertices_.begin();
- vertex_it != vertices_.end();) {
- if (vertex_it->incident_edge() == NULL) {
- vertex_it = vertices_.erase(vertex_it);
+ for (vertex_iterator it = vertices_.begin(); it != vertices_.end();) {
+ if (!it->incident_edge()) {
+ it = vertices_.erase(it);
+ --num_vertices_;
} else {
- ++vertex_it;
- ++num_vertices_;
+ ++it;
}
}
- // Update prev/next pointers for the ray-edges.
- for (cell_iterator cell_it = cells_.begin();
- cell_it != cells_.end(); ++cell_it) {
- // Move to the previous edge while
- // it is possible in the CW direction.
- edge_type *cur_edge = cell_it->incident_edge();
- if (cur_edge) {
- while (cur_edge->prev() != NULL) {
- cur_edge = cur_edge->prev();
+ // Set up next/prev pointers for infinite edges.
+ if (vertices_.empty()) {
+ if (!edges_.empty()) {
+ // Update prev/next pointers for the line edges.
+ edge_iterator edge_it = edges_.begin();
+ edge_type *edge1 = &(*edge_it);
+ edge1->next(edge1);
+ edge1->prev(edge1);
+ ++edge_it;
+ edge1 = &(*edge_it);
+ ++edge_it;
+
+ while (edge_it != edges_.end()) {
+ edge_type *edge2 = &(*edge_it);
+ ++edge_it;
+
+ edge1->next(edge2);
+ edge1->prev(edge2);
+ edge2->next(edge1);
+ edge2->prev(edge1);
+
+ edge1 = &(*edge_it);
+ ++edge_it;
+ }
+ edge1->next(edge1);
+ edge1->prev(edge1);
+ }
+ } else {
+ // Update prev/next pointers for the ray edges.
+ for (cell_iterator cell_it = cells_.begin();
+ cell_it != cells_.end(); ++cell_it) {
+ if (cell_it->is_degenerate())
+ continue;
+ // Move to the previous edge while
+ // it is possible in the CW direction.
+ edge_type *left_edge = cell_it->incident_edge();
+ while (left_edge->prev() != NULL) {
+ left_edge = left_edge->prev();
// Terminate if this is not a boundary cell.
- if (cur_edge == cell_it->incident_edge())
+ if (left_edge == cell_it->incident_edge())
break;
}
- // Rewind incident edge pointer to the
- // CW leftmost edge for the boundary cells.
- cell_it->incident_edge(cur_edge);
-
- // Set up prev/next half-edge pointers for the ray-edges.
- if (cur_edge->prev() == NULL) {
- edge_type *last_edge = cell_it->incident_edge();
- while (last_edge->next() != NULL)
- last_edge = last_edge->next();
- last_edge->next(cur_edge);
- cur_edge->prev(last_edge);
- }
+ if (left_edge->prev() != NULL)
+ continue;
+
+ edge_type *right_edge = cell_it->incident_edge();
+ while (right_edge->next() != NULL)
+ right_edge = right_edge->next();
+ left_edge->prev(right_edge);
+ right_edge->next(left_edge);
}
}
+
+ sealed_ = true;
}
private:
@@ -694,13 +662,11 @@
// Remove degenerate edge.
void remove_edge(edge_type *edge) {
- vertex_type *vertex1 = edge->vertex0();
- vertex_type *vertex2 = edge->vertex1();
-
// Update the endpoints of the incident edges to the second vertex.
+ vertex_type *vertex = edge->vertex0();
edge_type *updated_edge = edge->twin()->rot_next();
while (updated_edge != edge->twin()) {
- updated_edge->vertex0(vertex1);
+ updated_edge->vertex0(vertex);
updated_edge = updated_edge->rot_next();
}
@@ -718,17 +684,6 @@
edge2_rot_prev->prev(edge1_rot_next->twin());
edge1_rot_prev->prev(edge2_rot_next->twin());
edge2_rot_next->twin()->next(edge1_rot_prev);
-
- // Change the pointer to the incident edge if it points to the
- // degenerate edge.
- if (vertex1->incident_edge() == edge) {
- vertex1->incident_edge(edge->rot_prev());
- }
-
- // Set the incident edge pointer of the second vertex to NULL value.
- if (vertex1 != vertex2) {
- vertex2->incident_edge(NULL);
- }
}
cell_container_type cells_;
@@ -739,6 +694,8 @@
unsigned int num_edges_;
unsigned int num_vertices_;
+ bool sealed_;
+
brect_type vrect_;
ctype_converter_type convert_;
vertex_equality_predicate_type vertex_equality_predicate_;
Modified: sandbox/gtl/libs/polygon/test/voronoi_builder_test.cpp
==============================================================================
--- sandbox/gtl/libs/polygon/test/voronoi_builder_test.cpp (original)
+++ sandbox/gtl/libs/polygon/test/voronoi_builder_test.cpp 2012-03-08 19:01:58 EST (Thu, 08 Mar 2012)
@@ -20,6 +20,11 @@
#include "voronoi_test_helper.hpp"
typedef boost::mpl::list<int> test_types;
+typedef voronoi_diagram<double> vd_type;
+typedef vd_type::coordinate_type coordinate_type;
+typedef vd_type::edge_type voronoi_edge_type;
+typedef vd_type::const_cell_iterator const_cell_iterator;
+typedef vd_type::const_vertex_iterator const_vertex_iterator;
#define CHECK_EQUAL_POINTS(p1, p2) \
BOOST_CHECK(p1.x() == static_cast<T>(p2.x())); \
@@ -50,12 +55,6 @@
BOOST_CHECK(voronoi_test_helper::verify_output(output, \
voronoi_test_helper::NO_HALF_EDGE_INTERSECTIONS))
-typedef voronoi_diagram<double> vd_type;
-typedef vd_type::coordinate_type coordinate_type;
-typedef vd_type::edge_type voronoi_edge_type;
-typedef vd_type::const_cell_iterator const_cell_iterator;
-typedef vd_type::const_vertex_iterator const_vertex_iterator;
-
// Sites: (0, 0).
BOOST_AUTO_TEST_CASE_TEMPLATE(single_site_test, T, test_types) {
std::vector< point_data<T> > points;
@@ -161,18 +160,18 @@
const voronoi_edge_type *edge1_1 = it->incident_edge();
const voronoi_edge_type *edge1_2 = edge1_1->twin();
- CHECK_EQUAL_POINTS(edge1_1->cell()->point0(), point3);
- CHECK_EQUAL_POINTS(edge1_2->cell()->point0(), point1);
+ CHECK_EQUAL_POINTS(edge1_1->cell()->point0(), point2);
+ CHECK_EQUAL_POINTS(edge1_2->cell()->point0(), point3);
const voronoi_edge_type *edge2_1 = edge1_1->rot_prev();
const voronoi_edge_type *edge2_2 = edge2_1->twin();
- CHECK_EQUAL_POINTS(edge2_1->cell()->point0(), point1);
- CHECK_EQUAL_POINTS(edge2_2->cell()->point0(), point2);
+ CHECK_EQUAL_POINTS(edge2_1->cell()->point0(), point3);
+ CHECK_EQUAL_POINTS(edge2_2->cell()->point0(), point1);
const voronoi_edge_type *edge3_1 = edge2_1->rot_prev();
const voronoi_edge_type *edge3_2 = edge3_1->twin();
- CHECK_EQUAL_POINTS(edge3_1->cell()->point0(), point2);
- CHECK_EQUAL_POINTS(edge3_2->cell()->point0(), point3);
+ CHECK_EQUAL_POINTS(edge3_1->cell()->point0(), point1);
+ CHECK_EQUAL_POINTS(edge3_2->cell()->point0(), point2);
BOOST_CHECK_EQUAL(edge1_2->twin() == edge1_1, true);
BOOST_CHECK_EQUAL(edge2_2->twin() == edge2_1, true);
@@ -213,18 +212,18 @@
const voronoi_edge_type *edge1_1 = it->incident_edge();
const voronoi_edge_type *edge1_2 = edge1_1->twin();
- CHECK_EQUAL_POINTS(edge1_1->cell()->point0(), point2);
- CHECK_EQUAL_POINTS(edge1_2->cell()->point0(), point1);
+ CHECK_EQUAL_POINTS(edge1_1->cell()->point0(), point3);
+ CHECK_EQUAL_POINTS(edge1_2->cell()->point0(), point2);
const voronoi_edge_type *edge2_1 = edge1_1->rot_prev();
const voronoi_edge_type *edge2_2 = edge2_1->twin();
- CHECK_EQUAL_POINTS(edge2_1->cell()->point0(), point1);
- CHECK_EQUAL_POINTS(edge2_2->cell()->point0(), point3);
+ CHECK_EQUAL_POINTS(edge2_1->cell()->point0(), point2);
+ CHECK_EQUAL_POINTS(edge2_2->cell()->point0(), point1);
const voronoi_edge_type *edge3_1 = edge2_1->rot_prev();
const voronoi_edge_type *edge3_2 = edge3_1->twin();
- CHECK_EQUAL_POINTS(edge3_1->cell()->point0(), point3);
- CHECK_EQUAL_POINTS(edge3_2->cell()->point0(), point2);
+ CHECK_EQUAL_POINTS(edge3_1->cell()->point0(), point1);
+ CHECK_EQUAL_POINTS(edge3_2->cell()->point0(), point3);
BOOST_CHECK_EQUAL(edge1_2->twin() == edge1_1, true);
BOOST_CHECK_EQUAL(edge2_2->twin() == edge2_1, true);
@@ -269,23 +268,23 @@
// Check voronoi edges.
const voronoi_edge_type *edge1_1 = it->incident_edge();
const voronoi_edge_type *edge1_2 = edge1_1->twin();
- CHECK_EQUAL_POINTS(edge1_1->cell()->point0(), points[1]);
- CHECK_EQUAL_POINTS(edge1_2->cell()->point0(), points[3]);
+ CHECK_EQUAL_POINTS(edge1_1->cell()->point0(), points[3]);
+ CHECK_EQUAL_POINTS(edge1_2->cell()->point0(), points[2]);
const voronoi_edge_type *edge2_1 = edge1_1->rot_prev();
const voronoi_edge_type *edge2_2 = edge2_1->twin();
- CHECK_EQUAL_POINTS(edge2_1->cell()->point0(), points[3]);
- CHECK_EQUAL_POINTS(edge2_2->cell()->point0(), points[2]);
+ CHECK_EQUAL_POINTS(edge2_1->cell()->point0(), points[2]);
+ CHECK_EQUAL_POINTS(edge2_2->cell()->point0(), points[0]);
const voronoi_edge_type *edge3_1 = edge2_1->rot_prev();
const voronoi_edge_type *edge3_2 = edge3_1->twin();
- CHECK_EQUAL_POINTS(edge3_1->cell()->point0(), points[2]);
- CHECK_EQUAL_POINTS(edge3_2->cell()->point0(), points[0]);
+ CHECK_EQUAL_POINTS(edge3_1->cell()->point0(), points[0]);
+ CHECK_EQUAL_POINTS(edge3_2->cell()->point0(), points[1]);
const voronoi_edge_type *edge4_1 = edge3_1->rot_prev();
const voronoi_edge_type *edge4_2 = edge4_1->twin();
- CHECK_EQUAL_POINTS(edge4_1->cell()->point0(), points[0]);
- CHECK_EQUAL_POINTS(edge4_2->cell()->point0(), points[1]);
+ CHECK_EQUAL_POINTS(edge4_1->cell()->point0(), points[1]);
+ CHECK_EQUAL_POINTS(edge4_2->cell()->point0(), points[3]);
BOOST_CHECK_EQUAL(edge1_2->twin() == edge1_1, true);
BOOST_CHECK_EQUAL(edge2_2->twin() == edge2_1, true);
Modified: sandbox/gtl/libs/polygon/test/voronoi_test_helper.hpp
==============================================================================
--- sandbox/gtl/libs/polygon/test/voronoi_test_helper.hpp (original)
+++ sandbox/gtl/libs/polygon/test/voronoi_test_helper.hpp 2012-03-08 19:01:58 EST (Thu, 08 Mar 2012)
@@ -88,6 +88,8 @@
typename Output::const_vertex_iterator vertex_it;
for (vertex_it = output.vertices().begin();
vertex_it != output.vertices().end(); vertex_it++) {
+ if (vertex_it->is_degenerate())
+ continue;
const voronoi_edge_type *edge = vertex_it->incident_edge();
do {
const voronoi_edge_type *edge_next1 = edge->rot_next();