Subject: [Boost-commit] svn:boost r63187 - in sandbox/SOC/2010/sweepline: boost/sweepline boost/sweepline/detail libs/sweepline/test
From: sydorchuk.andriy_at_[hidden]
Date: 2010-06-21 09:47:47
Author: asydorchuk
Date: 2010-06-21 09:47:45 EDT (Mon, 21 Jun 2010)
New Revision: 63187
URL: http://svn.boost.org/trac/boost/changeset/63187
Log:
Splitted event_queue (contains only circle events now).
Made code refactoring.
Added:
sandbox/SOC/2010/sweepline/boost/sweepline/detail/voronoi_formation.hpp
- copied, changed from r63178, /sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_formation.hpp
sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_builder.hpp (contents, props changed)
sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_builder_test.cpp (contents, props changed)
Removed:
sandbox/SOC/2010/sweepline/boost/sweepline/event_queue.hpp
sandbox/SOC/2010/sweepline/boost/sweepline/event_types.hpp
sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_formation.hpp
sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_output.hpp
sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_formation_test.cpp
Text files modified:
sandbox/SOC/2010/sweepline/boost/sweepline/detail/voronoi_formation.hpp | 923 ++++++++++++++++++++++++---------------
sandbox/SOC/2010/sweepline/libs/sweepline/test/Jamfile.v2 | 2
sandbox/SOC/2010/sweepline/libs/sweepline/test/event_queue_test.cpp | 75 --
sandbox/SOC/2010/sweepline/libs/sweepline/test/event_types_test.cpp | 4
sandbox/SOC/2010/sweepline/libs/sweepline/test/node_comparer_test.cpp | 4
5 files changed, 586 insertions(+), 422 deletions(-)
Copied: sandbox/SOC/2010/sweepline/boost/sweepline/detail/voronoi_formation.hpp (from r63178, /sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_formation.hpp)
==============================================================================
--- /sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_formation.hpp (original)
+++ sandbox/SOC/2010/sweepline/boost/sweepline/detail/voronoi_formation.hpp 2010-06-21 09:47:45 EDT (Mon, 21 Jun 2010)
@@ -7,19 +7,580 @@
// See http://www.boost.org for updates, documentation, and revision history.
-#include <map>
-#include <vector>
-
-#include "event_queue.hpp"
-#include "event_types.hpp"
-#include "voronoi_output.hpp"
-
#ifndef BOOST_SWEEPLINE_VORONOI_FORMATION
#define BOOST_SWEEPLINE_VORONOI_FORMATION
+#include <list>
+#include <map>
+#include <queue>
+#include <vector>
+
namespace boost {
namespace sweepline {
+namespace detail {
+
+ ///////////////////////////////////////////////////////////////////////////
+ // VORONOI EVENT TYPES ////////////////////////////////////////////////////
+ ///////////////////////////////////////////////////////////////////////////
+
+ template <typename T>
+ struct site_event;
+
+ template <typename T>
+ struct circle_event;
+
+ template <typename Point2D>
+ struct beach_line_node;
+
+ template <typename Point2D>
+ struct beach_line_node_data;
+
+ 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>
+ struct site_event {
+ public:
+ typedef T coordinate_type;
+
+ site_event() {}
+
+ site_event(T x, T y, int index) : point_(x, y), site_index_(index) {}
+
+ bool operator==(const site_event &s_event) const {
+ return point_ == s_event.get_point();
+ }
+
+ bool operator!=(const site_event &s_event) const {
+ return point_ != s_event.get_point();
+ }
+
+ bool operator<(const site_event &s_event) const {
+ return point_ < s_event.get_point();
+ }
+
+ bool operator<=(const site_event &s_event) const {
+ return point_ <= s_event.get_point();
+ }
+
+ bool operator>(const site_event &s_event) const {
+ return point_ > s_event.get_point();
+ }
+
+ bool operator>=(const site_event &s_event) const {
+ return point_ >= s_event.get_point();
+ }
+
+ coordinate_type x() const {
+ return point_.x();
+ }
+
+ coordinate_type y() const {
+ return point_.y();
+ }
+
+ const point_2d<T> &get_point() const {
+ return point_;
+ }
+
+ int get_site_index() const {
+ return site_index_;
+ }
+
+ private:
+ point_2d<T> 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);
+ }
+
+ // Circle event type. Occurs when sweepline sweeps over the bottom point of
+ // the voronoi circle (with center at the bisectors intersection point).
+ // Circle event contains circle center and squared radius (to avoid sqrt
+ // computation). To compare bottom points of two different voronoi circles
+ // we don't compute exact radius and use special arithmetic for that. This
+ // way voronoi diagram implementation may be used with rational arithmetic.
+ // Let circle center coordinates be (x, y), squared radius be r.
+ // 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>
+ 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;
+
+ circle_event() {}
+
+ circle_event(T c_x, T c_y, T sqr_r) :
+ center_(c_x, c_y), sqr_radius_(sqr_r) {}
+
+ bool equals(const circle_event &c_event) const {
+ return center_.x() == c_event.x() && center_.y() == c_event.y() &&
+ sqr_radius_ == c_event.get_sqr_radius();
+ }
+
+ bool operator==(const circle_event &c_event) const {
+ 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.get_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_ *
+ c_event.get_sqr_radius();
+
+ return value_left == value_right;
+ }
+
+ bool operator!=(const circle_event &c_event) const {
+ return !((*this) == c_event);
+ }
+
+ 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;
+
+ if (x1 > x2) {
+ if (sqr_r2 <= sqr_r1)
+ return false;
+
+ if (sqr_dif_x >= sum_r_sqr)
+ return false;
+
+ if (value_left == value_right)
+ return y1 < y2;
+ else
+ return value_left > value_right;
+ }
+ else if (x1 < x2) {
+ if (sqr_r1 <= sqr_r2)
+ return true;
+
+ if (sqr_dif_x >= sum_r_sqr)
+ return true;
+
+ if (value_left == value_right)
+ return y1 < y2;
+ else
+ return value_left < value_right;
+ }
+ else {
+ if (sqr_r1 != sqr_r2)
+ return sqr_r1 < sqr_r2;
+ return y1 < y2;
+ }
+ }
+
+ bool operator<=(const circle_event &c_event) const {
+ return !(c_event < (*this));
+ }
+
+ bool operator>(const circle_event &c_event) const {
+ return c_event < (*this);
+ }
+
+ bool operator>=(const circle_event &c_event) const {
+ return !((*this) < c_event);
+ }
+
+ // Compares bottom voronoi circle point with site event point.
+ // 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 {
+ if (s_event.x() < center_.x())
+ return 1;
+ T 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;
+ return (center_.y() < s_event.y()) ? -1 : 1;
+ }
+ return (sqr_dif_x < sqr_radius_) ? 1 : -1;
+ }
+
+ coordinate_type x() const {
+ return center_.x();
+ }
+
+ coordinate_type y() const {
+ return center_.y();
+ }
+
+ const point_2d<T> &get_center() const {
+ return center_;
+ }
+
+ const T &get_sqr_radius() const {
+ return sqr_radius_;
+ }
+
+ void set_bisector(beach_line_iterator iterator) {
+ bisector_node_ = iterator;
+ }
+
+ const beach_line_iterator &get_bisector() const {
+ return bisector_node_;
+ }
+ private:
+ point_2d<T> center_;
+ T sqr_radius_;
+ beach_line_iterator bisector_node_;
+ };
+
+ 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) {}
+ };
+
+ // 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) {}
+ };
+
+ // 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&);
+ };
+
+ ///////////////////////////////////////////////////////////////////////////
+ // VORONOI CIRCLE EVENTS QUEUE ////////////////////////////////////////////
+ ///////////////////////////////////////////////////////////////////////////
+
+ // Event queue data structure, processes circle events.
+ template <typename Point2D>
+ class circle_events_queue {
+ public:
+ typedef typename Point2D::coordinate_type coordinate_type;
+ typedef typename Point2D::circle_event_type circle_event_type;
+
+ circle_events_queue() {}
+
+ void reset() {
+ while (!circle_events_.empty())
+ circle_events_.pop();
+ while (!deactivated_events_.empty())
+ deactivated_events_.pop();
+ }
+
+ bool empty() {
+ remove_not_active_events();
+ if (!circle_events_.empty())
+ return false;
+ return true;
+ }
+
+ circle_event_type &top() {
+ remove_not_active_events();
+ return circle_events_.top();
+ }
+
+ void pop() {
+ remove_not_active_events();
+ circle_events_.pop();
+ }
+
+ void push(const circle_event_type &circle_event) {
+ circle_events_.push(circle_event);
+ }
+
+ void deactivate_event(const circle_event_type &circle_event) {
+ deactivated_events_.push(circle_event);
+ }
+
+ private:
+ void remove_not_active_events() {
+ while (!circle_events_.empty() && !deactivated_events_.empty() &&
+ circle_events_.top().equals(deactivated_events_.top())) {
+ circle_events_.pop();
+ deactivated_events_.pop();
+ }
+ }
+
+ std::priority_queue< circle_event_type,
+ std::vector<circle_event_type>,
+ std::greater<circle_event_type> > circle_events_;
+ std::priority_queue< circle_event_type,
+ std::vector<circle_event_type>,
+ std::greater<circle_event_type> > deactivated_events_;
+
+ //Disallow copy constructor and operator=
+ circle_events_queue(const circle_events_queue&);
+ void operator=(const circle_events_queue&);
+ };
+
+ /////////////////////////////////////////////////////////////////////////////
+ // VORONOI BEACH LINE TYPES /////////////////////////////////////////////////
+ /////////////////////////////////////////////////////////////////////////////
+
// Represents bisector made by two arcs that correspond to the left and
// right sites. Arc is defined as curve with points equidistant from the
// site and from the sweepline.
@@ -166,351 +727,9 @@
return !node2.less(node1.get_new_site());
}
};
-
- // Voronoi diagram formation. Sweepline sweeps from left to right.
- template <typename T>
- class voronoi_formation {
- public:
- typedef typename point_2d<T> Point2D;
- 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 typename voronoi_output<Point2D> Output;
- typedef typename Output::edge_type edge_type;
- typedef typename Output::edge_iterator edge_iterator;
- typedef typename Output::cell_records cell_records;
- typedef typename Output::voronoi_vertices voronoi_vertices;
- typedef typename voronoi_vertices::const_iterator voronoi_vertices_iterator;
-
- typedef typename event_queue<Point2D> EventQueue;
- 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;
-
- // Functor to process events from the event queue.
- struct event_processor {
- event_processor() : beach_line_(NULL) {}
-
- void operator()(const site_event_type &site_event) {
- beach_line_->process_site_event(site_event);
- }
-
- void operator()(const circle_event_type &circle_event) {
- beach_line_->process_circle_event(circle_event);
- }
-
- voronoi_formation *beach_line_;
- };
-
- voronoi_formation() : event_processor_() {}
-
- // 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> &sites) {
- output_.init(sites.size());
-
- // Init beach_line pointer in the event_processor data sturcture.
- // This is done here to avoid compiler warning in the constructor.
- event_processor_.beach_line_ = this;
-
- // Sort all sites.
- std::sort(sites.begin(), sites.end());
- int skip = 0;
-
- if (sites.size() == 1) {
- skip = 1;
- } else {
- std::vector<Point2D>::const_iterator it = sites.begin();
- while(it != sites.end() && it->x() == sites.begin()->x()) {
- it++;
- skip++;
- }
-
- if (skip == 1) {
- // Init beach line with two sites.
- init_beach_line(*sites.begin(), *it);
-
- // Skip the second point also.
- skip++;
- } else {
- // Init beach line with sites situated on the same vertical line.
- init_beach_line(sites.begin(), it);
- }
- }
- // Init event queue with the rest of the sites.
- event_queue_.init(sites, skip);
- }
-
- void reset() {
- event_queue_.reset();
- beach_line_.clear();
- output_.clear();
- }
-
- void run_sweepline() {
- // Algorithm stops when there are no events in the queue.
- while (!event_queue_.empty()) {
- event_queue_.process_top_event(event_processor_);
- event_queue_.pop();
- }
- }
-
- // Uses special comparison function for the lower bound and insertion
- // operations.
- void process_site_event(const site_event_type &site_event) {
- // 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);
-
- site_event_type site_arc;
- if (it == beach_line_.end()) {
- it--;
- 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_event);
- new_node_it--;
-
- // 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()) {
- site_arc = it->first.get_left_site();
-
- // Insert new arc into the sweepline.
- beach_line_iterator new_node_it = insert_new_arc(site_arc, site_event);
- new_node_it++;
-
- // Add candidate circle to the event queue.
- activate_circle_event(site_event,
- it->first.get_left_site(),
- it->first.get_right_site(),
- new_node_it);
- } else {
- site_arc = it->first.get_left_site();
-
- // Insert new arc into the sweepline.
- beach_line_iterator new_node_it = insert_new_arc(site_arc, site_event);
-
- const site_event_type &site2 = it->first.get_left_site();
- const site_event_type &site3 = it->first.get_right_site();
- it--;
- const site_event_type &site1 = it->first.get_right_site();
-
- // Remove candidate circle from the event queue.
- deactivate_circle_event(site1, site2, site3);
-
- // Add candidate circles to the event queue.
- new_node_it--;
- activate_circle_event(site1, site2, site_event, new_node_it);
- new_node_it++;
- new_node_it++;
- activate_circle_event(site_event, site2, 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) {
- // 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 second and the third sites that create given circle event.
- site_event_type site2 = it_first->first.get_left_site();
- site_event_type site3 = it_first->first.get_right_site();
-
- // Get second bisector;
- Value bisector2 = it_first->second;
-
- // Get first bisector;
- it_first--;
- Value bisector1 = it_first->second;
-
- // 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.
- const_cast<Key &>(it_first->first).set_right_site(it_last->first.get_right_site());
- 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);
- beach_line_.erase(it_last);
- it_last = it_first;
-
- // Check the new triplets formed by the neighboring arcs
- // for potential circle events. Check left.
- if (it_first != beach_line_.begin()) {
- it_first--;
- const site_event_type &site_l1 = it_first->first.get_left_site();
- deactivate_circle_event(site_l1, site1, site2);
- if (it_first != beach_line_.begin()) {
- it_first--;
- const site_event_type &site_l2 = it_first->first.get_left_site();
- it_first++;
- activate_circle_event(site_l2, site_l1, site1, it_first);
- }
- }
-
- // Check the new triplets formed by the neighboring arcs
- // for potential circle events. Check right.
- it_last++;
- if (it_last != beach_line_.end()) {
- const site_event_type &site_r1 = it_last->first.get_right_site();
- deactivate_circle_event(site2, site3, site_r1);
- it_last++;
- if (it_last != beach_line_.end()) {
- it_last++;
- const site_event_type &site_r2 = it_last->first.get_right_site();
- activate_circle_event(site3, site_r1, site_r2, it_last);
- }
- }
- }
-
- const cell_records &get_cell_records() const {
- return output_.get_cell_records();
- }
-
- const voronoi_vertices &get_voronoi_vertices() const {
- return output_.get_voronoi_vertices();
- }
-
- protected:
- void init_beach_line(typename std::vector<Point2D>::const_iterator it_begin,
- typename std::vector<Point2D>::const_iterator it_end) {
- typename std::vector<Point2D>::const_iterator it_first = it_begin;
- typename std::vector<Point2D>::const_iterator it_second = it_begin;
- it_second++;
- int cur_site = 0;
- while (it_second != it_end) {
- site_event_type site1 = make_site_event<coordinate_type>(
- it_first->x(), it_first->y(), cur_site);
- site_event_type site2 = make_site_event<coordinate_type>(
- it_second->x(), it_second->y(), cur_site+1);
-
- // Create new beach line node.
- Key new_node(site1, site2);
-
- // Update output.
- edge_type *edge = output_.insert_new_edge(site1, site2);
-
- // 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++;
- cur_site++;
- }
- }
-
- void init_beach_line(const Point2D &first_point,
- const Point2D &second_point) {
- site_event_type site1 = make_site_event<coordinate_type>(
- first_point.x(), first_point.y(), 0);
- site_event_type site2 = make_site_event<coordinate_type>(
- second_point.x(), second_point.y(), 1);
-
- // Create two new beach line nodes.
- Key new_left_node(site1, site2);
- Key new_right_node(site2, site1);
-
- // Update output.
- edge_type *edge = output_.insert_new_edge(site1, site2);
-
- // Insert two new nodes into the binary search tree.
- beach_line_.insert(std::pair<Key, Value>(new_left_node, Value(edge)));
- beach_line_.insert(std::pair<Key, Value>(new_right_node, Value(edge->twin)));
- }
-
- // Insert new arc below site arc into the beach line.
- beach_line_iterator insert_new_arc(const site_event_type &site_arc,
- const site_event_type &site_event) {
- // 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.
- edge_type *edge = output_.insert_new_edge(site_arc, site_event);
- beach_line_.insert(std::pair<Key, Value>(new_left_node, Value(edge)));
- return beach_line_.insert(std::pair<Key, Value>(new_right_node, Value(edge->twin))).first;
- }
-
- // 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 {
- coordinate_type a = (site1.x() - site2.x()) * (site2.y() - site3.y()) -
- (site1.y() - site2.y()) * (site2.x() - site3.x());
- // Check if bisectors intersect.
- if (a >= static_cast<coordinate_type>(0))
- return false;
- coordinate_type b1 = (site1.x() - site2.x()) * (site1.x() + site2.x())+
- (site1.y() - site2.y()) * (site1.y() + site2.y());
- coordinate_type b2 = (site2.x() - site3.x()) * (site2.x() + site3.x())+
- (site2.y() - site3.y()) * (site2.y() + site3.y());
- coordinate_type c_x = (b1*(site2.y() - site3.y()) - b2*(site1.y() - site2.y())) / a *
- static_cast<coordinate_type>(0.5);
- coordinate_type c_y = (b2*(site1.x() - site2.x()) - b1*(site2.x() - site3.x())) / a *
- static_cast<coordinate_type>(0.5);
- 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);
- return true;
- }
-
- // 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);
- event_queue_.push(c_event);
- }
- }
-
- // Remove circle event from the event queue.
- void deactivate_circle_event(const site_event_type &point1,
- const site_event_type &point2,
- const site_event_type &point3) {
- circle_event_type c_event;
- if (create_circle_event(point1, point2, point3, c_event))
- event_queue_.deactivate_event(c_event);
- }
-
- private:
- EventQueue event_queue_;
- event_processor event_processor_;
- BeachLine beach_line_;
- Output output_;
-
- //Disallow copy constructor and operator=
- voronoi_formation(const voronoi_formation&);
- void operator=(const voronoi_formation&);
- };
-
+
} // sweepline
} // boost
+} // detail
-#endif
\ No newline at end of file
+#endif
Deleted: sandbox/SOC/2010/sweepline/boost/sweepline/event_queue.hpp
==============================================================================
--- sandbox/SOC/2010/sweepline/boost/sweepline/event_queue.hpp 2010-06-21 09:47:45 EDT (Mon, 21 Jun 2010)
+++ (empty file)
@@ -1,141 +0,0 @@
-// Boost sweepline/event_queue.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_EVENT_QUEUE
-#define BOOST_SWEPPLINE_EVENT_QUEUE
-
-#include <queue>
-
-namespace boost {
-namespace sweepline {
-
- // Event queue data structure, contains two types of events:
- // site events and circle events.
- template <typename Point2D>
- class event_queue {
- 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;
-
- enum kEventType {
- SITE_EVENT = 0,
- CIRCLE_EVENT = 1,
- NONE = 2,
- };
-
- event_queue() {
- site_events_iterator_ = site_events_.begin();
- }
-
- // Init event queue with sites, starting from the element with
- // skip index. Vector of sites should be sorted.
- void init(const std::vector<Point2D> &sites, int skip) {
- site_events_.clear();
- site_events_.resize(sites.size() - skip);
- std::vector<Point2D>::const_iterator sites_it;
- int index = 0;
- for (sites_it = sites.begin() + skip; sites_it != sites.end(); sites_it++, index++)
- site_events_[index] = make_site_event(sites_it->x(),
- sites_it->y(),
- index + skip);
- init_site_events();
- }
-
- void reset() {
- site_events_iterator_ = site_events_.begin();
- while (!circle_events_.empty())
- circle_events_.pop();
- while (!deactivated_events_.empty())
- deactivated_events_.pop();
- }
-
- bool empty() {
- if (site_events_iterator_ != site_events_.end())
- return false;
- remove_not_active_events();
- if (!circle_events_.empty())
- return false;
- return true;
- }
-
- template <typename event_handler>
- void process_top_event(event_handler &functor) {
- kEventType top_event_type = get_top_event_type();
- if (top_event_type == SITE_EVENT)
- functor(*site_events_iterator_);
- else
- functor(circle_events_.top());
- }
-
- void pop() {
- kEventType top_event_type = get_top_event_type();
- if (top_event_type == SITE_EVENT)
- site_events_iterator_++;
- else if (top_event_type == CIRCLE_EVENT)
- circle_events_.pop();
- }
-
- void push(const circle_event_type &circle_event) {
- circle_events_.push(circle_event);
- }
-
- void deactivate_event(const circle_event_type &circle_event) {
- deactivated_events_.push(circle_event);
- }
-
- private:
- void init_site_events() {
- site_events_iterator_ = site_events_.begin();
- }
-
- void remove_not_active_events() {
- while (!circle_events_.empty() && !deactivated_events_.empty() &&
- circle_events_.top().equals(deactivated_events_.top())) {
- circle_events_.pop();
- deactivated_events_.pop();
- }
- }
-
- kEventType get_top_event_type() {
- remove_not_active_events();
- if (site_events_iterator_ == site_events_.end())
- return CIRCLE_EVENT;
- else if (circle_events_.empty())
- return SITE_EVENT;
- else {
- // If two event points have the same coordinates return
- // site event at first.
- if (circle_events_.top().compare(*site_events_iterator_) >= 0)
- return SITE_EVENT;
- else
- return CIRCLE_EVENT;
- }
- return NONE;
- }
-
- typename std::vector<site_event_type>::const_iterator
- site_events_iterator_;
- std::vector<site_event_type> site_events_;
- std::priority_queue< circle_event_type,
- std::vector<circle_event_type>,
- std::greater<circle_event_type> > circle_events_;
- std::priority_queue< circle_event_type,
- std::vector<circle_event_type>,
- std::greater<circle_event_type> > deactivated_events_;
-
- //Disallow copy constructor and operator=
- event_queue(const event_queue&);
- void operator=(const event_queue&);
- };
-
-} // sweepline
-} // boost
-
-#endif
\ No newline at end of file
Deleted: sandbox/SOC/2010/sweepline/boost/sweepline/event_types.hpp
==============================================================================
--- sandbox/SOC/2010/sweepline/boost/sweepline/event_types.hpp 2010-06-21 09:47:45 EDT (Mon, 21 Jun 2010)
+++ (empty file)
@@ -1,311 +0,0 @@
-// Boost sweepline/event_types.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_EVENT_TYPES
-#define BOOST_SWEEPLINE_EVENT_TYPES
-
-namespace boost {
-namespace sweepline {
-
- template <typename T>
- struct site_event;
-
- template <typename T>
- struct circle_event;
-
- template <typename T>
- class voronoi_formation;
-
- // 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>
- struct site_event {
- public:
- typedef T coordinate_type;
-
- site_event() {}
-
- site_event(T x, T y, int index) : point_(x, y), site_index_(index) {}
-
- bool operator==(const site_event &s_event) const {
- return point_ == s_event.get_point();
- }
-
- bool operator!=(const site_event &s_event) const {
- return point_ != s_event.get_point();
- }
-
- bool operator<(const site_event &s_event) const {
- return point_ < s_event.get_point();
- }
-
- bool operator<=(const site_event &s_event) const {
- return point_ <= s_event.get_point();
- }
-
- bool operator>(const site_event &s_event) const {
- return point_ > s_event.get_point();
- }
-
- bool operator>=(const site_event &s_event) const {
- return point_ >= s_event.get_point();
- }
-
- coordinate_type x() const {
- return point_.x();
- }
-
- coordinate_type y() const {
- return point_.y();
- }
-
- const point_2d<T> &get_point() const {
- return point_;
- }
-
- int get_site_index() const {
- return site_index_;
- }
-
- private:
- point_2d<T> 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);
- }
-
- // Circle event type. Occurs when sweepline sweeps over the bottom point of
- // the voronoi circle (with center at the bisectors intersection point).
- // Circle event contains circle center and squared radius (to avoid sqrt
- // computation). To compare bottom points of two different voronoi circles
- // we don't compute exact radius and use special arithmetic for that. This
- // way voronoi diagram implementation may be used with rational arithmetic.
- // Let circle center coordinates be (x, y), squared radius be r.
- // 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>
- struct circle_event {
- public:
- typedef T coordinate_type;
- typedef typename voronoi_formation<T>::beach_line_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) {}
-
- bool equals(const circle_event &c_event) const {
- return center_.x() == c_event.x() && center_.y() == c_event.y() &&
- sqr_radius_ == c_event.get_sqr_radius();
- }
-
- bool operator==(const circle_event &c_event) const {
- 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.get_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_ *
- c_event.get_sqr_radius();
-
- return value_left == value_right;
- }
-
- bool operator!=(const circle_event &c_event) const {
- return !((*this) == c_event);
- }
-
- 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;
-
- if (x1 > x2) {
- if (sqr_r2 <= sqr_r1)
- return false;
-
- if (sqr_dif_x >= sum_r_sqr)
- return false;
-
- if (value_left == value_right)
- return y1 < y2;
- else
- return value_left > value_right;
- }
- else if (x1 < x2) {
- if (sqr_r1 <= sqr_r2)
- return true;
-
- if (sqr_dif_x >= sum_r_sqr)
- return true;
-
- if (value_left == value_right)
- return y1 < y2;
- else
- return value_left < value_right;
- }
- else {
- if (sqr_r1 != sqr_r2)
- return sqr_r1 < sqr_r2;
- return y1 < y2;
- }
- }
-
- bool operator<=(const circle_event &c_event) const {
- return !(c_event < (*this));
- }
-
- bool operator>(const circle_event &c_event) const {
- return c_event < (*this);
- }
-
- bool operator>=(const circle_event &c_event) const {
- return !((*this) < c_event);
- }
-
- // Compares bottom voronoi circle point with site event point.
- // 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 {
- if (s_event.x() < center_.x())
- return 1;
- T 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;
- return (center_.y() < s_event.y()) ? -1 : 1;
- }
- return (sqr_dif_x < sqr_radius_) ? 1 : -1;
- }
-
- coordinate_type x() const {
- return center_.x();
- }
-
- coordinate_type y() const {
- return center_.y();
- }
-
- const point_2d<T> &get_center() const {
- return center_;
- }
-
- const T &get_sqr_radius() const {
- return sqr_radius_;
- }
-
- void set_bisector(beach_line_iterator iterator) {
- bisector_node_ = iterator;
- }
-
- const beach_line_iterator &get_bisector() const {
- return bisector_node_;
- }
- private:
- point_2d<T> center_;
- T sqr_radius_;
- beach_line_iterator bisector_node_;
- };
-
- 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);
- }
-
-} // sweepline
-} // boost
-
-#endif
\ No newline at end of file
Added: sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_builder.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_builder.hpp 2010-06-21 09:47:45 EDT (Mon, 21 Jun 2010)
@@ -0,0 +1,372 @@
+// 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.
+
+#include "detail/voronoi_formation.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 typename Point2D::coordinate_type coordinate_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() {}
+
+ // 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> &sites) {
+ // Sort all sites.
+ std::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_event_index++;
+ }
+ }
+
+ // Init output with number of site events.
+ output_.init(site_events_.size());
+
+ // Set sites iterator.
+ site_events_iterator_ = site_events_.begin();
+
+ int skip = 0;
+ if (site_events_.size() == 1) {
+ skip = 1;
+ site_events_iterator_++;
+ } else {
+ while(site_events_iterator_ != site_events_.end() &&
+ site_events_iterator_->x() == site_events_.begin()->x()) {
+ site_events_iterator_++;
+ skip++;
+ }
+
+ if (skip == 1) {
+ // Init beach line with two sites.
+ init_beach_line();
+
+ // Skip the second point also.
+ site_events_iterator_++;
+ } else {
+ // Init beach line with sites situated on the same vertical line.
+ init_beach_line_colinear_sites();
+ }
+ }
+ }
+
+ void reset() {
+ site_events_.clear();
+ site_events_iterator_ = site_events_.begin();
+ circle_events_.reset();
+ beach_line_.clear();
+ output_.clear();
+ }
+
+ void run_sweepline() {
+ // 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()) {
+ process_circle_event(circle_events_.top());
+ circle_events_.pop();
+ } else {
+ if (circle_events_.top().compare(*site_events_iterator_) >= 0) {
+ process_site_event(*site_events_iterator_);
+ site_events_iterator_++;
+ } else {
+ process_circle_event(circle_events_.top());
+ circle_events_.pop();
+ }
+ }
+ }
+ }
+
+ const cell_records &get_cell_records() const {
+ return output_.get_cell_records();
+ }
+
+ const voronoi_vertices &get_voronoi_vertices() const {
+ return output_.get_voronoi_vertices();
+ }
+
+ protected:
+ typedef typename Point2D::site_event_type site_event_type;
+ typedef typename Point2D::circle_event_type 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;
+
+ void init_beach_line() {
+ site_events_iterator it_first = site_events_.begin();
+ site_events_iterator it_second = site_events_.begin();
+ it_second++;
+
+ // Create two new beach line nodes.
+ Key new_left_node(*it_first, *it_second);
+ Key new_right_node(*it_second, *it_first);
+
+ // Update output.
+ edge_type *edge = output_.insert_new_edge(*it_first, *it_second);
+
+ // Insert two new nodes into the binary search tree.
+ beach_line_.insert(std::pair<Key, Value>(new_left_node, Value(edge)));
+ beach_line_.insert(std::pair<Key, Value>(new_right_node, Value(edge->twin)));
+ }
+
+ void init_beach_line_colinear_sites() {
+ site_events_iterator it_first = site_events_.begin();
+ site_events_iterator it_second = site_events_.begin();
+ it_second++;
+ int cur_site = 0;
+ 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++;
+ cur_site++;
+ }
+ }
+
+ // Uses special comparison function for the lower bound and insertion
+ // operations.
+ void process_site_event(const site_event_type &site_event) {
+ // 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);
+
+ site_event_type site_arc;
+ if (it == beach_line_.end()) {
+ it--;
+ 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_event);
+ new_node_it--;
+
+ // 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()) {
+ site_arc = it->first.get_left_site();
+
+ // Insert new arc into the sweepline.
+ beach_line_iterator new_node_it = insert_new_arc(site_arc, site_event);
+ new_node_it++;
+
+ // Add candidate circle to the event queue.
+ activate_circle_event(site_event,
+ it->first.get_left_site(),
+ it->first.get_right_site(),
+ new_node_it);
+ } else {
+ site_arc = it->first.get_left_site();
+
+ // Insert new arc into the sweepline.
+ beach_line_iterator new_node_it = insert_new_arc(site_arc, site_event);
+
+ const site_event_type &site2 = it->first.get_left_site();
+ const site_event_type &site3 = it->first.get_right_site();
+ it--;
+ const site_event_type &site1 = it->first.get_right_site();
+
+ // Remove candidate circle from the event queue.
+ deactivate_circle_event(site1, site2, site3);
+
+ // Add candidate circles to the event queue.
+ new_node_it--;
+ activate_circle_event(site1, site2, site_event, new_node_it);
+ new_node_it++;
+ new_node_it++;
+ activate_circle_event(site_event, site2, 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) {
+ // 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 second and the third sites that create given circle event.
+ site_event_type site2 = it_first->first.get_left_site();
+ site_event_type site3 = it_first->first.get_right_site();
+
+ // Get second bisector;
+ Value bisector2 = it_first->second;
+
+ // Get first bisector;
+ it_first--;
+ Value bisector1 = it_first->second;
+
+ // 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.
+ const_cast<Key &>(it_first->first).set_right_site(it_last->first.get_right_site());
+ 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);
+ beach_line_.erase(it_last);
+ it_last = it_first;
+
+ // Check the new triplets formed by the neighboring arcs
+ // for potential circle events. Check left.
+ if (it_first != beach_line_.begin()) {
+ it_first--;
+ const site_event_type &site_l1 = it_first->first.get_left_site();
+ deactivate_circle_event(site_l1, site1, site3);
+ if (it_first != beach_line_.begin()) {
+ it_first--;
+ const site_event_type &site_l2 = it_first->first.get_left_site();
+ it_first++;
+ activate_circle_event(site_l2, site_l1, site1, it_first);
+ }
+ }
+
+ // Check the new triplets formed by the neighboring arcs
+ // for potential circle events. Check right.
+ it_last++;
+ if (it_last != beach_line_.end()) {
+ const site_event_type &site_r1 = it_last->first.get_right_site();
+ deactivate_circle_event(site1, site3, site_r1);
+ it_last++;
+ if (it_last != beach_line_.end()) {
+ const site_event_type &site_r2 = it_last->first.get_right_site();
+ activate_circle_event(site3, site_r1, site_r2, it_last);
+ }
+ }
+ }
+
+ // Insert new arc below site arc into the beach line.
+ beach_line_iterator insert_new_arc(const site_event_type &site_arc,
+ const site_event_type &site_event) {
+ // 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.
+ edge_type *edge = output_.insert_new_edge(site_arc, site_event);
+ beach_line_.insert(std::pair<Key, Value>(new_left_node, Value(edge)));
+ return beach_line_.insert(std::pair<Key, Value>(new_right_node, Value(edge->twin))).first;
+ }
+
+ // 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 {
+ coordinate_type a = (site1.x() - site2.x()) * (site2.y() - site3.y()) -
+ (site1.y() - site2.y()) * (site2.x() - site3.x());
+ // Check if bisectors intersect.
+ if (a >= static_cast<coordinate_type>(0))
+ return false;
+ coordinate_type b1 = (site1.x() - site2.x()) * (site1.x() + site2.x())+
+ (site1.y() - site2.y()) * (site1.y() + site2.y());
+ coordinate_type b2 = (site2.x() - site3.x()) * (site2.x() + site3.x())+
+ (site2.y() - site3.y()) * (site2.y() + site3.y());
+ coordinate_type c_x = (b1*(site2.y() - site3.y()) - b2*(site1.y() - site2.y())) / a *
+ static_cast<coordinate_type>(0.5);
+ coordinate_type c_y = (b2*(site1.x() - site2.x()) - b1*(site2.x() - site3.x())) / a *
+ static_cast<coordinate_type>(0.5);
+ 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);
+ return true;
+ }
+
+ // 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);
+ circle_events_.push(c_event);
+ }
+ }
+
+ // Remove circle event from the event queue.
+ void deactivate_circle_event(const site_event_type &point1,
+ const site_event_type &point2,
+ const site_event_type &point3) {
+ circle_event_type c_event;
+ if (create_circle_event(point1, point2, point3, c_event))
+ circle_events_.deactivate_event(c_event);
+ }
+
+ private:
+ std::vector<site_event_type> site_events_;
+ site_events_iterator site_events_iterator_;
+ 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
\ No newline at end of file
Deleted: sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_formation.hpp
==============================================================================
--- sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_formation.hpp 2010-06-21 09:47:45 EDT (Mon, 21 Jun 2010)
+++ (empty file)
@@ -1,516 +0,0 @@
-// Boost sweepline/voronoi_formation.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.
-
-#include <map>
-#include <vector>
-
-#include "event_queue.hpp"
-#include "event_types.hpp"
-#include "voronoi_output.hpp"
-
-#ifndef BOOST_SWEEPLINE_VORONOI_FORMATION
-#define BOOST_SWEEPLINE_VORONOI_FORMATION
-
-namespace boost {
-namespace sweepline {
-
- // Represents bisector made by two arcs that correspond to the left and
- // right sites. Arc is defined as curve with points equidistant from the
- // site and from the sweepline.
- // Let sweepline sweep from left to right and it's current coordinate
- // be x0, site coordinates be (x1, y1). In this case equation of the arc
- // may be written as: (x-x0)^2 = (x-x1)^2 + (y-y1)^2, or
- // x = ((y - y1)^2 + x1^2 - x0^2) / (2*(x1 - x0)).
- // In general case two arcs will create two different bisectors. That's why
- // the order of arcs is important to define unique bisector.
- template <typename Point2D>
- 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;
-
- beach_line_node() {}
-
- // Constructs degenerate bisector, used to search arc that is above
- // given site. The input to the constructor is the site event point.
- explicit beach_line_node(const site_event_type &new_point) {
- left_site_ = new_point;
- right_site_ = new_point;
- }
-
- // Constructs new bisector. The input to the constructor is two sites
- // that create bisector. The order of sites is important.
- beach_line_node(const site_event_type &left_point,
- const site_event_type &right_point) {
- left_site_ = left_point;
- right_site_ = right_point;
- }
-
- // Returns the left site of the bisector.
- const site_event_type &get_left_site() const {
- return left_site_;
- }
-
- // Returns the right site of the bisector.
- const site_event_type &get_right_site() const {
- return right_site_;
- }
-
- void set_left_site(const site_event_type &site) {
- left_site_ = site;
- }
-
- void set_right_site(const site_event_type &site) {
- right_site_ = site;
- }
-
- // Returns x coordinate of the rightmost site.
- coordinate_type get_sweepline_coord() const {
- return std::max(left_site_.x(), right_site_.x());
- }
-
- // Returns the rightmost site.
- const site_event_type& get_new_site() const {
- if (left_site_.x() > right_site_.x())
- return left_site_;
- return right_site_;
- }
-
- // Returns true if horizontal line going through new site intersects
- // right arc at first, else returns false. If horizontal line goes
- // through intersection point of the given two arcs returns false also.
- // Used during nodes comparison.
- // Let x0 be sweepline coordinate, left site coordinates be (x1, y1),
- // right site coordinates be (x2, y2). Equations of the arcs will be:
- // x1(y) = ((y - y1)^2 + x1^2 - x0^2) / (2*(x1 - x0));
- // x2(y) = ((y - y2)^2 + x2^2 - x0^2) / (2*(x2 - x0)).
- // Horizontal line going throught site (x*, y*) intersects second arc
- // at first if x2(y*) > x1(y*) or:
- // (x2-x0)*(x1-x0)*(x1-x2) + (x2-x0)*(y*-y1)^2 < (x1-x0)*(y*-y2)^2
- bool less(const site_event_type &new_site) const {
- coordinate_type sweepline_coord = new_site.x();
- coordinate_type new_node_coord = new_site.y();
- coordinate_type a1 = left_site_.x() - sweepline_coord;
- coordinate_type a2 = right_site_.x() - sweepline_coord;
- coordinate_type b1 = new_node_coord - left_site_.y();
- coordinate_type b2 = new_node_coord - right_site_.y();
- coordinate_type c = left_site_.x() - right_site_.x();
- return a1 * a2 * c + a2 * b1 * b1 < a1 * b2 * b2;
- }
-
- private:
- site_event_type left_site_;
- site_event_type right_site_;
- };
-
- // Represents edge data sturcture (bisector segment), which is
- // associated with beach line node key in the binary search tree.
- template <typename Point2D>
- struct beach_line_node_data {
- typedef typename half_edge<Point2D> Edge;
-
- Edge *edge;
-
- beach_line_node_data(Edge *new_edge) : edge(new_edge) {}
-
- void change_edge(Edge *new_edge) {
- edge = new_edge;
- }
- };
-
- template <typename BeachLineNode>
- struct node_comparer {
- public:
- typedef typename BeachLineNode::coordinate_type coordinate_type;
-
- // Compares nodes in the balanced binary search tree. Nodes are
- // compared based on the y coordinates of the arcs intersection points.
- // Nodes with lesser y coordinate of the intersection point go first.
- // Comparison is only called during site events processing. That's why
- // one of the nodes will always lie on the sweepline. Comparison won't
- // work fine for nodes situated above sweepline.
- bool operator() (const BeachLineNode &node1,
- const BeachLineNode &node2) const {
- // Get x coordinate of the righmost site from both nodes.
- coordinate_type node1_line = node1.get_sweepline_coord();
- coordinate_type node2_line = node2.get_sweepline_coord();
-
- // Both nodes are situated on the same vertical line.
- if (node1_line == node2_line) {
- // Let A be the new site event point, and B the site that
- // creates arc above A. In this case two new nodes are being
- // inserted: (A,B) and (B,A). As intersection points for the
- // first node and for the second are the same we need to
- // compare them based on some another characteristic.
- // That's why we assume that node (C, D) goes before node
- // (D, C), only if D lies on the sweepline.
- if (node1.get_left_site().get_site_index() ==
- node2.get_right_site().get_site_index() &&
- node1.get_right_site().get_site_index() ==
- node2.get_left_site().get_site_index())
- return node1.get_right_site().x() == node1_line;
-
- // Just compare coordinates of the sites situated on the sweepline.
- return node1.get_new_site().y() < node2.get_new_site().y();
- }
- else if (node1_line < node2_line)
- return node1.less(node2.get_new_site());
- else
- return !node2.less(node1.get_new_site());
- }
- };
-
- // Voronoi diagram formation. Sweepline sweeps from left to right.
- template <typename T>
- class voronoi_formation {
- public:
- typedef typename point_2d<T> Point2D;
- 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 typename voronoi_output<Point2D> Output;
- typedef typename Output::edge_type edge_type;
- typedef typename Output::edge_iterator edge_iterator;
- typedef typename Output::cell_records cell_records;
- typedef typename Output::voronoi_vertices voronoi_vertices;
- typedef typename voronoi_vertices::const_iterator voronoi_vertices_iterator;
-
- typedef typename event_queue<Point2D> EventQueue;
- 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;
-
- // Functor to process events from the event queue.
- struct event_processor {
- event_processor() : beach_line_(NULL) {}
-
- void operator()(const site_event_type &site_event) {
- beach_line_->process_site_event(site_event);
- }
-
- void operator()(const circle_event_type &circle_event) {
- beach_line_->process_circle_event(circle_event);
- }
-
- voronoi_formation *beach_line_;
- };
-
- voronoi_formation() : event_processor_() {}
-
- // 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> &sites) {
- output_.init(sites.size());
-
- // Init beach_line pointer in the event_processor data sturcture.
- // This is done here to avoid compiler warning in the constructor.
- event_processor_.beach_line_ = this;
-
- // Sort all sites.
- std::sort(sites.begin(), sites.end());
- int skip = 0;
-
- if (sites.size() == 1) {
- skip = 1;
- } else {
- std::vector<Point2D>::const_iterator it = sites.begin();
- while(it != sites.end() && it->x() == sites.begin()->x()) {
- it++;
- skip++;
- }
-
- if (skip == 1) {
- // Init beach line with two sites.
- init_beach_line(*sites.begin(), *it);
-
- // Skip the second point also.
- skip++;
- } else {
- // Init beach line with sites situated on the same vertical line.
- init_beach_line(sites.begin(), it);
- }
- }
- // Init event queue with the rest of the sites.
- event_queue_.init(sites, skip);
- }
-
- void reset() {
- event_queue_.reset();
- beach_line_.clear();
- output_.clear();
- }
-
- void run_sweepline() {
- // Algorithm stops when there are no events in the queue.
- while (!event_queue_.empty()) {
- event_queue_.process_top_event(event_processor_);
- event_queue_.pop();
- }
- }
-
- // Uses special comparison function for the lower bound and insertion
- // operations.
- void process_site_event(const site_event_type &site_event) {
- // 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);
-
- site_event_type site_arc;
- if (it == beach_line_.end()) {
- it--;
- 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_event);
- new_node_it--;
-
- // 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()) {
- site_arc = it->first.get_left_site();
-
- // Insert new arc into the sweepline.
- beach_line_iterator new_node_it = insert_new_arc(site_arc, site_event);
- new_node_it++;
-
- // Add candidate circle to the event queue.
- activate_circle_event(site_event,
- it->first.get_left_site(),
- it->first.get_right_site(),
- new_node_it);
- } else {
- site_arc = it->first.get_left_site();
-
- // Insert new arc into the sweepline.
- beach_line_iterator new_node_it = insert_new_arc(site_arc, site_event);
-
- const site_event_type &site2 = it->first.get_left_site();
- const site_event_type &site3 = it->first.get_right_site();
- it--;
- const site_event_type &site1 = it->first.get_right_site();
-
- // Remove candidate circle from the event queue.
- deactivate_circle_event(site1, site2, site3);
-
- // Add candidate circles to the event queue.
- new_node_it--;
- activate_circle_event(site1, site2, site_event, new_node_it);
- new_node_it++;
- new_node_it++;
- activate_circle_event(site_event, site2, 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) {
- // 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 second and the third sites that create given circle event.
- site_event_type site2 = it_first->first.get_left_site();
- site_event_type site3 = it_first->first.get_right_site();
-
- // Get second bisector;
- Value bisector2 = it_first->second;
-
- // Get first bisector;
- it_first--;
- Value bisector1 = it_first->second;
-
- // 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.
- const_cast<Key &>(it_first->first).set_right_site(it_last->first.get_right_site());
- 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);
- beach_line_.erase(it_last);
- it_last = it_first;
-
- // Check the new triplets formed by the neighboring arcs
- // for potential circle events. Check left.
- if (it_first != beach_line_.begin()) {
- it_first--;
- const site_event_type &site_l1 = it_first->first.get_left_site();
- deactivate_circle_event(site_l1, site1, site2);
- if (it_first != beach_line_.begin()) {
- it_first--;
- const site_event_type &site_l2 = it_first->first.get_left_site();
- it_first++;
- activate_circle_event(site_l2, site_l1, site1, it_first);
- }
- }
-
- // Check the new triplets formed by the neighboring arcs
- // for potential circle events. Check right.
- it_last++;
- if (it_last != beach_line_.end()) {
- const site_event_type &site_r1 = it_last->first.get_right_site();
- deactivate_circle_event(site2, site3, site_r1);
- it_last++;
- if (it_last != beach_line_.end()) {
- it_last++;
- const site_event_type &site_r2 = it_last->first.get_right_site();
- activate_circle_event(site3, site_r1, site_r2, it_last);
- }
- }
- }
-
- const cell_records &get_cell_records() const {
- return output_.get_cell_records();
- }
-
- const voronoi_vertices &get_voronoi_vertices() const {
- return output_.get_voronoi_vertices();
- }
-
- protected:
- void init_beach_line(typename std::vector<Point2D>::const_iterator it_begin,
- typename std::vector<Point2D>::const_iterator it_end) {
- typename std::vector<Point2D>::const_iterator it_first = it_begin;
- typename std::vector<Point2D>::const_iterator it_second = it_begin;
- it_second++;
- int cur_site = 0;
- while (it_second != it_end) {
- site_event_type site1 = make_site_event<coordinate_type>(
- it_first->x(), it_first->y(), cur_site);
- site_event_type site2 = make_site_event<coordinate_type>(
- it_second->x(), it_second->y(), cur_site+1);
-
- // Create new beach line node.
- Key new_node(site1, site2);
-
- // Update output.
- edge_type *edge = output_.insert_new_edge(site1, site2);
-
- // 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++;
- cur_site++;
- }
- }
-
- void init_beach_line(const Point2D &first_point,
- const Point2D &second_point) {
- site_event_type site1 = make_site_event<coordinate_type>(
- first_point.x(), first_point.y(), 0);
- site_event_type site2 = make_site_event<coordinate_type>(
- second_point.x(), second_point.y(), 1);
-
- // Create two new beach line nodes.
- Key new_left_node(site1, site2);
- Key new_right_node(site2, site1);
-
- // Update output.
- edge_type *edge = output_.insert_new_edge(site1, site2);
-
- // Insert two new nodes into the binary search tree.
- beach_line_.insert(std::pair<Key, Value>(new_left_node, Value(edge)));
- beach_line_.insert(std::pair<Key, Value>(new_right_node, Value(edge->twin)));
- }
-
- // Insert new arc below site arc into the beach line.
- beach_line_iterator insert_new_arc(const site_event_type &site_arc,
- const site_event_type &site_event) {
- // 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.
- edge_type *edge = output_.insert_new_edge(site_arc, site_event);
- beach_line_.insert(std::pair<Key, Value>(new_left_node, Value(edge)));
- return beach_line_.insert(std::pair<Key, Value>(new_right_node, Value(edge->twin))).first;
- }
-
- // 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 {
- coordinate_type a = (site1.x() - site2.x()) * (site2.y() - site3.y()) -
- (site1.y() - site2.y()) * (site2.x() - site3.x());
- // Check if bisectors intersect.
- if (a >= static_cast<coordinate_type>(0))
- return false;
- coordinate_type b1 = (site1.x() - site2.x()) * (site1.x() + site2.x())+
- (site1.y() - site2.y()) * (site1.y() + site2.y());
- coordinate_type b2 = (site2.x() - site3.x()) * (site2.x() + site3.x())+
- (site2.y() - site3.y()) * (site2.y() + site3.y());
- coordinate_type c_x = (b1*(site2.y() - site3.y()) - b2*(site1.y() - site2.y())) / a *
- static_cast<coordinate_type>(0.5);
- coordinate_type c_y = (b2*(site1.x() - site2.x()) - b1*(site2.x() - site3.x())) / a *
- static_cast<coordinate_type>(0.5);
- 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);
- return true;
- }
-
- // 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);
- event_queue_.push(c_event);
- }
- }
-
- // Remove circle event from the event queue.
- void deactivate_circle_event(const site_event_type &point1,
- const site_event_type &point2,
- const site_event_type &point3) {
- circle_event_type c_event;
- if (create_circle_event(point1, point2, point3, c_event))
- event_queue_.deactivate_event(c_event);
- }
-
- private:
- EventQueue event_queue_;
- event_processor event_processor_;
- BeachLine beach_line_;
- Output output_;
-
- //Disallow copy constructor and operator=
- voronoi_formation(const voronoi_formation&);
- void operator=(const voronoi_formation&);
- };
-
-} // sweepline
-} // boost
-
-#endif
\ No newline at end of file
Deleted: sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_output.hpp
==============================================================================
--- sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_output.hpp 2010-06-21 09:47:45 EDT (Mon, 21 Jun 2010)
+++ (empty file)
@@ -1,206 +0,0 @@
-// 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.
-
-#ifndef BOOST_SWEEPLINE_VORONOI_OUTPUT
-#define BOOST_SWEEPLINE_VORONOI_OUTPUT
-
-#include <list>
-#include <vector>
-
-namespace boost {
-namespace sweepline {
-
- 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) {}
- };
-
- // 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) {}
- };
-
- // 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&);
- };
-
-} // sweepline
-} // boost
-
-#endif
\ No newline at end of file
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-21 09:47:45 EDT (Mon, 21 Jun 2010)
@@ -15,5 +15,5 @@
[ run event_queue_test.cpp : : : <link>static ]
[ run event_types_test.cpp : : : <link>static ]
[ run node_comparer_test.cpp : : : <link>static ]
- [ run voronoi_formation_test.cpp : : : <link>static ]
+ [ run voronoi_builder_test.cpp : : : <link>static ]
;
\ 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-21 09:47:45 EDT (Mon, 21 Jun 2010)
@@ -8,84 +8,31 @@
// See http://www.boost.org for updates, documentation, and revision history.
#include "test_type_list.hpp"
-#include <boost/sweepline/voronoi_formation.hpp>
-using namespace boost::sweepline;
+#include <boost/sweepline/detail/voronoi_formation.hpp>
+using namespace boost::sweepline::detail;
#define BOOST_TEST_MODULE event_queue_test
#include <boost/test/test_case_template.hpp>
#define CHECK_TOP_ELEMENT_EQUALITY(TOP, X, Y) \
- BOOST_CHECK_EQUAL(TOP.x == static_cast<T>(X) && \
- TOP.y == static_cast<T>(Y), true)
-
-template <typename Point2D>
-struct event_processor {
- 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;
-
- event_processor() {}
-
- void operator()(const site_event_type &site_event) {
- x = site_event.x();
- y = site_event.y();
- }
-
- void operator()(const circle_event_type &circle_event) {
- x = circle_event.x() +
- sqrt(static_cast<coordinate_type>(circle_event.get_sqr_radius()));
- y = circle_event.y();
- }
-
- coordinate_type x;
- coordinate_type y;
-};
+ BOOST_CHECK_EQUAL(TOP.x() + sqrt(static_cast<T>(TOP.get_sqr_radius())) \
+ == static_cast<T>(X) && \
+ TOP.y() == static_cast<T>(Y), true)
BOOST_AUTO_TEST_CASE_TEMPLATE(event_queue_test1, T, test_types) {
- event_processor< point_2d<T> > test_processor;
-
- event_queue< point_2d<T> > event_q;
+ circle_events_queue< point_2d<T> > event_q;
BOOST_CHECK_EQUAL(event_q.empty(), true);
event_q.reset();
- std::vector< point_2d<T> > site_event_vec;
- for (int i = 0; i <= 10; i++) {
- T x = static_cast<T>(10-i);
- T y = static_cast<T>(10-i);
- site_event_vec.push_back(make_point_2d(x, y));
- }
- sort(site_event_vec.begin(), site_event_vec.end());
- event_q.init(site_event_vec, 0);
-
- event_q.process_top_event(test_processor);
- CHECK_TOP_ELEMENT_EQUALITY(test_processor, 0, 0);
- event_q.pop();
-
- event_q.process_top_event(test_processor);
- CHECK_TOP_ELEMENT_EQUALITY(test_processor, 1, 1);
-
- for (int i = 5; i < 10; i++) {
+ 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)));
}
- for (int i = 0; i < 5; i++) {
- T x = static_cast<T>(-i);
- T y = static_cast<T>(10-i-1);
- event_q.push(make_circle_event(x, y, static_cast<T>(100)));
- }
-
for (int i = 0; i < 10; i++) {
- event_q.process_top_event(test_processor);
- CHECK_TOP_ELEMENT_EQUALITY(test_processor, 1 + i/2, 1 + i/2);
- event_q.pop();
- }
-
- for (int i = 10; i < 20; i++) {
- event_q.process_top_event(test_processor);
- CHECK_TOP_ELEMENT_EQUALITY(test_processor, 1 + i/2, 1 + (i-1)/2);
+ CHECK_TOP_ELEMENT_EQUALITY(event_q.top(), 1 + i, 1 + i);
event_q.pop();
}
@@ -93,8 +40,7 @@
}
BOOST_AUTO_TEST_CASE_TEMPLATE(event_queue_test2, T, test_types) {
- event_processor< point_2d<T> > test_processor;
- event_queue< point_2d<T> > event_q;
+ circle_events_queue< point_2d<T> > event_q;
for (int i = 0; i < 10; i++) {
T x = static_cast<T>(10-i);
@@ -109,8 +55,7 @@
}
for (int i = 0; i < 5; i++) {
- event_q.process_top_event(test_processor);
- CHECK_TOP_ELEMENT_EQUALITY(test_processor, 2 + 2*i, 2 + 2*i);
+ CHECK_TOP_ELEMENT_EQUALITY(event_q.top(), 2 + 2*i, 2 + 2*i);
event_q.pop();
}
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-21 09:47:45 EDT (Mon, 21 Jun 2010)
@@ -8,8 +8,8 @@
// See http://www.boost.org for updates, documentation, and revision history.
#include "test_type_list.hpp"
-#include <boost/sweepline/voronoi_formation.hpp>
-using namespace boost::sweepline;
+#include <boost/sweepline/detail/voronoi_formation.hpp>
+using namespace boost::sweepline::detail;
#define BOOST_TEST_MODULE event_types_test
#include <boost/test/test_case_template.hpp>
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-21 09:47:45 EDT (Mon, 21 Jun 2010)
@@ -8,8 +8,8 @@
// See http://www.boost.org for updates, documentation, and revision history.
#include "test_type_list.hpp"
-#include <boost/sweepline/voronoi_formation.hpp>
-using namespace boost::sweepline;
+#include <boost/sweepline/detail/voronoi_formation.hpp>
+using namespace boost::sweepline::detail;
#define BOOST_TEST_MODULE node_comparer_test
#include <boost/test/test_case_template.hpp>
Added: sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_builder_test.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_builder_test.cpp 2010-06-21 09:47:45 EDT (Mon, 21 Jun 2010)
@@ -0,0 +1,162 @@
+// Boost sweepline library voronoi_builder_test.cpp 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.
+
+#include "test_type_list.hpp"
+#include <boost/sweepline/voronoi_builder.hpp>
+using namespace boost::sweepline;
+
+#define BOOST_TEST_MODULE voronoi_builder_test
+#include <boost/test/test_case_template.hpp>
+
+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;
+
+ voronoi_builder<T> test_beach_line;
+ point_2d<T> point1 = make_point_2d<T>(0, 0);
+ point_2d<T> point2 = make_point_2d<T>(0, 4);
+ point_2d<T> point3 = make_point_2d<T>(2, 1);
+
+ std::vector< point_2d<T> > points;
+ points.push_back(point1);
+ points.push_back(point2);
+ points.push_back(point3);
+
+ 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);
+
+ voronoi_vertices_iterator it = test_beach_line.get_voronoi_vertices().begin();
+ BOOST_CHECK_EQUAL(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_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);
+
+ 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);
+
+ 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(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->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(edge1_1->prev == edge3_2, true);
+ BOOST_CHECK_EQUAL(edge2_1->prev == edge1_2, true);
+ BOOST_CHECK_EQUAL(edge3_1->prev == edge2_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 == edge1_1, true);
+
+}
+
+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;
+
+ voronoi_builder<T> test_beach_line;
+ point_2d<T> point1 = make_point_2d<T>(0, 1);
+ point_2d<T> point2 = make_point_2d<T>(2, 0);
+ point_2d<T> point3 = make_point_2d<T>(2, 4);
+
+ std::vector< point_2d<T> > points;
+ points.push_back(point1);
+ points.push_back(point2);
+ points.push_back(point3);
+
+ 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);
+
+ voronoi_vertices_iterator it = test_beach_line.get_voronoi_vertices().begin();
+ BOOST_CHECK_EQUAL(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_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);
+
+ 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);
+
+ 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(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->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(edge1_1->prev == edge3_2, true);
+ BOOST_CHECK_EQUAL(edge2_1->prev == edge1_2, true);
+ BOOST_CHECK_EQUAL(edge3_1->prev == edge2_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 == edge1_1, true);
+}
+
+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;
+
+ voronoi_builder<T> test_beach_line;
+ point_2d<T> point1 = make_point_2d<T>(0, 0);
+ point_2d<T> point2 = make_point_2d<T>(0, 1);
+ point_2d<T> point3 = make_point_2d<T>(1, 0);
+ point_2d<T> point4 = make_point_2d<T>(1, 1);
+
+ std::vector< point_2d<T> > points;
+ points.push_back(point1);
+ points.push_back(point2);
+ points.push_back(point3);
+ points.push_back(point4);
+
+ 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(), 1);
+}
\ No newline at end of file
Deleted: sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_formation_test.cpp
==============================================================================
--- sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_formation_test.cpp 2010-06-21 09:47:45 EDT (Mon, 21 Jun 2010)
+++ (empty file)
@@ -1,138 +0,0 @@
-// Boost sweepline library voronoi_formation_test.cpp 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.
-
-#include "test_type_list.hpp"
-#include <boost/sweepline/voronoi_formation.hpp>
-using namespace boost::sweepline;
-
-#define BOOST_TEST_MODULE voronoi_formation_test
-#include <boost/test/test_case_template.hpp>
-
-BOOST_AUTO_TEST_CASE_TEMPLATE(beach_line_test1, T, test_types) {
- typedef typename voronoi_formation<T>::edge_type edge_type;
- typedef typename voronoi_formation<T>::edge_iterator edge_iterator;
- typedef typename voronoi_formation<T>::voronoi_vertices_iterator
- voronoi_vertices_iterator;
-
- voronoi_formation<T> test_beach_line;
- point_2d<T> point1 = make_point_2d<T>(0, 0);
- point_2d<T> point2 = make_point_2d<T>(0, 4);
- point_2d<T> point3 = make_point_2d<T>(2, 1);
-
- std::vector< point_2d<T> > points;
- points.push_back(point1);
- points.push_back(point2);
- points.push_back(point3);
-
- 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);
-
- voronoi_vertices_iterator it = test_beach_line.get_voronoi_vertices().begin();
- BOOST_CHECK_EQUAL(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_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);
-
- 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);
-
- 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(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->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(edge1_1->prev == edge3_2, true);
- BOOST_CHECK_EQUAL(edge2_1->prev == edge1_2, true);
- BOOST_CHECK_EQUAL(edge3_1->prev == edge2_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 == edge1_1, true);
-
-}
-
-BOOST_AUTO_TEST_CASE_TEMPLATE(beach_line_test2, T, test_types) {
- typedef typename voronoi_formation<T>::edge_type edge_type;
- typedef typename voronoi_formation<T>::edge_iterator edge_iterator;
- typedef typename voronoi_formation<T>::voronoi_vertices_iterator
- voronoi_vertices_iterator;
-
- voronoi_formation<T> test_beach_line;
- point_2d<T> point1 = make_point_2d<T>(0, 1);
- point_2d<T> point2 = make_point_2d<T>(2, 0);
- point_2d<T> point3 = make_point_2d<T>(2, 4);
-
- std::vector< point_2d<T> > points;
- points.push_back(point1);
- points.push_back(point2);
- points.push_back(point3);
-
- 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);
-
- voronoi_vertices_iterator it = test_beach_line.get_voronoi_vertices().begin();
- BOOST_CHECK_EQUAL(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_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);
-
- 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);
-
- 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(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->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(edge1_1->prev == edge3_2, true);
- BOOST_CHECK_EQUAL(edge2_1->prev == edge1_2, true);
- BOOST_CHECK_EQUAL(edge3_1->prev == edge2_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 == edge1_1, true);
-}
\ No newline at end of file