|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r62968 - in sandbox/SOC/2010/sweepline: boost/sweepline libs/sweepline/test
From: sydorchuk.andriy_at_[hidden]
Date: 2010-06-15 07:43:36
Author: asydorchuk
Date: 2010-06-15 07:43:34 EDT (Tue, 15 Jun 2010)
New Revision: 62968
URL: http://svn.boost.org/trac/boost/changeset/62968
Log:
Updated circle events definition that doesn't require sqrt computation.
Added proper arithmetic for comparison for circle events and site events.
Updated algorithm using new circle events definition.
Added event types unit tests.
Added:
sandbox/SOC/2010/sweepline/libs/sweepline/test/event_types_test.cpp (contents, props changed)
Text files modified:
sandbox/SOC/2010/sweepline/boost/sweepline/beach_line.hpp | 189 ++++++++++++++++++++++++++++-----------
sandbox/SOC/2010/sweepline/boost/sweepline/event_queue.hpp | 10 +
sandbox/SOC/2010/sweepline/boost/sweepline/event_types.hpp | 124 ++++++++++++++++++++++---
sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_builder.hpp | 21 +---
sandbox/SOC/2010/sweepline/libs/sweepline/test/Jamfile.v2 | 1
sandbox/SOC/2010/sweepline/libs/sweepline/test/event_queue_test.cpp | 21 ++--
6 files changed, 268 insertions(+), 98 deletions(-)
Modified: sandbox/SOC/2010/sweepline/boost/sweepline/beach_line.hpp
==============================================================================
--- sandbox/SOC/2010/sweepline/boost/sweepline/beach_line.hpp (original)
+++ sandbox/SOC/2010/sweepline/boost/sweepline/beach_line.hpp 2010-06-15 07:43:34 EDT (Tue, 15 Jun 2010)
@@ -17,6 +17,15 @@
namespace boost {
namespace sweepline {
+ // Represents bisector made by two arcs that correspond to the left and
+ // right points. Arc is defined as curve with points equidistant from the
+ // point and from the sweepline.
+ // Let sweepline sweep from left to right and it's current coordinate
+ // be x0, point 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:
@@ -27,36 +36,50 @@
beach_line_node() {}
+ // Constructs degenerate bisector, used to search arc that is above
+ // given point. The input to the constructor is the site event point.
explicit beach_line_node(const Point2D &new_point) {
left_point_ = new_point;
right_point_ = new_point;
}
- beach_line_node(const Point2D &left_point, const Point2D &right_point) {
+ // Constructs new bisector. The input to the constructor is two points
+ // which create bisector. The order of points is important.
+ beach_line_node(const Point2D &left_point,
+ const Point2D &right_point) {
left_point_ = left_point;
right_point_ = right_point;
}
+ // Returns left point of the bisector.
const Point2D &get_left_point() const {
return left_point_;
}
+ // Returns right point of the bisector.
const Point2D &get_right_point() const {
return right_point_;
}
+ // Returns x coordinate of the rightmost point.
coordinate_type get_sweepline_coord() const {
return std::max(left_point_.x(), right_point_.x());
}
+ // Returns rightmost point.
const Point2D& get_new_point() const {
if (left_point_.x() > right_point_.x())
return left_point_;
return right_point_;
}
- Point2D get_intersection_point(bool use_right_point, const Point2D &new_point) const {
- const Point2D &use_point = (use_right_point) ? right_point_ : left_point_;
+ // Returns intersection point of the given arc with horizontal line
+ // going through new_point. If use_right_point is true we look for the
+ // intersection with right arc of the bisector, else with left arc.
+ Point2D get_intersection_point(bool use_right_point,
+ const Point2D &new_point) const {
+ const Point2D &use_point = (use_right_point) ?
+ right_point_ : left_point_;
coordinate_type vertex_x = ((new_point.y() - use_point.y()) *
(new_point.y() - use_point.y()) /
(use_point.x() - new_point.x()) +
@@ -65,6 +88,16 @@
return make_point_2d(vertex_x, new_point.y());
}
+ // Returns true if horizontal line going through new_point intersects
+ // right arc at first, else returns false. Used during nodes
+ // comparison.
+ // Let x0 be sweepline coordinate, left point coordinates be (x1, y1),
+ // right point 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 point (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 Point2D &new_point) const {
coordinate_type sweepline_coord = new_point.x();
coordinate_type new_node_coord = new_point.y();
@@ -97,14 +130,29 @@
public:
typedef typename BeachLineNode::coordinate_type coordinate_type;
- bool operator() (const BeachLineNode &node1, const BeachLineNode &node2) const {
+ // 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 go first.
+ bool operator() (const BeachLineNode &node1,
+ const BeachLineNode &node2) const {
+ // Get x coordinate of the righmost point 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 sweepline.
if (node1_line == node2_line) {
+ // Let A be the new site event point, and B the point 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 is a site event.
if (node1.get_left_point() == node2.get_right_point() &&
node1.get_right_point() == node2.get_left_point())
return node1.get_right_point().x() == node1_line;
- return node1.get_left_point().y() <= node2.get_left_point().y();
+ return node1.get_left_point().y() <=
+ node2.get_left_point().y();
}
else if (node1_line < node2_line)
return node1.less(node2.get_new_point());
@@ -113,7 +161,11 @@
}
};
- template <typename Key, typename Value, typename NodeComparer, typename EventQueue>
+ // Beach line data structure. Sweepline sweeps from left to right.
+ template <typename Key,
+ typename Value,
+ typename NodeComparer,
+ typename EventQueue>
class beach_line {
public:
typedef typename Key::Point2D Point2D;
@@ -123,43 +175,34 @@
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) {}
+ 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);
+ beach_line_.process_site_event(site_event);
}
void operator()(const circle_event_type &circle_event) {
- beach_line_->process_circle_event(circle_event);
+ beach_line_.process_circle_event(circle_event);
}
- beach_line* beach_line_;
+ beach_line &beach_line_;
};
- beach_line() {
- event_queue_ = new EventQueue;
- event_processor_ = new event_processor(this);
- }
-
- ~beach_line() {
- if (event_queue_) {
- delete event_queue_;
- event_queue_ = NULL;
- }
- if (event_processor_) {
- delete event_processor_;
- event_processor_ = NULL;
- }
- }
+ 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 sweepline 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
+ skip = 1;
} else {
std::vector<Point2D>::const_iterator it = sites.begin();
while(it != sites.end() && it->x() == sites.begin()->x()) {
@@ -168,12 +211,15 @@
}
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);
}
}
- event_queue_->init(sites, skip);
+ // Init event queue with the rest of the sites.
+ event_queue_.init(sites, skip);
}
void reset() {
@@ -182,13 +228,16 @@
}
void run_sweepline() {
- while (!event_queue_->empty()) {
- event_queue_->process_top_event(*event_processor_);
- event_queue_->pop();
+ // 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.get_point());
beach_line_iterator it = beach_line_.lower_bound(new_key);
@@ -198,12 +247,16 @@
it--;
point_arc = it->first.get_right_point();
voronoi_vertex = it->first.get_intersection_point(true, site_event.get_point());
+
+ // Add candidate circle to the event queue.
activate_circle_event(it->first.get_left_point(),
it->first.get_right_point(),
site_event.get_point());
} else if (it == beach_line_.begin()) {
point_arc = it->first.get_left_point();
voronoi_vertex = it->first.get_intersection_point(false, site_event.get_point());
+
+ // Add candidate circle to the event queue.
activate_circle_event(site_event.get_point(),
it->first.get_left_point(),
it->first.get_right_point());
@@ -216,18 +269,25 @@
it--;
const Point2D &point1 = it->first.get_right_point();
+ // Remove candidate circle from the event queue.
deactivate_circle_event(point1, point2, point3);
+
+ // Add candidate circles to the event queue.
activate_circle_event(point1, point2, site_event.get_point());
activate_circle_event(site_event.get_point(), point2, point3);
}
+ // Create two new nodes.
Key new_left_node(point_arc, site_event.get_point());
Key new_right_node(site_event.get_point(), point_arc);
+
+ // Insert two new nodes into the binary search tree.
beach_line_.insert(std::pair<Key, Value>(new_left_node, Value()));
beach_line_.insert(std::pair<Key, Value>(new_right_node, Value()));
}
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_point(),
circle_event.get_bisector_right_point());
beach_line_iterator it_first = beach_line_.find(new_key);
@@ -236,13 +296,20 @@
if (it_first == beach_line_.end())
return;
-
+ // This will be the second and the third sites that create
+ // given circle event.
Point2D point2 = it_first->first.get_left_point();
Point2D point3 = it_first->first.get_right_point();
it_first--;
it_last++;
+ // This will be the first site that creates given circle event.
Point2D point1 = it_first->first.get_left_point();
+
+ // Delete nodes that correspond to the (1st and 2d points) and
+ // (2d and 3d points).
beach_line_.erase(it_first, it_last);
+
+ // Insert new node that corresponds to the (1st and 3d points).
Key new_node(point1, point3);
beach_line_pair it_pair =
beach_line_.insert(std::pair<Key, Value>(new_node, Value()));
@@ -250,6 +317,8 @@
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 Point2D &point_l1 = it_first->first.get_left_point();
@@ -261,6 +330,8 @@
}
}
+ // Check the new triplets formed by the neighboring arcs
+ // for potential circle events. Check right.
it_last++;
if (it_last != beach_line_.end()) {
const Point2D &point_r1 = it_last->first.get_right_point();
@@ -288,55 +359,69 @@
}
}
- void init_beach_line(const Point2D &first_point, const Point2D &second_point) {
+ void init_beach_line(const Point2D &first_point,
+ const Point2D &second_point) {
beach_line_node new_left_node(firs_point, second_point);
beach_line_node new_second_node(second_point, first_point);
beach_line_.insert(std::pair<Key, Value>(new_left_node, Value()));
beach_line_.insert(std::pair<Key, Value>(new_right_node, Value()));
}
+ // Create circle event from given three points.
bool create_circle_event(const Point2D &point1,
const Point2D &point2,
const Point2D &point3,
circle_event_type &c_event) const {
- coordinate_type a = (point1.x() - point2.x())*(point2.y() - point3.y()) -
- (point1.y() - point2.y())*(point2.x() - point3.x());
- if (a <= static_cast<coordinate_type>(0))
+ coordinate_type a = (point1.x() - point2.x())*
+ (point2.y() - point3.y())-
+ (point1.y() - point2.y())*
+ (point2.x() - point3.x());
+ // Check if bisectors intersect.
+ if (a == static_cast<coordinate_type>(0))
return false;
- coordinate_type b1 = (point1.x() - point2.x())*(point1.x() + point2.x()) +
- (point1.y() - point2.y())*(point1.y() + point2.y());
- coordinate_type b2 = (point2.x() - point3.x())*(point2.x() + point3.x()) +
- (point2.y() - point3.y())*(point2.y() + point3.y());
- coordinate_type c_x = (b1*(point2.y() - point3.y()) - b2*(point1.y() - point2.y())) / a *
- static_cast<coordinate_type>(0.5);
- coordinate_type c_y = (b2*(point1.x() - point2.x()) - b1*(point2.x() - point3.x())) / a *
+ coordinate_type b1 = (point1.x() - point2.x())*
+ (point1.x() + point2.x())+
+ (point1.y() - point2.y())*
+ (point1.y() + point2.y());
+ coordinate_type b2 = (point2.x() - point3.x())*
+ (point2.x() + point3.x())+
+ (point2.y() - point3.y())*
+ (point2.y() + point3.y());
+ coordinate_type c_x = (b1*(point2.y() - point3.y()) -
+ b2*(point1.y() - point2.y())) / a *
static_cast<coordinate_type>(0.5);
- coordinate_type sqr_radius = (c_x-point1.x())*(c_x-point1.x()) + (c_y-point1.y())*(c_y-point1.y());
- coordinate_type radius = static_cast<coordinate_type>(sqr_radius);
- c_event = make_circle_event(c_x + radius, c_y);
+ coordinate_type c_y = (b2*(point1.x() - point2.x()) -
+ b1*(point2.x() - point3.x())) / a *
+ static_cast<coordinate_type>(0.5);
+ coordinate_type sqr_radius = (c_x-point1.x())*(c_x-point1.x()) +
+ (c_y-point1.y())*(c_y-point1.y());
+ // Create new circle event;
+ c_event = make_circle_event(c_x, c_y, sqr_radius);
c_event.set_bisector(point2, point3);
return true;
}
+ // Add new circle event to the event queue.
void activate_circle_event(const Point2D &point1,
const Point2D &point2,
- const Point2D &point3) const {
+ const Point2D &point3) {
circle_event_type c_event;
if (create_circle_event(point1, point2, point3, c_event))
- event_queue_->push(c_event);
+ event_queue_.push(c_event);
}
+ // Remove circle event from the event queue.
void deactivate_circle_event(const Point2D &point1,
const Point2D &point2,
- const Point2D &point3) const {
+ const Point2D &point3) {
circle_event_type c_event;
if (create_circle_event(point1, point2, point3, c_event))
- event_queue_->deactivate_event(c_event);
+ event_queue_.deactivate_event(c_event);
}
private:
- EventQueue* event_queue_;
- event_processor* event_processor_;
+ EventQueue event_queue_;
+ event_processor event_processor_;
std::map< Key, Value, NodeComparer > beach_line_;
};
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-15 07:43:34 EDT (Tue, 15 Jun 2010)
@@ -78,11 +78,11 @@
circle_events_.pop();
}
- void push(circle_event_type &circle_event) {
+ void push(const circle_event_type &circle_event) {
circle_events_.push(circle_event);
}
- void deactivate_event(circle_event_type &circle_event) {
+ void deactivate_event(const circle_event_type &circle_event) {
deactivated_events_.push(circle_event);
}
@@ -93,7 +93,7 @@
void remove_not_active_events() {
while (!circle_events_.empty() && !deactivated_events_.empty() &&
- circle_events_.top() == deactivated_events_.top()) {
+ circle_events_.top().equals(deactivated_events_.top())) {
circle_events_.pop();
deactivated_events_.pop();
}
@@ -106,7 +106,9 @@
else if (circle_events_.empty())
return SITE_EVENT;
else {
- if (site_events_iterator_->get_point() <= circle_events_.top().get_point())
+ // 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;
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-15 07:43:34 EDT (Tue, 15 Jun 2010)
@@ -19,6 +19,8 @@
template <typename T>
struct circle_event;
+ // Point in 2D space data structure. Comparators defined in this
+ // datascturcture actually define sweepline movement direction.
template <typename T>
struct point_2d {
public:
@@ -38,9 +40,12 @@
}
bool operator!=(const point_2d &point) const {
- return (this->x_ != point.x) || (this->y_ != point.y());
+ return (this->x_ != point.x()) || (this->y_ != point.y());
}
+ // 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 {
if (this->x_ != point.x_)
return this->x_ < point.x_;
@@ -85,6 +90,7 @@
return point_2d<T>(x,y);
}
+ // Site event type. Occurs when sweepline sweeps over one of the initial sites.
template <typename T>
struct site_event {
public:
@@ -139,8 +145,14 @@
return site_event<T>(x,y);
}
- struct BeachLineNode;
-
+ // 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).
template <typename T>
struct circle_event {
public:
@@ -148,42 +160,119 @@
circle_event() {}
- circle_event(T x, T y) : point_(x, y) {}
+ 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 {
- return point_ == c_event.get_point();
+ 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 point_ != c_event.get_point();
+ return !((*this) == c_event);
}
bool operator<(const circle_event &c_event) const {
- return point_ < c_event.get_point();
+ 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 point_ <= c_event.get_point();
+ return !(c_event < (*this));
}
bool operator>(const circle_event &c_event) const {
- return point_ > c_event.get_point();
+ return c_event < (*this);
}
bool operator>=(const circle_event &c_event) const {
- return point_ >= c_event.get_point();
+ 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 point_.x();
+ return center_.x();
}
coordinate_type y() const {
- return point_.y();
+ return center_.y();
}
- const point_2d<T> &get_point() const {
- return point_;
+ const point_2d<T> &get_center() const {
+ return center_;
+ }
+
+ const T &get_sqr_radius() const {
+ return sqr_radius_;
}
void set_bisector(const point_2d<T> &left_point, const point_2d<T> &right_point) {
@@ -200,14 +289,15 @@
}
private:
- point_2d<T> point_;
+ point_2d<T> center_;
+ T sqr_radius_;
point_2d<T> bisector_left_point_;
point_2d<T> bisector_right_point_;
};
template <typename T>
- circle_event<T> make_circle_event(T x, T y) {
- return circle_event<T>(x,y);
+ 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
Modified: sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_builder.hpp
==============================================================================
--- sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_builder.hpp (original)
+++ sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_builder.hpp 2010-06-15 07:43:34 EDT (Tue, 15 Jun 2010)
@@ -15,34 +15,25 @@
namespace boost {
namespace sweepline {
-template <typename Point2D, typename BeachLine>
+ template <typename Point2D, typename BeachLine>
class voronoi_builder {
public:
- voronoi_builder() {
- beach_line_ = new BeachLine;
- }
-
- ~voronoi_builder() {
- if (beach_line_) {
- delete beach_line_;
- beach_line_ = NULL;
- }
- }
+ voronoi_builder() {}
void init(const std::vector<Point2D> &sites) {
- beach_line_->init(sites);
+ beach_line_.init(sites);
}
void reset() {
- beach_line_->reset();
+ beach_line_.reset();
}
void build_voronoi_diagram() {
- beach_line_->run_sweepline();
+ beach_line_.run_sweepline();
}
private:
- BeachLine* beach_line_;
+ BeachLine beach_line_;
};
} // 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-15 07:43:34 EDT (Tue, 15 Jun 2010)
@@ -14,4 +14,5 @@
:
[ run event_queue_test.cpp : : : <link>static ]
[ run beach_line_test.cpp : : : <link>static ]
+ [ run event_types_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-15 07:43:34 EDT (Tue, 15 Jun 2010)
@@ -1,10 +1,10 @@
// Boost sweepline library event_queue_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"
@@ -33,7 +33,8 @@
}
void operator()(const circle_event_type &circle_event) {
- x = circle_event.x();
+ x = circle_event.x() +
+ sqrt(static_cast<coordinate_type>(circle_event.get_sqr_radius()));
y = circle_event.y();
}
@@ -66,15 +67,15 @@
CHECK_TOP_ELEMENT_EQUALITY(test_processor, 1, 1);
for (int i = 5; i < 10; i++) {
- T x = static_cast<T>(10-i);
+ T x = static_cast<T>(-i);
T y = static_cast<T>(10-i);
- event_q.push(make_circle_event(x, y));
+ event_q.push(make_circle_event(x, y, static_cast<T>(100)));
}
for (int i = 0; i < 5; i++) {
- T x = static_cast<T>(10-i);
+ T x = static_cast<T>(-i);
T y = static_cast<T>(10-i-1);
- event_q.push(make_circle_event(x, y));
+ event_q.push(make_circle_event(x, y, static_cast<T>(100)));
}
for (int i = 0; i < 10; i++) {
@@ -88,7 +89,7 @@
CHECK_TOP_ELEMENT_EQUALITY(test_processor, 1 + i/2, 1 + (i-1)/2);
event_q.pop();
}
-
+
BOOST_CHECK_EQUAL(event_q.empty(), true);
}
@@ -99,13 +100,13 @@
for (int i = 0; i < 10; i++) {
T x = static_cast<T>(10-i);
T y = static_cast<T>(10-i);
- event_q.push(make_circle_event(x, y));
+ event_q.push(make_circle_event(x, y, static_cast<T>(0)));
}
for (int i = 0; i < 5; i++) {
T x = static_cast<T>(10-2*i-1);
T y = static_cast<T>(10-2*i-1);
- event_q.deactivate_event(make_circle_event(x, y));
+ event_q.deactivate_event(make_circle_event(x, y, static_cast<T>(0)));
}
for (int i = 0; i < 5; i++) {
Added: sandbox/SOC/2010/sweepline/libs/sweepline/test/event_types_test.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/test/event_types_test.cpp 2010-06-15 07:43:34 EDT (Tue, 15 Jun 2010)
@@ -0,0 +1,128 @@
+// Boost sweepline library event_types_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/event_types.hpp>
+using namespace boost::sweepline;
+
+#define BOOST_TEST_MODULE event_types_test
+#include <boost/test/test_case_template.hpp>
+
+#define EVENT_TYPES_CHECK_COMPARISON(A, B, ARR) \
+ BOOST_CHECK_EQUAL((A)<(B), (ARR)[0]); \
+ BOOST_CHECK_EQUAL((A)>(B), (ARR)[1]); \
+ BOOST_CHECK_EQUAL((A)<=(B), (ARR)[2]); \
+ BOOST_CHECK_EQUAL((A)>=(B), (ARR)[3]); \
+ BOOST_CHECK_EQUAL((A)==(B), (ARR)[4]); \
+ BOOST_CHECK_EQUAL((A)!=(B), (ARR)[5])
+
+BOOST_AUTO_TEST_CASE_TEMPLATE(point_2d_test1, T, test_types) {
+ point_2d<T> point1 = make_point_2d(static_cast<T>(1), static_cast<T>(1.05));
+ point_2d<T> point2;
+
+ BOOST_CHECK_EQUAL(point1.x(), static_cast<T>(1));
+ BOOST_CHECK_EQUAL(point1.y(), static_cast<T>(1.05));
+
+ point2 = make_point_2d(static_cast<T>(0.999999), static_cast<T>(1));
+ bool arr1[] = { false, true, false, true, false, true };
+ EVENT_TYPES_CHECK_COMPARISON(point1, point2, arr1);
+
+ point2 = make_point_2d(static_cast<T>(1), static_cast<T>(1.1));
+ bool arr2[] = { true, false, true, false, false, true };
+ EVENT_TYPES_CHECK_COMPARISON(point1, point2, arr2);
+
+ point2 = make_point_2d(static_cast<T>(1), static_cast<T>(1.05));
+ bool arr3[] = { false, false, true, true, true, false };
+ EVENT_TYPES_CHECK_COMPARISON(point1, point2, arr3);
+}
+
+BOOST_AUTO_TEST_CASE_TEMPLATE(site_event_test1, T, test_types) {
+ site_event<T> site1 = make_site_event(static_cast<T>(1),
+ static_cast<T>(1.05));
+ site_event<T> site2;
+
+ BOOST_CHECK_EQUAL(site1.x(), static_cast<T>(1));
+ BOOST_CHECK_EQUAL(site1.y(), static_cast<T>(1.05));
+
+ site2 = make_site_event(static_cast<T>(0.999999), static_cast<T>(1));
+ bool arr1[] = { false, true, false, true, false, true };
+ EVENT_TYPES_CHECK_COMPARISON(site1, site2, arr1);
+
+ site2 = make_site_event(static_cast<T>(1), static_cast<T>(1.1));
+ bool arr2[] = { true, false, true, false, false, true };
+ EVENT_TYPES_CHECK_COMPARISON(site1, site2, arr2);
+
+ site2 = make_site_event(static_cast<T>(1), static_cast<T>(1.05));
+ bool arr3[] = { false, false, true, true, true, false };
+ EVENT_TYPES_CHECK_COMPARISON(site1, site2, arr3);
+}
+
+BOOST_AUTO_TEST_CASE_TEMPLATE(circle_event_test1, T, test_types) {
+ circle_event<T> circle1 = make_circle_event<T>(static_cast<T>(1),
+ static_cast<T>(2),
+ static_cast<T>(4));
+ circle_event<T> circle2;
+
+ BOOST_CHECK_EQUAL(circle1.x(), static_cast<T>(1));
+ BOOST_CHECK_EQUAL(circle1.y(), static_cast<T>(2));
+ BOOST_CHECK_EQUAL(circle1.get_sqr_radius(), static_cast<T>(4));
+
+ circle2 = make_circle_event<T>(static_cast<T>(1),
+ static_cast<T>(2),
+ static_cast<T>(4));
+ bool arr1[] = { false, false, true, true, true, false };
+ EVENT_TYPES_CHECK_COMPARISON(circle1, circle2, arr1);
+
+ circle2 = make_circle_event<T>(static_cast<T>(1),
+ static_cast<T>(3),
+ static_cast<T>(4));
+ bool arr2[] = { true, false, true, false, false, true };
+ EVENT_TYPES_CHECK_COMPARISON(circle1, circle2, arr2);
+
+ circle2 = make_circle_event<T>(static_cast<T>(1),
+ static_cast<T>(2),
+ static_cast<T>(5));
+ bool arr3[] = { true, false, true, false, false, true };
+ EVENT_TYPES_CHECK_COMPARISON(circle1, circle2, arr3);
+
+
+ circle2 = make_circle_event<T>(static_cast<T>(0),
+ static_cast<T>(2),
+ static_cast<T>(4));
+ bool arr4[] = { false, true, false, true, false, true };
+ EVENT_TYPES_CHECK_COMPARISON(circle1, circle2, arr4);
+
+ circle2 = make_circle_event<T>(static_cast<T>(0),
+ static_cast<T>(0),
+ static_cast<T>(10));
+ bool arr5[] = { true, false, true, false, false, true };
+ EVENT_TYPES_CHECK_COMPARISON(circle1, circle2, arr5);
+}
+
+BOOST_AUTO_TEST_CASE_TEMPLATE(circle_event_test2, T, test_types) {
+ circle_event<T> circle = make_circle_event<T>(static_cast<T>(1),
+ static_cast<T>(2),
+ static_cast<T>(4));
+ site_event<T> site;
+
+ site = make_site_event<T>(0, 100);
+ BOOST_CHECK_EQUAL(circle.compare(site), 1);
+
+ site = make_site_event<T>(3, 0);
+ BOOST_CHECK_EQUAL(circle.compare(site), 1);
+
+ site = make_site_event<T>(3, 2);
+ BOOST_CHECK_EQUAL(circle.compare(site), 0);
+
+ site = make_site_event<T>(3, 2);
+ BOOST_CHECK_EQUAL(circle.compare(site), 0);
+
+ site = make_site_event<T>(4, 2);
+ BOOST_CHECK_EQUAL(circle.compare(site), -1);
+}
\ No newline at end of file
Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk