Subject: [Boost-commit] svn:boost r63064 - in sandbox/SOC/2010/sweepline: boost/sweepline libs/sweepline/test
From: sydorchuk.andriy_at_[hidden]
Date: 2010-06-17 17:08:26
Author: asydorchuk
Date: 2010-06-17 17:08:25 EDT (Thu, 17 Jun 2010)
New Revision: 63064
URL: http://svn.boost.org/trac/boost/changeset/63064
Log:
Added output generation (half-edges).
Updated event processing step.
Added:
sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_output.hpp (contents, props changed)
Text files modified:
sandbox/SOC/2010/sweepline/boost/sweepline/beach_line.hpp | 353 +++++++++++++++++++++------------------
sandbox/SOC/2010/sweepline/boost/sweepline/event_queue.hpp | 8
sandbox/SOC/2010/sweepline/boost/sweepline/event_types.hpp | 30 ++-
sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_builder.hpp | 2
sandbox/SOC/2010/sweepline/libs/sweepline/test/beach_line_test.cpp | 55 +----
sandbox/SOC/2010/sweepline/libs/sweepline/test/event_types_test.cpp | 20 +-
6 files changed, 241 insertions(+), 227 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-17 17:08:25 EDT (Thu, 17 Jun 2010)
@@ -18,10 +18,10 @@
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.
+ // 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, point coordinates be (x1, y1). In this case equation of the arc
+ // 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
@@ -37,92 +37,75 @@
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;
+ // 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 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;
+ // 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 left point of the bisector.
- const Point2D &get_left_point() const {
- return left_point_;
+ // Returns the left site of the bisector.
+ const site_event_type &get_left_site() const {
+ return left_site_;
}
- // Returns right point of the bisector.
- const Point2D &get_right_point() const {
- return right_point_;
+ // Returns the right site of the bisector.
+ const site_event_type &get_right_site() const {
+ return right_site_;
}
- // Returns x coordinate of the rightmost point.
+ // Returns x coordinate of the rightmost site.
coordinate_type get_sweepline_coord() const {
- return std::max(left_point_.x(), right_point_.x());
+ return std::max(left_site_.x(), right_site_.x());
}
- // Returns rightmost point.
- const Point2D& get_new_point() const {
- if (left_point_.x() > right_point_.x())
- return left_point_;
- return right_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()) +
- use_point.x() + new_point.x()) *
- static_cast<coordinate_type>(0.5);
- return make_point_2d(vertex_x, new_point.y());
+ // 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_point intersects
+ // 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 point coordinates be (x1, y1),
- // right point coordinates be (x2, y2). Equations of the arcs will be:
+ // 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 point (x*, y*) intersects second arc
+ // 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 Point2D &new_point) const {
- coordinate_type sweepline_coord = new_point.x();
- coordinate_type new_node_coord = new_point.y();
- coordinate_type a1 = left_point_.x() - sweepline_coord;
- coordinate_type a2 = right_point_.x() - sweepline_coord;
- coordinate_type b1 = new_node_coord - left_point_.y();
- coordinate_type b2 = new_node_coord - right_point_.y();
- coordinate_type c = left_point_.x() - right_point_.x();
+ 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:
- Point2D left_point_;
- Point2D right_point_;
+ site_event_type left_site_;
+ site_event_type right_site_;
};
- template <typename Point2D>
+ // 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 {
- 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_data(Edge &new_edge) : edge(new_edge) {}
- beach_line_node_data() {}
- private:
+ Edge &edge;
};
template <typename BeachLineNode>
@@ -132,32 +115,39 @@
// 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.
+ // 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 point from both nodes.
+ // 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 sweepline.
+ // 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 point that
+ // 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 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();
+ // (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_point());
+ return node1.less(node2.get_new_site());
else
- return !node2.less(node1.get_new_point());
+ return !node2.less(node1.get_new_site());
}
};
@@ -165,13 +155,17 @@
template <typename Key,
typename Value,
typename NodeComparer,
- typename EventQueue>
+ 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;
@@ -191,11 +185,12 @@
beach_line &beach_line_;
};
- beach_line() : event_processor_(*this) {}
+ 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.
+ // 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());
@@ -220,11 +215,13 @@
}
// 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() {
@@ -238,82 +235,87 @@
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());
+ Key new_key(site_event);
beach_line_iterator it = beach_line_.lower_bound(new_key);
- Point2D point_arc;
- Point2D voronoi_vertex;
+ site_event_type site_arc;
if (it == beach_line_.end()) {
it--;
- point_arc = it->first.get_right_point();
- voronoi_vertex = it->first.get_intersection_point(true, site_event.get_point());
+ site_arc = it->first.get_right_site();
// Add candidate circle to the event queue.
- activate_circle_event(it->first.get_left_point(),
- it->first.get_right_point(),
- site_event.get_point());
+ activate_circle_event(it->first.get_left_site(),
+ it->first.get_right_site(),
+ site_event);
} 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());
+ site_arc = it->first.get_left_site();
// Add candidate circle to the event queue.
- activate_circle_event(site_event.get_point(),
- it->first.get_left_point(),
- it->first.get_right_point());
+ activate_circle_event(site_event,
+ it->first.get_left_site(),
+ it->first.get_right_site());
} else {
- point_arc = it->first.get_left_point();
- voronoi_vertex = it->first.get_intersection_point(false, site_event.get_point());
-
- const Point2D &point2 = it->first.get_left_point();
- const Point2D &point3 = it->first.get_right_point();
+ 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 Point2D &point1 = it->first.get_right_point();
+ const site_event_type &site1 = it->first.get_right_site();
// Remove candidate circle from the event queue.
- deactivate_circle_event(point1, point2, point3);
+ deactivate_circle_event(site1, site2, site3);
// 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);
+ activate_circle_event(site1, site2, site_event);
+ activate_circle_event(site_event, site2, site3);
}
// Create two new nodes.
- Key new_left_node(point_arc, site_event.get_point());
- Key new_right_node(site_event.get_point(), point_arc);
+ 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.
- beach_line_.insert(std::pair<Key, Value>(new_left_node, Value()));
- beach_line_.insert(std::pair<Key, Value>(new_right_node, Value()));
+ // 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_point(),
- circle_event.get_bisector_right_point());
+ // 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;
- if (it_first == beach_line_.end())
- return;
+ // 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();
- // 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();
+ // Get second bisector;
+ Value bisector2 = it_first->second;
+
+ // Get first bisector;
it_first--;
- it_last++;
- // This will be the first site that creates given circle event.
- Point2D point1 = it_first->first.get_left_point();
+ 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).
- Key new_node(point1, point3);
- beach_line_pair it_pair =
- beach_line_.insert(std::pair<Key, Value>(new_node, Value()));
-
+ // 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;
@@ -321,12 +323,12 @@
// for potential circle events. Check left.
if (it_first != beach_line_.begin()) {
it_first--;
- const Point2D &point_l1 = it_first->first.get_left_point();
- deactivate_circle_event(point_l1, point1, point2);
+ 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 Point2D &point_l2 = it_first->first.get_left_point();
- activate_circle_event(point_l2, point_l1, point1);
+ const site_event_type &site_l2 = it_first->first.get_left_site();
+ activate_circle_event(site_l2, site_l1, site1);
}
}
@@ -334,13 +336,13 @@
// for potential circle events. Check right.
it_last++;
if (it_last != beach_line_.end()) {
- const Point2D &point_r1 = it_last->first.get_right_point();
- deactivate_circle_event(point2, point3, point_r1);
+ 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 Point2D &point_r2 = it_last->first.get_right_point();
- activate_circle_event(point3, point_r1, point_r2);
+ const site_event_type &site_r2 = it_last->first.get_right_site();
+ activate_circle_event(site3, site_r1, site_r2);
}
}
}
@@ -351,69 +353,91 @@
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) {
- beach_line_node new_node(*it_first, *it_second);
- beach_line_.insert(std::pair<Key, Value>(new_node, Value()));
+ 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) {
- 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()));
+ 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 given three points.
- bool create_circle_event(const Point2D &point1,
- const Point2D &point2,
- const Point2D &point3,
+ // 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 = (point1.x() - point2.x())*
- (point2.y() - point3.y())-
- (point1.y() - point2.y())*
- (point2.x() - point3.x());
+ 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))
+ 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 *
+ 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*(point1.x() - point2.x()) -
- b1*(point2.x() - point3.x())) / a *
+ 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-point1.x())*(c_x-point1.x()) +
- (c_y-point1.y())*(c_y-point1.y());
+ 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(point2, point3);
+ c_event.set_bisector(site2, site3);
return true;
}
// Add new circle event to the event queue.
- void activate_circle_event(const Point2D &point1,
- const Point2D &point2,
- const Point2D &point3) {
+ 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(point1, point2, point3, 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 Point2D &point1,
- const Point2D &point2,
- const Point2D &point3) {
+ 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);
@@ -423,6 +447,7 @@
EventQueue event_queue_;
event_processor event_processor_;
std::map< Key, Value, NodeComparer > beach_line_;
+ Output output_;
};
} // sweepline
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-17 17:08:25 EDT (Thu, 17 Jun 2010)
@@ -39,8 +39,10 @@
site_events_.resize(sites.size() - skip);
std::vector<Point2D>::const_iterator sites_it;
int index = 0;
- for (sites_it = sites.begin() + skip; sites_it != sites.end(); sites_it++)
- site_events_[index++] = make_site_event(sites_it->x(), sites_it->y());
+ for (sites_it = sites.begin() + skip; sites_it != sites.end(); sites_it++, index++)
+ site_events_[index] = make_site_event(sites_it->x(),
+ sites_it->y(),
+ index + skip);
init_site_events();
}
@@ -93,7 +95,7 @@
void remove_not_active_events() {
while (!circle_events_.empty() && !deactivated_events_.empty() &&
- circle_events_.top().equals(deactivated_events_.top())) {
+ circle_events_.top().equals(deactivated_events_.top())) {
circle_events_.pop();
deactivated_events_.pop();
}
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-17 17:08:25 EDT (Thu, 17 Jun 2010)
@@ -98,7 +98,7 @@
site_event() {}
- site_event(T x, T y) : point_(x, y) {}
+ site_event(T x, T y, int index) : point_(x, y), site_index_(index) {}
bool operator==(const site_event &s_event) const {
return point_ == s_event.get_point();
@@ -136,13 +136,18 @@
return point_;
}
+ int get_site_index() const {
+ return site_index_;
+ }
+
private:
point_2d<T> point_;
+ int site_index_;
};
template <typename T>
- site_event<T> make_site_event(T x, T y) {
- return site_event<T>(x,y);
+ site_event<T> make_site_event(T x, T y, int index) {
+ return site_event<T>(x, y, index);
}
// Circle event type. Occurs when sweepline sweeps over the bottom point of
@@ -275,24 +280,25 @@
return sqr_radius_;
}
- void set_bisector(const point_2d<T> &left_point, const point_2d<T> &right_point) {
- bisector_left_point_ = left_point;
- bisector_right_point_ = right_point;
+ 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;
}
- const point_2d<T> &get_bisector_left_point() const {
- return bisector_left_point_;
+ const site_event<T> &get_bisector_left_site() const {
+ return bisector_left_site_;
}
- const point_2d<T> &get_bisector_right_point() const {
- return bisector_right_point_;
+ const site_event<T> &get_bisector_right_site() const {
+ return bisector_right_site_;
}
private:
point_2d<T> center_;
T sqr_radius_;
- point_2d<T> bisector_left_point_;
- point_2d<T> bisector_right_point_;
+ site_event<T> bisector_left_site_;
+ site_event<T> bisector_right_site_;
};
template <typename T>
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-17 17:08:25 EDT (Thu, 17 Jun 2010)
@@ -21,7 +21,7 @@
voronoi_builder() {}
void init(const std::vector<Point2D> &sites) {
- beach_line_.init(sites);
+ beach_line_.init(sites, output_);
}
void reset() {
Added: sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_output.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_output.hpp 2010-06-17 17:08:25 EDT (Thu, 17 Jun 2010)
@@ -0,0 +1,182 @@
+// Boost sweepline/voronoi_output.hpp header file
+
+// Copyright Andrii Sydorchuk 2010.
+// Distributed under the Boost Software License, Version 1.0.
+// (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+// See http://www.boost.org for updates, documentation, and revision history.
+
+#ifndef BOOST_SWEEPLINE_VORONOI_OUTPUT
+#define BOOST_SWEEPLINE_VORONOI_OUTPUT
+
+#include <list>
+#include <vector>
+
+namespace boost {
+namespace sweepline {
+
+ template <typename Point2D>
+ struct half_edge;
+
+ // Cell record data structure. Represents voronoi cell.
+ // Contains site point and pointer to any incident half-edge.
+ template <typename Point2D>
+ struct cell_record {
+ half_edge<Point2D> *incident_edge;
+ Point2D site_point;
+
+ cell_record(Point2D site, half_edge<Point2D>* edge) : incident_edge(edge), site_point(site) {}
+ };
+
+ // Voronoi vertex data structure. Represents voronoi vertex.
+ // Contains vertex coordinates and pointers to all incident half-edges.
+ template <typename Point2D>
+ struct vertex_record {
+ std::list< half_edge<Point2D>* > incident_edges;
+ Point2D vertex;
+
+ vertex_record(Point2D vertex) : vertex(vertex) {}
+ };
+
+ // Half-edge data structure. Represents voronoi edge.
+ // Contains: 1) pointer to cell records;
+ // 2) pointers to start/end vertices of half-edge;
+ // 3) pointers to previous/next half-edges(CCW);
+ // 4) pointer to twin half-edge.
+ template <typename Point2D>
+ struct half_edge {
+ typedef typename cell_record<Point2D> cell_record_type;
+ typedef typename vertex_record<Point2D> vertex_record_type;
+ typedef typename half_edge<Point2D> half_edge_type;
+
+ cell_record_type *cell_record;
+ vertex_record_type *start_point;
+ vertex_record_type *end_point;
+ half_edge_type *prev;
+ half_edge_type *next;
+ half_edge_type *twin;
+
+ half_edge(int site_index) :
+ cell_record(NULL),
+ start_point(NULL),
+ end_point(NULL),
+ prev(NULL),
+ next(NULL),
+ twin(NULL) {}
+ };
+
+ // Voronoi output data structure based on the half-edges.
+ // Contains vector of voronoi cells, doubly linked list of
+ // voronoi vertices and voronoi edges.
+ template <typename Point2D>
+ class voronoi_output {
+ public:
+ typedef typename Point2D::site_event_type site_event_type;
+ typedef typename Point2D::circle_event_type circle_event_type;
+ typedef typename cell_record<Point2D> cell_record_type;
+ typedef typename vertex_record<Point2D> vertex_record_type;
+ typedef typename half_edge<Point2D> edge_type;
+
+ voronoi_output() {}
+
+ void reset() {
+ cell_records_.clear();
+ vertex_records_.clear();
+ edges_.clear();
+ }
+
+ // Inserts new half-edge into the output data structure during site
+ // event processing. Takes as input left and right sites of the new
+ // beach line node and returns reference to the new half-edge.
+ // Second argument is new site. During this step we add two new
+ // twin half-edges.
+ edge_type &insert_new_edge(const site_event_type &site1,
+ const site_event_type &site2) {
+ // Get indexes of sites.
+ int site_index1 = site1.get_site_index();
+ int site_index2 = site2.get_site_index();
+
+ // Create new half-edge that belongs to the cell with second site.
+ edges_.push_back(edge_type(site_index2));
+ edge_type &edge2 = edges_.back();
+
+ // 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];
+
+ // Update twin pointers.
+ edge1.twin = &edge2;
+ edge2.twin = &edge1;
+
+ return edges_.back();
+ }
+
+ edge_type &insert_new_edge(const site_event_type &site1,
+ const site_event_type &site2,
+ const site_event_type &site3,
+ const circle_event_type &circle,
+ edge_type &edge12,
+ edge_type &edge23) {
+ // Add new voronoi vertex as voronoi circle center.
+ vertex_records_.push_back(vertex_record_type(circle.get_center()));
+ vertex_record_type new_vertex = vertex_records_.back();
+
+ // Update two input bisectors and their twins half-edges with
+ // new voronoi vertex.
+ edge12.start_point = &new_vertex;
+ edge12.twin->end_point = &new_vertex;
+ edge23.end_point = &new_vertex;
+ edge23.twin->start_point = &new_vertex;
+
+ // Add new half-edge.
+ edges_.push_back(edge_type(site1.get_site_index()));
+ edge_type &new_edge1 = edges_.back();
+ new_edge1.cell_record = &cell_records_[site1.get_site_index()];
+ new_edge1.end_point = &new_vertex;
+
+ // Add new half-edge.
+ edges_.push_back(edge_type(site3.get_site_index()));
+ edge_type &new_edge2 = edges_.back();
+ new_edge2.cell_record = &cell_records_[site3.get_site_index()];
+ new_edge2.start_point = &new_vertex;
+
+ // Update twin pointers of the new half-edges.
+ new_edge1.twin = &new_edge2;
+ new_edge2.twin = &new_edge1;
+
+ // Update voronoi prev/next pointers of all half-edges incident
+ // to the new voronoi vertex.
+ edge12.prev = &new_edge1;
+ new_edge1.next = &edge12;
+ edge12.twin->next = &edge23;
+ edge23.prev = edge12.twin;
+ edge23.twin->next = &new_edge2;
+ new_edge2.prev = edge23.twin;
+
+ // Update voronoi vertex incident edges pointers.
+ new_vertex.incident_edges.push_back(&edge12);
+ new_vertex.incident_edges.push_back(&edge23);
+ new_vertex.incident_edges.push_back(&new_edge1);
+
+ return edges_.back();
+ }
+
+ private:
+ std::vector<cell_record_type> cell_records_;
+ std::list<vertex_record_type> vertex_records_;
+ std::list<edge_type> edges_;
+ };
+
+} // sweepline
+} // boost
+
+#endif
\ No newline at end of file
Modified: sandbox/SOC/2010/sweepline/libs/sweepline/test/beach_line_test.cpp
==============================================================================
--- sandbox/SOC/2010/sweepline/libs/sweepline/test/beach_line_test.cpp (original)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/test/beach_line_test.cpp 2010-06-17 17:08:25 EDT (Thu, 17 Jun 2010)
@@ -15,47 +15,23 @@
#define BOOST_TEST_MODULE beach_line_test
#include <boost/test/test_case_template.hpp>
-BOOST_AUTO_TEST_CASE_TEMPLATE(voronoi_vertex_computation_test1, T, test_types) {
- typedef beach_line_node< point_2d<T> > bline_node;
- bline_node initial_node(make_point_2d<T>(static_cast<T>(0), static_cast<T>(0)),
- make_point_2d<T>(static_cast<T>(0), static_cast<T>(2)));
-
- point_2d<T> point1 = make_point_2d<T>(static_cast<T>(1), static_cast<T>(0));
- point_2d<T> point2 = make_point_2d<T>(static_cast<T>(1), static_cast<T>(1));
- point_2d<T> point3 = make_point_2d<T>(static_cast<T>(1), static_cast<T>(2));
-
- point_2d<T> voronoi_vertex1 = initial_node.get_intersection_point(false, point1);
- BOOST_CHECK_EQUAL(voronoi_vertex1.x() == static_cast<T>(0.5) &&
- voronoi_vertex1.y() == static_cast<T>(0.0), true);
-
- point_2d<T> voronoi_vertex2_1 = initial_node.get_intersection_point(false, point2);
- point_2d<T> voronoi_vertex2_2 = initial_node.get_intersection_point(true, point2);
- BOOST_CHECK_EQUAL(voronoi_vertex2_1.x() == static_cast<T>(0.0) &&
- voronoi_vertex2_1.y() == static_cast<T>(1.0) &&
- voronoi_vertex2_1.x() == voronoi_vertex2_2.x() &&
- voronoi_vertex2_1.y() == voronoi_vertex2_2.y(), true);
-
- point_2d<T> voronoi_vertex3 = initial_node.get_intersection_point(true, point3);
- BOOST_CHECK_EQUAL(voronoi_vertex3.x() == static_cast<T>(0.5) &&
- voronoi_vertex3.y() == static_cast<T>(2.0), true);
-}
-
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_point_2d<T>(static_cast<T>(0), static_cast<T>(0)),
- make_point_2d<T>(static_cast<T>(0), static_cast<T>(2)));
+ 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_point_2d<T>(static_cast<T>(1), static_cast<T>(0)));
- bline_node new_node2(make_point_2d<T>(static_cast<T>(1), static_cast<T>(1)));
- bline_node new_node3(make_point_2d<T>(static_cast<T>(1), static_cast<T>(2)));
- bline_node new_node4(make_point_2d<T>(static_cast<T>(1), static_cast<T>(1.000001)));
- bline_node new_node5(make_point_2d<T>(static_cast<T>(1), static_cast<T>(0.999999)));
+ 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);
@@ -71,6 +47,9 @@
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) {
@@ -79,14 +58,14 @@
std::map< bline_node, int, node_comparer<bline_node> > test_beach_line;
- point_2d<T> point1 = make_point_2d<T>(static_cast<T>(0), static_cast<T>(0));
- point_2d<T> point2 = make_point_2d<T>(static_cast<T>(0), static_cast<T>(2));
- bline_node initial_node(point1, point2);
+ 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;
- point_2d<T> point3 = make_point_2d<T>(static_cast<T>(1), static_cast<T>(0));
- bline_node node1(point1, point3);
- bline_node node2(point3, point1);
+ 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));
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-17 17:08:25 EDT (Thu, 17 Jun 2010)
@@ -44,21 +44,23 @@
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));
+ static_cast<T>(1.05),
+ 0);
site_event<T> site2;
BOOST_CHECK_EQUAL(site1.x(), static_cast<T>(1));
BOOST_CHECK_EQUAL(site1.y(), static_cast<T>(1.05));
+ BOOST_CHECK_EQUAL(site1.get_site_index(), 0);
- site2 = make_site_event(static_cast<T>(0.999999), static_cast<T>(1));
+ site2 = make_site_event(static_cast<T>(0.999999), static_cast<T>(1), 1);
bool arr1[] = { false, true, false, true, false, true };
EVENT_TYPES_CHECK_COMPARISON(site1, site2, arr1);
- site2 = make_site_event(static_cast<T>(1), static_cast<T>(1.1));
+ site2 = make_site_event(static_cast<T>(1), static_cast<T>(1.1), 1);
bool arr2[] = { true, false, true, false, false, true };
EVENT_TYPES_CHECK_COMPARISON(site1, site2, arr2);
- site2 = make_site_event(static_cast<T>(1), static_cast<T>(1.05));
+ site2 = make_site_event(static_cast<T>(1), static_cast<T>(1.05), 1);
bool arr3[] = { false, false, true, true, true, false };
EVENT_TYPES_CHECK_COMPARISON(site1, site2, arr3);
}
@@ -111,18 +113,18 @@
static_cast<T>(4));
site_event<T> site;
- site = make_site_event<T>(0, 100);
+ site = make_site_event<T>(0, 100, 0);
BOOST_CHECK_EQUAL(circle.compare(site), 1);
- site = make_site_event<T>(3, 0);
+ site = make_site_event<T>(3, 0, 0);
BOOST_CHECK_EQUAL(circle.compare(site), 1);
- site = make_site_event<T>(3, 2);
+ site = make_site_event<T>(3, 2, 0);
BOOST_CHECK_EQUAL(circle.compare(site), 0);
- site = make_site_event<T>(3, 2);
+ site = make_site_event<T>(3, 2, 0);
BOOST_CHECK_EQUAL(circle.compare(site), 0);
- site = make_site_event<T>(4, 2);
+ site = make_site_event<T>(4, 2, 0);
BOOST_CHECK_EQUAL(circle.compare(site), -1);
}
\ No newline at end of file