|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r63407 - in sandbox/SOC/2010/sweepline: boost/sweepline boost/sweepline/detail libs/sweepline/test
From: sydorchuk.andriy_at_[hidden]
Date: 2010-06-28 11:04:39
Author: asydorchuk
Date: 2010-06-28 11:04:37 EDT (Mon, 28 Jun 2010)
New Revision: 63407
URL: http://svn.boost.org/trac/boost/changeset/63407
Log:
Fixed errors and compile warnings using gcc-3.4.4 and gcc-4.3.4 compilers.
Added output post processing (removing zero length edges).
Updated output structure, moved output from detail namespace.
Updated unit tests for voronoi builder.
Added:
sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_output.hpp (contents, props changed)
Text files modified:
sandbox/SOC/2010/sweepline/boost/sweepline/detail/voronoi_formation.hpp | 384 +++++++--------------------------------
sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_builder.hpp | 105 +++++-----
sandbox/SOC/2010/sweepline/libs/sweepline/test/Jamfile.v2 | 8
sandbox/SOC/2010/sweepline/libs/sweepline/test/event_queue_test.cpp | 30 +-
sandbox/SOC/2010/sweepline/libs/sweepline/test/event_types_test.cpp | 86 ++++----
sandbox/SOC/2010/sweepline/libs/sweepline/test/node_comparer_test.cpp | 133 +++++++------
sandbox/SOC/2010/sweepline/libs/sweepline/test/test_type_list.hpp | 6
sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_builder_test.cpp | 232 ++++++++++++++---------
8 files changed, 403 insertions(+), 581 deletions(-)
Modified: sandbox/SOC/2010/sweepline/boost/sweepline/detail/voronoi_formation.hpp
==============================================================================
--- sandbox/SOC/2010/sweepline/boost/sweepline/detail/voronoi_formation.hpp (original)
+++ sandbox/SOC/2010/sweepline/boost/sweepline/detail/voronoi_formation.hpp 2010-06-28 11:04:37 EDT (Mon, 28 Jun 2010)
@@ -23,12 +23,6 @@
// VORONOI EVENT TYPES ////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////
- template <typename T>
- struct site_event;
-
- template <typename T>
- struct circle_event;
-
template <typename Point2D>
struct beach_line_node;
@@ -38,87 +32,21 @@
template <typename BeachLineNode>
struct node_comparer;
- // Point in 2D space data structure. Comparators defined in this
- // data structure actually define sweepline movement direction.
- template <typename T>
- struct point_2d {
- public:
- typedef T coordinate_type;
- typedef site_event<T> site_event_type;
- typedef circle_event<T> circle_event_type;
-
- point_2d() {}
-
- point_2d(T x, T y) {
- x_ = x;
- y_ = y;
- }
-
- bool operator==(const point_2d &point) const {
- return (this->x_ == point.x()) && (this->y_ == point.y());
- }
-
- bool operator!=(const point_2d &point) const {
- return (this->x_ != point.x()) || (this->y_ != point.y());
- }
-
- // This comparator actually defines sweepline movement direction.
- bool operator<(const point_2d &point) const {
- // Sweepline sweeps from left to right.
- if (this->x_ != point.x_)
- return this->x_ < point.x_;
- return this->y_ < point.y_;
- }
-
- bool operator<=(const point_2d &point) const {
- return !(point < (*this));
- }
-
- bool operator>(const point_2d &point) const {
- return point < (*this);
- }
-
- bool operator>=(const point_2d &point) const {
- return !((*this) < point);
- }
-
- coordinate_type x() const {
- return this->x_;
- }
-
- coordinate_type y() const {
- return this->y_;
- }
-
- void x(coordinate_type x) {
- x_ = x;
- }
-
- void y(coordinate_type y) {
- y_ = y;
- }
-
- private:
- coordinate_type x_;
- coordinate_type y_;
- };
-
- template <typename T>
- point_2d<T> make_point_2d(T x, T y) {
- return point_2d<T>(x,y);
- }
-
// Site event type.
// Occurs when sweepline sweeps over one of the initial sites.
// Contains index of a site below the other sorted sites.
- template <typename T>
+ template <typename Point2D>
struct site_event {
public:
- typedef T coordinate_type;
+ typedef typename Point2D::coordinate_type coordinate_type;
site_event() {}
- site_event(T x, T y, int index) : point_(x, y), site_index_(index) {}
+ site_event(coordinate_type x, coordinate_type y, int index) :
+ point_(x, y), site_index_(index) {}
+
+ site_event(const Point2D &point, int index) :
+ point_(point), site_index_(index) {}
bool operator==(const site_event &s_event) const {
return point_ == s_event.get_point();
@@ -152,7 +80,7 @@
return point_.y();
}
- const point_2d<T> &get_point() const {
+ const Point2D &get_point() const {
return point_;
}
@@ -161,13 +89,20 @@
}
private:
- point_2d<T> point_;
+ Point2D point_;
int site_index_;
};
- template <typename T>
- site_event<T> make_site_event(T x, T y, int index) {
- return site_event<T>(x, y, index);
+ template <typename Point2D>
+ site_event<Point2D> make_site_event(typename Point2D::coordinate_type x,
+ typename Point2D::coordinate_type y,
+ int index) {
+ return site_event<Point2D>(x, y, index);
+ }
+
+ template <typename Point2D>
+ site_event<Point2D> make_site_event(const Point2D &point, int index) {
+ return site_event<Point2D>(point, index);
}
// Circle event type. Occurs when sweepline sweeps over the bottom point of
@@ -180,19 +115,22 @@
// Bottom point of the voronoi circle will be defined as (x + sqrt(r), y).
// Contains reference to the second bisector node (ordered from left to
// right in the beach line) that creates given circle event.
- template <typename T>
+ template <typename Point2D>
struct circle_event {
public:
- typedef T coordinate_type;
- typedef typename beach_line_node< point_2d<T> > Key;
- typedef typename beach_line_node_data< point_2d<T> > Value;
- typedef typename node_comparer<Key> NodeComparer;
- typedef typename std::map< Key, Value, NodeComparer >::const_iterator beach_line_iterator;
+ typedef typename Point2D::coordinate_type coordinate_type;
+ typedef beach_line_node<Point2D> Key;
+ typedef beach_line_node_data<typename Point2D::Edge> Value;
+ typedef node_comparer<Key> NodeComparer;
+ typedef typename std::map< Key, Value, NodeComparer >::iterator beach_line_iterator;
circle_event() {}
- circle_event(T c_x, T c_y, T sqr_r) :
- center_(c_x, c_y), sqr_radius_(sqr_r) {}
+ circle_event(coordinate_type c_x, coordinate_type c_y, coordinate_type sqr_r) :
+ center_(c_x, c_y), sqr_radius_(sqr_r) {}
+
+ circle_event(const Point2D ¢er, coordinate_type sqr_r) :
+ center_(center), sqr_radius_(sqr_r) {}
circle_event(const circle_event& c_event) {
center_ = c_event.center_;
@@ -227,11 +165,11 @@
if (center_.y() != c_event.y())
return false;
- T sqr_dif_x = (center_.x() - c_event.x()) *
- (center_.x() - c_event.x());
- T sum_r_sqr = sqr_radius_ + c_event.sqr_radius_;
- T value_left = (sum_r_sqr - sqr_dif_x) * (sum_r_sqr - sqr_dif_x);
- T value_right = static_cast<T>(4) * sqr_radius_ *
+ coordinate_type sqr_dif_x = (center_.x() - c_event.x()) *
+ (center_.x() - c_event.x());
+ coordinate_type sum_r_sqr = sqr_radius_ + c_event.sqr_radius_;
+ coordinate_type value_left = (sum_r_sqr - sqr_dif_x) * (sum_r_sqr - sqr_dif_x);
+ coordinate_type value_right = static_cast<coordinate_type>(4) * sqr_radius_ *
c_event.sqr_radius_;
return value_left == value_right;
@@ -242,17 +180,17 @@
}
bool operator<(const circle_event &c_event) const {
- T x1 = center_.x();
- T y1 = center_.y();
- T sqr_r1 = sqr_radius_;
- T x2 = c_event.x();
- T y2 = c_event.y();
- T sqr_r2 = c_event.get_sqr_radius();
-
- T sqr_dif_x = (x1 - x2) * (x1 - x2);
- T sum_r_sqr = sqr_r1 + sqr_r2;
- T value_left = (sum_r_sqr - sqr_dif_x) * (sum_r_sqr - sqr_dif_x);
- T value_right = static_cast<T>(4) * sqr_r1 * sqr_r2;
+ coordinate_type x1 = center_.x();
+ coordinate_type y1 = center_.y();
+ coordinate_type sqr_r1 = sqr_radius_;
+ coordinate_type x2 = c_event.x();
+ coordinate_type y2 = c_event.y();
+ coordinate_type sqr_r2 = c_event.get_sqr_radius();
+
+ coordinate_type sqr_dif_x = (x1 - x2) * (x1 - x2);
+ coordinate_type sum_r_sqr = sqr_r1 + sqr_r2;
+ coordinate_type value_left = (sum_r_sqr - sqr_dif_x) * (sum_r_sqr - sqr_dif_x);
+ coordinate_type value_right = static_cast<coordinate_type>(4) * sqr_r1 * sqr_r2;
if (x1 > x2) {
if (sqr_r2 <= sqr_r1)
@@ -329,10 +267,10 @@
// If circle point is less then site point return -1.
// If circle point is equal to site point return 0.
// If circle point is greater then site point return 1.
- int compare(const site_event<T> &s_event) const {
+ int compare(const site_event<Point2D> &s_event) const {
if (s_event.x() < center_.x())
return 1;
- T sqr_dif_x = (s_event.x() - center_.x()) * (s_event.x() - center_.x());
+ coordinate_type sqr_dif_x = (s_event.x() - center_.x()) * (s_event.x() - center_.x());
if (sqr_dif_x == sqr_radius_) {
if (center_.y() == s_event.y())
return 0;
@@ -349,11 +287,11 @@
return center_.y();
}
- const point_2d<T> &get_center() const {
+ const Point2D &get_center() const {
return center_;
}
- const T &get_sqr_radius() const {
+ const coordinate_type &get_sqr_radius() const {
return sqr_radius_;
}
@@ -361,9 +299,9 @@
bisector_node_ = iterator;
}
- void set_sites(const site_event<T> site1,
- const site_event<T> site2,
- const site_event<T> site3) {
+ void set_sites(const site_event<Point2D> site1,
+ const site_event<Point2D> site2,
+ const site_event<Point2D> site3) {
sites_[0] = site1;
sites_[1] = site2;
sites_[2] = site3;
@@ -373,209 +311,30 @@
return bisector_node_;
}
- const site_event<T>* get_sites() const {
+ const site_event<Point2D>* get_sites() const {
return sites_;
}
private:
- point_2d<T> center_;
- T sqr_radius_;
+ Point2D center_;
+ coordinate_type sqr_radius_;
beach_line_iterator bisector_node_;
- site_event<T> sites_[3];
- };
-
- template <typename T>
- circle_event<T> make_circle_event(T center_x, T center_y, T sqr_radius) {
- return circle_event<T>(center_x, center_y, sqr_radius);
- }
-
- ///////////////////////////////////////////////////////////////////////////
- // VORONOI OUTPUT TYPES ///////////////////////////////////////////////////
- ///////////////////////////////////////////////////////////////////////////
-
- template <typename Point2D>
- struct half_edge;
-
- // Cell record data structure. Represents voronoi cell.
- // Contains site point and pointer to any incident half-edge.
- template <typename Point2D>
- struct cell_record {
- half_edge<Point2D> *incident_edge;
- Point2D site_point;
-
- cell_record(Point2D site, half_edge<Point2D>* edge) : incident_edge(edge), site_point(site) {}
- };
-
- // Voronoi vertex data structure. Represents voronoi vertex.
- // Contains vertex coordinates and pointers to all incident half-edges.
- template <typename Point2D>
- struct vertex_record {
- std::list< half_edge<Point2D>* > incident_edges;
- Point2D vertex;
-
- vertex_record(Point2D vertex) : vertex(vertex) {}
+ site_event<Point2D> sites_[3];
};
- // 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) pointer to twin half-edge.
template <typename Point2D>
- struct half_edge {
- typedef typename cell_record<Point2D> cell_record_type;
- typedef typename vertex_record<Point2D> vertex_record_type;
- typedef typename half_edge<Point2D> half_edge_type;
-
- cell_record_type *cell_record;
- vertex_record_type *start_point;
- vertex_record_type *end_point;
- half_edge_type *prev;
- half_edge_type *next;
- half_edge_type *twin;
-
- half_edge(int site_index) :
- cell_record(NULL),
- start_point(NULL),
- end_point(NULL),
- prev(NULL),
- next(NULL),
- twin(NULL) {}
- };
+ circle_event<Point2D> make_circle_event(
+ typename Point2D::coordinate_type c_x,
+ typename Point2D::coordinate_type c_y,
+ typename Point2D::coordinate_type sqr_radius) {
+ return circle_event<Point2D>(c_x, c_y, sqr_radius);
+ }
- // 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 Point2D>
- class voronoi_output {
- public:
- typedef typename Point2D::site_event_type site_event_type;
- typedef typename Point2D::circle_event_type circle_event_type;
- typedef typename cell_record<Point2D> cell_record_type;
- typedef typename vertex_record<Point2D> vertex_record_type;
- typedef typename half_edge<Point2D> edge_type;
- typedef typename std::vector<cell_record_type> cell_records;
- typedef typename std::list<vertex_record_type> voronoi_vertices;
- typedef typename std::list<edge_type *>::const_iterator edge_iterator;
- typedef typename voronoi_vertices::const_iterator voronoi_vertices_iterator;
-
- voronoi_output() {}
-
- // This preserves the validity of iterators.
- void init(int num_sites) {
- cell_records_.reserve(num_sites);
- }
-
- void reset() {
- cell_records_.clear();
- vertex_records_.clear();
- edges_.clear();
- }
-
- // 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 reference to the new half-edge.
- // Second argument is new site. During this step we add two new
- // twin half-edges.
- edge_type *insert_new_edge(const site_event_type &site1,
- const site_event_type &site2) {
- // Get indexes of sites.
- int site_index1 = site1.get_site_index();
- int site_index2 = site2.get_site_index();
-
- // Create new half-edge that belongs to the cell with the first site.
- edges_.push_back(edge_type(site_index1));
- edge_type &edge1 = edges_.back();
-
- // Create new half-edge that belongs to the cell with the second site.
- edges_.push_back(edge_type(site_index2));
- edge_type &edge2 = edges_.back();
-
- // Add initial cell during first edge insertion.
- if (cell_records_.empty())
- cell_records_.push_back(cell_record_type(site1.get_point(), &edge1));
-
- // Second site represents new site during site event processing.
- // Add new cell to the cell records vector.
- cell_records_.push_back(cell_record_type(site2.get_point(), &edge2));
-
- // Update pointers to cells.
- edge1.cell_record = &cell_records_[site_index1];
- edge2.cell_record = &cell_records_[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 &site2,
- const site_event_type &site3,
- const circle_event_type &circle,
- edge_type *edge12,
- edge_type *edge23) {
- // Add new voronoi vertex as voronoi circle center.
- vertex_records_.push_back(vertex_record_type(circle.get_center()));
- vertex_record_type &new_vertex = vertex_records_.back();
-
- // Update two input bisectors and their twins 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(site1.get_site_index()));
- edge_type &new_edge1 = edges_.back();
- new_edge1.cell_record = &cell_records_[site1.get_site_index()];
- new_edge1.end_point = &new_vertex;
-
- // Add new half-edge.
- edges_.push_back(edge_type(site3.get_site_index()));
- edge_type &new_edge2 = edges_.back();
- new_edge2.cell_record = &cell_records_[site3.get_site_index()];
- new_edge2.start_point = &new_vertex;
-
- // Update twin pointers of the new half-edges.
- new_edge1.twin = &new_edge2;
- new_edge2.twin = &new_edge1;
-
- // 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;
-
- // Update voronoi vertex incident edges pointers.
- new_vertex.incident_edges.push_back(edge12);
- new_vertex.incident_edges.push_back(edge23);
- new_vertex.incident_edges.push_back(&new_edge2);
- return &new_edge1;
- }
-
- const cell_records &get_cell_records() const {
- return cell_records_;
- }
-
- const voronoi_vertices &get_voronoi_vertices() const {
- return vertex_records_;
- }
-
- private:
- std::vector<cell_record_type> cell_records_;
- std::list<vertex_record_type> vertex_records_;
- std::list<edge_type> edges_;
-
- //Disallow copy constructor and operator=
- voronoi_output(const voronoi_output&);
- void operator=(const voronoi_output&);
- };
+ circle_event<Point2D> make_circle_event(Point2D center,
+ typename Point2D::coordinate_type sqr_radius) {
+ return circle_event<Point2D>(center, sqr_radius);
+ }
///////////////////////////////////////////////////////////////////////////
// VORONOI CIRCLE EVENTS QUEUE ////////////////////////////////////////////
@@ -586,7 +345,7 @@
class circle_events_queue {
public:
typedef typename Point2D::coordinate_type coordinate_type;
- typedef typename Point2D::circle_event_type circle_event_type;
+ typedef circle_event<Point2D> circle_event_type;
circle_events_queue() {}
@@ -659,8 +418,7 @@
struct beach_line_node {
public:
typedef typename Point2D::coordinate_type coordinate_type;
- typedef typename Point2D::site_event_type site_event_type;
- typedef typename Point2D::circle_event_type circle_event_type;
+ typedef site_event<Point2D> site_event_type;
beach_line_node() {}
@@ -738,10 +496,8 @@
// Represents edge data sturcture (bisector segment), which is
// associated with beach line node key in the binary search tree.
- template <typename Point2D>
+ template <typename Edge>
struct beach_line_node_data {
- typedef typename half_edge<Point2D> Edge;
-
Edge *edge;
beach_line_node_data(Edge *new_edge) : edge(new_edge) {}
Modified: sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_builder.hpp
==============================================================================
--- sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_builder.hpp (original)
+++ sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_builder.hpp 2010-06-28 11:04:37 EDT (Mon, 28 Jun 2010)
@@ -7,30 +7,29 @@
// See http://www.boost.org for updates, documentation, and revision history.
-#include "detail/voronoi_formation.hpp"
+#include <algorithm>
+
+#include "voronoi_output.hpp"
#ifndef BOOST_SWEEPLINE_VORONOI_BUILDER
#define BOOST_SWEEPLINE_VORONOI_BUILDER
namespace boost {
namespace sweepline {
-
- using namespace detail;
// Voronoi diagram builder. Sweepline sweeps from left to right.
template <typename T>
class voronoi_builder {
public:
- typedef typename point_2d<T> Point2D;
+ typedef point_2d<T> Point2D;
typedef typename Point2D::coordinate_type coordinate_type;
+ typedef voronoi_output<Point2D> Output;
+ typedef typename Output::edge_type edge_type;
- typedef typename voronoi_output<Point2D>::edge_type edge_type;
- typedef typename voronoi_output<Point2D>::edge_iterator edge_iterator;
- typedef typename voronoi_output<Point2D>::cell_records cell_records;
- typedef typename voronoi_output<Point2D>::voronoi_vertices voronoi_vertices;
- typedef typename voronoi_vertices::const_iterator voronoi_vertices_iterator;
-
- voronoi_builder() {}
+ voronoi_builder() {
+ // 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
@@ -38,24 +37,23 @@
// In other case just use the first two sites for the initialization.
void init(std::vector<Point2D> &sites) {
// Sort all sites.
- std::sort(sites.begin(), sites.end());
+ sort(sites.begin(), sites.end());
// Add all unique sites to the site events vector.
int site_event_index = 0;
int sz = sites.size();
for (int i = 0; i < sz; i++) {
if (!i || sites[i] != sites[i-1]) {
- site_events_.push_back(make_site_event(sites[i].x(), sites[i].y(),
- site_event_index));
+ site_events_.push_back(detail::make_site_event(sites[i], site_event_index));
site_event_index++;
}
}
- // Init output with number of site events.
- output_.init(site_events_.size());
-
// Set sites iterator.
site_events_iterator_ = site_events_.begin();
+
+ // Init output with number of site events.
+ output_.init(site_events_.size());
int skip = 0;
if (site_events_.size() == 1) {
@@ -93,47 +91,37 @@
// 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(*site_events_iterator_);
- site_events_iterator_++;
- } else if (site_events_iterator_ == site_events_.end()) {
- circle_event<T> c_event = circle_events_.top();
- circle_events_.pop();
- process_circle_event(c_event);
- } else {
- if (circle_events_.top().compare(*site_events_iterator_) >= 0) {
- process_site_event(*site_events_iterator_);
- site_events_iterator_++;
- } else {
- circle_event<T> c_event = circle_events_.top();
- circle_events_.pop();
- process_circle_event(c_event);
- }
+ 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_) >= 0)
+ process_site_event();
+ else
+ process_circle_event();
}
}
- }
- const cell_records &get_cell_records() const {
- return output_.get_cell_records();
+ // Simplify output.
+ output_.simplify();
}
- const voronoi_vertices &get_voronoi_vertices() const {
- return output_.get_voronoi_vertices();
+ const Output &get_output() const {
+ return output_;
}
protected:
- typedef typename Point2D::site_event_type site_event_type;
- typedef typename Point2D::circle_event_type circle_event_type;
+ typedef typename detail::site_event<Point2D> site_event_type;
+ typedef typename detail::circle_event<Point2D> circle_event_type;
typedef typename std::vector<site_event_type>::const_iterator site_events_iterator;
- typedef typename circle_events_queue<Point2D> CircleEventsQueue;
- typedef typename beach_line_node<Point2D> Key;
- typedef typename beach_line_node_data<Point2D> Value;
- typedef typename node_comparer<Key> NodeComparer;
- typedef typename std::map< Key, Value, NodeComparer > BeachLine;
- typedef typename BeachLine::const_iterator beach_line_iterator;
-
- typedef typename voronoi_output<Point2D> Output;
+ typedef typename detail::circle_events_queue<Point2D> CircleEventsQueue;
+ typedef typename detail::beach_line_node<Point2D> Key;
+ typedef typename detail::beach_line_node_data<edge_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;
void init_beach_line() {
site_events_iterator it_first = site_events_.begin();
@@ -176,7 +164,10 @@
// Uses special comparison function for the lower bound and insertion
// operations.
- void process_site_event(const site_event_type &site_event) {
+ void process_site_event() {
+ const site_event_type &site_event = *site_events_iterator_;
+ site_events_iterator_++;
+
// Find the node in the binary search tree with left arc
// lying above the new site point.
Key new_key(site_event);
@@ -232,7 +223,9 @@
// 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) {
+ 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();
@@ -262,10 +255,14 @@
const_cast<Key &>(it_first->first).set_right_site(site3);
edge_type *edge = output_.insert_new_edge(site1, site2, site3, circle_event,
bisector1.edge, bisector2.edge);
- const_cast<Value &>(it_first->second).change_edge(edge);
+ it_first->second.change_edge(edge);
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()) {
@@ -292,8 +289,6 @@
// Create two new nodes.
Key new_left_node(site_arc, site_event);
Key new_right_node(site_event, site_arc);
- int site_index1 = site_arc.get_site_index();
- int site_index2 = site_event.get_site_index();
// Insert two new nodes into the binary search tree.
// Update output.
@@ -323,7 +318,7 @@
coordinate_type sqr_radius = (c_x-site1.x())*(c_x-site1.x()) +
(c_y-site1.y())*(c_y-site1.y());
// Create new circle event;
- c_event = make_circle_event(c_x, c_y, sqr_radius);
+ c_event = detail::make_circle_event<Point2D>(c_x, c_y, sqr_radius);
c_event.set_sites(site1, site2, site3);
return true;
}
@@ -364,4 +359,4 @@
} // sweepline
} // boost
-#endif
\ No newline at end of file
+#endif
Added: sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_output.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_output.hpp 2010-06-28 11:04:37 EDT (Mon, 28 Jun 2010)
@@ -0,0 +1,453 @@
+// Boost sweepline/voronoi_output.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.
+
+// Point in 2D space data structure. Comparators defined in this
+ // data structure actually define sweepline movement direction.
+
+#ifndef BOOST_SWEEPLINE_VORONOI_OUTPUT
+#define BOOST_SWEEPLINE_VORONOI_OUTPUT
+
+#include "detail/voronoi_formation.hpp"
+
+namespace boost {
+namespace sweepline {
+
+ template <typename Point2D>
+ struct half_edge;
+
+ template <typename T>
+ struct point_2d {
+ public:
+ typedef T coordinate_type;
+ typedef half_edge< point_2d<T> > Edge;
+
+ point_2d() {}
+
+ point_2d(T x, T y) {
+ x_ = x;
+ y_ = y;
+ }
+
+ bool operator==(const point_2d &point) const {
+ return (this->x_ == point.x()) && (this->y_ == point.y());
+ }
+
+ bool operator!=(const point_2d &point) const {
+ return (this->x_ != point.x()) || (this->y_ != point.y());
+ }
+
+ // This comparator actually defines sweepline movement direction.
+ bool operator<(const point_2d &point) const {
+ // Sweepline sweeps from left to right.
+ if (this->x_ != point.x_)
+ return this->x_ < point.x_;
+ return this->y_ < point.y_;
+ }
+
+ bool operator<=(const point_2d &point) const {
+ return !(point < (*this));
+ }
+
+ bool operator>(const point_2d &point) const {
+ return point < (*this);
+ }
+
+ bool operator>=(const point_2d &point) const {
+ return !((*this) < point);
+ }
+
+ coordinate_type x() const {
+ return this->x_;
+ }
+
+ coordinate_type y() const {
+ return this->y_;
+ }
+
+ void x(coordinate_type x) {
+ x_ = x;
+ }
+
+ void y(coordinate_type y) {
+ y_ = y;
+ }
+
+ private:
+ coordinate_type x_;
+ coordinate_type y_;
+ };
+
+ template <typename T>
+ point_2d<T> make_point_2d(T x, T y) {
+ return point_2d<T>(x,y);
+ }
+
+ ///////////////////////////////////////////////////////////////////////////
+ // VORONOI OUTPUT TYPES ///////////////////////////////////////////////////
+ ///////////////////////////////////////////////////////////////////////////
+
+ // Cell record data structure. Represents voronoi cell.
+ // Contains site point pointer to any incident half-edge and number
+ // of incident half-edges.
+ template <typename Point2D>
+ struct cell_record {
+ half_edge<Point2D> *incident_edge;
+ Point2D site_point;
+ int num_incident_edges;
+
+ cell_record(Point2D site, half_edge<Point2D>* edge) :
+ incident_edge(edge),
+ site_point(site),
+ num_incident_edges(0) {}
+ };
+
+ // Voronoi vertex data structure. Represents voronoi vertex.
+ // Contains vertex coordinates, pointers to all incident half-edges and
+ // number of incident half-edges.
+ template <typename Point2D>
+ struct vertex_record {
+ typedef typename std::list< half_edge<Point2D>* >::iterator vertex_incident_edges_it;
+
+ std::list< half_edge<Point2D>* > incident_edges;
+ Point2D vertex;
+ int num_incident_edges;
+ typename std::list< vertex_record<Point2D> >::iterator vertex_it;
+
+ vertex_record(Point2D vertex) : vertex(vertex), num_incident_edges(3) {}
+
+ vertex_incident_edges_it get_prev_incident_edge(vertex_incident_edges_it it) {
+ if (it != incident_edges.begin()) {
+ it--;
+ return it;
+ }
+ it = incident_edges.end();
+ it--;
+ return it;
+ }
+
+ vertex_incident_edges_it get_next_incident_edge(vertex_incident_edges_it it) {
+ it++;
+ if (it != incident_edges.end())
+ return it;
+ return incident_edges.begin();
+ }
+ };
+
+ // 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) pointer to twin half-edge;
+ // 5) iterator in the vertex incident edges list.
+ template <typename Point2D>
+ struct half_edge {
+ typedef cell_record<Point2D> cell_record_type;
+ typedef vertex_record<Point2D> vertex_record_type;
+ typedef half_edge<Point2D> half_edge_type;
+
+ cell_record_type *cell;
+ vertex_record_type *start_point;
+ vertex_record_type *end_point;
+ half_edge_type *prev;
+ half_edge_type *next;
+ half_edge_type *twin;
+ typename std::list< half_edge<Point2D>* >::iterator incident_it;
+
+ half_edge(int site_index) :
+ cell(NULL),
+ start_point(NULL),
+ end_point(NULL),
+ prev(NULL),
+ next(NULL),
+ twin(NULL) {}
+ };
+
+ // 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 Point2D>
+ class voronoi_output {
+ public:
+ typedef typename detail::site_event<Point2D> site_event_type;
+ typedef typename detail::circle_event<Point2D> circle_event_type;
+ typedef cell_record<Point2D> cell_record_type;
+ typedef vertex_record<Point2D> vertex_record_type;
+ typedef half_edge<Point2D> edge_type;
+ typedef std::vector<cell_record_type> cell_records_type;
+ typedef std::list<vertex_record_type> voronoi_vertices_type;
+ typedef typename std::list<edge_type *>::iterator edge_pointer_iterator_type;
+ typedef typename std::list<edge_type *>::const_iterator edge_pointer_const_iterator_type;
+ typedef typename voronoi_vertices_type::iterator voronoi_vertices_iterator_type;
+ typedef typename voronoi_vertices_type::const_iterator
+ voronoi_vertices_const_iterator_type;
+
+ voronoi_output() {
+ num_cell_records_ = 0;
+ num_edges_ = 0;
+ num_vertex_records_ = 0;
+ }
+
+ // This preserves the validity of iterators.
+ void init(int num_sites) {
+ cell_records_.reserve(num_sites);
+ num_cell_records_ = 0;
+ num_edges_ = 0;
+ num_vertex_records_ = 0;
+ }
+
+ void reset() {
+ cell_records_.clear();
+ vertex_records_.clear();
+ edges_.clear();
+
+ num_cell_records_ = 0;
+ num_edges_ = 0;
+ num_vertex_records_ = 0;
+ }
+
+ // 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 reference to the new half-edge.
+ // Second argument is new site. During this step we add two new
+ // twin half-edges.
+ edge_type *insert_new_edge(const site_event_type &site1,
+ const site_event_type &site2) {
+ num_cell_records_++;
+ num_edges_++;
+
+ // Get indexes of sites.
+ int site_index1 = site1.get_site_index();
+ int site_index2 = site2.get_site_index();
+
+ // Create new half-edge that belongs to the cell with the first site.
+ edges_.push_back(edge_type(site_index1));
+ edge_type &edge1 = edges_.back();
+
+ // Create new half-edge that belongs to the cell with the second site.
+ edges_.push_back(edge_type(site_index2));
+ edge_type &edge2 = edges_.back();
+
+ // Add initial cell during first edge insertion.
+ if (cell_records_.empty()) {
+ cell_records_.push_back(cell_record_type(site1.get_point(), &edge1));
+ num_cell_records_++;
+ }
+
+ // Second site represents new site during site event processing.
+ // Add new cell to the cell records vector.
+ cell_records_.push_back(cell_record_type(site2.get_point(), &edge2));
+
+ // Update pointers to cells.
+ edge1.cell = &cell_records_[site_index1];
+ edge2.cell = &cell_records_[site_index2];
+
+ // Update incident edges counters.
+ cell_records_[site_index1].num_incident_edges++;
+ cell_records_[site_index2].num_incident_edges++;
+
+ // 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 &site2,
+ const site_event_type &site3,
+ const circle_event_type &circle,
+ edge_type *edge12,
+ edge_type *edge23) {
+ num_vertex_records_++;
+ num_edges_++;
+
+ // Add new voronoi vertex as voronoi circle center.
+ vertex_records_.push_back(vertex_record_type(circle.get_center()));
+ vertex_record_type &new_vertex = vertex_records_.back();
+
+ // Update vertex iterator.
+ voronoi_vertices_iterator_type vertices_it = vertex_records_.end();
+ vertices_it--;
+ new_vertex.vertex_it = vertices_it;
+
+ // Update two input bisectors and their twins 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(site1.get_site_index()));
+ edge_type &new_edge1 = edges_.back();
+ new_edge1.cell = &cell_records_[site1.get_site_index()];
+ cell_records_[site1.get_site_index()].num_incident_edges++;
+ new_edge1.end_point = &new_vertex;
+
+ // Add new half-edge.
+ edges_.push_back(edge_type(site3.get_site_index()));
+ edge_type &new_edge2 = edges_.back();
+ new_edge2.cell = &cell_records_[site3.get_site_index()];
+ cell_records_[site3.get_site_index()].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;
+
+ // 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;
+
+ // Update voronoi vertex incident edges pointers.
+ new_vertex.incident_edges.push_back(edge12);
+ typename std::list<edge_type*>::iterator temp_iter =new_vertex.incident_edges.begin();
+ edge12->incident_it = temp_iter;
+
+ new_vertex.incident_edges.push_back(edge23);
+ temp_iter++;
+ edge23->incident_it = temp_iter;
+
+ new_vertex.incident_edges.push_back(&new_edge2);
+ temp_iter++;
+ new_edge2.incident_it = temp_iter;
+
+ return &new_edge1;
+ }
+
+ const cell_records_type &get_cell_records() const {
+ return cell_records_;
+ }
+
+ const voronoi_vertices_type &get_voronoi_vertices() const {
+ return vertex_records_;
+ }
+
+ int get_num_voronoi_cells() const {
+ return num_cell_records_;
+ }
+
+ int get_num_voronoi_vertices() const {
+ return num_vertex_records_;
+ }
+
+ int get_num_voronoi_edges() const {
+ return num_edges_;
+ }
+
+ void simplify() {
+ typename std::list<edge_type>::iterator edge_it1;
+ typename std::list<edge_type>::iterator edge_it = edges_.begin();
+
+ // Iterate over all edges and remove degeneracies.
+ while (edge_it != edges_.end()) {
+ edge_it1 = edge_it;
+ edge_it++;
+ edge_it++;
+
+ if (edge_it1->start_point && edge_it1->end_point &&
+ edge_it1->start_point->vertex == edge_it1->end_point->vertex) {
+ // Splice incident edges of the second voronoi vertex to the first
+ // one, if it contains less or equal number of them.
+
+ // 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->start_point->num_incident_edges >=
+ edge_it1->end_point->num_incident_edges)
+ simplify_edge(*edge_it1);
+ else
+ simplify_edge(*edge_it1->twin);
+
+ // Remove zero length edges.
+ edges_.erase(edge_it1, edge_it);
+
+ num_vertex_records_--;
+ num_edges_--;
+ }
+ }
+ }
+
+ bool check() {
+ return true;
+ }
+
+ private:
+ void simplify_edge(edge_type &edge) {
+ vertex_record_type *vertex1 = edge.start_point;
+ vertex_record_type *vertex2 = edge.end_point;
+
+ // Update number of vertex incident edges.
+ vertex1->num_incident_edges += vertex2->num_incident_edges - 2;
+
+ // Update second vertex incident edges start and end points.
+ for (edge_pointer_iterator_type it = vertex2->incident_edges.begin();
+ it != vertex2->incident_edges.end(); it++) {
+ (*it)->start_point = vertex1;
+ (*it)->twin->end_point = vertex1;
+ }
+
+ // Update prev and next pointers of incident edges that
+ // belongs to different voronoi vertices.
+ edge_pointer_iterator_type edge1_it = edge.incident_it;
+ edge_pointer_iterator_type edge2_it = edge.twin->incident_it;
+
+ edge_pointer_iterator_type edge1_it_prev = vertex1->get_prev_incident_edge(edge1_it);
+ edge_pointer_iterator_type edge1_it_next = vertex1->get_next_incident_edge(edge1_it);
+
+ edge_pointer_iterator_type edge2_it_prev = vertex2->get_prev_incident_edge(edge2_it);
+ edge_pointer_iterator_type edge2_it_next = vertex2->get_next_incident_edge(edge2_it);
+
+ (*edge1_it_prev)->twin->next = *edge2_it_next;
+ (*edge2_it_next)->prev = (*edge1_it_prev)->twin;
+
+ (*edge1_it_next)->prev = (*edge2_it_prev)->twin;
+ (*edge2_it_prev)->twin->next = (*edge1_it_next);
+
+ // Splice incident edges of the second voronoi vertex to the first one.
+ edge2_it++;
+ for (; edge2_it != vertex2->incident_edges.end(); edge2_it++)
+ (*edge2_it)->incident_it = vertex1->incident_edges.insert(edge1_it, *edge2_it);
+
+ edge2_it = vertex2->incident_edges.begin();
+ for (; edge2_it != edge.twin->incident_it; edge2_it++)
+ (*edge2_it)->incident_it = vertex1->incident_edges.insert(edge1_it, *edge2_it);
+
+ // Remove zero length edge from list of incident edges.
+ vertex1->incident_edges.erase(edge1_it);
+
+ // Remove second vertex from the vertex records.
+ vertex_records_.erase(vertex2->vertex_it);
+ }
+
+ std::vector<cell_record_type> cell_records_;
+ std::list<vertex_record_type> vertex_records_;
+ std::list<edge_type> edges_;
+
+ int num_cell_records_;
+ int num_vertex_records_;
+ int num_edges_;
+
+ //Disallow copy constructor and operator=
+ voronoi_output(const voronoi_output&);
+ void operator=(const voronoi_output&);
+ };
+
+} // sweepline
+} // boost
+
+#endif
Modified: sandbox/SOC/2010/sweepline/libs/sweepline/test/Jamfile.v2
==============================================================================
--- sandbox/SOC/2010/sweepline/libs/sweepline/test/Jamfile.v2 (original)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/test/Jamfile.v2 2010-06-28 11:04:37 EDT (Mon, 28 Jun 2010)
@@ -12,8 +12,8 @@
test-suite "sweepline"
:
- [ run event_queue_test.cpp : : : <link>static ]
- [ run event_types_test.cpp : : : <link>static ]
- [ run node_comparer_test.cpp : : : <link>static ]
- [ run voronoi_builder_test.cpp : : : <link>static ]
+ [ run event_queue_test.cpp ]
+ [ run event_types_test.cpp ]
+ [ run node_comparer_test.cpp ]
+ [ run voronoi_builder_test.cpp ]
;
\ No newline at end of file
Modified: sandbox/SOC/2010/sweepline/libs/sweepline/test/event_queue_test.cpp
==============================================================================
--- sandbox/SOC/2010/sweepline/libs/sweepline/test/event_queue_test.cpp (original)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/test/event_queue_test.cpp 2010-06-28 11:04:37 EDT (Mon, 28 Jun 2010)
@@ -7,9 +7,11 @@
//
// See http://www.boost.org for updates, documentation, and revision history.
+#include <cmath>
+
#include "test_type_list.hpp"
-#include "boost/sweepline/detail/voronoi_formation.hpp"
-using namespace boost::sweepline::detail;
+#include "boost/sweepline/voronoi_output.hpp"
+using namespace boost::sweepline;
#define BOOST_TEST_MODULE event_queue_test
#include <boost/test/test_case_template.hpp>
@@ -20,7 +22,9 @@
TOP.y() == static_cast<T>(Y), true)
BOOST_AUTO_TEST_CASE_TEMPLATE(event_queue_test1, T, test_types) {
- circle_events_queue< point_2d<T> > event_q;
+ typedef point_2d<T> Point2D;
+
+ detail::circle_events_queue< point_2d<T> > event_q;
BOOST_CHECK_EQUAL(event_q.empty(), true);
event_q.reset();
@@ -28,7 +32,7 @@
for (int i = 0; i < 10; i++) {
T x = static_cast<T>(-i);
T y = static_cast<T>(10-i);
- event_q.push(make_circle_event(x, y, static_cast<T>(100)));
+ event_q.push(detail::make_circle_event<Point2D>(x, y, static_cast<T>(100)));
}
for (int i = 0; i < 10; i++) {
@@ -40,15 +44,19 @@
}
BOOST_AUTO_TEST_CASE_TEMPLATE(event_queue_test2, T, test_types) {
- circle_events_queue< point_2d<T> > event_q;
- site_event<T> temp_site = make_site_event(static_cast<T>(0),
- static_cast<T>(0),
- 0);
+ typedef point_2d<T> Point2D;
+ typedef detail::circle_event<Point2D> circle_event_type;
+
+ detail::circle_events_queue< point_2d<T> > event_q;
+ detail::site_event<Point2D> temp_site =
+ detail::make_site_event<Point2D>(static_cast<T>(0),
+ static_cast<T>(0),
+ 0);
for (int i = 0; i < 10; i++) {
T x = static_cast<T>(10-i);
T y = static_cast<T>(10-i);
- circle_event<T> &c = make_circle_event(x, y, static_cast<T>(0));
+ circle_event_type c = detail::make_circle_event<Point2D>(x, y, static_cast<T>(0));
c.set_sites(temp_site, temp_site, temp_site);
event_q.push(c);
}
@@ -56,7 +64,7 @@
for (int i = 0; i < 5; i++) {
T x = static_cast<T>(10-2*i-1);
T y = static_cast<T>(10-2*i-1);
- circle_event<T> &c = make_circle_event(x, y, static_cast<T>(0));
+ circle_event_type c = detail::make_circle_event<Point2D>(x, y, static_cast<T>(0));
c.set_sites(temp_site, temp_site, temp_site);
event_q.deactivate_event(c);
}
@@ -67,4 +75,4 @@
}
BOOST_CHECK_EQUAL(event_q.empty(), true);
-}
\ No newline at end of file
+}
Modified: sandbox/SOC/2010/sweepline/libs/sweepline/test/event_types_test.cpp
==============================================================================
--- sandbox/SOC/2010/sweepline/libs/sweepline/test/event_types_test.cpp (original)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/test/event_types_test.cpp 2010-06-28 11:04:37 EDT (Mon, 28 Jun 2010)
@@ -8,7 +8,8 @@
// See http://www.boost.org for updates, documentation, and revision history.
#include "test_type_list.hpp"
-#include "boost/sweepline/detail/voronoi_formation.hpp"
+#include "boost/sweepline/voronoi_output.hpp"
+using namespace boost::sweepline;
using namespace boost::sweepline::detail;
#define BOOST_TEST_MODULE event_types_test
@@ -43,97 +44,102 @@
}
BOOST_AUTO_TEST_CASE_TEMPLATE(site_event_test1, T, test_types) {
- site_event<T> site1 = make_site_event(static_cast<T>(1),
- static_cast<T>(1.05),
- 0);
- site_event<T> site2;
+ typedef point_2d<T> Point2D;
+
+ site_event<Point2D> site1 = make_site_event<Point2D>(static_cast<T>(1),
+ static_cast<T>(1.05),
+ 0);
+ site_event<Point2D> site2;
BOOST_CHECK_EQUAL(site1.x(), static_cast<T>(1));
BOOST_CHECK_EQUAL(site1.y(), static_cast<T>(1.05));
BOOST_CHECK_EQUAL(site1.get_site_index(), 0);
- site2 = make_site_event(static_cast<T>(0.999999), static_cast<T>(1), 1);
+ site2 = make_site_event<Point2D>(static_cast<T>(0.999999), static_cast<T>(1), 1);
bool arr1[] = { false, true, false, true, false, true };
EVENT_TYPES_CHECK_COMPARISON(site1, site2, arr1);
- site2 = make_site_event(static_cast<T>(1), static_cast<T>(1.1), 1);
+ site2 = make_site_event<Point2D>(static_cast<T>(1), static_cast<T>(1.1), 1);
bool arr2[] = { true, false, true, false, false, true };
EVENT_TYPES_CHECK_COMPARISON(site1, site2, arr2);
- site2 = make_site_event(static_cast<T>(1), static_cast<T>(1.05), 1);
+ site2 = make_site_event<Point2D>(static_cast<T>(1), static_cast<T>(1.05), 1);
bool arr3[] = { false, false, true, true, true, false };
EVENT_TYPES_CHECK_COMPARISON(site1, site2, arr3);
}
BOOST_AUTO_TEST_CASE_TEMPLATE(circle_event_test1, T, test_types) {
- circle_event<T> circle1 = make_circle_event<T>(static_cast<T>(1),
- static_cast<T>(2),
- static_cast<T>(4));
- site_event<T> temp_site = make_site_event<T>(static_cast<T>(0),
- static_cast<T>(0),
- 0);
+ typedef point_2d<T> Point2D;
+
+ circle_event<Point2D> circle1 = make_circle_event<Point2D>(static_cast<T>(1),
+ static_cast<T>(2),
+ static_cast<T>(4));
+ site_event<Point2D> temp_site = make_site_event<Point2D>(static_cast<T>(0),
+ static_cast<T>(0),
+ 0);
circle1.set_sites(temp_site, temp_site, temp_site);
- circle_event<T> circle2;
+ circle_event<Point2D> circle2;
BOOST_CHECK_EQUAL(circle1.x(), static_cast<T>(1));
BOOST_CHECK_EQUAL(circle1.y(), static_cast<T>(2));
BOOST_CHECK_EQUAL(circle1.get_sqr_radius(), static_cast<T>(4));
- circle2 = make_circle_event<T>(static_cast<T>(1),
- static_cast<T>(2),
- static_cast<T>(4));
+ circle2 = make_circle_event<Point2D>(static_cast<T>(1),
+ static_cast<T>(2),
+ static_cast<T>(4));
circle2.set_sites(temp_site, temp_site, temp_site);
bool arr1[] = { false, false, true, true, true, false };
EVENT_TYPES_CHECK_COMPARISON(circle1, circle2, arr1);
- circle2 = make_circle_event<T>(static_cast<T>(1),
- static_cast<T>(3),
- static_cast<T>(4));
+ circle2 = make_circle_event<Point2D>(static_cast<T>(1),
+ static_cast<T>(3),
+ static_cast<T>(4));
circle2.set_sites(temp_site, temp_site, temp_site);
bool arr2[] = { true, false, true, false, false, true };
EVENT_TYPES_CHECK_COMPARISON(circle1, circle2, arr2);
- circle2 = make_circle_event<T>(static_cast<T>(1),
- static_cast<T>(2),
- static_cast<T>(5));
+ circle2 = make_circle_event<Point2D>(static_cast<T>(1),
+ static_cast<T>(2),
+ static_cast<T>(5));
circle2.set_sites(temp_site, temp_site, temp_site);
bool arr3[] = { true, false, true, false, false, true };
EVENT_TYPES_CHECK_COMPARISON(circle1, circle2, arr3);
- circle2 = make_circle_event<T>(static_cast<T>(0),
- static_cast<T>(2),
- static_cast<T>(4));
+ circle2 = make_circle_event<Point2D>(static_cast<T>(0),
+ static_cast<T>(2),
+ static_cast<T>(4));
circle2.set_sites(temp_site, temp_site, temp_site);
bool arr4[] = { false, true, false, true, false, true };
EVENT_TYPES_CHECK_COMPARISON(circle1, circle2, arr4);
- circle2 = make_circle_event<T>(static_cast<T>(0),
- static_cast<T>(0),
- static_cast<T>(10));
+ circle2 = make_circle_event<Point2D>(static_cast<T>(0),
+ static_cast<T>(0),
+ static_cast<T>(10));
circle2.set_sites(temp_site, temp_site, temp_site);
bool arr5[] = { true, false, true, false, false, true };
EVENT_TYPES_CHECK_COMPARISON(circle1, circle2, arr5);
}
BOOST_AUTO_TEST_CASE_TEMPLATE(circle_event_test2, T, test_types) {
- circle_event<T> circle = make_circle_event<T>(static_cast<T>(1),
- static_cast<T>(2),
- static_cast<T>(4));
- site_event<T> site;
+ typedef point_2d<T> Point2D;
+ circle_event<Point2D> circle = make_circle_event<Point2D>(static_cast<T>(1),
+ static_cast<T>(2),
+ static_cast<T>(4));
+ site_event<Point2D> site;
- site = make_site_event<T>(0, 100, 0);
+ site = make_site_event<Point2D>(0, 100, 0);
BOOST_CHECK_EQUAL(circle.compare(site), 1);
- site = make_site_event<T>(3, 0, 0);
+ site = make_site_event<Point2D>(3, 0, 0);
BOOST_CHECK_EQUAL(circle.compare(site), 1);
- site = make_site_event<T>(3, 2, 0);
+ site = make_site_event<Point2D>(3, 2, 0);
BOOST_CHECK_EQUAL(circle.compare(site), 0);
- site = make_site_event<T>(3, 2, 0);
+ site = make_site_event<Point2D>(3, 2, 0);
BOOST_CHECK_EQUAL(circle.compare(site), 0);
- site = make_site_event<T>(4, 2, 0);
+ site = make_site_event<Point2D>(4, 2, 0);
BOOST_CHECK_EQUAL(circle.compare(site), -1);
-}
\ No newline at end of file
+}
Modified: sandbox/SOC/2010/sweepline/libs/sweepline/test/node_comparer_test.cpp
==============================================================================
--- sandbox/SOC/2010/sweepline/libs/sweepline/test/node_comparer_test.cpp (original)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/test/node_comparer_test.cpp 2010-06-28 11:04:37 EDT (Mon, 28 Jun 2010)
@@ -8,24 +8,28 @@
// See http://www.boost.org for updates, documentation, and revision history.
#include "test_type_list.hpp"
-#include "boost/sweepline/detail/voronoi_formation.hpp"
+#include "boost/sweepline/voronoi_output.hpp"
+using namespace boost::sweepline;
using namespace boost::sweepline::detail;
#define BOOST_TEST_MODULE node_comparer_test
#include <boost/test/test_case_template.hpp>
BOOST_AUTO_TEST_CASE_TEMPLATE(node_comparer_test1, T, test_types) {
+ typedef point_2d<T> Point2D;
+ typedef site_event<Point2D> site_event_type;
typedef beach_line_node< point_2d<T> > bline_node;
- typedef std::map< bline_node, int, node_comparer<bline_node> >::const_iterator bline_it;
+ typedef typename std::map< bline_node, int,
+ node_comparer<bline_node> >::const_iterator bline_it;
std::map< bline_node, int, node_comparer<bline_node> > test_beach_line;
- site_event<T> site1 = make_site_event<T>(static_cast<T>(0), static_cast<T>(0), 0);
- site_event<T> site2 = make_site_event<T>(static_cast<T>(0), static_cast<T>(2), 1);
+ site_event_type site1 = make_site_event<Point2D>(static_cast<T>(0), static_cast<T>(0), 0);
+ site_event_type site2 = make_site_event<Point2D>(static_cast<T>(0), static_cast<T>(2), 1);
bline_node initial_node(site1, site2);
test_beach_line[initial_node] = 2;
- site_event<T> site3 = make_site_event<T>(static_cast<T>(1), static_cast<T>(0), 2);
+ site_event_type site3 = make_site_event<Point2D>(static_cast<T>(1), static_cast<T>(0), 2);
bline_node node1(site1, site3);
bline_node node2(site3, site1);
test_beach_line.insert(std::pair< bline_node, int>(node1, 0));
@@ -39,14 +43,17 @@
}
BOOST_AUTO_TEST_CASE_TEMPLATE(node_comparer_test2, T, test_types) {
+ typedef point_2d<T> Point2D;
+ typedef site_event<Point2D> site_event_type;
typedef beach_line_node< point_2d<T> > bline_node;
- typedef std::map< bline_node, int, node_comparer<bline_node> >::const_iterator bline_it;
+ typedef typename std::map< bline_node, int,
+ node_comparer<bline_node> >::const_iterator bline_it;
std::map< bline_node, int, node_comparer<bline_node> > test_beach_line;
- site_event<T> site1 = make_site_event<T>(static_cast<T>(0), static_cast<T>(1), 0);
- site_event<T> site2 = make_site_event<T>(static_cast<T>(2), static_cast<T>(0), 1);
- site_event<T> site3 = make_site_event<T>(static_cast<T>(2), static_cast<T>(4), 2);
+ site_event_type site1 = make_site_event<Point2D>(static_cast<T>(0), static_cast<T>(1), 0);
+ site_event_type site2 = make_site_event<Point2D>(static_cast<T>(2), static_cast<T>(0), 1);
+ site_event_type site3 = make_site_event<Point2D>(static_cast<T>(2), static_cast<T>(4), 2);
bline_node initial_node1(site1, site2);
bline_node initial_node2(site2, site1);
test_beach_line[initial_node1] = 0;
@@ -65,20 +72,21 @@
}
BOOST_AUTO_TEST_CASE_TEMPLATE(node_comparer_test3, T, test_types) {
+ typedef point_2d<T> Point2D;
typedef beach_line_node< point_2d<T> > bline_node;
node_comparer<bline_node> node_comparer_test;
bline_node initial_node(
- make_site_event<T>(static_cast<T>(1), static_cast<T>(0), 0),
- make_site_event<T>(static_cast<T>(0), static_cast<T>(2), 1));
+ make_site_event<Point2D>(static_cast<T>(1), static_cast<T>(0), 0),
+ make_site_event<Point2D>(static_cast<T>(0), static_cast<T>(2), 1));
- bline_node new_node1(make_site_event<T>(static_cast<T>(1.5), static_cast<T>(-10), 2));
- bline_node new_node2(make_site_event<T>(static_cast<T>(1.5), static_cast<T>(-0.5), 3));
- bline_node new_node3(make_site_event<T>(static_cast<T>(1.5), static_cast<T>(0), 4));
- bline_node new_node4(make_site_event<T>(static_cast<T>(1.5), static_cast<T>(0.5), 4));
- bline_node new_node5(make_site_event<T>(static_cast<T>(1.5), static_cast<T>(1.0), 4));
- bline_node new_node6(make_site_event<T>(static_cast<T>(1.5), static_cast<T>(3.0), 4));
- bline_node new_node7(make_site_event<T>(static_cast<T>(2.0), static_cast<T>(1.0), 4));
+ bline_node new_node1(make_site_event<Point2D>(static_cast<T>(1.5), static_cast<T>(-10), 2));
+ bline_node new_node2(make_site_event<Point2D>(static_cast<T>(1.5), static_cast<T>(-0.5), 3));
+ bline_node new_node3(make_site_event<Point2D>(static_cast<T>(1.5), static_cast<T>(0), 4));
+ bline_node new_node4(make_site_event<Point2D>(static_cast<T>(1.5), static_cast<T>(0.5), 4));
+ bline_node new_node5(make_site_event<Point2D>(static_cast<T>(1.5), static_cast<T>(1.0), 4));
+ bline_node new_node6(make_site_event<Point2D>(static_cast<T>(1.5), static_cast<T>(3.0), 4));
+ bline_node new_node7(make_site_event<Point2D>(static_cast<T>(2.0), static_cast<T>(1.0), 4));
BOOST_CHECK_EQUAL(node_comparer_test(initial_node, new_node1), false);
@@ -100,20 +108,21 @@
}
BOOST_AUTO_TEST_CASE_TEMPLATE(node_comparer_test4, T, test_types) {
+ typedef point_2d<T> Point2D;
typedef beach_line_node< point_2d<T> > bline_node;
node_comparer<bline_node> node_comparer_test;
bline_node initial_node(
- make_site_event<T>(static_cast<T>(0), static_cast<T>(1), 0),
- make_site_event<T>(static_cast<T>(1), static_cast<T>(0), 1));
+ make_site_event<Point2D>(static_cast<T>(0), static_cast<T>(1), 0),
+ make_site_event<Point2D>(static_cast<T>(1), static_cast<T>(0), 1));
- bline_node new_node1(make_site_event<T>(static_cast<T>(1.5), static_cast<T>(-3), 2));
- bline_node new_node2(make_site_event<T>(static_cast<T>(1.5), static_cast<T>(-1.8), 3));
- bline_node new_node3(make_site_event<T>(static_cast<T>(1.5), static_cast<T>(-1.7), 4));
- bline_node new_node4(make_site_event<T>(static_cast<T>(1.5), static_cast<T>(0.0), 4));
- bline_node new_node5(make_site_event<T>(static_cast<T>(1.5), static_cast<T>(1.0), 4));
- bline_node new_node6(make_site_event<T>(static_cast<T>(1.5), static_cast<T>(3.0), 4));
- bline_node new_node7(make_site_event<T>(static_cast<T>(1.5), static_cast<T>(10.0), 4));
+ bline_node new_node1(make_site_event<Point2D>(static_cast<T>(1.5), static_cast<T>(-3), 2));
+ bline_node new_node2(make_site_event<Point2D>(static_cast<T>(1.5), static_cast<T>(-1.8), 3));
+ bline_node new_node3(make_site_event<Point2D>(static_cast<T>(1.5), static_cast<T>(-1.7), 4));
+ bline_node new_node4(make_site_event<Point2D>(static_cast<T>(1.5), static_cast<T>(0.0), 4));
+ bline_node new_node5(make_site_event<Point2D>(static_cast<T>(1.5), static_cast<T>(1.0), 4));
+ bline_node new_node6(make_site_event<Point2D>(static_cast<T>(1.5), static_cast<T>(3.0), 4));
+ bline_node new_node7(make_site_event<Point2D>(static_cast<T>(1.5), static_cast<T>(10.0), 4));
BOOST_CHECK_EQUAL(node_comparer_test(initial_node, new_node1), false);
BOOST_CHECK_EQUAL(node_comparer_test(initial_node, new_node2), false);
@@ -133,20 +142,21 @@
}
BOOST_AUTO_TEST_CASE_TEMPLATE(node_comparer_test5, T, test_types) {
+ typedef point_2d<T> Point2D;
typedef beach_line_node< point_2d<T> > bline_node;
node_comparer<bline_node> node_comparer_test;
bline_node initial_node(
- make_site_event<T>(static_cast<T>(0), static_cast<T>(0), 0),
- make_site_event<T>(static_cast<T>(1), static_cast<T>(2), 1));
+ make_site_event<Point2D>(static_cast<T>(0), static_cast<T>(0), 0),
+ make_site_event<Point2D>(static_cast<T>(1), static_cast<T>(2), 1));
- bline_node new_node1(make_site_event<T>(static_cast<T>(1.5), static_cast<T>(-10), 2));
- bline_node new_node2(make_site_event<T>(static_cast<T>(1.5), static_cast<T>(0), 3));
- bline_node new_node3(make_site_event<T>(static_cast<T>(1.5), static_cast<T>(1.05), 4));
- bline_node new_node4(make_site_event<T>(static_cast<T>(1.5), static_cast<T>(1.1), 4));
- bline_node new_node5(make_site_event<T>(static_cast<T>(1.5), static_cast<T>(2), 4));
- bline_node new_node6(make_site_event<T>(static_cast<T>(1.5), static_cast<T>(5), 4));
- bline_node new_node7(make_site_event<T>(static_cast<T>(1.5), static_cast<T>(20), 4));
+ bline_node new_node1(make_site_event<Point2D>(static_cast<T>(1.5), static_cast<T>(-10), 2));
+ bline_node new_node2(make_site_event<Point2D>(static_cast<T>(1.5), static_cast<T>(0), 3));
+ bline_node new_node3(make_site_event<Point2D>(static_cast<T>(1.5), static_cast<T>(1.05), 4));
+ bline_node new_node4(make_site_event<Point2D>(static_cast<T>(1.5), static_cast<T>(1.1), 4));
+ bline_node new_node5(make_site_event<Point2D>(static_cast<T>(1.5), static_cast<T>(2), 4));
+ bline_node new_node6(make_site_event<Point2D>(static_cast<T>(1.5), static_cast<T>(5), 4));
+ bline_node new_node7(make_site_event<Point2D>(static_cast<T>(1.5), static_cast<T>(20), 4));
BOOST_CHECK_EQUAL(node_comparer_test(initial_node, new_node1), false);
@@ -168,20 +178,21 @@
}
BOOST_AUTO_TEST_CASE_TEMPLATE(node_comparer_test6, T, test_types) {
+ typedef point_2d<T> Point2D;
typedef beach_line_node< point_2d<T> > bline_node;
node_comparer<bline_node> node_comparer_test;
bline_node initial_node(
- make_site_event<T>(static_cast<T>(1), static_cast<T>(1), 0),
- make_site_event<T>(static_cast<T>(0), static_cast<T>(0), 1));
+ make_site_event<Point2D>(static_cast<T>(1), static_cast<T>(1), 0),
+ make_site_event<Point2D>(static_cast<T>(0), static_cast<T>(0), 1));
- bline_node new_node1(make_site_event<T>(static_cast<T>(1.5), static_cast<T>(-3), 2));
- bline_node new_node2(make_site_event<T>(static_cast<T>(1.5), static_cast<T>(-1.75), 3));
- bline_node new_node3(make_site_event<T>(static_cast<T>(1.5), static_cast<T>(0.0), 4));
- bline_node new_node4(make_site_event<T>(static_cast<T>(1.5), static_cast<T>(0.28), 4));
- bline_node new_node5(make_site_event<T>(static_cast<T>(1.5), static_cast<T>(2.7), 4));
- bline_node new_node6(make_site_event<T>(static_cast<T>(1.5), static_cast<T>(2.8), 4));
- bline_node new_node7(make_site_event<T>(static_cast<T>(1.5), static_cast<T>(5.0), 4));
+ bline_node new_node1(make_site_event<Point2D>(static_cast<T>(1.5), static_cast<T>(-3), 2));
+ bline_node new_node2(make_site_event<Point2D>(static_cast<T>(1.5), static_cast<T>(-1.75), 3));
+ bline_node new_node3(make_site_event<Point2D>(static_cast<T>(1.5), static_cast<T>(0.0), 4));
+ bline_node new_node4(make_site_event<Point2D>(static_cast<T>(1.5), static_cast<T>(0.28), 4));
+ bline_node new_node5(make_site_event<Point2D>(static_cast<T>(1.5), static_cast<T>(2.7), 4));
+ bline_node new_node6(make_site_event<Point2D>(static_cast<T>(1.5), static_cast<T>(2.8), 4));
+ bline_node new_node7(make_site_event<Point2D>(static_cast<T>(1.5), static_cast<T>(5.0), 4));
BOOST_CHECK_EQUAL(node_comparer_test(initial_node, new_node1), false);
BOOST_CHECK_EQUAL(node_comparer_test(initial_node, new_node2), false);
@@ -201,18 +212,19 @@
}
BOOST_AUTO_TEST_CASE_TEMPLATE(node_comparer_test7, T, test_types) {
+ typedef point_2d<T> Point2D;
typedef beach_line_node< point_2d<T> > bline_node;
node_comparer<bline_node> node_comparer_test;
bline_node initial_node(
- make_site_event<T>(static_cast<T>(0), static_cast<T>(0), 0),
- make_site_event<T>(static_cast<T>(0), static_cast<T>(2), 1));
+ make_site_event<Point2D>(static_cast<T>(0), static_cast<T>(0), 0),
+ make_site_event<Point2D>(static_cast<T>(0), static_cast<T>(2), 1));
- bline_node new_node1(make_site_event<T>(static_cast<T>(1), static_cast<T>(0), 2));
- bline_node new_node2(make_site_event<T>(static_cast<T>(1), static_cast<T>(1), 3));
- bline_node new_node3(make_site_event<T>(static_cast<T>(1), static_cast<T>(2), 4));
- bline_node new_node4(make_site_event<T>(static_cast<T>(1), static_cast<T>(1.000001), 5));
- bline_node new_node5(make_site_event<T>(static_cast<T>(1), static_cast<T>(0.999999), 6));
+ bline_node new_node1(make_site_event<Point2D>(static_cast<T>(1), static_cast<T>(0), 2));
+ bline_node new_node2(make_site_event<Point2D>(static_cast<T>(1), static_cast<T>(1), 3));
+ bline_node new_node3(make_site_event<Point2D>(static_cast<T>(1), static_cast<T>(2), 4));
+ bline_node new_node4(make_site_event<Point2D>(static_cast<T>(1), static_cast<T>(1.000001), 5));
+ bline_node new_node5(make_site_event<Point2D>(static_cast<T>(1), static_cast<T>(0.999999), 6));
BOOST_CHECK_EQUAL(node_comparer_test(initial_node, new_node1), false);
BOOST_CHECK_EQUAL(node_comparer_test(initial_node, new_node2), false);
@@ -228,19 +240,20 @@
}
BOOST_AUTO_TEST_CASE_TEMPLATE(node_comparer_test8, T, test_types) {
+ typedef point_2d<T> Point2D;
typedef beach_line_node< point_2d<T> > bline_node;
node_comparer<bline_node> node_comparer_test;
bline_node initial_node(
- make_site_event<T>(static_cast<T>(0), static_cast<T>(0), 0),
- make_site_event<T>(static_cast<T>(1), static_cast<T>(1), 1));
+ make_site_event<Point2D>(static_cast<T>(0), static_cast<T>(0), 0),
+ make_site_event<Point2D>(static_cast<T>(1), static_cast<T>(1), 1));
- bline_node new_node1(make_site_event<T>(static_cast<T>(1), static_cast<T>(0), 2));
- bline_node new_node2(make_site_event<T>(static_cast<T>(1), static_cast<T>(1), 1));
- bline_node new_node3(make_site_event<T>(static_cast<T>(1), static_cast<T>(2), 3));
+ bline_node new_node1(make_site_event<Point2D>(static_cast<T>(1), static_cast<T>(0), 2));
+ bline_node new_node2(make_site_event<Point2D>(static_cast<T>(1), static_cast<T>(1), 1));
+ bline_node new_node3(make_site_event<Point2D>(static_cast<T>(1), static_cast<T>(2), 3));
bline_node new_node4(
- make_site_event<T>(static_cast<T>(1), static_cast<T>(1), 1),
- make_site_event<T>(static_cast<T>(0), static_cast<T>(0), 0));
+ make_site_event<Point2D>(static_cast<T>(1), static_cast<T>(1), 1),
+ make_site_event<Point2D>(static_cast<T>(0), static_cast<T>(0), 0));
BOOST_CHECK_EQUAL(node_comparer_test(initial_node, new_node1), false);
BOOST_CHECK_EQUAL(node_comparer_test(initial_node, new_node2), false);
@@ -251,4 +264,4 @@
BOOST_CHECK_EQUAL(node_comparer_test(new_node2, initial_node), false);
BOOST_CHECK_EQUAL(node_comparer_test(new_node3, initial_node), false);
BOOST_CHECK_EQUAL(node_comparer_test(new_node4, initial_node), false);
-}
\ No newline at end of file
+}
Modified: sandbox/SOC/2010/sweepline/libs/sweepline/test/test_type_list.hpp
==============================================================================
--- sandbox/SOC/2010/sweepline/libs/sweepline/test/test_type_list.hpp (original)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/test/test_type_list.hpp 2010-06-28 11:04:37 EDT (Mon, 28 Jun 2010)
@@ -12,8 +12,8 @@
#include <boost/mpl/list.hpp>
-typedef boost::mpl::list<float,
- double,
+typedef boost::mpl::list<//float,
+ //double,
long double> test_types;
-#endif
\ No newline at end of file
+#endif
Modified: sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_builder_test.cpp
==============================================================================
--- sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_builder_test.cpp (original)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_builder_test.cpp 2010-06-28 11:04:37 EDT (Mon, 28 Jun 2010)
@@ -19,10 +19,11 @@
// Sites: (0, 0), (0, 4), (2, 1).
BOOST_AUTO_TEST_CASE_TEMPLATE(voronoi_builder_test1, T, test_types) {
- typedef typename voronoi_builder<T>::edge_type edge_type;
- typedef typename voronoi_builder<T>::edge_iterator edge_iterator;
- typedef typename voronoi_builder<T>::voronoi_vertices_iterator
- voronoi_vertices_iterator;
+ typedef typename voronoi_output< point_2d<T> >::edge_type edge_type;
+ typedef typename voronoi_output< point_2d<T> >::edge_pointer_const_iterator_type
+ edge_pointer_iterator_type;
+ typedef typename voronoi_output< point_2d<T> >::voronoi_vertices_const_iterator_type
+ voronoi_vertices_iterator_type;
voronoi_builder<T> test_beach_line;
point_2d<T> point1 = make_point_2d<T>(0, 0);
@@ -36,31 +37,33 @@
test_beach_line.init(points);
test_beach_line.run_sweepline();
- BOOST_CHECK_EQUAL(test_beach_line.get_cell_records().size(), 3);
- BOOST_CHECK_EQUAL(test_beach_line.get_voronoi_vertices().size(), 1);
+ const voronoi_output< point_2d<T> > &test_output = test_beach_line.get_output();
- voronoi_vertices_iterator it = test_beach_line.get_voronoi_vertices().begin();
- BOOST_CHECK_EQUAL(it->incident_edges.size(), 3);
+ BOOST_CHECK_EQUAL(static_cast<int>(test_output.get_cell_records().size()), 3);
+ BOOST_CHECK_EQUAL(static_cast<int>(test_output.get_voronoi_vertices().size()), 1);
+
+ voronoi_vertices_iterator_type it = test_output.get_voronoi_vertices().begin();
+ BOOST_CHECK_EQUAL(static_cast<int>(it->incident_edges.size()), 3);
BOOST_CHECK_EQUAL(it->vertex.x() == static_cast<T>(0.25) &&
it->vertex.y() == static_cast<T>(2.0), true);
- edge_iterator edge_it = it->incident_edges.begin();
+ edge_pointer_iterator_type edge_it = it->incident_edges.begin();
edge_type *edge1_1 = *edge_it;
edge_type *edge1_2 = edge1_1->twin;
- BOOST_CHECK_EQUAL(edge1_1->cell_record->site_point == point3, true);
- BOOST_CHECK_EQUAL(edge1_2->cell_record->site_point == point1, true);
+ BOOST_CHECK_EQUAL(edge1_1->cell->site_point == point3, true);
+ BOOST_CHECK_EQUAL(edge1_2->cell->site_point == point1, true);
edge_it++;
edge_type *edge2_1 = *edge_it;
edge_type *edge2_2 = edge2_1->twin;
- BOOST_CHECK_EQUAL(edge2_1->cell_record->site_point == point1, true);
- BOOST_CHECK_EQUAL(edge2_2->cell_record->site_point == point2, true);
+ BOOST_CHECK_EQUAL(edge2_1->cell->site_point == point1, true);
+ BOOST_CHECK_EQUAL(edge2_2->cell->site_point == point2, true);
edge_it++;
edge_type *edge3_1 = *edge_it;
edge_type *edge3_2 = edge3_1->twin;
- BOOST_CHECK_EQUAL(edge3_1->cell_record->site_point == point2, true);
- BOOST_CHECK_EQUAL(edge3_2->cell_record->site_point == point3, true);
+ BOOST_CHECK_EQUAL(edge3_1->cell->site_point == point2, true);
+ BOOST_CHECK_EQUAL(edge3_2->cell->site_point == point3, true);
BOOST_CHECK_EQUAL(edge1_2->twin == edge1_1, true);
BOOST_CHECK_EQUAL(edge2_2->twin == edge2_1, true);
@@ -82,10 +85,11 @@
// Sites: (0, 1), (2, 0), (2, 4).
BOOST_AUTO_TEST_CASE_TEMPLATE(voronoi_builder_test2, T, test_types) {
- typedef typename voronoi_builder<T>::edge_type edge_type;
- typedef typename voronoi_builder<T>::edge_iterator edge_iterator;
- typedef typename voronoi_builder<T>::voronoi_vertices_iterator
- voronoi_vertices_iterator;
+ typedef typename voronoi_output< point_2d<T> >::edge_type edge_type;
+ typedef typename voronoi_output< point_2d<T> >::edge_pointer_const_iterator_type
+ edge_pointer_iterator_type;
+ typedef typename voronoi_output< point_2d<T> >::voronoi_vertices_const_iterator_type
+ voronoi_vertices_iterator_type;
voronoi_builder<T> test_beach_line;
point_2d<T> point1 = make_point_2d<T>(0, 1);
@@ -99,31 +103,33 @@
test_beach_line.init(points);
test_beach_line.run_sweepline();
- BOOST_CHECK_EQUAL(test_beach_line.get_cell_records().size(), 3);
- BOOST_CHECK_EQUAL(test_beach_line.get_voronoi_vertices().size(), 1);
+ const voronoi_output< point_2d<T> > &test_output = test_beach_line.get_output();
+
+ BOOST_CHECK_EQUAL(static_cast<int>(test_output.get_cell_records().size()), 3);
+ BOOST_CHECK_EQUAL(static_cast<int>(test_output.get_voronoi_vertices().size()), 1);
- voronoi_vertices_iterator it = test_beach_line.get_voronoi_vertices().begin();
- BOOST_CHECK_EQUAL(it->incident_edges.size(), 3);
+ voronoi_vertices_iterator_type it = test_output.get_voronoi_vertices().begin();
+ BOOST_CHECK_EQUAL(static_cast<int>(it->incident_edges.size()), 3);
BOOST_CHECK_EQUAL(it->vertex.x() == static_cast<T>(1.75) &&
it->vertex.y() == static_cast<T>(2.0), true);
- edge_iterator edge_it = it->incident_edges.begin();
+ edge_pointer_iterator_type edge_it = it->incident_edges.begin();
edge_type *edge1_1 = *edge_it;
edge_type *edge1_2 = edge1_1->twin;
- BOOST_CHECK_EQUAL(edge1_1->cell_record->site_point == point2, true);
- BOOST_CHECK_EQUAL(edge1_2->cell_record->site_point == point1, true);
+ BOOST_CHECK_EQUAL(edge1_1->cell->site_point == point2, true);
+ BOOST_CHECK_EQUAL(edge1_2->cell->site_point == point1, true);
edge_it++;
edge_type *edge2_1 = *edge_it;
edge_type *edge2_2 = edge2_1->twin;
- BOOST_CHECK_EQUAL(edge2_1->cell_record->site_point == point1, true);
- BOOST_CHECK_EQUAL(edge2_2->cell_record->site_point == point3, true);
+ BOOST_CHECK_EQUAL(edge2_1->cell->site_point == point1, true);
+ BOOST_CHECK_EQUAL(edge2_2->cell->site_point == point3, true);
edge_it++;
edge_type *edge3_1 = *edge_it;
edge_type *edge3_2 = edge3_1->twin;
- BOOST_CHECK_EQUAL(edge3_1->cell_record->site_point == point3, true);
- BOOST_CHECK_EQUAL(edge3_2->cell_record->site_point == point2, true);
+ BOOST_CHECK_EQUAL(edge3_1->cell->site_point == point3, true);
+ BOOST_CHECK_EQUAL(edge3_2->cell->site_point == point2, true);
BOOST_CHECK_EQUAL(edge1_2->twin == edge1_1, true);
BOOST_CHECK_EQUAL(edge2_2->twin == edge2_1, true);
@@ -144,10 +150,11 @@
// Sites: (0, 0), (0, 1), (1, 0), (1, 1).
BOOST_AUTO_TEST_CASE_TEMPLATE(voronoi_builder_test3, T, test_types) {
- typedef typename voronoi_builder<T>::edge_type edge_type;
- typedef typename voronoi_builder<T>::edge_iterator edge_iterator;
- typedef typename voronoi_builder<T>::voronoi_vertices_iterator
- voronoi_vertices_iterator;
+ typedef typename voronoi_output< point_2d<T> >::edge_type edge_type;
+ typedef typename voronoi_output< point_2d<T> >::edge_pointer_const_iterator_type
+ edge_pointer_iterator_type;
+ typedef typename voronoi_output< point_2d<T> >::voronoi_vertices_const_iterator_type
+ voronoi_vertices_iterator_type;
voronoi_builder<T> test_beach_line;
std::vector< point_2d<T> > points;
@@ -158,17 +165,70 @@
test_beach_line.init(points);
test_beach_line.run_sweepline();
- BOOST_CHECK_EQUAL(test_beach_line.get_cell_records().size(), 4);
- BOOST_CHECK_EQUAL(test_beach_line.get_voronoi_vertices().size(), 2);
+ const voronoi_output< point_2d<T> > &test_output = test_beach_line.get_output();
+
+ BOOST_CHECK_EQUAL(static_cast<T>(test_output.get_cell_records().size()), 4);
+ BOOST_CHECK_EQUAL(static_cast<T>(test_output.get_voronoi_vertices().size()), 1);
+ BOOST_CHECK_EQUAL(test_output.get_num_voronoi_cells(), 4);
+ BOOST_CHECK_EQUAL(test_output.get_num_voronoi_vertices(), 1);
+ BOOST_CHECK_EQUAL(test_output.get_num_voronoi_edges(), 4);
+
+ // Check voronoi vertex.
+ voronoi_vertices_iterator_type it = test_output.get_voronoi_vertices().begin();
+ BOOST_CHECK_EQUAL(static_cast<int>(it->incident_edges.size()), 4);
+ BOOST_CHECK_EQUAL(static_cast<int>(it->incident_edges.size()), it->num_incident_edges);
+ BOOST_CHECK_EQUAL(it->vertex.x() == static_cast<T>(0.5) &&
+ it->vertex.y() == static_cast<T>(0.5), true);
+ BOOST_CHECK_EQUAL(it == it->vertex_it, true);
+
+ // Check voronoi edges.
+ edge_pointer_iterator_type edge_it = it->incident_edges.begin();
+ edge_type *edge1_1 = *edge_it;
+ edge_type *edge1_2 = edge1_1->twin;
+ BOOST_CHECK_EQUAL(edge1_1->cell->site_point == points[2], true);
+ BOOST_CHECK_EQUAL(edge1_2->cell->site_point == points[0], true);
+
+ edge_it++;
+ edge_type *edge2_1 = *edge_it;
+ edge_type *edge2_2 = edge2_1->twin;
+ BOOST_CHECK_EQUAL(edge2_1->cell->site_point == points[0], true);
+ BOOST_CHECK_EQUAL(edge2_2->cell->site_point == points[1], true);
+
+ edge_it++;
+ edge_type *edge3_1 = *edge_it;
+ edge_type *edge3_2 = edge3_1->twin;
+ BOOST_CHECK_EQUAL(edge3_1->cell->site_point == points[1], true);
+ BOOST_CHECK_EQUAL(edge3_2->cell->site_point == points[3], true);
+
+ edge_it++;
+ edge_type *edge4_1 = *edge_it;
+ edge_type *edge4_2 = edge4_1->twin;
+ BOOST_CHECK_EQUAL(edge4_1->cell->site_point == points[3], true);
+ BOOST_CHECK_EQUAL(edge4_2->cell->site_point == points[2], true);
+
+ 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->next == NULL && edge1_2->prev == NULL, true);
+ BOOST_CHECK_EQUAL(edge2_1->next == NULL && edge2_2->prev == NULL, true);
+ BOOST_CHECK_EQUAL(edge3_1->next == NULL && edge3_2->prev == NULL, true);
+ BOOST_CHECK_EQUAL(edge4_1->next == NULL && edge4_2->prev == NULL, true);
+
+ BOOST_CHECK_EQUAL(edge1_1->prev == edge4_2, true);
+ BOOST_CHECK_EQUAL(edge2_1->prev == edge1_2, true);
+ BOOST_CHECK_EQUAL(edge3_1->prev == edge2_2, true);
+ BOOST_CHECK_EQUAL(edge4_1->prev == edge3_2, true);
+
+ BOOST_CHECK_EQUAL(edge1_2->next == edge2_1, true);
+ BOOST_CHECK_EQUAL(edge2_2->next == edge3_1, true);
+ BOOST_CHECK_EQUAL(edge3_2->next == edge4_1, true);
+ BOOST_CHECK_EQUAL(edge4_2->next == edge1_1, true);
}
// Sites: {(x, y) | x = 0 .. 3, y = 0 .. 3}.
BOOST_AUTO_TEST_CASE_TEMPLATE(voronoi_builder_test4, T, test_types) {
- typedef typename voronoi_builder<T>::edge_type edge_type;
- typedef typename voronoi_builder<T>::edge_iterator edge_iterator;
- typedef typename voronoi_builder<T>::voronoi_vertices_iterator
- voronoi_vertices_iterator;
-
voronoi_builder<T> test_beach_line;
std::vector< point_2d<T> > points;
for (int i = 0; i < 3; i++)
@@ -178,15 +238,15 @@
test_beach_line.init(points);
test_beach_line.run_sweepline();
+ const voronoi_output< point_2d<T> > &test_output = test_beach_line.get_output();
+
+ BOOST_CHECK_EQUAL(test_output.get_num_voronoi_cells(), 9);
+ BOOST_CHECK_EQUAL(test_output.get_num_voronoi_vertices(), 4);
+ BOOST_CHECK_EQUAL(test_output.get_num_voronoi_edges(), 12);
}
// Generate 10 random sites 1000 times.
BOOST_AUTO_TEST_CASE_TEMPLATE(voronoi_builder_test4_1, T, test_types) {
- typedef typename voronoi_builder<T>::edge_type edge_type;
- typedef typename voronoi_builder<T>::edge_iterator edge_iterator;
- typedef typename voronoi_builder<T>::voronoi_vertices_iterator
- voronoi_vertices_iterator;
-
srand(static_cast<unsigned int>(time(NULL)));
voronoi_builder<T> test_beach_line;
std::vector< point_2d<T> > points;
@@ -206,11 +266,6 @@
// Sites: {(x, y) | x = 0 .. 9, y = 0 .. 9}.
BOOST_AUTO_TEST_CASE_TEMPLATE(voronoi_builder_test5, T, test_types) {
- typedef typename voronoi_builder<T>::edge_type edge_type;
- typedef typename voronoi_builder<T>::edge_iterator edge_iterator;
- typedef typename voronoi_builder<T>::voronoi_vertices_iterator
- voronoi_vertices_iterator;
-
voronoi_builder<T> test_beach_line;
std::vector< point_2d<T> > points;
for (int i = 0; i < 10; i++)
@@ -220,15 +275,15 @@
test_beach_line.init(points);
test_beach_line.run_sweepline();
+ const voronoi_output< point_2d<T> > &test_output = test_beach_line.get_output();
+
+ BOOST_CHECK_EQUAL(test_output.get_num_voronoi_cells(), 100);
+ BOOST_CHECK_EQUAL(test_output.get_num_voronoi_vertices(), 81);
+ BOOST_CHECK_EQUAL(test_output.get_num_voronoi_edges(), 180);
}
// Generate 100 random sites 100 times.
BOOST_AUTO_TEST_CASE_TEMPLATE(voronoi_builder_test5_1, T, test_types) {
- typedef typename voronoi_builder<T>::edge_type edge_type;
- typedef typename voronoi_builder<T>::edge_iterator edge_iterator;
- typedef typename voronoi_builder<T>::voronoi_vertices_iterator
- voronoi_vertices_iterator;
-
srand(static_cast<unsigned int>(time(NULL)));
voronoi_builder<T> test_beach_line;
std::vector< point_2d<T> > points;
@@ -248,11 +303,6 @@
// Sites: {(x, y) | x = 0 .. 33, y = 0 .. 33}.
BOOST_AUTO_TEST_CASE_TEMPLATE(voronoi_builder_test6, T, test_types) {
- typedef typename voronoi_builder<T>::edge_type edge_type;
- typedef typename voronoi_builder<T>::edge_iterator edge_iterator;
- typedef typename voronoi_builder<T>::voronoi_vertices_iterator
- voronoi_vertices_iterator;
-
voronoi_builder<T> test_beach_line;
std::vector< point_2d<T> > points;
for (int i = 0; i < 33; i++)
@@ -262,15 +312,15 @@
test_beach_line.init(points);
test_beach_line.run_sweepline();
+ const voronoi_output< point_2d<T> > &test_output = test_beach_line.get_output();
+
+ BOOST_CHECK_EQUAL(test_output.get_num_voronoi_cells(), 1089);
+ BOOST_CHECK_EQUAL(test_output.get_num_voronoi_vertices(), 1024);
+ BOOST_CHECK_EQUAL(test_output.get_num_voronoi_edges(), 2112);
}
// Generate 1000 random sites 10 times.
BOOST_AUTO_TEST_CASE_TEMPLATE(voronoi_builder_test6_1, T, test_types) {
- typedef typename voronoi_builder<T>::edge_type edge_type;
- typedef typename voronoi_builder<T>::edge_iterator edge_iterator;
- typedef typename voronoi_builder<T>::voronoi_vertices_iterator
- voronoi_vertices_iterator;
-
srand(static_cast<unsigned int>(time(NULL)));
voronoi_builder<T> test_beach_line;
std::vector< point_2d<T> > points;
@@ -290,11 +340,6 @@
// Sites: {(x, y) | x = 0 .. 100, y = 0 .. 100}.
BOOST_AUTO_TEST_CASE_TEMPLATE(voronoi_builder_test7, T, test_types) {
- typedef typename voronoi_builder<T>::edge_type edge_type;
- typedef typename voronoi_builder<T>::edge_iterator edge_iterator;
- typedef typename voronoi_builder<T>::voronoi_vertices_iterator
- voronoi_vertices_iterator;
-
voronoi_builder<T> test_beach_line;
std::vector< point_2d<T> > points;
for (int i = 0; i < 100; i++)
@@ -304,15 +349,15 @@
test_beach_line.init(points);
test_beach_line.run_sweepline();
+ const voronoi_output< point_2d<T> > &test_output = test_beach_line.get_output();
+
+ BOOST_CHECK_EQUAL(test_output.get_num_voronoi_cells(), 10000);
+ BOOST_CHECK_EQUAL(test_output.get_num_voronoi_vertices(), 9801);
+ BOOST_CHECK_EQUAL(test_output.get_num_voronoi_edges(), 19800);
}
// Generate 10000 random sites.
BOOST_AUTO_TEST_CASE_TEMPLATE(voronoi_builder_test7_1, T, test_types) {
- typedef typename voronoi_builder<T>::edge_type edge_type;
- typedef typename voronoi_builder<T>::edge_iterator edge_iterator;
- typedef typename voronoi_builder<T>::voronoi_vertices_iterator
- voronoi_vertices_iterator;
-
srand(static_cast<unsigned int>(time(NULL)));
voronoi_builder<T> test_beach_line;
std::vector< point_2d<T> > points;
@@ -324,21 +369,20 @@
test_beach_line.run_sweepline();
}
-//// Sites: {(x, y) | x = 0 .. 333, y = 0 .. 333}.
-//BOOST_AUTO_TEST_CASE_TEMPLATE(voronoi_builder_test8, T, test_types) {
-// typedef typename voronoi_builder<T>::edge_type edge_type;
-// typedef typename voronoi_builder<T>::edge_iterator edge_iterator;
-// typedef typename voronoi_builder<T>::voronoi_vertices_iterator
-// voronoi_vertices_iterator;
-//
-// srand(static_cast<unsigned int>(time(NULL)));
-// voronoi_builder<T> test_beach_line;
-// std::vector< point_2d<T> > points;
-// for (int i = 0; i < 270; i++)
-// for (int j = 0; j < 270; j++)
-// points.push_back(make_point_2d<T>(static_cast<T>(rand() % 1000),
-// static_cast<T>(rand() % 1000)));
-//
-// test_beach_line.init(points);
-// test_beach_line.run_sweepline();
-//}
\ No newline at end of file
+// Sites: {(x, y) | x = 0 .. 333, y = 0 .. 333}.
+BOOST_AUTO_TEST_CASE_TEMPLATE(voronoi_builder_test8, T, test_types) {
+ voronoi_builder<T> test_beach_line;
+ std::vector< point_2d<T> > points;
+ for (int i = 0; i < 333; i++)
+ for (int j = 0; j < 333; j++)
+ points.push_back(make_point_2d<T>(static_cast<T>(i),
+ static_cast<T>(j)));
+
+ test_beach_line.init(points);
+ test_beach_line.run_sweepline();
+ const voronoi_output< point_2d<T> > &test_output = test_beach_line.get_output();
+
+ BOOST_CHECK_EQUAL(test_output.get_num_voronoi_cells(), 110889);
+ BOOST_CHECK_EQUAL(test_output.get_num_voronoi_vertices(), 110224);
+ BOOST_CHECK_EQUAL(test_output.get_num_voronoi_edges(), 221112);
+}
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