Subject: [Boost-commit] svn:boost r74369 - in sandbox/SOC/2010/sweepline: boost/sweepline boost/sweepline/detail libs/sweepline/example libs/sweepline/test
From: sydorchuk.andriy_at_[hidden]
Date: 2011-09-13 12:39:37
Author: asydorchuk
Date: 2011-09-13 12:39:35 EDT (Tue, 13 Sep 2011)
New Revision: 74369
URL: http://svn.boost.org/trac/boost/changeset/74369
Log:
Refactoring: 1) removed all the dependencies between voronoi_builder and voronoi_diagram classes (splitted them).
Changed benchmark test to use file streams.
Changed ercs to doubles in circle_events as they are not used anymore.
Added:
sandbox/SOC/2010/sweepline/boost/sweepline/voronoi.hpp (contents, props changed)
sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_builder.hpp (contents, props changed)
Text files modified:
sandbox/SOC/2010/sweepline/boost/sweepline/detail/voronoi_formation.hpp | 112 ++----
sandbox/SOC/2010/sweepline/boost/sweepline/detail/voronoi_fpt_kernel.hpp | 66 +--
sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_diagram.hpp | 619 ---------------------------------------
sandbox/SOC/2010/sweepline/libs/sweepline/example/voronoi_visualizer.cpp | 26
sandbox/SOC/2010/sweepline/libs/sweepline/test/benchmark_test.cpp | 4
sandbox/SOC/2010/sweepline/libs/sweepline/test/circle_event_creation_test.cpp | 6
sandbox/SOC/2010/sweepline/libs/sweepline/test/clipping_test.cpp | 1
sandbox/SOC/2010/sweepline/libs/sweepline/test/event_queue_test.cpp | 2
sandbox/SOC/2010/sweepline/libs/sweepline/test/event_types_test.cpp | 2
sandbox/SOC/2010/sweepline/libs/sweepline/test/node_comparer_test.cpp | 18
sandbox/SOC/2010/sweepline/libs/sweepline/test/predicates_test.cpp | 2
sandbox/SOC/2010/sweepline/libs/sweepline/test/robust_fpt_test.cpp | 2
sandbox/SOC/2010/sweepline/libs/sweepline/test/sqrt_expr_evaluator_test.cpp | 2
sandbox/SOC/2010/sweepline/libs/sweepline/test/sweepline_test.cpp | 64 ++--
14 files changed, 146 insertions(+), 780 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-13 12:39:35 EDT (Tue, 13 Sep 2011)
@@ -15,10 +15,6 @@
namespace boost {
namespace sweepline {
-
- template <typename T>
- class voronoi_edge;
-
namespace detail {
///////////////////////////////////////////////////////////////////////////
@@ -27,7 +23,7 @@
// Forward declarations.
template <typename T>
- class beach_line_node;
+ class beach_line_node_key;
template <typename T>
class beach_line_node_data;
@@ -35,9 +31,6 @@
template <typename T>
struct node_comparer;
- template <typename T>
- class epsilon_robust_comparator;
-
// Represents the result of the orientation test.
enum kOrientation {
RIGHT_ORIENTATION = -1,
@@ -402,8 +395,7 @@
typedef T coordinate_type;
typedef point_2d<T> point_type;
typedef site_event<T> site_event_type;
- typedef epsilon_robust_comparator<T> erc_type;
- typedef beach_line_node<coordinate_type> Key;
+ typedef beach_line_node_key<coordinate_type> Key;
typedef beach_line_node_data<coordinate_type> Value;
typedef node_comparer<Key> NodeComparer;
typedef typename std::map< Key, Value, NodeComparer >::iterator
@@ -419,17 +411,9 @@
lower_x_(lower_x),
is_active_(true) {}
- circle_event(const erc_type &c_x,
- const erc_type &c_y,
- const erc_type &lower_x) :
- center_x_(c_x),
- center_y_(c_y),
- lower_x_(lower_x),
- is_active_(true) {}
-
bool operator==(const circle_event &that) const {
- return (this->lower_x_.compare(that.lower_x_, 128) == UNDEFINED &&
- this->center_y_.compare(that.center_y_, 128) == UNDEFINED);
+ return almost_equal(this->lower_x_, that.lower_x_, 128) &&
+ almost_equal(this->center_y_, that.center_y_, 128);
}
bool operator!=(const circle_event &that) const {
@@ -440,14 +424,11 @@
// Each rightmost point has next representation:
// (lower_x / denom, center_y / denom), denom is always positive.
bool operator<(const circle_event &that) const {
- // Compare x-coordinates of the rightmost points. If the result
- // is undefined we assume that x-coordinates are equal.
- kPredicateResult pres = this->lower_x_.compare(that.lower_x_, 128);
- if (pres != UNDEFINED)
- return (pres == LESS);
-
- // Compare y-coordinates of the rightmost points.
- return this->center_y_.compare(that.center_y_, 128) == LESS;
+ if (almost_equal(this->lower_x_, that.lower_x_, 128)) {
+ if (almost_equal(this->center_y_, that.center_y_, 128)) return false;
+ return this->center_y_ < that.center_y_;
+ }
+ return this->lower_x_ < that.lower_x_;
}
bool operator<=(const circle_event &that) const {
@@ -467,20 +448,17 @@
// If circle point is less than site point return -1.
// If circle point is equal to site point return 0.
// If circle point is greater than site point return 1.
- kPredicateResult compare(const site_event_type &s_event) const {
- // Compare x-coordinates.
- kPredicateResult pres = lower_x_.compare(s_event.x(), 64);
- // If the comparison result is undefined
- // x-coordinates are considered to be equal.
- if (pres != UNDEFINED)
- return pres;
- // Compare y-coordinates in case of equal x-coordinates.
- return center_y_.compare(s_event.y(), 64);
+ kPredicateResult compare(const site_event_type &that) const {
+ if (almost_equal(this->lower_x_, that.x(), 64)) {
+ if (almost_equal(this->center_y_, that.y(), 64)) return UNDEFINED;
+ return this->center_y_ < that.y() ? LESS : MORE;
+ }
+ return this->lower_x_ < that.x() ? LESS : MORE;
}
// Evaluate x-coordinate of the center of the circle.
coordinate_type x() const {
- return center_x_.dif();
+ return center_x_;
}
void x(coordinate_type center_x) {
@@ -489,7 +467,7 @@
// Evaluate y-coordinate of the center of the circle.
coordinate_type y() const {
- return center_y_.dif();
+ return center_y_;
}
void y(coordinate_type center_y) {
@@ -498,25 +476,13 @@
// Evaluate x-coordinate of the rightmost point of the circle.
coordinate_type lower_x() const {
- return lower_x_.dif();
+ return lower_x_;
}
void lower_x(coordinate_type lower_x) {
lower_x_ = lower_x;
}
- point_type center() const {
- return point_type(x(), y());
- }
-
- const erc_type &erc_x() const {
- return center_x_;
- }
-
- const erc_type &erc_y() const {
- return center_y_;
- }
-
// Return iterator to the second bisector from the beach line
// data structure that forms current circle event.
const beach_line_iterator &bisector() const {
@@ -536,9 +502,9 @@
}
private:
- erc_type center_x_;
- erc_type center_y_;
- erc_type lower_x_;
+ coordinate_type center_x_;
+ coordinate_type center_y_;
+ coordinate_type lower_x_;
beach_line_iterator bisector_node_;
bool is_active_;
};
@@ -1513,7 +1479,7 @@
t += teta / (robust_fpt<T>(8.0) * A);
t -= A / (robust_fpt<T>(2.0) * teta);
} else {
- robust_fpt<T> det = ((teta * teta + denom * denom) * A * B).get_sqrt();
+ robust_fpt<T> det = ((teta * teta + denom * denom) * A * B).sqrt();
if (segment_index == 2) {
t -= det / (denom * denom);
} else {
@@ -1589,9 +1555,9 @@
t -= robust_fpt<T>(a1) * robust_fpt<T>((segm_start1.x() + segm_start2.x()) * 0.5 - site1.x());
t -= robust_fpt<T>(b1) * robust_fpt<T>((segm_start1.y() + segm_start2.y()) * 0.5 - site1.y());
if (point_index == 2) {
- t += det.get_sqrt();
+ t += det.sqrt();
} else {
- t -= det.get_sqrt();
+ t -= det.sqrt();
}
t /= a;
epsilon_robust_comparator< robust_fpt<T> > c_x, c_y;
@@ -1600,7 +1566,7 @@
c_y += robust_fpt<T>(0.5 * (segm_start1.y() + segm_start2.y()));
c_y += robust_fpt<T>(b1) * t;
epsilon_robust_comparator< robust_fpt<T> > lower_x(c_x);
- lower_x += robust_fpt<T>(0.5) * c.fabs() / a.get_sqrt();
+ lower_x += robust_fpt<T>(0.5) * c.fabs() / a.sqrt();
recompute_c_x = c_x.dif().ulp() > 128;
recompute_c_y = c_y.dif().ulp() > 128;
recompute_lower_x = lower_x.dif().ulp() > 128;
@@ -1636,9 +1602,9 @@
b -= sqr_sum2 * robust_fpt<T>(robust_cross_product(a1, b1, -site1.y(), site1.x()), 2.0);
t -= b;
if (point_index == 2) {
- t += det.get_sqrt();
+ t += det.sqrt();
} else {
- t -= det.get_sqrt();
+ t -= det.sqrt();
}
t /= (a * a);
epsilon_robust_comparator< robust_fpt<T> > c_x(ix), c_y(iy);
@@ -1686,9 +1652,9 @@
robust_fpt<T> b3(site3.y1(true) - site3.y0(true), 0.0);
robust_fpt<T> c3(robust_cross_product(site3.x0(true), site3.y0(true), site3.x1(true), site3.y1(true)), 2.0);
- robust_fpt<T> len1 = (a1 * a1 + b1 * b1).get_sqrt();
- robust_fpt<T> len2 = (a2 * a2 + b2 * b2).get_sqrt();
- robust_fpt<T> len3 = (a3 * a3 + b3 * b3).get_sqrt();
+ robust_fpt<T> len1 = (a1 * a1 + b1 * b1).sqrt();
+ robust_fpt<T> len2 = (a2 * a2 + b2 * b2).sqrt();
+ robust_fpt<T> len3 = (a3 * a3 + b3 * b3).sqrt();
robust_fpt<T> cross_12(robust_cross_product(a1.fpv(), b1.fpv(), a2.fpv(), b2.fpv()), 2.0);
robust_fpt<T> cross_23(robust_cross_product(a2.fpv(), b2.fpv(), a3.fpv(), b3.fpv()), 2.0);
robust_fpt<T> cross_31(robust_cross_product(a3.fpv(), b3.fpv(), a1.fpv(), b1.fpv()), 2.0);
@@ -1746,25 +1712,25 @@
// The one site is considered to be newer than the other in case it was
// processed by the algorithm later.
template <typename T>
- class beach_line_node {
+ class beach_line_node_key {
public:
typedef T coordinate_type;
typedef point_2d<T> point_type;
typedef site_event<T> site_event_type;
- beach_line_node() {}
+ beach_line_node_key() {}
// Constructs degenerate bisector, used to search an arc that is above
// the given site. The input to the constructor is the new site point.
- explicit beach_line_node(const site_event_type &new_site) {
+ explicit beach_line_node_key(const site_event_type &new_site) {
left_site_ = new_site;
right_site_ = new_site;
}
// Constructs a new bisector. The input to the constructor is the two
// sites that create the bisector. The order of sites is important.
- beach_line_node(const site_event_type &left_site,
- const site_event_type &right_site) {
+ beach_line_node_key(const site_event_type &left_site,
+ const site_event_type &right_site) {
left_site_ = left_site;
right_site_ = right_site;
}
@@ -1864,7 +1830,7 @@
template <typename T>
class beach_line_node_data {
public:
- explicit beach_line_node_data(voronoi_edge<T> *new_edge) :
+ explicit beach_line_node_data(void *new_edge) :
edge_(new_edge),
contains_circle_event_(false) {}
@@ -1879,17 +1845,17 @@
contains_circle_event_ = false;
}
- voronoi_edge<T> *edge() const {
+ void *edge() const {
return edge_;
}
- void edge(voronoi_edge<T> *new_edge) {
+ void edge(void *new_edge) {
edge_ = new_edge;
}
private:
typename circle_events_queue<T>::circle_event_type_it circle_event_it_;
- voronoi_edge<T> *edge_;
+ void *edge_;
bool contains_circle_event_;
};
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-13 12:39:35 EDT (Tue, 13 Sep 2011)
@@ -14,6 +14,9 @@
namespace sweepline {
namespace detail {
+ template <typename T>
+ class epsilon_robust_comparator;
+
// Represents the result of the epsilon robust predicate.
// If the result is undefined some further processing is usually required.
enum kPredicateResult {
@@ -27,10 +30,7 @@
// sign-magnitude integers. Values are considered to be almost equal if
// their integer reinterpretatoins differ in not more than maxUlps units.
template <typename T>
- 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;
- }
+ bool almost_equal(T a, T b, unsigned int ulps);
template<>
bool almost_equal<float>(float a, float b, unsigned int maxUlps) {
@@ -90,10 +90,10 @@
return value;
}
- template <typename _fpt>
+ template <typename FPT>
class robust_fpt {
public:
- typedef _fpt floating_point_type;
+ typedef FPT floating_point_type;
typedef double relative_error_type;
// Rounding error is at most 1 EPS.
@@ -112,39 +112,39 @@
relative_error_type re() const { return re_; }
relative_error_type ulp() const { return re_; }
- bool operator==(double that) const {
- if (that == 0)
- return this->fpv_ == that;
- return almost_equal(this->fpv_, that,
- static_cast<unsigned int>(this->ulp()));
+ template <typename T>
+ bool operator==(T that) const {
+ floating_point_type value = static_cast<floating_point_type>(that);
+ return almost_equal(this->fpv_, value, static_cast<unsigned int>(this->ulp()));
}
- bool operator!=(double that) const {
+ template <typename T>
+ bool operator!=(T that) const {
return !(*this == that);
}
- bool operator<(double that) const {
- if (*this == that)
- return false;
- return this->fpv_ < that;
+ template <typename T>
+ bool operator<(T that) const {
+ if (*this == that) return false;
+ return this->fpv_ < static_cast<floating_point_type>(that);
}
- bool operator<=(double that) const {
- if (*this == that)
- return true;
- return this->fpv_ < that;
+ template <typename T>
+ bool operator<=(T that) const {
+ if (*this == that) return true;
+ return this->fpv_ < static_cast<floating_point_type>(that);
}
- bool operator>(double that) const {
- if (*this == that)
- return false;
- return this->fpv_ > that;
+ template <typename T>
+ bool operator>(T that) const {
+ if (*this == that) return false;
+ return this->fpv_ > static_cast<floating_point_type>(that);
}
- bool operator>=(double that) const {
- if (*this == that)
- return true;
- return this->fpv_ > that;
+ template <typename T>
+ bool operator>=(T that) const {
+ if (*this == that) return true;
+ return this->fpv_ > static_cast<floating_point_type>(that);
}
bool operator==(const robust_fpt &that) const {
@@ -260,7 +260,7 @@
return robust_fpt(fpv, re);
}
- robust_fpt get_sqrt() const {
+ robust_fpt sqrt() const {
return robust_fpt(std::sqrt(fpv_), re_ * 0.5 + ROUNDING_ERROR);
}
@@ -408,12 +408,6 @@
return (lhs < rhs) ? LESS : MORE;
}
- // Check whether comparison has undefined result.
- bool compares_undefined(const epsilon_robust_comparator &rc,
- int ulp) const {
- return this->compare(rc, ulp) == UNDEFINED;
- }
-
private:
T positive_sum_;
T negative_sum_;
@@ -575,4 +569,4 @@
} // sweepline
} // boost
-#endif
\ No newline at end of file
+#endif
Added: sandbox/SOC/2010/sweepline/boost/sweepline/voronoi.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2010/sweepline/boost/sweepline/voronoi.hpp 2011-09-13 12:39:35 EDT (Tue, 13 Sep 2011)
@@ -0,0 +1,59 @@
+// Boost sweepline/voronoi.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
+#define BOOST_SWEEPLINE_VORONOI
+
+#include "boost/polygon/polygon.hpp"
+using namespace boost::polygon;
+
+#include "voronoi_builder.hpp"
+#include "voronoi_diagram.hpp"
+
+namespace boost {
+namespace sweepline {
+
+ // Public methods to compute voronoi diagram.
+ // points - vector of input points.
+ // segments - vector of input segments.
+ // output - voronoi output data structure to hold voronoi diagram.
+ // The assumption is made that input doesn't contain segments that
+ // intersect or points lying on the segments. Also coordinates of
+ // the points and of the endpoints of the segments should be within
+ // signed integer range [-2^31, 2^31-1].
+ // Complexity - O(N*logN), memory usage - O(N), where N is the total
+ // number of points and segments.
+ 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, 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, 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();
+ }
+
+}
+}
+
+#endif
Added: sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_builder.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_builder.hpp 2011-09-13 12:39:35 EDT (Tue, 13 Sep 2011)
@@ -0,0 +1,581 @@
+// Boost sweepline/voronoi_builder.hpp header file
+
+// Copyright Andrii Sydorchuk 2010.
+// Distributed under the Boost Software License, Version 1.0.
+// (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+// See http://www.boost.org for updates, documentation, and revision history.
+
+#ifndef BOOST_SWEEPLINE_VORONOI_BUILDER
+#define BOOST_SWEEPLINE_VORONOI_BUILDER
+
+#include <algorithm>
+#include <cmath>
+#include <cstring>
+#include <list>
+#include <map>
+#include <queue>
+#include <vector>
+
+#pragma warning(disable:4800)
+#include <gmpxx.h>
+
+#include "boost/polygon/polygon.hpp"
+using namespace boost::polygon;
+
+#include "detail/mpt_wrapper.hpp"
+#include "detail/voronoi_fpt_kernel.hpp"
+#include "detail/voronoi_formation.hpp"
+
+namespace boost {
+namespace sweepline {
+
+ ///////////////////////////////////////////////////////////////////////////
+ // 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_key<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 = static_cast<edge_type *>(it_first->second.edge());
+
+ // Get the half-edge corresponding to the first bisector - (A, B).
+ --it_first;
+ edge_type *bisector1 = static_cast<edge_type *>(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&);
+ };
+
+} // sweepline
+} // boost
+
+#endif
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-13 12:39:35 EDT (Tue, 13 Sep 2011)
@@ -10,25 +10,14 @@
#ifndef BOOST_SWEEPLINE_VORONOI_DIAGRAM
#define BOOST_SWEEPLINE_VORONOI_DIAGRAM
-#include <algorithm>
#include <cmath>
-#include <cstring>
#include <list>
-#include <map>
-#include <queue>
#include <stack>
#include <vector>
-#pragma warning(disable:4800)
-#include <gmpxx.h>
-
#include "boost/polygon/polygon.hpp"
using namespace boost::polygon;
-#include "detail/mpt_wrapper.hpp"
-#include "detail/voronoi_fpt_kernel.hpp"
-#include "detail/voronoi_formation.hpp"
-
namespace boost {
namespace sweepline {
@@ -43,9 +32,6 @@
template <typename T>
class voronoi_edge;
- template <typename T>
- class voronoi_output;
-
// Bounding rectangle data structure. Contains coordinates
// of the bottom left and the upper right points of the rectangle.
template <typename T>
@@ -732,12 +718,10 @@
// to the new vector as removing elements from a vector takes O(n)
// time.
template <typename T>
- class voronoi_output {
+ class voronoi_diagram {
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;
@@ -760,7 +744,7 @@
typedef typename voronoi_edges_type::const_iterator
voronoi_edge_const_iterator_type;
- voronoi_output() :
+ voronoi_diagram() :
num_cell_records_(0),
num_edge_records_(0),
num_vertex_records_(0) {}
@@ -814,7 +798,8 @@
}
// Update the voronoi output in case of a single point input.
- void process_single_site(const site_event_type &site) {
+ template <typename SEvent>
+ void process_single_site(const SEvent &site) {
// Update bounding rectangle.
voronoi_rect_ = BRect<coordinate_type>(site.point0());
@@ -828,8 +813,8 @@
// Insert a new half-edge into the output data structure.
// Takes as input left and right sites that form a new bisector.
// Returns a pointer to a new half-edge.
- voronoi_edge_type *insert_new_edge(const site_event_type &site1,
- const site_event_type &site2) {
+ template <typename SEvent>
+ voronoi_edge_type *insert_new_edge(const SEvent &site1, const SEvent &site2) {
// Get sites' indices.
int site_index1 = site1.index();
int site_index2 = site2.index();
@@ -885,14 +870,15 @@
// that correponds to the intersection point of the two old half-edges,
// pointers to those half-edges. Half-edges' direction goes out of the
// new voronoi vertex point. Returns a pointer to the new half-edge.
- voronoi_edge_type *insert_new_edge(const site_event_type &site1,
- const site_event_type &site3,
- const circle_event_type &circle,
+ template <typename SEvent, typename CEvent>
+ voronoi_edge_type *insert_new_edge(const SEvent &site1,
+ const SEvent &site3,
+ const CEvent &circle,
voronoi_edge_type *edge12,
voronoi_edge_type *edge23) {
// Add a new voronoi vertex.
vertex_records_.push_back(voronoi_vertex_type(
- point_type(circle.erc_x().dif(), circle.erc_y().dif()), edge12));
+ point_type(circle.x(), circle.y()), edge12));
voronoi_vertex_type &new_vertex = vertex_records_.back();
// Update vertex pointers of the old edges.
@@ -1137,589 +1123,10 @@
BRect<coordinate_type> voronoi_rect_;
// Disallow copy constructor and operator=
- voronoi_output(const voronoi_output&);
- 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&);
+ voronoi_diagram(const voronoi_diagram&);
+ void operator=(const voronoi_diagram&);
};
- // Public methods to compute voronoi diagram.
- // points - vector of input points.
- // segments - vector of input segments.
- // output - voronoi output data structure to hold voronoi diagram.
- // The assumption is made that input doesn't contain segments that
- // intersect or points lying on the segments. Also coordinates of
- // the points and of the endpoints of the segments should be within
- // signed integer range [-2^31, 2^31-1].
- // Complexity - O(N*logN), memory usage - O(N), where N is the total
- // number of points and segments.
-
- 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, 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, 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
} // boost
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-13 12:39:35 EDT (Tue, 13 Sep 2011)
@@ -12,7 +12,7 @@
#include <QtOpenGL/QGLWidget>
#include <QtGui/QtGui>
-#include "boost/sweepline/voronoi_diagram.hpp"
+#include "boost/sweepline/voronoi.hpp"
using namespace boost::sweepline;
class GLWidget : public QGLWidget {
@@ -57,9 +57,9 @@
in_stream.flush();
// Build voronoi diagram.
- construct_voronoi<int>(point_sites, segment_sites, voronoi_output_);
+ construct_voronoi<int>(point_sites, segment_sites, vd_);
brect_ = voronoi_helper<coordinate_type>::get_view_rectangle(
- voronoi_output_.bounding_rectangle());
+ vd_.bounding_rectangle());
// Update view.
update_view_port();
@@ -83,7 +83,7 @@
// Draw voronoi sites.
{
- const voronoi_cells_type &cells = voronoi_output_.cell_records();
+ const voronoi_cells_type &cells = vd_.cell_records();
voronoi_cell_const_iterator_type it;
glColor3f(0.0f, 0.0f, 1.0f);
glPointSize(9);
@@ -108,7 +108,7 @@
// Draw voronoi vertices.
{
- const voronoi_vertices_type &vertices = voronoi_output_.vertex_records();
+ const voronoi_vertices_type &vertices = vd_.vertex_records();
voronoi_vertex_const_iterator_type it;
glColor3f(0.0f, 1.0f, 0.0f);
glBegin(GL_POINTS);
@@ -119,7 +119,7 @@
// Draw voronoi edges.
{
- const voronoi_edges_type &edges = voronoi_output_.edge_records();
+ const voronoi_edges_type &edges = vd_.edge_records();
voronoi_edge_const_iterator_type it;
glColor3f(0.0f, 1.0f, 0.0f);
glBegin(GL_LINES);
@@ -161,17 +161,17 @@
typedef directed_line_segment_data<int> isegment_type;
typedef std::vector<ipoint_type> ipoint_set_type;
typedef directed_line_segment_set_data<int> isegment_set_type;
- typedef voronoi_output<coordinate_type>::voronoi_cells_type voronoi_cells_type;
- typedef voronoi_output<coordinate_type>::voronoi_vertices_type voronoi_vertices_type;
- typedef voronoi_output<coordinate_type>::voronoi_edges_type voronoi_edges_type;
- typedef voronoi_output<coordinate_type>::voronoi_cell_const_iterator_type
+ typedef voronoi_diagram<coordinate_type>::voronoi_cells_type voronoi_cells_type;
+ typedef voronoi_diagram<coordinate_type>::voronoi_vertices_type voronoi_vertices_type;
+ typedef voronoi_diagram<coordinate_type>::voronoi_edges_type voronoi_edges_type;
+ typedef voronoi_diagram<coordinate_type>::voronoi_cell_const_iterator_type
voronoi_cell_const_iterator_type;
- typedef voronoi_output<coordinate_type>::voronoi_vertex_const_iterator_type
+ typedef voronoi_diagram<coordinate_type>::voronoi_vertex_const_iterator_type
voronoi_vertex_const_iterator_type;
- typedef voronoi_output<coordinate_type>::voronoi_edge_const_iterator_type
+ typedef voronoi_diagram<coordinate_type>::voronoi_edge_const_iterator_type
voronoi_edge_const_iterator_type;
BRect<coordinate_type> brect_;
- voronoi_output<coordinate_type> voronoi_output_;
+ voronoi_diagram<coordinate_type> vd_;
bool primary_edges_only_;
};
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-13 12:39:35 EDT (Tue, 13 Sep 2011)
@@ -17,7 +17,7 @@
#include <boost/test/test_case_template.hpp>
#include <boost/timer.hpp>
-#include "boost/sweepline/voronoi_diagram.hpp"
+#include "boost/sweepline/voronoi.hpp"
typedef boost::mpl::list<int> test_types;
@@ -26,7 +26,7 @@
typedef point_data<coordinate_type> point_type;
boost::mt19937 gen(static_cast<unsigned int>(time(NULL)));
boost::timer timer;
- typename boost::sweepline::voronoi_output<double> test_output;
+ typename boost::sweepline::voronoi_diagram<double> test_output;
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;
Modified: sandbox/SOC/2010/sweepline/libs/sweepline/test/circle_event_creation_test.cpp
==============================================================================
--- sandbox/SOC/2010/sweepline/libs/sweepline/test/circle_event_creation_test.cpp (original)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/test/circle_event_creation_test.cpp 2011-09-13 12:39:35 EDT (Tue, 13 Sep 2011)
@@ -11,7 +11,7 @@
#include <boost/mpl/list.hpp>
#include <boost/test/test_case_template.hpp>
-#include "boost/sweepline/voronoi_diagram.hpp"
+#include "boost/sweepline/voronoi_builder.hpp"
using namespace boost::sweepline;
using namespace boost::sweepline::detail;
@@ -64,8 +64,8 @@
site_event_type site1_2(static_cast<T>(0), static_cast<T>(2), 0);
is_event = create_circle_event_pps(site1_1, site1_2, segm_site, 2, c_event);
BOOST_CHECK_EQUAL(is_event, true);
- BOOST_CHECK_EQUAL(c_event.center().x() == static_cast<T>(-1), true);
- BOOST_CHECK_EQUAL(c_event.center().y() == static_cast<T>(1), true);
+ BOOST_CHECK_EQUAL(c_event.x() == static_cast<T>(-1), true);
+ BOOST_CHECK_EQUAL(c_event.y() == static_cast<T>(1), true);
is_event = create_circle_event_pps(site1_1, site1_2, segm_site, 1, c_event);
BOOST_CHECK_EQUAL(is_event, false);
is_event = create_circle_event_pps(site1_1, site1_2, segm_site, 3, c_event);
Modified: sandbox/SOC/2010/sweepline/libs/sweepline/test/clipping_test.cpp
==============================================================================
--- sandbox/SOC/2010/sweepline/libs/sweepline/test/clipping_test.cpp (original)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/test/clipping_test.cpp 2011-09-13 12:39:35 EDT (Tue, 13 Sep 2011)
@@ -13,7 +13,6 @@
#include "boost/sweepline/voronoi_diagram.hpp"
using namespace boost::sweepline;
-using namespace boost::sweepline::detail;
typedef boost::mpl::list<double> test_types;
Modified: sandbox/SOC/2010/sweepline/libs/sweepline/test/event_queue_test.cpp
==============================================================================
--- sandbox/SOC/2010/sweepline/libs/sweepline/test/event_queue_test.cpp (original)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/test/event_queue_test.cpp 2011-09-13 12:39:35 EDT (Tue, 13 Sep 2011)
@@ -13,7 +13,7 @@
#include <boost/mpl/list.hpp>
#include <boost/test/test_case_template.hpp>
-#include "boost/sweepline/voronoi_diagram.hpp"
+#include "boost/sweepline/voronoi_builder.hpp"
using namespace boost::sweepline;
using namespace boost::sweepline::detail;
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 2011-09-13 12:39:35 EDT (Tue, 13 Sep 2011)
@@ -11,7 +11,7 @@
#include <boost/mpl/list.hpp>
#include <boost/test/test_case_template.hpp>
-#include "boost/sweepline/voronoi_diagram.hpp"
+#include "boost/sweepline/voronoi_builder.hpp"
using namespace boost::sweepline;
using namespace boost::sweepline::detail;
Modified: sandbox/SOC/2010/sweepline/libs/sweepline/test/node_comparer_test.cpp
==============================================================================
--- sandbox/SOC/2010/sweepline/libs/sweepline/test/node_comparer_test.cpp (original)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/test/node_comparer_test.cpp 2011-09-13 12:39:35 EDT (Tue, 13 Sep 2011)
@@ -11,7 +11,7 @@
#include <boost/mpl/list.hpp>
#include <boost/test/test_case_template.hpp>
-#include "boost/sweepline/voronoi_diagram.hpp"
+#include "boost/sweepline/voronoi_builder.hpp"
using namespace boost::sweepline;
using namespace boost::sweepline::detail;
@@ -19,7 +19,7 @@
BOOST_AUTO_TEST_CASE_TEMPLATE(node_comparer_test_pp1, T, test_types) {
typedef site_event<T> site_event_type;
- typedef beach_line_node<T> bline_node;
+ typedef beach_line_node_key<T> bline_node;
typedef typename std::map< bline_node, int,
node_comparer<bline_node> >::const_iterator bline_it;
@@ -45,7 +45,7 @@
BOOST_AUTO_TEST_CASE_TEMPLATE(node_comparer_test_pp2, T, test_types) {
typedef site_event<T> site_event_type;
- typedef beach_line_node<T> bline_node;
+ typedef beach_line_node_key<T> bline_node;
typedef typename std::map< bline_node, int,
node_comparer<bline_node> >::const_iterator bline_it;
@@ -73,7 +73,7 @@
BOOST_AUTO_TEST_CASE_TEMPLATE(node_comparer_test_pp3, T, test_types) {
typedef point_2d<T> Point2D;
- typedef beach_line_node<T> bline_node;
+ typedef beach_line_node_key<T> bline_node;
node_comparer<bline_node> node_comparer_test;
bline_node initial_node(
@@ -106,7 +106,7 @@
BOOST_AUTO_TEST_CASE_TEMPLATE(node_comparer_test_pp4, T, test_types) {
typedef point_2d<T> Point2D;
- typedef beach_line_node<T> bline_node;
+ typedef beach_line_node_key<T> bline_node;
node_comparer<bline_node> node_comparer_test;
bline_node initial_node(
@@ -137,7 +137,7 @@
BOOST_AUTO_TEST_CASE_TEMPLATE(node_comparer_test_pp5, T, test_types) {
typedef point_2d<T> Point2D;
- typedef beach_line_node<T> bline_node;
+ typedef beach_line_node_key<T> bline_node;
node_comparer<bline_node> node_comparer_test;
bline_node initial_node(
@@ -170,7 +170,7 @@
BOOST_AUTO_TEST_CASE_TEMPLATE(node_comparer_test_pp6, T, test_types) {
typedef point_2d<T> Point2D;
- typedef beach_line_node<T> bline_node;
+ typedef beach_line_node_key<T> bline_node;
node_comparer<bline_node> node_comparer_test;
bline_node initial_node(
@@ -204,7 +204,7 @@
BOOST_AUTO_TEST_CASE_TEMPLATE(node_comparer_test_pp7, T, test_types) {
typedef point_2d<T> Point2D;
- typedef beach_line_node<T> bline_node;
+ typedef beach_line_node_key<T> bline_node;
node_comparer<bline_node> node_comparer_test;
bline_node initial_node(
@@ -226,7 +226,7 @@
BOOST_AUTO_TEST_CASE_TEMPLATE(node_comparer_test_pp8, T, test_types) {
typedef point_2d<T> Point2D;
- typedef beach_line_node<T> bline_node;
+ typedef beach_line_node_key<T> bline_node;
node_comparer<bline_node> node_comparer_test;
bline_node initial_node(
Modified: sandbox/SOC/2010/sweepline/libs/sweepline/test/predicates_test.cpp
==============================================================================
--- sandbox/SOC/2010/sweepline/libs/sweepline/test/predicates_test.cpp (original)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/test/predicates_test.cpp 2011-09-13 12:39:35 EDT (Tue, 13 Sep 2011)
@@ -11,7 +11,7 @@
#include <boost/mpl/list.hpp>
#include <boost/test/test_case_template.hpp>
-#include "boost/sweepline/voronoi_diagram.hpp"
+#include "boost/sweepline/voronoi_builder.hpp"
using namespace boost::sweepline;
using namespace boost::sweepline::detail;
Modified: sandbox/SOC/2010/sweepline/libs/sweepline/test/robust_fpt_test.cpp
==============================================================================
--- sandbox/SOC/2010/sweepline/libs/sweepline/test/robust_fpt_test.cpp (original)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/test/robust_fpt_test.cpp 2011-09-13 12:39:35 EDT (Tue, 13 Sep 2011)
@@ -11,7 +11,7 @@
#include <boost/mpl/list.hpp>
#include <boost/test/test_case_template.hpp>
-#include "boost/sweepline/voronoi_diagram.hpp"
+#include "boost/sweepline/voronoi_builder.hpp"
using namespace boost::sweepline::detail;
typedef boost::mpl::list<double, mpf_class, mpt_wrapper<mpf_class, 8> > test_types;
Modified: sandbox/SOC/2010/sweepline/libs/sweepline/test/sqrt_expr_evaluator_test.cpp
==============================================================================
--- sandbox/SOC/2010/sweepline/libs/sweepline/test/sqrt_expr_evaluator_test.cpp (original)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/test/sqrt_expr_evaluator_test.cpp 2011-09-13 12:39:35 EDT (Tue, 13 Sep 2011)
@@ -13,7 +13,7 @@
#include <boost/random/mersenne_twister.hpp>
#include <boost/test/test_case_template.hpp>
-#include "boost/sweepline/voronoi_diagram.hpp"
+#include "boost/sweepline/voronoi_builder.hpp"
using namespace boost::sweepline::detail;
template <int N>
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-13 12:39:35 EDT (Tue, 13 Sep 2011)
@@ -14,7 +14,7 @@
#include <boost/random/mersenne_twister.hpp>
#include <boost/test/test_case_template.hpp>
-#include "boost/sweepline/voronoi_diagram.hpp"
+#include "boost/sweepline/voronoi.hpp"
using namespace boost::sweepline;
using namespace boost::sweepline::detail;
#include "output_verification.hpp"
@@ -48,12 +48,12 @@
// Sites: (0, 0).
BOOST_AUTO_TEST_CASE_TEMPLATE(single_site_test, T, test_types) {
typedef double coordinate_type;
- typedef typename voronoi_output<coordinate_type>::voronoi_cell_const_iterator_type
+ typedef typename voronoi_diagram<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;
+ voronoi_diagram<coordinate_type> test_output;
construct_voronoi_points<T>(points, test_output);
VERIFY_OUTPUT(test_output);
@@ -68,14 +68,14 @@
// Sites: (0, 0), (0, 1).
BOOST_AUTO_TEST_CASE_TEMPLATE(collinear_sites_test1, T, test_types) {
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
+ typedef typename voronoi_diagram<coordinate_type>::voronoi_edge_type voronoi_edge_type;
+ typedef typename voronoi_diagram<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));
points.push_back(point_data<T>(0, 1));
- voronoi_output<coordinate_type> test_output;
+ voronoi_diagram<coordinate_type> test_output;
construct_voronoi_points<T>(points, test_output);
VERIFY_OUTPUT(test_output);
@@ -107,15 +107,15 @@
// Sites: (0, 0), (1, 1), (2, 2).
BOOST_AUTO_TEST_CASE_TEMPLATE(collinear_sites_test2, T, test_types) {
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
+ typedef typename voronoi_diagram<coordinate_type>::voronoi_edge_type voronoi_edge_type;
+ typedef typename voronoi_diagram<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));
points.push_back(point_data<T>(1, 1));
points.push_back(point_data<T>(2, 2));
- voronoi_output<coordinate_type> test_output;
+ voronoi_diagram<coordinate_type> test_output;
construct_voronoi_points<T>(points, test_output);
VERIFY_OUTPUT(test_output);
@@ -150,8 +150,8 @@
// Sites: (0, 0), (0, 4), (2, 1).
BOOST_AUTO_TEST_CASE_TEMPLATE(triangle_test1, T, test_types) {
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
+ typedef typename voronoi_diagram<coordinate_type>::voronoi_edge_type voronoi_edge_type;
+ typedef typename voronoi_diagram<coordinate_type>::voronoi_vertex_const_iterator_type
voronoi_vertex_const_iterator_type;
point_2d<coordinate_type> point1 = point_2d<coordinate_type>(
@@ -165,7 +165,7 @@
points.push_back(point_data<T>(point1.x(), point1.y()));
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;
+ voronoi_diagram<coordinate_type> test_output;
construct_voronoi_points<T>(points, test_output);
VERIFY_OUTPUT(test_output);
@@ -211,8 +211,8 @@
// Sites: (0, 1), (2, 0), (2, 4).
BOOST_AUTO_TEST_CASE_TEMPLATE(triangle_test2, T, test_types) {
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
+ typedef typename voronoi_diagram<coordinate_type>::voronoi_edge_type voronoi_edge_type;
+ typedef typename voronoi_diagram<coordinate_type>::voronoi_vertex_const_iterator_type
voronoi_vertex_const_iterator_type;
point_2d<coordinate_type> point1 = point_2d<coordinate_type>(
@@ -226,7 +226,7 @@
points.push_back(point_data<T>(point1.x(), point1.y()));
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;
+ voronoi_diagram<coordinate_type> test_output;
construct_voronoi_points<T>(points, test_output);
VERIFY_OUTPUT(test_output);
@@ -272,8 +272,8 @@
// Sites: (0, 0), (0, 1), (1, 0), (1, 1).
BOOST_AUTO_TEST_CASE_TEMPLATE(square_test1, T, test_types) {
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
+ typedef typename voronoi_diagram<coordinate_type>::voronoi_edge_type voronoi_edge_type;
+ typedef typename voronoi_diagram<coordinate_type>::voronoi_vertex_const_iterator_type
voronoi_vertex_const_iterator_type;
point_2d<coordinate_type> point1 = point_2d<coordinate_type>(
@@ -290,7 +290,7 @@
points.push_back(point_data<T>(point2.x(), point2.y()));
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;
+ voronoi_diagram<coordinate_type> test_output;
construct_voronoi_points<T>(points, test_output);
VERIFY_OUTPUT(test_output);
@@ -346,7 +346,7 @@
#ifdef NDEBUG
BOOST_AUTO_TEST_CASE_TEMPLATE(grid_test, T, test_types) {
- voronoi_output<double> test_output_small, test_output_large;
+ voronoi_diagram<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};
@@ -376,7 +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<double> test_output_small, test_output_large;
+ voronoi_diagram<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};
@@ -412,7 +412,7 @@
#ifdef NDEBUG
BOOST_AUTO_TEST_CASE_TEMPLATE(enormous_random_test, T, test_types) {
boost::mt19937 gen(static_cast<unsigned int>(time(NULL)));
- voronoi_output<double> test_output;
+ voronoi_diagram<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));
@@ -423,7 +423,7 @@
BOOST_AUTO_TEST_CASE_TEMPLATE(segment_sites_test1, T, test_types) {
typedef T coordinate_type;
- voronoi_output<double> test_output;
+ voronoi_diagram<double> test_output;
directed_line_segment_set_data<T> segments;
point_data<T> point1(0, 0);
point_data<T> point2(1, 1);
@@ -435,7 +435,7 @@
BOOST_AUTO_TEST_CASE_TEMPLATE(segment_sites_test2, T, test_types) {
typedef T coordinate_type;
- voronoi_output<double> test_output;
+ voronoi_diagram<double> test_output;
std::vector< point_data<T> > points;
directed_line_segment_set_data<T> segments;
point_data<T> point1(0, 0);
@@ -452,7 +452,7 @@
BOOST_AUTO_TEST_CASE_TEMPLATE(segment_sites_test3, T, test_types) {
typedef T coordinate_type;
- voronoi_output<double> test_output;
+ voronoi_diagram<double> test_output;
std::vector< point_data<T> > points;
directed_line_segment_set_data<T> segments;
point_data<T> point1(4, 0);
@@ -469,7 +469,7 @@
BOOST_AUTO_TEST_CASE_TEMPLATE(segment_sites_test4, T, test_types) {
typedef T coordinate_type;
- voronoi_output<double> test_output;
+ voronoi_diagram<double> test_output;
std::vector< point_data<T> > points;
directed_line_segment_set_data<T> segments;
point_data<T> point1(4, 0);
@@ -486,7 +486,7 @@
BOOST_AUTO_TEST_CASE_TEMPLATE(segment_site_test5, T, test_types) {
typedef T coordinate_type;
- voronoi_output<double> test_output;
+ voronoi_diagram<double> test_output;
std::vector< point_data<T> > points;
directed_line_segment_set_data<T> segments;
point_data<T> point1(0, 0);
@@ -505,7 +505,7 @@
BOOST_AUTO_TEST_CASE_TEMPLATE(segment_site_test6, T, test_types) {
typedef T coordinate_type;
- voronoi_output<double> test_output;
+ voronoi_diagram<double> test_output;
std::vector< point_data<T> > points;
directed_line_segment_set_data<T> segments;
point_data<T> point1(-1, 1);
@@ -520,7 +520,7 @@
BOOST_AUTO_TEST_CASE_TEMPLATE(segment_site_test7, T, test_types) {
typedef T coordinate_type;
- voronoi_output<double> test_output;
+ voronoi_diagram<double> test_output;
directed_line_segment_set_data<T> segments;
point_data<T> point1(0, 0);
point_data<T> point2(4, 0);
@@ -536,7 +536,7 @@
BOOST_AUTO_TEST_CASE_TEMPLATE(segment_site_test8, T, test_types) {
typedef T coordinate_type;
- voronoi_output<double> test_output;
+ voronoi_diagram<double> test_output;
directed_line_segment_set_data<T> segments;
point_data<T> point1(0, 0);
point_data<T> point2(4, 0);
@@ -553,7 +553,7 @@
#ifdef NDEBUG
BOOST_AUTO_TEST_CASE_TEMPLATE(segment_grid_test, T, test_types) {
- voronoi_output<double> test_output_small, test_output_large;
+ voronoi_diagram<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};
@@ -592,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<double> test_output;
+ voronoi_diagram<double> test_output;
std::vector< point_data<T> > points;
directed_line_segment_set_data<T> segments;
int num_runs = 1000;
@@ -625,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<double> test_output_small, test_output_large;
+ voronoi_diagram<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};