Subject: [Boost-commit] svn:boost r74295 - in sandbox/SOC/2010/sweepline: boost/sweepline boost/sweepline/detail libs/sweepline/example libs/sweepline/test
From: sydorchuk.andriy_at_[hidden]
Date: 2011-09-07 06:43:36
Author: asydorchuk
Date: 2011-09-07 06:43:35 EDT (Wed, 07 Sep 2011)
New Revision: 74295
URL: http://svn.boost.org/trac/boost/changeset/74295
Log:
Made voronoi_builder class public.
Changed voronoi_builder interface.
Changed benchmark test to use file streams.
Text files modified:
sandbox/SOC/2010/sweepline/boost/sweepline/detail/voronoi_formation.hpp | 557 -------------------------------------
sandbox/SOC/2010/sweepline/boost/sweepline/detail/voronoi_fpt_kernel.hpp | 12
sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_diagram.hpp | 591 ++++++++++++++++++++++++++++++++++++++-
sandbox/SOC/2010/sweepline/libs/sweepline/example/voronoi_visualizer.cpp | 2
sandbox/SOC/2010/sweepline/libs/sweepline/test/benchmark_test.cpp | 34 +-
sandbox/SOC/2010/sweepline/libs/sweepline/test/sweepline_test.cpp | 105 +++---
6 files changed, 640 insertions(+), 661 deletions(-)
Modified: sandbox/SOC/2010/sweepline/boost/sweepline/detail/voronoi_formation.hpp
==============================================================================
--- sandbox/SOC/2010/sweepline/boost/sweepline/detail/voronoi_formation.hpp (original)
+++ sandbox/SOC/2010/sweepline/boost/sweepline/detail/voronoi_formation.hpp 2011-09-07 06:43:35 EDT (Wed, 07 Sep 2011)
@@ -19,9 +19,6 @@
template <typename T>
class voronoi_edge;
- template <typename T>
- class voronoi_output;
-
namespace detail {
///////////////////////////////////////////////////////////////////////////
@@ -1945,560 +1942,6 @@
}
};
- template <typename T>
- struct voronoi_traits;
-
- template <>
- struct voronoi_traits<int> {
- typedef int input_coordinate_type;
- typedef double coordinate_type;
- typedef double output_coordinate_type;
-
- typedef point_data<input_coordinate_type> input_point_type;
- typedef std::vector<input_point_type> input_point_set_type;
-
- typedef directed_line_segment_data<input_coordinate_type> input_segment_type;
- typedef directed_line_segment_set_data<input_coordinate_type> input_segment_set_type;
-
- typedef voronoi_output<output_coordinate_type> output_type;
- };
-
- ///////////////////////////////////////////////////////////////////////////
- // VORONOI BUILDER ////////////////////////////////////////////////////////
- ///////////////////////////////////////////////////////////////////////////
-
- // The sweepline algorithm implementation to compute voronoi diagram of
- // input data sets of points and segments (Fortune's algorithm).
- // Complexity - O(N*logN), memory usage - O(N), where N is the total
- // number of input objects.
- // Sweepline is a vertical line that sweeps from the left to the right
- // along the x-axis positive direction. Each of the input objects is
- // wrapped into the site event. Each event is characterized by its
- // coordinates: the point site is defined by the point itself,
- // the segment site is defined by its startpoint. At any moment we
- // consider only the sites that lie to the left of the sweepline. Beach
- // line is a curve formed by the parabolic arcs and line segments, that
- // consists of the points equidistant from the sweepline and the nearest
- // site to the left of the sweepline. The part of the generated diagram to
- // the left of the beach line remains unchanged until the end of the
- // algorithm. Each node in the beach line corresponds to some voronoi edge.
- // Each node is represented by two sites. Two neighboring nodes has a
- // common site. Circle event appears at the rightmost point of the circle
- // tangent to the three sites that correspond to the two consecutive
- // bisectors. At each step algorithm goes over the leftmost event
- // and processes it appropriately. This is made until there are no events.
- // At the end output data structure holds the voronoi diagram of the
- // initial set of objects.
- // Each point creates one site event. Each segment creates three site
- // events: two for its endpoints and one for the segment itself (this is
- // made to simplify output construction). All the site events are
- // constructed at the algorithm initialization step. After that they
- // are ordered using quicksort algorithm.
- // Priority queue is used to dynamically hold circle events. At each step
- // of the algorithm the leftmost event is retrieved by comparing the
- // current site event and the topmost element from the circle event queue.
- // Standard map container was chosen to hold state of the beach line. The
- // keys of the map correspond to the bisectors and values to the
- // corresponding edges from the output data structure. Specially defined
- // comparison functor is used to make the beach line correctly ordered.
- // Epsilon-based and high-precision approaches are used to guarantee
- // efficiency and robustness of the algorithm implementation.
- // Member data: 1) site_events_ - vector of the site events;
- // 2) site_event_iterator_ - iterator to the next
- // site event;
- // 3) circle_events_ - priority queue of circle events,
- // allows to retrieve topmost event in O(logN) time;
- // 4) beach_line_ - contains current state of the beach line;
- // 5) end_points_ - maps endpoints of the segment sites with
- // temporary nodes from the beach line. While sweepline
- // sweeps over the second endpoint of the segments
- // temporary nodes are being removed;
- // 6) output_ - contains voronoi diagram itself.
- template <typename T>
- class voronoi_builder {
- public:
- typedef typename voronoi_traits<T>::input_point_type input_point_type;
- typedef typename voronoi_traits<T>::input_point_set_type input_point_set_type;
-
- typedef typename voronoi_traits<T>::input_segment_type input_segment_type;
- typedef typename voronoi_traits<T>::input_segment_set_type input_segment_set_type;
-
- typedef typename voronoi_traits<T>::coordinate_type coordinate_type;
- typedef point_2d<coordinate_type> point_type;
- typedef typename voronoi_traits<T>::output_type output_type;
- typedef site_event<coordinate_type> site_event_type;
- typedef circle_event<coordinate_type> circle_event_type;
-
- voronoi_builder(output_type &output) : output_(output) {
- // Avoid algorithm fails in case we forgot to init the builder.
- site_event_iterator_ = site_events_.begin();
- }
-
- // Create site events.
- // There will be one site event for each input point and three site
- // events for each input segment (both endpoints of a segment and the
- // segment itself).
- void init(const input_point_set_type &points,
- const input_segment_set_type &segments) {
- // Clear output.
- output_.clear();
-
- // Avoid additional memory reallocations.
- segments.clean();
- site_events_.reserve(points.size() + segments.size() * 3);
-
- // Create a site event from each input point.
- for (typename input_point_set_type::const_iterator it = points.begin();
- it != points.end(); ++it) {
- site_events_.push_back(make_site_event(
- static_cast<coordinate_type>(it->x()),
- static_cast<coordinate_type>(it->y()), 0));
- }
-
- // Each segment creates three segment sites:
- // 1) the startpoint of the segment;
- // 2) the endpoint of the segment;
- // 3) the segment itself.
- for (typename input_segment_set_type::iterator_type it = segments.begin();
- it != segments.end(); ++it) {
- coordinate_type x1 = static_cast<coordinate_type>(it->low().x());
- coordinate_type y1 = static_cast<coordinate_type>(it->low().y());
- coordinate_type x2 = static_cast<coordinate_type>(it->high().x());
- coordinate_type y2 = static_cast<coordinate_type>(it->high().y());
- site_events_.push_back(make_site_event(x1, y1, 0));
- site_events_.push_back(make_site_event(x2, y2, 0));
- site_events_.push_back(make_site_event(x1, y1, x2, y2, 0));
- }
-
- // Sort the site events.
- sort(site_events_.begin(), site_events_.end());
-
- // Remove duplicates.
- site_events_.erase(unique(
- site_events_.begin(), site_events_.end()), site_events_.end());
-
- // Number the sites.
- for (size_t cur = 0; cur < site_events_.size(); ++cur)
- site_events_[cur].index(cur);
-
- // Init the site's iterator.
- site_event_iterator_ = site_events_.begin();
-
- // Init the output data structure.
- output_.reserve(site_events_.size());
- }
-
- void clear() {
- beach_line_.clear();
- circle_events_.clear();
- site_events_.clear();
- }
-
- // Run the sweepline algorithm.
- void run_sweepline() {
- // Init the beach line.
- if (site_events_.empty()) {
- // No input sites.
- return;
- } else if (site_events_.size() == 1) {
- // Handle one input site case.
- output_.process_single_site(site_events_[0]);
- ++site_event_iterator_;
- } else {
- int skip = 0;
-
- // Count the number of the sites to init the beach line.
- while(site_event_iterator_ != site_events_.end() &&
- site_event_iterator_->x() == site_events_.begin()->x() &&
- site_event_iterator_->is_vertical()) {
- ++site_event_iterator_;
- ++skip;
- }
-
- if (skip == 1) {
- // Init the beach line with the two first sites.
- init_beach_line();
- } else {
- // Init the beach line with the sites situated on the same
- // vertical line. This could be a set of point and vertical
- // segment sites.
- init_beach_line_collinear_sites();
- }
- }
-
- // The algorithm stops when there are no events to process.
- // The circle events with the same rightmost point as the next
- // site event go first.
- while (!circle_events_.empty() ||
- !(site_event_iterator_ == site_events_.end())) {
- if (circle_events_.empty()) {
- process_site_event();
- } else if (site_event_iterator_ == site_events_.end()) {
- process_circle_event();
- } else {
- if (circle_events_.top().compare(*site_event_iterator_) == MORE) {
- process_site_event();
- } else {
- process_circle_event();
- }
- }
- }
-
- // Clean the output (remove zero-length edges).
- output_.clean();
- clear();
- }
-
- private:
- typedef typename std::vector<site_event_type>::const_iterator
- site_event_iterator_type;
- typedef typename output_type::voronoi_edge_type edge_type;
- typedef circle_events_queue<coordinate_type> circle_event_queue_type;
- typedef beach_line_node<coordinate_type> key_type;
- typedef beach_line_node_data<coordinate_type> value_type;
- typedef node_comparer<key_type> node_comparer_type;
- typedef std::map< key_type, value_type, node_comparer_type >
- beach_line_type;
- typedef typename beach_line_type::iterator beach_line_iterator;
- typedef std::pair<point_type, beach_line_iterator> end_point_type;
-
- // Init the beach line with the two first sites.
- // The first site is always a point.
- void init_beach_line() {
- // Get the first and the second site events.
- site_event_iterator_type it_first = site_events_.begin();
- site_event_iterator_type it_second = site_events_.begin();
- ++it_second;
-
- // Update the beach line.
- insert_new_arc(*it_first, *it_first, *it_second, beach_line_.begin());
-
- // The second site has been already processed.
- // Move the site's iterator.
- ++site_event_iterator_;
- }
-
- // Insert bisectors for all collinear initial sites.
- void init_beach_line_collinear_sites() {
- site_event_iterator_type it_first = site_events_.begin();
- site_event_iterator_type it_second = site_events_.begin();
- ++it_second;
- while (it_second != site_event_iterator_) {
- // Create a new beach line node.
- key_type new_node(*it_first, *it_second);
-
- // Update the output.
- edge_type *edge = output_.insert_new_edge(*it_first, *it_second);
-
- // Insert a new bisector into the beach line.
- beach_line_.insert(
- std::pair<key_type, value_type>(new_node, value_type(edge)));
-
- // Update iterators.
- ++it_first;
- ++it_second;
- }
- }
-
- // Process a single site.
- void process_site_event() {
- // Get the site event to process.
- site_event_type site_event = *site_event_iterator_;
-
- // Move the site's iterator.
- site_event_iterator_type last = site_event_iterator_ + 1;
-
- // If a new site is an end point of some segment,
- // remove temporary nodes from the beach line data structure.
- if (!site_event.is_segment()) {
- while (!end_points_.empty() &&
- end_points_.top().first == site_event.point0()) {
- beach_line_.erase(end_points_.top().second);
- end_points_.pop();
- }
- } else {
- while (last != site_events_.end() &&
- last->is_segment() && last->point0() == site_event.point0())
- last++;
- }
-
- for (; site_event_iterator_ != last; ++site_event_iterator_) {
- site_event = *site_event_iterator_;
- // Create degenerate node.
- key_type new_key(site_event);
-
- // Find the node in the binary search tree with left arc
- // lying above the new site point.
- beach_line_iterator it = beach_line_.lower_bound(new_key);
- int it_dist = site_event.is_segment() ? 2 : 1;
-
- // Do further processing depending on the above node position.
- // For any two neighbouring nodes the second site of the first node
- // is the same as the first site of the second arc.
- if (it == beach_line_.end()) {
- // The above arc corresponds to the second arc of the last node.
- // Move the iterator to the last node.
- --it;
-
- // Get the second site of the last node
- const site_event_type &site_arc = it->first.right_site();
-
- // Insert new nodes into the beach line. Update the output.
- beach_line_iterator new_node_it =
- insert_new_arc(site_arc, site_arc, site_event, it);
-
- // Add a candidate circle to the circle event queue.
- // There could be only one new circle event formed by
- // a new bisector and the one on the left.
- std::advance(new_node_it, -it_dist);
- activate_circle_event(it->first.left_site(),
- it->first.right_site(),
- site_event, new_node_it);
- } else if (it == beach_line_.begin()) {
- // The above arc corresponds to the first site of the first node.
- const site_event_type &site_arc = it->first.left_site();
-
- // Insert new nodes into the beach line. Update the output.
- insert_new_arc(site_arc, site_arc, site_event, it);
-
- // If the site event is a segment, update its direction.
- if (site_event.is_segment()) {
- site_event.inverse();
- }
-
- // Add a candidate circle to the circle event queue.
- // There could be only one new circle event formed by
- // a new bisector and the one on the right.
- activate_circle_event(site_event, it->first.left_site(),
- it->first.right_site(), it);
- } else {
- // The above arc corresponds neither to the first,
- // nor to the last site in the beach line.
- const site_event_type &site_arc2 = it->first.left_site();
- const site_event_type &site3 = it->first.right_site();
-
- // Remove the candidate circle from the event queue.
- it->second.deactivate_circle_event();
- --it;
- const site_event_type &site_arc1 = it->first.right_site();
- const site_event_type &site1 = it->first.left_site();
-
- // Insert new nodes into the beach line. Update the output.
- beach_line_iterator new_node_it =
- insert_new_arc(site_arc1, site_arc2, site_event, it);
-
- // Add candidate circles to the circle event queue.
- // There could be up to two circle events formed by
- // a new bisector and the one on the left or right.
- std::advance(new_node_it, -it_dist);
- activate_circle_event(site1, site_arc1, site_event,
- new_node_it);
-
- // If the site event is a segment, update its direction.
- if (site_event.is_segment()) {
- site_event.inverse();
- }
- std::advance(new_node_it, it_dist + 1);
- activate_circle_event(site_event, site_arc2, site3,
- new_node_it);
- }
- }
- }
-
- // Process a single circle event.
- // In general case circle event is made of the three consequtive sites
- // that form two bisector nodes in the beach line data structure.
- // 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 comparer
- // works correctly only if one of the nodes is a new one we 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.
- void process_circle_event() {
- // Get the topmost circle event.
- const circle_event_type &circle_event = circle_events_.top();
- beach_line_iterator it_first = circle_event.bisector();
- beach_line_iterator it_last = it_first;
-
- // Get the C site.
- site_event_type site3 = it_first->first.right_site();
-
- // Get the half-edge corresponding to the second bisector - (B, C).
- edge_type *bisector2 = it_first->second.edge();
-
- // Get the half-edge corresponding to the first bisector - (A, B).
- --it_first;
- edge_type *bisector1 = it_first->second.edge();
-
- // Get the A site.
- site_event_type site1 = it_first->first.left_site();
-
- if (!site1.is_segment() && site3.is_segment() &&
- site3.point1(true) == site1.point0()) {
- site3.inverse();
- }
-
- // Change the (A, B) bisector node to the (A, C) bisector node.
- const_cast<key_type &>(it_first->first).right_site(site3);
-
- // Insert the new bisector into the beach line.
- it_first->second.edge(output_.insert_new_edge(site1, site3, circle_event,
- bisector1, bisector2));
-
- // Remove the (B, C) bisector node from the beach line.
- beach_line_.erase(it_last);
- it_last = it_first;
-
- // Pop the topmost circle event from the event queue.
- circle_events_.pop();
-
- // Check new triplets formed by the neighboring arcs
- // to the left for potential circle events.
- if (it_first != beach_line_.begin()) {
- it_first->second.deactivate_circle_event();
- --it_first;
- const site_event_type &site_l1 = it_first->first.left_site();
- activate_circle_event(site_l1, site1, site3, it_last);
- }
-
- // Check the new triplet formed by the neighboring arcs
- // to the right for potential circle events.
- ++it_last;
- if (it_last != beach_line_.end()) {
- it_last->second.deactivate_circle_event();
- const site_event_type &site_r1 = it_last->first.right_site();
- activate_circle_event(site1, site3, site_r1, it_last);
- }
- }
-
- // Insert new nodes into the beach line. Update the output.
- beach_line_iterator insert_new_arc(const site_event_type &site_arc1,
- const site_event_type &site_arc2,
- const site_event_type &site_event,
- const beach_line_iterator &position) {
- // Create two new bisectors with opposite directions.
- key_type new_left_node(site_arc1, site_event);
- key_type new_right_node(site_event, site_arc2);
-
- // Set correct orientation for the first site of the second node.
- if (site_event.is_segment()) {
- new_right_node.inverse_left_site();
- }
-
- // Update the output.
- edge_type *edge = output_.insert_new_edge(site_arc2, site_event);
-
- // Update the beach line with the (site_arc1, site_event) bisector.
- beach_line_iterator it = beach_line_.insert(position,
- typename beach_line_type::value_type(new_right_node, value_type(edge->twin())));
-
- if (site_event.is_segment()) {
- // Update the beach line with temporary bisector, that will
- // disappear after processing site event going through the
- // endpoint of the segment site.
- key_type new_node(site_event, site_event);
- new_node.inverse_right_site();
- beach_line_iterator temp_it = beach_line_.insert(position,
- typename beach_line_type::value_type(new_node, value_type(NULL)));
-
- // Update the data structure that holds temporary bisectors.
- end_points_.push(std::make_pair(site_event.point1(), temp_it));
- }
-
- // Update the beach line with the (site_event, site_arc2) bisector.
- beach_line_.insert(position,
- typename beach_line_type::value_type(new_left_node, value_type(edge)));
- return it;
- }
-
- // Create a circle event from the given three sites.
- // Returns true if the circle event exists, else false.
- // If exists circle event is saved into the c_event variable.
- 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 {
- if (!site1.is_segment()) {
- if (!site2.is_segment()) {
- if (!site3.is_segment()) {
- // (point, point, point) sites.
- return create_circle_event_ppp(site1, site2, site3, c_event);
- } else {
- // (point, point, segment) sites.
- return create_circle_event_pps(site1, site2, site3, 3, c_event);
- }
- } else {
- if (!site3.is_segment()) {
- // (point, segment, point) sites.
- return create_circle_event_pps(site1, site3, site2, 2, c_event);
- } else {
- // (point, segment, segment) sites.
- return create_circle_event_pss(site1, site2, site3, 1, c_event);
- }
- }
- } else {
- if (!site2.is_segment()) {
- if (!site3.is_segment()) {
- // (segment, point, point) sites.
- return create_circle_event_pps(site2, site3, site1, 1, c_event);
- } else {
- // (segment, point, segment) sites.
- return create_circle_event_pss(site2, site1, site3, 2, c_event);
- }
- } else {
- if (!site3.is_segment()) {
- // (segment, segment, point) sites.
- return create_circle_event_pss(site3, site1, site2, 3, c_event);
- } else {
- // (segment, segment, segment) sites.
- return create_circle_event_sss(site1, site2, site3, c_event);
- }
- }
- }
- }
-
- // Add a new circle event to the event queue.
- // bisector_node corresponds to the (site2, site3) bisector.
- 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;
- // Check if the three input sites create a circle event.
- if (create_circle_event(site1, site2, site3, c_event)) {
- // Update circle event's bisector iterator to point to the
- // second bisector that forms it in the beach line.
- c_event.bisector(bisector_node);
-
- // Add the new circle event to the circle events queue.
- // Update bisector's circle event iterator to point to the
- // new circle event in the circle event queue.
- bisector_node->second.activate_circle_event(
- circle_events_.push(c_event));
- }
- }
-
- private:
- struct end_point_comparison {
- bool operator() (const end_point_type &end1, const end_point_type &end2) const {
- return end1.first > end2.first;
- }
- };
-
- std::vector<site_event_type> site_events_;
- site_event_iterator_type site_event_iterator_;
- std::priority_queue< end_point_type, std::vector<end_point_type>,
- end_point_comparison > end_points_;
- circle_event_queue_type circle_events_;
- beach_line_type beach_line_;
- output_type &output_;
-
- //Disallow copy constructor and operator=
- voronoi_builder(const voronoi_builder&);
- void operator=(const voronoi_builder&);
- };
-
} // detail
} // sweepline
} // boost
Modified: sandbox/SOC/2010/sweepline/boost/sweepline/detail/voronoi_fpt_kernel.hpp
==============================================================================
--- sandbox/SOC/2010/sweepline/boost/sweepline/detail/voronoi_fpt_kernel.hpp (original)
+++ sandbox/SOC/2010/sweepline/boost/sweepline/detail/voronoi_fpt_kernel.hpp 2011-09-07 06:43:35 EDT (Wed, 07 Sep 2011)
@@ -27,13 +27,13 @@
// sign-magnitude integers. Values are considered to be almost equal if
// their integer reinterpretatoins differ in not more than maxUlps units.
template <typename T>
- static bool almost_equal(T a, T b, unsigned int ulps) {
+ bool almost_equal(T a, T b, unsigned int ulps) {
if (a < b) return static_cast<unsigned int>(b - a) <= ulps;
return static_cast<unsigned int>(a - b) <= ulps;
}
template<>
- static bool almost_equal<float>(float a, float b, unsigned int maxUlps) {
+ bool almost_equal<float>(float a, float b, unsigned int maxUlps) {
unsigned int ll_a, ll_b;
// Reinterpret double bits as 32-bit signed integer.
@@ -51,7 +51,7 @@
}
template<>
- static bool almost_equal<double>(double a, double b, unsigned int maxUlps) {
+ bool almost_equal<double>(double a, double b, unsigned int maxUlps) {
unsigned long long ll_a, ll_b;
// Reinterpret double bits as 64-bit signed integer.
@@ -76,17 +76,17 @@
}
template <typename T>
- static double get_d(const T& value) {
+ double get_d(const T& value) {
return value.get_d();
}
template <>
- static double get_d(const float& value) {
+ double get_d(const float& value) {
return value;
}
template <>
- static double get_d(const double& value) {
+ double get_d(const double& value) {
return value;
}
Modified: sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_diagram.hpp
==============================================================================
--- sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_diagram.hpp (original)
+++ sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_diagram.hpp 2011-09-07 06:43:35 EDT (Wed, 07 Sep 2011)
@@ -736,6 +736,8 @@
public:
typedef T coordinate_type;
typedef point_data<coordinate_type> point_type;
+ typedef detail::site_event<coordinate_type> site_event_type;
+ typedef detail::circle_event<coordinate_type> circle_event_type;
typedef voronoi_cell<coordinate_type> voronoi_cell_type;
typedef std::vector<voronoi_cell_type> voronoi_cells_type;
@@ -801,12 +803,6 @@
return num_vertex_records_;
}
- private:
- typedef detail::site_event<coordinate_type> site_event_type;
- typedef detail::circle_event<coordinate_type> circle_event_type;
-
- friend class detail::voronoi_builder<int>;
-
void reserve(int num_sites) {
// Resize cell vector to avoid reallocations.
cell_records_.reserve(num_sites);
@@ -1086,6 +1082,7 @@
}
}
+ private:
// Remove degenerate edge.
void remove_edge(voronoi_edge_type *edge) {
voronoi_vertex_type *vertex1 = edge->vertex0();
@@ -1144,6 +1141,550 @@
void operator=(const voronoi_output&);
};
+ ///////////////////////////////////////////////////////////////////////////
+ // VORONOI TRAITS /////////////////////////////////////////////////////////
+ ///////////////////////////////////////////////////////////////////////////
+
+ template <typename T>
+ struct voronoi_traits;
+
+ template <>
+ struct voronoi_traits<int> {
+ typedef double coordinate_type;
+ };
+
+ ///////////////////////////////////////////////////////////////////////////
+ // VORONOI BUILDER ////////////////////////////////////////////////////////
+ ///////////////////////////////////////////////////////////////////////////
+
+ // The sweepline algorithm implementation to compute voronoi diagram of
+ // input data sets of points and segments (Fortune's algorithm).
+ // Complexity - O(N*logN), memory usage - O(N), where N is the total
+ // number of input objects.
+ // Sweepline is a vertical line that sweeps from the left to the right
+ // along the x-axis positive direction. Each of the input objects is
+ // wrapped into the site event. Each event is characterized by its
+ // coordinates: the point site is defined by the point itself,
+ // the segment site is defined by its startpoint. At any moment we
+ // consider only the sites that lie to the left of the sweepline. Beach
+ // line is a curve formed by the parabolic arcs and line segments, that
+ // consists of the points equidistant from the sweepline and the nearest
+ // site to the left of the sweepline. The part of the generated diagram to
+ // the left of the beach line remains unchanged until the end of the
+ // algorithm. Each node in the beach line corresponds to some voronoi edge.
+ // Each node is represented by two sites. Two neighboring nodes has a
+ // common site. Circle event appears at the rightmost point of the circle
+ // tangent to the three sites that correspond to the two consecutive
+ // bisectors. At each step algorithm goes over the leftmost event
+ // and processes it appropriately. This is made until there are no events.
+ // At the end output data structure holds the voronoi diagram of the
+ // initial set of objects.
+ // Each point creates one site event. Each segment creates three site
+ // events: two for its endpoints and one for the segment itself (this is
+ // made to simplify output construction). All the site events are
+ // constructed at the algorithm initialization step. After that they
+ // are ordered using quicksort algorithm.
+ // Priority queue is used to dynamically hold circle events. At each step
+ // of the algorithm the leftmost event is retrieved by comparing the
+ // current site event and the topmost element from the circle event queue.
+ // Standard map container was chosen to hold state of the beach line. The
+ // keys of the map correspond to the bisectors and values to the
+ // corresponding edges from the output data structure. Specially defined
+ // comparison functor is used to make the beach line correctly ordered.
+ // Epsilon-based and high-precision approaches are used to guarantee
+ // efficiency and robustness of the algorithm implementation.
+ // Member data: 1) site_events_ - vector of the site events;
+ // 2) site_event_iterator_ - iterator to the next
+ // site event;
+ // 3) circle_events_ - priority queue of circle events,
+ // allows to retrieve topmost event in O(logN) time;
+ // 4) beach_line_ - contains current state of the beach line;
+ // 5) end_points_ - maps endpoints of the segment sites with
+ // temporary nodes from the beach line. While sweepline
+ // sweeps over the second endpoint of the segments
+ // temporary nodes are being removed;
+ // 6) output_ - contains voronoi diagram itself.
+ template <typename T, typename VD>
+ class voronoi_builder {
+ public:
+ typedef typename voronoi_traits<T>::coordinate_type coordinate_type;
+ typedef VD output_type;
+
+ voronoi_builder() {}
+
+ template <typename PointIterator>
+ void insert_points(PointIterator first_point, PointIterator last_point) {
+ // Create a site event from each input point.
+ for (PointIterator it = first_point; it != last_point; ++it) {
+ site_events_.push_back(detail::make_site_event(
+ static_cast<coordinate_type>(it->x()),
+ static_cast<coordinate_type>(it->y()), 0));
+ }
+ }
+
+ template <typename SegmentIterator>
+ void insert_segments(SegmentIterator first_segment, SegmentIterator last_segment) {
+ // Each segment creates three segment sites:
+ // 1) the startpoint of the segment;
+ // 2) the endpoint of the segment;
+ // 3) the segment itself.
+ for (SegmentIterator it = first_segment; it != last_segment; ++it) {
+ coordinate_type x1 = static_cast<coordinate_type>(it->low().x());
+ coordinate_type y1 = static_cast<coordinate_type>(it->low().y());
+ coordinate_type x2 = static_cast<coordinate_type>(it->high().x());
+ coordinate_type y2 = static_cast<coordinate_type>(it->high().y());
+ site_events_.push_back(detail::make_site_event(x1, y1, 0));
+ site_events_.push_back(detail::make_site_event(x2, y2, 0));
+ site_events_.push_back(detail::make_site_event(x1, y1, x2, y2, 0));
+ }
+ }
+
+ template <typename PointIterator, typename SegmentIterator>
+ void insert_sites(PointIterator first_point, PointIterator last_point,
+ SegmentIterator first_segment, SegmentIterator last_segment) {
+ insert_points(first_point, last_point);
+ insert_segments(first_segment, last_segment);
+ }
+
+ // Run the sweepline algorithm.
+ void construct(output_type &output) {
+ // Init structures.
+ output_ = &output;
+ output_->clear();
+ output_->reserve(site_events_.size());
+ init_sites_queue();
+ init_beach_line();
+
+ // The algorithm stops when there are no events to process.
+ // The circle events with the same rightmost point as the next
+ // site event go first.
+ while (!circle_events_.empty() ||
+ !(site_event_iterator_ == site_events_.end())) {
+ if (circle_events_.empty()) {
+ process_site_event();
+ } else if (site_event_iterator_ == site_events_.end()) {
+ process_circle_event();
+ } else {
+ if (circle_events_.top().compare(*site_event_iterator_) == detail::MORE) {
+ process_site_event();
+ } else {
+ process_circle_event();
+ }
+ }
+ }
+
+ beach_line_.clear();
+
+ // Clean the output (remove zero-length edges).
+ output_->clean();
+ }
+
+ void clear() {
+ site_events_.clear();
+ }
+
+ private:
+ typedef detail::point_2d<coordinate_type> point_type;
+ typedef detail::site_event<coordinate_type> site_event_type;
+ typedef detail::circle_event<coordinate_type> circle_event_type;
+ typedef typename std::vector<site_event_type>::const_iterator
+ site_event_iterator_type;
+ typedef typename output_type::voronoi_edge_type edge_type;
+ typedef detail::circle_events_queue<coordinate_type> circle_event_queue_type;
+ typedef detail::beach_line_node<coordinate_type> key_type;
+ typedef detail::beach_line_node_data<coordinate_type> value_type;
+ typedef detail::node_comparer<key_type> node_comparer_type;
+ typedef std::map< key_type, value_type, node_comparer_type >
+ beach_line_type;
+ typedef typename beach_line_type::iterator beach_line_iterator;
+ typedef std::pair<point_type, beach_line_iterator> end_point_type;
+
+ // Create site events.
+ // There will be one site event for each input point and three site
+ // events for each input segment (both endpoints of a segment and the
+ // segment itself).
+ void init_sites_queue() {
+ // Sort the site events.
+ sort(site_events_.begin(), site_events_.end());
+
+ // Remove duplicates.
+ site_events_.erase(unique(
+ site_events_.begin(), site_events_.end()), site_events_.end());
+
+ // Number the sites.
+ for (size_t cur = 0; cur < site_events_.size(); ++cur)
+ site_events_[cur].index(cur);
+
+ // Init the site's iterator.
+ site_event_iterator_ = site_events_.begin();
+ }
+
+ void init_beach_line() {
+ if (site_events_.empty()) return;
+ if (site_events_.size() == 1) {
+ // Handle one input site case.
+ output_->process_single_site(site_events_[0]);
+ ++site_event_iterator_;
+ } else {
+ int skip = 0;
+
+ // Count the number of the sites to init the beach line.
+ while(site_event_iterator_ != site_events_.end() &&
+ site_event_iterator_->x() == site_events_.begin()->x() &&
+ site_event_iterator_->is_vertical()) {
+ ++site_event_iterator_;
+ ++skip;
+ }
+
+ if (skip == 1) {
+ // Init the beach line with the two first sites.
+ init_beach_line_default();
+ } else {
+ // Init the beach line with the sites situated on the same
+ // vertical line. This could be a set of point and vertical
+ // segment sites.
+ init_beach_line_collinear_sites();
+ }
+ }
+ }
+
+ // Init the beach line with the two first sites.
+ // The first site is always a point.
+ void init_beach_line_default() {
+ // Get the first and the second site events.
+ site_event_iterator_type it_first = site_events_.begin();
+ site_event_iterator_type it_second = site_events_.begin();
+ ++it_second;
+
+ // Update the beach line.
+ insert_new_arc(*it_first, *it_first, *it_second, beach_line_.begin());
+
+ // The second site has been already processed.
+ // Move the site's iterator.
+ ++site_event_iterator_;
+ }
+
+ // Insert bisectors for all collinear initial sites.
+ void init_beach_line_collinear_sites() {
+ site_event_iterator_type it_first = site_events_.begin();
+ site_event_iterator_type it_second = site_events_.begin();
+ ++it_second;
+ while (it_second != site_event_iterator_) {
+ // Create a new beach line node.
+ key_type new_node(*it_first, *it_second);
+
+ // Update the output.
+ edge_type *edge = output_->insert_new_edge(*it_first, *it_second);
+
+ // Insert a new bisector into the beach line.
+ beach_line_.insert(
+ std::pair<key_type, value_type>(new_node, value_type(edge)));
+
+ // Update iterators.
+ ++it_first;
+ ++it_second;
+ }
+ }
+
+ // Process a single site.
+ void process_site_event() {
+ // Get the site event to process.
+ site_event_type site_event = *site_event_iterator_;
+
+ // Move the site's iterator.
+ site_event_iterator_type last = site_event_iterator_ + 1;
+
+ // If a new site is an end point of some segment,
+ // remove temporary nodes from the beach line data structure.
+ if (!site_event.is_segment()) {
+ while (!end_points_.empty() &&
+ end_points_.top().first == site_event.point0()) {
+ beach_line_.erase(end_points_.top().second);
+ end_points_.pop();
+ }
+ } else {
+ while (last != site_events_.end() &&
+ last->is_segment() && last->point0() == site_event.point0())
+ last++;
+ }
+
+ for (; site_event_iterator_ != last; ++site_event_iterator_) {
+ site_event = *site_event_iterator_;
+ // Create degenerate node.
+ key_type new_key(site_event);
+
+ // Find the node in the binary search tree with left arc
+ // lying above the new site point.
+ beach_line_iterator it = beach_line_.lower_bound(new_key);
+ int it_dist = site_event.is_segment() ? 2 : 1;
+
+ // Do further processing depending on the above node position.
+ // For any two neighbouring nodes the second site of the first node
+ // is the same as the first site of the second arc.
+ if (it == beach_line_.end()) {
+ // The above arc corresponds to the second arc of the last node.
+ // Move the iterator to the last node.
+ --it;
+
+ // Get the second site of the last node
+ const site_event_type &site_arc = it->first.right_site();
+
+ // Insert new nodes into the beach line. Update the output.
+ beach_line_iterator new_node_it =
+ insert_new_arc(site_arc, site_arc, site_event, it);
+
+ // Add a candidate circle to the circle event queue.
+ // There could be only one new circle event formed by
+ // a new bisector and the one on the left.
+ std::advance(new_node_it, -it_dist);
+ activate_circle_event(it->first.left_site(),
+ it->first.right_site(),
+ site_event, new_node_it);
+ } else if (it == beach_line_.begin()) {
+ // The above arc corresponds to the first site of the first node.
+ const site_event_type &site_arc = it->first.left_site();
+
+ // Insert new nodes into the beach line. Update the output.
+ insert_new_arc(site_arc, site_arc, site_event, it);
+
+ // If the site event is a segment, update its direction.
+ if (site_event.is_segment()) {
+ site_event.inverse();
+ }
+
+ // Add a candidate circle to the circle event queue.
+ // There could be only one new circle event formed by
+ // a new bisector and the one on the right.
+ activate_circle_event(site_event, it->first.left_site(),
+ it->first.right_site(), it);
+ } else {
+ // The above arc corresponds neither to the first,
+ // nor to the last site in the beach line.
+ const site_event_type &site_arc2 = it->first.left_site();
+ const site_event_type &site3 = it->first.right_site();
+
+ // Remove the candidate circle from the event queue.
+ it->second.deactivate_circle_event();
+ --it;
+ const site_event_type &site_arc1 = it->first.right_site();
+ const site_event_type &site1 = it->first.left_site();
+
+ // Insert new nodes into the beach line. Update the output.
+ beach_line_iterator new_node_it =
+ insert_new_arc(site_arc1, site_arc2, site_event, it);
+
+ // Add candidate circles to the circle event queue.
+ // There could be up to two circle events formed by
+ // a new bisector and the one on the left or right.
+ std::advance(new_node_it, -it_dist);
+ activate_circle_event(site1, site_arc1, site_event,
+ new_node_it);
+
+ // If the site event is a segment, update its direction.
+ if (site_event.is_segment()) {
+ site_event.inverse();
+ }
+ std::advance(new_node_it, it_dist + 1);
+ activate_circle_event(site_event, site_arc2, site3,
+ new_node_it);
+ }
+ }
+ }
+
+ // Process a single circle event.
+ // In general case circle event is made of the three consequtive sites
+ // that form two bisector nodes in the beach line data structure.
+ // 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 comparer
+ // works correctly only if one of the nodes is a new one we 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.
+ void process_circle_event() {
+ // Get the topmost circle event.
+ const circle_event_type &circle_event = circle_events_.top();
+ beach_line_iterator it_first = circle_event.bisector();
+ beach_line_iterator it_last = it_first;
+
+ // Get the C site.
+ site_event_type site3 = it_first->first.right_site();
+
+ // Get the half-edge corresponding to the second bisector - (B, C).
+ edge_type *bisector2 = it_first->second.edge();
+
+ // Get the half-edge corresponding to the first bisector - (A, B).
+ --it_first;
+ edge_type *bisector1 = it_first->second.edge();
+
+ // Get the A site.
+ site_event_type site1 = it_first->first.left_site();
+
+ if (!site1.is_segment() && site3.is_segment() &&
+ site3.point1(true) == site1.point0()) {
+ site3.inverse();
+ }
+
+ // Change the (A, B) bisector node to the (A, C) bisector node.
+ const_cast<key_type &>(it_first->first).right_site(site3);
+
+ // Insert the new bisector into the beach line.
+ it_first->second.edge(output_->insert_new_edge(site1, site3, circle_event,
+ bisector1, bisector2));
+
+ // Remove the (B, C) bisector node from the beach line.
+ beach_line_.erase(it_last);
+ it_last = it_first;
+
+ // Pop the topmost circle event from the event queue.
+ circle_events_.pop();
+
+ // Check new triplets formed by the neighboring arcs
+ // to the left for potential circle events.
+ if (it_first != beach_line_.begin()) {
+ it_first->second.deactivate_circle_event();
+ --it_first;
+ const site_event_type &site_l1 = it_first->first.left_site();
+ activate_circle_event(site_l1, site1, site3, it_last);
+ }
+
+ // Check the new triplet formed by the neighboring arcs
+ // to the right for potential circle events.
+ ++it_last;
+ if (it_last != beach_line_.end()) {
+ it_last->second.deactivate_circle_event();
+ const site_event_type &site_r1 = it_last->first.right_site();
+ activate_circle_event(site1, site3, site_r1, it_last);
+ }
+ }
+
+ // Insert new nodes into the beach line. Update the output.
+ beach_line_iterator insert_new_arc(const site_event_type &site_arc1,
+ const site_event_type &site_arc2,
+ const site_event_type &site_event,
+ const beach_line_iterator &position) {
+ // Create two new bisectors with opposite directions.
+ key_type new_left_node(site_arc1, site_event);
+ key_type new_right_node(site_event, site_arc2);
+
+ // Set correct orientation for the first site of the second node.
+ if (site_event.is_segment()) {
+ new_right_node.inverse_left_site();
+ }
+
+ // Update the output.
+ edge_type *edge = output_->insert_new_edge(site_arc2, site_event);
+
+ // Update the beach line with the (site_arc1, site_event) bisector.
+ beach_line_iterator it = beach_line_.insert(position,
+ typename beach_line_type::value_type(new_right_node, value_type(edge->twin())));
+
+ if (site_event.is_segment()) {
+ // Update the beach line with temporary bisector, that will
+ // disappear after processing site event going through the
+ // endpoint of the segment site.
+ key_type new_node(site_event, site_event);
+ new_node.inverse_right_site();
+ beach_line_iterator temp_it = beach_line_.insert(position,
+ typename beach_line_type::value_type(new_node, value_type(NULL)));
+
+ // Update the data structure that holds temporary bisectors.
+ end_points_.push(std::make_pair(site_event.point1(), temp_it));
+ }
+
+ // Update the beach line with the (site_event, site_arc2) bisector.
+ beach_line_.insert(position,
+ typename beach_line_type::value_type(new_left_node, value_type(edge)));
+ return it;
+ }
+
+ // Create a circle event from the given three sites.
+ // Returns true if the circle event exists, else false.
+ // If exists circle event is saved into the c_event variable.
+ 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 {
+ if (!site1.is_segment()) {
+ if (!site2.is_segment()) {
+ if (!site3.is_segment()) {
+ // (point, point, point) sites.
+ return create_circle_event_ppp(site1, site2, site3, c_event);
+ } else {
+ // (point, point, segment) sites.
+ return create_circle_event_pps(site1, site2, site3, 3, c_event);
+ }
+ } else {
+ if (!site3.is_segment()) {
+ // (point, segment, point) sites.
+ return create_circle_event_pps(site1, site3, site2, 2, c_event);
+ } else {
+ // (point, segment, segment) sites.
+ return create_circle_event_pss(site1, site2, site3, 1, c_event);
+ }
+ }
+ } else {
+ if (!site2.is_segment()) {
+ if (!site3.is_segment()) {
+ // (segment, point, point) sites.
+ return create_circle_event_pps(site2, site3, site1, 1, c_event);
+ } else {
+ // (segment, point, segment) sites.
+ return create_circle_event_pss(site2, site1, site3, 2, c_event);
+ }
+ } else {
+ if (!site3.is_segment()) {
+ // (segment, segment, point) sites.
+ return create_circle_event_pss(site3, site1, site2, 3, c_event);
+ } else {
+ // (segment, segment, segment) sites.
+ return create_circle_event_sss(site1, site2, site3, c_event);
+ }
+ }
+ }
+ }
+
+ // Add a new circle event to the event queue.
+ // bisector_node corresponds to the (site2, site3) bisector.
+ 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;
+ // Check if the three input sites create a circle event.
+ if (create_circle_event(site1, site2, site3, c_event)) {
+ // Update circle event's bisector iterator to point to the
+ // second bisector that forms it in the beach line.
+ c_event.bisector(bisector_node);
+
+ // Add the new circle event to the circle events queue.
+ // Update bisector's circle event iterator to point to the
+ // new circle event in the circle event queue.
+ bisector_node->second.activate_circle_event(
+ circle_events_.push(c_event));
+ }
+ }
+
+ private:
+ struct end_point_comparison {
+ bool operator() (const end_point_type &end1, const end_point_type &end2) const {
+ return end1.first > end2.first;
+ }
+ };
+
+ std::vector<site_event_type> site_events_;
+ site_event_iterator_type site_event_iterator_;
+ std::priority_queue< end_point_type, std::vector<end_point_type>,
+ end_point_comparison > end_points_;
+ circle_event_queue_type circle_events_;
+ beach_line_type beach_line_;
+ output_type *output_;
+
+ //Disallow copy constructor and operator=
+ voronoi_builder(const voronoi_builder&);
+ void operator=(const voronoi_builder&);
+ };
+
// Public methods to compute voronoi diagram.
// points - vector of input points.
// segments - vector of input segments.
@@ -1155,30 +1696,28 @@
// Complexity - O(N*logN), memory usage - O(N), where N is the total
// number of points and segments.
- template <typename T>
- static inline void build_voronoi(
- const typename detail::voronoi_traits<T>::input_point_set_type &points,
- typename detail::voronoi_traits<T>::output_type &output) {
- typename detail::voronoi_traits<T>::input_segment_set_type segments_empty;
- build_voronoi<T>(points, segments_empty, output);
+ template <typename T, typename PC, typename VD>
+ static inline void construct_voronoi_points(const PC &points, VD &output) {
+ voronoi_builder<T, VD> builder;
+ builder.insert_points(points.begin(), points.end());
+ builder.construct(output);
+ builder.clear();
}
- template <typename T>
- static inline void build_voronoi(
- const typename detail::voronoi_traits<T>::input_segment_set_type &segments,
- typename detail::voronoi_traits<T>::output_type &output) {
- typename detail::voronoi_traits<T>::input_point_set_type points_empty;
- build_voronoi<T>(points_empty, segments, output);
+ template <typename T, typename SC, typename VD>
+ static inline void construct_voronoi_segments(const SC &segments, VD &output) {
+ voronoi_builder<T, VD> builder;
+ builder.insert_segments(segments.begin(), segments.end());
+ builder.construct(output);
+ builder.clear();
}
- template <typename T>
- static inline void build_voronoi(
- const typename detail::voronoi_traits<T>::input_point_set_type &points,
- const typename detail::voronoi_traits<T>::input_segment_set_type &segments,
- typename detail::voronoi_traits<T>::output_type &output) {
- detail::voronoi_builder<T> builder(output);
- builder.init(points, segments);
- builder.run_sweepline();
+ template <typename T, typename PC, typename SC, typename VD>
+ static inline void construct_voronoi(const PC &points, const SC &segments, VD &output) {
+ voronoi_builder<T, VD> builder;
+ builder.insert_sites(points.begin(), points.end(), segments.begin(), segments.end());
+ builder.construct(output);
+ builder.clear();
}
} // sweepline
Modified: sandbox/SOC/2010/sweepline/libs/sweepline/example/voronoi_visualizer.cpp
==============================================================================
--- sandbox/SOC/2010/sweepline/libs/sweepline/example/voronoi_visualizer.cpp (original)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/example/voronoi_visualizer.cpp 2011-09-07 06:43:35 EDT (Wed, 07 Sep 2011)
@@ -57,7 +57,7 @@
in_stream.flush();
// Build voronoi diagram.
- build_voronoi<int>(point_sites, segment_sites, voronoi_output_);
+ construct_voronoi<int>(point_sites, segment_sites, voronoi_output_);
brect_ = voronoi_helper<coordinate_type>::get_view_rectangle(
voronoi_output_.bounding_rectangle());
Modified: sandbox/SOC/2010/sweepline/libs/sweepline/test/benchmark_test.cpp
==============================================================================
--- sandbox/SOC/2010/sweepline/libs/sweepline/test/benchmark_test.cpp (original)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/test/benchmark_test.cpp 2011-09-07 06:43:35 EDT (Wed, 07 Sep 2011)
@@ -7,8 +7,9 @@
// See http://www.boost.org for updates, documentation, and revision history.
-#include <cstdio>
+#include <iomanip>
#include <iostream>
+#include <fstream>
#define BOOST_TEST_MODULE benchmark_test
#include <boost/mpl/list.hpp>
@@ -20,19 +21,17 @@
typedef boost::mpl::list<int> test_types;
-#ifdef WIN32
-#pragma warning( disable : 4996 )
-#endif
-
BOOST_AUTO_TEST_CASE_TEMPLATE(benchmark_test1, T, test_types) {
typedef T coordinate_type;
+ typedef point_data<coordinate_type> point_type;
boost::mt19937 gen(static_cast<unsigned int>(time(NULL)));
boost::timer timer;
- typename boost::sweepline::detail::voronoi_traits<coordinate_type>::output_type test_output;
+ typename boost::sweepline::voronoi_output<double> test_output;
- FILE *bench_file = fopen("benchmark.txt", "a");
- fprintf(bench_file, "Voronoi Segment Sweepline Benchmark Test (time in seconds):\n");
- fprintf(bench_file, "| Number of points | Number of tests | Time per one test |\n");
+ std::ofstream bench_file("benchmark.txt", std::ios_base::out | std::ios_base::app);
+ bench_file << "Voronoi Segment Sweepline Benchmark Test (time in seconds):" << std::endl;
+ bench_file << "| Number of points | Number of tests | Time per one test |" << std::endl;
+ bench_file << std::setiosflags(std::ios::right | std::ios::fixed) << std::setprecision(6);
#ifdef NDEBUG
int max_points = 1000000;
@@ -40,27 +39,26 @@
int max_points = 100;
#endif
- typename boost::sweepline::detail::voronoi_traits<coordinate_type>::input_point_set_type points;
- typedef typename boost::sweepline::detail::voronoi_traits<coordinate_type>::input_point_type
- input_point_type;
+ std::vector<point_type> points;
for (int num_points = 10; num_points <= max_points; num_points *= 10) {
points.resize(num_points);
timer.restart();
int num_tests = max_points / num_points;
for (int cur = 0; cur < num_tests; cur++) {
for (int cur_point = 0; cur_point < num_points; cur_point++) {
- points[cur_point] = point_mutable_traits<input_point_type>::construct(
+ points[cur_point] = point_mutable_traits<point_type>::construct(
static_cast<coordinate_type>(gen()),
static_cast<coordinate_type>(gen()));
}
- boost::sweepline::build_voronoi<coordinate_type>(points, test_output);
+ boost::sweepline::construct_voronoi_points<coordinate_type>(points, test_output);
}
double elapsed_time = timer.elapsed();
double time_per_test = elapsed_time / num_tests;
- fprintf(bench_file, "| %16d ", num_points);
- fprintf(bench_file, "| %15d ", num_tests);
- fprintf(bench_file, "| %17.6f |\n", time_per_test);
+ bench_file << "| " << std::setw(16) << num_points << " ";
+ bench_file << "| " << std::setw(15) << num_tests << " ";
+ bench_file << "| " << std::setw(17) << time_per_test << " ";
+ bench_file << "| " << std::endl;
}
- fclose(bench_file);
+ bench_file.close();
}
Modified: sandbox/SOC/2010/sweepline/libs/sweepline/test/sweepline_test.cpp
==============================================================================
--- sandbox/SOC/2010/sweepline/libs/sweepline/test/sweepline_test.cpp (original)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/test/sweepline_test.cpp 2011-09-07 06:43:35 EDT (Wed, 07 Sep 2011)
@@ -32,29 +32,29 @@
BOOST_CHECK_EQUAL(brect.y_max() == static_cast<coordinate_type>(ymax), true)
#define CHECK_OUTPUT_SIZE(output, cells, vertices, edges) \
- BOOST_CHECK_EQUAL(output.cell_records().size() == cells, true); \
+ BOOST_CHECK_EQUAL(output.cell_records().size() == static_cast<unsigned int>(cells), true); \
BOOST_CHECK_EQUAL(output.num_cell_records() == cells, true); \
- BOOST_CHECK_EQUAL(output.vertex_records().size() == vertices, true); \
+ BOOST_CHECK_EQUAL(output.vertex_records().size() == static_cast<unsigned int>(vertices), true); \
BOOST_CHECK_EQUAL(output.num_vertex_records() == vertices, true); \
- BOOST_CHECK_EQUAL(output.edge_records().size() == (edges << 1), true); \
+ BOOST_CHECK_EQUAL(output.edge_records().size() == static_cast<unsigned int>(edges << 1), true); \
BOOST_CHECK_EQUAL(output.num_edge_records() == edges, true)
#define VERIFY_OUTPUT(output) \
- BOOST_CHECK_EQUAL(verify_output(output, HALF_EDGE_ORIENTATION), true); \
- BOOST_CHECK_EQUAL(verify_output(output, CELL_CONVEXITY), true); \
- BOOST_CHECK_EQUAL(verify_output(output, INCIDENT_EDGES_CCW_ORDER), true); \
- BOOST_CHECK_EQUAL(verify_output(output, NO_HALF_EDGE_INTERSECTIONS), true)
+ BOOST_CHECK_EQUAL(verify_output(output, HALF_EDGE_ORIENTATION), true); \
+ BOOST_CHECK_EQUAL(verify_output(output, CELL_CONVEXITY), true); \
+ BOOST_CHECK_EQUAL(verify_output(output, INCIDENT_EDGES_CCW_ORDER), true); \
+ BOOST_CHECK_EQUAL(verify_output(output, NO_HALF_EDGE_INTERSECTIONS), true)
// Sites: (0, 0).
BOOST_AUTO_TEST_CASE_TEMPLATE(single_site_test, T, test_types) {
- typedef typename voronoi_traits<T>::coordinate_type coordinate_type;
+ typedef double coordinate_type;
typedef typename voronoi_output<coordinate_type>::voronoi_cell_const_iterator_type
voronoi_cell_const_iterator_type;
std::vector< point_data<T> > points;
points.push_back(point_data<T>(0, 0));
voronoi_output<coordinate_type> test_output;
- build_voronoi<T>(points, test_output);
+ construct_voronoi_points<T>(points, test_output);
VERIFY_OUTPUT(test_output);
CHECK_BRECT(test_output.bounding_rectangle(), 0, 0, 0, 0);
@@ -67,7 +67,7 @@
// Sites: (0, 0), (0, 1).
BOOST_AUTO_TEST_CASE_TEMPLATE(collinear_sites_test1, T, test_types) {
- typedef typename voronoi_traits<T>::coordinate_type coordinate_type;
+ typedef double coordinate_type;
typedef typename voronoi_output<coordinate_type>::voronoi_edge_type voronoi_edge_type;
typedef typename voronoi_output<coordinate_type>::voronoi_cell_const_iterator_type
voronoi_cell_const_iterator_type;
@@ -76,7 +76,7 @@
points.push_back(point_data<T>(0, 0));
points.push_back(point_data<T>(0, 1));
voronoi_output<coordinate_type> test_output;
- build_voronoi<T>(points, test_output);
+ construct_voronoi_points<T>(points, test_output);
VERIFY_OUTPUT(test_output);
CHECK_BRECT(test_output.bounding_rectangle(), 0, 0, 0, 1);
@@ -106,7 +106,7 @@
// Sites: (0, 0), (1, 1), (2, 2).
BOOST_AUTO_TEST_CASE_TEMPLATE(collinear_sites_test2, T, test_types) {
- typedef typename voronoi_traits<T>::coordinate_type coordinate_type;
+ typedef double coordinate_type;
typedef typename voronoi_output<coordinate_type>::voronoi_edge_type voronoi_edge_type;
typedef typename voronoi_output<coordinate_type>::voronoi_cell_const_iterator_type
voronoi_cell_const_iterator_type;
@@ -116,7 +116,7 @@
points.push_back(point_data<T>(1, 1));
points.push_back(point_data<T>(2, 2));
voronoi_output<coordinate_type> test_output;
- build_voronoi<T>(points, test_output);
+ construct_voronoi_points<T>(points, test_output);
VERIFY_OUTPUT(test_output);
CHECK_BRECT(test_output.bounding_rectangle(), 0, 0, 2, 2);
@@ -149,7 +149,7 @@
// Sites: (0, 0), (0, 4), (2, 1).
BOOST_AUTO_TEST_CASE_TEMPLATE(triangle_test1, T, test_types) {
- typedef typename voronoi_traits<T>::coordinate_type coordinate_type;
+ typedef double coordinate_type;
typedef typename voronoi_output<coordinate_type>::voronoi_edge_type voronoi_edge_type;
typedef typename voronoi_output<coordinate_type>::voronoi_vertex_const_iterator_type
voronoi_vertex_const_iterator_type;
@@ -166,7 +166,7 @@
points.push_back(point_data<T>(point2.x(), point2.y()));
points.push_back(point_data<T>(point3.x(), point3.y()));
voronoi_output<coordinate_type> test_output;
- build_voronoi<T>(points, test_output);
+ construct_voronoi_points<T>(points, test_output);
VERIFY_OUTPUT(test_output);
CHECK_BRECT(test_output.bounding_rectangle(), 0, 0, 2, 4);
@@ -210,7 +210,7 @@
// Sites: (0, 1), (2, 0), (2, 4).
BOOST_AUTO_TEST_CASE_TEMPLATE(triangle_test2, T, test_types) {
- typedef typename voronoi_traits<T>::coordinate_type coordinate_type;
+ typedef double coordinate_type;
typedef typename voronoi_output<coordinate_type>::voronoi_edge_type voronoi_edge_type;
typedef typename voronoi_output<coordinate_type>::voronoi_vertex_const_iterator_type
voronoi_vertex_const_iterator_type;
@@ -227,7 +227,7 @@
points.push_back(point_data<T>(point2.x(), point2.y()));
points.push_back(point_data<T>(point3.x(), point3.y()));
voronoi_output<coordinate_type> test_output;
- build_voronoi<T>(points, test_output);
+ construct_voronoi_points<T>(points, test_output);
VERIFY_OUTPUT(test_output);
CHECK_BRECT(test_output.bounding_rectangle(), 0, 0, 2, 4);
@@ -271,7 +271,7 @@
// Sites: (0, 0), (0, 1), (1, 0), (1, 1).
BOOST_AUTO_TEST_CASE_TEMPLATE(square_test1, T, test_types) {
- typedef typename voronoi_traits<T>::coordinate_type coordinate_type;
+ typedef double coordinate_type;
typedef typename voronoi_output<coordinate_type>::voronoi_edge_type voronoi_edge_type;
typedef typename voronoi_output<coordinate_type>::voronoi_vertex_const_iterator_type
voronoi_vertex_const_iterator_type;
@@ -291,7 +291,7 @@
points.push_back(point_data<T>(point3.x(), point3.y()));
points.push_back(point_data<T>(point4.x(), point4.y()));
voronoi_output<coordinate_type> test_output;
- build_voronoi<T>(points, test_output);
+ construct_voronoi_points<T>(points, test_output);
VERIFY_OUTPUT(test_output);
CHECK_BRECT(test_output.bounding_rectangle(), 0, 0, 1, 1);
@@ -346,8 +346,7 @@
#ifdef NDEBUG
BOOST_AUTO_TEST_CASE_TEMPLATE(grid_test, T, test_types) {
- voronoi_output<typename voronoi_traits<T>::coordinate_type>
- test_output_small, test_output_large;
+ voronoi_output<double> test_output_small, test_output_large;
std::vector< point_data<T> > point_vec_small, point_vec_large;
int grid_size[4] = {10, 33, 101, 163};
int max_value[4] = {10, 33, 101, 163};
@@ -361,8 +360,8 @@
point_vec_small.push_back(point_data<T>(i, j));
point_vec_large.push_back(point_data<T>(koef * i, koef * j));
}
- build_voronoi<T>(point_vec_small, test_output_small);
- build_voronoi<T>(point_vec_large, test_output_large);
+ construct_voronoi_points<T>(point_vec_small, test_output_small);
+ construct_voronoi_points<T>(point_vec_large, test_output_large);
VERIFY_OUTPUT(test_output_small);
VERIFY_OUTPUT(test_output_large);
int num_cells = grid_size[k] * grid_size[k];
@@ -377,8 +376,7 @@
#ifdef NDEBUG
BOOST_AUTO_TEST_CASE_TEMPLATE(random_test, T, test_types) {
boost::mt19937 gen(static_cast<unsigned int>(time(NULL)));
- voronoi_output<typename voronoi_traits<T>::coordinate_type>
- test_output_small, test_output_large;
+ voronoi_output<double> test_output_small, test_output_large;
std::vector< point_data<T> > point_vec_small, point_vec_large;
int num_points[] = {5, 100, 1000, 10000, 100000};
int num_runs[] = {10000, 1000, 100, 10, 1};
@@ -396,8 +394,8 @@
point_vec_small.push_back(point_data<T>(x, y));
point_vec_large.push_back(point_data<T>(koef * x, koef * y));
}
- build_voronoi<T>(point_vec_small, test_output_small);
- build_voronoi<T>(point_vec_large, test_output_large);
+ construct_voronoi_points<T>(point_vec_small, test_output_small);
+ construct_voronoi_points<T>(point_vec_large, test_output_large);
VERIFY_OUTPUT(test_output_small);
VERIFY_OUTPUT(test_output_large);
BOOST_CHECK_EQUAL(test_output_small.num_cell_records(),
@@ -414,30 +412,30 @@
#ifdef NDEBUG
BOOST_AUTO_TEST_CASE_TEMPLATE(enormous_random_test, T, test_types) {
boost::mt19937 gen(static_cast<unsigned int>(time(NULL)));
- voronoi_output<typename voronoi_traits<T>::coordinate_type> test_output;
+ voronoi_output<double> test_output;
std::vector< point_data<T> > point_vec;
for (int i = 0; i < 1000000; i++)
point_vec.push_back(point_data<T>(gen() % 10000 - 5000, gen() % 10000 - 5000));
- build_voronoi<T>(point_vec, test_output);
+ construct_voronoi_points<T>(point_vec, test_output);
BOOST_CHECK_EQUAL(verify_output(test_output, FAST_VERIFICATION), true);
}
#endif
BOOST_AUTO_TEST_CASE_TEMPLATE(segment_sites_test1, T, test_types) {
typedef T coordinate_type;
- voronoi_output<typename voronoi_traits<T>::coordinate_type> test_output;
+ voronoi_output<double> test_output;
directed_line_segment_set_data<T> segments;
point_data<T> point1(0, 0);
point_data<T> point2(1, 1);
segments.insert(directed_line_segment_data<T>(point1, point2));
- build_voronoi<T>(segments, test_output);
+ construct_voronoi_segments<T>(segments, test_output);
CHECK_OUTPUT_SIZE(test_output, 3, 0, 2);
BOOST_CHECK_EQUAL(verify_output(test_output, NO_HALF_EDGE_INTERSECTIONS), true);
}
BOOST_AUTO_TEST_CASE_TEMPLATE(segment_sites_test2, T, test_types) {
typedef T coordinate_type;
- voronoi_output<typename voronoi_traits<T>::coordinate_type> test_output;
+ voronoi_output<double> test_output;
std::vector< point_data<T> > points;
directed_line_segment_set_data<T> segments;
point_data<T> point1(0, 0);
@@ -447,14 +445,14 @@
segments.insert(directed_line_segment_data<T>(point1, point2));
points.push_back(point3);
points.push_back(point4);
- build_voronoi<T>(points, segments, test_output);
+ construct_voronoi<T>(points, segments, test_output);
CHECK_OUTPUT_SIZE(test_output, 5, 4, 8);
BOOST_CHECK_EQUAL(verify_output(test_output, NO_HALF_EDGE_INTERSECTIONS), true);
}
BOOST_AUTO_TEST_CASE_TEMPLATE(segment_sites_test3, T, test_types) {
typedef T coordinate_type;
- voronoi_output<typename voronoi_traits<T>::coordinate_type> test_output;
+ voronoi_output<double> test_output;
std::vector< point_data<T> > points;
directed_line_segment_set_data<T> segments;
point_data<T> point1(4, 0);
@@ -464,14 +462,14 @@
segments.insert(directed_line_segment_data<T>(point1, point2));
points.push_back(point3);
points.push_back(point4);
- build_voronoi<T>(points, segments, test_output);
+ construct_voronoi<T>(points, segments, test_output);
CHECK_OUTPUT_SIZE(test_output, 5, 4, 8);
BOOST_CHECK_EQUAL(verify_output(test_output, NO_HALF_EDGE_INTERSECTIONS), true);
}
BOOST_AUTO_TEST_CASE_TEMPLATE(segment_sites_test4, T, test_types) {
typedef T coordinate_type;
- voronoi_output<typename voronoi_traits<T>::coordinate_type> test_output;
+ voronoi_output<double> test_output;
std::vector< point_data<T> > points;
directed_line_segment_set_data<T> segments;
point_data<T> point1(4, 0);
@@ -481,14 +479,14 @@
segments.insert(directed_line_segment_data<T>(point1, point2));
points.push_back(point3);
points.push_back(point4);
- build_voronoi<T>(points, segments, test_output);
+ construct_voronoi<T>(points, segments, test_output);
CHECK_OUTPUT_SIZE(test_output, 5, 3, 7);
BOOST_CHECK_EQUAL(verify_output(test_output, NO_HALF_EDGE_INTERSECTIONS), true);
}
BOOST_AUTO_TEST_CASE_TEMPLATE(segment_site_test5, T, test_types) {
typedef T coordinate_type;
- voronoi_output<typename voronoi_traits<T>::coordinate_type> test_output;
+ voronoi_output<double> test_output;
std::vector< point_data<T> > points;
directed_line_segment_set_data<T> segments;
point_data<T> point1(0, 0);
@@ -500,14 +498,14 @@
points.push_back(point3);
points.push_back(point4);
points.push_back(point5);
- build_voronoi<T>(points, segments, test_output);
+ construct_voronoi<T>(points, segments, test_output);
CHECK_OUTPUT_SIZE(test_output, 6, 4, 9);
BOOST_CHECK_EQUAL(verify_output(test_output, NO_HALF_EDGE_INTERSECTIONS), true);
}
BOOST_AUTO_TEST_CASE_TEMPLATE(segment_site_test6, T, test_types) {
typedef T coordinate_type;
- voronoi_output<typename voronoi_traits<T>::coordinate_type> test_output;
+ voronoi_output<double> test_output;
std::vector< point_data<T> > points;
directed_line_segment_set_data<T> segments;
point_data<T> point1(-1, 1);
@@ -515,14 +513,14 @@
point_data<T> point3(1, 2);
segments.insert(directed_line_segment_data<T>(point2, point3));
points.push_back(point1);
- build_voronoi<T>(points, segments, test_output);
+ construct_voronoi<T>(points, segments, test_output);
CHECK_OUTPUT_SIZE(test_output, 4, 2, 5);
BOOST_CHECK_EQUAL(verify_output(test_output, NO_HALF_EDGE_INTERSECTIONS), true);
}
BOOST_AUTO_TEST_CASE_TEMPLATE(segment_site_test7, T, test_types) {
typedef T coordinate_type;
- voronoi_output<typename voronoi_traits<T>::coordinate_type> test_output;
+ voronoi_output<double> test_output;
directed_line_segment_set_data<T> segments;
point_data<T> point1(0, 0);
point_data<T> point2(4, 0);
@@ -531,14 +529,14 @@
segments.insert(directed_line_segment_data<T>(point1, point2));
segments.insert(directed_line_segment_data<T>(point2, point3));
segments.insert(directed_line_segment_data<T>(point3, point4));
- build_voronoi<T>(segments, test_output);
+ construct_voronoi_segments<T>(segments, test_output);
CHECK_OUTPUT_SIZE(test_output, 7, 6, 12);
BOOST_CHECK_EQUAL(verify_output(test_output, NO_HALF_EDGE_INTERSECTIONS), true);
}
BOOST_AUTO_TEST_CASE_TEMPLATE(segment_site_test8, T, test_types) {
typedef T coordinate_type;
- voronoi_output<typename voronoi_traits<T>::coordinate_type> test_output;
+ voronoi_output<double> test_output;
directed_line_segment_set_data<T> segments;
point_data<T> point1(0, 0);
point_data<T> point2(4, 0);
@@ -548,14 +546,14 @@
segments.insert(directed_line_segment_data<T>(point2, point3));
segments.insert(directed_line_segment_data<T>(point3, point4));
segments.insert(directed_line_segment_data<T>(point4, point1));
- build_voronoi<T>(segments, test_output);
+ construct_voronoi_segments<T>(segments, test_output);
CHECK_OUTPUT_SIZE(test_output, 8, 5, 12);
BOOST_CHECK_EQUAL(verify_output(test_output, NO_HALF_EDGE_INTERSECTIONS), true);
}
#ifdef NDEBUG
BOOST_AUTO_TEST_CASE_TEMPLATE(segment_grid_test, T, test_types) {
- voronoi_output<typename voronoi_traits<T>::coordinate_type> test_output_small, test_output_large;
+ voronoi_output<double> test_output_small, test_output_large;
directed_line_segment_set_data<T> segments_small, segments_large;
int grid_size[] = {10, 33, 100};
int max_value[] = {100, 330, 1000};
@@ -580,8 +578,8 @@
segments_small.insert(directed_line_segment_data<T>(point3_1, point4_1));
segments_large.insert(directed_line_segment_data<T>(point3_2, point4_2));
}
- build_voronoi<T>(segments_small, test_output_small);
- build_voronoi<T>(segments_large, test_output_large);
+ construct_voronoi_segments<T>(segments_small, test_output_small);
+ construct_voronoi_segments<T>(segments_large, test_output_large);
BOOST_CHECK_EQUAL(verify_output(test_output_small, NO_HALF_EDGE_INTERSECTIONS), true);
BOOST_CHECK_EQUAL(verify_output(test_output_large, NO_HALF_EDGE_INTERSECTIONS), true);
BOOST_CHECK_EQUAL(test_output_small.num_cell_records(), test_output_large.num_cell_records());
@@ -594,7 +592,7 @@
#ifdef NDEBUG
BOOST_AUTO_TEST_CASE_TEMPLATE(segment_random_test1, T, test_types) {
boost::mt19937 gen(static_cast<unsigned int>(time(NULL)));
- voronoi_output<typename voronoi_traits<T>::coordinate_type> test_output;
+ voronoi_output<double> test_output;
std::vector< point_data<T> > points;
directed_line_segment_set_data<T> segments;
int num_runs = 1000;
@@ -617,7 +615,8 @@
point_data<T> point2(x2, y2);
segments.insert(directed_line_segment_data<T>(point1, point2));
}
- build_voronoi<T>(points, segments, test_output);
+ segments.clean();
+ construct_voronoi<T>(points, segments, test_output);
BOOST_CHECK_EQUAL(verify_output(test_output, NO_HALF_EDGE_INTERSECTIONS), true);
}
}
@@ -626,7 +625,7 @@
#ifdef NDEBUG
BOOST_AUTO_TEST_CASE_TEMPLATE(segment_random_test2, T, test_types) {
boost::mt19937 gen(static_cast<unsigned int>(time(NULL)));
- voronoi_output<typename voronoi_traits<T>::coordinate_type> test_output_small, test_output_large;
+ voronoi_output<double> test_output_small, test_output_large;
directed_line_segment_set_data<T> segments_small, segments_large;
int num_segments[] = {5, 25, 125, 625};
int num_runs[] = {1000, 100, 10, 1};
@@ -664,8 +663,8 @@
point_data<T> point2_large(x2, y2);
segments_large.insert(directed_line_segment_data<T>(point1_large, point2_large));
}
- build_voronoi<T>(segments_small, test_output_small);
- build_voronoi<T>(segments_large, test_output_large);
+ construct_voronoi_segments<T>(segments_small, test_output_small);
+ construct_voronoi_segments<T>(segments_large, test_output_large);
BOOST_CHECK_EQUAL(verify_output(test_output_small, NO_HALF_EDGE_INTERSECTIONS), true);
BOOST_CHECK_EQUAL(verify_output(test_output_large, NO_HALF_EDGE_INTERSECTIONS), true);
BOOST_CHECK_EQUAL(test_output_small.num_cell_records(), test_output_large.num_cell_records());