Subject: [Boost-commit] svn:boost r63178 - in sandbox/SOC/2010/sweepline: boost/sweepline libs/sweepline/test
From: sydorchuk.andriy_at_[hidden]
Date: 2010-06-20 19:10:18
Author: asydorchuk
Date: 2010-06-20 19:10:16 EDT (Sun, 20 Jun 2010)
New Revision: 63178
URL: http://svn.boost.org/trac/boost/changeset/63178
Log:
Fixed voronoi_output generation.
Added unit tests for simple voronoi diagrams.
Changed cicle events processing algorithm (doesn't use node comparison).
Made refactoring.
Added:
sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_formation.hpp (contents, props changed)
sandbox/SOC/2010/sweepline/libs/sweepline/test/node_comparer_test.cpp (contents, props changed)
sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_formation_test.cpp (contents, props changed)
Removed:
sandbox/SOC/2010/sweepline/boost/sweepline/beach_line.hpp
sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_builder.hpp
sandbox/SOC/2010/sweepline/libs/sweepline/test/beach_line_test.cpp
sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_builder_test.cpp
Text files modified:
sandbox/SOC/2010/sweepline/boost/sweepline/event_queue.hpp | 6 ++-
sandbox/SOC/2010/sweepline/boost/sweepline/event_types.hpp | 37 +++++++++----------
sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_output.hpp | 74 ++++++++++++++++++++++++++-------------
sandbox/SOC/2010/sweepline/libs/sweepline/test/Jamfile.v2 | 3 +
sandbox/SOC/2010/sweepline/libs/sweepline/test/event_queue_test.cpp | 3 -
sandbox/SOC/2010/sweepline/libs/sweepline/test/event_types_test.cpp | 2
6 files changed, 75 insertions(+), 50 deletions(-)
Deleted: sandbox/SOC/2010/sweepline/boost/sweepline/beach_line.hpp
==============================================================================
--- sandbox/SOC/2010/sweepline/boost/sweepline/beach_line.hpp 2010-06-20 19:10:16 EDT (Sun, 20 Jun 2010)
+++ (empty file)
@@ -1,456 +0,0 @@
-// Boost sweepline/beach_line.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 <cmath>
-
-#ifndef BOOST_SWEEPLINE_BEACH_LINE
-#define BOOST_SWEEPLINE_BEACH_LINE
-
-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 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;
-
- 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_;
- }
-
- // Returns x coordinate of the rightmost site.
- coordinate_type get_sweepline_coord() const {
- return std::max(left_site_.x(), right_site_.x());
- }
-
- // Returns 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. 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 Edge>
- struct beach_line_node_data {
- beach_line_node_data(Edge &new_edge) : edge(new_edge) {}
-
- Edge &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.
- 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() == node2.get_right_site() &&
- node1.get_right_site() == node2.get_left_site())
- return node1.get_right_site().x() == node1_line;
-
- // Used when we are searching for the bisector during
- // circle events processing. Guarantees correct comparison.
- if (node1.get_left_site() == node2.get_left_site() &&
- node1.get_right_site() == node2.get_right_site())
- return false;
-
- return node1.get_left_site().y() <=
- node2.get_left_site().y();
- }
- else if (node1_line < node2_line)
- return node1.less(node2.get_new_site());
- else
- return !node2.less(node1.get_new_site());
- }
- };
-
- // Beach line data structure. Sweepline sweeps from left to right.
- template <typename Key,
- typename Value,
- typename NodeComparer,
- typename EventQueue,
- typename Output>
- class beach_line {
- public:
- typedef typename Key::Point2D Point2D;
- typedef typename Key::coordinate_type coordinate_type;
- typedef typename Key::site_event_type site_event_type;
- typedef typename Key::circle_event_type circle_event_type;
-
- typedef typename Output::edge_type edge_type;
-
- typedef typename std::map< Key, Value, node_comparer<Key> >::const_iterator beach_line_iterator;
- typedef typename std::pair< beach_line_iterator, bool > beach_line_pair;
-
- // Functor to process events from the event queue.
- struct event_processor {
- explicit event_processor(beach_line &b_line)
- : beach_line_(b_line) {}
-
- 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);
- }
-
- beach_line &beach_line_;
- };
-
- beach_line() : event_processor_(*this) {
- }
-
- // 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(const std::vector<Point2D> &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 (num == 1) {
- // Init beach line with two sites.
- init_beach_line(*sites.begin(), *it);
- } 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);
- output_.init(sites.size());
- }
-
- 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();
- }
- }
-
- 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();
-
- // Add candidate circle to the event queue.
- activate_circle_event(it->first.get_left_site(),
- it->first.get_right_site(),
- site_event);
- } else if (it == beach_line_.begin()) {
- site_arc = it->first.get_left_site();
-
- // Add candidate circle to the event queue.
- activate_circle_event(site_event,
- it->first.get_left_site(),
- it->first.get_right_site());
- } else {
- site_arc = it->first.get_left_site();
- 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.
- activate_circle_event(site1, site2, site_event);
- activate_circle_event(site_event, site2, site3);
- }
-
- // 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)));
- beach_line_.insert(std::pair<Key, Value>(new_right_node, Value(edge)));
- }
-
- void process_circle_event(const circle_event_type &circle_event) {
- // Find the node that corresponds to the given circle event.
- Key new_key(circle_event.get_bisector_left_site(),
- circle_event.get_bisector_right_site());
- beach_line_iterator it_first = beach_line_.find(new_key);
- 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();
-
- // Delete nodes that correspond to the (1st and 2d points) and
- // (2d and 3d points).
- it_last++;
- beach_line_.erase(it_first, it_last);
-
- // Insert new node that corresponds to the (1st and 3d points).
- // Update output.
- Key new_node(site1, site3);
- beach_line_pair it_pair = beach_line_.insert(std::pair<Key, Value>(
- new_node,
- output_.insert_new_edge(site1, site2, site3,
- circle_event,
- bisector1.edge, bisector2.edge)));
- it_first = it_pair.first;
- 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();
- activate_circle_event(site_l2, site_l1, site1);
- }
- }
-
- // 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);
- }
- }
- }
-
- 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(it_first->x, it_first->y, cur_site);
- site_event_type site2 = make_site_event(it_second->x, it_second->y, cur_site+1);
-
- // Create new beach line node.
- beach_line_node 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(first_point.x(), first_point.y(), 0);
- site_event_type site2 = make_site_event(second_point.x(), second_point.y(), 1);
-
- // Create two new beach line nodes.
- beach_line_node new_left_node(site1, site2);
- beach_line_node new_second_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(egge)));
- }
-
- // 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);
- c_event.set_bisector(site2, site3);
- 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) {
- circle_event_type c_event;
- if (create_circle_event(site1, site2, site3, c_event))
- 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_;
- std::map< Key, Value, NodeComparer > beach_line_;
- Output output_;
- };
-
-} // sweepline
-} // boost
-
-#endif
\ No newline at end of file
Modified: sandbox/SOC/2010/sweepline/boost/sweepline/event_queue.hpp
==============================================================================
--- sandbox/SOC/2010/sweepline/boost/sweepline/event_queue.hpp (original)
+++ sandbox/SOC/2010/sweepline/boost/sweepline/event_queue.hpp 2010-06-20 19:10:16 EDT (Sun, 20 Jun 2010)
@@ -34,6 +34,8 @@
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);
@@ -50,16 +52,16 @@
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;
}
Modified: sandbox/SOC/2010/sweepline/boost/sweepline/event_types.hpp
==============================================================================
--- sandbox/SOC/2010/sweepline/boost/sweepline/event_types.hpp (original)
+++ sandbox/SOC/2010/sweepline/boost/sweepline/event_types.hpp 2010-06-20 19:10:16 EDT (Sun, 20 Jun 2010)
@@ -19,8 +19,11 @@
template <typename T>
struct circle_event;
+ template <typename T>
+ class voronoi_formation;
+
// Point in 2D space data structure. Comparators defined in this
- // datascturcture actually define sweepline movement direction.
+ // data structure actually define sweepline movement direction.
template <typename T>
struct point_2d {
public:
@@ -44,9 +47,8 @@
}
// This comparator actually defines sweepline movement direction.
- // Sweepline will move in the horizontal direction:
- // from left to right or from right to left.
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_;
@@ -90,7 +92,9 @@
return point_2d<T>(x,y);
}
- // Site event type. Occurs when sweepline sweeps over one of the initial sites.
+ // 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:
@@ -158,10 +162,14 @@
// 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() {}
@@ -254,8 +262,7 @@
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());
+ 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;
@@ -280,25 +287,17 @@
return sqr_radius_;
}
- void set_bisector(const site_event<T> &left_site,
- const site_event<T> &right_site) {
- bisector_left_site_ = left_site;
- bisector_right_site_ = right_site;
+ void set_bisector(beach_line_iterator iterator) {
+ bisector_node_ = iterator;
}
- const site_event<T> &get_bisector_left_site() const {
- return bisector_left_site_;
+ const beach_line_iterator &get_bisector() const {
+ return bisector_node_;
}
-
- const site_event<T> &get_bisector_right_site() const {
- return bisector_right_site_;
- }
-
private:
point_2d<T> center_;
T sqr_radius_;
- site_event<T> bisector_left_site_;
- site_event<T> bisector_right_site_;
+ beach_line_iterator bisector_node_;
};
template <typename T>
Deleted: sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_builder.hpp
==============================================================================
--- sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_builder.hpp 2010-06-20 19:10:16 EDT (Sun, 20 Jun 2010)
+++ (empty file)
@@ -1,42 +0,0 @@
-// Boost sweepline/voronoi_builder.hpp header file
-
-// Copyright Andrii Sydorchuk 2010.
-// Distributed under the Boost Software License, Version 1.0.
-// (See accompanying file LICENSE_1_0.txt or copy at
-// http://www.boost.org/LICENSE_1_0.txt)
-
-// See http://www.boost.org for updates, documentation, and revision history.
-
-#ifndef BOOST_SWEEPLINE_VORONOI_BUILDER
-#define BOOST_SWEEPLINE_VORONOI_BUILDER
-
-#include <vector>
-
-namespace boost {
-namespace sweepline {
-
- template <typename Point2D, typename BeachLine>
- class voronoi_builder {
- public:
- voronoi_builder() {}
-
- void init(const std::vector<Point2D> &sites) {
- beach_line_.init(sites, output_);
- }
-
- void reset() {
- beach_line_.reset();
- }
-
- void build_voronoi_diagram() {
- beach_line_.run_sweepline();
- }
-
- private:
- BeachLine beach_line_;
- };
-
-} // sweepline
-} // boost
-
-#endif
\ No newline at end of file
Added: sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_formation.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_formation.hpp 2010-06-20 19:10:16 EDT (Sun, 20 Jun 2010)
@@ -0,0 +1,516 @@
+// 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
Modified: sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_output.hpp
==============================================================================
--- sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_output.hpp (original)
+++ sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_output.hpp 2010-06-20 19:10:16 EDT (Sun, 20 Jun 2010)
@@ -77,9 +77,18 @@
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();
@@ -91,24 +100,28 @@
// 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,
+ 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 second site.
+ // 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));
- // Create new half-edge that belongs to the cell with first site.
- edges_.push_back(edge_type(site_index1));
- edge_type &edge1 = edges_.back();
-
// Update pointers to cells.
edge1.cell_record = &cell_records_[site_index1];
edge2.cell_record = &cell_records_[site_index2];
@@ -117,25 +130,25 @@
edge1.twin = &edge2;
edge2.twin = &edge1;
- return edges_.back();
+ return &edge1;
}
- edge_type &insert_new_edge(const site_event_type &site1,
+ 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) {
+ 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();
+ 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.end_point = &new_vertex;
- edge23.twin->start_point = &new_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()));
@@ -155,25 +168,36 @@
// 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;
+ 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_edge1);
+ 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;
+ }
- return edges_.back();
+ 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
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-20 19:10:16 EDT (Sun, 20 Jun 2010)
@@ -13,6 +13,7 @@
test-suite "sweepline"
:
[ run event_queue_test.cpp : : : <link>static ]
- [ run beach_line_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 ]
;
\ No newline at end of file
Deleted: sandbox/SOC/2010/sweepline/libs/sweepline/test/beach_line_test.cpp
==============================================================================
--- sandbox/SOC/2010/sweepline/libs/sweepline/test/beach_line_test.cpp 2010-06-20 19:10:16 EDT (Sun, 20 Jun 2010)
+++ (empty file)
@@ -1,80 +0,0 @@
-// Boost sweepline library beach_line_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/beach_line.hpp>
-#include <boost/sweepline/event_types.hpp>
-using namespace boost::sweepline;
-
-#define BOOST_TEST_MODULE beach_line_test
-#include <boost/test/test_case_template.hpp>
-
-BOOST_AUTO_TEST_CASE_TEMPLATE(node_comparer_test1, T, test_types) {
- typedef beach_line_node< point_2d<T> > bline_node;
- typedef std::map< bline_node, int, node_comparer<bline_node> >::const_iterator bline_it;
-
- std::map< bline_node, int, node_comparer<bline_node> > test_beach_line;
-
- bline_node initial_node(
- make_site_event<T>(static_cast<T>(0), static_cast<T>(0), 0),
- make_site_event<T>(static_cast<T>(0), static_cast<T>(2), 1));
- test_beach_line[initial_node] = 0;
- BOOST_CHECK_EQUAL(test_beach_line.size(), 1);
-
- bline_node new_node1(make_site_event<T>(static_cast<T>(1), static_cast<T>(0), 2));
- bline_node new_node2(make_site_event<T>(static_cast<T>(1), static_cast<T>(1), 3));
- bline_node new_node3(make_site_event<T>(static_cast<T>(1), static_cast<T>(2), 4));
- bline_node new_node4(make_site_event<T>(static_cast<T>(1), static_cast<T>(1.000001), 5));
- bline_node new_node5(make_site_event<T>(static_cast<T>(1), static_cast<T>(0.999999), 6));
-
- bline_it it = test_beach_line.lower_bound(new_node1);
- BOOST_CHECK_EQUAL(it == test_beach_line.begin(), true);
-
- it = test_beach_line.lower_bound(new_node2);
- BOOST_CHECK_EQUAL(it == test_beach_line.begin(), true);
-
- it = test_beach_line.lower_bound(new_node3);
- BOOST_CHECK_EQUAL(it == test_beach_line.end(), true);
-
- it = test_beach_line.lower_bound(new_node4);
- BOOST_CHECK_EQUAL(it == test_beach_line.end(), true);
-
- it = test_beach_line.lower_bound(new_node5);
- BOOST_CHECK_EQUAL(it == test_beach_line.begin(), true);
-
- it = test_beach_line.lower_bound(initial_node);
- BOOST_CHECK_EQUAL(it == test_beach_line.begin(), true);
-}
-
-BOOST_AUTO_TEST_CASE_TEMPLATE(node_comparer_test2, T, test_types) {
- typedef beach_line_node< point_2d<T> > bline_node;
- typedef std::map< bline_node, int, node_comparer<bline_node> >::const_iterator bline_it;
-
- std::map< bline_node, int, node_comparer<bline_node> > test_beach_line;
-
- site_event<T> site1 = make_site_event<T>(static_cast<T>(0), static_cast<T>(0), 0);
- site_event<T> site2 = make_site_event<T>(static_cast<T>(0), static_cast<T>(2), 1);
- bline_node initial_node(site1, site2);
- test_beach_line[initial_node] = 0;
-
- site_event<T> site3 = make_site_event<T>(static_cast<T>(1), static_cast<T>(0), 2);
- bline_node node1(site1, site3);
- bline_node node2(site3, site1);
- test_beach_line.insert(std::pair< bline_node, int>(node1, 1));
- test_beach_line.insert(std::pair< bline_node, int>(node2, 2));
-
- bline_it it = test_beach_line.begin();
- BOOST_CHECK_EQUAL(it->second == 1, true);
-
- ++it;
- BOOST_CHECK_EQUAL(it->second == 2, true);
-
- ++it;
- BOOST_CHECK_EQUAL(it->second == 0, true);
-}
\ 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-20 19:10:16 EDT (Sun, 20 Jun 2010)
@@ -8,8 +8,7 @@
// See http://www.boost.org for updates, documentation, and revision history.
#include "test_type_list.hpp"
-#include <boost/sweepline/event_queue.hpp>
-#include <boost/sweepline/event_types.hpp>
+#include <boost/sweepline/voronoi_formation.hpp>
using namespace boost::sweepline;
#define BOOST_TEST_MODULE event_queue_test
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-20 19:10:16 EDT (Sun, 20 Jun 2010)
@@ -8,7 +8,7 @@
// See http://www.boost.org for updates, documentation, and revision history.
#include "test_type_list.hpp"
-#include <boost/sweepline/event_types.hpp>
+#include <boost/sweepline/voronoi_formation.hpp>
using namespace boost::sweepline;
#define BOOST_TEST_MODULE event_types_test
Added: sandbox/SOC/2010/sweepline/libs/sweepline/test/node_comparer_test.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/test/node_comparer_test.cpp 2010-06-20 19:10:16 EDT (Sun, 20 Jun 2010)
@@ -0,0 +1,102 @@
+// Boost sweepline library node_comparer_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 node_comparer_test
+#include <boost/test/test_case_template.hpp>
+
+BOOST_AUTO_TEST_CASE_TEMPLATE(node_comparer_test1, T, test_types) {
+ typedef beach_line_node< point_2d<T> > bline_node;
+ typedef std::map< bline_node, int, node_comparer<bline_node> >::const_iterator bline_it;
+
+ std::map< bline_node, int, node_comparer<bline_node> > test_beach_line;
+
+ bline_node initial_node(
+ make_site_event<T>(static_cast<T>(0), static_cast<T>(0), 0),
+ make_site_event<T>(static_cast<T>(0), static_cast<T>(2), 1));
+ test_beach_line[initial_node] = 0;
+ BOOST_CHECK_EQUAL(test_beach_line.size(), 1);
+
+ bline_node new_node1(make_site_event<T>(static_cast<T>(1), static_cast<T>(0), 2));
+ bline_node new_node2(make_site_event<T>(static_cast<T>(1), static_cast<T>(1), 3));
+ bline_node new_node3(make_site_event<T>(static_cast<T>(1), static_cast<T>(2), 4));
+ bline_node new_node4(make_site_event<T>(static_cast<T>(1), static_cast<T>(1.000001), 5));
+ bline_node new_node5(make_site_event<T>(static_cast<T>(1), static_cast<T>(0.999999), 6));
+
+ bline_it it = test_beach_line.lower_bound(new_node1);
+ BOOST_CHECK_EQUAL(it == test_beach_line.begin(), true);
+
+ it = test_beach_line.lower_bound(new_node2);
+ BOOST_CHECK_EQUAL(it == test_beach_line.begin(), true);
+
+ it = test_beach_line.lower_bound(new_node3);
+ BOOST_CHECK_EQUAL(it == test_beach_line.end(), true);
+
+ it = test_beach_line.lower_bound(new_node4);
+ BOOST_CHECK_EQUAL(it == test_beach_line.end(), true);
+
+ it = test_beach_line.lower_bound(new_node5);
+ BOOST_CHECK_EQUAL(it == test_beach_line.begin(), true);
+
+ it = test_beach_line.lower_bound(initial_node);
+ BOOST_CHECK_EQUAL(it == test_beach_line.begin(), true);
+}
+
+BOOST_AUTO_TEST_CASE_TEMPLATE(node_comparer_test2, T, test_types) {
+ typedef beach_line_node< point_2d<T> > bline_node;
+ typedef std::map< bline_node, int, node_comparer<bline_node> >::const_iterator bline_it;
+
+ std::map< bline_node, int, node_comparer<bline_node> > test_beach_line;
+
+ site_event<T> site1 = make_site_event<T>(static_cast<T>(0), static_cast<T>(0), 0);
+ site_event<T> site2 = make_site_event<T>(static_cast<T>(0), static_cast<T>(2), 1);
+ bline_node initial_node(site1, site2);
+ test_beach_line[initial_node] = 2;
+
+ site_event<T> site3 = make_site_event<T>(static_cast<T>(1), static_cast<T>(0), 2);
+ bline_node node1(site1, site3);
+ bline_node node2(site3, site1);
+ test_beach_line.insert(std::pair< bline_node, int>(node1, 0));
+ test_beach_line.insert(std::pair< bline_node, int>(node2, 1));
+
+ int cur_value = 0;
+ for (bline_it it = test_beach_line.begin();
+ it != test_beach_line.end();
+ it++, cur_value++)
+ BOOST_CHECK_EQUAL(it->second, cur_value);
+}
+
+BOOST_AUTO_TEST_CASE_TEMPLATE(node_comparer_test3, T, test_types) {
+ typedef beach_line_node< point_2d<T> > bline_node;
+ typedef std::map< bline_node, int, node_comparer<bline_node> >::const_iterator bline_it;
+
+ std::map< bline_node, int, node_comparer<bline_node> > test_beach_line;
+
+ site_event<T> site1 = make_site_event<T>(static_cast<T>(0), static_cast<T>(1), 0);
+ site_event<T> site2 = make_site_event<T>(static_cast<T>(2), static_cast<T>(0), 1);
+ site_event<T> site3 = make_site_event<T>(static_cast<T>(2), static_cast<T>(4), 2);
+ bline_node initial_node1(site1, site2);
+ bline_node initial_node2(site2, site1);
+ test_beach_line[initial_node1] = 0;
+ test_beach_line[initial_node2] = 1;
+
+ bline_node new_node1(site1, site3);
+ bline_node new_node2(site3, site1);
+ test_beach_line[new_node1] = 2;
+ test_beach_line[new_node2] = 3;
+
+ int cur_value = 0;
+ for (bline_it it = test_beach_line.begin();
+ it != test_beach_line.end();
+ it++, cur_value++)
+ BOOST_CHECK_EQUAL(it->second, cur_value);
+}
\ No newline at end of file
Deleted: sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_builder_test.cpp
==============================================================================
--- sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_builder_test.cpp 2010-06-20 19:10:16 EDT (Sun, 20 Jun 2010)
+++ (empty file)
@@ -1,20 +0,0 @@
-// 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/beach_line.hpp>
-//#include <boost/sweepline/event_queue.hpp>
-//#include <boost/sweepline/event_types.hpp>
-//#include <boost/sweepline/voronoi_builder.hpp>
-//
-//#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) {
-//}
\ No newline at end of file
Added: sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_formation_test.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_formation_test.cpp 2010-06-20 19:10:16 EDT (Sun, 20 Jun 2010)
@@ -0,0 +1,138 @@
+// 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