|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r66864 - in sandbox/SOC/2010/sweepline: boost/sweepline boost/sweepline/detail libs/sweepline/example libs/sweepline/test
From: sydorchuk.andriy_at_[hidden]
Date: 2010-11-29 19:02:19
Author: asydorchuk
Date: 2010-11-29 19:02:09 EST (Mon, 29 Nov 2010)
New Revision: 66864
URL: http://svn.boost.org/trac/boost/changeset/66864
Log:
Changed output data structure.
Changed tests.
Reduced memory consumption two times.
Changed voronoi algorithm interface (static functions instead of voronoi_builder class).
Removed:
sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_builder.hpp
Text files modified:
sandbox/SOC/2010/sweepline/boost/sweepline/detail/voronoi_formation.hpp | 976 +++++++++++++--------------------
sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_output.hpp | 894 +++++++++++++++++++++++-------
sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_sweepline.hpp | 34 +
sandbox/SOC/2010/sweepline/libs/sweepline/example/voronoi_visualizer.cpp | 47
sandbox/SOC/2010/sweepline/libs/sweepline/test/benchmark_test.cpp | 12
sandbox/SOC/2010/sweepline/libs/sweepline/test/clipping_test.cpp | 92 +-
sandbox/SOC/2010/sweepline/libs/sweepline/test/output_verification.hpp | 79 +-
sandbox/SOC/2010/sweepline/libs/sweepline/test/sweepline_test.cpp | 1150 +++++++++++++++++++--------------------
8 files changed, 1755 insertions(+), 1529 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-11-29 19:02:09 EST (Mon, 29 Nov 2010)
@@ -7,8 +7,8 @@
// See http://www.boost.org for updates, documentation, and revision history.
-#ifndef BOOST_SWEEPLINE_VORONOI_SEGMENT_FORMATION
-#define BOOST_SWEEPLINE_VORONOI_SEGMENT_FORMATION
+#ifndef BOOST_SWEEPLINE_VORONOI_FORMATION
+#define BOOST_SWEEPLINE_VORONOI_FORMATION
#define INT_PREDICATE_COMPUTE_DIFFERENCE(a, b, res, sign) \
if (a >= b) { res = static_cast<unsigned long long>(a - b); sign = true; } \
@@ -26,6 +26,7 @@
// VORONOI EVENT TYPES ////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////
+ // Forward declarations.
template <typename T>
class beach_line_node;
@@ -78,6 +79,18 @@
is_vertical_(true),
is_inverse_(false) {}
+ site_event(coordinate_type x1, coordinate_type y1,
+ coordinate_type x2, coordinate_type y2, int index):
+ point0_(x1, y1),
+ point1_(x2, y2),
+ site_index_(index),
+ is_segment_(true),
+ is_inverse_(false) {
+ if (point0_ > point1_)
+ (std::swap)(point0_, point1_);
+ is_vertical_ = (point0_.x() == point1_.x());
+ }
+
site_event(const Point2D &point1, const Point2D &point2, int index) :
point0_(point1),
point1_(point2),
@@ -238,6 +251,11 @@
}
template <typename T>
+ site_event<T> make_site_event(T x1, T y1, T x2, T y2, int index) {
+ return site_event<T>(x1, y1, x2, y2, index);
+ }
+
+ template <typename T>
site_event<T> make_site_event(const point_2d<T> &point1,
const point_2d<T> &point2, int index) {
return site_event<T>(point1, point2, index);
@@ -404,7 +422,6 @@
class circle_events_queue {
public:
typedef T coordinate_type;
- typedef point_2d<T> Point2D;
typedef circle_event<T> circle_event_type;
typedef typename std::list<circle_event_type>::iterator circle_event_type_it;
@@ -464,7 +481,7 @@
///////////////////////////////////////////////////////////////////////////
// GEOMETRY PREDICATES ////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////
- inline static void avoid_cancellation(double value, double &left_expr, double &right_expr) {
+ static void avoid_cancellation(double value, double &left_expr, double &right_expr) {
if (value >= 0)
left_expr += value;
else
@@ -588,7 +605,7 @@
}
template <typename T>
- static T robust_cross_product(T a1_, T b1_, T a2_, T b2_) {
+ static double robust_cross_product(T a1_, T b1_, T a2_, T b2_) {
typedef unsigned long long ull;
ull a1, b1, a2, b2;
bool a1_plus, a2_plus, b1_plus, b2_plus;
@@ -720,6 +737,10 @@
return (lhs < rhs) ? LESS : MORE;
}
+ bool compares_undefined(const epsilon_robust_comparator &rc, int ulp) const {
+ return this->compare(rc, ulp) == UNDEFINED;
+ }
+
private:
T positive_sum_;
T negative_sum_;
@@ -1120,7 +1141,7 @@
// CIRCLE EVENTS CREATION /////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////
template <typename T>
- inline static T get_sqr_distance(T dif_x, T dif_y) {
+ static T get_sqr_distance(T dif_x, T dif_y) {
return dif_x * dif_x + dif_y * dif_y;
}
@@ -1509,9 +1530,6 @@
site_event_type right_site_;
};
- template <typename T>
- struct voronoi_edge;
-
// Represents edge data sturcture (bisector segment), which is
// associated with beach line node key in the binary search tree.
template <typename T>
@@ -1588,632 +1606,406 @@
}
};
- ///////////////////////////////////////////////////////////////////////////
- // VORONOI OUTPUT /////////////////////////////////////////////////////////
- ///////////////////////////////////////////////////////////////////////////
- template <typename T>
- struct voronoi_cell {
- typedef T coordinate_type;
- typedef site_event<T> site_event_type;
-
- voronoi_edge<coordinate_type> *incident_edge;
- site_event_type site;
- int num_incident_edges;
-
- voronoi_cell(const site_event_type &new_site, voronoi_edge<coordinate_type>* edge) :
- incident_edge(edge),
- site(new_site),
- num_incident_edges(0) {}
- };
-
- template <typename T>
- struct voronoi_vertex {
- typedef T coordinate_type;
- typedef point_2d<T> Point2D;
-
- voronoi_edge<coordinate_type> *incident_edge;
- epsilon_robust_comparator<T> center_x;
- epsilon_robust_comparator<T> center_y;
- epsilon_robust_comparator<T> denom;
- Point2D vertex;
- int num_incident_edges;
- typename std::list< voronoi_vertex<coordinate_type> >::iterator voronoi_record_it;
-
- voronoi_vertex(const epsilon_robust_comparator<T> &c_x,
- const epsilon_robust_comparator<T> &c_y,
- const epsilon_robust_comparator<T> &den,
- voronoi_edge<coordinate_type>* edge) :
- incident_edge(edge),
- center_x(c_x),
- center_y(c_y),
- denom(den),
- vertex(c_x.dif() / den.dif(), c_y.dif() / den.dif()),
- num_incident_edges(0) {}
- };
-
- // Half-edge data structure. Represents voronoi edge.
- // Contains: 1) pointer to cell records;
- // 2) pointers to start/end vertices of half-edge;
- // 3) pointers to previous/next half-edges(CCW);
- // 4) pointers to previous/next half-edges rotated
- // around start point;
- // 5) pointer to twin half-edge;
- // 6) pointer to clipped edge during clipping.
- template <typename T>
- struct voronoi_edge {
- typedef T coordinate_type;
- typedef point_2d<T> Point2D;
- typedef voronoi_cell<coordinate_type> voronoi_cell_type;
- typedef voronoi_vertex<coordinate_type> voronoi_vertex_type;
- typedef voronoi_edge<coordinate_type> voronoi_edge_type;
- typedef voronoi_edge_clipped<coordinate_type> voronoi_edge_clipped_type;
-
- voronoi_cell_type *cell;
- voronoi_vertex_type *start_point;
- voronoi_vertex_type *end_point;
- voronoi_edge_type *prev;
- voronoi_edge_type *next;
- voronoi_edge_type *rot_prev;
- voronoi_edge_type *rot_next;
- voronoi_edge_type *twin;
- voronoi_edge_clipped_type *clipped_edge;
-
- voronoi_edge() :
- cell(NULL),
- start_point(NULL),
- end_point(NULL),
- prev(NULL),
- next(NULL),
- rot_prev(NULL),
- rot_next(NULL),
- twin(NULL),
- clipped_edge(NULL) {}
- };
-
- // Voronoi output data structure based on the half-edges.
- // Contains vector of voronoi cells, doubly linked list of
- // voronoi vertices and voronoi edges.
+ // Voronoi diagram builder. Sweepline sweeps from left to right.
template <typename T>
- class voronoi_output {
+ class voronoi_builder {
public:
typedef T coordinate_type;
- typedef point_2d<T> Point2D;
+ typedef point_2d<coordinate_type> Point2D;
+ typedef voronoi_output<coordinate_type> Output;
typedef site_event<coordinate_type> site_event_type;
typedef circle_event<coordinate_type> circle_event_type;
- typedef voronoi_cell<coordinate_type> voronoi_cell_type;
- typedef std::list<voronoi_cell_type> voronoi_cells_type;
- typedef typename voronoi_cells_type::iterator voronoi_cell_iterator_type;
- typedef typename voronoi_cells_type::const_iterator voronoi_cell_const_iterator_type;
-
- typedef voronoi_vertex<coordinate_type> voronoi_vertex_type;
- typedef std::list<voronoi_vertex_type> voronoi_vertices_type;
- typedef typename voronoi_vertices_type::iterator voronoi_vertex_iterator_type;
- typedef typename voronoi_vertices_type::const_iterator voronoi_vertex_const_iterator_type;
-
- typedef voronoi_edge<coordinate_type> edge_type;
- typedef voronoi_edge_clipped<coordinate_type> clipped_edge_type;
- typedef std::list<edge_type> voronoi_edges_type;
- typedef typename voronoi_edges_type::iterator edges_iterator_type;
-
- typedef voronoi_cell_clipped<coordinate_type> clipped_voronoi_cell_type;
- typedef voronoi_vertex_clipped<coordinate_type> clipped_voronoi_vertex_type;
- typedef voronoi_edge_clipped<coordinate_type> clipped_voronoi_edge_type;
-
- voronoi_output() {
- num_cell_records_ = 0;
- num_edges_ = 0;
- num_vertex_records_ = 0;
- }
-
- void init(int num_sites) {
- cell_iterators_.reserve(num_sites);
- num_cell_records_ = 0;
- num_edges_ = 0;
- num_vertex_records_ = 0;
- }
-
- void reset() {
- cell_iterators_.clear();
- cell_records_.clear();
- vertex_records_.clear();
- edges_.clear();
-
- num_cell_records_ = 0;
- num_edges_ = 0;
- num_vertex_records_ = 0;
- }
-
- // Update voronoi output in case of single site input.
- void process_single_site(const site_event_type &site) {
- // Update counters.
- num_cell_records_++;
-
- // Update bounding rectangle.
- voronoi_rect_ = BRect<coordinate_type>(site.get_point0(), site.get_point0());
-
- // Update cell records.
- cell_records_.push_back(voronoi_cell_type(site, NULL));
- }
-
- // Inserts new half-edge into the output data structure during site
- // event processing. Takes as input left and right sites of the new
- // beach line node and returns pointer to the new half-edge.
- edge_type *insert_new_edge(const site_event_type &site1,
- const site_event_type &site2) {
- // Update counters.
- num_cell_records_++;
- num_edges_++;
-
- // Get indices of sites.
- int site_index1 = site1.get_site_index();
- int site_index2 = site2.get_site_index();
-
- // Create new half-edge that belongs to the first site.
- edges_.push_back(edge_type());
- edge_type &edge1 = edges_.back();
-
- // Create new half-edge that belongs to the second site.
- edges_.push_back(edge_type());
- edge_type &edge2 = edges_.back();
-
- // Add initial cell during first edge insertion.
- if (cell_records_.empty()) {
- cell_iterators_.push_back(cell_records_.insert(
- cell_records_.end(), voronoi_cell_type(site1, &edge1)));
- num_cell_records_++;
- voronoi_rect_ = BRect<coordinate_type>(site1.get_point0(), site1.get_point0());
- }
- cell_iterators_[site_index1]->num_incident_edges++;
-
- // Update bounding rectangle.
- voronoi_rect_.update(site2.get_point0());
- if (site2.is_segment()) {
- voronoi_rect_.update(site2.get_point1());
- }
-
- // Second site represents new site during site event processing.
- // Add new cell to the cell records vector.
- cell_iterators_.push_back(cell_records_.insert(
- cell_records_.end(), voronoi_cell_type(site2, &edge2)));
- cell_records_.back().num_incident_edges++;
+ voronoi_builder(Output &output) : output_(output) {
+ // Set sites iterator.
+ site_events_iterator_ = site_events_.begin();
+ }
+
+ // Init beach line before sweepline run.
+ // In case of a few first sites situated on the same
+ // vertical line, we init beach line with all of them.
+ // In other case just use the first two sites for the initialization.
+ template <typename iType>
+ void init(const std::vector< point_2d<iType> > &points,
+ const std::vector< std::pair< point_2d<iType>, point_2d<iType> > > &segments) {
+ typedef std::pair< point_2d<iType>, point_2d<iType> > iSegment2D;
+ // Clear all data structures.
+ output_.reset();
+
+ // TODO(asydorchuk): Add segments intersection check.
+
+ // Avoid additional memory reallocations.
+ site_events_.reserve(points.size() + segments.size() * 3);
+
+ // Create site events from point sites.
+ for (typename std::vector< point_2d<iType> >::const_iterator it = points.begin();
+ it != points.end(); it++) {
+ site_events_.push_back(make_site_event(static_cast<T>(it->x()),
+ static_cast<T>(it->y()), 0));
+ }
- // Update pointers to cells.
- edge1.cell = &(*cell_iterators_[site_index1]);
- edge2.cell = &(*cell_iterators_[site_index2]);
-
- // Update twin pointers.
- edge1.twin = &edge2;
- edge2.twin = &edge1;
-
- return &edge1;
- }
-
- edge_type *insert_new_edge(const site_event_type &site1,
- const site_event_type &site3,
- const circle_event_type &circle,
- edge_type *edge12,
- edge_type *edge23) {
- // Update counters.
- num_vertex_records_++;
- num_edges_++;
-
- // Update bounding rectangle.
- //voronoi_rect_.update(circle.get_center());
-
- // Add new voronoi vertex with point at center of the circle.
- vertex_records_.push_back(voronoi_vertex_type(
- circle.get_erc_x(), circle.get_erc_y(), circle.get_erc_denom(), edge12));
- voronoi_vertex_type &new_vertex = vertex_records_.back();
- new_vertex.num_incident_edges = 3;
- new_vertex.voronoi_record_it = vertex_records_.end();
- new_vertex.voronoi_record_it--;
-
- // Update two input bisectors and their twin half-edges with
- // new voronoi vertex.
- edge12->start_point = &new_vertex;
- edge12->twin->end_point = &new_vertex;
- edge23->start_point = &new_vertex;
- edge23->twin->end_point = &new_vertex;
-
- // Add new half-edge.
- edges_.push_back(edge_type());
- edge_type &new_edge1 = edges_.back();
- new_edge1.cell = &(*cell_iterators_[site1.get_site_index()]);
- new_edge1.cell->num_incident_edges++;
- new_edge1.end_point = &new_vertex;
-
- // Add new half-edge.
- edges_.push_back(edge_type());
- edge_type &new_edge2 = edges_.back();
- new_edge2.cell = &(*cell_iterators_[site3.get_site_index()]);
- new_edge2.cell->num_incident_edges++;
- new_edge2.start_point = &new_vertex;
-
- // Update twin pointers of the new half-edges.
- new_edge1.twin = &new_edge2;
- new_edge2.twin = &new_edge1;
+ // Create site events from end points of segment sites and segment itself.
+ for (typename std::vector<iSegment2D>::const_iterator it = segments.begin();
+ it != segments.end(); it++) {
+ T x1 = static_cast<T>(it->first.x());
+ T y1 = static_cast<T>(it->first.y());
+ T x2 = static_cast<T>(it->second.x());
+ T y2 = static_cast<T>(it->second.y());
+ site_events_.push_back(make_site_event(x1, y1, 0));
+ site_events_.push_back(make_site_event(x2, y2, 0));
+ site_events_.push_back(make_site_event(x1, y1, x2, y2, 0));
+ }
+
+ // Sort site events.
+ sort(site_events_.begin(), site_events_.end());
+
+ // Remove duplicates.
+ site_events_.erase(unique(site_events_.begin(), site_events_.end()),
+ site_events_.end());
+
+ // Number sites.
+ for (int cur_index = 0; cur_index < static_cast<int>(site_events_.size()); cur_index++)
+ site_events_[cur_index].set_site_index(cur_index);
+
+ // Set site iterator.
+ site_events_iterator_ = site_events_.begin();
+
+ // Init output with number of site events.
+ // There will be one site event for each input point and three site events
+ // for each input segment: both ends of a segment and the segment itself.
+ output_.init(site_events_.size());
+ }
+
+ void clear() {
+ circle_events_.reset();
+ beach_line_.clear();
+ site_events_.clear();
+ }
+
+ void run_sweepline() {
+ // Init beach line.
+ if (site_events_.empty()) {
+ return;
+ } else if (site_events_.size() == 1) {
+ // Handle one input site case.
+ output_.process_single_site(site_events_[0]);
+ site_events_iterator_++;
+ } else {
+ int skip = 0;
+ // Init beach line.
+ while(site_events_iterator_ != site_events_.end() &&
+ site_events_iterator_->x() == site_events_.begin()->x() &&
+ site_events_iterator_->is_vertical()) {
+ site_events_iterator_++;
+ skip++;
+ }
- // Update voronoi prev/next pointers of all half-edges incident
- // to the new voronoi vertex.
- edge12->prev = &new_edge1;
- new_edge1.next = edge12;
- edge12->twin->next = edge23;
- edge23->prev = edge12->twin;
- edge23->twin->next = &new_edge2;
- new_edge2.prev = edge23->twin;
+ if (skip == 1) {
+ // Init beach line with two sites.
+ init_beach_line();
+ } else {
+ // Init beach line with sites situated on the same vertical line.
+ init_beach_line_collinear_sites();
+ }
+ }
- // Update voronoi vertices incident edges pointers.
- edge12->rot_next = &new_edge2;
- new_edge2.rot_prev = edge12;
- edge23->rot_next = edge12;
- edge12->rot_prev = edge23;
- new_edge2.rot_next = edge23;
- edge23->rot_prev = &new_edge2;
+ // Algorithm stops when there are no events to process.
+ while (!circle_events_.empty() ||
+ !(site_events_iterator_ == site_events_.end())) {
+ if (circle_events_.empty()) {
+ process_site_event();
+ } else if (site_events_iterator_ == site_events_.end()) {
+ process_circle_event();
+ } else {
+ if (circle_events_.top().compare(*site_events_iterator_) == MORE) {
+ process_site_event();
+ } else {
+ process_circle_event();
+ }
+ }
+ }
- return &new_edge1;
+ // Simplify output.
+ output_.simplify();
+ clear();
}
- const voronoi_cells_type &get_cell_records() const {
- return cell_records_;
- }
+ private:
+ typedef typename std::vector<site_event_type>::const_iterator site_events_iterator_type;
+ typedef typename Output::voronoi_edge_type edge_type;
+ typedef circle_events_queue<coordinate_type> CircleEventsQueue;
+ typedef beach_line_node<coordinate_type> Key;
+ typedef beach_line_node_data<coordinate_type> Value;
+ typedef node_comparer<Key> NodeComparer;
+ typedef std::map< Key, Value, NodeComparer > BeachLine;
+ typedef typename std::map< Key, Value, NodeComparer >::iterator beach_line_iterator;
+ typedef typename std::pair<Point2D, beach_line_iterator> end_point_type;
- const voronoi_vertices_type &get_voronoi_vertices() const {
- return vertex_records_;
- }
+ void init_beach_line() {
+ // The first site is always a point.
+ // Get the first and the second site events.
+ site_events_iterator_type it_first = site_events_.begin();
+ site_events_iterator_type it_second = site_events_.begin();
+ it_second++;
+
+ // Insert new nodes.
+ insert_new_arc(*it_first, *it_first, *it_second, beach_line_.begin());
+
+ // The second site has been already processed.
+ site_events_iterator_++;
+ }
+
+ // Insert bisectors for all collinear initial sites.
+ // There should be at least two colinear sites.
+ void init_beach_line_collinear_sites() {
+ site_events_iterator_type it_first = site_events_.begin();
+ site_events_iterator_type it_second = site_events_.begin();
+ it_second++;
+ while (it_second != site_events_iterator_) {
+ // Create new beach line node.
+ Key new_node(*it_first, *it_second);
+
+ // Update output.
+ edge_type *edge = output_.insert_new_edge(*it_first, *it_second);
+
+ // Insert new node into the binary search tree.
+ beach_line_.insert(std::pair<Key, Value>(new_node, Value(edge)));
+
+ // Update iterators.
+ it_first++;
+ it_second++;
+ }
+ }
+
+ // Uses special comparison function for the lower bound and insertion
+ // operations.
+ void process_site_event() {
+ site_event_type site_event = *site_events_iterator_;
+ site_events_iterator_++;
+
+ // If new site is end point of some segment, remove temporary nodes from
+ // beach line data structure.
+ if (!site_event.is_segment()) {
+ while (!end_points_.empty() && end_points_.top().first == site_event.get_point0()) {
+ beach_line_.erase(end_points_.top().second);
+ end_points_.pop();
+ }
+ }
- const voronoi_edges_type &get_voronoi_edges() const {
- return edges_;
- }
+ // Find the node in the binary search tree with left arc
+ // lying above the new site point.
+ Key new_key(site_event);
+ beach_line_iterator it = beach_line_.lower_bound(new_key);
+ int it_dist = site_event.is_segment() ? 2 : 1;
+
+ if (it == beach_line_.end()) {
+ it--;
+ const site_event_type &site_arc = it->first.get_right_site();
+
+ // Insert new arc into the sweepline.
+ beach_line_iterator new_node_it = insert_new_arc(site_arc, site_arc, site_event, it);
+ std::advance(new_node_it, -it_dist);
+
+ // Add candidate circle to the event queue.
+ activate_circle_event(it->first.get_left_site(), it->first.get_right_site(),
+ site_event, new_node_it);
+ } else if (it == beach_line_.begin()) {
+ const site_event_type &site_arc = it->first.get_left_site();
+
+ // Insert new arc into the sweepline.
+ insert_new_arc(site_arc, site_arc, site_event, it);
+
+ // Add candidate circle to the event queue.
+ if (site_event.is_segment()) {
+ site_event.set_inverse();
+ }
+ activate_circle_event(site_event, it->first.get_left_site(),
+ it->first.get_right_site(), it);
+ } else {
+ const site_event_type &site_arc2 = it->first.get_left_site();
+ const site_event_type &site3 = it->first.get_right_site();
- int get_num_voronoi_cells() const {
- return num_cell_records_;
+ // Remove candidate circle from the event queue.
+ it->second.deactivate_circle_event();
+ it--;
+ const site_event_type &site_arc1 = it->first.get_right_site();
+ const site_event_type &site1 = it->first.get_left_site();
+
+ // Insert new arc into the sweepline.
+ beach_line_iterator new_node_it =
+ insert_new_arc(site_arc1, site_arc2, site_event, it);
+
+ // Add candidate circles to the event queue.
+ std::advance(new_node_it, -it_dist);
+ activate_circle_event(site1, site_arc1, site_event, new_node_it);
+ if (site_event.is_segment()) {
+ site_event.set_inverse();
+ }
+ std::advance(new_node_it, it_dist + 1);
+ activate_circle_event(site_event, site_arc2, site3, new_node_it);
+ }
}
- int get_num_voronoi_vertices() const {
- return num_vertex_records_;
- }
+ // Doesn't use special comparison function as it works fine only for
+ // the site events processing.
+ void process_circle_event() {
+ const circle_event_type &circle_event = circle_events_.top();
- int get_num_voronoi_edges() const {
- return num_edges_;
- }
+ // Retrieve the second bisector node that corresponds to the given
+ // circle event.
+ beach_line_iterator it_first = circle_event.get_bisector();
+ beach_line_iterator it_last = it_first;
- const BRect<coordinate_type> &get_bounding_rectangle() const {
- return voronoi_rect_;
- }
+ // Get the the third site.
+ site_event_type site3 = it_first->first.get_right_site();
- void simplify() {
- edges_iterator_type edge_it1;
- edges_iterator_type edge_it = edges_.begin();
+ // Get second bisector;
+ edge_type *bisector2 = it_first->second.get_edge();
+
+ // Get first bisector;
+ it_first--;
+ edge_type *bisector1 = it_first->second.get_edge();
+
+ // Get the first site that creates given circle event.
+ site_event_type site1 = it_first->first.get_left_site();
- // Return in case of collinear sites input.
- if (num_vertex_records_ == 0) {
- if (edge_it == edges_.end())
- return;
+ // Let circle event sites be A, B, C, two bisectors that define
+ // circle event be (A, B), (B, C). During circle event processing
+ // we remove (A, B), (B, C) and insert (A, C). As beach line nodes
+ // comparer doesn't work fine for the circle events we only remove
+ // (B, C) bisector and change (A, B) bisector to the (A, C). That's
+ // why we use const_cast there and take all the responsibility that
+ // map data structure keeps correct ordering.
+ if (!site1.is_segment() && site3.is_segment() &&
+ site3.get_point1(true) == site1.get_point0()) {
+ site3.set_inverse();
+ }
+ const_cast<Key &>(it_first->first).set_right_site(site3);
+ it_first->second.set_edge(output_.insert_new_edge(site1, site3, circle_event,
+ bisector1, bisector2));
+ beach_line_.erase(it_last);
+ it_last = it_first;
- edge_type *edge1 = &(*edge_it);
- edge1->next = edge1->prev = edge1;
- edge_it++;
- edge1 = &(*edge_it);
- edge_it++;
+ // Pop circle event from the event queue, before we might
+ // insert new events in it.
+ circle_events_.pop();
- while (edge_it != edges_.end()) {
- edge_type *edge2 = &(*edge_it);
- edge_it++;
-
- edge1->next = edge1->prev = edge2;
- edge2->next = edge2->prev = edge1;
+ // Check the new triplets formed by the neighboring arcs
+ // for potential circle events. Check left.
+ if (it_first != beach_line_.begin()) {
+ it_first->second.deactivate_circle_event();
+ it_first--;
+ const site_event_type &site_l1 = it_first->first.get_left_site();
+ activate_circle_event(site_l1, site1, site3, it_last);
+ }
+
+ // Check the new triplets formed by the neighboring arcs
+ // for potential circle events. Check right.
+ it_last++;
+ if (it_last != beach_line_.end()) {
+ it_last->second.deactivate_circle_event();
+ const site_event_type &site_r1 = it_last->first.get_right_site();
+ activate_circle_event(site1, site3, site_r1, it_last);
+ }
- edge1 = &(*edge_it);
- edge_it++;
- }
+ }
- edge1->next = edge1->prev = edge1;
- return;
+ // Insert new arc below site arc into the beach line.
+ beach_line_iterator insert_new_arc(const site_event_type &site_arc1,
+ const site_event_type &site_arc2,
+ const site_event_type &site_event,
+ const beach_line_iterator &position) {
+ // Create two new nodes.
+ Key new_left_node(site_arc1, site_event);
+ Key new_right_node(site_event, site_arc2);
+ if (site_event.is_segment()) {
+ new_right_node.set_left_site_inverse();
}
-
- // Iterate over all edges and remove degeneracies.
- while (edge_it != edges_.end()) {
- edge_it1 = edge_it;
- std::advance(edge_it, 2);
-
- if (!edge_it1->start_point || !edge_it1->end_point)
- continue;
-
- const voronoi_vertex_type *p1 = edge_it1->start_point;
- const voronoi_vertex_type *p2 = edge_it1->end_point;
- epsilon_robust_comparator<T> lhs1 = p1->center_x * p2->denom;
- epsilon_robust_comparator<T> rhs1 = p1->denom * p2->center_x;
- epsilon_robust_comparator<T> lhs2 = p1->center_y * p2->denom;
- epsilon_robust_comparator<T> rhs2 = p1->denom * p2->center_y;
-
- if (lhs1.compare(rhs1, 64) == UNDEFINED && lhs2.compare(rhs2, 64) == UNDEFINED) {
- // Decrease number of cell incident edges.
- edge_it1->cell->num_incident_edges--;
- edge_it1->twin->cell->num_incident_edges--;
-
- // To guarantee N*lon(N) time we merge vertex with
- // less incident edges to the one with more.
- if (edge_it1->cell->incident_edge == &(*edge_it1)) {
- if (edge_it1->cell->incident_edge == edge_it1->next) {
- edge_it1->cell->incident_edge = NULL;
- } else {
- edge_it1->cell->incident_edge = edge_it1->next;
- }
- }
- if (edge_it1->twin->cell->incident_edge == edge_it1->twin) {
- 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;
- }
+
+ // Insert two new nodes into the binary search tree.
+ // Update output.
+ edge_type *edge = output_.insert_new_edge(site_arc2, site_event);
+ beach_line_iterator it = beach_line_.insert(position,
+ std::pair<Key, Value>(new_right_node, Value(edge->twin())));
+ if (site_event.is_segment()) {
+ Key new_node(site_event, site_event);
+ new_node.set_right_site_inverse();
+ beach_line_iterator temp_it = beach_line_.insert(position,
+ std::pair<Key, Value>(new_node, Value(NULL)));
+ end_points_.push(std::make_pair(site_event.get_point1(), temp_it));
+ }
+ beach_line_.insert(position, std::pair<Key, Value>(new_left_node, Value(edge)));
+ return it;
+ }
+
+ // Create circle event from the given three points.
+ bool create_circle_event(const site_event_type &site1,
+ const site_event_type &site2,
+ const site_event_type &site3,
+ circle_event_type &c_event) const {
+ if (!site1.is_segment()) {
+ if (!site2.is_segment()) {
+ if (!site3.is_segment()) {
+ return create_circle_event_ppp(site1, site2, site3, c_event);
+ } else {
+ return create_circle_event_pps(site1, site2, site3, 3, c_event);
}
- if (edge_it1->start_point->num_incident_edges >=
- edge_it1->end_point->num_incident_edges) {
- simplify_edge(&(*edge_it1));
+ } else {
+ if (!site3.is_segment()) {
+ return create_circle_event_pps(site1, site3, site2, 2, c_event);
} else {
- simplify_edge(edge_it1->twin);
+ return create_circle_event_pss(site1, site2, site3, 1, c_event);
}
-
- // Remove zero length edges.
- edges_.erase(edge_it1, edge_it);
- num_edges_--;
}
- }
-
- // Make some post processing.
- for (voronoi_cell_iterator_type cell_it = cell_records_.begin();
- cell_it != cell_records_.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;
-
- // Terminate if this is not a boundary cell.
- if (cur_edge == cell_it->incident_edge)
- break;
+ } else {
+ if (!site2.is_segment()) {
+ if (!site3.is_segment()) {
+ return create_circle_event_pps(site2, site3, site1, 1, c_event);
+ } else {
+ return create_circle_event_pss(site2, site1, site3, 2, c_event);
}
-
- // Rewind incident edge pointer to the leftmost edge for the boundary cells.
- cell_it->incident_edge = cur_edge;
-
- // Set up prev/next half-edge pointers for 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;
+ } else {
+ if (!site3.is_segment()) {
+ return create_circle_event_pss(site3, site1, site2, 3, c_event);
+ } else {
+ return create_circle_event_sss(site1, site2, site3, c_event);
}
}
}
}
- void clip(voronoi_output_clipped<coordinate_type> &clipped_output) {
- coordinate_type x_len = (voronoi_rect_.x_max - voronoi_rect_.x_min);
- coordinate_type y_len = (voronoi_rect_.y_max - voronoi_rect_.y_min);
- coordinate_type x_mid = (voronoi_rect_.x_max + voronoi_rect_.x_min) /
- static_cast<coordinate_type>(2);
- coordinate_type y_mid = (voronoi_rect_.y_max + voronoi_rect_.y_min) /
- static_cast<coordinate_type>(2);
-
- coordinate_type offset = x_len;
- if (offset < y_len)
- offset = y_len;
-
- if (offset == static_cast<coordinate_type>(0.0))
- offset = 0.5;
-
- BRect<coordinate_type> new_brect(x_mid - offset, y_mid - offset,
- x_mid + offset, y_mid + offset);
- clip(new_brect, clipped_output);
- }
-
- private:
- // Simplify degenerate edge.
- void simplify_edge(edge_type *edge) {
- voronoi_vertex_type *vertex1 = edge->start_point;
- voronoi_vertex_type *vertex2 = edge->end_point;
-
- // Update number of incident edges.
- vertex1->num_incident_edges += vertex2->num_incident_edges - 2;
-
- // Update second vertex incident edges start and end points.
- edge_type *updated_edge = edge->twin->rot_next;
- while (updated_edge != edge->twin) {
- updated_edge->start_point = vertex1;
- updated_edge->twin->end_point = vertex1;
- updated_edge = updated_edge->rot_next;
- }
-
- edge_type *edge1 = edge;
- edge_type *edge2 = edge->twin;
-
- edge_type *edge1_rot_prev = edge1->rot_prev;
- edge_type *edge1_rot_next = edge1->rot_next;
-
- edge_type *edge2_rot_prev = edge2->rot_prev;
- edge_type *edge2_rot_next = edge2->rot_next;
-
- // Update prev and next pointers of incident edges.
- edge1_rot_next->twin->next = edge2_rot_prev;
- edge2_rot_prev->prev = edge1_rot_next->twin;
- edge1_rot_prev->prev = edge2_rot_next->twin;
- edge2_rot_next->twin->next = edge1_rot_prev;
-
- // Update rotation prev and next pointers of incident edges.
- edge1_rot_prev->rot_next = edge2_rot_next;
- edge2_rot_next->rot_prev = edge1_rot_prev;
- edge1_rot_next->rot_prev = edge2_rot_prev;
- edge2_rot_prev->rot_next = edge1_rot_next;
-
- // Change incident edge pointer of a vertex if it correspongs to the
- // degenerate edge.
- if (vertex1->incident_edge == edge)
- vertex1->incident_edge = edge->rot_prev;
-
- // Remove second vertex from the vertex records list.
- if (vertex1->voronoi_record_it != vertex2->voronoi_record_it) {
- vertex_records_.erase(vertex2->voronoi_record_it);
- num_vertex_records_--;
+ // Add new circle event to the event queue.
+ void activate_circle_event(const site_event_type &site1,
+ const site_event_type &site2,
+ const site_event_type &site3,
+ beach_line_iterator bisector_node) {
+ circle_event_type c_event;
+ if (create_circle_event(site1, site2, site3, c_event)) {
+ c_event.set_bisector(bisector_node);
+ bisector_node->second.activate_circle_event(circle_events_.push(c_event));
}
}
- void clip(const BRect<coordinate_type> &brect,
- voronoi_output_clipped<coordinate_type> &clipped_output) {
- if (!brect.is_valid())
- return;
- clipped_output.reset();
- clipped_output.bounding_rectangle = brect;
-
- // collinear input sites case.
- if (num_vertex_records_ == 0) {
- // Return in case of single site input.
- if (num_cell_records_ == 1) {
- clipped_output.cell_records.push_back(
- clipped_voronoi_cell_type(cell_records_.back().site, NULL));
- clipped_output.num_cell_records++;
- return;
- }
-
- edges_iterator_type edge_it = edges_.begin();
- while (edge_it != edges_.end()) {
- edge_type *cur_edge = &(*edge_it);
- edge_it++;
- edge_type *cur_twin_edge = &(*edge_it);
- edge_it++;
- // Add new clipped edges.
- clipped_edge_type &new_edge = add_clipped_edge(clipped_output);
- clipped_edge_type &new_twin_edge = add_clipped_edge(clipped_output);
-
- // Update twin pointers.
- new_edge.twin = &new_twin_edge;
- new_twin_edge.twin = &new_edge;
-
- // Update clipped edge pointers.
- cur_edge->clipped_edge = &new_edge;
- cur_twin_edge->clipped_edge = &new_twin_edge;
- }
- } else {
- // Iterate over all voronoi vertices.
- for (voronoi_vertex_const_iterator_type vertex_it = vertex_records_.begin();
- vertex_it != vertex_records_.end(); vertex_it++) {
- edge_type *cur_edge = vertex_it->incident_edge;
- const Point2D &cur_vertex_point = vertex_it->vertex;
-
- // Add current voronoi vertex to clipped output.
- clipped_output.vertex_records.push_back(
- clipped_voronoi_vertex_type(cur_vertex_point, NULL));
- clipped_output.num_vertex_records++;
- clipped_voronoi_vertex_type &new_vertex = clipped_output.vertex_records.back();
- new_vertex.num_incident_edges = vertex_it->num_incident_edges;
- clipped_edge_type *rot_prev_edge = NULL;
-
- // Process all half-edges incident to the current voronoi vertex.
- do {
- // Add new edge to the clipped output.
- clipped_edge_type &new_edge = add_clipped_edge(clipped_output);
- new_edge.start_point = &new_vertex;
- cur_edge->clipped_edge = &new_edge;
-
- // Ray edges with no start point don't correspond to any voronoi vertex.
- // That's why ray edges are processed during their twin edge processing.
- if (cur_edge->end_point == NULL) {
- // Add new twin edge.
- clipped_edge_type &new_twin_edge = add_clipped_edge(clipped_output);
- cur_edge->twin->clipped_edge = &new_twin_edge;
- }
-
- // Update twin and end point pointers.
- clipped_edge_type *twin = cur_edge->twin->clipped_edge;
- if (twin != NULL) {
- new_edge.twin = twin;
- twin->twin = &new_edge;
- new_edge.end_point = twin->start_point;
- twin->end_point = new_edge.start_point;
- }
-
- // Update rotation prev/next pointers.
- if (rot_prev_edge != NULL) {
- new_edge.rot_prev = rot_prev_edge;
- rot_prev_edge->rot_next = &new_edge;
- }
-
- rot_prev_edge = &new_edge;
- cur_edge = cur_edge->rot_next;
- } while(cur_edge != vertex_it->incident_edge);
-
- // Update rotation prev/next pointers.
- cur_edge->clipped_edge->rot_prev = rot_prev_edge;
- rot_prev_edge->rot_next = cur_edge->clipped_edge;
- new_vertex.incident_edge = cur_edge->clipped_edge;
- }
- }
-
- // Iterate over all voronoi cells.
- for (voronoi_cell_const_iterator_type cell_it = cell_records_.begin();
- cell_it != cell_records_.end(); cell_it++) {
- // Add new cell to the clipped output.
- clipped_output.cell_records.push_back(
- clipped_voronoi_cell_type(cell_it->site, NULL));
- clipped_output.num_cell_records++;
- clipped_voronoi_cell_type &new_cell = clipped_output.cell_records.back();
- edge_type *cur_edge = cell_it->incident_edge;
-
- // Update cell, next/prev pointers.
- if (cur_edge) {
- clipped_edge_type *prev = NULL;
- do {
- clipped_edge_type *new_edge = cur_edge->clipped_edge;
- if (new_edge) {
- if (prev) {
- new_edge->prev = prev;
- prev->next = new_edge;
- }
- new_edge->cell = &new_cell;
- if (new_cell.incident_edge == NULL)
- new_cell.incident_edge = cur_edge->clipped_edge;
- new_cell.num_incident_edges++;
- prev = new_edge;
- cur_edge->clipped_edge = NULL;
- }
- cur_edge = cur_edge->next;
- } while(cur_edge != cell_it->incident_edge);
-
- // Update prev/next pointers.
- if (prev) {
- prev->next = new_cell.incident_edge;
- new_cell.incident_edge->prev = prev;
- }
- }
+ private:
+ struct end_point_comparison {
+ bool operator() (const end_point_type &end1, const end_point_type &end2) const {
+ return end1.first > end2.first;
}
- clipped_output.num_edge_records >>= 1;
- }
-
- inline clipped_voronoi_edge_type &add_clipped_edge(
- voronoi_output_clipped<coordinate_type> &clipped_output) {
- clipped_output.edge_records.push_back(clipped_voronoi_edge_type());
- clipped_output.num_edge_records++;
- return clipped_output.edge_records.back();
- }
-
- std::vector<voronoi_cell_iterator_type> cell_iterators_;
- voronoi_cells_type cell_records_;
- voronoi_vertices_type vertex_records_;
- voronoi_edges_type edges_;
-
- int num_cell_records_;
- int num_vertex_records_;
- int num_edges_;
+ };
- BRect<coordinate_type> voronoi_rect_;
+ std::vector<site_event_type> site_events_;
+ site_events_iterator_type site_events_iterator_;
+ std::priority_queue< end_point_type, std::vector<end_point_type>,
+ end_point_comparison > end_points_;
+ CircleEventsQueue circle_events_;
+ BeachLine beach_line_;
+ Output &output_;
- // Disallow copy constructor and operator=
- voronoi_output(const voronoi_output&);
- void operator=(const voronoi_output&);
+ //Disallow copy constructor and operator=
+ voronoi_builder(const voronoi_builder&);
+ void operator=(const voronoi_builder&);
};
-
+
} // sweepline
} // boost
} // detail
Deleted: sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_builder.hpp
==============================================================================
--- sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_builder.hpp 2010-11-29 19:02:09 EST (Mon, 29 Nov 2010)
+++ (empty file)
@@ -1,438 +0,0 @@
-// Boost sweepline/voronoi_builder.hpp header file
-
-// Copyright Andrii Sydorchuk 2010.
-// Distributed under the Boost Software License, Version 1.0.
-// (See accompanying file LICENSE_1_0.txt or copy at
-// http://www.boost.org/LICENSE_1_0.txt)
-
-// See http://www.boost.org for updates, documentation, and revision history.
-
-#ifndef BOOST_SWEEPLINE_VORONOI_SEGMENT_BUILDER
-#define BOOST_SWEEPLINE_VORONOI_SEGMENT_BUILDER
-
-namespace boost {
-namespace sweepline {
-
- // Voronoi diagram builder. Sweepline sweeps from left to right.
- template <typename T>
- class voronoi_builder {
- public:
- typedef T coordinate_type;
- typedef point_2d<coordinate_type> Point2D;
- typedef std::pair<Point2D, Point2D> Segment2D;
- typedef voronoi_output_clipped<coordinate_type> ClippedOutput;
- typedef typename detail::site_event<coordinate_type> site_event_type;
- typedef typename detail::circle_event<coordinate_type> circle_event_type;
-
- voronoi_builder() {
- // Set sites iterator.
- site_events_iterator_ = site_events_.begin();
- }
-
- void init(std::vector<Point2D> &points) {
- std::vector<Segment2D> empty_vec;
- init(points, empty_vec);
- }
-
- void init(std::vector<Segment2D> &segments) {
- std::vector<Point2D> empty_vec;
- init(empty_vec, segments);
- }
-
- // Init beach line before sweepline run.
- // In case of a few first sites situated on the same
- // vertical line, we init beach line with all of them.
- // In other case just use the first two sites for the initialization.
- void init(std::vector<Point2D> &points, std::vector<Segment2D> &segments) {
- // Clear all data structures.
- reset();
-
- // TODO(asydorchuk): Add segments intersection check.
-
- // Avoid additional memory reallocations.
- site_events_.reserve(points.size() + segments.size() * 3);
-
- // Create site events from point sites.
- for (typename std::vector<Point2D>::const_iterator it = points.begin();
- it != points.end(); it++) {
- site_events_.push_back(detail::make_site_event(it->x(), it->y(), 0));
- }
-
- // Create site events from end points of segment sites and segment itself.
- for (typename std::vector<Segment2D>::const_iterator it = segments.begin();
- it != segments.end(); it++) {
- site_events_.push_back(detail::make_site_event(it->first, 0));
- site_events_.push_back(detail::make_site_event(it->second, 0));
- site_events_.push_back(detail::make_site_event(it->first, it->second, 0));
- }
-
- // Sort site events.
- sort(site_events_.begin(), site_events_.end());
-
- // Remove duplicates.
- site_events_.erase(unique(site_events_.begin(), site_events_.end()),
- site_events_.end());
-
- // Number sites.
- for (int cur_index = 0; cur_index < static_cast<int>(site_events_.size()); cur_index++)
- site_events_[cur_index].set_site_index(cur_index);
-
- // Set site iterator.
- site_events_iterator_ = site_events_.begin();
-
- // Init output with number of site events.
- // There will be one site event for each input point and three site events
- // for each input segment: both ends of a segment and the segment itself.
- output_.init(site_events_.size());
- }
-
- void reset() {
- output_.reset();
- circle_events_.reset();
- beach_line_.clear();
- site_events_.clear();
- site_events_iterator_ = site_events_.begin();
- }
-
- void run_sweepline() {
- // Init beach line.
- if (site_events_.empty()) {
- return;
- } else if (site_events_.size() == 1) {
- // Handle one input site case.
- output_.process_single_site(site_events_[0]);
- site_events_iterator_++;
- } else {
- int skip = 0;
- // Init beach line.
- while(site_events_iterator_ != site_events_.end() &&
- site_events_iterator_->x() == site_events_.begin()->x() &&
- site_events_iterator_->is_vertical()) {
- site_events_iterator_++;
- skip++;
- }
-
- if (skip == 1) {
- // Init beach line with two sites.
- init_beach_line();
- } else {
- // Init beach line with sites situated on the same vertical line.
- init_beach_line_collinear_sites();
- }
- }
-
- // Algorithm stops when there are no events to process.
- while (!circle_events_.empty() ||
- !(site_events_iterator_ == site_events_.end())) {
- if (circle_events_.empty()) {
- process_site_event();
- } else if (site_events_iterator_ == site_events_.end()) {
- process_circle_event();
- } else {
- if (circle_events_.top().compare(*site_events_iterator_) == detail::MORE) {
- process_site_event();
- } else {
- process_circle_event();
- }
- }
- }
-
- // Simplify output.
- output_.simplify();
- }
-
- // Returns output bounding rectangle that includes all the vertices and sites
- // of the voronoi diagram.
- const BRect<coordinate_type> &get_bounding_rectangle() const {
- return output_.get_bounding_rectangle();
- }
-
- // Clip using bounding rectangle that includes all the vertices and sites
- // of the voronoi diagram.
- void clip(ClippedOutput &clipped_output) {
- output_.clip(clipped_output);
- }
-
- protected:
- typedef typename std::vector<site_event_type>::const_iterator site_events_iterator_type;
-
- typedef detail::voronoi_output<coordinate_type> Output;
- typedef typename Output::edge_type edge_type;
-
- typedef typename detail::circle_events_queue<coordinate_type> CircleEventsQueue;
- typedef typename detail::beach_line_node<coordinate_type> Key;
- typedef typename detail::beach_line_node_data<coordinate_type> Value;
- typedef typename detail::node_comparer<Key> NodeComparer;
- typedef std::map< Key, Value, NodeComparer > BeachLine;
- typedef typename std::map< Key, Value, NodeComparer >::iterator beach_line_iterator;
- typedef typename std::pair<Point2D, beach_line_iterator> end_point_type;
-
- void init_beach_line() {
- // The first site is always a point.
- // Get the first and the second site events.
- site_events_iterator_type it_first = site_events_.begin();
- site_events_iterator_type it_second = site_events_.begin();
- it_second++;
-
- // Insert new nodes.
- insert_new_arc(*it_first, *it_first, *it_second, beach_line_.begin());
-
- // The second site has been already processed.
- site_events_iterator_++;
- }
-
- // Insert bisectors for all collinear initial sites.
- // There should be at least two colinear sites.
- void init_beach_line_collinear_sites() {
- site_events_iterator_type it_first = site_events_.begin();
- site_events_iterator_type it_second = site_events_.begin();
- it_second++;
- while (it_second != site_events_iterator_) {
- // Create new beach line node.
- Key new_node(*it_first, *it_second);
-
- // Update output.
- edge_type *edge = output_.insert_new_edge(*it_first, *it_second);
-
- // Insert new node into the binary search tree.
- beach_line_.insert(std::pair<Key, Value>(new_node, Value(edge)));
-
- // Update iterators.
- it_first++;
- it_second++;
- }
- }
-
- // Uses special comparison function for the lower bound and insertion
- // operations.
- void process_site_event() {
- site_event_type site_event = *site_events_iterator_;
- site_events_iterator_++;
-
- // If new site is end point of some segment, remove temporary nodes from
- // beach line data structure.
- if (!site_event.is_segment()) {
- while (!end_points_.empty() && end_points_.top().first == site_event.get_point0()) {
- beach_line_.erase(end_points_.top().second);
- end_points_.pop();
- }
- }
-
- // Find the node in the binary search tree with left arc
- // lying above the new site point.
- Key new_key(site_event);
- beach_line_iterator it = beach_line_.lower_bound(new_key);
- int it_dist = site_event.is_segment() ? 2 : 1;
-
- if (it == beach_line_.end()) {
- it--;
- const site_event_type &site_arc = it->first.get_right_site();
-
- // Insert new arc into the sweepline.
- beach_line_iterator new_node_it = insert_new_arc(site_arc, site_arc, site_event, it);
- std::advance(new_node_it, -it_dist);
-
- // Add candidate circle to the event queue.
- activate_circle_event(it->first.get_left_site(), it->first.get_right_site(),
- site_event, new_node_it);
- } else if (it == beach_line_.begin()) {
- const site_event_type &site_arc = it->first.get_left_site();
-
- // Insert new arc into the sweepline.
- insert_new_arc(site_arc, site_arc, site_event, it);
-
- // Add candidate circle to the event queue.
- if (site_event.is_segment()) {
- site_event.set_inverse();
- }
- activate_circle_event(site_event, it->first.get_left_site(),
- it->first.get_right_site(), it);
- } else {
- const site_event_type &site_arc2 = it->first.get_left_site();
- const site_event_type &site3 = it->first.get_right_site();
-
- // Remove candidate circle from the event queue.
- it->second.deactivate_circle_event();
- it--;
- const site_event_type &site_arc1 = it->first.get_right_site();
- const site_event_type &site1 = it->first.get_left_site();
-
- // Insert new arc into the sweepline.
- beach_line_iterator new_node_it =
- insert_new_arc(site_arc1, site_arc2, site_event, it);
-
- // Add candidate circles to the event queue.
- std::advance(new_node_it, -it_dist);
- activate_circle_event(site1, site_arc1, site_event, new_node_it);
- if (site_event.is_segment()) {
- site_event.set_inverse();
- }
- std::advance(new_node_it, it_dist + 1);
- activate_circle_event(site_event, site_arc2, site3, new_node_it);
- }
- }
-
- // Doesn't use special comparison function as it works fine only for
- // the site events processing.
- void process_circle_event() {
- const circle_event_type &circle_event = circle_events_.top();
-
- // Retrieve the second bisector node that corresponds to the given
- // circle event.
- beach_line_iterator it_first = circle_event.get_bisector();
- beach_line_iterator it_last = it_first;
-
- // Get the the third site.
- site_event_type site3 = it_first->first.get_right_site();
-
- // Get second bisector;
- edge_type *bisector2 = it_first->second.get_edge();
-
- // Get first bisector;
- it_first--;
- edge_type *bisector1 = it_first->second.get_edge();
-
- // Get the first site that creates given circle event.
- site_event_type site1 = it_first->first.get_left_site();
-
- // Let circle event sites be A, B, C, two bisectors that define
- // circle event be (A, B), (B, C). During circle event processing
- // we remove (A, B), (B, C) and insert (A, C). As beach line nodes
- // comparer doesn't work fine for the circle events we only remove
- // (B, C) bisector and change (A, B) bisector to the (A, C). That's
- // why we use const_cast there and take all the responsibility that
- // map data structure keeps correct ordering.
- if (!site1.is_segment() && site3.is_segment() &&
- site3.get_point1(true) == site1.get_point0()) {
- site3.set_inverse();
- }
- const_cast<Key &>(it_first->first).set_right_site(site3);
- it_first->second.set_edge(output_.insert_new_edge(site1, site3, circle_event,
- bisector1, bisector2));
- beach_line_.erase(it_last);
- it_last = it_first;
-
- // Pop circle event from the event queue, before we might
- // insert new events in it.
- circle_events_.pop();
-
- // Check the new triplets formed by the neighboring arcs
- // for potential circle events. Check left.
- if (it_first != beach_line_.begin()) {
- it_first->second.deactivate_circle_event();
- it_first--;
- const site_event_type &site_l1 = it_first->first.get_left_site();
- activate_circle_event(site_l1, site1, site3, it_last);
- }
-
- // Check the new triplets formed by the neighboring arcs
- // for potential circle events. Check right.
- it_last++;
- if (it_last != beach_line_.end()) {
- it_last->second.deactivate_circle_event();
- const site_event_type &site_r1 = it_last->first.get_right_site();
- activate_circle_event(site1, site3, site_r1, it_last);
- }
-
- }
-
- // Insert new arc below site arc into the beach line.
- beach_line_iterator insert_new_arc(const site_event_type &site_arc1,
- const site_event_type &site_arc2,
- const site_event_type &site_event,
- const beach_line_iterator &position) {
- // Create two new nodes.
- Key new_left_node(site_arc1, site_event);
- Key new_right_node(site_event, site_arc2);
- if (site_event.is_segment()) {
- new_right_node.set_left_site_inverse();
- }
-
- // Insert two new nodes into the binary search tree.
- // Update output.
- edge_type *edge = output_.insert_new_edge(site_arc2, site_event);
- beach_line_iterator it = beach_line_.insert(position,
- std::pair<Key, Value>(new_right_node, Value(edge->twin)));
- if (site_event.is_segment()) {
- Key new_node(site_event, site_event);
- new_node.set_right_site_inverse();
- beach_line_iterator temp_it = beach_line_.insert(position,
- std::pair<Key, Value>(new_node, Value(NULL)));
- end_points_.push(std::make_pair(site_event.get_point1(), temp_it));
- }
- beach_line_.insert(position, std::pair<Key, Value>(new_left_node, Value(edge)));
- return it;
- }
-
- // Create circle event from the given three points.
- bool create_circle_event(const site_event_type &site1,
- const site_event_type &site2,
- const site_event_type &site3,
- circle_event_type &c_event) const {
- if (!site1.is_segment()) {
- if (!site2.is_segment()) {
- if (!site3.is_segment()) {
- return detail::create_circle_event_ppp(site1, site2, site3, c_event);
- } else {
- return detail::create_circle_event_pps(site1, site2, site3, 3, c_event);
- }
- } else {
- if (!site3.is_segment()) {
- return detail::create_circle_event_pps(site1, site3, site2, 2, c_event);
- } else {
- return detail::create_circle_event_pss(site1, site2, site3, 1, c_event);
- }
- }
- } else {
- if (!site2.is_segment()) {
- if (!site3.is_segment()) {
- return detail::create_circle_event_pps(site2, site3, site1, 1, c_event);
- } else {
- return detail::create_circle_event_pss(site2, site1, site3, 2, c_event);
- }
- } else {
- if (!site3.is_segment()) {
- return detail::create_circle_event_pss(site3, site1, site2, 3, c_event);
- } else {
- return detail::create_circle_event_sss(site1, site2, site3, c_event);
- }
- }
- }
- }
-
- // Add new circle event to the event queue.
- void activate_circle_event(const site_event_type &site1,
- const site_event_type &site2,
- const site_event_type &site3,
- beach_line_iterator bisector_node) {
- circle_event_type c_event;
- if (create_circle_event(site1, site2, site3, c_event)) {
- c_event.set_bisector(bisector_node);
- bisector_node->second.activate_circle_event(circle_events_.push(c_event));
- }
- }
-
- private:
- struct end_point_comparison {
- bool operator() (const end_point_type &end1, const end_point_type &end2) const {
- return end1.first > end2.first;
- }
- };
-
- std::vector<site_event_type> site_events_;
- site_events_iterator_type site_events_iterator_;
- std::priority_queue< end_point_type, std::vector<end_point_type>,
- end_point_comparison > end_points_;
- CircleEventsQueue circle_events_;
- BeachLine beach_line_;
- Output output_;
-
- //Disallow copy constructor and operator=
- voronoi_builder(const voronoi_builder&);
- void operator=(const voronoi_builder&);
- };
-
-} // sweepline
-} // boost
-
-#endif
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-11-29 19:02:09 EST (Mon, 29 Nov 2010)
@@ -7,11 +7,41 @@
// See http://www.boost.org for updates, documentation, and revision history.
-#ifndef BOOST_SWEEPLINE_VORONOI_SEGMENT_OUTPUT
-#define BOOST_SWEEPLINE_VORONOI_SEGMENT_OUTPUT
+#ifndef BOOST_SWEEPLINE_VORONOI_OUTPUT
+#define BOOST_SWEEPLINE_VORONOI_OUTPUT
namespace boost {
namespace sweepline {
+
+ ///////////////////////////////////////////////////////////////////////////
+ // VORONOI OUTPUT TYPES ///////////////////////////////////////////////////
+ ///////////////////////////////////////////////////////////////////////////
+
+ // Forward declarations.
+ namespace detail {
+ template <typename T>
+ class site_event;
+
+ template <typename T>
+ class circle_event;
+
+ template <typename T>
+ class epsilon_robust_comparator;
+
+ template <typename T>
+ class voronoi_builder;
+ }
+
+ template <typename T>
+ class voronoi_cell;
+
+ template <typename T>
+ class voronoi_edge;
+
+ template <typename T>
+ class voronoi_output;
+
+ // Represents 2D point.
template <typename T>
class point_2d {
public:
@@ -77,64 +107,74 @@
point_2d<T> make_point_2d(T x, T y) {
return point_2d<T>(x,y);
}
-
- ///////////////////////////////////////////////////////////////////////////
- // VORONOI OUTPUT TYPES ///////////////////////////////////////////////////
- ///////////////////////////////////////////////////////////////////////////
- namespace detail {
- template <typename T>
- class site_event;
- }
// Bounding rectangle data structure.
template <typename T>
- struct BRect {
+ class BRect {
public:
typedef T coordinate_type;
- typedef point_2d<T> Point2D;
-
- 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());
+ BRect(const point_2d<T> &p1, const point_2d<T> &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());
}
BRect(coordinate_type x_mn, coordinate_type y_mn,
coordinate_type x_mx, coordinate_type y_mx) {
- x_min = (std::min)(x_mn, x_mx);
- y_min = (std::min)(y_mn, y_mx);
- x_max = (std::max)(x_mn, x_mx);
- y_max = (std::max)(y_mn, y_mx);
+ x_min_ = (std::min)(x_mn, x_mx);
+ y_min_ = (std::min)(y_mn, y_mx);
+ x_max_ = (std::max)(x_mn, x_mx);
+ y_max_ = (std::max)(y_mn, y_mx);
}
- 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());
+ void update(const point_2d<T> &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());
}
- bool contains(const Point2D &p) const {
- return p.x() > x_min && p.x() < x_max && p.y() > y_min && p.y() < y_max;
+ bool contains(const point_2d<T> &p) const {
+ return p.x() > x_min_ && p.x() < x_max_ && p.y() > y_min_ && p.y() < y_max_;
}
bool is_valid() const {
- return (x_min < x_max) && (y_min < y_max);
+ return (x_min_ < x_max_) && (y_min_ < y_max_);
}
+
+ coordinate_type x_min() const {
+ return x_min_;
+ }
+
+ coordinate_type y_min() const {
+ return y_min_;
+ }
+
+ coordinate_type x_max() const {
+ return x_max_;
+ }
+
+ coordinate_type y_max() const {
+ return y_max_;
+ }
+
+ private:
+ coordinate_type x_min_;
+ coordinate_type y_min_;
+ coordinate_type x_max_;
+ coordinate_type y_max_;
};
+ // Contains output visualization tools.
template <typename T>
- class Helper {
+ class voronoi_helper {
public:
typedef T coordinate_type;
+ typedef point_2d<T> Point2D;
enum kEdgeType {
SEGMENT = 0,
@@ -143,19 +183,18 @@
};
// Find edge(segment, ray, line) rectangle intersetion points.
- static bool find_intersections(const point_2d<coordinate_type> &origin,
- const point_2d<coordinate_type> &direction,
+ static bool find_intersections(const Point2D &origin, const Point2D &direction,
kEdgeType edge_type, const BRect<coordinate_type> &brect,
- std::vector< point_2d<coordinate_type> > &intersections) {
+ std::vector< Point2D > &intersections) {
coordinate_type half = static_cast<coordinate_type>(0.5);
// Find rectangle center.
- coordinate_type center_x = (brect.x_min + brect.x_max) * half;
- coordinate_type center_y = (brect.y_min + brect.y_max) * half;
+ coordinate_type center_x = (brect.x_min() + brect.x_max()) * half;
+ coordinate_type center_y = (brect.y_min() + brect.y_max()) * half;
// Find rectangle half-diagonal vector.
- coordinate_type len_x = brect.x_max - center_x;
- coordinate_type len_y = brect.y_max - center_y;
+ coordinate_type len_x = brect.x_max() - center_x;
+ coordinate_type len_y = brect.y_max() - center_y;
// Find distance between origin and center of rectangle.
coordinate_type diff_x = origin.x() - center_x;
@@ -177,8 +216,8 @@
// origin + fT[i] * direction = intersections point, i = 0 .. 1.
bool fT0_used = false;
bool fT1_used = false;
- double fT0 = 0.0;
- double fT1 = 0.0;
+ coordinate_type fT0 = 0;
+ coordinate_type fT1 = 0;
// Find intersections with lines going through sides of a bounding rectangle.
clip_line(+direction.x(), -diff_x - len_x, fT0_used, fT1_used, fT0, fT1);
@@ -192,14 +231,13 @@
if (fT1_used && fT0 != fT1 && check_extent(fT1, edge_type))
intersections.push_back(make_point_2d(origin.x() + fT1 * direction.x(),
origin.y() + fT1 * direction.y()));
-
return fT0_used && fT1_used;
}
- static void fill_intermediate_points(point_2d<coordinate_type> point_site,
- point_2d<coordinate_type> segment_site_start,
- point_2d<coordinate_type> segment_site_end,
- std::vector< point_2d<double> > &intermediate_points) {
+ static void fill_intermediate_points(Point2D point_site,
+ Point2D segment_site_start,
+ Point2D segment_site_end,
+ std::vector<Point2D> &intermediate_points) {
int num_inter_points = get_intermediate_points_count(
intermediate_points[0], intermediate_points[1]);
if (num_inter_points <= 0 ||
@@ -208,54 +246,116 @@
return;
}
intermediate_points.reserve(2 + num_inter_points);
- double segm_vec_x = static_cast<double>(segment_site_end.x()) -
- static_cast<double>(segment_site_start.x());
- double segm_vec_y = static_cast<double>(segment_site_end.y()) -
- static_cast<double>(segment_site_start.y());
- double sqr_segment_length = segm_vec_x * segm_vec_x + segm_vec_y * segm_vec_y;
- double projection_start =
+ coordinate_type segm_vec_x = segment_site_end.x() - segment_site_start.x();
+ coordinate_type segm_vec_y = segment_site_end.y() - segment_site_start.y();
+ coordinate_type sqr_segment_length = segm_vec_x * segm_vec_x + segm_vec_y * segm_vec_y;
+ coordinate_type projection_start =
get_point_projection(intermediate_points[0], segment_site_start, segment_site_end);
- double projection_end =
+ coordinate_type projection_end =
get_point_projection(intermediate_points[1], segment_site_start, segment_site_end);
- double step = (projection_end - projection_start) *
+ coordinate_type step = (projection_end - projection_start) *
sqr_segment_length / (num_inter_points + 1);
- double point_vec_x = static_cast<double>(point_site.x()) -
- static_cast<double>(segment_site_start.x());
- double point_vec_y = static_cast<double>(point_site.y()) -
- static_cast<double>(segment_site_start.y());
- double point_rot_x = segm_vec_x * point_vec_x + segm_vec_y * point_vec_y;
- double point_rot_y = segm_vec_x * point_vec_y - segm_vec_y * point_vec_x;
- double projection_cur_x = projection_start * sqr_segment_length + step;
+ coordinate_type point_vec_x = point_site.x() - segment_site_start.x();
+ coordinate_type point_vec_y = point_site.y() - segment_site_start.y();
+ coordinate_type point_rot_x = segm_vec_x * point_vec_x + segm_vec_y * point_vec_y;
+ coordinate_type point_rot_y = segm_vec_x * point_vec_y - segm_vec_y * point_vec_x;
+ coordinate_type projection_cur_x = projection_start * sqr_segment_length + step;
point_2d<T> last_point = intermediate_points.back();
intermediate_points.pop_back();
for (int i = 0; i < num_inter_points; i++, projection_cur_x += step) {
- double inter_rot_x = projection_cur_x;
- double inter_rot_y =
+ coordinate_type inter_rot_x = projection_cur_x;
+ coordinate_type inter_rot_y =
((inter_rot_x - point_rot_x) * (inter_rot_x - point_rot_x) +
point_rot_y * point_rot_y) / (2.0 * point_rot_y);
- double new_point_x = (segm_vec_x * inter_rot_x - segm_vec_y * inter_rot_y) /
- sqr_segment_length + static_cast<double>(segment_site_start.x());
- double new_point_y = (segm_vec_x * inter_rot_y + segm_vec_y * inter_rot_x) /
- sqr_segment_length + static_cast<double>(segment_site_start.y());
+ coordinate_type new_point_x =
+ (segm_vec_x * inter_rot_x - segm_vec_y * inter_rot_y) /
+ sqr_segment_length + segment_site_start.x();
+ coordinate_type new_point_y =
+ (segm_vec_x * inter_rot_y + segm_vec_y * inter_rot_x) /
+ sqr_segment_length + segment_site_start.y();
intermediate_points.push_back(make_point_2d(new_point_x, new_point_y));
}
intermediate_points.push_back(last_point);
}
+
+ static BRect<coordinate_type> get_view_rectangle(const BRect<coordinate_type> &brect) {
+ coordinate_type x_len = (brect.x_max() - brect.x_min());
+ coordinate_type y_len = (brect.y_max() - brect.y_min());
+ coordinate_type x_mid = (brect.x_max() + brect.x_min()) / 2;
+ coordinate_type y_mid = (brect.y_max() + brect.y_min()) / 2;
+ coordinate_type offset = x_len;
+ if (offset < y_len)
+ offset = y_len;
+ if (offset == 0.0)
+ offset = 0.5;
+ BRect<coordinate_type> new_brect(x_mid - offset, y_mid - offset,
+ x_mid + offset, y_mid + offset);
+ return new_brect;
+ }
+
+ static std::vector< point_2d<coordinate_type> > get_intermediate_points(
+ const voronoi_edge<coordinate_type> *edge, const BRect<T> &brect) {
+ const voronoi_cell<coordinate_type> *cell1 = edge->cell();
+ const voronoi_cell<coordinate_type> *cell2 = edge->twin()->cell();
+ std::vector<Point2D> edge_points;
+ if (!(cell1->contains_segment() ^ cell2->contains_segment())) {
+ if (edge->vertex0() != NULL && edge->vertex1() != NULL) {
+ edge_points.push_back(edge->vertex0()->vertex());
+ edge_points.push_back(edge->vertex1()->vertex());
+ } else {
+ const Point2D &site1 = cell1->get_point0();
+ const Point2D &site2 = cell2->get_point0();
+ Point2D origin((site1.x() + site2.x()) * static_cast<coordinate_type>(0.5),
+ (site1.y() + site2.y()) * static_cast<coordinate_type>(0.5));
+ Point2D direction(site1.y() - site2.y(), site2.x() - site1.x());
+ find_intersections(origin, direction, LINE, brect, edge_points);
+ if (edge->vertex1() != NULL)
+ edge_points[1] = edge->vertex1()->vertex();
+ if (edge->vertex0() != NULL)
+ edge_points[0] = edge->vertex0()->vertex();
+ }
+ } else {
+ const Point2D &point1 = (cell1->contains_segment()) ?
+ cell2->get_point0() : cell1->get_point0();
+ const Point2D &point2 = (cell1->contains_segment()) ?
+ cell1->get_point0() : cell2->get_point0();
+ const Point2D &point3 = (cell1->contains_segment()) ?
+ cell1->get_point1() : cell2->get_point1();
+ if (edge->vertex0() != NULL && edge->vertex1() != NULL) {
+ edge_points.push_back(edge->vertex0()->vertex());
+ edge_points.push_back(edge->vertex1()->vertex());
+ fill_intermediate_points(point1, point2, point3, edge_points);
+ } else {
+ coordinate_type dir_x = (cell1->contains_segment() ^ (point1 == point3)) ?
+ point3.y() - point2.y() : point2.y() - point3.y();
+ coordinate_type dir_y = (cell1->contains_segment() ^ (point1 == point3)) ?
+ point2.x() - point3.x() : point3.x() - point2.x();
+ Point2D direction(dir_x, dir_y);
+ find_intersections(point1, direction, LINE, brect, edge_points);
+ if (edge->vertex1() != NULL)
+ edge_points[1] = edge->vertex1()->vertex();
+ if (edge->vertex0() != NULL)
+ edge_points[0] = edge->vertex0()->vertex();
+ }
+ }
+ return edge_points;
+ }
private:
- Helper();
+ voronoi_helper();
- static bool check_extent(double extent, kEdgeType etype) {
+ static bool check_extent(coordinate_type extent, kEdgeType etype) {
switch (etype) {
- case SEGMENT: return extent >= 0.0 && extent <= 1.0;
- case RAY: return extent >= 0.0;
+ case SEGMENT: return extent >= static_cast<coordinate_type>(0.0) &&
+ extent <= static_cast<coordinate_type>(1.0);
+ case RAY: return extent >= static_cast<coordinate_type>(0.0);
case LINE: return true;
}
return true;
}
static coordinate_type magnitude(coordinate_type value) {
- if (value >= static_cast<coordinate_type>(0))
+ if (value >= static_cast<coordinate_type>(0.0))
return value;
return -value;
}
@@ -263,8 +363,9 @@
static bool clip_line(coordinate_type denom,
coordinate_type numer,
bool &fT0_used, bool &fT1_used,
- double &fT0, double &fT1) {
- if (denom > static_cast<coordinate_type>(0)) {
+ coordinate_type &fT0,
+ coordinate_type &fT1) {
+ if (denom > static_cast<coordinate_type>(0.0)) {
if (fT1_used && numer > denom * fT1)
return false;
if (!fT0_used || numer > denom * fT0) {
@@ -272,7 +373,7 @@
fT0 = numer / denom;
}
return true;
- } else if (denom < static_cast<coordinate_type>(0)) {
+ } else if (denom < static_cast<coordinate_type>(0.0)) {
if (fT0_used && numer > denom * fT0)
return false;
if (!fT1_used || numer > denom * fT1) {
@@ -284,80 +385,117 @@
return false;
}
- static double get_point_projection(point_2d<coordinate_type> point,
- point_2d<coordinate_type> segment_start,
- point_2d<coordinate_type> segment_end) {
- double segment_vec_x = static_cast<double>(segment_end.x()) -
- static_cast<double>(segment_start.x());
- double segment_vec_y = static_cast<double>(segment_end.y()) -
- static_cast<double>(segment_start.y());
- double point_vec_x = static_cast<double>(point.x()) -
- static_cast<double>(segment_start.x());
- double point_vec_y = static_cast<double>(point.y()) -
- static_cast<double>(segment_start.y());
- double sqr_segment_length = segment_vec_x * segment_vec_x +
- segment_vec_y * segment_vec_y;
- double vec_dot = segment_vec_x * point_vec_x +
- segment_vec_y * point_vec_y;
+ static coordinate_type get_point_projection(const Point2D &point,
+ const Point2D &segment_start,
+ const Point2D &segment_end) {
+ coordinate_type segment_vec_x = segment_end.x() - segment_start.x();
+ coordinate_type segment_vec_y = segment_end.y() - segment_start.y();
+ coordinate_type point_vec_x = point.x() - segment_start.x();
+ coordinate_type point_vec_y = point.y() - segment_start.y();
+ coordinate_type sqr_segment_length = segment_vec_x * segment_vec_x +
+ segment_vec_y * segment_vec_y;
+ coordinate_type vec_dot = segment_vec_x * point_vec_x +
+ segment_vec_y * point_vec_y;
return vec_dot / sqr_segment_length;
}
- static int get_intermediate_points_count(point_2d<coordinate_type> point1,
- point_2d<coordinate_type> point2) {
- double vec_x = static_cast<double>(point1.x()) - static_cast<double>(point2.x());
- double vec_y = static_cast<double>(point1.y()) - static_cast<double>(point2.y());
- double sqr_len = vec_x * vec_x + vec_y * vec_y;
+ static int get_intermediate_points_count(const Point2D &point1,
+ const Point2D &point2) {
+ coordinate_type vec_x = point1.x() - point2.x();
+ coordinate_type vec_y = point1.y() - point2.y();
+ coordinate_type sqr_len = vec_x * vec_x + vec_y * vec_y;
return static_cast<int>(log(sqr_len) * 3.4 + 1E-6);
}
};
-
- template <typename T>
- struct voronoi_edge_clipped;
template <typename T>
- struct voronoi_cell_clipped {
+ class voronoi_cell {
+ public:
typedef T coordinate_type;
typedef detail::site_event<T> site_event_type;
+ typedef voronoi_edge<T> voronoi_edge_type;
+
+ bool contains_segment() const {
+ return site_.is_segment();
+ }
- voronoi_edge_clipped<coordinate_type> *incident_edge;
- int num_incident_edges;
+ const point_2d<T> &get_point0() const {
+ return site_.get_point0();
+ }
- voronoi_cell_clipped(const site_event_type &new_site,
- voronoi_edge_clipped<coordinate_type>* edge) :
- incident_edge(edge),
- num_incident_edges(0),
- site(new_site) {}
+ const point_2d<T> &get_point1() const {
+ return site_.get_point1();
+ }
- bool contains_segment() const {
- return site.is_segment();
+ voronoi_edge_type *incident_edge() {
+ return incident_edge_;
}
- point_2d<T> get_point0() const {
- return site.get_point0();
+ const voronoi_edge_type *incident_edge() const {
+ return incident_edge_;
}
- point_2d<T> get_point1() const {
- return site.get_point1();
+ int num_incident_edges() const {
+ return num_incident_edges_;
}
- private:
- site_event_type site;
+ voronoi_cell(const site_event_type &new_site, voronoi_edge_type *edge) :
+ site_(new_site),
+ incident_edge_(edge),
+ num_incident_edges_(0) {}
+ private:
+ friend class voronoi_output<T>;
+
+ site_event_type site_;
+ voronoi_edge_type *incident_edge_;
+ int num_incident_edges_;
};
template <typename T>
- struct voronoi_vertex_clipped {
+ class voronoi_vertex {
+ public:
typedef T coordinate_type;
- typedef point_2d<T> Point2D;
+ typedef voronoi_edge<T> voronoi_edge_type;
+
+ detail::epsilon_robust_comparator<T> center_x;
+ detail::epsilon_robust_comparator<T> center_y;
+ detail::epsilon_robust_comparator<T> denom;
+ typename std::list< voronoi_vertex<coordinate_type> >::iterator voronoi_record_it;
+
+ voronoi_vertex(const detail::epsilon_robust_comparator<T> &c_x,
+ const detail::epsilon_robust_comparator<T> &c_y,
+ const detail::epsilon_robust_comparator<T> &den,
+ voronoi_edge_type *edge) :
+ center_x(c_x),
+ center_y(c_y),
+ denom(den),
+ vertex_(c_x.dif() / den.dif(), c_y.dif() / den.dif()),
+ incident_edge_(edge),
+ num_incident_edges_(0) {}
+
+ const point_2d<T> &vertex() const {
+ return vertex_;
+ }
+
+ voronoi_edge_type *incident_edge() {
+ return incident_edge_;
+ }
+
+ const voronoi_edge_type *incident_edge() const {
+ return incident_edge_;
+ }
+
+ int num_incident_edges() const {
+ return num_incident_edges_;
+ }
+
+ private:
+ friend class voronoi_output<T>;
- voronoi_edge_clipped<coordinate_type> *incident_edge;
- Point2D vertex;
- int num_incident_edges;
-
- voronoi_vertex_clipped(const Point2D &point, voronoi_edge_clipped<coordinate_type>* edge) :
- incident_edge(edge),
- vertex(point),
- num_incident_edges(0) {}
+ point_2d<T> vertex_;
+ voronoi_edge_type *incident_edge_;
+ int num_incident_edges_;
};
// Half-edge data structure. Represents voronoi edge.
@@ -368,130 +506,432 @@
// around start point;
// 5) pointer to twin half-edge.
template <typename T>
- struct voronoi_edge_clipped {
- typedef T coordinate_type;
- typedef point_2d<T> Point2D;
- typedef voronoi_cell_clipped<coordinate_type> voronoi_cell_type;
- typedef voronoi_vertex_clipped<coordinate_type> voronoi_vertex_type;
- typedef voronoi_edge_clipped<coordinate_type> voronoi_edge_type;
- typedef detail::site_event<coordinate_type> site_event_type;
+ class voronoi_edge {
+ public:
+ typedef voronoi_cell<T> voronoi_cell_type;
+ typedef voronoi_vertex<T> voronoi_vertex_type;
+ typedef voronoi_edge<T> voronoi_edge_type;
- voronoi_cell_type *cell;
- voronoi_vertex_type *start_point;
- voronoi_vertex_type *end_point;
- voronoi_edge_type *prev;
- voronoi_edge_type *next;
- voronoi_edge_type *rot_prev;
- voronoi_edge_type *rot_next;
- voronoi_edge_type *twin;
-
- voronoi_edge_clipped() :
- cell(NULL),
- start_point(NULL),
- end_point(NULL),
- prev(NULL),
- next(NULL),
- rot_prev(NULL),
- rot_next(NULL),
- twin(NULL) {}
-
- std::vector<Point2D> get_intermediate_points(BRect<T> &brect) const {
- const voronoi_cell_type *cell1 = cell;
- const voronoi_cell_type *cell2 = twin->cell;
- std::vector<Point2D> edge_points;
- if (!(cell1->contains_segment() ^ cell2->contains_segment())) {
- if (start_point != NULL && end_point != NULL) {
- edge_points.push_back(start_point->vertex);
- edge_points.push_back(end_point->vertex);
- } else {
- const Point2D &site1 = cell1->get_point0();
- const Point2D &site2 = cell2->get_point0();
- Point2D origin((site1.x() + site2.x()) * static_cast<coordinate_type>(0.5),
- (site1.y() + site2.y()) * static_cast<coordinate_type>(0.5));
- Point2D direction(site1.y() - site2.y(), site2.x() - site1.x());
- Helper<T>::find_intersections(origin, direction, Helper<T>::LINE,
- brect, edge_points);
- if (end_point != NULL)
- edge_points[1] = end_point->vertex;
- if (start_point != NULL)
- edge_points[0] = start_point->vertex;
- }
- } else {
- const Point2D &point1 = (cell1->contains_segment()) ?
- cell2->get_point0() : cell1->get_point0();
- const Point2D &point2 = (cell1->contains_segment()) ?
- cell1->get_point0() : cell2->get_point0();
- const Point2D &point3 = (cell1->contains_segment()) ?
- cell1->get_point1() : cell2->get_point1();
- if (start_point != NULL && end_point != NULL) {
- edge_points.push_back(start_point->vertex);
- edge_points.push_back(end_point->vertex);
- Helper<T>::fill_intermediate_points(point1, point2, point3, edge_points);
- } else {
- coordinate_type dir_x = (cell1->contains_segment() ^ (point1 == point3)) ?
- point3.y() - point2.y() : point2.y() - point3.y();
- coordinate_type dir_y = (cell1->contains_segment() ^ (point1 == point3)) ?
- point2.x() - point3.x() : point3.x() - point2.x();
- Point2D direction(dir_x, dir_y);
- Helper<T>::find_intersections(point1, direction, Helper<T>::LINE,
- brect, edge_points);
- if (end_point != NULL)
- edge_points[1] = end_point->vertex;
- if (start_point != NULL)
- edge_points[0] = start_point->vertex;
- }
- }
- return edge_points;
+ voronoi_edge() :
+ cell_(NULL),
+ vertex_(NULL),
+ twin_(NULL),
+ next_(NULL),
+ prev_(NULL) {}
+
+ voronoi_cell_type *cell() { return cell_; }
+ const voronoi_cell_type *cell() const { return cell_; }
+
+ voronoi_vertex_type *vertex0() { return vertex_; }
+ const voronoi_vertex_type *vertex0() const { return vertex_; }
+
+ voronoi_vertex_type *vertex1() { return twin_->vertex0(); }
+ const voronoi_vertex_type *vertex1() const { return twin_->vertex0(); }
+
+ voronoi_edge_type *twin() { return twin_; }
+ const voronoi_edge_type *twin() const { return twin_; }
+
+ voronoi_edge_type *next() { return next_; }
+ const voronoi_edge_type *next() const { return next_; }
+
+ voronoi_edge_type *prev() { return prev_; }
+ const voronoi_edge_type *prev() const { return prev_; }
+
+ voronoi_edge_type *rot_next() {
+ if (prev_)
+ return prev_->twin();
+ return NULL;
+ }
+ const voronoi_edge_type *rot_next() const {
+ if (prev_)
+ return prev_->twin();
+ return NULL;
}
+
+ voronoi_edge_type *rot_prev() { return twin_->next(); }
+ const voronoi_edge_type *rot_prev() const { return twin_->next(); }
+
+ private:
+ friend class voronoi_output<T>;
+
+ void cell(voronoi_cell_type *c) { cell_ = c; }
+ void vertex0(voronoi_vertex_type *v) { vertex_ = v; }
+ void vertex1(voronoi_vertex_type *v) { twin_->vertex0(v); }
+ void twin(voronoi_edge_type *e) { twin_ = e; }
+ void next(voronoi_edge_type *e) { next_ = e; }
+ void prev(voronoi_edge_type *e) { prev_ = e; }
+
+ voronoi_cell_type *cell_;
+ voronoi_vertex_type *vertex_;
+ voronoi_edge_type *twin_;
+ voronoi_edge_type *next_;
+ voronoi_edge_type *prev_;
};
+ // Voronoi output data structure based on the half-edges.
+ // Contains vector of voronoi cells, doubly linked list of
+ // voronoi vertices and voronoi edges.
template <typename T>
- struct voronoi_output_clipped {
+ class voronoi_output {
public:
typedef T coordinate_type;
typedef point_2d<T> Point2D;
- typedef detail::site_event<T> site_event_type;
+ typedef detail::site_event<coordinate_type> site_event_type;
+ typedef detail::circle_event<coordinate_type> circle_event_type;
- typedef voronoi_cell_clipped<coordinate_type> voronoi_cell_type;
- typedef std::list<voronoi_cell_type> voronoi_cells_type;
+ typedef voronoi_cell<coordinate_type> voronoi_cell_type;
+ typedef std::vector<voronoi_cell_type> voronoi_cells_type;
typedef typename voronoi_cells_type::iterator voronoi_cell_iterator_type;
typedef typename voronoi_cells_type::const_iterator voronoi_cell_const_iterator_type;
- typedef voronoi_vertex_clipped<coordinate_type> voronoi_vertex_type;
+ typedef voronoi_vertex<coordinate_type> voronoi_vertex_type;
typedef std::list<voronoi_vertex_type> voronoi_vertices_type;
typedef typename voronoi_vertices_type::iterator voronoi_vertex_iterator_type;
typedef typename voronoi_vertices_type::const_iterator voronoi_vertex_const_iterator_type;
- typedef voronoi_edge_clipped<coordinate_type> voronoi_edge_type;
+ typedef voronoi_edge<coordinate_type> voronoi_edge_type;
typedef std::list<voronoi_edge_type> voronoi_edges_type;
typedef typename voronoi_edges_type::iterator voronoi_edge_iterator_type;
typedef typename voronoi_edges_type::const_iterator voronoi_edge_const_iterator_type;
- BRect<coordinate_type> bounding_rectangle;
-
- int num_cell_records;
- int num_vertex_records;
- int num_edge_records;
-
- voronoi_cells_type cell_records;
- voronoi_vertices_type vertex_records;
- voronoi_edges_type edge_records;
-
- voronoi_output_clipped() {
- num_cell_records = 0;
- num_vertex_records = 0;
- num_edge_records = 0;
+ voronoi_output() {
+ num_cell_records_ = 0;
+ num_edge_records_ = 0;
+ num_vertex_records_ = 0;
}
void reset() {
- cell_records.clear();
- vertex_records.clear();
- edge_records.clear();
-
- num_cell_records = 0;
- num_vertex_records = 0;
- num_edge_records = 0;
+ cell_records_.clear();
+ vertex_records_.clear();
+ edge_records_.clear();
+
+ num_cell_records_ = 0;
+ num_edge_records_ = 0;
+ num_vertex_records_ = 0;
+ }
+
+ const BRect<T> &bounding_rectangle() const {
+ return voronoi_rect_;
+ }
+
+ const voronoi_cells_type &cell_records() const {
+ return cell_records_;
+ }
+
+ const voronoi_vertices_type &vertex_records() const {
+ return vertex_records_;
+ }
+
+ const voronoi_edges_type &edge_records() const {
+ return edge_records_;
+ }
+
+ int num_cell_records() const {
+ return num_cell_records_;
+ }
+
+ int num_edge_records() const {
+ return num_edge_records_;
+ }
+
+ int num_vertex_records() const {
+ return num_vertex_records_;
+ }
+
+ private:
+ friend class detail::voronoi_builder<T>;
+
+ void init(int num_sites) {
+ cell_records_.reserve(num_sites);
+ num_cell_records_ = 0;
+ num_edge_records_ = 0;
+ num_vertex_records_ = 0;
+ }
+
+ // Update voronoi output in case of single site input.
+ void process_single_site(const site_event_type &site) {
+ // Update counters.
+ num_cell_records_++;
+
+ // Update bounding rectangle.
+ voronoi_rect_ = BRect<coordinate_type>(site.get_point0(), site.get_point0());
+
+ // Update cell records.
+ cell_records_.push_back(voronoi_cell_type(site, NULL));
+ }
+
+ // Inserts new half-edge into the output data structure during site
+ // event processing. Takes as input left and right sites of the new
+ // beach line node and returns pointer to the new half-edge.
+ voronoi_edge_type *insert_new_edge(const site_event_type &site1,
+ const site_event_type &site2) {
+ // Update counters.
+ num_cell_records_++;
+ num_edge_records_++;
+
+ // Get indices of sites.
+ int site_index1 = site1.get_site_index();
+ int site_index2 = site2.get_site_index();
+
+ // Create new half-edge that belongs to the first site.
+ edge_records_.push_back(voronoi_edge_type());
+ voronoi_edge_type &edge1 = edge_records_.back();
+
+ // Create new half-edge that belongs to the second site.
+ edge_records_.push_back(voronoi_edge_type());
+ voronoi_edge_type &edge2 = edge_records_.back();
+
+ // Add initial cell during first edge insertion.
+ if (cell_records_.empty()) {
+ cell_records_.push_back(voronoi_cell_type(site1, &edge1));
+ num_cell_records_++;
+ voronoi_rect_ = BRect<coordinate_type>(site1.get_point0(), site1.get_point0());
+ }
+ cell_records_[site_index1].num_incident_edges_++;
+
+ // Update bounding rectangle.
+ voronoi_rect_.update(site2.get_point0());
+ if (site2.is_segment()) {
+ voronoi_rect_.update(site2.get_point1());
+ }
+
+ // Second site represents new site during site event processing.
+ // Add new cell to the cell records vector.
+ cell_records_.push_back(voronoi_cell_type(site2, &edge2));
+ cell_records_.back().num_incident_edges_++;
+
+ // Update pointers to cells.
+ edge1.cell(&cell_records_[site_index1]);
+ edge2.cell(&cell_records_[site_index2]);
+
+ // Update twin pointers.
+ edge1.twin(&edge2);
+ edge2.twin(&edge1);
+
+ return &edge1;
+ }
+
+ voronoi_edge_type *insert_new_edge(const site_event_type &site1,
+ const site_event_type &site3,
+ const circle_event_type &circle,
+ voronoi_edge_type *edge12,
+ voronoi_edge_type *edge23) {
+ // Update counters.
+ num_vertex_records_++;
+ num_edge_records_++;
+
+ // Update bounding rectangle.
+ //voronoi_rect_.update(circle.get_center());
+
+ // Add new voronoi vertex with point at center of the circle.
+ vertex_records_.push_back(voronoi_vertex_type(
+ circle.get_erc_x(), circle.get_erc_y(), circle.get_erc_denom(), edge12));
+ voronoi_vertex_type &new_vertex = vertex_records_.back();
+ new_vertex.num_incident_edges_ = 3;
+ new_vertex.voronoi_record_it = vertex_records_.end();
+ new_vertex.voronoi_record_it--;
+
+ // Update two input bisectors and their twin half-edges with
+ // new voronoi vertex.
+ edge12->vertex0(&new_vertex);
+ edge23->vertex0(&new_vertex);
+
+ // Add new half-edge.
+ edge_records_.push_back(voronoi_edge_type());
+ voronoi_edge_type &new_edge1 = edge_records_.back();
+ new_edge1.cell(&cell_records_[site1.get_site_index()]);
+ new_edge1.cell_->num_incident_edges_++;
+
+ // Add new half-edge.
+ edge_records_.push_back(voronoi_edge_type());
+ voronoi_edge_type &new_edge2 = edge_records_.back();
+ new_edge2.cell(&cell_records_[site3.get_site_index()]);
+ new_edge2.cell_->num_incident_edges_++;
+
+ // Update twin pointers of the new half-edges.
+ new_edge1.twin(&new_edge2);
+ new_edge2.twin(&new_edge1);
+ new_edge2.vertex0(&new_vertex);
+
+ // Update voronoi prev/next pointers of all half-edges incident
+ // to the new voronoi vertex.
+ edge12->prev(&new_edge1);
+ new_edge1.next(edge12);
+ edge12->twin_->next(edge23);
+ edge23->prev(edge12->twin());
+ edge23->twin_->next(&new_edge2);
+ new_edge2.prev(edge23->twin());
+
+ return &new_edge1;
+ }
+
+ void simplify() {
+ voronoi_edge_iterator_type edge_it1;
+ voronoi_edge_iterator_type edge_it = edge_records_.begin();
+
+ // Return in case of collinear sites input.
+ if (num_vertex_records_ == 0) {
+ if (edge_it == edge_records_.end())
+ return;
+
+ voronoi_edge_type *edge1 = &(*edge_it);
+ edge1->next(edge1);
+ edge1->prev(edge1);
+ edge_it++;
+ edge1 = &(*edge_it);
+ edge_it++;
+
+ while (edge_it != edge_records_.end()) {
+ voronoi_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);
+ return;
+ }
+
+ // Iterate over all edges and remove degeneracies.
+ while (edge_it != edge_records_.end()) {
+ edge_it1 = edge_it;
+ std::advance(edge_it, 2);
+
+ if (!edge_it1->vertex0() || !edge_it1->vertex1())
+ continue;
+
+ const voronoi_vertex_type *p1 = edge_it1->vertex0();
+ const voronoi_vertex_type *p2 = edge_it1->vertex1();
+ detail::epsilon_robust_comparator<T> lhs1(p1->center_x * p2->denom);
+ detail::epsilon_robust_comparator<T> rhs1(p1->denom * p2->center_x);
+ detail::epsilon_robust_comparator<T> lhs2(p1->center_y * p2->denom);
+ detail::epsilon_robust_comparator<T> rhs2(p1->denom * p2->center_y);
+
+ if (lhs1.compares_undefined(rhs1, 64) && lhs2.compares_undefined(rhs2, 64)) {
+ // Decrease number of cell incident edges.
+ edge_it1->cell_->num_incident_edges_--;
+ edge_it1->twin_->cell_->num_incident_edges_--;
+
+ // To guarantee N*lon(N) time we merge vertex with
+ // less incident edges to the one with more.
+ if (edge_it1->cell_->incident_edge_ == &(*edge_it1)) {
+ if (edge_it1->cell_->incident_edge_ == edge_it1->next_) {
+ edge_it1->cell_->incident_edge_ = NULL;
+ } else {
+ edge_it1->cell_->incident_edge_ = edge_it1->next_;
+ }
+ }
+ if (edge_it1->twin_->cell_->incident_edge_ == edge_it1->twin_) {
+ 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_;
+ }
+ }
+ if (edge_it1->vertex0()->num_incident_edges_ >=
+ edge_it1->vertex1()->num_incident_edges_) {
+ simplify_edge(&(*edge_it1));
+ } else {
+ simplify_edge(edge_it1->twin_);
+ }
+
+ // Remove zero length edges.
+ edge_records_.erase(edge_it1, edge_it);
+ num_edge_records_--;
+ }
+ }
+
+ // Make some post processing.
+ for (voronoi_cell_iterator_type cell_it = cell_records_.begin();
+ cell_it != cell_records_.end(); cell_it++) {
+ // Move to the previous edge while it is possible in the CW direction.
+ voronoi_edge_type *cur_edge = cell_it->incident_edge_;
+ if (cur_edge) {
+ while (cur_edge->prev_ != NULL) {
+ cur_edge = cur_edge->prev_;
+
+ // Terminate if this is not a boundary cell.
+ if (cur_edge == cell_it->incident_edge_)
+ break;
+ }
+
+ // Rewind incident edge pointer to the leftmost edge for the boundary cells.
+ cell_it->incident_edge_ = cur_edge;
+
+ // Set up prev/next half-edge pointers for ray edges.
+ if (cur_edge->prev_ == NULL) {
+ voronoi_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);
+ }
+ }
+ }
}
+
+ // Simplify degenerate edge.
+ void simplify_edge(voronoi_edge_type *edge) {
+ voronoi_vertex_type *vertex1 = edge->vertex0();
+ voronoi_vertex_type *vertex2 = edge->vertex1();
+
+ // Update number of incident edges.
+ vertex1->num_incident_edges_ += vertex2->num_incident_edges_ - 2;
+
+ // Update second vertex incident edges start and end points.
+ voronoi_edge_type *updated_edge = edge->twin()->rot_next();
+ while (updated_edge != edge->twin()) {
+ updated_edge->vertex0(vertex1);
+ updated_edge = updated_edge->rot_next();
+ }
+
+ voronoi_edge_type *edge1 = edge;
+ voronoi_edge_type *edge2 = edge->twin();
+
+ voronoi_edge_type *edge1_rot_prev = edge1->rot_prev();
+ voronoi_edge_type *edge1_rot_next = edge1->rot_next();
+
+ voronoi_edge_type *edge2_rot_prev = edge2->rot_prev();
+ voronoi_edge_type *edge2_rot_next = edge2->rot_next();
+
+ // Update prev and next pointers of incident edges.
+ edge1_rot_next->twin()->next(edge2_rot_prev);
+ 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 incident edge pointer of a vertex if it corresponds to the
+ // degenerate edge.
+ if (vertex1->incident_edge() == edge)
+ vertex1->incident_edge_ = edge->rot_prev();
+
+ // Remove second vertex from the vertex records list.
+ if (vertex1->voronoi_record_it != vertex2->voronoi_record_it) {
+ vertex_records_.erase(vertex2->voronoi_record_it);
+ num_vertex_records_--;
+ }
+ }
+
+ voronoi_cells_type cell_records_;
+ voronoi_vertices_type vertex_records_;
+ voronoi_edges_type edge_records_;
+
+ int num_cell_records_;
+ int num_vertex_records_;
+ int num_edge_records_;
+
+ BRect<coordinate_type> voronoi_rect_;
+
+ // Disallow copy constructor and operator=
+ voronoi_output(const voronoi_output&);
+ void operator=(const voronoi_output&);
};
} // sweepline
Modified: sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_sweepline.hpp
==============================================================================
--- sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_sweepline.hpp (original)
+++ sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_sweepline.hpp 2010-11-29 19:02:09 EST (Mon, 29 Nov 2010)
@@ -7,8 +7,8 @@
// See http://www.boost.org for updates, documentation, and revision history.
-#ifndef BOOST_SWEEPLINE_VORONOI_SEGMENT_SWEEPLINE
-#define BOOST_SWEEPLINE_VORONOI_SEGMENT_SWEEPLINE
+#ifndef BOOST_SWEEPLINE_VORONOI_SWEEPLINE
+#define BOOST_SWEEPLINE_VORONOI_SWEEPLINE
#include <algorithm>
#include <cmath>
@@ -24,9 +24,35 @@
#endif
#include "voronoi_output.hpp"
-
#include "detail/voronoi_formation.hpp"
-#include "voronoi_builder.hpp"
+namespace boost {
+namespace sweepline {
+
+ template <typename T>
+ static void build_voronoi(const std::vector< point_2d<T> > &points,
+ voronoi_output<double> &output) {
+ std::vector< std::pair< point_2d<T>, point_2d<T> > > segments_empty;
+ build_voronoi<T>(points, segments_empty, output);
+ }
+
+ template <typename T>
+ static void build_voronoi(const std::vector< std::pair< point_2d<T>, point_2d<T> > > &segments,
+ voronoi_output<double> &output) {
+ std::vector< point_2d<T> > points_empty;
+ build_voronoi<T>(points_empty, segments, output);
+ }
+
+ template <typename T>
+ static void build_voronoi(const std::vector< point_2d<T> > &points,
+ const std::vector< std::pair< point_2d<T>, point_2d<T> > > &segments,
+ voronoi_output<double> &output) {
+ detail::voronoi_builder<double> builder(output);
+ builder.init(points, segments);
+ builder.run_sweepline();
+ }
+
+} // sweepline
+} // boost
#endif
Modified: sandbox/SOC/2010/sweepline/libs/sweepline/example/voronoi_visualizer.cpp
==============================================================================
--- sandbox/SOC/2010/sweepline/libs/sweepline/example/voronoi_visualizer.cpp (original)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/example/voronoi_visualizer.cpp 2010-11-29 19:02:09 EST (Mon, 29 Nov 2010)
@@ -25,8 +25,8 @@
}
void build(QString file_path) {
- std::vector<Point2D> point_sites;
- std::vector<Segment2D> segment_sites;
+ std::vector<iPoint2D> point_sites;
+ std::vector<iSegment2D> segment_sites;
// Open file.
QFile data(file_path);
@@ -38,7 +38,7 @@
QTextStream in_stream(&data);
int num_point_sites = 0;
int num_edge_sites = 0;
- coordinate_type x1, y1, x2, y2;
+ int x1, y1, x2, y2;
in_stream >> num_point_sites;
for (int i = 0; i < num_point_sites; i++) {
in_stream >> x1 >> y1;
@@ -53,10 +53,9 @@
in_stream.flush();
// Build voronoi diagram.
- voronoi_builder_.init(point_sites, segment_sites);
- voronoi_builder_.run_sweepline();
- voronoi_builder_.clip(voronoi_output_);
- brect_ = voronoi_output_.bounding_rectangle;
+ build_voronoi(point_sites, segment_sites, voronoi_output_);
+ brect_ = voronoi_helper<coordinate_type>::get_view_rectangle(
+ voronoi_output_.bounding_rectangle());
// Update view.
update_view_port();
@@ -69,7 +68,7 @@
// Draw voronoi sites.
{
- voronoi_cells_type cells = voronoi_output_.cell_records;
+ const voronoi_cells_type &cells = voronoi_output_.cell_records();
voronoi_cell_const_iterator_type it;
glColor3f(0.0f, 0.0f, 1.0f);
glPointSize(9);
@@ -94,23 +93,24 @@
// Draw voronoi vertices.
{
- voronoi_vertices_type vertices = voronoi_output_.vertex_records;
+ const voronoi_vertices_type &vertices = voronoi_output_.vertex_records();
voronoi_vertex_const_iterator_type it;
glColor3f(0.0f, 1.0f, 0.0f);
glBegin(GL_POINTS);
for (it = vertices.begin(); it != vertices.end(); it++)
- glVertex2f(it->vertex.x(), it->vertex.y());
+ glVertex2f(it->vertex().x(), it->vertex().y());
glEnd();
}
// Draw voronoi edges.
{
- voronoi_edges_type edges = voronoi_output_.edge_records;
+ const voronoi_edges_type &edges = voronoi_output_.edge_records();
voronoi_edge_const_iterator_type it;
glColor3f(0.0f, 1.0f, 0.0f);
glBegin(GL_LINES);
for (it = edges.begin(); it != edges.end(); it++) {
- std::vector<Point2D> temp_v = it->get_intermediate_points(brect_);
+ std::vector<Point2D> temp_v =
+ voronoi_helper<coordinate_type>::get_intermediate_points(&(*it), brect_);
for (int i = 0; i < static_cast<int>(temp_v.size()) - 1; i++) {
glVertex2f(temp_v[i].x(), temp_v[i].y());
glVertex2f(temp_v[i+1].x(), temp_v[i+1].y());
@@ -133,28 +133,25 @@
void update_view_port() {
glMatrixMode(GL_PROJECTION);
glLoadIdentity();
- glOrtho(brect_.x_min, brect_.x_max, brect_.y_min, brect_.y_max, -1.0, 1.0);
+ glOrtho(brect_.x_min(), brect_.x_max(), brect_.y_min(), brect_.y_max(), -1.0, 1.0);
glMatrixMode(GL_MODELVIEW);
}
typedef double coordinate_type;
typedef point_2d<coordinate_type> Point2D;
- typedef voronoi_builder<coordinate_type>::Segment2D Segment2D;
- typedef voronoi_output_clipped<coordinate_type>::voronoi_cells_type
- voronoi_cells_type;
- typedef voronoi_output_clipped<coordinate_type>::voronoi_vertices_type
- voronoi_vertices_type;
- typedef voronoi_output_clipped<coordinate_type>::voronoi_edges_type
- voronoi_edges_type;
- typedef voronoi_output_clipped<coordinate_type>::voronoi_cell_const_iterator_type
+ typedef point_2d<int> iPoint2D;
+ typedef std::pair<iPoint2D, iPoint2D> iSegment2D;
+ typedef voronoi_output<coordinate_type>::voronoi_cells_type voronoi_cells_type;
+ typedef voronoi_output<coordinate_type>::voronoi_vertices_type voronoi_vertices_type;
+ typedef voronoi_output<coordinate_type>::voronoi_edges_type voronoi_edges_type;
+ typedef voronoi_output<coordinate_type>::voronoi_cell_const_iterator_type
voronoi_cell_const_iterator_type;
- typedef voronoi_output_clipped<coordinate_type>::voronoi_vertex_const_iterator_type
+ typedef voronoi_output<coordinate_type>::voronoi_vertex_const_iterator_type
voronoi_vertex_const_iterator_type;
- typedef voronoi_output_clipped<coordinate_type>::voronoi_edge_const_iterator_type
+ typedef voronoi_output<coordinate_type>::voronoi_edge_const_iterator_type
voronoi_edge_const_iterator_type;
- voronoi_builder<coordinate_type> voronoi_builder_;
BRect<coordinate_type> brect_;
- voronoi_output_clipped<coordinate_type> voronoi_output_;
+ voronoi_output<coordinate_type> voronoi_output_;
};
class MainWindow : public QWidget {
Modified: sandbox/SOC/2010/sweepline/libs/sweepline/test/benchmark_test.cpp
==============================================================================
--- sandbox/SOC/2010/sweepline/libs/sweepline/test/benchmark_test.cpp (original)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/test/benchmark_test.cpp 2010-11-29 19:02:09 EST (Mon, 29 Nov 2010)
@@ -26,9 +26,7 @@
BOOST_AUTO_TEST_CASE_TEMPLATE(benchmark_test1, T, test_types) {
typedef T coordinate_type;
srand(static_cast<unsigned int>(time(NULL)));
-
- voronoi_builder<coordinate_type> test_builder;
- voronoi_output_clipped<coordinate_type> test_output;
+ voronoi_output<coordinate_type> test_output;
FILE *bench_file = fopen("benchmark.txt", "a");
fprintf(bench_file, "Voronoi Segment Sweepline Benchmark Test (time in seconds):\n");
@@ -40,7 +38,7 @@
#endif
for (int num_points = 10; num_points <= max_points; num_points *= 10) {
- std::vector< point_2d<coordinate_type> > points;
+ std::vector< point_2d<T> > points;
points.reserve(num_points);
time_t start_time = time(NULL);
@@ -51,11 +49,7 @@
static_cast<coordinate_type>(rand() % 5000 - 10000),
static_cast<coordinate_type>(rand() % 5000 - 10000)));
}
- test_builder.init(points);
- test_builder.run_sweepline();
- test_builder.clip(test_output);
- test_builder.reset();
- test_output.reset();
+ build_voronoi(points, test_output);
points.clear();
}
time_t end_time = time(NULL);
Modified: sandbox/SOC/2010/sweepline/libs/sweepline/test/clipping_test.cpp
==============================================================================
--- sandbox/SOC/2010/sweepline/libs/sweepline/test/clipping_test.cpp (original)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/test/clipping_test.cpp 2010-11-29 19:02:09 EST (Mon, 29 Nov 2010)
@@ -21,7 +21,6 @@
BOOST_AUTO_TEST_CASE_TEMPLATE(segment_clipping_test1, T, test_types) {
BRect<T> test_rect(static_cast<T>(0.0), static_cast<T>(-1.0),
static_cast<T>(4.0), static_cast<T>(2.0));
- detail::voronoi_output<T> test_output;
point_2d<T> test_origin(static_cast<T>(-1), static_cast<T>(3));
point_2d<T> test_direction1_1(static_cast<T>(8), static_cast<T>(-8));
point_2d<T> test_direction1_2(static_cast<T>(2), static_cast<T>(-2));
@@ -32,8 +31,9 @@
point_2d<T> test_direction5(static_cast<T>(5), static_cast<T>(-1));
std::vector< point_2d<T> > intersections;
- Helper<T>::find_intersections(test_origin, test_direction1_1,
- Helper<T>::SEGMENT, test_rect, intersections);
+ voronoi_helper<T>::find_intersections(test_origin, test_direction1_1,
+ voronoi_helper<T>::SEGMENT,
+ test_rect, intersections);
BOOST_CHECK_EQUAL(static_cast<int>(intersections.size()), 2);
BOOST_CHECK_EQUAL(intersections[0].x() == static_cast<T>(0) &&
intersections[0].y() == static_cast<T>(2), true);
@@ -41,20 +41,20 @@
intersections[1].y() == static_cast<T>(-1), true);
intersections.clear();
- Helper<T>::find_intersections(test_origin, test_direction1_2,
- Helper<T>::SEGMENT, test_rect, intersections);
+ voronoi_helper<T>::find_intersections(test_origin, test_direction1_2,
+ voronoi_helper<T>::SEGMENT, test_rect, intersections);
BOOST_CHECK_EQUAL(static_cast<int>(intersections.size()), 1);
BOOST_CHECK_EQUAL(intersections[0].x() == static_cast<T>(0) &&
intersections[0].y() == static_cast<T>(2), true);
intersections.clear();
- Helper<T>::find_intersections(test_origin, test_direction1_3,
- Helper<T>::SEGMENT, test_rect, intersections);
+ voronoi_helper<T>::find_intersections(test_origin, test_direction1_3,
+ voronoi_helper<T>::SEGMENT, test_rect, intersections);
BOOST_CHECK_EQUAL(intersections.empty(), true);
intersections.clear();
- Helper<T>::find_intersections(test_origin, test_direction2,
- Helper<T>::SEGMENT, test_rect, intersections);
+ voronoi_helper<T>::find_intersections(test_origin, test_direction2,
+ voronoi_helper<T>::SEGMENT, test_rect, intersections);
BOOST_CHECK_EQUAL(static_cast<int>(intersections.size()), 2);
BOOST_CHECK_EQUAL(intersections[0].x() == static_cast<T>(0) &&
intersections[0].y() == static_cast<T>(1), true);
@@ -62,22 +62,22 @@
intersections[1].y() == static_cast<T>(-1), true);
intersections.clear();
- Helper<T>::find_intersections(test_origin, test_direction3,
- Helper<T>::SEGMENT, test_rect, intersections);
+ voronoi_helper<T>::find_intersections(test_origin, test_direction3,
+ voronoi_helper<T>::SEGMENT, test_rect, intersections);
BOOST_CHECK_EQUAL(static_cast<int>(intersections.size()), 1);
BOOST_CHECK_EQUAL(intersections[0].x() == static_cast<T>(1) &&
intersections[0].y() == static_cast<T>(2), true);
intersections.clear();
- Helper<T>::find_intersections(test_origin, test_direction4,
- Helper<T>::SEGMENT, test_rect, intersections);
+ voronoi_helper<T>::find_intersections(test_origin, test_direction4,
+ voronoi_helper<T>::SEGMENT, test_rect, intersections);
BOOST_CHECK_EQUAL(static_cast<int>(intersections.size()), 1);
BOOST_CHECK_EQUAL(intersections[0].x() == static_cast<T>(0) &&
intersections[0].y() == static_cast<T>(-1), true);
intersections.clear();
- Helper<T>::find_intersections(test_origin, test_direction5,
- Helper<T>::SEGMENT, test_rect, intersections);
+ voronoi_helper<T>::find_intersections(test_origin, test_direction5,
+ voronoi_helper<T>::SEGMENT, test_rect, intersections);
BOOST_CHECK_EQUAL(static_cast<int>(intersections.size()), 1);
BOOST_CHECK_EQUAL(intersections[0].x() == static_cast<T>(4) &&
intersections[0].y() == static_cast<T>(2), true);
@@ -86,7 +86,6 @@
BOOST_AUTO_TEST_CASE_TEMPLATE(segment_clipping_test2, T, test_types) {
BRect<T> test_rect(static_cast<T>(0.0), static_cast<T>(-1.0),
static_cast<T>(4.0), static_cast<T>(3.0));
- detail::voronoi_output<T> test_output;
std::vector< point_2d<T> > intersections;
srand(static_cast<unsigned int>(time(NULL)));
point_2d<T> test_origin(2, 1);
@@ -95,8 +94,8 @@
for (int j = -50; j <= 50; j++) {
intersections.clear();
point_2d<T> test_direction(static_cast<T>(i), static_cast<T>(j));
- Helper<T>::find_intersections(test_origin, test_direction,
- Helper<T>::SEGMENT, test_rect, intersections);
+ voronoi_helper<T>::find_intersections(test_origin, test_direction,
+ voronoi_helper<T>::SEGMENT, test_rect, intersections);
if (abs(i) >= 2 || abs(j) >= 2)
BOOST_CHECK_EQUAL(static_cast<int>(intersections.size()), 1);
else
@@ -107,7 +106,6 @@
BOOST_AUTO_TEST_CASE_TEMPLATE(segment_clipping_test3, T, test_types) {
BRect<T> test_rect(static_cast<T>(0.0), static_cast<T>(-1.0),
static_cast<T>(4.0), static_cast<T>(3.0));
- detail::voronoi_output<T> test_output;
std::vector< point_2d<T> > intersections;
srand(static_cast<unsigned int>(time(NULL)));
point_2d<T> test_origin(2, 1);
@@ -118,8 +116,8 @@
T x = static_cast<T>(i) / static_cast<T>(26);
T y = static_cast<T>(j) / static_cast<T>(26);
point_2d<T> test_direction(x, y);
- Helper<T>::find_intersections(test_origin, test_direction,
- Helper<T>::SEGMENT, test_rect, intersections);
+ voronoi_helper<T>::find_intersections(test_origin, test_direction,
+ voronoi_helper<T>::SEGMENT, test_rect, intersections);
BOOST_CHECK_EQUAL(static_cast<int>(intersections.size()), 0);
}
}
@@ -128,7 +126,6 @@
BOOST_AUTO_TEST_CASE_TEMPLATE(ray_clipping_test1, T, test_types) {
BRect<T> test_rect(static_cast<T>(0.0), static_cast<T>(-1.0),
static_cast<T>(4.0), static_cast<T>(2.0));
- detail::voronoi_output<T> test_output;
point_2d<T> test_origin(static_cast<T>(-1), static_cast<T>(3));
point_2d<T> test_direction1(static_cast<T>(2), static_cast<T>(-2));
point_2d<T> test_direction2(static_cast<T>(2), static_cast<T>(-4));
@@ -137,8 +134,8 @@
point_2d<T> test_direction5(static_cast<T>(5), static_cast<T>(-1));
std::vector< point_2d<T> > intersections;
- Helper<T>::find_intersections(test_origin, test_direction1,
- Helper<T>::RAY, test_rect, intersections);
+ voronoi_helper<T>::find_intersections(test_origin, test_direction1,
+ voronoi_helper<T>::RAY, test_rect, intersections);
BOOST_CHECK_EQUAL(static_cast<int>(intersections.size()), 2);
BOOST_CHECK_EQUAL(intersections[0].x() == static_cast<T>(0) &&
intersections[0].y() == static_cast<T>(2), true);
@@ -146,8 +143,8 @@
intersections[1].y() == static_cast<T>(-1), true);
intersections.clear();
- Helper<T>::find_intersections(test_origin, test_direction2,
- Helper<T>::RAY, test_rect, intersections);
+ voronoi_helper<T>::find_intersections(test_origin, test_direction2,
+ voronoi_helper<T>::RAY, test_rect, intersections);
BOOST_CHECK_EQUAL(static_cast<int>(intersections.size()), 2);
BOOST_CHECK_EQUAL(intersections[0].x() == static_cast<T>(0) &&
intersections[0].y() == static_cast<T>(1), true);
@@ -155,8 +152,8 @@
intersections[1].y() == static_cast<T>(-1), true);
intersections.clear();
- Helper<T>::find_intersections(test_origin, test_direction3,
- Helper<T>::RAY, test_rect, intersections);
+ voronoi_helper<T>::find_intersections(test_origin, test_direction3,
+ voronoi_helper<T>::RAY, test_rect, intersections);
BOOST_CHECK_EQUAL(static_cast<int>(intersections.size()), 2);
BOOST_CHECK_EQUAL(intersections[0].x() == static_cast<T>(1) &&
intersections[0].y() == static_cast<T>(2), true);
@@ -164,15 +161,15 @@
intersections[1].y() == static_cast<T>(0.5), true);
intersections.clear();
- Helper<T>::find_intersections(test_origin, test_direction4,
- Helper<T>::RAY, test_rect, intersections);
+ voronoi_helper<T>::find_intersections(test_origin, test_direction4,
+ voronoi_helper<T>::RAY, test_rect, intersections);
BOOST_CHECK_EQUAL(static_cast<int>(intersections.size()), 1);
BOOST_CHECK_EQUAL(intersections[0].x() == static_cast<T>(0) &&
intersections[0].y() == static_cast<T>(-1), true);
intersections.clear();
- Helper<T>::find_intersections(test_origin, test_direction5,
- Helper<T>::RAY, test_rect, intersections);
+ voronoi_helper<T>::find_intersections(test_origin, test_direction5,
+ voronoi_helper<T>::RAY, test_rect, intersections);
BOOST_CHECK_EQUAL(static_cast<int>(intersections.size()), 1);
BOOST_CHECK_EQUAL(intersections[0].x() == static_cast<T>(4) &&
intersections[0].y() == static_cast<T>(2), true);
@@ -181,7 +178,6 @@
BOOST_AUTO_TEST_CASE_TEMPLATE(ray_clipping_test2, T, test_types) {
BRect<T> test_rect(static_cast<T>(0.0), static_cast<T>(-1.0),
static_cast<T>(4.0), static_cast<T>(3.0));
- detail::voronoi_output<T> test_output;
std::vector< point_2d<T> > intersections;
srand(static_cast<unsigned int>(time(NULL)));
point_2d<T> test_origin(2, 1);
@@ -192,8 +188,8 @@
T x = static_cast<T>(i) / static_cast<T>(26);
T y = static_cast<T>(j) / static_cast<T>(26);
point_2d<T> test_direction(x, y);
- Helper<T>::find_intersections(test_origin, test_direction,
- Helper<T>::RAY, test_rect, intersections);
+ voronoi_helper<T>::find_intersections(test_origin, test_direction,
+ voronoi_helper<T>::RAY, test_rect, intersections);
if (i && j)
BOOST_CHECK_EQUAL(static_cast<int>(intersections.size()), 1);
}
@@ -203,7 +199,6 @@
BOOST_AUTO_TEST_CASE_TEMPLATE(line_clipping_test1, T, test_types) {
BRect<T> test_rect(static_cast<T>(0.0), static_cast<T>(-1.0),
static_cast<T>(4.0), static_cast<T>(2.0));
- detail::voronoi_output<T> test_output;
point_2d<T> test_origin(static_cast<T>(-1), static_cast<T>(3));
point_2d<T> test_direction1(static_cast<T>(-1), static_cast<T>(1));
point_2d<T> test_direction2(static_cast<T>(-1), static_cast<T>(2));
@@ -212,8 +207,8 @@
point_2d<T> test_direction5(static_cast<T>(-5), static_cast<T>(1));
std::vector< point_2d<T> > intersections;
- Helper<T>::find_intersections(test_origin, test_direction1,
- Helper<T>::LINE, test_rect, intersections);
+ voronoi_helper<T>::find_intersections(test_origin, test_direction1,
+ voronoi_helper<T>::LINE, test_rect, intersections);
BOOST_CHECK_EQUAL(static_cast<int>(intersections.size()), 2);
BOOST_CHECK_EQUAL(intersections[0].x() == static_cast<T>(3) &&
intersections[0].y() == static_cast<T>(-1), true);
@@ -221,8 +216,8 @@
intersections[1].y() == static_cast<T>(2), true);
intersections.clear();
- Helper<T>::find_intersections(test_origin, test_direction2,
- Helper<T>::LINE, test_rect, intersections);
+ voronoi_helper<T>::find_intersections(test_origin, test_direction2,
+ voronoi_helper<T>::LINE, test_rect, intersections);
BOOST_CHECK_EQUAL(static_cast<int>(intersections.size()), 2);
BOOST_CHECK_EQUAL(intersections[0].x() == static_cast<T>(1) &&
intersections[0].y() == static_cast<T>(-1), true);
@@ -230,8 +225,8 @@
intersections[1].y() == static_cast<T>(1), true);
intersections.clear();
- Helper<T>::find_intersections(test_origin, test_direction3,
- Helper<T>::LINE, test_rect, intersections);
+ voronoi_helper<T>::find_intersections(test_origin, test_direction3,
+ voronoi_helper<T>::LINE, test_rect, intersections);
BOOST_CHECK_EQUAL(static_cast<int>(intersections.size()), 2);
BOOST_CHECK_EQUAL(intersections[0].x() == static_cast<T>(4) &&
intersections[0].y() == static_cast<T>(0.5), true);
@@ -239,15 +234,15 @@
intersections[1].y() == static_cast<T>(2), true);
intersections.clear();
- Helper<T>::find_intersections(test_origin, test_direction4,
- Helper<T>::LINE, test_rect, intersections);
+ voronoi_helper<T>::find_intersections(test_origin, test_direction4,
+ voronoi_helper<T>::LINE, test_rect, intersections);
BOOST_CHECK_EQUAL(static_cast<int>(intersections.size()), 1);
BOOST_CHECK_EQUAL(intersections[0].x() == static_cast<T>(0) &&
intersections[0].y() == static_cast<T>(-1), true);
intersections.clear();
- Helper<T>::find_intersections(test_origin, test_direction5,
- Helper<T>::LINE, test_rect, intersections);
+ voronoi_helper<T>::find_intersections(test_origin, test_direction5,
+ voronoi_helper<T>::LINE, test_rect, intersections);
BOOST_CHECK_EQUAL(static_cast<int>(intersections.size()), 1);
BOOST_CHECK_EQUAL(intersections[0].x() == static_cast<T>(4) &&
intersections[0].y() == static_cast<T>(2), true);
@@ -256,7 +251,6 @@
BOOST_AUTO_TEST_CASE_TEMPLATE(line_clipping_test2, T, test_types) {
BRect<T> test_rect(static_cast<T>(0.0), static_cast<T>(-1.0),
static_cast<T>(4.0), static_cast<T>(3.0));
- detail::voronoi_output<T> test_output;
std::vector< point_2d<T> > intersections;
srand(static_cast<unsigned int>(time(NULL)));
point_2d<T> test_origin(2, 1);
@@ -267,8 +261,8 @@
T x = static_cast<T>(i) / static_cast<T>(26);
T y = static_cast<T>(j) / static_cast<T>(26);
point_2d<T> test_direction(x, y);
- Helper<T>::find_intersections(test_origin, test_direction,
- Helper<T>::LINE, test_rect, intersections);
+ voronoi_helper<T>::find_intersections(test_origin, test_direction,
+ voronoi_helper<T>::LINE, test_rect, intersections);
if (i && j)
BOOST_CHECK_EQUAL(static_cast<int>(intersections.size()), 2);
}
Modified: sandbox/SOC/2010/sweepline/libs/sweepline/test/output_verification.hpp
==============================================================================
--- sandbox/SOC/2010/sweepline/libs/sweepline/test/output_verification.hpp (original)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/test/output_verification.hpp 2010-11-29 19:02:09 EST (Mon, 29 Nov 2010)
@@ -32,12 +32,12 @@
bool verify_half_edge_orientation(const Output &output) {
typedef typename Output::Point2D Point2D;
typename Output::voronoi_edge_const_iterator_type edge_it;
- for (edge_it = output.edge_records.begin();
- edge_it != output.edge_records.end(); edge_it++) {
- if (edge_it->start_point != NULL && edge_it->end_point != NULL) {
- const Point2D &site_point = edge_it->cell->get_point0();
- const Point2D &start_point = edge_it->start_point->vertex;
- const Point2D &end_point = edge_it->end_point->vertex;
+ for (edge_it = output.edge_records().begin();
+ edge_it != output.edge_records().end(); edge_it++) {
+ if (edge_it->vertex0() != NULL && edge_it->vertex1() != NULL) {
+ const Point2D &site_point = edge_it->cell()->get_point0();
+ const Point2D &start_point = edge_it->vertex0()->vertex();
+ const Point2D &end_point = edge_it->vertex1()->vertex();
if (get_orientation(start_point, end_point, site_point) != LEFT_ORIENTATION)
return false;
}
@@ -49,27 +49,27 @@
bool verify_cell_convexity(const Output &output) {
typedef typename Output::Point2D Point2D;
typename Output::voronoi_cell_const_iterator_type cell_it;
- for (cell_it = output.cell_records.begin();
- cell_it != output.cell_records.end(); cell_it++) {
- const typename Output::voronoi_edge_type *edge = cell_it->incident_edge;
+ for (cell_it = output.cell_records().begin();
+ cell_it != output.cell_records().end(); cell_it++) {
+ const typename Output::voronoi_edge_type *edge = cell_it->incident_edge();
if (edge)
do {
- if (edge->next->prev != edge)
+ if (edge->next()->prev() != edge)
return false;
- if (edge->cell != &(*cell_it))
+ if (edge->cell() != &(*cell_it))
return false;
- if (edge->start_point != NULL &&
- edge->end_point != NULL &&
- edge->end_point == edge->next->start_point &&
- 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 (edge->vertex0() != NULL &&
+ edge->vertex1() != NULL &&
+ edge->vertex1() == edge->next()->vertex0() &&
+ edge->next()->vertex1() != NULL) {
+ const Point2D &vertex1 = edge->vertex0()->vertex();
+ const Point2D &vertex2 = edge->vertex1()->vertex();
+ const Point2D &vertex3 = edge->next()->vertex1()->vertex();
if (get_orientation(vertex1, vertex2, vertex3) != LEFT_ORIENTATION)
return false;
}
- edge = edge->next;
- } while(edge != cell_it->incident_edge);
+ edge = edge->next();
+ } while(edge != cell_it->incident_edge());
}
return true;
}
@@ -77,24 +77,25 @@
template <typename Output>
bool verify_incident_edges_ccw_order(const Output &output) {
typedef typename Output::Point2D Point2D;
+ typedef typename Output::voronoi_edge_type voronoi_edge_type;
typename Output::voronoi_vertex_const_iterator_type vertex_it;
- for (vertex_it = output.vertex_records.begin();
- vertex_it != output.vertex_records.end(); vertex_it++) {
- if (vertex_it->num_incident_edges < 3)
+ for (vertex_it = output.vertex_records().begin();
+ vertex_it != output.vertex_records().end(); vertex_it++) {
+ if (vertex_it->num_incident_edges() < 3)
continue;
- typename Output::voronoi_edge_type *edge = vertex_it->incident_edge;
+ const voronoi_edge_type *edge = vertex_it->incident_edge();
do {
- typename Output::voronoi_edge_type *edge_next1 = edge->rot_next;
- typename Output::voronoi_edge_type *edge_next2 = edge_next1->rot_next;
- const Point2D &site1 = edge->cell->get_point0();
- const Point2D &site2 = edge_next1->cell->get_point0();
- const Point2D &site3 = edge_next2->cell->get_point0();
+ const voronoi_edge_type *edge_next1 = edge->rot_next();
+ const voronoi_edge_type *edge_next2 = edge_next1->rot_next();
+ const Point2D &site1 = edge->cell()->get_point0();
+ const Point2D &site2 = edge_next1->cell()->get_point0();
+ const Point2D &site3 = edge_next2->cell()->get_point0();
if (get_orientation(site1, site2, site3) != LEFT_ORIENTATION)
return false;
- edge = edge->rot_next;
- } while (edge != vertex_it->incident_edge);
+ edge = edge->rot_next();
+ } while (edge != vertex_it->incident_edge());
}
return true;
}
@@ -109,15 +110,15 @@
typedef typename std::map< Point2D, std::vector<Point2D> >::const_iterator
edge_map_iterator;
typename Output::voronoi_edge_const_iterator_type edge_it;
- for (edge_it = output.edge_records.begin();
- edge_it != output.edge_records.end(); edge_it++) {
- if (edge_it->cell->contains_segment() && edge_it->twin->cell->contains_segment())
+ for (edge_it = output.edge_records().begin();
+ edge_it != output.edge_records().end(); edge_it++) {
+ if (edge_it->cell()->contains_segment() && edge_it->twin()->cell()->contains_segment())
continue;
- 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);
+ if (edge_it->vertex0() != NULL && edge_it->vertex1() != NULL) {
+ const Point2D &vertex0 = edge_it->vertex0()->vertex();
+ const Point2D &vertex1 = edge_it->vertex1()->vertex();
+ if (vertex0 < vertex1)
+ edge_map[vertex0].push_back(vertex1);
}
}
Modified: sandbox/SOC/2010/sweepline/libs/sweepline/test/sweepline_test.cpp
==============================================================================
--- sandbox/SOC/2010/sweepline/libs/sweepline/test/sweepline_test.cpp (original)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/test/sweepline_test.cpp 2010-11-29 19:02:09 EST (Mon, 29 Nov 2010)
@@ -31,374 +31,369 @@
// Sites: (0, 0).
BOOST_AUTO_TEST_CASE_TEMPLATE(single_site_test, T, test_types) {
typedef T coordinate_type;
- typedef typename voronoi_output_clipped<coordinate_type>::voronoi_cell_const_iterator_type
+ typedef typename voronoi_output<coordinate_type>::voronoi_cell_const_iterator_type
voronoi_cell_const_iterator_type;
- voronoi_builder<coordinate_type> test_voronoi_builder;
std::vector< point_2d<coordinate_type> > points;
points.push_back(make_point_2d<coordinate_type>(static_cast<coordinate_type>(0),
static_cast<coordinate_type>(0)));
-
- test_voronoi_builder.init(points);
- test_voronoi_builder.run_sweepline();
- voronoi_output_clipped<coordinate_type> test_output;
- test_voronoi_builder.clip(test_output);
- VERIFY_VORONOI_OUTPUT(test_output, COMPLETE_VERIFICATION);
-
- BRect<coordinate_type> bounding_rectangle = test_voronoi_builder.get_bounding_rectangle();
- BOOST_CHECK_EQUAL(bounding_rectangle.x_min == static_cast<coordinate_type>(0) &&
- bounding_rectangle.y_min == static_cast<coordinate_type>(0) &&
- bounding_rectangle.x_max == static_cast<coordinate_type>(0) &&
- bounding_rectangle.y_max == static_cast<coordinate_type>(0), true);
-
- BOOST_CHECK_EQUAL(static_cast<int>(test_output.cell_records.size()), 1);
- BOOST_CHECK_EQUAL(static_cast<int>(test_output.vertex_records.size()), 0);
- BOOST_CHECK_EQUAL(static_cast<int>(test_output.edge_records.size()), 0);
-
- BOOST_CHECK_EQUAL(test_output.num_cell_records, 1);
- BOOST_CHECK_EQUAL(test_output.num_vertex_records, 0);
- BOOST_CHECK_EQUAL(test_output.num_edge_records, 0);
-
- voronoi_cell_const_iterator_type it = test_output.cell_records.begin();
- BOOST_CHECK_EQUAL(it->num_incident_edges, 0);
- BOOST_CHECK_EQUAL(it->incident_edge == NULL, true);
-}
-
-// Sites: (0, 0), (0, 1).
-BOOST_AUTO_TEST_CASE_TEMPLATE(collinear_sites_test1, T, test_types) {
- typedef T coordinate_type;
- typedef typename voronoi_output_clipped<coordinate_type>::voronoi_edge_type voronoi_edge_type;
- typedef typename voronoi_output_clipped<coordinate_type>::voronoi_cell_const_iterator_type
- voronoi_cell_const_iterator_type;
-
- voronoi_builder<coordinate_type> test_voronoi_builder;
- std::vector< point_2d<coordinate_type> > points;
- points.push_back(make_point_2d<coordinate_type>(static_cast<coordinate_type>(0),
- static_cast<coordinate_type>(0)));
- points.push_back(make_point_2d<coordinate_type>(static_cast<coordinate_type>(0),
- static_cast<coordinate_type>(1)));
-
- test_voronoi_builder.init(points);
- test_voronoi_builder.run_sweepline();
- voronoi_output_clipped<coordinate_type> test_output;
- test_voronoi_builder.clip(test_output);
- VERIFY_VORONOI_OUTPUT(test_output, COMPLETE_VERIFICATION);
-
- BRect<coordinate_type> bounding_rectangle = test_voronoi_builder.get_bounding_rectangle();
- BOOST_CHECK_EQUAL(bounding_rectangle.x_min == static_cast<coordinate_type>(0) &&
- bounding_rectangle.y_min == static_cast<coordinate_type>(0) &&
- bounding_rectangle.x_max == static_cast<coordinate_type>(0) &&
- bounding_rectangle.y_max == static_cast<coordinate_type>(1), true);
-
- BOOST_CHECK_EQUAL(static_cast<int>(test_output.cell_records.size()), 2);
- BOOST_CHECK_EQUAL(static_cast<int>(test_output.vertex_records.size()), 0);
- BOOST_CHECK_EQUAL(static_cast<int>(test_output.edge_records.size()), 2);
-
- BOOST_CHECK_EQUAL(test_output.num_cell_records, 2);
- BOOST_CHECK_EQUAL(test_output.num_vertex_records, 0);
- BOOST_CHECK_EQUAL(test_output.num_edge_records, 1);
-
- voronoi_cell_const_iterator_type cell_it = test_output.cell_records.begin();
- BOOST_CHECK_EQUAL(cell_it->num_incident_edges, 1);
- cell_it++;
- BOOST_CHECK_EQUAL(cell_it->num_incident_edges, 1);
-
- voronoi_edge_type *edge1_1 = cell_it->incident_edge;
- voronoi_edge_type *edge1_2 = edge1_1->twin;
-
- BOOST_CHECK_EQUAL(edge1_1->twin == edge1_2, true);
- BOOST_CHECK_EQUAL(edge1_2->twin == edge1_1, true);
-
- BOOST_CHECK_EQUAL(edge1_1->next == edge1_1, true);
- BOOST_CHECK_EQUAL(edge1_1->prev == edge1_1, true);
- BOOST_CHECK_EQUAL(edge1_1->rot_next == NULL, true);
- BOOST_CHECK_EQUAL(edge1_1->rot_prev == NULL, true);
-
- BOOST_CHECK_EQUAL(edge1_2->next == edge1_2, true);
- BOOST_CHECK_EQUAL(edge1_2->prev == edge1_2, true);
- BOOST_CHECK_EQUAL(edge1_2->rot_next == NULL, true);
- BOOST_CHECK_EQUAL(edge1_2->rot_prev == NULL, true);
-}
-
-// Sites: (0, 0), (1, 1), (2, 2).
-BOOST_AUTO_TEST_CASE_TEMPLATE(collinear_sites_test2, T, test_types) {
- typedef T coordinate_type;
- typedef typename voronoi_output_clipped<coordinate_type>::voronoi_edge_type voronoi_edge_type;
- typedef typename voronoi_output_clipped<coordinate_type>::voronoi_cell_const_iterator_type
- voronoi_cell_const_iterator_type;
-
- voronoi_builder<coordinate_type> test_voronoi_builder;
- std::vector< point_2d<coordinate_type> > points;
- points.push_back(make_point_2d<coordinate_type>(static_cast<coordinate_type>(0),
- static_cast<coordinate_type>(0)));
- points.push_back(make_point_2d<coordinate_type>(static_cast<coordinate_type>(1),
- static_cast<coordinate_type>(1)));
- points.push_back(make_point_2d<coordinate_type>(static_cast<coordinate_type>(2),
- static_cast<coordinate_type>(2)));
-
- test_voronoi_builder.init(points);
- test_voronoi_builder.run_sweepline();
- voronoi_output_clipped<coordinate_type> test_output;
- test_voronoi_builder.clip(test_output);
- VERIFY_VORONOI_OUTPUT(test_output, COMPLETE_VERIFICATION);
-
- BRect<coordinate_type> bounding_rectangle = test_voronoi_builder.get_bounding_rectangle();
- BOOST_CHECK_EQUAL(bounding_rectangle.x_min == static_cast<coordinate_type>(0) &&
- bounding_rectangle.y_min == static_cast<coordinate_type>(0) &&
- bounding_rectangle.x_max == static_cast<coordinate_type>(2) &&
- bounding_rectangle.y_max == static_cast<coordinate_type>(2), true);
-
- BOOST_CHECK_EQUAL(static_cast<int>(test_output.cell_records.size()), 3);
- BOOST_CHECK_EQUAL(static_cast<int>(test_output.vertex_records.size()), 0);
- BOOST_CHECK_EQUAL(static_cast<int>(test_output.edge_records.size()), 4);
-
- BOOST_CHECK_EQUAL(test_output.num_cell_records, 3);
- BOOST_CHECK_EQUAL(test_output.num_vertex_records, 0);
- BOOST_CHECK_EQUAL(test_output.num_edge_records, 2);
-
- voronoi_cell_const_iterator_type cell_it = test_output.cell_records.begin();
- BOOST_CHECK_EQUAL(cell_it->num_incident_edges, 1);
- voronoi_edge_type *edge1_1 = cell_it->incident_edge;
- voronoi_edge_type *edge1_2 = edge1_1->twin;
- cell_it++;
- BOOST_CHECK_EQUAL(cell_it->num_incident_edges, 2);
- cell_it++;
- BOOST_CHECK_EQUAL(cell_it->num_incident_edges, 1);
- voronoi_edge_type *edge2_2 = cell_it->incident_edge;
- voronoi_edge_type *edge2_1 = edge2_2->twin;
-
- BOOST_CHECK_EQUAL(edge1_1->twin == edge1_2 && edge1_2->twin == edge1_1, true);
- BOOST_CHECK_EQUAL(edge2_1->twin == edge2_2 && edge2_2->twin == edge2_1, true);
-
- BOOST_CHECK_EQUAL(edge1_1->next == edge1_1 && edge1_1->prev == edge1_1, true);
- BOOST_CHECK_EQUAL(edge1_1->rot_next == NULL && edge1_1->rot_prev == NULL, true);
- BOOST_CHECK_EQUAL(edge1_2->rot_next == NULL && edge1_2->rot_prev == NULL, true);
- BOOST_CHECK_EQUAL(edge2_1->rot_next == NULL && edge2_1->rot_prev == NULL, true);
- BOOST_CHECK_EQUAL(edge2_2->next == edge2_2 && edge2_2->prev == edge2_2, true);
- BOOST_CHECK_EQUAL(edge2_2->rot_next == NULL && edge2_2->rot_prev == NULL, true);
-
- BOOST_CHECK_EQUAL(edge1_2->next == edge2_1 && edge1_2->prev == edge2_1, true);
- BOOST_CHECK_EQUAL(edge2_1->next == edge1_2 && edge2_1->prev == edge1_2, true);
-}
-
-// Sites: (0, 0), (0, 4), (2, 1).
-BOOST_AUTO_TEST_CASE_TEMPLATE(triangle_test1, T, test_types) {
- typedef T coordinate_type;
- typedef typename voronoi_output_clipped<coordinate_type>::voronoi_edge_type voronoi_edge_type;
- typedef typename voronoi_output_clipped<coordinate_type>::voronoi_vertex_const_iterator_type
- voronoi_vertex_const_iterator_type;
-
- voronoi_builder<coordinate_type> test_beach_line;
- point_2d<coordinate_type> point1 = make_point_2d<coordinate_type>(
- static_cast<coordinate_type>(0), static_cast<coordinate_type>(0));
- point_2d<coordinate_type> point2 = make_point_2d<coordinate_type>(
- static_cast<coordinate_type>(0), static_cast<coordinate_type>(4));
- point_2d<coordinate_type> point3 = make_point_2d<coordinate_type>(
- static_cast<coordinate_type>(2), static_cast<coordinate_type>(1));
-
- std::vector< point_2d<coordinate_type> > points;
- points.push_back(point1);
- points.push_back(point2);
- points.push_back(point3);
-
- test_beach_line.init(points);
- test_beach_line.run_sweepline();
- voronoi_output_clipped<coordinate_type> test_output;
- test_beach_line.clip(test_output);
- VERIFY_VORONOI_OUTPUT(test_output, COMPLETE_VERIFICATION);
-
- BRect<coordinate_type> bounding_rectangle = test_beach_line.get_bounding_rectangle();
- BOOST_CHECK_EQUAL(bounding_rectangle.x_min == static_cast<coordinate_type>(0) &&
- bounding_rectangle.y_min == static_cast<coordinate_type>(0) &&
- bounding_rectangle.x_max == static_cast<coordinate_type>(2) &&
- bounding_rectangle.y_max == static_cast<coordinate_type>(4), true);
-
- BOOST_CHECK_EQUAL(static_cast<int>(test_output.cell_records.size()), 3);
- BOOST_CHECK_EQUAL(static_cast<int>(test_output.vertex_records.size()), 1);
-
- voronoi_vertex_const_iterator_type it = test_output.vertex_records.begin();
- BOOST_CHECK_EQUAL(it->num_incident_edges, 3);
- BOOST_CHECK_EQUAL(it->vertex.x() == static_cast<coordinate_type>(0.25) &&
- it->vertex.y() == static_cast<coordinate_type>(2.0), true);
-
- voronoi_edge_type *edge1_1 = it->incident_edge;
- voronoi_edge_type *edge1_2 = edge1_1->twin;
- CHECK_EQUAL_POINTS(edge1_1->cell->get_point0(), point3);
- CHECK_EQUAL_POINTS(edge1_2->cell->get_point0(), point1);
-
- voronoi_edge_type *edge2_1 = edge1_1->rot_prev;
- voronoi_edge_type *edge2_2 = edge2_1->twin;
- CHECK_EQUAL_POINTS(edge2_1->cell->get_point0(), point1);
- CHECK_EQUAL_POINTS(edge2_2->cell->get_point0(), point2);
-
- voronoi_edge_type *edge3_1 = edge2_1->rot_prev;
- voronoi_edge_type *edge3_2 = edge3_1->twin;
- CHECK_EQUAL_POINTS(edge3_1->cell->get_point0(), point2);
- CHECK_EQUAL_POINTS(edge3_2->cell->get_point0(), point3);
-
- BOOST_CHECK_EQUAL(edge1_2->twin == edge1_1, true);
- BOOST_CHECK_EQUAL(edge2_2->twin == edge2_1, true);
- BOOST_CHECK_EQUAL(edge3_2->twin == edge3_1, true);
-
- BOOST_CHECK_EQUAL(edge1_1->prev == edge3_2 && edge1_1->next == edge3_2, true);
- BOOST_CHECK_EQUAL(edge2_1->prev == edge1_2 && edge2_1->next == edge1_2, true);
- BOOST_CHECK_EQUAL(edge3_1->prev == edge2_2 && edge3_1->next == edge2_2, true);
-
- BOOST_CHECK_EQUAL(edge1_2->next == edge2_1 && edge1_2->prev == edge2_1, true);
- BOOST_CHECK_EQUAL(edge2_2->next == edge3_1 && edge2_2->prev == edge3_1, true);
- BOOST_CHECK_EQUAL(edge3_2->next == edge1_1 && edge3_2->prev == edge1_1, true);
-
- BOOST_CHECK_EQUAL(edge1_1->rot_next == edge3_1, true);
- BOOST_CHECK_EQUAL(edge3_1->rot_next == edge2_1, true);
- BOOST_CHECK_EQUAL(edge2_1->rot_next == edge1_1, true);
-}
-
-// Sites: (0, 1), (2, 0), (2, 4).
-BOOST_AUTO_TEST_CASE_TEMPLATE(triangle_test2, T, test_types) {
- typedef T coordinate_type;
- typedef typename voronoi_output_clipped<coordinate_type>::voronoi_edge_type voronoi_edge_type;
- typedef typename voronoi_output_clipped<coordinate_type>::voronoi_vertex_const_iterator_type
- voronoi_vertex_const_iterator_type;
-
- voronoi_builder<coordinate_type> test_beach_line;
- point_2d<coordinate_type> point1 = make_point_2d<coordinate_type>(
- static_cast<coordinate_type>(0), static_cast<coordinate_type>(1));
- point_2d<coordinate_type> point2 = make_point_2d<coordinate_type>(
- static_cast<coordinate_type>(2), static_cast<coordinate_type>(0));
- point_2d<coordinate_type> point3 = make_point_2d<coordinate_type>(
- static_cast<coordinate_type>(2), static_cast<coordinate_type>(4));
-
- std::vector< point_2d<coordinate_type> > points;
- points.push_back(point1);
- points.push_back(point2);
- points.push_back(point3);
-
- test_beach_line.init(points);
- test_beach_line.run_sweepline();
- voronoi_output_clipped<coordinate_type> test_output;
- test_beach_line.clip(test_output);
- VERIFY_VORONOI_OUTPUT(test_output, COMPLETE_VERIFICATION);
-
- BOOST_CHECK_EQUAL(static_cast<int>(test_output.cell_records.size()), 3);
- BOOST_CHECK_EQUAL(static_cast<int>(test_output.vertex_records.size()), 1);
-
- voronoi_vertex_const_iterator_type it = test_output.vertex_records.begin();
- BOOST_CHECK_EQUAL(it->num_incident_edges, 3);
- BOOST_CHECK_EQUAL(it->vertex.x() == static_cast<coordinate_type>(1.75) &&
- it->vertex.y() == static_cast<coordinate_type>(2.0), true);
-
- voronoi_edge_type *edge1_1 = it->incident_edge;
- voronoi_edge_type *edge1_2 = edge1_1->twin;
- CHECK_EQUAL_POINTS(edge1_1->cell->get_point0(), point2);
- CHECK_EQUAL_POINTS(edge1_2->cell->get_point0(), point1);
-
- voronoi_edge_type *edge2_1 = edge1_1->rot_prev;
- voronoi_edge_type *edge2_2 = edge2_1->twin;
- CHECK_EQUAL_POINTS(edge2_1->cell->get_point0(), point1);
- CHECK_EQUAL_POINTS(edge2_2->cell->get_point0(), point3);
-
- voronoi_edge_type *edge3_1 = edge2_1->rot_prev;
- voronoi_edge_type *edge3_2 = edge3_1->twin;
- CHECK_EQUAL_POINTS(edge3_1->cell->get_point0(), point3);
- CHECK_EQUAL_POINTS(edge3_2->cell->get_point0(), point2);
-
- BOOST_CHECK_EQUAL(edge1_2->twin == edge1_1, true);
- BOOST_CHECK_EQUAL(edge2_2->twin == edge2_1, true);
- BOOST_CHECK_EQUAL(edge3_2->twin == edge3_1, true);
-
- BOOST_CHECK_EQUAL(edge1_1->prev == edge3_2 && edge1_1->next == edge3_2, true);
- BOOST_CHECK_EQUAL(edge2_1->prev == edge1_2 && edge2_1->next == edge1_2, true);
- BOOST_CHECK_EQUAL(edge3_1->prev == edge2_2 && edge3_1->next == edge2_2, true);
-
- BOOST_CHECK_EQUAL(edge1_2->next == edge2_1 && edge1_2->prev == edge2_1, true);
- BOOST_CHECK_EQUAL(edge2_2->next == edge3_1 && edge2_2->prev == edge3_1, true);
- BOOST_CHECK_EQUAL(edge3_2->next == edge1_1 && edge3_2->prev == edge1_1, true);
-
- BOOST_CHECK_EQUAL(edge1_1->rot_next == edge3_1, true);
- BOOST_CHECK_EQUAL(edge3_1->rot_next == edge2_1, true);
- BOOST_CHECK_EQUAL(edge2_1->rot_next == edge1_1, true);
-}
-
-// Sites: (0, 0), (0, 1), (1, 0), (1, 1).
-BOOST_AUTO_TEST_CASE_TEMPLATE(square_test1, T, test_types) {
- typedef T coordinate_type;
- typedef typename voronoi_output_clipped<coordinate_type>::voronoi_edge_type voronoi_edge_type;
- typedef typename voronoi_output_clipped<coordinate_type>::voronoi_vertex_const_iterator_type
- voronoi_vertex_const_iterator_type;
-
- voronoi_builder<coordinate_type> test_beach_line;
- std::vector< point_2d<coordinate_type> > points;
- points.push_back(make_point_2d<coordinate_type>(static_cast<coordinate_type>(0),
- static_cast<coordinate_type>(0)));
- points.push_back(make_point_2d<coordinate_type>(static_cast<coordinate_type>(0),
- static_cast<coordinate_type>(1)));
- points.push_back(make_point_2d<coordinate_type>(static_cast<coordinate_type>(1),
- static_cast<coordinate_type>(0)));
- points.push_back(make_point_2d<coordinate_type>(static_cast<coordinate_type>(1),
- static_cast<coordinate_type>(1)));
-
- test_beach_line.init(points);
- test_beach_line.run_sweepline();
- voronoi_output_clipped<coordinate_type> test_output;
- test_beach_line.clip(test_output);
+ voronoi_output<coordinate_type> test_output;
+ build_voronoi(points, test_output);
VERIFY_VORONOI_OUTPUT(test_output, COMPLETE_VERIFICATION);
- BOOST_CHECK_EQUAL(test_output.num_cell_records, 4);
- BOOST_CHECK_EQUAL(test_output.num_vertex_records, 1);
- BOOST_CHECK_EQUAL(test_output.num_edge_records, 4);
-
- // Check voronoi vertex.
- voronoi_vertex_const_iterator_type it = test_output.vertex_records.begin();
- BOOST_CHECK_EQUAL(it->num_incident_edges, 4);
- BOOST_CHECK_EQUAL(it->vertex.x() == static_cast<coordinate_type>(0.5) &&
- it->vertex.y() == static_cast<coordinate_type>(0.5), true);
-
- // Check voronoi edges.
- voronoi_edge_type *edge1_1 = it->incident_edge;
- voronoi_edge_type *edge1_2 = edge1_1->twin;
- CHECK_EQUAL_POINTS(edge1_1->cell->get_point0(), points[1]);
- CHECK_EQUAL_POINTS(edge1_2->cell->get_point0(), points[3]);
-
- voronoi_edge_type *edge2_1 = edge1_1->rot_prev;
- voronoi_edge_type *edge2_2 = edge2_1->twin;
- CHECK_EQUAL_POINTS(edge2_1->cell->get_point0(), points[3]);
- CHECK_EQUAL_POINTS(edge2_2->cell->get_point0(), points[2]);
-
- voronoi_edge_type *edge3_1 = edge2_1->rot_prev;
- voronoi_edge_type *edge3_2 = edge3_1->twin;
- CHECK_EQUAL_POINTS(edge3_1->cell->get_point0(), points[2]);
- CHECK_EQUAL_POINTS(edge3_2->cell->get_point0(), points[0]);
-
- voronoi_edge_type *edge4_1 = edge3_1->rot_prev;
- voronoi_edge_type *edge4_2 = edge4_1->twin;
- CHECK_EQUAL_POINTS(edge4_1->cell->get_point0(), points[0]);
- CHECK_EQUAL_POINTS(edge4_2->cell->get_point0(), points[1]);
-
- BOOST_CHECK_EQUAL(edge1_2->twin == edge1_1, true);
- BOOST_CHECK_EQUAL(edge2_2->twin == edge2_1, true);
- BOOST_CHECK_EQUAL(edge3_2->twin == edge3_1, true);
- BOOST_CHECK_EQUAL(edge4_2->twin == edge4_1, true);
-
- BOOST_CHECK_EQUAL(edge1_1->prev == edge4_2 && edge1_1->next == edge4_2, true);
- BOOST_CHECK_EQUAL(edge2_1->prev == edge1_2 && edge2_1->next == edge1_2, true);
- BOOST_CHECK_EQUAL(edge3_1->prev == edge2_2 && edge3_1->next == edge2_2, true);
- BOOST_CHECK_EQUAL(edge4_1->prev == edge3_2 && edge4_1->next == edge3_2, true);
-
- BOOST_CHECK_EQUAL(edge1_2->next == edge2_1 && edge1_2->prev == edge2_1, true);
- BOOST_CHECK_EQUAL(edge2_2->next == edge3_1 && edge2_2->prev == edge3_1, true);
- BOOST_CHECK_EQUAL(edge3_2->next == edge4_1 && edge3_2->prev == edge4_1, true);
- BOOST_CHECK_EQUAL(edge4_2->next == edge1_1 && edge4_2->prev == edge1_1, true);
-
- BOOST_CHECK_EQUAL(edge1_1->rot_next == edge4_1, true);
- BOOST_CHECK_EQUAL(edge4_1->rot_next == edge3_1, true);
- BOOST_CHECK_EQUAL(edge3_1->rot_next == edge2_1, true);
- BOOST_CHECK_EQUAL(edge2_1->rot_next == edge1_1, true);
-}
-
+ BRect<coordinate_type> bounding_rectangle = test_output.bounding_rectangle();
+ BOOST_CHECK_EQUAL(bounding_rectangle.x_min() == static_cast<coordinate_type>(0) &&
+ bounding_rectangle.y_min() == static_cast<coordinate_type>(0) &&
+ bounding_rectangle.x_max() == static_cast<coordinate_type>(0) &&
+ bounding_rectangle.y_max() == static_cast<coordinate_type>(0), true);
+
+ BOOST_CHECK_EQUAL(static_cast<int>(test_output.cell_records().size()), 1);
+ BOOST_CHECK_EQUAL(static_cast<int>(test_output.vertex_records().size()), 0);
+ BOOST_CHECK_EQUAL(static_cast<int>(test_output.edge_records().size()), 0);
+
+ BOOST_CHECK_EQUAL(test_output.num_cell_records(), 1);
+ BOOST_CHECK_EQUAL(test_output.num_vertex_records(), 0);
+ BOOST_CHECK_EQUAL(test_output.num_edge_records(), 0);
+
+ voronoi_cell_const_iterator_type it = test_output.cell_records().begin();
+ BOOST_CHECK_EQUAL(it->num_incident_edges(), 0);
+ BOOST_CHECK_EQUAL(it->incident_edge() == NULL, true);
+}
+//
+//// Sites: (0, 0), (0, 1).
+//BOOST_AUTO_TEST_CASE_TEMPLATE(collinear_sites_test1, T, test_types) {
+// typedef T coordinate_type;
+// typedef typename voronoi_output_clipped<coordinate_type>::voronoi_edge_type voronoi_edge_type;
+// typedef typename voronoi_output_clipped<coordinate_type>::voronoi_cell_const_iterator_type
+// voronoi_cell_const_iterator_type;
+//
+// voronoi_builder<coordinate_type> test_voronoi_builder;
+// std::vector< point_2d<coordinate_type> > points;
+// points.push_back(make_point_2d<coordinate_type>(static_cast<coordinate_type>(0),
+// static_cast<coordinate_type>(0)));
+// points.push_back(make_point_2d<coordinate_type>(static_cast<coordinate_type>(0),
+// static_cast<coordinate_type>(1)));
+//
+// test_voronoi_builder.init(points);
+// test_voronoi_builder.run_sweepline();
+// voronoi_output_clipped<coordinate_type> test_output;
+// test_voronoi_builder.clip(test_output);
+// VERIFY_VORONOI_OUTPUT(test_output, COMPLETE_VERIFICATION);
+//
+// BRect<coordinate_type> bounding_rectangle = test_voronoi_builder.get_bounding_rectangle();
+// BOOST_CHECK_EQUAL(bounding_rectangle.x_min == static_cast<coordinate_type>(0) &&
+// bounding_rectangle.y_min == static_cast<coordinate_type>(0) &&
+// bounding_rectangle.x_max == static_cast<coordinate_type>(0) &&
+// bounding_rectangle.y_max == static_cast<coordinate_type>(1), true);
+//
+// BOOST_CHECK_EQUAL(static_cast<int>(test_output.cell_records.size()), 2);
+// BOOST_CHECK_EQUAL(static_cast<int>(test_output.vertex_records.size()), 0);
+// BOOST_CHECK_EQUAL(static_cast<int>(test_output.edge_records.size()), 2);
+//
+// BOOST_CHECK_EQUAL(test_output.num_cell_records, 2);
+// BOOST_CHECK_EQUAL(test_output.num_vertex_records, 0);
+// BOOST_CHECK_EQUAL(test_output.num_edge_records, 1);
+//
+// voronoi_cell_const_iterator_type cell_it = test_output.cell_records.begin();
+// BOOST_CHECK_EQUAL(cell_it->num_incident_edges, 1);
+// cell_it++;
+// BOOST_CHECK_EQUAL(cell_it->num_incident_edges, 1);
+//
+// voronoi_edge_type *edge1_1 = cell_it->incident_edge;
+// voronoi_edge_type *edge1_2 = edge1_1->twin;
+//
+// BOOST_CHECK_EQUAL(edge1_1->twin == edge1_2, true);
+// BOOST_CHECK_EQUAL(edge1_2->twin == edge1_1, true);
+//
+// BOOST_CHECK_EQUAL(edge1_1->next == edge1_1, true);
+// BOOST_CHECK_EQUAL(edge1_1->prev == edge1_1, true);
+// BOOST_CHECK_EQUAL(edge1_1->rot_next == NULL, true);
+// BOOST_CHECK_EQUAL(edge1_1->rot_prev == NULL, true);
+//
+// BOOST_CHECK_EQUAL(edge1_2->next == edge1_2, true);
+// BOOST_CHECK_EQUAL(edge1_2->prev == edge1_2, true);
+// BOOST_CHECK_EQUAL(edge1_2->rot_next == NULL, true);
+// BOOST_CHECK_EQUAL(edge1_2->rot_prev == NULL, true);
+//}
+//
+//// Sites: (0, 0), (1, 1), (2, 2).
+//BOOST_AUTO_TEST_CASE_TEMPLATE(collinear_sites_test2, T, test_types) {
+// typedef T coordinate_type;
+// typedef typename voronoi_output_clipped<coordinate_type>::voronoi_edge_type voronoi_edge_type;
+// typedef typename voronoi_output_clipped<coordinate_type>::voronoi_cell_const_iterator_type
+// voronoi_cell_const_iterator_type;
+//
+// voronoi_builder<coordinate_type> test_voronoi_builder;
+// std::vector< point_2d<coordinate_type> > points;
+// points.push_back(make_point_2d<coordinate_type>(static_cast<coordinate_type>(0),
+// static_cast<coordinate_type>(0)));
+// points.push_back(make_point_2d<coordinate_type>(static_cast<coordinate_type>(1),
+// static_cast<coordinate_type>(1)));
+// points.push_back(make_point_2d<coordinate_type>(static_cast<coordinate_type>(2),
+// static_cast<coordinate_type>(2)));
+//
+// test_voronoi_builder.init(points);
+// test_voronoi_builder.run_sweepline();
+// voronoi_output_clipped<coordinate_type> test_output;
+// test_voronoi_builder.clip(test_output);
+// VERIFY_VORONOI_OUTPUT(test_output, COMPLETE_VERIFICATION);
+//
+// BRect<coordinate_type> bounding_rectangle = test_voronoi_builder.get_bounding_rectangle();
+// BOOST_CHECK_EQUAL(bounding_rectangle.x_min == static_cast<coordinate_type>(0) &&
+// bounding_rectangle.y_min == static_cast<coordinate_type>(0) &&
+// bounding_rectangle.x_max == static_cast<coordinate_type>(2) &&
+// bounding_rectangle.y_max == static_cast<coordinate_type>(2), true);
+//
+// BOOST_CHECK_EQUAL(static_cast<int>(test_output.cell_records.size()), 3);
+// BOOST_CHECK_EQUAL(static_cast<int>(test_output.vertex_records.size()), 0);
+// BOOST_CHECK_EQUAL(static_cast<int>(test_output.edge_records.size()), 4);
+//
+// BOOST_CHECK_EQUAL(test_output.num_cell_records, 3);
+// BOOST_CHECK_EQUAL(test_output.num_vertex_records, 0);
+// BOOST_CHECK_EQUAL(test_output.num_edge_records, 2);
+//
+// voronoi_cell_const_iterator_type cell_it = test_output.cell_records.begin();
+// BOOST_CHECK_EQUAL(cell_it->num_incident_edges, 1);
+// voronoi_edge_type *edge1_1 = cell_it->incident_edge;
+// voronoi_edge_type *edge1_2 = edge1_1->twin;
+// cell_it++;
+// BOOST_CHECK_EQUAL(cell_it->num_incident_edges, 2);
+// cell_it++;
+// BOOST_CHECK_EQUAL(cell_it->num_incident_edges, 1);
+// voronoi_edge_type *edge2_2 = cell_it->incident_edge;
+// voronoi_edge_type *edge2_1 = edge2_2->twin;
+//
+// BOOST_CHECK_EQUAL(edge1_1->twin == edge1_2 && edge1_2->twin == edge1_1, true);
+// BOOST_CHECK_EQUAL(edge2_1->twin == edge2_2 && edge2_2->twin == edge2_1, true);
+//
+// BOOST_CHECK_EQUAL(edge1_1->next == edge1_1 && edge1_1->prev == edge1_1, true);
+// BOOST_CHECK_EQUAL(edge1_1->rot_next == NULL && edge1_1->rot_prev == NULL, true);
+// BOOST_CHECK_EQUAL(edge1_2->rot_next == NULL && edge1_2->rot_prev == NULL, true);
+// BOOST_CHECK_EQUAL(edge2_1->rot_next == NULL && edge2_1->rot_prev == NULL, true);
+// BOOST_CHECK_EQUAL(edge2_2->next == edge2_2 && edge2_2->prev == edge2_2, true);
+// BOOST_CHECK_EQUAL(edge2_2->rot_next == NULL && edge2_2->rot_prev == NULL, true);
+//
+// BOOST_CHECK_EQUAL(edge1_2->next == edge2_1 && edge1_2->prev == edge2_1, true);
+// BOOST_CHECK_EQUAL(edge2_1->next == edge1_2 && edge2_1->prev == edge1_2, true);
+//}
+//
+//// Sites: (0, 0), (0, 4), (2, 1).
+//BOOST_AUTO_TEST_CASE_TEMPLATE(triangle_test1, T, test_types) {
+// typedef T coordinate_type;
+// typedef typename voronoi_output_clipped<coordinate_type>::voronoi_edge_type voronoi_edge_type;
+// typedef typename voronoi_output_clipped<coordinate_type>::voronoi_vertex_const_iterator_type
+// voronoi_vertex_const_iterator_type;
+//
+// voronoi_builder<coordinate_type> test_beach_line;
+// point_2d<coordinate_type> point1 = make_point_2d<coordinate_type>(
+// static_cast<coordinate_type>(0), static_cast<coordinate_type>(0));
+// point_2d<coordinate_type> point2 = make_point_2d<coordinate_type>(
+// static_cast<coordinate_type>(0), static_cast<coordinate_type>(4));
+// point_2d<coordinate_type> point3 = make_point_2d<coordinate_type>(
+// static_cast<coordinate_type>(2), static_cast<coordinate_type>(1));
+//
+// std::vector< point_2d<coordinate_type> > points;
+// points.push_back(point1);
+// points.push_back(point2);
+// points.push_back(point3);
+//
+// test_beach_line.init(points);
+// test_beach_line.run_sweepline();
+// voronoi_output_clipped<coordinate_type> test_output;
+// test_beach_line.clip(test_output);
+// VERIFY_VORONOI_OUTPUT(test_output, COMPLETE_VERIFICATION);
+//
+// BRect<coordinate_type> bounding_rectangle = test_beach_line.get_bounding_rectangle();
+// BOOST_CHECK_EQUAL(bounding_rectangle.x_min == static_cast<coordinate_type>(0) &&
+// bounding_rectangle.y_min == static_cast<coordinate_type>(0) &&
+// bounding_rectangle.x_max == static_cast<coordinate_type>(2) &&
+// bounding_rectangle.y_max == static_cast<coordinate_type>(4), true);
+//
+// BOOST_CHECK_EQUAL(static_cast<int>(test_output.cell_records.size()), 3);
+// BOOST_CHECK_EQUAL(static_cast<int>(test_output.vertex_records.size()), 1);
+//
+// voronoi_vertex_const_iterator_type it = test_output.vertex_records.begin();
+// BOOST_CHECK_EQUAL(it->num_incident_edges, 3);
+// BOOST_CHECK_EQUAL(it->vertex.x() == static_cast<coordinate_type>(0.25) &&
+// it->vertex.y() == static_cast<coordinate_type>(2.0), true);
+//
+// voronoi_edge_type *edge1_1 = it->incident_edge;
+// voronoi_edge_type *edge1_2 = edge1_1->twin;
+// CHECK_EQUAL_POINTS(edge1_1->cell->get_point0(), point3);
+// CHECK_EQUAL_POINTS(edge1_2->cell->get_point0(), point1);
+//
+// voronoi_edge_type *edge2_1 = edge1_1->rot_prev;
+// voronoi_edge_type *edge2_2 = edge2_1->twin;
+// CHECK_EQUAL_POINTS(edge2_1->cell->get_point0(), point1);
+// CHECK_EQUAL_POINTS(edge2_2->cell->get_point0(), point2);
+//
+// voronoi_edge_type *edge3_1 = edge2_1->rot_prev;
+// voronoi_edge_type *edge3_2 = edge3_1->twin;
+// CHECK_EQUAL_POINTS(edge3_1->cell->get_point0(), point2);
+// CHECK_EQUAL_POINTS(edge3_2->cell->get_point0(), point3);
+//
+// BOOST_CHECK_EQUAL(edge1_2->twin == edge1_1, true);
+// BOOST_CHECK_EQUAL(edge2_2->twin == edge2_1, true);
+// BOOST_CHECK_EQUAL(edge3_2->twin == edge3_1, true);
+//
+// BOOST_CHECK_EQUAL(edge1_1->prev == edge3_2 && edge1_1->next == edge3_2, true);
+// BOOST_CHECK_EQUAL(edge2_1->prev == edge1_2 && edge2_1->next == edge1_2, true);
+// BOOST_CHECK_EQUAL(edge3_1->prev == edge2_2 && edge3_1->next == edge2_2, true);
+//
+// BOOST_CHECK_EQUAL(edge1_2->next == edge2_1 && edge1_2->prev == edge2_1, true);
+// BOOST_CHECK_EQUAL(edge2_2->next == edge3_1 && edge2_2->prev == edge3_1, true);
+// BOOST_CHECK_EQUAL(edge3_2->next == edge1_1 && edge3_2->prev == edge1_1, true);
+//
+// BOOST_CHECK_EQUAL(edge1_1->rot_next == edge3_1, true);
+// BOOST_CHECK_EQUAL(edge3_1->rot_next == edge2_1, true);
+// BOOST_CHECK_EQUAL(edge2_1->rot_next == edge1_1, true);
+//}
+//
+//// Sites: (0, 1), (2, 0), (2, 4).
+//BOOST_AUTO_TEST_CASE_TEMPLATE(triangle_test2, T, test_types) {
+// typedef T coordinate_type;
+// typedef typename voronoi_output_clipped<coordinate_type>::voronoi_edge_type voronoi_edge_type;
+// typedef typename voronoi_output_clipped<coordinate_type>::voronoi_vertex_const_iterator_type
+// voronoi_vertex_const_iterator_type;
+//
+// voronoi_builder<coordinate_type> test_beach_line;
+// point_2d<coordinate_type> point1 = make_point_2d<coordinate_type>(
+// static_cast<coordinate_type>(0), static_cast<coordinate_type>(1));
+// point_2d<coordinate_type> point2 = make_point_2d<coordinate_type>(
+// static_cast<coordinate_type>(2), static_cast<coordinate_type>(0));
+// point_2d<coordinate_type> point3 = make_point_2d<coordinate_type>(
+// static_cast<coordinate_type>(2), static_cast<coordinate_type>(4));
+//
+// std::vector< point_2d<coordinate_type> > points;
+// points.push_back(point1);
+// points.push_back(point2);
+// points.push_back(point3);
+//
+// test_beach_line.init(points);
+// test_beach_line.run_sweepline();
+// voronoi_output_clipped<coordinate_type> test_output;
+// test_beach_line.clip(test_output);
+// VERIFY_VORONOI_OUTPUT(test_output, COMPLETE_VERIFICATION);
+//
+// BOOST_CHECK_EQUAL(static_cast<int>(test_output.cell_records.size()), 3);
+// BOOST_CHECK_EQUAL(static_cast<int>(test_output.vertex_records.size()), 1);
+//
+// voronoi_vertex_const_iterator_type it = test_output.vertex_records.begin();
+// BOOST_CHECK_EQUAL(it->num_incident_edges, 3);
+// BOOST_CHECK_EQUAL(it->vertex.x() == static_cast<coordinate_type>(1.75) &&
+// it->vertex.y() == static_cast<coordinate_type>(2.0), true);
+//
+// voronoi_edge_type *edge1_1 = it->incident_edge;
+// voronoi_edge_type *edge1_2 = edge1_1->twin;
+// CHECK_EQUAL_POINTS(edge1_1->cell->get_point0(), point2);
+// CHECK_EQUAL_POINTS(edge1_2->cell->get_point0(), point1);
+//
+// voronoi_edge_type *edge2_1 = edge1_1->rot_prev;
+// voronoi_edge_type *edge2_2 = edge2_1->twin;
+// CHECK_EQUAL_POINTS(edge2_1->cell->get_point0(), point1);
+// CHECK_EQUAL_POINTS(edge2_2->cell->get_point0(), point3);
+//
+// voronoi_edge_type *edge3_1 = edge2_1->rot_prev;
+// voronoi_edge_type *edge3_2 = edge3_1->twin;
+// CHECK_EQUAL_POINTS(edge3_1->cell->get_point0(), point3);
+// CHECK_EQUAL_POINTS(edge3_2->cell->get_point0(), point2);
+//
+// BOOST_CHECK_EQUAL(edge1_2->twin == edge1_1, true);
+// BOOST_CHECK_EQUAL(edge2_2->twin == edge2_1, true);
+// BOOST_CHECK_EQUAL(edge3_2->twin == edge3_1, true);
+//
+// BOOST_CHECK_EQUAL(edge1_1->prev == edge3_2 && edge1_1->next == edge3_2, true);
+// BOOST_CHECK_EQUAL(edge2_1->prev == edge1_2 && edge2_1->next == edge1_2, true);
+// BOOST_CHECK_EQUAL(edge3_1->prev == edge2_2 && edge3_1->next == edge2_2, true);
+//
+// BOOST_CHECK_EQUAL(edge1_2->next == edge2_1 && edge1_2->prev == edge2_1, true);
+// BOOST_CHECK_EQUAL(edge2_2->next == edge3_1 && edge2_2->prev == edge3_1, true);
+// BOOST_CHECK_EQUAL(edge3_2->next == edge1_1 && edge3_2->prev == edge1_1, true);
+//
+// BOOST_CHECK_EQUAL(edge1_1->rot_next == edge3_1, true);
+// BOOST_CHECK_EQUAL(edge3_1->rot_next == edge2_1, true);
+// BOOST_CHECK_EQUAL(edge2_1->rot_next == edge1_1, true);
+//}
+//
+//// Sites: (0, 0), (0, 1), (1, 0), (1, 1).
+//BOOST_AUTO_TEST_CASE_TEMPLATE(square_test1, T, test_types) {
+// typedef T coordinate_type;
+// typedef typename voronoi_output_clipped<coordinate_type>::voronoi_edge_type voronoi_edge_type;
+// typedef typename voronoi_output_clipped<coordinate_type>::voronoi_vertex_const_iterator_type
+// voronoi_vertex_const_iterator_type;
+//
+// voronoi_builder<coordinate_type> test_beach_line;
+// std::vector< point_2d<coordinate_type> > points;
+// points.push_back(make_point_2d<coordinate_type>(static_cast<coordinate_type>(0),
+// static_cast<coordinate_type>(0)));
+// points.push_back(make_point_2d<coordinate_type>(static_cast<coordinate_type>(0),
+// static_cast<coordinate_type>(1)));
+// points.push_back(make_point_2d<coordinate_type>(static_cast<coordinate_type>(1),
+// static_cast<coordinate_type>(0)));
+// points.push_back(make_point_2d<coordinate_type>(static_cast<coordinate_type>(1),
+// static_cast<coordinate_type>(1)));
+//
+// test_beach_line.init(points);
+// test_beach_line.run_sweepline();
+// voronoi_output_clipped<coordinate_type> test_output;
+// test_beach_line.clip(test_output);
+// VERIFY_VORONOI_OUTPUT(test_output, COMPLETE_VERIFICATION);
+//
+// BOOST_CHECK_EQUAL(test_output.num_cell_records, 4);
+// BOOST_CHECK_EQUAL(test_output.num_vertex_records, 1);
+// BOOST_CHECK_EQUAL(test_output.num_edge_records, 4);
+//
+// // Check voronoi vertex.
+// voronoi_vertex_const_iterator_type it = test_output.vertex_records.begin();
+// BOOST_CHECK_EQUAL(it->num_incident_edges, 4);
+// BOOST_CHECK_EQUAL(it->vertex.x() == static_cast<coordinate_type>(0.5) &&
+// it->vertex.y() == static_cast<coordinate_type>(0.5), true);
+//
+// // Check voronoi edges.
+// voronoi_edge_type *edge1_1 = it->incident_edge;
+// voronoi_edge_type *edge1_2 = edge1_1->twin;
+// CHECK_EQUAL_POINTS(edge1_1->cell->get_point0(), points[1]);
+// CHECK_EQUAL_POINTS(edge1_2->cell->get_point0(), points[3]);
+//
+// voronoi_edge_type *edge2_1 = edge1_1->rot_prev;
+// voronoi_edge_type *edge2_2 = edge2_1->twin;
+// CHECK_EQUAL_POINTS(edge2_1->cell->get_point0(), points[3]);
+// CHECK_EQUAL_POINTS(edge2_2->cell->get_point0(), points[2]);
+//
+// voronoi_edge_type *edge3_1 = edge2_1->rot_prev;
+// voronoi_edge_type *edge3_2 = edge3_1->twin;
+// CHECK_EQUAL_POINTS(edge3_1->cell->get_point0(), points[2]);
+// CHECK_EQUAL_POINTS(edge3_2->cell->get_point0(), points[0]);
+//
+// voronoi_edge_type *edge4_1 = edge3_1->rot_prev;
+// voronoi_edge_type *edge4_2 = edge4_1->twin;
+// CHECK_EQUAL_POINTS(edge4_1->cell->get_point0(), points[0]);
+// CHECK_EQUAL_POINTS(edge4_2->cell->get_point0(), points[1]);
+//
+// BOOST_CHECK_EQUAL(edge1_2->twin == edge1_1, true);
+// BOOST_CHECK_EQUAL(edge2_2->twin == edge2_1, true);
+// BOOST_CHECK_EQUAL(edge3_2->twin == edge3_1, true);
+// BOOST_CHECK_EQUAL(edge4_2->twin == edge4_1, true);
+//
+// BOOST_CHECK_EQUAL(edge1_1->prev == edge4_2 && edge1_1->next == edge4_2, true);
+// BOOST_CHECK_EQUAL(edge2_1->prev == edge1_2 && edge2_1->next == edge1_2, true);
+// BOOST_CHECK_EQUAL(edge3_1->prev == edge2_2 && edge3_1->next == edge2_2, true);
+// BOOST_CHECK_EQUAL(edge4_1->prev == edge3_2 && edge4_1->next == edge3_2, true);
+//
+// BOOST_CHECK_EQUAL(edge1_2->next == edge2_1 && edge1_2->prev == edge2_1, true);
+// BOOST_CHECK_EQUAL(edge2_2->next == edge3_1 && edge2_2->prev == edge3_1, true);
+// BOOST_CHECK_EQUAL(edge3_2->next == edge4_1 && edge3_2->prev == edge4_1, true);
+// BOOST_CHECK_EQUAL(edge4_2->next == edge1_1 && edge4_2->prev == edge1_1, true);
+//
+// BOOST_CHECK_EQUAL(edge1_1->rot_next == edge4_1, true);
+// BOOST_CHECK_EQUAL(edge4_1->rot_next == edge3_1, true);
+// BOOST_CHECK_EQUAL(edge3_1->rot_next == edge2_1, true);
+// BOOST_CHECK_EQUAL(edge2_1->rot_next == edge1_1, true);
+//}
+//
#ifdef NDEBUG
BOOST_AUTO_TEST_CASE_TEMPLATE(grid_test, T, test_types) {
- voronoi_builder<T> test_builder;
- voronoi_output_clipped<T> test_output_small, test_output_large;
+ voronoi_output<T> test_output_small, test_output_large;
std::vector< point_2d<T> > point_vec_small, point_vec_large;
int grid_size[4] = {10, 33, 100, 333};
int max_value[4] = {10, 33, 100, 333};
@@ -410,17 +405,13 @@
point_vec_small.push_back(make_point_2d<T>(i, j));
point_vec_large.push_back(make_point_2d<T>(koef * i, koef * j));
}
- test_builder.init(point_vec_small);
- test_builder.run_sweepline();
- test_builder.clip(test_output_small);
- test_builder.init(point_vec_large);
- test_builder.run_sweepline();
- test_builder.clip(test_output_large);
+ build_voronoi(point_vec_small, test_output_small);
+ build_voronoi(point_vec_large, test_output_large);
VERIFY_VORONOI_OUTPUT(test_output_small, COMPLETE_VERIFICATION);
VERIFY_VORONOI_OUTPUT(test_output_large, COMPLETE_VERIFICATION);
- BOOST_CHECK_EQUAL(test_output_small.num_cell_records, test_output_large.num_cell_records);
- BOOST_CHECK_EQUAL(test_output_small.num_vertex_records, test_output_large.num_vertex_records);
- BOOST_CHECK_EQUAL(test_output_small.num_edge_records, test_output_large.num_edge_records);
+ BOOST_CHECK_EQUAL(test_output_small.num_cell_records(), test_output_large.num_cell_records());
+ BOOST_CHECK_EQUAL(test_output_small.num_vertex_records(), test_output_large.num_vertex_records());
+ BOOST_CHECK_EQUAL(test_output_small.num_edge_records(), test_output_large.num_edge_records());
point_vec_small.clear();
point_vec_large.clear();
}
@@ -430,12 +421,11 @@
#ifdef NDEBUG
BOOST_AUTO_TEST_CASE_TEMPLATE(random_test, T, test_types) {
srand(static_cast<unsigned int>(time(NULL)));
- voronoi_builder<T> test_builder;
- voronoi_output_clipped<T> test_output_small, test_output_large;
+ voronoi_output<T> test_output_small, test_output_large;
std::vector< point_2d<T> > point_vec_small, point_vec_large;
int num_points[] = {10, 100, 1000, 10000, 100000};
int num_runs[] = {10000, 1000, 100, 10, 1};
- int mod_koef[] = {10, 100, 100, 10000, 10000};
+ int mod_koef[] = {10, 100, 100, 1000, 10000};
int max_value[] = {5, 50, 50, 5000, 5000};
int array_length = sizeof(num_points) / sizeof(int);
for (int k = 0; k < array_length; k++) {
@@ -447,17 +437,16 @@
point_vec_small.push_back(make_point_2d<T>(x, y));
point_vec_large.push_back(make_point_2d<T>(koef * x, koef * y));
}
- test_builder.init(point_vec_small);
- test_builder.run_sweepline();
- test_builder.clip(test_output_small);
- test_builder.init(point_vec_large);
- test_builder.run_sweepline();
- test_builder.clip(test_output_large);
+ build_voronoi(point_vec_small, test_output_small);
+ build_voronoi(point_vec_large, test_output_large);
VERIFY_VORONOI_OUTPUT(test_output_small, COMPLETE_VERIFICATION);
VERIFY_VORONOI_OUTPUT(test_output_large, COMPLETE_VERIFICATION);
- BOOST_CHECK_EQUAL(test_output_small.num_cell_records, test_output_large.num_cell_records);
- BOOST_CHECK_EQUAL(test_output_small.num_vertex_records, test_output_large.num_vertex_records);
- BOOST_CHECK_EQUAL(test_output_small.num_edge_records, test_output_large.num_edge_records);
+ BOOST_CHECK_EQUAL(test_output_small.num_cell_records(),
+ test_output_large.num_cell_records());
+ BOOST_CHECK_EQUAL(test_output_small.num_vertex_records(),
+ test_output_large.num_vertex_records());
+ BOOST_CHECK_EQUAL(test_output_small.num_edge_records(),
+ test_output_large.num_edge_records());
point_vec_small.clear();
point_vec_large.clear();
}
@@ -468,196 +457,192 @@
#ifdef NDEBUG
BOOST_AUTO_TEST_CASE_TEMPLATE(enormous_random_test, T, test_types) {
srand(static_cast<unsigned int>(time(NULL)));
- voronoi_builder<T> test_builder;
- voronoi_output_clipped<T> test_output;
+ voronoi_output<T> test_output;
std::vector< point_2d<T> > point_vec;
for (int i = 0; i < 1000000; i++)
point_vec.push_back(make_point_2d<T>(rand() % 10000 - 5000, rand() % 10000 - 5000));
- test_builder.init(point_vec);
- test_builder.run_sweepline();
- test_builder.clip(test_output);
+ build_voronoi(point_vec, test_output);
VERIFY_VORONOI_OUTPUT(test_output, FAST_VERIFICATION);
}
#endif
-
-BOOST_AUTO_TEST_CASE_TEMPLATE(segment_sites_test1, T, test_types) {
- typedef T coordinate_type;
- voronoi_builder<coordinate_type> test_builder;
- voronoi_output_clipped<coordinate_type> test_output;
- std::vector< typename voronoi_builder<coordinate_type>::Segment2D > segm_vec;
- point_2d<T> point1 = make_point_2d<T>(0, 0);
- point_2d<T> point2 = make_point_2d<T>(1, 1);
- segm_vec.push_back(std::make_pair< point_2d<T>, point_2d<T> >(point1, point2));
- test_builder.init(segm_vec);
- test_builder.run_sweepline();
- test_builder.clip(test_output);
- BOOST_CHECK_EQUAL(test_output.num_cell_records, 3);
- BOOST_CHECK_EQUAL(test_output.num_vertex_records, 0);
- BOOST_CHECK_EQUAL(test_output.num_edge_records, 2);
- VERIFY_VORONOI_OUTPUT(test_output, NO_HALF_EDGE_INTERSECTIONS);
-}
-
-BOOST_AUTO_TEST_CASE_TEMPLATE(segment_sites_test2, T, test_types) {
- typedef T coordinate_type;
- voronoi_builder<coordinate_type> test_builder;
- voronoi_output_clipped<coordinate_type> test_output;
- std::vector< point_2d<T> > point_vec;
- std::vector< typename voronoi_builder<coordinate_type>::Segment2D > segm_vec;
- point_2d<T> point1 = make_point_2d<T>(0, 0);
- point_2d<T> point2 = make_point_2d<T>(4, 4);
- point_2d<T> point3 = make_point_2d<T>(3, 1);
- point_2d<T> point4 = make_point_2d<T>(1, 3);
- segm_vec.push_back(std::make_pair< point_2d<T>, point_2d<T> >(point1, point2));
- point_vec.push_back(point3);
- point_vec.push_back(point4);
- test_builder.init(point_vec, segm_vec);
- test_builder.run_sweepline();
- test_builder.clip(test_output);
- BOOST_CHECK_EQUAL(test_output.num_cell_records, 5);
- BOOST_CHECK_EQUAL(test_output.num_vertex_records, 4);
- BOOST_CHECK_EQUAL(test_output.num_edge_records, 8);
- VERIFY_VORONOI_OUTPUT(test_output, NO_HALF_EDGE_INTERSECTIONS);
-}
-
-BOOST_AUTO_TEST_CASE_TEMPLATE(segment_sites_test3, T, test_types) {
- typedef T coordinate_type;
- voronoi_builder<coordinate_type> test_builder;
- voronoi_output_clipped<coordinate_type> test_output;
- std::vector< point_2d<T> > point_vec;
- std::vector< typename voronoi_builder<coordinate_type>::Segment2D > segm_vec;
- point_2d<T> point1 = make_point_2d<T>(4, 0);
- point_2d<T> point2 = make_point_2d<T>(0, 4);
- point_2d<T> point3 = make_point_2d<T>(3, 3);
- point_2d<T> point4 = make_point_2d<T>(1, 1);
- segm_vec.push_back(std::make_pair< point_2d<T>, point_2d<T> >(point1, point2));
- point_vec.push_back(point3);
- point_vec.push_back(point4);
- test_builder.init(point_vec, segm_vec);
- test_builder.run_sweepline();
- test_builder.clip(test_output);
- BOOST_CHECK_EQUAL(test_output.num_cell_records, 5);
- BOOST_CHECK_EQUAL(test_output.num_vertex_records, 4);
- BOOST_CHECK_EQUAL(test_output.num_edge_records, 8);
- VERIFY_VORONOI_OUTPUT(test_output, NO_HALF_EDGE_INTERSECTIONS);
-}
-
-BOOST_AUTO_TEST_CASE_TEMPLATE(segment_sites_test4, T, test_types) {
- typedef T coordinate_type;
- voronoi_builder<coordinate_type> test_builder;
- voronoi_output_clipped<coordinate_type> test_output;
- std::vector< point_2d<T> > point_vec;
- std::vector< typename voronoi_builder<coordinate_type>::Segment2D > segm_vec;
- point_2d<T> point1 = make_point_2d<T>(4, 0);
- point_2d<T> point2 = make_point_2d<T>(0, 4);
- point_2d<T> point3 = make_point_2d<T>(3, 2);
- point_2d<T> point4 = make_point_2d<T>(2, 3);
- segm_vec.push_back(std::make_pair< point_2d<T>, point_2d<T> >(point1, point2));
- point_vec.push_back(point3);
- point_vec.push_back(point4);
- test_builder.init(point_vec, segm_vec);
- test_builder.run_sweepline();
- test_builder.clip(test_output);
- BOOST_CHECK_EQUAL(test_output.num_cell_records, 5);
- BOOST_CHECK_EQUAL(test_output.num_vertex_records, 3);
- BOOST_CHECK_EQUAL(test_output.num_edge_records, 7);
- VERIFY_VORONOI_OUTPUT(test_output, NO_HALF_EDGE_INTERSECTIONS);
-}
-
-BOOST_AUTO_TEST_CASE_TEMPLATE(segment_site_test5, T, test_types) {
- typedef T coordinate_type;
- voronoi_builder<coordinate_type> test_builder;
- voronoi_output_clipped<coordinate_type> test_output;
- std::vector< point_2d<T> > point_vec;
- std::vector< typename voronoi_builder<coordinate_type>::Segment2D > segm_vec;
- point_2d<T> point1 = make_point_2d<T>(0, 0);
- point_2d<T> point2 = make_point_2d<T>(0, 8);
- point_2d<T> point3 = make_point_2d<T>(-2, -2);
- point_2d<T> point4 = make_point_2d<T>(-2, 4);
- point_2d<T> point5 = make_point_2d<T>(-2, 10);
- segm_vec.push_back(std::make_pair< point_2d<T>, point_2d<T> >(point1, point2));
- point_vec.push_back(point3);
- point_vec.push_back(point4);
- point_vec.push_back(point5);
- test_builder.init(point_vec, segm_vec);
- test_builder.run_sweepline();
- test_builder.clip(test_output);
- BOOST_CHECK_EQUAL(test_output.num_cell_records, 6);
- BOOST_CHECK_EQUAL(test_output.num_vertex_records, 4);
- BOOST_CHECK_EQUAL(test_output.num_edge_records, 9);
- VERIFY_VORONOI_OUTPUT(test_output, NO_HALF_EDGE_INTERSECTIONS);
-}
-
-BOOST_AUTO_TEST_CASE_TEMPLATE(segment_site_test6, T, test_types) {
- typedef T coordinate_type;
- voronoi_builder<coordinate_type> test_builder;
- voronoi_output_clipped<coordinate_type> test_output;
- std::vector< point_2d<T> > point_vec;
- std::vector< typename voronoi_builder<coordinate_type>::Segment2D > segm_vec;
- point_2d<T> point1 = make_point_2d<T>(-1, 1);
- point_2d<T> point2 = make_point_2d<T>(1, 0);
- point_2d<T> point3 = make_point_2d<T>(1, 2);
- segm_vec.push_back(std::make_pair< point_2d<T>, point_2d<T> >(point2, point3));
- point_vec.push_back(point1);
- test_builder.init(point_vec, segm_vec);
- test_builder.run_sweepline();
- test_builder.clip(test_output);
- BOOST_CHECK_EQUAL(test_output.num_cell_records, 4);
- BOOST_CHECK_EQUAL(test_output.num_vertex_records, 2);
- BOOST_CHECK_EQUAL(test_output.num_edge_records, 5);
- VERIFY_VORONOI_OUTPUT(test_output, NO_HALF_EDGE_INTERSECTIONS);
-}
-
-BOOST_AUTO_TEST_CASE_TEMPLATE(segment_site_test7, T, test_types) {
- typedef T coordinate_type;
- voronoi_builder<coordinate_type> test_builder;
- voronoi_output_clipped<coordinate_type> test_output;
- std::vector< point_2d<T> > point_vec;
- std::vector< typename voronoi_builder<coordinate_type>::Segment2D > segm_vec;
- point_2d<T> point1 = make_point_2d<T>(0, 0);
- point_2d<T> point2 = make_point_2d<T>(4, 0);
- point_2d<T> point3 = make_point_2d<T>(0, 4);
- point_2d<T> point4 = make_point_2d<T>(4, 4);
- segm_vec.push_back(std::make_pair(point1, point2));
- segm_vec.push_back(std::make_pair(point2, point3));
- segm_vec.push_back(std::make_pair(point3, point4));
- test_builder.init(segm_vec);
- test_builder.run_sweepline();
- test_builder.clip(test_output);
- BOOST_CHECK_EQUAL(test_output.num_cell_records, 7);
- BOOST_CHECK_EQUAL(test_output.num_vertex_records, 6);
- BOOST_CHECK_EQUAL(test_output.num_edge_records, 12);
- VERIFY_VORONOI_OUTPUT(test_output, NO_HALF_EDGE_INTERSECTIONS);
-
-}
-
-BOOST_AUTO_TEST_CASE_TEMPLATE(segment_site_test8, T, test_types) {
- typedef T coordinate_type;
- voronoi_builder<coordinate_type> test_builder;
- voronoi_output_clipped<coordinate_type> test_output;
- std::vector< point_2d<T> > point_vec;
- std::vector< typename voronoi_builder<coordinate_type>::Segment2D > segm_vec;
- point_2d<T> point1 = make_point_2d<T>(0, 0);
- point_2d<T> point2 = make_point_2d<T>(4, 0);
- point_2d<T> point3 = make_point_2d<T>(4, 4);
- point_2d<T> point4 = make_point_2d<T>(0, 4);
- segm_vec.push_back(std::make_pair(point1, point2));
- segm_vec.push_back(std::make_pair(point2, point3));
- segm_vec.push_back(std::make_pair(point3, point4));
- segm_vec.push_back(std::make_pair(point4, point1));
- test_builder.init(segm_vec);
- test_builder.run_sweepline();
- test_builder.clip(test_output);
- BOOST_CHECK_EQUAL(test_output.num_cell_records, 8);
- BOOST_CHECK_EQUAL(test_output.num_vertex_records, 5);
- BOOST_CHECK_EQUAL(test_output.num_edge_records, 12);
- VERIFY_VORONOI_OUTPUT(test_output, NO_HALF_EDGE_INTERSECTIONS);
-}
+//
+//BOOST_AUTO_TEST_CASE_TEMPLATE(segment_sites_test1, T, test_types) {
+// typedef T coordinate_type;
+// voronoi_builder<coordinate_type> test_builder;
+// voronoi_output_clipped<coordinate_type> test_output;
+// std::vector< typename voronoi_builder<coordinate_type>::Segment2D > segm_vec;
+// point_2d<T> point1 = make_point_2d<T>(0, 0);
+// point_2d<T> point2 = make_point_2d<T>(1, 1);
+// segm_vec.push_back(std::make_pair< point_2d<T>, point_2d<T> >(point1, point2));
+// test_builder.init(segm_vec);
+// test_builder.run_sweepline();
+// test_builder.clip(test_output);
+// BOOST_CHECK_EQUAL(test_output.num_cell_records, 3);
+// BOOST_CHECK_EQUAL(test_output.num_vertex_records, 0);
+// BOOST_CHECK_EQUAL(test_output.num_edge_records, 2);
+// VERIFY_VORONOI_OUTPUT(test_output, NO_HALF_EDGE_INTERSECTIONS);
+//}
+//
+//BOOST_AUTO_TEST_CASE_TEMPLATE(segment_sites_test2, T, test_types) {
+// typedef T coordinate_type;
+// voronoi_builder<coordinate_type> test_builder;
+// voronoi_output_clipped<coordinate_type> test_output;
+// std::vector< point_2d<T> > point_vec;
+// std::vector< typename voronoi_builder<coordinate_type>::Segment2D > segm_vec;
+// point_2d<T> point1 = make_point_2d<T>(0, 0);
+// point_2d<T> point2 = make_point_2d<T>(4, 4);
+// point_2d<T> point3 = make_point_2d<T>(3, 1);
+// point_2d<T> point4 = make_point_2d<T>(1, 3);
+// segm_vec.push_back(std::make_pair< point_2d<T>, point_2d<T> >(point1, point2));
+// point_vec.push_back(point3);
+// point_vec.push_back(point4);
+// test_builder.init(point_vec, segm_vec);
+// test_builder.run_sweepline();
+// test_builder.clip(test_output);
+// BOOST_CHECK_EQUAL(test_output.num_cell_records, 5);
+// BOOST_CHECK_EQUAL(test_output.num_vertex_records, 4);
+// BOOST_CHECK_EQUAL(test_output.num_edge_records, 8);
+// VERIFY_VORONOI_OUTPUT(test_output, NO_HALF_EDGE_INTERSECTIONS);
+//}
+//
+//BOOST_AUTO_TEST_CASE_TEMPLATE(segment_sites_test3, T, test_types) {
+// typedef T coordinate_type;
+// voronoi_builder<coordinate_type> test_builder;
+// voronoi_output_clipped<coordinate_type> test_output;
+// std::vector< point_2d<T> > point_vec;
+// std::vector< typename voronoi_builder<coordinate_type>::Segment2D > segm_vec;
+// point_2d<T> point1 = make_point_2d<T>(4, 0);
+// point_2d<T> point2 = make_point_2d<T>(0, 4);
+// point_2d<T> point3 = make_point_2d<T>(3, 3);
+// point_2d<T> point4 = make_point_2d<T>(1, 1);
+// segm_vec.push_back(std::make_pair< point_2d<T>, point_2d<T> >(point1, point2));
+// point_vec.push_back(point3);
+// point_vec.push_back(point4);
+// test_builder.init(point_vec, segm_vec);
+// test_builder.run_sweepline();
+// test_builder.clip(test_output);
+// BOOST_CHECK_EQUAL(test_output.num_cell_records, 5);
+// BOOST_CHECK_EQUAL(test_output.num_vertex_records, 4);
+// BOOST_CHECK_EQUAL(test_output.num_edge_records, 8);
+// VERIFY_VORONOI_OUTPUT(test_output, NO_HALF_EDGE_INTERSECTIONS);
+//}
+//
+//BOOST_AUTO_TEST_CASE_TEMPLATE(segment_sites_test4, T, test_types) {
+// typedef T coordinate_type;
+// voronoi_builder<coordinate_type> test_builder;
+// voronoi_output_clipped<coordinate_type> test_output;
+// std::vector< point_2d<T> > point_vec;
+// std::vector< typename voronoi_builder<coordinate_type>::Segment2D > segm_vec;
+// point_2d<T> point1 = make_point_2d<T>(4, 0);
+// point_2d<T> point2 = make_point_2d<T>(0, 4);
+// point_2d<T> point3 = make_point_2d<T>(3, 2);
+// point_2d<T> point4 = make_point_2d<T>(2, 3);
+// segm_vec.push_back(std::make_pair< point_2d<T>, point_2d<T> >(point1, point2));
+// point_vec.push_back(point3);
+// point_vec.push_back(point4);
+// test_builder.init(point_vec, segm_vec);
+// test_builder.run_sweepline();
+// test_builder.clip(test_output);
+// BOOST_CHECK_EQUAL(test_output.num_cell_records, 5);
+// BOOST_CHECK_EQUAL(test_output.num_vertex_records, 3);
+// BOOST_CHECK_EQUAL(test_output.num_edge_records, 7);
+// VERIFY_VORONOI_OUTPUT(test_output, NO_HALF_EDGE_INTERSECTIONS);
+//}
+//
+//BOOST_AUTO_TEST_CASE_TEMPLATE(segment_site_test5, T, test_types) {
+// typedef T coordinate_type;
+// voronoi_builder<coordinate_type> test_builder;
+// voronoi_output_clipped<coordinate_type> test_output;
+// std::vector< point_2d<T> > point_vec;
+// std::vector< typename voronoi_builder<coordinate_type>::Segment2D > segm_vec;
+// point_2d<T> point1 = make_point_2d<T>(0, 0);
+// point_2d<T> point2 = make_point_2d<T>(0, 8);
+// point_2d<T> point3 = make_point_2d<T>(-2, -2);
+// point_2d<T> point4 = make_point_2d<T>(-2, 4);
+// point_2d<T> point5 = make_point_2d<T>(-2, 10);
+// segm_vec.push_back(std::make_pair< point_2d<T>, point_2d<T> >(point1, point2));
+// point_vec.push_back(point3);
+// point_vec.push_back(point4);
+// point_vec.push_back(point5);
+// test_builder.init(point_vec, segm_vec);
+// test_builder.run_sweepline();
+// test_builder.clip(test_output);
+// BOOST_CHECK_EQUAL(test_output.num_cell_records, 6);
+// BOOST_CHECK_EQUAL(test_output.num_vertex_records, 4);
+// BOOST_CHECK_EQUAL(test_output.num_edge_records, 9);
+// VERIFY_VORONOI_OUTPUT(test_output, NO_HALF_EDGE_INTERSECTIONS);
+//}
+//
+//BOOST_AUTO_TEST_CASE_TEMPLATE(segment_site_test6, T, test_types) {
+// typedef T coordinate_type;
+// voronoi_builder<coordinate_type> test_builder;
+// voronoi_output_clipped<coordinate_type> test_output;
+// std::vector< point_2d<T> > point_vec;
+// std::vector< typename voronoi_builder<coordinate_type>::Segment2D > segm_vec;
+// point_2d<T> point1 = make_point_2d<T>(-1, 1);
+// point_2d<T> point2 = make_point_2d<T>(1, 0);
+// point_2d<T> point3 = make_point_2d<T>(1, 2);
+// segm_vec.push_back(std::make_pair< point_2d<T>, point_2d<T> >(point2, point3));
+// point_vec.push_back(point1);
+// test_builder.init(point_vec, segm_vec);
+// test_builder.run_sweepline();
+// test_builder.clip(test_output);
+// BOOST_CHECK_EQUAL(test_output.num_cell_records, 4);
+// BOOST_CHECK_EQUAL(test_output.num_vertex_records, 2);
+// BOOST_CHECK_EQUAL(test_output.num_edge_records, 5);
+// VERIFY_VORONOI_OUTPUT(test_output, NO_HALF_EDGE_INTERSECTIONS);
+//}
+//
+//BOOST_AUTO_TEST_CASE_TEMPLATE(segment_site_test7, T, test_types) {
+// typedef T coordinate_type;
+// voronoi_builder<coordinate_type> test_builder;
+// voronoi_output_clipped<coordinate_type> test_output;
+// std::vector< point_2d<T> > point_vec;
+// std::vector< typename voronoi_builder<coordinate_type>::Segment2D > segm_vec;
+// point_2d<T> point1 = make_point_2d<T>(0, 0);
+// point_2d<T> point2 = make_point_2d<T>(4, 0);
+// point_2d<T> point3 = make_point_2d<T>(0, 4);
+// point_2d<T> point4 = make_point_2d<T>(4, 4);
+// segm_vec.push_back(std::make_pair(point1, point2));
+// segm_vec.push_back(std::make_pair(point2, point3));
+// segm_vec.push_back(std::make_pair(point3, point4));
+// test_builder.init(segm_vec);
+// test_builder.run_sweepline();
+// test_builder.clip(test_output);
+// BOOST_CHECK_EQUAL(test_output.num_cell_records, 7);
+// BOOST_CHECK_EQUAL(test_output.num_vertex_records, 6);
+// BOOST_CHECK_EQUAL(test_output.num_edge_records, 12);
+// VERIFY_VORONOI_OUTPUT(test_output, NO_HALF_EDGE_INTERSECTIONS);
+//
+//}
+//
+//BOOST_AUTO_TEST_CASE_TEMPLATE(segment_site_test8, T, test_types) {
+// typedef T coordinate_type;
+// voronoi_builder<coordinate_type> test_builder;
+// voronoi_output_clipped<coordinate_type> test_output;
+// std::vector< point_2d<T> > point_vec;
+// std::vector< typename voronoi_builder<coordinate_type>::Segment2D > segm_vec;
+// point_2d<T> point1 = make_point_2d<T>(0, 0);
+// point_2d<T> point2 = make_point_2d<T>(4, 0);
+// point_2d<T> point3 = make_point_2d<T>(4, 4);
+// point_2d<T> point4 = make_point_2d<T>(0, 4);
+// segm_vec.push_back(std::make_pair(point1, point2));
+// segm_vec.push_back(std::make_pair(point2, point3));
+// segm_vec.push_back(std::make_pair(point3, point4));
+// segm_vec.push_back(std::make_pair(point4, point1));
+// test_builder.init(segm_vec);
+// test_builder.run_sweepline();
+// test_builder.clip(test_output);
+// BOOST_CHECK_EQUAL(test_output.num_cell_records, 8);
+// BOOST_CHECK_EQUAL(test_output.num_vertex_records, 5);
+// BOOST_CHECK_EQUAL(test_output.num_edge_records, 12);
+// VERIFY_VORONOI_OUTPUT(test_output, NO_HALF_EDGE_INTERSECTIONS);
+//}
#ifdef NDEBUG
BOOST_AUTO_TEST_CASE_TEMPLATE(segment_grid_test, T, test_types) {
- voronoi_builder<T> test_builder;
- voronoi_output_clipped<T> test_output_small, test_output_large;
- std::vector< typename voronoi_builder<T>::Segment2D > segm_vec_small, segm_vec_large;
+ voronoi_output<T> test_output_small, test_output_large;
+ std::vector< std::pair< point_2d<T>, point_2d<T> > > segm_vec_small, segm_vec_large;
int grid_size[4] = {10, 33, 100, 333};
int max_value[4] = {100, 330, 1000, 3330};
int array_length = sizeof(grid_size) / sizeof(int);
@@ -679,17 +664,16 @@
segm_vec_small.push_back(std::make_pair(point3_1, point4_1));
segm_vec_large.push_back(std::make_pair(point3_2, point4_2));
}
- test_builder.init(segm_vec_small);
- test_builder.run_sweepline();
- test_builder.clip(test_output_small);
- test_builder.init(segm_vec_large);
- test_builder.run_sweepline();
- test_builder.clip(test_output_large);
+ build_voronoi(segm_vec_small, test_output_small);
+ build_voronoi(segm_vec_large, test_output_large);
VERIFY_VORONOI_OUTPUT(test_output_small, NO_HALF_EDGE_INTERSECTIONS);
VERIFY_VORONOI_OUTPUT(test_output_large, NO_HALF_EDGE_INTERSECTIONS);
- BOOST_CHECK_EQUAL(test_output_small.num_cell_records, test_output_large.num_cell_records);
- BOOST_CHECK_EQUAL(test_output_small.num_vertex_records, test_output_large.num_vertex_records);
- BOOST_CHECK_EQUAL(test_output_small.num_edge_records, test_output_large.num_edge_records);
+ BOOST_CHECK_EQUAL(test_output_small.num_cell_records(),
+ test_output_large.num_cell_records());
+ BOOST_CHECK_EQUAL(test_output_small.num_vertex_records(),
+ test_output_large.num_vertex_records());
+ BOOST_CHECK_EQUAL(test_output_small.num_edge_records(),
+ test_output_large.num_edge_records());
segm_vec_small.clear();
segm_vec_large.clear();
}
@@ -699,14 +683,13 @@
#ifdef NDEBUG
BOOST_AUTO_TEST_CASE_TEMPLATE(segment_random_test, T, test_types) {
srand(static_cast<unsigned int>(time(NULL)));
- voronoi_builder<T> test_builder;
- voronoi_output_clipped<T> test_output_small, test_output_large;
- std::vector< typename voronoi_builder<T>::Segment2D > segm_vec;
+ voronoi_output<T> test_output_small, test_output_large;
+ std::vector< std::pair< point_2d<T>, point_2d<T> > > segm_vec;
int num_segments[] = {10, 100, 1000, 10000, 100000};
int num_runs[] = {10000, 1000, 100, 10, 1};
- int mod_koef1[] = {10, 100, 100, 10000, 10000};
+ int mod_koef1[] = {10, 100, 100, 1000, 4000};
int mod_koef2[] = {10, 100, 100, 100, 100};
- int max_value[] = {10, 100, 100, 5050, 5050};
+ int max_value[] = {10, 100, 100, 550, 2050};
int array_length = sizeof(num_segments) / sizeof(int);
for (int k = 0; k < array_length; k++) {
int koef = std::numeric_limits<int>::max() / max_value[k];
@@ -726,23 +709,22 @@
segm_vec.push_back(std::make_pair(point1_small, point2_small));
}
remove_intersections(segm_vec);
- test_builder.init(segm_vec);
- test_builder.run_sweepline();
- test_builder.clip(test_output_small);
+ build_voronoi(segm_vec, test_output_small);
for (size_t j = 0; j < segm_vec.size(); j++) {
segm_vec[j].first.x(segm_vec[j].first.x() * koef);
segm_vec[j].first.y(segm_vec[j].first.y() * koef);
segm_vec[j].second.x(segm_vec[j].second.x() * koef);
segm_vec[j].second.y(segm_vec[j].second.y() * koef);
}
- test_builder.init(segm_vec);
- test_builder.run_sweepline();
- test_builder.clip(test_output_large);
+ build_voronoi(segm_vec, test_output_large);
VERIFY_VORONOI_OUTPUT(test_output_small, NO_HALF_EDGE_INTERSECTIONS);
VERIFY_VORONOI_OUTPUT(test_output_large, NO_HALF_EDGE_INTERSECTIONS);
- BOOST_CHECK_EQUAL(test_output_small.num_cell_records, test_output_large.num_cell_records);
- BOOST_CHECK_EQUAL(test_output_small.num_vertex_records, test_output_large.num_vertex_records);
- BOOST_CHECK_EQUAL(test_output_small.num_edge_records, test_output_large.num_edge_records);
+ BOOST_CHECK_EQUAL(test_output_small.num_cell_records(),
+ test_output_large.num_cell_records());
+ BOOST_CHECK_EQUAL(test_output_small.num_vertex_records(),
+ test_output_large.num_vertex_records());
+ BOOST_CHECK_EQUAL(test_output_small.num_edge_records(),
+ test_output_large.num_edge_records());
segm_vec.clear();
}
}
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