|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r74498 - in sandbox/SOC/2010/sweepline: boost/sweepline boost/sweepline/detail libs/sweepline/test
From: sydorchuk.andriy_at_[hidden]
Date: 2011-09-21 15:01:55
Author: asydorchuk
Date: 2011-09-21 15:01:54 EDT (Wed, 21 Sep 2011)
New Revision: 74498
URL: http://svn.boost.org/trac/boost/changeset/74498
Log:
Updated point segment distance function (some strange behaviour on gcc-4.4.3).
Updated circle event queue structure.
Updated beach line node key / data structure.
Updated tests.
Text files modified:
sandbox/SOC/2010/sweepline/boost/sweepline/detail/voronoi_formation.hpp | 495 ++++++++++++++-------------------------
sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_builder.hpp | 54 ++-
sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_diagram.hpp | 2
sandbox/SOC/2010/sweepline/libs/sweepline/test/event_queue_test.cpp | 44 +--
sandbox/SOC/2010/sweepline/libs/sweepline/test/event_types_test.cpp | 62 ++--
sandbox/SOC/2010/sweepline/libs/sweepline/test/node_comparer_test.cpp | 229 ++++++++---------
sandbox/SOC/2010/sweepline/libs/sweepline/test/predicates_test.cpp | 98 +++---
7 files changed, 418 insertions(+), 566 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-21 15:01:54 EDT (Wed, 21 Sep 2011)
@@ -21,16 +21,6 @@
// VORONOI EVENT TYPES ////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////
- // Forward declarations.
- template <typename T>
- class beach_line_node_key;
-
- template <typename T>
- class beach_line_node_data;
-
- template <typename T>
- struct node_comparer;
-
// Represents the result of the orientation test.
enum kOrientation {
RIGHT_ORIENTATION = -1,
@@ -343,30 +333,6 @@
bool is_inverse_;
};
- template <typename T>
- static inline site_event<T> make_site_event(T x, T y, int index) {
- return site_event<T>(x, y, index);
- }
-
- template <typename T>
- static inline site_event<T> make_site_event(const point_2d<T> &point,
- int index) {
- return site_event<T>(point, index);
- }
-
- template <typename T>
- static inline site_event<T> make_site_event(T x1, T y1, T x2, T y2,
- int index) {
- return site_event<T>(x1, y1, x2, y2, index);
- }
-
- template <typename T>
- static inline site_event<T> make_site_event(const point_2d<T> &point1,
- const point_2d<T> &point2,
- int index) {
- return site_event<T>(point1, point2, index);
- }
-
// Circle event type.
// Occrus when the sweepline sweeps over the rightmost point of the voronoi
// circle (with the center at the intersection point of the bisectors).
@@ -395,11 +361,7 @@
typedef T coordinate_type;
typedef point_2d<T> point_type;
typedef site_event<T> site_event_type;
- 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
- beach_line_iterator;
+ typedef circle_event<T> circle_event_type;
circle_event() : is_active_(true) {}
@@ -483,16 +445,6 @@
lower_x_ = lower_x;
}
- // Return iterator to the second bisector from the beach line
- // data structure that forms current circle event.
- const beach_line_iterator &bisector() const {
- return bisector_node_;
- }
-
- void bisector(beach_line_iterator iterator) {
- bisector_node_ = iterator;
- }
-
bool is_active() const {
return is_active_;
}
@@ -505,15 +457,9 @@
coordinate_type center_x_;
coordinate_type center_y_;
coordinate_type lower_x_;
- beach_line_iterator bisector_node_;
bool is_active_;
};
- template <typename T>
- static inline circle_event<T> make_circle_event(T c_x, T c_y, T lower_x) {
- return circle_event<T>(c_x, c_y, lower_x);
- }
-
///////////////////////////////////////////////////////////////////////////
// VORONOI CIRCLE EVENTS QUEUE ////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////
@@ -525,68 +471,50 @@
// Instead list is used to store all the circle events and priority queue
// of the iterators to the list elements is used to keep the correct circle
// events ordering.
- template <typename T>
- class circle_events_queue {
+ template <typename T, typename Predicate>
+ class ordered_queue {
public:
- typedef T coordinate_type;
- typedef circle_event<T> circle_event_type;
- typedef typename std::list<circle_event_type>::iterator
- circle_event_type_it;
-
- circle_events_queue() {}
-
- void clear() {
- while (!circle_events_.empty())
- circle_events_.pop();
- circle_events_list_.clear();
- }
+ ordered_queue() {}
bool empty() {
- remove_not_active_events();
- return circle_events_.empty();
+ return c_.empty();
}
- const circle_event_type &top() {
- remove_not_active_events();
- return (*circle_events_.top());
+ const T &top() {
+ return *c_.top();
}
void pop() {
- circle_event_type_it temp_it = circle_events_.top();
- circle_events_.pop();
- circle_events_list_.erase(temp_it);
+ list_iterator_type it = c_.top();
+ c_.pop();
+ c_list_.erase(it);
}
- circle_event_type_it push(const circle_event_type &c_event) {
- circle_events_list_.push_front(c_event);
- circle_events_.push(circle_events_list_.begin());
- return circle_events_list_.begin();
+ T &push(const T &e) {
+ c_list_.push_front(e);
+ c_.push(c_list_.begin());
+ return c_list_.front();
}
private:
+ typedef typename std::list<T>::iterator list_iterator_type;
+
struct comparison {
- bool operator() (const circle_event_type_it &node1,
- const circle_event_type_it &node2) const {
- return (*node1) > (*node2);
+ Predicate cmp_;
+ bool operator() (const list_iterator_type &it1,
+ const list_iterator_type &it2) const {
+ return cmp_(*it1, *it2);
}
};
- // Remove all the inactive events from the top of the priority
- // queue until the first active event is found.
- void remove_not_active_events() {
- while (!circle_events_.empty() &&
- !circle_events_.top()->is_active())
- pop();
- }
-
- std::priority_queue< circle_event_type_it,
- std::vector<circle_event_type_it>,
- comparison > circle_events_;
- std::list<circle_event_type> circle_events_list_;
+ std::priority_queue< list_iterator_type,
+ std::vector<list_iterator_type>,
+ comparison > c_;
+ std::list<T> c_list_;
//Disallow copy constructor and operator=
- circle_events_queue(const circle_events_queue&);
- void operator=(const circle_events_queue&);
+ ordered_queue(const ordered_queue&);
+ void operator=(const ordered_queue&);
};
///////////////////////////////////////////////////////////////////////////
@@ -734,10 +662,10 @@
// with the arc corresponding to the point site.
// The relative error is atmost 3EPS.
template <typename T>
- static double find_distance_to_point_arc(const point_2d<T> &point_site,
+ static double find_distance_to_point_arc(const site_event<T> &point_site,
const point_2d<T> &new_point) {
- double dx = point_site.x() - new_point.x();
- double dy = point_site.y() - new_point.y();
+ double dx = point_site.point0().x() - new_point.x();
+ double dy = point_site.point0().y() - new_point.y();
return (dx * dx + dy * dy) / (2 * dx);
}
@@ -751,27 +679,16 @@
if (segment.is_vertical()) {
return (segment.point0().x() - new_point.x()) * 0.5;
} else {
- const point_2d<T> &segment_start = segment.point1();
- const point_2d<T> &segment_end = segment.point0();
+ const point_2d<T> &segment_start = segment.point0(true);
+ const point_2d<T> &segment_end = segment.point1(true);
double a1 = segment_end.x() - segment_start.x();
double b1 = segment_end.y() - segment_start.y();
double a3 = new_point.x() - segment_start.x();
double b3 = new_point.y() - segment_start.y();
double k = std::sqrt(a1 * a1 + b1 * b1);
// Avoid substraction while computing k.
- if (segment.is_inverse()) {
- if (b1 >= 0.0) {
- k = 1.0 / (b1 + k);
- } else {
- k = (-b1 + k) / (a1 * a1);
- }
- } else {
- if (b1 >= 0.0) {
- k = (-b1 - k) / (a1 * a1);
- } else {
- k = 1.0 / (b1 - k);
- }
- }
+ if (b1 >= 0) k = 1.0 / (b1 + k);
+ else k = (k - b1) / (a1 * a1);
// Relative error of the robust cross product is 2EPS.
// Relative error of the k is atmost 5EPS.
// The resulting relative error is atmost 8EPS.
@@ -779,81 +696,26 @@
}
}
- //// Robust 65-bit predicate, avoids using high-precision libraries.
- //// Works correctly for any input coordinate type that can be casted without
- //// lose of data to the integer type within a range [-2^31, 2^31 - 1].
- //template <typename T>
- //static bool robust_65bit_less_predicate(const point_2d<T> &left_point,
- // const point_2d<T> &right_point,
- // const point_2d<T> &new_point) {
- // polygon_ulong_long_type a1, a2, b1, b2;
- // polygon_ulong_long_type b1_sqr, b2_sqr, l_expr, r_expr;
- // bool l_expr_plus, r_expr_plus;
-
- // // Compute a1 = (x0-x1), a2 = (x0-x2), b1 = (y0 - y1), b2 = (y0 - y2).
- // convert_to_65_bit(new_point.x() - left_point.x(), a1);
- // convert_to_65_bit(new_point.x() - right_point.x(), a2);
- // convert_to_65_bit(new_point.y() - left_point.y(), b1);
- // convert_to_65_bit(new_point.y() - right_point.y(), b2);
-
- // // Compute b1_sqr = (y0-y1)^2 and b2_sqr = (y0-y2)^2.
- // b1_sqr = b1 * b1;
- // b2_sqr = b2 * b2;
- // polygon_ulong_long_type b1_sqr_mod = b1_sqr % a1;
- // polygon_ulong_long_type b2_sqr_mod = b2_sqr % a2;
-
- // // Compute l_expr = (x1 - x2).
- // l_expr_plus = convert_to_65_bit(left_point.x() - right_point.x(), l_expr);
-
- // // In case (b2_sqr / a2) < (b1_sqr / a1), decrease left_expr by 1.
- // if (b2_sqr_mod * a1 < b1_sqr_mod * a2) {
- // if (!l_expr_plus)
- // ++l_expr;
- // else if (l_expr != 0)
- // --l_expr;
- // else {
- // ++l_expr;
- // l_expr_plus = false;
- // }
- // }
-
- // // Compute right expression.
- // polygon_ulong_long_type value1 = b1_sqr / a1;
- // polygon_ulong_long_type value2 = b2_sqr / a2;
- // if (value1 >= value2) {
- // r_expr = value1 - value2;
- // r_expr_plus = true;
- // } else {
- // r_expr = value2 - value1;
- // r_expr_plus = false;
- // }
-
- // // Compare left and right expressions.
- // if (!l_expr_plus && r_expr_plus)
- // return true;
- // if (l_expr_plus && !r_expr_plus)
- // return false;
- // if (l_expr_plus && r_expr_plus)
- // return l_expr < r_expr;
- // return l_expr > r_expr;
- //}
-
// Robust predicate, avoids using high-precision libraries.
// Returns true if a horizontal line going through the new point site
// intersects right arc at first, else returns false. If horizontal line
// goes through intersection point of the given two arcs returns false.
// Works correctly for any input coordinate type that can be casted without
// lose of data to the integer type within a range [-2^31, 2^31-1].
- template <typename T>
- static bool less_predicate(const point_2d<T> &left_point,
- const point_2d<T> &right_point,
- const point_2d<T> &new_point) {
+ template <typename Site>
+ static bool less_predicate_pp(const Site &left_site,
+ const Site &right_site,
+ const Site &new_site) {
// Any two point sites with different x-coordinates create two
// bisectors. Each bisector is defined by the order the sites
// appear in its representation. Predicates used in this function
// won't produce the correct result for the any arrangment of the
// input sites. That's why some preprocessing is required to handle
// such cases.
+ typedef typename Site::point_type point_type;
+ const point_type &left_point = left_site.point0();
+ const point_type &right_point = right_site.point0();
+ const point_type &new_point = new_site.point0();
if (left_point.x() > right_point.x()) {
if (new_point.y() <= left_point.y())
return false;
@@ -866,29 +728,33 @@
return left_point.y() + right_point.y() < 2.0 * new_point.y();
}
- double dist1 = find_distance_to_point_arc(left_point, new_point);
- double dist2 = find_distance_to_point_arc(right_point, new_point);
+ double dist1 = find_distance_to_point_arc(left_site, new_point);
+ double dist2 = find_distance_to_point_arc(right_site, new_point);
// The undefined ulp range is equal to 3EPS + 3EPS <= 6ULP.
return dist1 < dist2;
}
- template <typename T>
- static kPredicateResult fast_less_predicate(point_2d<T> site_point, site_event<T> segment_site,
- point_2d<T> new_point, bool reverse_order) {
- if (orientation_test(segment_site.point0(true), segment_site.point1(true),
- new_point) != RIGHT_ORIENTATION) {
- return (!segment_site.is_inverse()) ? LESS : MORE;
+ template <typename Site>
+ static kPredicateResult fast_less_predicate_ps(const Site &left_site,
+ const Site &right_site,
+ const Site &new_site,
+ bool reverse_order) {
+ typedef typename Site::point_type point_type;
+ const point_type &site_point = left_site.point0();
+ const point_type &segment_start = right_site.point0(true);
+ const point_type &segment_end = right_site.point1(true);
+ const point_type &new_point = new_site.point0();
+ if (orientation_test(segment_start, segment_end, new_point) != RIGHT_ORIENTATION) {
+ return (!right_site.is_inverse()) ? LESS : MORE;
}
- const point_2d<T> &segment_start = segment_site.point0(true);
- const point_2d<T> &segment_end = segment_site.point1(true);
double dif_x = new_point.x() - site_point.x();
double dif_y = new_point.y() - site_point.y();
double a = segment_end.x() - segment_start.x();
double b = segment_end.y() - segment_start.y();
- if (segment_site.is_vertical()) {
+ if (right_site.is_vertical()) {
if (new_point.y() < site_point.y() && !reverse_order)
return MORE;
else if (new_point.y() > site_point.y() && reverse_order)
@@ -897,7 +763,7 @@
} else {
kOrientation orientation = orientation_test(a, b, dif_x, dif_y);
if (orientation == LEFT_ORIENTATION) {
- if (!segment_site.is_inverse())
+ if (!right_site.is_inverse())
return reverse_order ? LESS : UNDEFINED;
return reverse_order ? UNDEFINED : MORE;
}
@@ -918,17 +784,19 @@
// through intersection point of the given two arcs returns false also.
// reverse_order flag defines arrangement of the sites. If it's false
// the order is (point, segment), else - (segment, point).
- template <typename T>
- static bool less_predicate(point_2d<T> site_point, site_event<T> segment_site,
- point_2d<T> new_point, bool reverse_order) {
- kPredicateResult fast_res = fast_less_predicate(
- site_point, segment_site, new_point, reverse_order);
+ template <typename Site>
+ static bool less_predicate_ps(const Site &left_site,
+ const Site &right_site,
+ const Site &new_site,
+ bool reverse_order) {
+ kPredicateResult fast_res = fast_less_predicate_ps(
+ left_site, right_site, new_site, reverse_order);
if (fast_res != UNDEFINED) {
return (fast_res == LESS);
}
- double dist1 = find_distance_to_point_arc(site_point, new_point);
- double dist2 = find_distance_to_segment_arc(segment_site, new_point);
+ double dist1 = find_distance_to_point_arc(left_site, new_site.point0());
+ double dist2 = find_distance_to_segment_arc(right_site, new_site.point0());
// The undefined ulp range is equal to 3EPS + 8EPS <= 11ULP.
return reverse_order ^ (dist1 < dist2);
@@ -937,23 +805,23 @@
// Returns true if a horizontal line going through a new site intersects
// right arc at first, else returns false. If horizontal line goes
// through intersection point of the given two arcs returns false also.
- template <typename T>
- static bool less_predicate(site_event<T> left_segment,
- site_event<T> right_segment,
- point_2d<T> new_point) {
+ template <typename Site>
+ static bool less_predicate_ss(const Site &left_site,
+ const Site &right_site,
+ const Site &new_site) {
// Handle temporary segment sites.
- if (left_segment.index() == right_segment.index()) {
- return orientation_test(left_segment.point0(),
- left_segment.point1(),
- new_point) == LEFT_ORIENTATION;
+ if (left_site.index() == right_site.index()) {
+ return orientation_test(left_site.point0(),
+ left_site.point1(),
+ new_site.point0()) == LEFT_ORIENTATION;
}
// Distances between the x-coordinate of the sweepline and
// the x-coordinates of the points of the intersections of the
// horizontal line going through the new site with arcs corresponding
// to the first and to the second segment sites respectively.
- double dist1 = find_distance_to_segment_arc(left_segment, new_point);
- double dist2 = find_distance_to_segment_arc(right_segment, new_point);
+ double dist1 = find_distance_to_segment_arc(left_site, new_site.point0());
+ double dist2 = find_distance_to_segment_arc(right_site, new_site.point0());
// The undefined ulp range is equal to 8EPS + 8EPS <= 16ULP.
return dist1 < dist2;
@@ -1711,29 +1579,26 @@
// why the order of the sites is important to define the unique bisector.
// The one site is considered to be newer than the other in case it was
// processed by the algorithm later.
- template <typename T>
+ template <typename SEvent>
class beach_line_node_key {
public:
- typedef T coordinate_type;
- typedef point_2d<T> point_type;
- typedef site_event<T> site_event_type;
+ typedef SEvent site_event_type;
+ typedef typename site_event_type::coordinate_type coordinate_type;
+ typedef typename site_event_type::point_type point_type;
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_key(const site_event_type &new_site) {
- left_site_ = new_site;
- right_site_ = 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_key(const site_event_type &left_site,
- const site_event_type &right_site) {
- left_site_ = left_site;
- right_site_ = 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) {}
const site_event_type &left_site() const {
return left_site_;
@@ -1759,66 +1624,7 @@
right_site_.inverse();
}
- // Get the x coordinate of the newer site.
- coordinate_type comparison_x() const {
- return (left_site_.index() >= right_site_.index()) ?
- left_site_.x() : right_site_.x();
- }
-
- // Get comparison pair: y coordinate and direction of the newer site.
- std::pair<coordinate_type, int> comparison_y(bool is_new_node = true) const {
- if (left_site_.index() == right_site_.index()) {
- return std::make_pair(left_site_.y(), 0);
- }
- if (left_site_.index() > right_site_.index()) {
- if (!is_new_node && left_site_.is_segment() && left_site_.is_vertical()) {
- return std::make_pair(left_site_.y1(), 1);
- }
- return std::make_pair(left_site_.y(), 1);
- }
- return std::make_pair(right_site_.y(), -1);
- }
-
- // Get the index of the newer site.
- int comparison_index() const {
- return (left_site_.index() > right_site_.index()) ?
- left_site_.index() : right_site_.index();
- }
-
- // Get the newer site.
- const site_event_type &comparison_site() const {
- return (left_site_.index() >= right_site_.index()) ?
- left_site_ : right_site_;
- }
-
- // Return true if the horizontal line going through the new site
- // intersects the arc corresponding to the right_site before the
- // arc corresponding to the left_site.
- bool less(const point_type &new_site) const {
- if (!left_site_.is_segment()) {
- return (!right_site_.is_segment()) ? less_pp(new_site) : less_ps(new_site);
- } else {
- return (!right_site_.is_segment()) ? less_sp(new_site) : less_ss(new_site);
- }
- }
-
private:
- bool less_pp(const point_type &new_site) const {
- return less_predicate(left_site_.point0(), right_site_.point0(), new_site);
- }
-
- bool less_ps(const point_type &new_site) const {
- return less_predicate(left_site_.point0(), right_site_, new_site, false);
- }
-
- bool less_sp(const point_type &new_site) const {
- return less_predicate(right_site_.point0(), left_site_, new_site, true);
- }
-
- bool less_ss(const point_type &new_site) const {
- return less_predicate(left_site_, right_site_, new_site);
- }
-
site_event_type left_site_;
site_event_type right_site_;
};
@@ -1827,22 +1633,22 @@
// associated as a value with beach line bisector as a key in the beach
// line. Contains iterator to the circle event in the circle event
// queue in case it's the second bisector that forms a circle event.
- template <typename T>
+ template <typename CEvent>
class beach_line_node_data {
public:
explicit beach_line_node_data(void *new_edge) :
- edge_(new_edge),
- contains_circle_event_(false) {}
+ circle_event_(0),
+ edge_(new_edge) {}
- void activate_circle_event(typename circle_events_queue<T>::circle_event_type_it it) {
- circle_event_it_ = it;
- contains_circle_event_ = true;
+ void activate_circle_event(CEvent *circle_event) {
+ circle_event_ = circle_event;
}
void deactivate_circle_event() {
- if (contains_circle_event_)
- circle_event_it_->deactivate();
- contains_circle_event_ = false;
+ if (circle_event_) {
+ circle_event_->deactivate();
+ circle_event_ = 0;
+ }
}
void *edge() const {
@@ -1854,16 +1660,18 @@
}
private:
- typename circle_events_queue<T>::circle_event_type_it circle_event_it_;
+ CEvent *circle_event_;
void *edge_;
- bool contains_circle_event_;
};
// Beach line comparison functor.
template <typename BeachLineNode>
- struct node_comparer {
+ class beach_line_node_comparer {
public:
+ typedef BeachLineNode beach_line_node_type;
typedef typename BeachLineNode::coordinate_type coordinate_type;
+ typedef typename BeachLineNode::point_type point_type;
+ typedef typename BeachLineNode::site_event_type site_event_type;
// Compares nodes in the balanced binary search tree. Nodes are
// compared based on the y coordinates of the arcs intersection points.
@@ -1871,38 +1679,95 @@
// Comparison is only called during the new site events processing.
// That's why one of the nodes will always lie on the sweepline and may
// be represented as a straight horizontal line.
- bool operator() (const BeachLineNode &node1,
- const BeachLineNode &node2) const {
+ bool operator() (const beach_line_node_type &node1,
+ const beach_line_node_type &node2) const {
// Get x coordinate of the righmost site from both nodes.
- coordinate_type node1_x = node1.comparison_x();
- coordinate_type node2_x = node2.comparison_x();
+ coordinate_type node1_x = get_comparison_x(node1);
+ coordinate_type node2_x = get_comparison_x(node2);
if (node1_x < node2_x) {
// The second node contains a new site.
- return node1.less(node2.comparison_site().point0());
+ return less(node1, get_comparison_site(node2));
} else if (node1_x > node2_x) {
// The first node contains a new site.
- return !node2.less(node1.comparison_site().point0());
+ return !less(node2, get_comparison_site(node1));
} else {
// This checks were evaluated experimentally.
- if (node1.comparison_index() == node2.comparison_index()) {
- // Both nodes are new (inserted during the same site event
- // processing).
- return node1.comparison_y() < node2.comparison_y();
- } else if (node1.comparison_index() < node2.comparison_index()) {
- std::pair<coordinate_type, int> y1 = node1.comparison_y(false);
- std::pair<coordinate_type, int> y2 = node2.comparison_y();
- if (y1.first != y2.first) {
- return y1.first < y2.first;
- }
- return (!node1.comparison_site().is_segment()) ? (y1.second < 0) : false;
+ int index1 = get_comparison_index(node1);
+ int index2 = get_comparison_index(node2);
+ if (index1 == index2) {
+ // Both nodes are new (inserted during the same site event processing).
+ return get_comparison_y(node1) < get_comparison_y(node2);
+ } else if (index1 < index2) {
+ std::pair<coordinate_type, int> y1 = get_comparison_y(node1, false);
+ std::pair<coordinate_type, int> y2 = get_comparison_y(node2, true);
+ if (y1.first != y2.first) return y1.first < y2.first;
+ return (!get_comparison_site(node1).is_segment()) ? (y1.second < 0) : false;
} else {
- std::pair<coordinate_type, int> y1 = node1.comparison_y();
- std::pair<coordinate_type, int> y2 = node2.comparison_y(false);
- if (y1.first != y2.first) {
- return y1.first < y2.first;
- }
- return (!node2.comparison_site().is_segment()) ? (y2.second > 0) : true;
+ std::pair<coordinate_type, int> y1 = get_comparison_y(node1, true);
+ std::pair<coordinate_type, int> y2 = get_comparison_y(node2, false);
+ if (y1.first != y2.first) return y1.first < y2.first;
+ return (!get_comparison_site(node2).is_segment()) ? (y2.second > 0) : true;
+ }
+ }
+ }
+
+ private:
+ // Get the x coordinate of the newer site.
+ coordinate_type get_comparison_x(const beach_line_node_type &node) const {
+ if (node.left_site().index() >= node.right_site().index()) {
+ return node.left_site().x();
+ }
+ return node.right_site().x();
+ }
+
+ // Get comparison pair: y coordinate and direction of the newer site.
+ std::pair<coordinate_type, int> get_comparison_y(const beach_line_node_type &node,
+ bool is_new_node = true) const {
+ if (node.left_site().index() == node.right_site().index()) {
+ return std::make_pair(node.left_site().y(), 0);
+ }
+ if (node.left_site().index() > node.right_site().index()) {
+ if (!is_new_node &&
+ node.left_site().is_segment() &&
+ node.left_site().is_vertical()) {
+ return std::make_pair(node.left_site().y1(), 1);
+ }
+ return std::make_pair(node.left_site().y(), 1);
+ }
+ return std::make_pair(node.right_site().y(), -1);
+ }
+
+ // Get the index of the newer site.
+ int get_comparison_index(const beach_line_node_type &node) const {
+ if (node.left_site().index() > node.right_site().index()) {
+ return node.left_site().index();
+ }
+ return node.right_site().index();
+ }
+
+ // Get the newer site.
+ const site_event_type &get_comparison_site(const beach_line_node_type &node) const {
+ if (node.left_site().index() > node.right_site().index()) {
+ return node.left_site();
+ }
+ return node.right_site();
+ }
+
+ bool less(const beach_line_node_type &lhs, const site_event_type &new_site) const {
+ const site_event_type &left_site = lhs.left_site();
+ const site_event_type &right_site = lhs.right_site();
+ if (!left_site.is_segment()) {
+ if (!right_site.is_segment()) {
+ return less_predicate_pp(left_site, right_site, new_site);
+ } else {
+ return less_predicate_ps(left_site, right_site, new_site, false);
+ }
+ } else {
+ if (!right_site.is_segment()) {
+ return less_predicate_ps(right_site, left_site, new_site, true);
+ } else {
+ return less_predicate_ss(left_site, right_site, new_site);
}
}
}
Modified: sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_builder.hpp
==============================================================================
--- sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_builder.hpp (original)
+++ sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_builder.hpp 2011-09-21 15:01:54 EDT (Wed, 21 Sep 2011)
@@ -36,10 +36,10 @@
///////////////////////////////////////////////////////////////////////////
template <typename T>
- struct voronoi_traits;
+ struct voronoi_builder_traits;
template <>
- struct voronoi_traits<int> {
+ struct voronoi_builder_traits<int> {
typedef double coordinate_type;
};
@@ -97,7 +97,7 @@
template <typename T, typename VD>
class voronoi_builder {
public:
- typedef typename voronoi_traits<T>::coordinate_type coordinate_type;
+ typedef typename voronoi_builder_traits<T>::coordinate_type coordinate_type;
typedef VD output_type;
voronoi_builder() {}
@@ -106,7 +106,7 @@
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(
+ site_events_.push_back(detail::site_event<coordinate_type>(
static_cast<coordinate_type>(it->x()),
static_cast<coordinate_type>(it->y()), 0));
}
@@ -123,9 +123,9 @@
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));
+ site_events_.push_back(detail::site_event<coordinate_type>(x1, y1, 0));
+ site_events_.push_back(detail::site_event<coordinate_type>(x2, y2, 0));
+ site_events_.push_back(detail::site_event<coordinate_type>(x1, y1, x2, y2, 0));
}
}
@@ -155,12 +155,15 @@
} else if (site_event_iterator_ == site_events_.end()) {
process_circle_event();
} else {
- if (circle_events_.top().compare(*site_event_iterator_) == detail::MORE) {
+ if (circle_events_.top().first.compare(*site_event_iterator_) == detail::MORE) {
process_site_event();
} else {
process_circle_event();
}
}
+ while (!circle_events_.empty() && !circle_events_.top().first.is_active()) {
+ circle_events_.pop();
+ }
}
beach_line_.clear();
@@ -175,18 +178,27 @@
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 detail::circle_event<coordinate_type> circle_event_type;
+ typedef detail::beach_line_node_key<site_event_type> key_type;
+ typedef detail::beach_line_node_data<circle_event_type> value_type;
+ typedef detail::beach_line_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<circle_event_type, beach_line_iterator> event_type;
+ typedef struct {
+ bool operator()(const event_type &lhs, const event_type &rhs) const {
+ return lhs.first > rhs.first;
+ }
+ } event_comparison;
+ typedef detail::ordered_queue<event_type, event_comparison>
+ circle_event_queue_type;
+ typedef typename output_type::voronoi_edge_type edge_type;
typedef std::pair<point_type, beach_line_iterator> end_point_type;
// Create site events.
@@ -394,8 +406,9 @@
// 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();
+ const event_type &e = circle_events_.top();
+ const circle_event_type &circle_event = e.first;
+ beach_line_iterator it_first = e.second;
beach_line_iterator it_last = it_first;
// Get the C site.
@@ -544,15 +557,12 @@
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));
+ event_type &e = circle_events_.push(
+ std::pair<circle_event_type, beach_line_iterator>(c_event, bisector_node));
+ bisector_node->second.activate_circle_event(&e.first);
}
}
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-21 15:01:54 EDT (Wed, 21 Sep 2011)
@@ -18,6 +18,8 @@
#include "boost/polygon/polygon.hpp"
using namespace boost::polygon;
+#include "detail/voronoi_fpt_kernel.hpp"
+
namespace boost {
namespace sweepline {
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-21 15:01:54 EDT (Wed, 21 Sep 2011)
@@ -19,48 +19,30 @@
typedef boost::mpl::list<double> test_types;
-#define CHECK_TOP_ELEMENT_EQUALITY(TOP, X, Y) \
- BOOST_CHECK_EQUAL(TOP.lower_x() == static_cast<T>(X) && \
- TOP.y() == static_cast<T>(Y), true)
-
BOOST_AUTO_TEST_CASE_TEMPLATE(event_queue_test1, T, test_types) {
- circle_events_queue<T> event_q;
+ ordered_queue<T, std::greater<T> > event_q;
BOOST_CHECK_EQUAL(event_q.empty(), true);
-
- event_q.clear();
- for (int i = 0; i < 10; i++) {
- T x = static_cast<T>(-i);
- T y = static_cast<T>(10-i);
- event_q.push(make_circle_event<T>(x, y, x + static_cast<T>(10)));
+ for (int i = 0; i <= 10; ++i) {
+ event_q.push(static_cast<T>(20 - 2 * i));
+ event_q.push(static_cast<T>(2 * i + 1));
}
-
- for (int i = 0; i < 10; i++) {
- CHECK_TOP_ELEMENT_EQUALITY(event_q.top(), 1 + i, 1 + i);
+ BOOST_CHECK_EQUAL(event_q.empty(), false);
+ for (int i = 0; i <= 21; ++i) {
+ T top = event_q.top();
event_q.pop();
+ BOOST_CHECK_EQUAL(top, static_cast<T>(i));
}
-
BOOST_CHECK_EQUAL(event_q.empty(), true);
}
BOOST_AUTO_TEST_CASE_TEMPLATE(event_queue_test2, T, test_types) {
- typedef circle_event<T> circle_event_type;
- circle_events_queue<T> event_q;
- site_event<T> temp_site = make_site_event<T>(static_cast<T>(0), static_cast<T>(0), 0);
-
- for (int i = 0; i < 10; i++) {
- T x = static_cast<T>(10-i);
- T y = static_cast<T>(10-i);
- circle_event_type c = make_circle_event<T>(x, y, x);
- if (i&1)
- event_q.push(c)->deactivate();
- else
- event_q.push(c);
+ ordered_queue<T, std::greater<T> > event_q;
+ for (int i = 0; i <= 10; i++) {
+ event_q.push(static_cast<T>(i)) *= 2;
}
-
- for (int i = 0; i < 5; i++) {
- CHECK_TOP_ELEMENT_EQUALITY(event_q.top(), 2 + 2*i, 2 + 2*i);
+ for (int i = 0; i <= 10; i++) {
+ BOOST_CHECK_EQUAL(event_q.top(), static_cast<T>(2 * i));
event_q.pop();
}
-
BOOST_CHECK_EQUAL(event_q.empty(), true);
}
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-21 15:01:54 EDT (Wed, 21 Sep 2011)
@@ -46,22 +46,22 @@
}
BOOST_AUTO_TEST_CASE_TEMPLATE(site_event_test1, T, test_types) {
- site_event<T> site1 = make_site_event<T>(static_cast<T>(1), static_cast<T>(2), 0);
+ site_event<T> site1 = site_event<T>(static_cast<T>(1), static_cast<T>(2), 0);
site_event<T> site2;
BOOST_CHECK_EQUAL(site1.x(), static_cast<T>(1));
BOOST_CHECK_EQUAL(site1.y(), static_cast<T>(2));
BOOST_CHECK_EQUAL(site1.index(), 0);
- site2 = make_site_event<T>(static_cast<T>(0), static_cast<T>(2), 1);
+ site2 = site_event<T>(static_cast<T>(0), static_cast<T>(2), 1);
bool arr1[] = { false, true, false, true, false, true };
EVENT_TYPES_CHECK_COMPARISON(site1, site2, arr1);
- site2 = make_site_event<T>(static_cast<T>(1), static_cast<T>(3), 1);
+ site2 = site_event<T>(static_cast<T>(1), static_cast<T>(3), 1);
bool arr2[] = { true, false, true, false, false, true };
EVENT_TYPES_CHECK_COMPARISON(site1, site2, arr2);
- site2 = make_site_event<T>(static_cast<T>(1), static_cast<T>(2), 1);
+ site2 = site_event<T>(static_cast<T>(1), static_cast<T>(2), 1);
bool arr3[] = { false, false, true, true, true, false };
EVENT_TYPES_CHECK_COMPARISON(site1, site2, arr3);
}
@@ -73,14 +73,14 @@
point_2d<T> point3 = point_2d<T>(static_cast<T>(0), static_cast<T>(-2));
point_2d<T> point4 = point_2d<T>(static_cast<T>(0), static_cast<T>(-1));
point_2d<T> point5 = point_2d<T>(static_cast<T>(1), static_cast<T>(1));
- site_event<T> site1 = make_site_event<T>(point1, point2, 0);
+ site_event<T> site1 = site_event<T>(point1, point2, 0);
BOOST_CHECK_EQUAL(point1 == site1.point1(), true);
BOOST_CHECK_EQUAL(point2 == site1.point0(), true);
BOOST_CHECK_EQUAL(site1.is_segment(), true);
BOOST_CHECK_EQUAL(site1.is_vertical(), true);
- site_event<T> site2 = make_site_event<T>(point1, 0);
+ site_event<T> site2 = site_event<T>(point1, 0);
BOOST_CHECK_EQUAL(site2.is_segment(), false);
BOOST_CHECK_EQUAL(site2.is_vertical(), true);
@@ -89,25 +89,25 @@
EVENT_TYPES_CHECK_COMPARISON(site1, site2, arr1_1);
EVENT_TYPES_CHECK_COMPARISON(site2, site1, arr1_2);
- site2 = make_site_event<T>(point2, 0);
+ site2 = site_event<T>(point2, 0);
bool arr2_1[] = { false, true, false, true, false, true };
bool arr2_2[] = { true, false, true, false, false, true };
EVENT_TYPES_CHECK_COMPARISON(site1, site2, arr2_1);
EVENT_TYPES_CHECK_COMPARISON(site2, site1, arr2_2);
- site2 = make_site_event<T>(point3, point4, 0);
+ site2 = site_event<T>(point3, point4, 0);
bool arr3_1[] = { false, true, false, true, false, true };
bool arr3_2[] = { true, false, true, false, false, true };
EVENT_TYPES_CHECK_COMPARISON(site1, site2, arr3_1);
EVENT_TYPES_CHECK_COMPARISON(site2, site1, arr3_2);
- site2 = make_site_event<T>(point3, point5, 0);
+ site2 = site_event<T>(point3, point5, 0);
bool arr4_1[] = { true, false, true, false, false, true };
bool arr4_2[] = { false, true, false, true, false, true };
EVENT_TYPES_CHECK_COMPARISON(site1, site2, arr4_1);
EVENT_TYPES_CHECK_COMPARISON(site2, site1, arr4_2);
- site2 = make_site_event<T>(point2, point5, 0);
+ site2 = site_event<T>(point2, point5, 0);
bool arr5_1[] = { true, false, true, false, false, true };
bool arr5_2[] = { false, true, false, true, false, true };
EVENT_TYPES_CHECK_COMPARISON(site1, site2, arr5_1);
@@ -119,98 +119,98 @@
point_2d<T> point2 = point_2d<T>(static_cast<T>(0), static_cast<T>(0));
point_2d<T> point3 = point_2d<T>(static_cast<T>(0), static_cast<T>(1));
point_2d<T> point4 = point_2d<T>(static_cast<T>(0), static_cast<T>(10));
- site_event<T> site1 = make_site_event<T>(point1, point2, 0);
+ site_event<T> site1 = site_event<T>(point1, point2, 0);
BOOST_CHECK_EQUAL(point1 == site1.point1(), true);
BOOST_CHECK_EQUAL(point2 == site1.point0(), true);
BOOST_CHECK_EQUAL(site1.is_segment(), true);
BOOST_CHECK_EQUAL(site1.is_vertical(), false);
- site_event<T> site2 = make_site_event<T>(point2, 0);
+ site_event<T> site2 = site_event<T>(point2, 0);
bool arr1_1[] = { false, true, false, true, false, true };
bool arr1_2[] = { true, false, true, false, false, true };
EVENT_TYPES_CHECK_COMPARISON(site1, site2, arr1_1);
EVENT_TYPES_CHECK_COMPARISON(site2, site1, arr1_2);
- site2 = make_site_event<T>(static_cast<T>(0), static_cast<T>(-1), 0);
+ site2 = site_event<T>(static_cast<T>(0), static_cast<T>(-1), 0);
EVENT_TYPES_CHECK_COMPARISON(site1, site2, arr1_1);
EVENT_TYPES_CHECK_COMPARISON(site2, site1, arr1_2);
- site2 = make_site_event<T>(static_cast<T>(0), static_cast<T>(1), 0);
+ site2 = site_event<T>(static_cast<T>(0), static_cast<T>(1), 0);
EVENT_TYPES_CHECK_COMPARISON(site1, site2, arr1_1);
EVENT_TYPES_CHECK_COMPARISON(site2, site1, arr1_2);
- site2 = make_site_event<T>(point3, point4, 0);
+ site2 = site_event<T>(point3, point4, 0);
EVENT_TYPES_CHECK_COMPARISON(site1, site2, arr1_1);
EVENT_TYPES_CHECK_COMPARISON(site2, site1, arr1_2);
point3 = point_2d<T>(static_cast<T>(0), static_cast<T>(-10));
point4 = point_2d<T>(static_cast<T>(0), static_cast<T>(-1));
- site2 = make_site_event<T>(point3, point4, 0);
+ site2 = site_event<T>(point3, point4, 0);
EVENT_TYPES_CHECK_COMPARISON(site1, site2, arr1_1);
EVENT_TYPES_CHECK_COMPARISON(site2, site1, arr1_2);
point4 = point_2d<T>(static_cast<T>(10), static_cast<T>(9));
- site2 = make_site_event<T>(point2, point4, 0);
+ site2 = site_event<T>(point2, point4, 0);
EVENT_TYPES_CHECK_COMPARISON(site1, site2, arr1_2);
EVENT_TYPES_CHECK_COMPARISON(site2, site1, arr1_1);
point4 = point_2d<T>(static_cast<T>(9), static_cast<T>(10));
- site2 = make_site_event<T>(point2, point4, 0);
+ site2 = site_event<T>(point2, point4, 0);
EVENT_TYPES_CHECK_COMPARISON(site1, site2, arr1_1);
EVENT_TYPES_CHECK_COMPARISON(site2, site1, arr1_2);
}
BOOST_AUTO_TEST_CASE_TEMPLATE(circle_event_test1, T, test_types) {
- circle_event<T> circle1 = make_circle_event<T>(static_cast<T>(1),
+ circle_event<T> circle1 = circle_event<T>(static_cast<T>(1),
static_cast<T>(2),
static_cast<T>(3));
- site_event<T> temp_site = make_site_event<T>(static_cast<T>(0), static_cast<T>(0),0);
+ site_event<T> temp_site = site_event<T>(static_cast<T>(0), static_cast<T>(0),0);
circle_event<T> circle2;
BOOST_CHECK_EQUAL(circle1.x(), static_cast<T>(1));
BOOST_CHECK_EQUAL(circle1.y(), static_cast<T>(2));
BOOST_CHECK_EQUAL(circle1.lower_x(), static_cast<T>(3));
- circle2 = make_circle_event<T>(static_cast<T>(1), static_cast<T>(2), static_cast<T>(3));
+ circle2 = circle_event<T>(static_cast<T>(1), static_cast<T>(2), static_cast<T>(3));
bool arr1[] = { false, false, true, true, true, false };
EVENT_TYPES_CHECK_COMPARISON(circle1, circle2, arr1);
- circle2 = make_circle_event<T>(static_cast<T>(1), static_cast<T>(3), static_cast<T>(3));
+ circle2 = circle_event<T>(static_cast<T>(1), static_cast<T>(3), static_cast<T>(3));
bool arr2[] = { true, false, true, false, false, true };
EVENT_TYPES_CHECK_COMPARISON(circle1, circle2, arr2);
- circle2 = make_circle_event<T>(static_cast<T>(1), static_cast<T>(2), static_cast<T>(4));
+ circle2 = circle_event<T>(static_cast<T>(1), static_cast<T>(2), static_cast<T>(4));
bool arr3[] = { true, false, true, false, false, true };
EVENT_TYPES_CHECK_COMPARISON(circle1, circle2, arr3);
- circle2 = make_circle_event<T>(static_cast<T>(0), static_cast<T>(2), static_cast<T>(2));
+ circle2 = circle_event<T>(static_cast<T>(0), static_cast<T>(2), static_cast<T>(2));
bool arr4[] = { false, true, false, true, false, true };
EVENT_TYPES_CHECK_COMPARISON(circle1, circle2, arr4);
- circle2 = make_circle_event<T>(static_cast<T>(-1), static_cast<T>(2), static_cast<T>(3));
+ circle2 = circle_event<T>(static_cast<T>(-1), static_cast<T>(2), static_cast<T>(3));
bool arr5[] = { false, false, true, true, true, false };
EVENT_TYPES_CHECK_COMPARISON(circle1, circle2, arr5);
}
BOOST_AUTO_TEST_CASE_TEMPLATE(circle_event_test2, T, test_types) {
- circle_event<T> circle = make_circle_event<T>(static_cast<T>(1),
+ circle_event<T> circle = circle_event<T>(static_cast<T>(1),
static_cast<T>(2),
static_cast<T>(3));
site_event<T> site;
- site = make_site_event<T>(static_cast<T>(0), static_cast<T>(100), 0);
+ site = site_event<T>(static_cast<T>(0), static_cast<T>(100), 0);
BOOST_CHECK_EQUAL(circle.compare(site), 1);
- site = make_site_event<T>(static_cast<T>(3), static_cast<T>(0), 0);
+ site = site_event<T>(static_cast<T>(3), static_cast<T>(0), 0);
BOOST_CHECK_EQUAL(circle.compare(site), 1);
- site = make_site_event<T>(static_cast<T>(3), static_cast<T>(2), 0);
+ site = site_event<T>(static_cast<T>(3), static_cast<T>(2), 0);
BOOST_CHECK_EQUAL(circle.compare(site), 0);
- site = make_site_event<T>(static_cast<T>(3), static_cast<T>(3), 0);
+ site = site_event<T>(static_cast<T>(3), static_cast<T>(3), 0);
BOOST_CHECK_EQUAL(circle.compare(site), -1);
- site = make_site_event<T>(static_cast<T>(4), static_cast<T>(2), 0);
+ site = site_event<T>(static_cast<T>(4), static_cast<T>(2), 0);
BOOST_CHECK_EQUAL(circle.compare(site), -1);
}
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-21 15:01:54 EDT (Wed, 21 Sep 2011)
@@ -17,75 +17,73 @@
typedef boost::mpl::list<double> test_types;
+#define DEFINE_BEACH_LINE \
+ typedef site_event<T> site_event_type; \
+ typedef beach_line_node_key<site_event_type> key_type; \
+ typedef beach_line_node_comparer<key_type> node_comparer_type; \
+ typedef std::map< key_type, int, node_comparer_type > beach_line_type; \
+ typedef typename beach_line_type::iterator beach_line_iterator
+
BOOST_AUTO_TEST_CASE_TEMPLATE(node_comparer_test_pp1, T, test_types) {
- typedef site_event<T> site_event_type;
- typedef beach_line_node_key<T> bline_node;
- typedef typename std::map< bline_node, int,
- node_comparer<bline_node> >::const_iterator bline_it;
-
- std::map< bline_node, int, node_comparer<bline_node> > test_beach_line;
-
- site_event_type site1 = make_site_event<T>(static_cast<T>(0), static_cast<T>(0), 0);
- site_event_type site2 = make_site_event<T>(static_cast<T>(0), static_cast<T>(2), 1);
- bline_node initial_node(site1, site2);
+ DEFINE_BEACH_LINE;
+ beach_line_type test_beach_line;
+
+ site_event_type site1 = site_event<T>(static_cast<T>(0), static_cast<T>(0), 0);
+ site_event_type site2 = site_event<T>(static_cast<T>(0), static_cast<T>(2), 1);
+ key_type initial_node(site1, site2);
test_beach_line[initial_node] = 2;
- site_event_type site3 = make_site_event<T>(static_cast<T>(1), static_cast<T>(0), 2);
- bline_node node1(site1, site3);
- bline_node node2(site3, site1);
- test_beach_line.insert(std::pair<bline_node, int>(node1, 0));
- test_beach_line.insert(std::pair<bline_node, int>(node2, 1));
+ site_event_type site3 = site_event<T>(static_cast<T>(1), static_cast<T>(0), 2);
+ key_type node1(site1, site3);
+ key_type node2(site3, site1);
+ test_beach_line.insert(std::pair<key_type, int>(node1, 0));
+ test_beach_line.insert(std::pair<key_type, int>(node2, 1));
int cur_value = 0;
- for (bline_it it = test_beach_line.begin();
+ for (beach_line_iterator it = test_beach_line.begin();
it != test_beach_line.end();
it++, cur_value++)
BOOST_CHECK_EQUAL(it->second, cur_value);
}
BOOST_AUTO_TEST_CASE_TEMPLATE(node_comparer_test_pp2, T, test_types) {
- typedef site_event<T> site_event_type;
- typedef beach_line_node_key<T> bline_node;
- typedef typename std::map< bline_node, int,
- node_comparer<bline_node> >::const_iterator bline_it;
-
- std::map< bline_node, int, node_comparer<bline_node> > test_beach_line;
-
- site_event_type site1 = make_site_event<T>(static_cast<T>(0), static_cast<T>(1), 0);
- site_event_type site2 = make_site_event<T>(static_cast<T>(2), static_cast<T>(0), 1);
- site_event_type site3 = make_site_event<T>(static_cast<T>(2), static_cast<T>(4), 2);
- bline_node initial_node1(site1, site2);
- bline_node initial_node2(site2, site1);
- test_beach_line.insert(std::pair<bline_node, int>(initial_node1, 0));
- test_beach_line.insert(std::pair<bline_node, int>(initial_node2, 1));
-
- bline_node new_node1(site1, site3);
- bline_node new_node2(site3, site1);
- test_beach_line.insert(std::pair<bline_node, int>(new_node1, 2));
- test_beach_line.insert(std::pair<bline_node, int>(new_node2, 3));
+ DEFINE_BEACH_LINE;
+ beach_line_type test_beach_line;
+
+ site_event_type site1 = site_event<T>(static_cast<T>(0), static_cast<T>(1), 0);
+ site_event_type site2 = site_event<T>(static_cast<T>(2), static_cast<T>(0), 1);
+ site_event_type site3 = site_event<T>(static_cast<T>(2), static_cast<T>(4), 2);
+ key_type initial_node1(site1, site2);
+ key_type initial_node2(site2, site1);
+ test_beach_line.insert(std::pair<key_type, int>(initial_node1, 0));
+ test_beach_line.insert(std::pair<key_type, int>(initial_node2, 1));
+
+ key_type new_node1(site1, site3);
+ key_type new_node2(site3, site1);
+ test_beach_line.insert(std::pair<key_type, int>(new_node1, 2));
+ test_beach_line.insert(std::pair<key_type, int>(new_node2, 3));
int cur_value = 0;
- for (bline_it it = test_beach_line.begin();
+ for (beach_line_iterator it = test_beach_line.begin();
it != test_beach_line.end();
it++, cur_value++)
BOOST_CHECK_EQUAL(it->second, cur_value);
}
BOOST_AUTO_TEST_CASE_TEMPLATE(node_comparer_test_pp3, T, test_types) {
- typedef point_2d<T> Point2D;
- typedef beach_line_node_key<T> bline_node;
- node_comparer<bline_node> node_comparer_test;
-
- bline_node initial_node(
- make_site_event<T>(static_cast<T>(1), static_cast<T>(0), 0),
- make_site_event<T>(static_cast<T>(0), static_cast<T>(2), 1));
-
- bline_node new_node1(make_site_event<T>(static_cast<T>(2), static_cast<T>(-10), 2));
- bline_node new_node2(make_site_event<T>(static_cast<T>(2), static_cast<T>(-1), 3));
- bline_node new_node3(make_site_event<T>(static_cast<T>(2), static_cast<T>(0), 4));
- bline_node new_node4(make_site_event<T>(static_cast<T>(2), static_cast<T>(1), 4));
- bline_node new_node5(make_site_event<T>(static_cast<T>(2), static_cast<T>(2), 4));
- bline_node new_node6(make_site_event<T>(static_cast<T>(2), static_cast<T>(3), 4));
+ DEFINE_BEACH_LINE;
+ node_comparer_type node_comparer_test;
+
+ key_type initial_node(
+ site_event<T>(static_cast<T>(1), static_cast<T>(0), 0),
+ site_event<T>(static_cast<T>(0), static_cast<T>(2), 1));
+
+ key_type new_node1(site_event<T>(static_cast<T>(2), static_cast<T>(-10), 2));
+ key_type new_node2(site_event<T>(static_cast<T>(2), static_cast<T>(-1), 3));
+ key_type new_node3(site_event<T>(static_cast<T>(2), static_cast<T>(0), 4));
+ key_type new_node4(site_event<T>(static_cast<T>(2), static_cast<T>(1), 4));
+ key_type new_node5(site_event<T>(static_cast<T>(2), static_cast<T>(2), 4));
+ key_type new_node6(site_event<T>(static_cast<T>(2), static_cast<T>(3), 4));
BOOST_CHECK_EQUAL(node_comparer_test(initial_node, new_node1), false);
@@ -105,20 +103,19 @@
}
BOOST_AUTO_TEST_CASE_TEMPLATE(node_comparer_test_pp4, T, test_types) {
- typedef point_2d<T> Point2D;
- typedef beach_line_node_key<T> bline_node;
- node_comparer<bline_node> node_comparer_test;
-
- bline_node initial_node(
- make_site_event<T>(static_cast<T>(0), static_cast<T>(1), 0),
- make_site_event<T>(static_cast<T>(1), static_cast<T>(0), 1));
-
- bline_node new_node1(make_site_event<T>(static_cast<T>(2), static_cast<T>(-3), 2));
- bline_node new_node2(make_site_event<T>(static_cast<T>(2), static_cast<T>(-2), 2));
- bline_node new_node3(make_site_event<T>(static_cast<T>(2), static_cast<T>(-1), 2));
- bline_node new_node4(make_site_event<T>(static_cast<T>(2), static_cast<T>(0), 2));
- bline_node new_node5(make_site_event<T>(static_cast<T>(2), static_cast<T>(1), 2));
- bline_node new_node6(make_site_event<T>(static_cast<T>(2), static_cast<T>(3), 2));
+ DEFINE_BEACH_LINE;
+ node_comparer_type node_comparer_test;
+
+ key_type initial_node(
+ site_event<T>(static_cast<T>(0), static_cast<T>(1), 0),
+ site_event<T>(static_cast<T>(1), static_cast<T>(0), 1));
+
+ key_type new_node1(site_event<T>(static_cast<T>(2), static_cast<T>(-3), 2));
+ key_type new_node2(site_event<T>(static_cast<T>(2), static_cast<T>(-2), 2));
+ key_type new_node3(site_event<T>(static_cast<T>(2), static_cast<T>(-1), 2));
+ key_type new_node4(site_event<T>(static_cast<T>(2), static_cast<T>(0), 2));
+ key_type new_node5(site_event<T>(static_cast<T>(2), static_cast<T>(1), 2));
+ key_type new_node6(site_event<T>(static_cast<T>(2), static_cast<T>(3), 2));
BOOST_CHECK_EQUAL(node_comparer_test(initial_node, new_node1), false);
BOOST_CHECK_EQUAL(node_comparer_test(initial_node, new_node2), true);
@@ -136,20 +133,19 @@
}
BOOST_AUTO_TEST_CASE_TEMPLATE(node_comparer_test_pp5, T, test_types) {
- typedef point_2d<T> Point2D;
- typedef beach_line_node_key<T> bline_node;
- node_comparer<bline_node> node_comparer_test;
-
- bline_node initial_node(
- make_site_event<T>(static_cast<T>(0), static_cast<T>(0), 0),
- make_site_event<T>(static_cast<T>(1), static_cast<T>(2), 1));
-
- bline_node new_node1(make_site_event<T>(static_cast<T>(2), static_cast<T>(-10), 2));
- bline_node new_node2(make_site_event<T>(static_cast<T>(2), static_cast<T>(0), 3));
- bline_node new_node3(make_site_event<T>(static_cast<T>(2), static_cast<T>(1), 4));
- bline_node new_node4(make_site_event<T>(static_cast<T>(2), static_cast<T>(2), 4));
- bline_node new_node5(make_site_event<T>(static_cast<T>(2), static_cast<T>(5), 4));
- bline_node new_node6(make_site_event<T>(static_cast<T>(2), static_cast<T>(20), 4));
+ DEFINE_BEACH_LINE;
+ node_comparer_type node_comparer_test;
+
+ key_type initial_node(
+ site_event<T>(static_cast<T>(0), static_cast<T>(0), 0),
+ site_event<T>(static_cast<T>(1), static_cast<T>(2), 1));
+
+ key_type new_node1(site_event<T>(static_cast<T>(2), static_cast<T>(-10), 2));
+ key_type new_node2(site_event<T>(static_cast<T>(2), static_cast<T>(0), 3));
+ key_type new_node3(site_event<T>(static_cast<T>(2), static_cast<T>(1), 4));
+ key_type new_node4(site_event<T>(static_cast<T>(2), static_cast<T>(2), 4));
+ key_type new_node5(site_event<T>(static_cast<T>(2), static_cast<T>(5), 4));
+ key_type new_node6(site_event<T>(static_cast<T>(2), static_cast<T>(20), 4));
BOOST_CHECK_EQUAL(node_comparer_test(initial_node, new_node1), false);
@@ -169,21 +165,20 @@
}
BOOST_AUTO_TEST_CASE_TEMPLATE(node_comparer_test_pp6, T, test_types) {
- typedef point_2d<T> Point2D;
- typedef beach_line_node_key<T> bline_node;
- node_comparer<bline_node> node_comparer_test;
-
- bline_node initial_node(
- make_site_event<T>(static_cast<T>(1), static_cast<T>(1), 0),
- make_site_event<T>(static_cast<T>(0), static_cast<T>(0), 1));
-
- bline_node new_node1(make_site_event<T>(static_cast<T>(2), static_cast<T>(-3), 2));
- bline_node new_node2(make_site_event<T>(static_cast<T>(2), static_cast<T>(-2), 3));
- bline_node new_node3(make_site_event<T>(static_cast<T>(2), static_cast<T>(0), 4));
- bline_node new_node4(make_site_event<T>(static_cast<T>(2), static_cast<T>(1), 4));
- bline_node new_node5(make_site_event<T>(static_cast<T>(2), static_cast<T>(2), 4));
- bline_node new_node6(make_site_event<T>(static_cast<T>(2), static_cast<T>(3), 4));
- bline_node new_node7(make_site_event<T>(static_cast<T>(2), static_cast<T>(5), 4));
+ DEFINE_BEACH_LINE;
+ node_comparer_type node_comparer_test;
+
+ key_type initial_node(
+ site_event<T>(static_cast<T>(1), static_cast<T>(1), 0),
+ site_event<T>(static_cast<T>(0), static_cast<T>(0), 1));
+
+ key_type new_node1(site_event<T>(static_cast<T>(2), static_cast<T>(-3), 2));
+ key_type new_node2(site_event<T>(static_cast<T>(2), static_cast<T>(-2), 3));
+ key_type new_node3(site_event<T>(static_cast<T>(2), static_cast<T>(0), 4));
+ key_type new_node4(site_event<T>(static_cast<T>(2), static_cast<T>(1), 4));
+ key_type new_node5(site_event<T>(static_cast<T>(2), static_cast<T>(2), 4));
+ key_type new_node6(site_event<T>(static_cast<T>(2), static_cast<T>(3), 4));
+ key_type new_node7(site_event<T>(static_cast<T>(2), static_cast<T>(5), 4));
BOOST_CHECK_EQUAL(node_comparer_test(initial_node, new_node1), false);
BOOST_CHECK_EQUAL(node_comparer_test(initial_node, new_node2), false);
@@ -203,17 +198,16 @@
}
BOOST_AUTO_TEST_CASE_TEMPLATE(node_comparer_test_pp7, T, test_types) {
- typedef point_2d<T> Point2D;
- typedef beach_line_node_key<T> bline_node;
- node_comparer<bline_node> node_comparer_test;
-
- bline_node initial_node(
- make_site_event<T>(static_cast<T>(0), static_cast<T>(0), 0),
- make_site_event<T>(static_cast<T>(0), static_cast<T>(2), 1));
-
- bline_node new_node1(make_site_event<T>(static_cast<T>(1), static_cast<T>(0), 2));
- bline_node new_node2(make_site_event<T>(static_cast<T>(1), static_cast<T>(1), 3));
- bline_node new_node3(make_site_event<T>(static_cast<T>(1), static_cast<T>(2), 4));
+ DEFINE_BEACH_LINE;
+ node_comparer_type node_comparer_test;
+
+ key_type initial_node(
+ site_event<T>(static_cast<T>(0), static_cast<T>(0), 0),
+ site_event<T>(static_cast<T>(0), static_cast<T>(2), 1));
+
+ key_type new_node1(site_event<T>(static_cast<T>(1), static_cast<T>(0), 2));
+ key_type new_node2(site_event<T>(static_cast<T>(1), static_cast<T>(1), 3));
+ key_type new_node3(site_event<T>(static_cast<T>(1), static_cast<T>(2), 4));
BOOST_CHECK_EQUAL(node_comparer_test(initial_node, new_node1), false);
BOOST_CHECK_EQUAL(node_comparer_test(initial_node, new_node2), false);
@@ -225,20 +219,19 @@
}
BOOST_AUTO_TEST_CASE_TEMPLATE(node_comparer_test_pp8, T, test_types) {
- typedef point_2d<T> Point2D;
- typedef beach_line_node_key<T> bline_node;
- node_comparer<bline_node> node_comparer_test;
-
- bline_node initial_node(
- make_site_event<T>(static_cast<T>(0), static_cast<T>(0), 0),
- make_site_event<T>(static_cast<T>(1), static_cast<T>(1), 1));
-
- bline_node new_node1(make_site_event<T>(static_cast<T>(1), static_cast<T>(0), 2));
- bline_node new_node2(make_site_event<T>(static_cast<T>(1), static_cast<T>(1), 1));
- bline_node new_node3(make_site_event<T>(static_cast<T>(1), static_cast<T>(2), 3));
- bline_node new_node4(
- make_site_event<T>(static_cast<T>(1), static_cast<T>(1), 1),
- make_site_event<T>(static_cast<T>(0), static_cast<T>(0), 0));
+ DEFINE_BEACH_LINE;
+ node_comparer_type node_comparer_test;
+
+ key_type initial_node(
+ site_event<T>(static_cast<T>(0), static_cast<T>(0), 0),
+ site_event<T>(static_cast<T>(1), static_cast<T>(1), 1));
+
+ key_type new_node1(site_event<T>(static_cast<T>(1), static_cast<T>(0), 2));
+ key_type new_node2(site_event<T>(static_cast<T>(1), static_cast<T>(1), 1));
+ key_type new_node3(site_event<T>(static_cast<T>(1), static_cast<T>(2), 3));
+ key_type new_node4(
+ site_event<T>(static_cast<T>(1), static_cast<T>(1), 1),
+ site_event<T>(static_cast<T>(0), static_cast<T>(0), 0));
BOOST_CHECK_EQUAL(node_comparer_test(initial_node, new_node1), false);
BOOST_CHECK_EQUAL(node_comparer_test(initial_node, new_node2), true);
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-21 15:01:54 EDT (Wed, 21 Sep 2011)
@@ -20,21 +20,21 @@
#define CHECK_ORIENTATION_EQUAL(p1, p2, p3, exp) \
BOOST_CHECK_EQUAL(orientation_test(p1, p2, p3) == exp, true)
-#define CHECK_LESS_PREDICATE_PP(lp, rp, np, exp) \
- BOOST_CHECK_EQUAL(less_predicate(lp, rp, np) == exp, true)
+#define CHECK_LESS_PREDICATE_PP(ls, rs, ns, exp) \
+ BOOST_CHECK_EQUAL(less_predicate_pp(ls, rs, ns) == exp, true)
-#define CHECK_FAST_LESS_PREDICATE_PS(lp, rs, np, reverse, exp) \
- BOOST_CHECK_EQUAL(fast_less_predicate(lp, rs, np, reverse) == exp, true); \
+#define CHECK_FAST_LESS_PREDICATE_PS(ls, rs, ns, reverse, exp) \
+ BOOST_CHECK_EQUAL(fast_less_predicate_ps(ls, rs, ns, reverse) == exp, true); \
if (exp != UNDEFINED) { \
bool exp_res = (exp == LESS) ? true : false; \
- BOOST_CHECK_EQUAL(less_predicate(lp, rs, np, reverse), exp_res); \
+ BOOST_CHECK_EQUAL(less_predicate_ps(ls, rs, ns, reverse), exp_res); \
}
-#define CHECK_LESS_PREDICATE_PS(lp, rs, np, reverse, exp) \
- BOOST_CHECK_EQUAL(less_predicate(lp, rs, np, reverse) == exp, true)
+#define CHECK_LESS_PREDICATE_PS(ls, rs, ns, reverse, exp) \
+ BOOST_CHECK_EQUAL(less_predicate_ps(ls, rs, ns, reverse) == exp, true)
-#define CHECK_LESS_PREDICATE_SS(ls, rs, np, exp) \
- BOOST_CHECK_EQUAL(less_predicate(ls, rs, np) == exp, true)
+#define CHECK_LESS_PREDICATE_SS(ls, rs, ns, exp) \
+ BOOST_CHECK_EQUAL(less_predicate_ss(ls, rs, ns) == exp, true)
// This test uses integer values in the range [-2^31, 2^31), to validate
// orientation predicate for the hole integer range input coordinates.
@@ -71,19 +71,19 @@
// Test main point-point predicate.
BOOST_AUTO_TEST_CASE_TEMPLATE(less_predicates_point_point_test1, T, test_types) {
- point_2d<T> point1 = point_2d<T>(static_cast<T>(-5), static_cast<T>(0));
- point_2d<T> point2 = point_2d<T>(static_cast<T>(-8), static_cast<T>(9));
- point_2d<T> point3 = point_2d<T>(static_cast<T>(-2), static_cast<T>(1));
+ site_event<T> point1(static_cast<T>(-5), static_cast<T>(0), 0);
+ site_event<T> point2(static_cast<T>(-8), static_cast<T>(9), 0);
+ site_event<T> point3(static_cast<T>(-2), static_cast<T>(1), 0);
- point_2d<T> site1 = point_2d<T>(static_cast<T>(0), static_cast<T>(5));
+ site_event<T> site1(static_cast<T>(0), static_cast<T>(5), 0);
CHECK_LESS_PREDICATE_PP(point1, point2, site1, false);
CHECK_LESS_PREDICATE_PP(point3, point1, site1, false);
- point_2d<T> site2 = point_2d<T>(static_cast<T>(0), static_cast<T>(4));
+ site_event<T> site2(static_cast<T>(0), static_cast<T>(4), 0);
CHECK_LESS_PREDICATE_PP(point1, point2, site2, false);
CHECK_LESS_PREDICATE_PP(point3, point1, site2, false);
- point_2d<T> site3 = point_2d<T>(static_cast<T>(0), static_cast<T>(6));
+ site_event<T> site3(static_cast<T>(0), static_cast<T>(6), 0);
CHECK_LESS_PREDICATE_PP(point1, point2, site3, true);
CHECK_LESS_PREDICATE_PP(point3, point1, site3, true);
}
@@ -94,9 +94,9 @@
point_2d<T> segm_end = point_2d<T>(static_cast<T>(-4), static_cast<T>(20));
site_event<T> segm_site(segm_start, segm_end, 0);
- point_2d<T> site_p = point_2d<T>(static_cast<T>(-2), static_cast<T>(10));
- point_2d<T> new_p1 = point_2d<T>(static_cast<T>(0), static_cast<T>(11));
- point_2d<T> new_p2 = point_2d<T>(static_cast<T>(0), static_cast<T>(9));
+ site_event<T> site_p(static_cast<T>(-2), static_cast<T>(10), 0);
+ site_event<T> new_p1(static_cast<T>(0), static_cast<T>(11), 1);
+ site_event<T> new_p2(static_cast<T>(0), static_cast<T>(9), 2);
CHECK_FAST_LESS_PREDICATE_PS(site_p, segm_site, new_p1, false, UNDEFINED);
CHECK_FAST_LESS_PREDICATE_PS(site_p, segm_site, new_p2, false, MORE);
@@ -110,21 +110,21 @@
point_2d<T> segm_end = point_2d<T>(static_cast<T>(2), static_cast<T>(-2));
site_event<T> segm_site(segm_start, segm_end, 0);
- point_2d<T> site_p1 = point_2d<T>(static_cast<T>(-2), static_cast<T>(4));
- point_2d<T> new_p1 = point_2d<T>(static_cast<T>(0), static_cast<T>(-1));
+ site_event<T> site_p1(static_cast<T>(-2), static_cast<T>(4), 0);
+ site_event<T> new_p1(static_cast<T>(0), static_cast<T>(-1), 0);
segm_site.inverse();
CHECK_FAST_LESS_PREDICATE_PS(site_p1, segm_site, new_p1, false, MORE);
CHECK_FAST_LESS_PREDICATE_PS(site_p1, segm_site, new_p1, true, MORE);
- point_2d<T> new_p2 = point_2d<T>(static_cast<T>(0), static_cast<T>(1));
+ site_event<T> new_p2(static_cast<T>(0), static_cast<T>(1), 0);
CHECK_FAST_LESS_PREDICATE_PS(site_p1, segm_site, new_p2, false, MORE);
CHECK_FAST_LESS_PREDICATE_PS(site_p1, segm_site, new_p2, true, UNDEFINED);
- point_2d<T> new_p3 = point_2d<T>(static_cast<T>(0), static_cast<T>(4));
+ site_event<T> new_p3(static_cast<T>(0), static_cast<T>(4), 0);
CHECK_FAST_LESS_PREDICATE_PS(site_p1, segm_site, new_p3, false, MORE);
CHECK_FAST_LESS_PREDICATE_PS(site_p1, segm_site, new_p3, true, UNDEFINED);
- point_2d<T> new_p4 = point_2d<T>(static_cast<T>(0), static_cast<T>(5));
+ site_event<T> new_p4(static_cast<T>(0), static_cast<T>(5), 0);
CHECK_FAST_LESS_PREDICATE_PS(site_p1, segm_site, new_p4, false, UNDEFINED);
CHECK_FAST_LESS_PREDICATE_PS(site_p1, segm_site, new_p4, true, LESS);
}
@@ -135,28 +135,28 @@
point_2d<T> segm_end = point_2d<T>(static_cast<T>(2), static_cast<T>(-2));
site_event<T> segm_site(segm_start, segm_end, 0);
- point_2d<T> site_p1 = point_2d<T>(static_cast<T>(-2), static_cast<T>(-4));
- point_2d<T> site_p2 = point_2d<T>(static_cast<int>(-4), static_cast<int>(1));
+ site_event<T> site_p1(static_cast<T>(-2), static_cast<T>(-4), 0);
+ site_event<T> site_p2(static_cast<int>(-4), static_cast<int>(1), 0);
- point_2d<T> new_p1 = point_2d<T>(static_cast<T>(0), static_cast<T>(1));
+ site_event<T> new_p1(static_cast<T>(0), static_cast<T>(1), 0);
CHECK_FAST_LESS_PREDICATE_PS(site_p1, segm_site, new_p1, false, LESS);
CHECK_FAST_LESS_PREDICATE_PS(site_p1, segm_site, new_p1, true, LESS);
CHECK_FAST_LESS_PREDICATE_PS(site_p2, segm_site, new_p1, false, LESS);
CHECK_FAST_LESS_PREDICATE_PS(site_p2, segm_site, new_p1, true, LESS);
- point_2d<T> new_p2 = point_2d<T>(static_cast<T>(0), static_cast<T>(-2));
+ site_event<T> new_p2(static_cast<T>(0), static_cast<T>(-2), 0);
CHECK_FAST_LESS_PREDICATE_PS(site_p1, segm_site, new_p2, false, UNDEFINED);
CHECK_FAST_LESS_PREDICATE_PS(site_p1, segm_site, new_p2, true, LESS);
CHECK_FAST_LESS_PREDICATE_PS(site_p2, segm_site, new_p2, false, UNDEFINED);
CHECK_FAST_LESS_PREDICATE_PS(site_p2, segm_site, new_p2, true, LESS);
- point_2d<T> new_p3 = point_2d<T>(static_cast<T>(0), static_cast<T>(-8));
+ site_event<T> new_p3(static_cast<T>(0), static_cast<T>(-8), 0);
CHECK_FAST_LESS_PREDICATE_PS(site_p1, segm_site, new_p3, false, UNDEFINED);
CHECK_FAST_LESS_PREDICATE_PS(site_p1, segm_site, new_p3, true, LESS);
CHECK_FAST_LESS_PREDICATE_PS(site_p2, segm_site, new_p3, false, UNDEFINED);
CHECK_FAST_LESS_PREDICATE_PS(site_p2, segm_site, new_p3, true, LESS);
- point_2d<T> new_p4 = point_2d<T>(static_cast<T>(0), static_cast<T>(-9));
+ site_event<T> new_p4(static_cast<T>(0), static_cast<T>(-9), 0);
CHECK_FAST_LESS_PREDICATE_PS(site_p1, segm_site, new_p4, false, MORE);
CHECK_FAST_LESS_PREDICATE_PS(site_p1, segm_site, new_p4, true, UNDEFINED);
CHECK_FAST_LESS_PREDICATE_PS(site_p2, segm_site, new_p4, false, MORE);
@@ -171,39 +171,39 @@
site_event<T> segm_site2(segm_start, segm_end, 0);
segm_site2.inverse();
- point_2d<T> site_p1 = point_2d<T>(static_cast<T>(-2), static_cast<T>(4));
- point_2d<T> site_p2 = point_2d<T>(static_cast<T>(-2), static_cast<T>(-4));
- point_2d<T> site_p3 = point_2d<T>(static_cast<int>(-4), static_cast<int>(1));
+ site_event<T> site_p1(static_cast<T>(-2), static_cast<T>(4), 0);
+ site_event<T> site_p2(static_cast<T>(-2), static_cast<T>(-4), 0);
+ site_event<T> site_p3(static_cast<int>(-4), static_cast<int>(1), 0);
- point_2d<T> new_p1 = point_2d<T>(static_cast<T>(0), static_cast<T>(1));
+ site_event<T> new_p1(static_cast<T>(0), static_cast<T>(1), 0);
CHECK_LESS_PREDICATE_PS(site_p1, segm_site2, new_p1, true, false);
- point_2d<T> new_p2 = point_2d<T>(static_cast<T>(0), static_cast<T>(4));
+ site_event<T> new_p2(static_cast<T>(0), static_cast<T>(4), 0);
CHECK_LESS_PREDICATE_PS(site_p1, segm_site2, new_p2, true, true);
- point_2d<T> new_p3 = point_2d<T>(static_cast<T>(0), static_cast<T>(5));
+ site_event<T> new_p3(static_cast<T>(0), static_cast<T>(5), 0);
CHECK_LESS_PREDICATE_PS(site_p1, segm_site2, new_p3, false, false);
- point_2d<T> new_p4 = point_2d<T>(static_cast<T>(0), static_cast<T>(7));
+ site_event<T> new_p4(static_cast<T>(0), static_cast<T>(7), 0);
CHECK_LESS_PREDICATE_PS(site_p1, segm_site2, new_p4, false, true);
- point_2d<T> new_p5 = point_2d<T>(static_cast<T>(0), static_cast<T>(-2));
+ site_event<T> new_p5(static_cast<T>(0), static_cast<T>(-2), 0);
CHECK_LESS_PREDICATE_PS(site_p2, segm_site1, new_p5, false, false);
CHECK_LESS_PREDICATE_PS(site_p3, segm_site1, new_p5, false, false);
- point_2d<T> new_p6 = point_2d<T>(static_cast<T>(0), static_cast<T>(-8));
+ site_event<T> new_p6(static_cast<T>(0), static_cast<T>(-8), 0);
CHECK_LESS_PREDICATE_PS(site_p2, segm_site1, new_p6, false, false);
CHECK_LESS_PREDICATE_PS(site_p3, segm_site1, new_p6, false, false);
- point_2d<T> new_p7 = point_2d<T>(static_cast<T>(0), static_cast<T>(-9));
+ site_event<T> new_p7(static_cast<T>(0), static_cast<T>(-9), 0);
CHECK_LESS_PREDICATE_PS(site_p2, segm_site1, new_p7, true, true);
CHECK_LESS_PREDICATE_PS(site_p3, segm_site1, new_p7, true, true);
- point_2d<T> new_p8 = point_2d<T>(static_cast<T>(0), static_cast<T>(-18));
+ site_event<T> new_p8(static_cast<T>(0), static_cast<T>(-18), 0);
CHECK_LESS_PREDICATE_PS(site_p2, segm_site1, new_p8, true, false);
CHECK_LESS_PREDICATE_PS(site_p3, segm_site1, new_p8, true, false);
- point_2d<T> new_p9 = point_2d<T>(static_cast<T>(0), static_cast<T>(-1));
+ site_event<T> new_p9(static_cast<T>(0), static_cast<T>(-1), 0);
CHECK_LESS_PREDICATE_PS(site_p2, segm_site1, new_p9, false, true);
CHECK_LESS_PREDICATE_PS(site_p3, segm_site1, new_p9, false, true);
}
@@ -217,9 +217,9 @@
segm_site1_2.inverse();
// New sites.
- point_2d<T> new_site1 = point_2d<T>(static_cast<T>(2), static_cast<T>(7));
- point_2d<T> new_site2 = point_2d<T>(static_cast<T>(1), static_cast<T>(5));
- point_2d<T> new_site3 = point_2d<T>(static_cast<T>(-1), static_cast<T>(5));
+ site_event<T> new_site1(static_cast<T>(2), static_cast<T>(7), 0);
+ site_event<T> new_site2(static_cast<T>(1), static_cast<T>(5), 0);
+ site_event<T> new_site3(static_cast<T>(-1), static_cast<T>(5), 0);
CHECK_LESS_PREDICATE_SS(segm_site1_1, segm_site1_2, new_site1, false);
CHECK_LESS_PREDICATE_SS(segm_site1_1, segm_site1_2, new_site2, false);
@@ -236,10 +236,10 @@
segm_site1_2.inverse();
// New sites.
- point_2d<T> new_site1 = point_2d<T>(static_cast<T>(0), static_cast<T>(2));
- point_2d<T> new_site2 = point_2d<T>(static_cast<T>(0), static_cast<T>(5));
- point_2d<T> new_site3 = point_2d<T>(static_cast<T>(0), static_cast<T>(6));
- point_2d<T> new_site4 = point_2d<T>(static_cast<T>(0), static_cast<T>(8));
+ site_event<T> new_site1(static_cast<T>(0), static_cast<T>(2), 0);
+ site_event<T> new_site2(static_cast<T>(0), static_cast<T>(5), 0);
+ site_event<T> new_site3(static_cast<T>(0), static_cast<T>(6), 0);
+ site_event<T> new_site4(static_cast<T>(0), static_cast<T>(8), 0);
// Common end points.
point_2d<T> segm_start2 = point_2d<T>(static_cast<T>(-5), static_cast<T>(5));
@@ -273,6 +273,6 @@
site_event_type segm_site1(segm_start1, segm_end, 0);
segm_site1.inverse();
site_event_type segm_site2(segm_start2, segm_end, 1);
- point_2d<T> point(-4, 2);
+ site_event<T> point(-4, 2, 0);
CHECK_LESS_PREDICATE_SS(segm_site1, segm_site2, point, false);
}
Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk