Subject: [Boost-commit] svn:boost r63432 - in sandbox/SOC/2010: . sweepline/boost/sweepline sweepline/boost/sweepline/detail sweepline/libs/sweepline/test
From: sydorchuk.andriy_at_[hidden]
Date: 2010-06-29 10:21:06
Author: asydorchuk
Date: 2010-06-29 10:21:05 EDT (Tue, 29 Jun 2010)
New Revision: 63432
URL: http://svn.boost.org/trac/boost/changeset/63432
Log:
Added output checks: half-edges orientation check, cells convexity check, voronoi vertex incident edges correct ordering, half-edges intersection check.
Properties modified:
sandbox/SOC/2010/ (props changed)
Text files modified:
sandbox/SOC/2010/sweepline/boost/sweepline/detail/voronoi_formation.hpp | 6
sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_builder.hpp | 2
sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_output.hpp | 247 +++++++++++++++++++++++++++++++++++++--
sandbox/SOC/2010/sweepline/libs/sweepline/test/test_type_list.hpp | 4
sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_builder_test.cpp | 12 +
5 files changed, 245 insertions(+), 26 deletions(-)
Modified: sandbox/SOC/2010/sweepline/boost/sweepline/detail/voronoi_formation.hpp
==============================================================================
--- sandbox/SOC/2010/sweepline/boost/sweepline/detail/voronoi_formation.hpp (original)
+++ sandbox/SOC/2010/sweepline/boost/sweepline/detail/voronoi_formation.hpp 2010-06-29 10:21:05 EDT (Tue, 29 Jun 2010)
@@ -500,11 +500,7 @@
struct beach_line_node_data {
Edge *edge;
- beach_line_node_data(Edge *new_edge) : edge(new_edge) {}
-
- void change_edge(Edge *new_edge) {
- edge = new_edge;
- }
+ explicit beach_line_node_data(Edge *new_edge) : edge(new_edge) {}
};
template <typename BeachLineNode>
Modified: sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_builder.hpp
==============================================================================
--- sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_builder.hpp (original)
+++ sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_builder.hpp 2010-06-29 10:21:05 EDT (Tue, 29 Jun 2010)
@@ -255,7 +255,7 @@
const_cast<Key &>(it_first->first).set_right_site(site3);
edge_type *edge = output_.insert_new_edge(site1, site2, site3, circle_event,
bisector1.edge, bisector2.edge);
- it_first->second.change_edge(edge);
+ it_first->second.edge = edge;
beach_line_.erase(it_last);
it_last = it_first;
Modified: sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_output.hpp
==============================================================================
--- sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_output.hpp (original)
+++ sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_output.hpp 2010-06-29 10:21:05 EDT (Tue, 29 Jun 2010)
@@ -92,6 +92,33 @@
// VORONOI OUTPUT TYPES ///////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////
+ // Bounding rectangle data structure.
+ template <typename Point2D>
+ struct BRect {
+ typedef typename Point2D::coordinate_type coordinate_type;
+
+ coordinate_type x_min;
+ coordinate_type y_min;
+ coordinate_type x_max;
+ coordinate_type y_max;
+
+ BRect() {}
+
+ BRect(const Point2D &p1, const Point2D &p2) {
+ x_min = std::min(p1.x(), p2.x());
+ y_min = std::min(p1.y(), p2.y());
+ x_max = std::max(p1.x(), p2.x());
+ y_max = std::max(p1.y(), p2.y());
+ }
+
+ void update(const Point2D &p) {
+ x_min = std::min(x_min, p.x());
+ y_min = std::min(y_min, p.y());
+ x_max = std::max(x_max, p.x());
+ y_max = std::max(y_max, p.y());
+ }
+ };
+
// Cell record data structure. Represents voronoi cell.
// Contains site point pointer to any incident half-edge and number
// of incident half-edges.
@@ -101,7 +128,7 @@
Point2D site_point;
int num_incident_edges;
- cell_record(Point2D site, half_edge<Point2D>* edge) :
+ cell_record(const Point2D &site, half_edge<Point2D>* edge) :
incident_edge(edge),
site_point(site),
num_incident_edges(0) {}
@@ -112,16 +139,22 @@
// number of incident half-edges.
template <typename Point2D>
struct vertex_record {
- typedef typename std::list< half_edge<Point2D>* >::iterator vertex_incident_edges_it;
+ typedef typename std::list< half_edge<Point2D>* >::const_iterator
+ vertex_incident_edges_const_it;
std::list< half_edge<Point2D>* > incident_edges;
Point2D vertex;
int num_incident_edges;
typename std::list< vertex_record<Point2D> >::iterator vertex_it;
- vertex_record(Point2D vertex) : vertex(vertex), num_incident_edges(3) {}
+ vertex_record(const Point2D &vertex) : vertex(vertex), num_incident_edges(3) {}
- vertex_incident_edges_it get_prev_incident_edge(vertex_incident_edges_it it) {
+ bool is_boundary_point() const {
+ return (num_incident_edges == 1);
+ }
+
+ vertex_incident_edges_const_it get_prev_incident_edge(
+ vertex_incident_edges_const_it it) const {
if (it != incident_edges.begin()) {
it--;
return it;
@@ -131,7 +164,8 @@
return it;
}
- vertex_incident_edges_it get_next_incident_edge(vertex_incident_edges_it it) {
+ vertex_incident_edges_const_it get_next_incident_edge(
+ vertex_incident_edges_const_it it) const {
it++;
if (it != incident_edges.end())
return it;
@@ -159,7 +193,7 @@
half_edge_type *twin;
typename std::list< half_edge<Point2D>* >::iterator incident_it;
- half_edge(int site_index) :
+ half_edge() :
cell(NULL),
start_point(NULL),
end_point(NULL),
@@ -174,6 +208,7 @@
template <typename Point2D>
class voronoi_output {
public:
+ typedef typename Point2D::coordinate_type coordinate_type;
typedef typename detail::site_event<Point2D> site_event_type;
typedef typename detail::circle_event<Point2D> circle_event_type;
typedef cell_record<Point2D> cell_record_type;
@@ -187,6 +222,12 @@
typedef typename voronoi_vertices_type::const_iterator
voronoi_vertices_const_iterator_type;
+ enum kOrientation {
+ LEFT_ORIENTATION = 1,
+ RIGHT_ORIENTATION = -1,
+ COLINEAR = 0,
+ };
+
voronoi_output() {
num_cell_records_ = 0;
num_edges_ = 0;
@@ -226,22 +267,24 @@
int site_index2 = site2.get_site_index();
// Create new half-edge that belongs to the cell with the first site.
- edges_.push_back(edge_type(site_index1));
+ edges_.push_back(edge_type());
edge_type &edge1 = edges_.back();
// Create new half-edge that belongs to the cell with the second site.
- edges_.push_back(edge_type(site_index2));
+ edges_.push_back(edge_type());
edge_type &edge2 = edges_.back();
// Add initial cell during first edge insertion.
if (cell_records_.empty()) {
cell_records_.push_back(cell_record_type(site1.get_point(), &edge1));
num_cell_records_++;
+ voronoi_rect_ = BRect<Point2D>(site1.get_point(), site1.get_point());
}
// Second site represents new site during site event processing.
// Add new cell to the cell records vector.
cell_records_.push_back(cell_record_type(site2.get_point(), &edge2));
+ voronoi_rect_.update(site2.get_point());
// Update pointers to cells.
edge1.cell = &cell_records_[site_index1];
@@ -266,6 +309,7 @@
edge_type *edge23) {
num_vertex_records_++;
num_edges_++;
+ voronoi_rect_.update(circle.get_center());
// Add new voronoi vertex as voronoi circle center.
vertex_records_.push_back(vertex_record_type(circle.get_center()));
@@ -284,14 +328,14 @@
edge23->twin->end_point = &new_vertex;
// Add new half-edge.
- edges_.push_back(edge_type(site1.get_site_index()));
+ edges_.push_back(edge_type());
edge_type &new_edge1 = edges_.back();
new_edge1.cell = &cell_records_[site1.get_site_index()];
cell_records_[site1.get_site_index()].num_incident_edges++;
new_edge1.end_point = &new_vertex;
// Add new half-edge.
- edges_.push_back(edge_type(site3.get_site_index()));
+ edges_.push_back(edge_type());
edge_type &new_edge2 = edges_.back();
new_edge2.cell = &cell_records_[site3.get_site_index()];
cell_records_[site3.get_site_index()].num_incident_edges++;
@@ -312,7 +356,7 @@
// Update voronoi vertex incident edges pointers.
new_vertex.incident_edges.push_back(edge12);
- typename std::list<edge_type*>::iterator temp_iter =new_vertex.incident_edges.begin();
+ edge_pointer_iterator_type temp_iter =new_vertex.incident_edges.begin();
edge12->incident_it = temp_iter;
new_vertex.incident_edges.push_back(edge23);
@@ -346,6 +390,10 @@
return num_edges_;
}
+ const BRect<Point2D> &get_voronoi_bounding_rectangle() const {
+ return voronoi_rect_;
+ }
+
void simplify() {
typename std::list<edge_type>::iterator edge_it1;
typename std::list<edge_type>::iterator edge_it = edges_.begin();
@@ -382,10 +430,136 @@
}
}
- bool check() {
+ bool check() const {
+ // Check correct orientation of each half_edge.
+ typename std::list<edge_type>::const_iterator edge_it;
+ for (edge_it = edges_.begin(); edge_it != edges_.end(); edge_it++) {
+ const Point2D &site = edge_it->cell->site_point;
+ if (edge_it->start_point != NULL && edge_it->end_point != NULL) {
+ const Point2D &start_point = edge_it->start_point->vertex;
+ const Point2D &end_point = edge_it->end_point->vertex;
+ if (check_orientation(start_point, end_point, site) != LEFT_ORIENTATION)
+ return false;
+ }
+ }
+
+ // Check if each site belongs to convex cell.
+ typename cell_records_type::const_iterator cell_it;
+ for (cell_it = cell_records_.begin(); cell_it != cell_records_.end(); cell_it++) {
+ const edge_type *edge = cell_it->incident_edge;
+
+ if (edge->start_point != NULL)
+ edge = edge->prev;
+ while (edge->start_point != NULL && edge != cell_it->incident_edge)
+ edge = edge->prev;
+ if (edge->start_point != NULL)
+ edge = edge->next;
+
+ while (edge->end_point != NULL && edge != cell_it->incident_edge) {
+ if (edge->next->prev != edge)
+ return false;
+ if (edge->cell != &(*cell_it))
+ return false;
+ if (edge->start_point != NULL && edge->next->end_point != NULL) {
+ const Point2D &vertex1 = edge->start_point->vertex;
+ const Point2D &vertex2 = edge->end_point->vertex;
+ const Point2D &vertex3 = edge->next->end_point->vertex;
+ if (check_orientation(vertex1, vertex2, vertex3) != LEFT_ORIENTATION)
+ return false;
+ }
+ edge = edge->next;
+ }
+ }
+
+ // Check voronoi vertex incident edges correct ordering.
+ voronoi_vertices_const_iterator_type vertex_it;
+ for (vertex_it = vertex_records_.begin();
+ vertex_it != vertex_records_.end(); vertex_it++) {
+ edge_pointer_const_iterator_type edge_it;
+ for (edge_it = vertex_it->incident_edges.begin();
+ edge_it != vertex_it->incident_edges.end(); edge_it++) {
+ edge_pointer_const_iterator_type edge_it_next1 =
+ vertex_it->get_next_incident_edge(edge_it);
+ edge_pointer_const_iterator_type edge_it_next2 =
+ vertex_it->get_next_incident_edge(edge_it_next1);
+ const Point2D &site1 = (*edge_it)->cell->site_point;
+ const Point2D &site2 = (*edge_it_next1)->cell->site_point;
+ const Point2D &site3 = (*edge_it_next2)->cell->site_point;
+ if (check_orientation(site3, site2, site1) != LEFT_ORIENTATION)
+ return false;
+ }
+ }
+
+ // Check if any two half_edges intersect not at the end point.
+ // Create map from edges with first point less than the second one.
+ // Key is the first point of the edges, value is vector of second points
+ // with the same first point.
+ std::map< Point2D, std::vector<Point2D> > edge_map;
+ typedef typename std::map< Point2D, std::vector<Point2D> >::const_iterator
+ edge_map_iterator;
+ for (edge_it = edges_.begin(); edge_it != edges_.end(); edge_it++) {
+ if (edge_it->start_point != NULL && edge_it->end_point != NULL) {
+ const Point2D &start_point = edge_it->start_point->vertex;
+ const Point2D &end_point = edge_it->end_point->vertex;
+ if (start_point < end_point)
+ edge_map[start_point].push_back(end_point);
+ }
+ }
+
+ // Iterate over map of edges and check if there are any intersections.
+ // All the edges are stored by the low x value. That's why we iterate
+ // left to right checking for intersections between all pairs of edges
+ // that overlap in the x dimension.
+ // Complexity. Approximately N*sqrt(N). Worst case N^2.
+ edge_map_iterator edge_map_it1, edge_map_it2, edge_map_it_bound;
+ for (edge_map_it1 = edge_map.begin();
+ edge_map_it1 != edge_map.end(); edge_map_it1++) {
+ const Point2D &point1 = edge_map_it1->first;
+
+ typedef typename std::vector<Point2D>::size_type size_type;
+ for (size_type i = 0; i < edge_map_it1->second.size(); i++) {
+ const Point2D &point2 = edge_map_it1->second[i];
+ coordinate_type min_y1 = std::min(point1.y(), point2.y());
+ coordinate_type max_y1 = std::max(point1.y(), point2.y());
+
+ // Find the first edge with greate or equal first point.
+ edge_map_it_bound = edge_map.lower_bound(point2);
+
+ edge_map_it2 = edge_map_it1;
+ edge_map_it2++;
+ for (; edge_map_it2 != edge_map_it_bound; edge_map_it2++) {
+ const Point2D &point3 = edge_map_it2->first;
+
+ for (size_type j = 0; j < edge_map_it2->second.size(); j++) {
+ const Point2D &point4 = edge_map_it2->second[j];
+ coordinate_type min_y2 = std::min(point3.y(), point4.y());
+ coordinate_type max_y2 = std::max(point3.y(), point4.y());
+
+ // In most cases it is enought to make
+ // simple intersection check in the y dimension.
+ if (!(max_y1 > min_y2 && max_y2 > min_y1))
+ continue;
+
+ // Intersection check.
+ if (check_orientation(point1, point2, point3) *
+ check_orientation(point1, point2, point4) == -1 &&
+ check_orientation(point3, point4, point1) *
+ check_orientation(point3, point4, point2) == -1)
+ return false;
+ }
+ }
+ }
+ }
+
return true;
}
+ void clip(coordinate_type x_min, coordinate_type y_min,
+ coordinate_type x_max, coordinate_type y_max) {
+
+
+ }
+
private:
void simplify_edge(edge_type &edge) {
vertex_record_type *vertex1 = edge.start_point;
@@ -406,11 +580,15 @@
edge_pointer_iterator_type edge1_it = edge.incident_it;
edge_pointer_iterator_type edge2_it = edge.twin->incident_it;
- edge_pointer_iterator_type edge1_it_prev = vertex1->get_prev_incident_edge(edge1_it);
- edge_pointer_iterator_type edge1_it_next = vertex1->get_next_incident_edge(edge1_it);
-
- edge_pointer_iterator_type edge2_it_prev = vertex2->get_prev_incident_edge(edge2_it);
- edge_pointer_iterator_type edge2_it_next = vertex2->get_next_incident_edge(edge2_it);
+ edge_pointer_const_iterator_type edge1_it_prev =
+ vertex1->get_prev_incident_edge(edge1_it);
+ edge_pointer_const_iterator_type edge1_it_next =
+ vertex1->get_next_incident_edge(edge1_it);
+
+ edge_pointer_const_iterator_type edge2_it_prev =
+ vertex2->get_prev_incident_edge(edge2_it);
+ edge_pointer_const_iterator_type edge2_it_next =
+ vertex2->get_next_incident_edge(edge2_it);
(*edge1_it_prev)->twin->next = *edge2_it_next;
(*edge2_it_next)->prev = (*edge1_it_prev)->twin;
@@ -434,6 +612,18 @@
vertex_records_.erase(vertex2->vertex_it);
}
+ int check_orientation(const Point2D &point1,
+ const Point2D &point2,
+ const Point2D &point3) const {
+ coordinate_type a = (point2.x() - point1.x()) * (point3.y() - point2.y());
+ coordinate_type b = (point2.y() - point1.y()) * (point3.x() - point2.x());
+ if (a > b)
+ return LEFT_ORIENTATION;
+ else if (a < b)
+ return RIGHT_ORIENTATION;
+ return COLINEAR;
+ }
+
std::vector<cell_record_type> cell_records_;
std::list<vertex_record_type> vertex_records_;
std::list<edge_type> edges_;
@@ -442,11 +632,32 @@
int num_vertex_records_;
int num_edges_;
- //Disallow copy constructor and operator=
+ BRect<Point2D> voronoi_rect_;
+
+ // Disallow copy constructor and operator=
voronoi_output(const voronoi_output&);
void operator=(const voronoi_output&);
};
+ template <typename Point2D>
+ class voronoi_output_clipped {
+ public:
+ typedef typename Point2D::coordinate_type coordinate_type;
+
+ voronoi_output_clipped(const Point2D &p1, const Point2D &p2) : brect_(p1, p2) {}
+
+ void clip(const voronoi_output<Point2D> &output) {
+
+ }
+
+ private:
+ BRect<Point2D> brect_;
+
+ // Disallow copy constructor and operator=
+ voronoi_output_clipped(const voronoi_output_clipped&);
+ void operator=(const voronoi_output_clipped&);
+ };
+
} // sweepline
} // boost
Modified: sandbox/SOC/2010/sweepline/libs/sweepline/test/test_type_list.hpp
==============================================================================
--- sandbox/SOC/2010/sweepline/libs/sweepline/test/test_type_list.hpp (original)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/test/test_type_list.hpp 2010-06-29 10:21:05 EDT (Tue, 29 Jun 2010)
@@ -12,8 +12,8 @@
#include <boost/mpl/list.hpp>
-typedef boost::mpl::list<//float,
- //double,
+typedef boost::mpl::list<float,
+ double,
long double> test_types;
#endif
Modified: sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_builder_test.cpp
==============================================================================
--- sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_builder_test.cpp (original)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_builder_test.cpp 2010-06-29 10:21:05 EDT (Tue, 29 Jun 2010)
@@ -38,6 +38,7 @@
test_beach_line.init(points);
test_beach_line.run_sweepline();
const voronoi_output< point_2d<T> > &test_output = test_beach_line.get_output();
+ BOOST_CHECK_EQUAL(test_output.check(), true);
BOOST_CHECK_EQUAL(static_cast<int>(test_output.get_cell_records().size()), 3);
BOOST_CHECK_EQUAL(static_cast<int>(test_output.get_voronoi_vertices().size()), 1);
@@ -104,6 +105,7 @@
test_beach_line.init(points);
test_beach_line.run_sweepline();
const voronoi_output< point_2d<T> > &test_output = test_beach_line.get_output();
+ BOOST_CHECK_EQUAL(test_output.check(), true);
BOOST_CHECK_EQUAL(static_cast<int>(test_output.get_cell_records().size()), 3);
BOOST_CHECK_EQUAL(static_cast<int>(test_output.get_voronoi_vertices().size()), 1);
@@ -166,6 +168,7 @@
test_beach_line.init(points);
test_beach_line.run_sweepline();
const voronoi_output< point_2d<T> > &test_output = test_beach_line.get_output();
+ BOOST_CHECK_EQUAL(test_output.check(), true);
BOOST_CHECK_EQUAL(static_cast<T>(test_output.get_cell_records().size()), 4);
BOOST_CHECK_EQUAL(static_cast<T>(test_output.get_voronoi_vertices().size()), 1);
@@ -239,6 +242,7 @@
test_beach_line.init(points);
test_beach_line.run_sweepline();
const voronoi_output< point_2d<T> > &test_output = test_beach_line.get_output();
+ BOOST_CHECK_EQUAL(test_output.check(), true);
BOOST_CHECK_EQUAL(test_output.get_num_voronoi_cells(), 9);
BOOST_CHECK_EQUAL(test_output.get_num_voronoi_vertices(), 4);
@@ -262,6 +266,7 @@
test_beach_line.init(points);
test_beach_line.run_sweepline();
+ BOOST_CHECK_EQUAL(test_beach_line.get_output().check(), true);
}
// Sites: {(x, y) | x = 0 .. 9, y = 0 .. 9}.
@@ -276,6 +281,7 @@
test_beach_line.init(points);
test_beach_line.run_sweepline();
const voronoi_output< point_2d<T> > &test_output = test_beach_line.get_output();
+ BOOST_CHECK_EQUAL(test_output.check(), true);
BOOST_CHECK_EQUAL(test_output.get_num_voronoi_cells(), 100);
BOOST_CHECK_EQUAL(test_output.get_num_voronoi_vertices(), 81);
@@ -299,6 +305,7 @@
test_beach_line.init(points);
test_beach_line.run_sweepline();
+ BOOST_CHECK_EQUAL(test_beach_line.get_output().check(), true);
}
// Sites: {(x, y) | x = 0 .. 33, y = 0 .. 33}.
@@ -313,6 +320,7 @@
test_beach_line.init(points);
test_beach_line.run_sweepline();
const voronoi_output< point_2d<T> > &test_output = test_beach_line.get_output();
+ BOOST_CHECK_EQUAL(test_output.check(), true);
BOOST_CHECK_EQUAL(test_output.get_num_voronoi_cells(), 1089);
BOOST_CHECK_EQUAL(test_output.get_num_voronoi_vertices(), 1024);
@@ -336,6 +344,7 @@
test_beach_line.init(points);
test_beach_line.run_sweepline();
+ BOOST_CHECK_EQUAL(test_beach_line.get_output().check(), true);
}
// Sites: {(x, y) | x = 0 .. 100, y = 0 .. 100}.
@@ -350,6 +359,7 @@
test_beach_line.init(points);
test_beach_line.run_sweepline();
const voronoi_output< point_2d<T> > &test_output = test_beach_line.get_output();
+ BOOST_CHECK_EQUAL(test_output.check(), true);
BOOST_CHECK_EQUAL(test_output.get_num_voronoi_cells(), 10000);
BOOST_CHECK_EQUAL(test_output.get_num_voronoi_vertices(), 9801);
@@ -367,6 +377,7 @@
test_beach_line.init(points);
test_beach_line.run_sweepline();
+ BOOST_CHECK_EQUAL(test_beach_line.get_output().check(), true);
}
// Sites: {(x, y) | x = 0 .. 333, y = 0 .. 333}.
@@ -381,6 +392,7 @@
test_beach_line.init(points);
test_beach_line.run_sweepline();
const voronoi_output< point_2d<T> > &test_output = test_beach_line.get_output();
+ BOOST_CHECK_EQUAL(test_output.check(), true);
BOOST_CHECK_EQUAL(test_output.get_num_voronoi_cells(), 110889);
BOOST_CHECK_EQUAL(test_output.get_num_voronoi_vertices(), 110224);