Subject: [Boost-commit] svn:boost r74588 - in sandbox/SOC/2010/sweepline: boost/sweepline boost/sweepline/detail libs/sweepline/test
From: sydorchuk.andriy_at_[hidden]
Date: 2011-09-27 07:23:17
Author: asydorchuk
Date: 2011-09-27 07:23:16 EDT (Tue, 27 Sep 2011)
New Revision: 74588
URL: http://svn.boost.org/trac/boost/changeset/74588
Log:
Moved beach line insertion predicate to the voronoi_calc_kernel.
Auto fixed find_distance_to_segment_arc bug on linux, gcc-4.4.3 (this function returned different results for the same input set, it was impossible to recognize a bug during debugging or saving variables states in release mode, because everything started to work fine).
Updated tests.
Text files modified:
sandbox/SOC/2010/sweepline/boost/sweepline/detail/voronoi_calc_kernel.hpp | 310 +++++++++++++++++++++++++++++++++++++--
sandbox/SOC/2010/sweepline/boost/sweepline/detail/voronoi_formation.hpp | 282 ------------------------------------
sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_builder.hpp | 23 +-
sandbox/SOC/2010/sweepline/libs/sweepline/test/event_queue_test.cpp | 6
sandbox/SOC/2010/sweepline/libs/sweepline/test/event_types_test.cpp | 8
sandbox/SOC/2010/sweepline/libs/sweepline/test/node_comparer_test.cpp | 2
sandbox/SOC/2010/sweepline/libs/sweepline/test/predicates_test.cpp | 188 +++++++++++------------
7 files changed, 398 insertions(+), 421 deletions(-)
Modified: sandbox/SOC/2010/sweepline/boost/sweepline/detail/voronoi_calc_kernel.hpp
==============================================================================
--- sandbox/SOC/2010/sweepline/boost/sweepline/detail/voronoi_calc_kernel.hpp (original)
+++ sandbox/SOC/2010/sweepline/boost/sweepline/detail/voronoi_calc_kernel.hpp 2011-09-27 07:23:16 EDT (Tue, 27 Sep 2011)
@@ -17,22 +17,13 @@
namespace detail {
template <typename T>
-struct voronoi_calc_kernel_traits;
-
-template <>
-struct voronoi_calc_kernel_traits<int> {
- typedef double fpt_type;
- typedef polygon_ulong_long_type ulong_long_type;
-};
-
-template <typename T>
class voronoi_calc_kernel;
template <>
class voronoi_calc_kernel<int> {
public:
- typedef voronoi_calc_kernel_traits<int>::fpt_type fpt_type;
- typedef voronoi_calc_kernel_traits<int>::ulong_long_type ulong_long_type;
+ typedef double fpt_type;
+ typedef polygon_ulong_long_type ulong_long_type;
enum kOrientation {
RIGHT = -1,
@@ -116,9 +107,11 @@
point2.y() - point3.y()));
}
+ template <typename Site>
struct site_comparison_predicate {
- template <typename Site>
- bool operator()(const Site &lhs, const Site &rhs) const {
+ typedef Site site_type;
+
+ bool operator()(const site_type &lhs, const site_type &rhs) const {
if (lhs.x0() != rhs.x0()) return lhs.x0() < rhs.x0();
if (!lhs.is_segment()) {
if (!rhs.is_segment()) return lhs.y0() < rhs.y0();
@@ -136,19 +129,23 @@
}
};
+ template <typename Site>
struct site_equality_predicate {
- template <typename Site>
- bool operator()(const Site &lhs, const Site &rhs) const {
+ typedef Site site_type;
+
+ bool operator()(const site_type &lhs, const site_type &rhs) const {
return lhs.point0() == rhs.point0() &&
lhs.point1() == rhs.point1();
}
};
+ template <typename Circle>
struct circle_comparison_predicate {
+ typedef Circle circle_type;
+
static const unsigned int ULPS = 128;
- template <typename Circle>
- bool operator()(const Circle &lhs, const Circle &rhs) const {
+ bool operator()(const circle_type &lhs, const circle_type &rhs) const {
if (almost_equal(lhs.lower_x(), rhs.lower_x(), ULPS)) {
if (almost_equal(lhs.lower_y(), rhs.lower_y(), ULPS)) {
return false;
@@ -159,11 +156,14 @@
}
};
+ template <typename Site, typename Circle>
struct event_comparison_predicate {
+ typedef Site site_type;
+ typedef Circle circle_type;
+
static const unsigned int ULPS = 64;
- template <typename Site, typename Circle>
- bool operator()(const Site &lhs, const Circle &rhs) const {
+ bool operator()(const site_type &lhs, const circle_type &rhs) const {
if (almost_equal(lhs.x(), rhs.lower_x(), ULPS)) {
if (almost_equal(lhs.y(), rhs.lower_y(), ULPS)) return false;
return lhs.y() < rhs.lower_y();
@@ -172,10 +172,278 @@
}
};
+ template <typename Site>
+ class distance_predicate {
+ public:
+ typedef Site site_type;
+
+ bool operator()(const site_type& left_site,
+ const site_type& right_site,
+ const site_type& new_site) const {
+ if (!left_site.is_segment()) {
+ if (!right_site.is_segment()) {
+ return pp(left_site, right_site, new_site);
+ } else {
+ return ps(left_site, right_site, new_site, false);
+ }
+ } else {
+ if (!right_site.is_segment()) {
+ return ps(right_site, left_site, new_site, true);
+ } else {
+ return ss(left_site, right_site, new_site);
+ }
+ }
+ }
+
+ private:
+ typedef typename Site::point_type point_type;
+
+ // Find the x-coordinate (relative to the sweepline position) of the point
+ // of the intersection of the horizontal line going through the new site
+ // with the arc corresponding to the point site.
+ // The relative error is atmost 3EPS.
+ fpt_type find_distance_to_point_arc(const site_type &site,
+ const point_type &point) const {
+ fpt_type dx = static_cast<fpt_type>(site.x()) -
+ static_cast<fpt_type>(point.x());
+ fpt_type dy = static_cast<fpt_type>(site.y()) -
+ static_cast<fpt_type>(point.y());
+ return (dx * dx + dy * dy) / (static_cast<fpt_type>(2.0) * dx);
+ }
+
+ // Find the x-coordinate (relative to the sweepline position) of the point
+ // of the intersection of the horizontal line going through the new site
+ // with the arc corresponding to the segment site.
+ // The relative error is atmost 8EPS.
+ fpt_type find_distance_to_segment_arc(const site_type &site,
+ const point_type &point) const {
+ if (site.is_vertical()) {
+ return (static_cast<fpt_type>(site.x()) - static_cast<fpt_type>(point.x())) *
+ static_cast<fpt_type>(0.5);
+ } else {
+ const point_type &segment0 = site.point0(true);
+ const point_type &segment1 = site.point1(true);
+ fpt_type a1 = static_cast<fpt_type>(segment1.x()) -
+ static_cast<fpt_type>(segment0.x());
+ fpt_type b1 = static_cast<fpt_type>(segment1.y()) -
+ static_cast<fpt_type>(segment0.y());
+ fpt_type a3 = static_cast<fpt_type>(point.x()) -
+ static_cast<fpt_type>(segment0.x());
+ fpt_type b3 = static_cast<fpt_type>(point.y()) -
+ static_cast<fpt_type>(segment0.y());
+ fpt_type k = std::sqrt(a1 * a1 + b1 * b1);
+ // Avoid substraction while computing k.
+ if (b1 >= static_cast<fpt_type>(0.0)) k = static_cast<fpt_type>(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.
+ return robust_cross_product(a1, b1, a3, b3) * k;
+ }
+ }
+
+ // 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].
+ bool pp(const site_type &left_site,
+ const site_type &right_site,
+ const site_type &new_site) const {
+ // 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.
+ 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;
+ } else if (left_point.x() < right_point.x()) {
+ if (new_point.y() >= right_point.y())
+ return true;
+ } else {
+ // If x-coordinates of the sites are equal, we may produce the
+ // result without any further computations.
+ return static_cast<fpt_type>(left_point.y()) +
+ static_cast<fpt_type>(right_point.y()) <
+ static_cast<fpt_type>(2.0) *
+ static_cast<fpt_type>(new_point.y());
+ }
+
+ fpt_type dist1 = find_distance_to_point_arc(left_site, new_point);
+ fpt_type dist2 = find_distance_to_point_arc(right_site, new_point);
+
+ // The undefined ulp range is equal to 3EPS + 3EPS <= 6ULP.
+ return dist1 < dist2;
+ }
+
+ kPredicateResult fast_ps(const site_type &left_site, const site_type &right_site,
+ const site_type &new_site, bool reverse_order) const {
+ 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 (get_orientation(segment_start, segment_end, new_point) != RIGHT) {
+ return (!right_site.is_inverse()) ? LESS : MORE;
+ }
+
+ fpt_type dif_x = static_cast<fpt_type>(new_point.x()) -
+ static_cast<fpt_type>(site_point.x());
+ fpt_type dif_y = static_cast<fpt_type>(new_point.y()) -
+ static_cast<fpt_type>(site_point.y());
+ fpt_type a = static_cast<fpt_type>(segment_end.x()) -
+ static_cast<fpt_type>(segment_start.x());
+ fpt_type b = static_cast<fpt_type>(segment_end.y()) -
+ static_cast<fpt_type>(segment_start.y());
+
+ 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)
+ return LESS;
+ return UNDEFINED;
+ } else {
+ kOrientation orientation = get_orientation(a, b, dif_x, dif_y);
+ if (orientation == LEFT) {
+ if (!right_site.is_inverse())
+ return reverse_order ? LESS : UNDEFINED;
+ return reverse_order ? UNDEFINED : MORE;
+ }
+ }
+
+ fpt_type fast_left_expr = a * (dif_y + dif_x) * (dif_y - dif_x);
+ fpt_type fast_right_expr = (2.0 * b) * dif_x * dif_y;
+ if (!(almost_equal(fast_left_expr, fast_right_expr, 4))) {
+ if ((fast_left_expr > fast_right_expr) ^ reverse_order)
+ return reverse_order ? LESS : MORE;
+ return UNDEFINED;
+ }
+ return UNDEFINED;
+ }
+
+ // 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.
+ // reverse_order flag defines arrangement of the sites. If it's false
+ // the order is (point, segment), else - (segment, point).
+ bool ps(const site_type &left_site, const site_type &right_site,
+ const site_type &new_site, bool reverse_order) const {
+ kPredicateResult fast_res = fast_ps(
+ left_site, right_site, new_site, reverse_order);
+ if (fast_res != UNDEFINED) {
+ return (fast_res == LESS);
+ }
+
+ fpt_type dist1 = find_distance_to_point_arc(left_site, new_site.point0());
+ fpt_type 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);
+ }
+
+ // 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.
+ bool ss(const site_type &left_site,
+ const site_type &right_site,
+ const site_type &new_site) const {
+ // Handle temporary segment sites.
+ if (left_site.index() == right_site.index()) {
+ return get_orientation(left_site.point0(),
+ left_site.point1(),
+ new_site.point0()) == LEFT;
+ }
+
+ // 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.
+ fpt_type dist1 = find_distance_to_segment_arc(left_site, new_site.point0());
+ fpt_type dist2 = find_distance_to_segment_arc(right_site, new_site.point0());
+
+ // The undefined ulp range is equal to 8EPS + 8EPS <= 16ULP.
+ return dist1 < dist2;
+ }
+ };
+
template <typename Node>
- struct node_comparison_predicate {
- bool operator()(const Node &lhs, const Node &rhs) const {
+ class node_comparison_predicate {
+ public:
+ typedef Node node_type;
+ typedef typename Node::coordinate_type coordinate_type;
+ typedef typename Node::site_event_type site_type;
+
+ // Compares nodes in the balanced binary search tree. Nodes are
+ // compared based on the y coordinates of the arcs intersection points.
+ // Nodes with less y coordinate of the intersection point go first.
+ // 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 node_type &node1,
+ const node_type &node2) const {
+ // Get x coordinate of the righmost site from both nodes.
+ const site_type &site1 = get_comparison_site(node1);
+ const site_type &site2 = get_comparison_site(node2);
+
+ if (site1.x() < site2.x()) {
+ // The second node contains a new site.
+ return predicate_(node1.left_site(), node1.right_site(), site2);
+ } else if (site1.x() > site2.x()) {
+ // The first node contains a new site.
+ return !predicate_(node2.left_site(), node2.right_site(), site1);
+ } else {
+ // This checks were evaluated experimentally.
+ if (site1.index() == site2.index()) {
+ // Both nodes are new (inserted during the same site event processing).
+ return get_comparison_y(node1) < get_comparison_y(node2);
+ } else if (site1.index() < site2.index()) {
+ 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 (!site1.is_segment()) ? (y1.second < 0) : false;
+ } else {
+ 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 (!site2.is_segment()) ? (y2.second > 0) : true;
+ }
+ }
+ }
+
+ private:
+ typedef distance_predicate<site_type> distance_predicate_type;
+
+ // Get the newer site.
+ const site_type &get_comparison_site(const node_type &node) const {
+ if (node.left_site().index() > node.right_site().index()) {
+ return node.left_site();
+ }
+ return node.right_site();
+ }
+
+ // Get comparison pair: y coordinate and direction of the newer site.
+ std::pair<coordinate_type, int> get_comparison_y(const 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);
}
+
+ distance_predicate_type predicate_;
};
private:
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-27 07:23:16 EDT (Tue, 27 Sep 2011)
@@ -284,9 +284,6 @@
class circle_event {
public:
typedef T coordinate_type;
- typedef point_2d<T> point_type;
- typedef site_event<T> site_event_type;
- typedef circle_event<T> circle_event_type;
circle_event() : is_active_(true) {}
@@ -541,176 +538,6 @@
point2.y() - point3.y()));
}
- // Find the x-coordinate (relative to the sweepline position) of the point
- // of the intersection of the horizontal line going through the new site
- // 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 site_event<T> &point_site,
- const point_2d<T> &new_point) {
- 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);
- }
-
- // Find the x-coordinate (relative to the sweepline position) of the point
- // of the intersection of the horizontal line going through the new site
- // with the arc corresponding to the segment site.
- // The relative error is atmost 8EPS.
- template <typename T>
- static double find_distance_to_segment_arc(const site_event<T> &segment,
- const point_2d<T> &new_point) {
- if (segment.is_vertical()) {
- return (segment.point0().x() - new_point.x()) * 0.5;
- } else {
- 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 (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.
- return robust_cross_product(a1, b1, a3, b3) * k;
- }
- }
-
- // 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 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;
- } else if (left_point.x() < right_point.x()) {
- if (new_point.y() >= right_point.y())
- return true;
- } else {
- // If x-coordinates of the sites are equal, we may produce the
- // result without any further computations.
- return left_point.y() + right_point.y() < 2.0 * new_point.y();
- }
-
- 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 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;
- }
-
- 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 (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)
- return LESS;
- return UNDEFINED;
- } else {
- kOrientation orientation = orientation_test(a, b, dif_x, dif_y);
- if (orientation == LEFT_ORIENTATION) {
- if (!right_site.is_inverse())
- return reverse_order ? LESS : UNDEFINED;
- return reverse_order ? UNDEFINED : MORE;
- }
- }
-
- double fast_left_expr = a * (dif_y + dif_x) * (dif_y - dif_x);
- double fast_right_expr = (2.0 * b) * dif_x * dif_y;
- if (!(almost_equal(fast_left_expr, fast_right_expr, 4))) {
- if ((fast_left_expr > fast_right_expr) ^ reverse_order)
- return reverse_order ? LESS : MORE;
- return UNDEFINED;
- }
- return UNDEFINED;
- }
-
- // 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.
- // reverse_order flag defines arrangement of the sites. If it's false
- // the order is (point, segment), else - (segment, point).
- 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(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);
- }
-
- // 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 Site>
- static bool less_predicate_ss(const Site &left_site,
- const Site &right_site,
- const Site &new_site) {
- // Handle temporary segment sites.
- 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_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;
- }
-
///////////////////////////////////////////////////////////////////////////
// CIRCLE EVENTS CREATION /////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////
@@ -1548,115 +1375,6 @@
void *edge_;
};
- // Beach line comparison functor.
- template <typename BeachLineNode>
- 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.
- // Nodes with less y coordinate of the intersection point go first.
- // 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 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 = 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 less(node1, get_comparison_site(node2));
- } else if (node1_x > node2_x) {
- // The first node contains a new site.
- return !less(node2, get_comparison_site(node1));
- } else {
- // This checks were evaluated experimentally.
- 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 = 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);
- }
- }
- }
- };
-
} // detail
} // sweepline
} // boost
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-27 07:23:16 EDT (Tue, 27 Sep 2011)
@@ -181,21 +181,24 @@
private:
typedef voronoi_builder_traits<int>::calc_kernel_type calc_kernel_type;
-
+
typedef detail::point_2d<coordinate_type> point_type;
typedef detail::site_event<coordinate_type> site_event_type;
- typedef calc_kernel_type::site_comparison_predicate site_comparison_predicate;
- typedef calc_kernel_type::site_equality_predicate site_equality_predicate;
+ typedef calc_kernel_type::site_comparison_predicate<site_event_type>
+ site_comparison_predicate;
+ typedef calc_kernel_type::site_equality_predicate<site_event_type>
+ site_equality_predicate;
typedef typename std::vector<site_event_type>::const_iterator
site_event_iterator_type;
typedef detail::circle_event<coordinate_type> circle_event_type;
- typedef calc_kernel_type::circle_comparison_predicate circle_comparison_predicate;
- typedef calc_kernel_type::event_comparison_predicate event_comparison_predicate;
+ typedef calc_kernel_type::circle_comparison_predicate<circle_event_type>
+ circle_comparison_predicate;
+ typedef calc_kernel_type::event_comparison_predicate<site_event_type, circle_event_type>
+ event_comparison_predicate;
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 calc_kernel_type::node_comparison_predicate<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 {
@@ -203,8 +206,8 @@
return predicate(rhs.first, lhs.first);
}
circle_comparison_predicate predicate;
- } event_comparison;
- typedef detail::ordered_queue<event_type, event_comparison>
+ } event_comparison_type;
+ typedef detail::ordered_queue<event_type, event_comparison_type>
circle_event_queue_type;
typedef typename output_type::voronoi_edge_type edge_type;
typedef std::pair<point_type, beach_line_iterator> end_point_type;
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-27 07:23:16 EDT (Tue, 27 Sep 2011)
@@ -36,12 +36,12 @@
}
BOOST_AUTO_TEST_CASE_TEMPLATE(event_queue_test2, T, test_types) {
- ordered_queue<T, std::greater<T> > event_q;
+ ordered_queue< std::pair<T, T>, std::greater< std::pair<T, T> > > event_q;
for (int i = 0; i <= 10; i++) {
- event_q.push(static_cast<T>(i)) *= 2;
+ event_q.push(std::make_pair(i, i)).second *= 2;
}
for (int i = 0; i <= 10; i++) {
- BOOST_CHECK_EQUAL(event_q.top(), static_cast<T>(2 * i));
+ BOOST_CHECK_EQUAL(event_q.top().second, 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-27 07:23:16 EDT (Tue, 27 Sep 2011)
@@ -25,10 +25,10 @@
BOOST_CHECK_EQUAL((A)==(B), (ARR)[4]); \
BOOST_CHECK_EQUAL((A)!=(B), (ARR)[5])
-voronoi_calc_kernel<int>::site_comparison_predicate site_comparison;
-voronoi_calc_kernel<int>::site_equality_predicate site_equality;
-voronoi_calc_kernel<int>::circle_comparison_predicate circle_comparison;
-voronoi_calc_kernel<int>::event_comparison_predicate event_comparison;
+voronoi_calc_kernel<int>::site_comparison_predicate<site_event<double> > site_comparison;
+voronoi_calc_kernel<int>::site_equality_predicate<site_event<double> > site_equality;
+voronoi_calc_kernel<int>::circle_comparison_predicate<circle_event<double> > circle_comparison;
+voronoi_calc_kernel<int>::event_comparison_predicate< site_event<double>, circle_event<double> > event_comparison;
#define SITE_COMPARISON_CHECK(A, B, ARR) \
BOOST_CHECK_EQUAL(site_comparison(A, B), (ARR)[0]); \
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-27 07:23:16 EDT (Tue, 27 Sep 2011)
@@ -20,7 +20,7 @@
#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 voronoi_calc_kernel<int>::node_comparison_predicate<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
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-27 07:23:16 EDT (Tue, 27 Sep 2011)
@@ -18,23 +18,11 @@
typedef boost::mpl::list<double> test_types;
#define CHECK_ORIENTATION_EQUAL(p1, p2, p3, exp) \
- BOOST_CHECK_EQUAL(orientation_test(p1, p2, p3) == exp, true)
+ BOOST_CHECK_EQUAL(voronoi_calc_kernel<int>::get_orientation(p1, p2, p3) == 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(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_ps(ls, rs, ns, reverse), exp_res); \
- }
-
-#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, ns, exp) \
- BOOST_CHECK_EQUAL(less_predicate_ss(ls, rs, ns) == exp, true)
+voronoi_calc_kernel<int>::distance_predicate<site_event<double> > distance_predicate;
+#define CHECK_DISTANCE_PREDICATE(ls, rs, ns, exp) \
+ BOOST_CHECK_EQUAL(distance_predicate(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.
@@ -47,26 +35,26 @@
point_2d<T> point4 = point_2d<T>(min_int, max_int);
point_2d<T> point5 = point_2d<T>(max_int - 1, max_int);
- CHECK_ORIENTATION_EQUAL(point1, point2, point3, COLLINEAR);
- CHECK_ORIENTATION_EQUAL(point1, point3, point2, COLLINEAR);
- CHECK_ORIENTATION_EQUAL(point2, point3, point1, COLLINEAR);
- CHECK_ORIENTATION_EQUAL(point2, point1, point3, COLLINEAR);
- CHECK_ORIENTATION_EQUAL(point3, point1, point2, COLLINEAR);
- CHECK_ORIENTATION_EQUAL(point3, point2, point1, COLLINEAR);
-
- CHECK_ORIENTATION_EQUAL(point1, point4, point3, RIGHT_ORIENTATION);
- CHECK_ORIENTATION_EQUAL(point1, point3, point4, LEFT_ORIENTATION);
- CHECK_ORIENTATION_EQUAL(point4, point1, point3, LEFT_ORIENTATION);
- CHECK_ORIENTATION_EQUAL(point4, point3, point1, RIGHT_ORIENTATION);
- CHECK_ORIENTATION_EQUAL(point3, point4, point1, LEFT_ORIENTATION);
- CHECK_ORIENTATION_EQUAL(point3, point1, point4, RIGHT_ORIENTATION);
-
- CHECK_ORIENTATION_EQUAL(point1, point5, point3, RIGHT_ORIENTATION);
- CHECK_ORIENTATION_EQUAL(point1, point3, point5, LEFT_ORIENTATION);
- CHECK_ORIENTATION_EQUAL(point5, point1, point3, LEFT_ORIENTATION);
- CHECK_ORIENTATION_EQUAL(point5, point3, point1, RIGHT_ORIENTATION);
- CHECK_ORIENTATION_EQUAL(point3, point5, point1, LEFT_ORIENTATION);
- CHECK_ORIENTATION_EQUAL(point3, point1, point5, RIGHT_ORIENTATION);
+ CHECK_ORIENTATION_EQUAL(point1, point2, point3, voronoi_calc_kernel<int>::COLLINEAR);
+ CHECK_ORIENTATION_EQUAL(point1, point3, point2, voronoi_calc_kernel<int>::COLLINEAR);
+ CHECK_ORIENTATION_EQUAL(point2, point3, point1, voronoi_calc_kernel<int>::COLLINEAR);
+ CHECK_ORIENTATION_EQUAL(point2, point1, point3, voronoi_calc_kernel<int>::COLLINEAR);
+ CHECK_ORIENTATION_EQUAL(point3, point1, point2, voronoi_calc_kernel<int>::COLLINEAR);
+ CHECK_ORIENTATION_EQUAL(point3, point2, point1, voronoi_calc_kernel<int>::COLLINEAR);
+
+ CHECK_ORIENTATION_EQUAL(point1, point4, point3, voronoi_calc_kernel<int>::RIGHT);
+ CHECK_ORIENTATION_EQUAL(point1, point3, point4, voronoi_calc_kernel<int>::LEFT);
+ CHECK_ORIENTATION_EQUAL(point4, point1, point3, voronoi_calc_kernel<int>::LEFT);
+ CHECK_ORIENTATION_EQUAL(point4, point3, point1, voronoi_calc_kernel<int>::RIGHT);
+ CHECK_ORIENTATION_EQUAL(point3, point4, point1, voronoi_calc_kernel<int>::LEFT);
+ CHECK_ORIENTATION_EQUAL(point3, point1, point4, voronoi_calc_kernel<int>::RIGHT);
+
+ CHECK_ORIENTATION_EQUAL(point1, point5, point3, voronoi_calc_kernel<int>::RIGHT);
+ CHECK_ORIENTATION_EQUAL(point1, point3, point5, voronoi_calc_kernel<int>::LEFT);
+ CHECK_ORIENTATION_EQUAL(point5, point1, point3, voronoi_calc_kernel<int>::LEFT);
+ CHECK_ORIENTATION_EQUAL(point5, point3, point1, voronoi_calc_kernel<int>::RIGHT);
+ CHECK_ORIENTATION_EQUAL(point3, point5, point1, voronoi_calc_kernel<int>::LEFT);
+ CHECK_ORIENTATION_EQUAL(point3, point1, point5, voronoi_calc_kernel<int>::RIGHT);
}
// Test main point-point predicate.
@@ -76,16 +64,16 @@
site_event<T> point3(static_cast<T>(-2), static_cast<T>(1), 0);
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);
+ CHECK_DISTANCE_PREDICATE(point1, point2, site1, false);
+ CHECK_DISTANCE_PREDICATE(point3, point1, site1, false);
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);
+ CHECK_DISTANCE_PREDICATE(point1, point2, site2, false);
+ CHECK_DISTANCE_PREDICATE(point3, point1, site2, false);
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);
+ CHECK_DISTANCE_PREDICATE(point1, point2, site3, true);
+ CHECK_DISTANCE_PREDICATE(point3, point1, site3, true);
}
// Vertical segment case.
@@ -98,10 +86,10 @@
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);
- CHECK_FAST_LESS_PREDICATE_PS(site_p, segm_site, new_p1, true, LESS);
- CHECK_FAST_LESS_PREDICATE_PS(site_p, segm_site, new_p2, true, UNDEFINED);
+ CHECK_DISTANCE_PREDICATE(site_p, segm_site, new_p1, false);
+ CHECK_DISTANCE_PREDICATE(site_p, segm_site, new_p2, false);
+ CHECK_DISTANCE_PREDICATE(segm_site, site_p, new_p1, true);
+ CHECK_DISTANCE_PREDICATE(segm_site, site_p, new_p2, true);
}
// Not vertical segment case. Site is to the left of the segment vector.
@@ -113,20 +101,20 @@
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);
+ CHECK_DISTANCE_PREDICATE(site_p1, segm_site, new_p1, false);
+ CHECK_DISTANCE_PREDICATE(segm_site, site_p1, new_p1, false);
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);
+ CHECK_DISTANCE_PREDICATE(site_p1, segm_site, new_p2, false);
+ CHECK_DISTANCE_PREDICATE(segm_site, site_p1, new_p2, false);
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);
+ CHECK_DISTANCE_PREDICATE(site_p1, segm_site, new_p3, false);
+ CHECK_DISTANCE_PREDICATE(segm_site, site_p1, new_p3, true);
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);
+ CHECK_DISTANCE_PREDICATE(site_p1, segm_site, new_p4, false);
+ CHECK_DISTANCE_PREDICATE(segm_site, site_p1, new_p4, true);
}
// Not vertical segment case. Site is to the right of the segment vector.
@@ -139,28 +127,28 @@
site_event<T> site_p2(static_cast<int>(-4), static_cast<int>(1), 0);
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);
+ CHECK_DISTANCE_PREDICATE(site_p1, segm_site, new_p1, true);
+ CHECK_DISTANCE_PREDICATE(segm_site, site_p1, new_p1, true);
+ CHECK_DISTANCE_PREDICATE(site_p2, segm_site, new_p1, true);
+ CHECK_DISTANCE_PREDICATE(segm_site, site_p2, new_p1, true);
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);
+ CHECK_DISTANCE_PREDICATE(site_p1, segm_site, new_p2, false);
+ CHECK_DISTANCE_PREDICATE(segm_site, site_p1, new_p2, true);
+ CHECK_DISTANCE_PREDICATE(site_p2, segm_site, new_p2, false);
+ CHECK_DISTANCE_PREDICATE(segm_site, site_p2, new_p2, true);
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);
+ CHECK_DISTANCE_PREDICATE(site_p1, segm_site, new_p3, false);
+ CHECK_DISTANCE_PREDICATE(segm_site, site_p1, new_p3, true);
+ CHECK_DISTANCE_PREDICATE(site_p2, segm_site, new_p3, false);
+ CHECK_DISTANCE_PREDICATE(segm_site, site_p2, new_p3, true);
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);
- CHECK_FAST_LESS_PREDICATE_PS(site_p2, segm_site, new_p4, true, UNDEFINED);
+ CHECK_DISTANCE_PREDICATE(site_p1, segm_site, new_p4, false);
+ CHECK_DISTANCE_PREDICATE(segm_site, site_p1, new_p4, true);
+ CHECK_DISTANCE_PREDICATE(site_p2, segm_site, new_p4, false);
+ CHECK_DISTANCE_PREDICATE(segm_site, site_p2, new_p4, true);
}
// Test main point-segment predicate.
@@ -176,36 +164,36 @@
site_event<T> site_p3(static_cast<int>(-4), static_cast<int>(1), 0);
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);
+ CHECK_DISTANCE_PREDICATE(site_p1, segm_site2, new_p1, false);
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);
+ CHECK_DISTANCE_PREDICATE(site_p1, segm_site2, new_p2, false);
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);
+ CHECK_DISTANCE_PREDICATE(site_p1, segm_site2, new_p3, false);
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);
+ CHECK_DISTANCE_PREDICATE(site_p1, segm_site2, new_p4, true);
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);
+ CHECK_DISTANCE_PREDICATE(site_p2, segm_site1, new_p5, false);
+ CHECK_DISTANCE_PREDICATE(site_p3, segm_site1, new_p5, false);
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);
+ CHECK_DISTANCE_PREDICATE(site_p2, segm_site1, new_p6, false);
+ CHECK_DISTANCE_PREDICATE(site_p3, segm_site1, new_p6, false);
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);
+ CHECK_DISTANCE_PREDICATE(site_p2, segm_site1, new_p7, false);
+ CHECK_DISTANCE_PREDICATE(site_p3, segm_site1, new_p7, false);
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);
+ CHECK_DISTANCE_PREDICATE(site_p2, segm_site1, new_p8, false);
+ CHECK_DISTANCE_PREDICATE(site_p3, segm_site1, new_p8, false);
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);
+ CHECK_DISTANCE_PREDICATE(site_p2, segm_site1, new_p9, true);
+ CHECK_DISTANCE_PREDICATE(site_p3, segm_site1, new_p9, true);
}
// Test main segment-segment predicate.
@@ -221,9 +209,9 @@
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);
- CHECK_LESS_PREDICATE_SS(segm_site1_1, segm_site1_2, new_site3, true);
+ CHECK_DISTANCE_PREDICATE(segm_site1_1, segm_site1_2, new_site1, false);
+ CHECK_DISTANCE_PREDICATE(segm_site1_1, segm_site1_2, new_site2, false);
+ CHECK_DISTANCE_PREDICATE(segm_site1_1, segm_site1_2, new_site3, true);
}
BOOST_AUTO_TEST_CASE_TEMPLATE(less_predicate_segment_segment_test2, T, test_types) {
@@ -245,24 +233,24 @@
point_2d<T> segm_start2 = point_2d<T>(static_cast<T>(-5), static_cast<T>(5));
point_2d<T> segm_end2 = point_2d<T>(static_cast<T>(0), static_cast<T>(6));
site_event_type segm_site2(segm_start2, segm_end2, 1);
- CHECK_LESS_PREDICATE_SS(segm_site1_2, segm_site2, new_site1, false);
- CHECK_LESS_PREDICATE_SS(segm_site1_2, segm_site2, new_site2, true);
- CHECK_LESS_PREDICATE_SS(segm_site1_2, segm_site2, new_site3, true);
- CHECK_LESS_PREDICATE_SS(segm_site1_2, segm_site2, new_site4, true);
+ CHECK_DISTANCE_PREDICATE(segm_site1_2, segm_site2, new_site1, false);
+ CHECK_DISTANCE_PREDICATE(segm_site1_2, segm_site2, new_site2, true);
+ CHECK_DISTANCE_PREDICATE(segm_site1_2, segm_site2, new_site3, true);
+ CHECK_DISTANCE_PREDICATE(segm_site1_2, segm_site2, new_site4, true);
// No common end points.
point_2d<T> segm_start3 = point_2d<T>(static_cast<T>(-2), static_cast<T>(4));
point_2d<T> segm_end3 = point_2d<T>(static_cast<T>(0), static_cast<T>(4));
site_event_type segm_site3(segm_start3, segm_end3, 2);
- CHECK_LESS_PREDICATE_SS(segm_site1_2, segm_site3, new_site1, false);
- CHECK_LESS_PREDICATE_SS(segm_site1_2, segm_site3, new_site2, true);
- CHECK_LESS_PREDICATE_SS(segm_site1_2, segm_site3, new_site3, true);
- CHECK_LESS_PREDICATE_SS(segm_site1_2, segm_site3, new_site4, true);
+ CHECK_DISTANCE_PREDICATE(segm_site1_2, segm_site3, new_site1, false);
+ CHECK_DISTANCE_PREDICATE(segm_site1_2, segm_site3, new_site2, true);
+ CHECK_DISTANCE_PREDICATE(segm_site1_2, segm_site3, new_site3, true);
+ CHECK_DISTANCE_PREDICATE(segm_site1_2, segm_site3, new_site4, true);
segm_site3.inverse();
- CHECK_LESS_PREDICATE_SS(segm_site3, segm_site1_2, new_site1, false);
- CHECK_LESS_PREDICATE_SS(segm_site3, segm_site1_2, new_site2, false);
- CHECK_LESS_PREDICATE_SS(segm_site3, segm_site1_2, new_site3, false);
- CHECK_LESS_PREDICATE_SS(segm_site3, segm_site1_2, new_site4, true);
+ CHECK_DISTANCE_PREDICATE(segm_site3, segm_site1_2, new_site1, false);
+ CHECK_DISTANCE_PREDICATE(segm_site3, segm_site1_2, new_site2, false);
+ CHECK_DISTANCE_PREDICATE(segm_site3, segm_site1_2, new_site3, false);
+ CHECK_DISTANCE_PREDICATE(segm_site3, segm_site1_2, new_site4, true);
}
BOOST_AUTO_TEST_CASE_TEMPLATE(less_predicate_segment_segment_test3, T, test_types) {
@@ -274,5 +262,5 @@
segm_site1.inverse();
site_event_type segm_site2(segm_start2, segm_end, 1);
site_event<T> point(-4, 2, 0);
- CHECK_LESS_PREDICATE_SS(segm_site1, segm_site2, point, false);
+ CHECK_DISTANCE_PREDICATE(segm_site1, segm_site2, point, false);
}