Subject: [Boost-commit] svn:boost r84601 - in trunk: boost/polygon boost/polygon/detail libs/polygon/test
From: sydorchuk.andriy_at_[hidden]
Date: 2013-06-01 11:25:10
Author: asydorchuk
Date: 2013-06-01 11:25:09 EDT (Sat, 01 Jun 2013)
New Revision: 84601
URL: http://svn.boost.org/trac/boost/changeset/84601
Log:
Polygon: simplifying site event data structure.
Text files modified:
trunk/boost/polygon/detail/voronoi_predicates.hpp | 350 +++++++++++++++++++--------------------
trunk/boost/polygon/detail/voronoi_structures.hpp | 45 +---
trunk/boost/polygon/voronoi_builder.hpp | 2
trunk/libs/polygon/test/voronoi_builder_test.cpp | 9 -
trunk/libs/polygon/test/voronoi_predicates_test.cpp | 171 ++++++++++++------
trunk/libs/polygon/test/voronoi_structures_test.cpp | 70 ++++---
6 files changed, 340 insertions(+), 307 deletions(-)
Modified: trunk/boost/polygon/detail/voronoi_predicates.hpp
==============================================================================
--- trunk/boost/polygon/detail/voronoi_predicates.hpp (original)
+++ trunk/boost/polygon/detail/voronoi_predicates.hpp 2013-06-01 11:25:09 EDT (Sat, 01 Jun 2013)
@@ -161,21 +161,21 @@
bool operator()(const site_type& lhs, const circle_type& rhs) const {
typename ulp_cmp_type::Result xCmp =
- ulp_cmp(to_fpt(lhs.x()), to_fpt(rhs.lower_x()), ULPSx5);
+ ulp_cmp(to_fpt(lhs.x0()), to_fpt(rhs.lower_x()), ULPSx5);
if (xCmp != ulp_cmp_type::EQUAL)
return xCmp == ulp_cmp_type::LESS;
typename ulp_cmp_type::Result yCmp =
- ulp_cmp(to_fpt(lhs.y()), to_fpt(rhs.lower_y()), ULPSx5);
+ ulp_cmp(to_fpt(lhs.y0()), to_fpt(rhs.lower_y()), ULPSx5);
return yCmp == ulp_cmp_type::LESS;
}
bool operator()(const circle_type& lhs, const site_type& rhs) const {
typename ulp_cmp_type::Result xCmp =
- ulp_cmp(to_fpt(lhs.lower_x()), to_fpt(rhs.x()), ULPSx5);
+ ulp_cmp(to_fpt(lhs.lower_x()), to_fpt(rhs.x0()), ULPSx5);
if (xCmp != ulp_cmp_type::EQUAL)
return xCmp == ulp_cmp_type::LESS;
typename ulp_cmp_type::Result yCmp =
- ulp_cmp(to_fpt(lhs.lower_y()), to_fpt(rhs.y()), ULPSx5);
+ ulp_cmp(to_fpt(lhs.lower_y()), to_fpt(rhs.y0()), ULPSx5);
return yCmp == ulp_cmp_type::LESS;
}
@@ -198,24 +198,25 @@
class distance_predicate {
public:
typedef Site site_type;
+ typedef typename site_type::point_type point_type;
// 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 operator()(const site_type& left_site,
const site_type& right_site,
- const site_type& new_site) const {
+ const point_type& new_point) const {
if (!left_site.is_segment()) {
if (!right_site.is_segment()) {
- return pp(left_site, right_site, new_site);
+ return pp(left_site, right_site, new_point);
} else {
- return ps(left_site, right_site, new_site, false);
+ return ps(left_site, right_site, new_point, false);
}
} else {
if (!right_site.is_segment()) {
- return ps(right_site, left_site, new_site, true);
+ return ps(right_site, left_site, new_point, true);
} else {
- return ss(left_site, right_site, new_site);
+ return ss(left_site, right_site, new_point);
}
}
}
@@ -229,18 +230,15 @@
MORE = 1
};
- typedef typename Site::point_type point_type;
-
// 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.
bool pp(const site_type& left_site,
const site_type& right_site,
- const site_type& new_site) const {
+ const point_type& new_point) const {
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;
@@ -261,16 +259,15 @@
}
bool ps(const site_type& left_site, const site_type& right_site,
- const site_type& new_site, bool reverse_order) const {
+ const point_type& new_point, 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());
+ left_site, right_site, new_point, reverse_order);
+ if (fast_res != UNDEFINED) {
+ return fast_res == LESS;
+ }
+
+ fpt_type dist1 = find_distance_to_point_arc(left_site, new_point);
+ fpt_type dist2 = find_distance_to_segment_arc(right_site, new_point);
// The undefined ulp range is equal to 3EPS + 7EPS <= 10ULP.
return reverse_order ^ (dist1 < dist2);
@@ -278,19 +275,15 @@
bool ss(const site_type& left_site,
const site_type& right_site,
- const site_type& new_site) const {
+ const point_type& new_point) const {
// Handle temporary segment sites.
- if (left_site.point0() == right_site.point0() &&
- left_site.point1() == right_site.point1()) {
- return ot::eval(left_site.point0(),
- left_site.point1(),
- new_site.point0()) == ot::LEFT;
+ if (left_site.sorted_index() == right_site.sorted_index()) {
+ return ot::eval(
+ left_site.point0(), left_site.point1(), new_point) == ot::LEFT;
}
- 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());
+ fpt_type dist1 = find_distance_to_segment_arc(left_site, new_point);
+ fpt_type dist2 = find_distance_to_segment_arc(right_site, new_point);
// The undefined ulp range is equal to 7EPS + 7EPS <= 14ULP.
return dist1 < dist2;
@@ -309,8 +302,8 @@
if (is_vertical(site)) {
return (to_fpt(site.x()) - to_fpt(point.x())) * to_fpt(0.5);
} else {
- const point_type& segment0 = site.point0(true);
- const point_type& segment1 = site.point1(true);
+ const point_type& segment0 = site.point0();
+ const point_type& segment1 = site.point1();
fpt_type a1 = to_fpt(segment1.x()) - to_fpt(segment0.x());
fpt_type b1 = to_fpt(segment1.y()) - to_fpt(segment0.y());
fpt_type k = get_sqrt(a1 * a1 + b1 * b1);
@@ -335,11 +328,10 @@
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& new_point, 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();
+ const point_type& segment_start = right_site.point0();
+ const point_type& segment_end = right_site.point1();
if (ot::eval(segment_start, segment_end, new_point) != ot::RIGHT)
return (!right_site.is_inverse()) ? LESS : MORE;
@@ -394,7 +386,9 @@
public:
typedef Node node_type;
typedef typename Node::site_type site_type;
- typedef typename site_type::coordinate_type coordinate_type;
+ typedef typename site_type::point_type point_type;
+ typedef typename point_type::coordinate_type coordinate_type;
+ typedef point_comparison_predicate<point_type> point_comparison_type;
typedef distance_predicate<site_type> distance_predicate_type;
// Compares nodes in the balanced binary search tree. Nodes are
@@ -408,13 +402,17 @@
// Get x coordinate of the rightmost site from both nodes.
const site_type& site1 = get_comparison_site(node1);
const site_type& site2 = get_comparison_site(node2);
+ const point_type& point1 = get_comparison_point(site1);
+ const point_type& point2 = get_comparison_point(site2);
- if (site1.x() < site2.x()) {
+ if (point1.x() < point2.x()) {
// The second node contains a new site.
- return predicate_(node1.left_site(), node1.right_site(), site2);
- } else if (site1.x() > site2.x()) {
+ return distance_predicate_(
+ node1.left_site(), node1.right_site(), point2);
+ } else if (point1.x() > point2.x()) {
// The first node contains a new site.
- return !predicate_(node2.left_site(), node2.right_site(), site1);
+ return !distance_predicate_(
+ node2.left_site(), node2.right_site(), point1);
} else {
// This checks were evaluated experimentally.
if (site1.sorted_index() == site2.sorted_index()) {
@@ -443,25 +441,31 @@
return node.right_site();
}
+ const point_type& get_comparison_point(const site_type& site) const {
+ return point_comparison_(site.point0(), site.point1()) ?
+ site.point0() : site.point1();
+ }
+
// 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().sorted_index() ==
node.right_site().sorted_index()) {
- return std::make_pair(node.left_site().y(), 0);
+ return std::make_pair(node.left_site().y0(), 0);
}
if (node.left_site().sorted_index() > node.right_site().sorted_index()) {
if (!is_new_node &&
node.left_site().is_segment() &&
is_vertical(node.left_site())) {
- return std::make_pair(node.left_site().y1(), 1);
+ return std::make_pair(node.left_site().y0(), 1);
}
- return std::make_pair(node.left_site().y(), 1);
+ return std::make_pair(node.left_site().y1(), 1);
}
- return std::make_pair(node.right_site().y(), -1);
+ return std::make_pair(node.right_site().y0(), -1);
}
- distance_predicate_type predicate_;
+ point_comparison_type point_comparison_;
+ distance_predicate_type distance_predicate_;
};
template <typename Site>
@@ -473,8 +477,9 @@
bool ppp(const site_type& site1,
const site_type& site2,
const site_type& site3) const {
- return ot::eval(site1.point0(), site2.point0(), site3.point0()) ==
- ot::RIGHT;
+ return ot::eval(site1.point0(),
+ site2.point0(),
+ site3.point0()) == ot::RIGHT;
}
bool pps(const site_type& site1,
@@ -482,10 +487,10 @@
const site_type& site3,
int segment_index) const {
if (segment_index != 2) {
- typename ot::Orientation orient1 = ot::eval(site1.point0(),
- site2.point0(), site3.point0(true));
- typename ot::Orientation orient2 = ot::eval(site1.point0(),
- site2.point0(), site3.point1(true));
+ typename ot::Orientation orient1 = ot::eval(
+ site1.point0(), site2.point0(), site3.point0());
+ typename ot::Orientation orient2 = ot::eval(
+ site1.point0(), site2.point0(), site3.point1());
if (segment_index == 1 && site1.x0() >= site2.x0()) {
if (orient1 != ot::RIGHT)
return false;
@@ -496,9 +501,8 @@
return false;
}
} else {
- if (site3.point0(true) == site1.point0() &&
- site3.point1(true) == site2.point0())
- return false;
+ return (site3.point0() != site1.point0()) ||
+ (site3.point1() != site2.point0());
}
return true;
}
@@ -507,17 +511,16 @@
const site_type& site2,
const site_type& site3,
int point_index) const {
- if (site2.point0() == site3.point0() &&
- site2.point1() == site3.point1()) {
+ if (site2.sorted_index() == site3.sorted_index()) {
return false;
}
if (point_index == 2) {
if (!site2.is_inverse() && site3.is_inverse())
return false;
if (site2.is_inverse() == site3.is_inverse() &&
- ot::eval(site2.point0(true),
+ ot::eval(site2.point0(),
site1.point0(),
- site3.point1(true)) != ot::RIGHT)
+ site3.point1()) != ot::RIGHT)
return false;
}
return true;
@@ -526,11 +529,8 @@
bool sss(const site_type& site1,
const site_type& site2,
const site_type& site3) const {
- if (site1.point0() == site2.point0() && site1.point1() == site2.point1())
- return false;
- if (site2.point0() == site3.point0() && site2.point1() == site3.point1())
- return false;
- return true;
+ return (site1.sorted_index() != site2.sorted_index()) &&
+ (site2.sorted_index() != site3.sorted_index());
}
};
@@ -620,10 +620,10 @@
bool recompute_c_y = true,
bool recompute_lower_x = true) {
big_int_type cA[4], cB[4];
- big_int_type line_a = static_cast<int_x2_type>(site3.point1(true).y()) -
- static_cast<int_x2_type>(site3.point0(true).y());
- big_int_type line_b = static_cast<int_x2_type>(site3.point0(true).x()) -
- static_cast<int_x2_type>(site3.point1(true).x());
+ big_int_type line_a = static_cast<int_x2_type>(site3.y1()) -
+ static_cast<int_x2_type>(site3.y0());
+ big_int_type line_b = static_cast<int_x2_type>(site3.x0()) -
+ static_cast<int_x2_type>(site3.x1());
big_int_type segm_len = line_a * line_a + line_b * line_b;
big_int_type vec_x = static_cast<int_x2_type>(site2.y()) -
static_cast<int_x2_type>(site1.y());
@@ -636,15 +636,15 @@
big_int_type teta = line_a * vec_x + line_b * vec_y;
big_int_type denom = vec_x * line_b - vec_y * line_a;
- big_int_type dif0 = static_cast<int_x2_type>(site3.point1().y()) -
+ big_int_type dif0 = static_cast<int_x2_type>(site3.y1()) -
static_cast<int_x2_type>(site1.y());
big_int_type dif1 = static_cast<int_x2_type>(site1.x()) -
- static_cast<int_x2_type>(site3.point1().x());
+ static_cast<int_x2_type>(site3.x1());
big_int_type A = line_a * dif1 - line_b * dif0;
- dif0 = static_cast<int_x2_type>(site3.point1().y()) -
+ dif0 = static_cast<int_x2_type>(site3.y1()) -
static_cast<int_x2_type>(site2.y());
dif1 = static_cast<int_x2_type>(site2.x()) -
- static_cast<int_x2_type>(site3.point1().x());
+ static_cast<int_x2_type>(site3.x1());
big_int_type B = line_a * dif1 - line_b * dif0;
big_int_type sum_AB = A + B;
@@ -716,10 +716,10 @@
bool recompute_c_y = true,
bool recompute_lower_x = true) {
big_int_type a[2], b[2], c[2], cA[4], cB[4];
- const point_type& segm_start1 = site2.point1(true);
- const point_type& segm_end1 = site2.point0(true);
- const point_type& segm_start2 = site3.point0(true);
- const point_type& segm_end2 = site3.point1(true);
+ const point_type& segm_start1 = site2.point1();
+ const point_type& segm_end1 = site2.point0();
+ const point_type& segm_start2 = site3.point0();
+ const point_type& segm_end2 = site3.point1();
a[0] = static_cast<int_x2_type>(segm_end1.x()) -
static_cast<int_x2_type>(segm_start1.x());
b[0] = static_cast<int_x2_type>(segm_end1.y()) -
@@ -850,32 +850,32 @@
big_int_type a[3], b[3], c[3], cA[4], cB[4];
// cA - corresponds to the cross product.
// cB - corresponds to the squared length.
- a[0] = static_cast<int_x2_type>(site1.x1(true)) -
- static_cast<int_x2_type>(site1.x0(true));
- a[1] = static_cast<int_x2_type>(site2.x1(true)) -
- static_cast<int_x2_type>(site2.x0(true));
- a[2] = static_cast<int_x2_type>(site3.x1(true)) -
- static_cast<int_x2_type>(site3.x0(true));
-
- b[0] = static_cast<int_x2_type>(site1.y1(true)) -
- static_cast<int_x2_type>(site1.y0(true));
- b[1] = static_cast<int_x2_type>(site2.y1(true)) -
- static_cast<int_x2_type>(site2.y0(true));
- b[2] = static_cast<int_x2_type>(site3.y1(true)) -
- static_cast<int_x2_type>(site3.y0(true));
-
- c[0] = static_cast<int_x2_type>(site1.x0(true)) *
- static_cast<int_x2_type>(site1.y1(true)) -
- static_cast<int_x2_type>(site1.y0(true)) *
- static_cast<int_x2_type>(site1.x1(true));
- c[1] = static_cast<int_x2_type>(site2.x0(true)) *
- static_cast<int_x2_type>(site2.y1(true)) -
- static_cast<int_x2_type>(site2.y0(true)) *
- static_cast<int_x2_type>(site2.x1(true));
- c[2] = static_cast<int_x2_type>(site3.x0(true)) *
- static_cast<int_x2_type>(site3.y1(true)) -
- static_cast<int_x2_type>(site3.y0(true)) *
- static_cast<int_x2_type>(site3.x1(true));
+ a[0] = static_cast<int_x2_type>(site1.x1()) -
+ static_cast<int_x2_type>(site1.x0());
+ a[1] = static_cast<int_x2_type>(site2.x1()) -
+ static_cast<int_x2_type>(site2.x0());
+ a[2] = static_cast<int_x2_type>(site3.x1()) -
+ static_cast<int_x2_type>(site3.x0());
+
+ b[0] = static_cast<int_x2_type>(site1.y1()) -
+ static_cast<int_x2_type>(site1.y0());
+ b[1] = static_cast<int_x2_type>(site2.y1()) -
+ static_cast<int_x2_type>(site2.y0());
+ b[2] = static_cast<int_x2_type>(site3.y1()) -
+ static_cast<int_x2_type>(site3.y0());
+
+ c[0] = static_cast<int_x2_type>(site1.x0()) *
+ static_cast<int_x2_type>(site1.y1()) -
+ static_cast<int_x2_type>(site1.y0()) *
+ static_cast<int_x2_type>(site1.x1());
+ c[1] = static_cast<int_x2_type>(site2.x0()) *
+ static_cast<int_x2_type>(site2.y1()) -
+ static_cast<int_x2_type>(site2.y0()) *
+ static_cast<int_x2_type>(site2.x1());
+ c[2] = static_cast<int_x2_type>(site3.x0()) *
+ static_cast<int_x2_type>(site3.y1()) -
+ static_cast<int_x2_type>(site3.y0()) *
+ static_cast<int_x2_type>(site3.x1());
for (int i = 0; i < 3; ++i)
cB[i] = a[i] * a[i] + b[i] * b[i];
@@ -1060,48 +1060,46 @@
const site_type& site3,
int segment_index,
circle_type& c_event) {
- fpt_type line_a = to_fpt(site3.point1(true).y()) -
- to_fpt(site3.point0(true).y());
- fpt_type line_b = to_fpt(site3.point0(true).x()) -
- to_fpt(site3.point1(true).x());
+ fpt_type line_a = to_fpt(site3.y1()) - to_fpt(site3.y0());
+ fpt_type line_b = to_fpt(site3.x0()) - to_fpt(site3.x1());
fpt_type vec_x = to_fpt(site2.y()) - to_fpt(site1.y());
fpt_type vec_y = to_fpt(site1.x()) - to_fpt(site2.x());
robust_fpt_type teta(robust_cross_product(
- static_cast<int_x2_type>(site3.point1(true).y()) -
- static_cast<int_x2_type>(site3.point0(true).y()),
- static_cast<int_x2_type>(site3.point0(true).x()) -
- static_cast<int_x2_type>(site3.point1(true).x()),
+ static_cast<int_x2_type>(site3.y1()) -
+ static_cast<int_x2_type>(site3.y0()),
+ static_cast<int_x2_type>(site3.x0()) -
+ static_cast<int_x2_type>(site3.x1()),
static_cast<int_x2_type>(site2.x()) -
static_cast<int_x2_type>(site1.x()),
static_cast<int_x2_type>(site2.y()) -
static_cast<int_x2_type>(site1.y())), to_fpt(1.0));
robust_fpt_type A(robust_cross_product(
- static_cast<int_x2_type>(site3.point1(true).y()) -
- static_cast<int_x2_type>(site3.point0(true).y()),
- static_cast<int_x2_type>(site3.point0(true).x()) -
- static_cast<int_x2_type>(site3.point1(true).x()),
- static_cast<int_x2_type>(site3.point1().y()) -
+ static_cast<int_x2_type>(site3.y0()) -
+ static_cast<int_x2_type>(site3.y1()),
+ static_cast<int_x2_type>(site3.x0()) -
+ static_cast<int_x2_type>(site3.x1()),
+ static_cast<int_x2_type>(site3.y1()) -
static_cast<int_x2_type>(site1.y()),
- static_cast<int_x2_type>(site1.x()) -
- static_cast<int_x2_type>(site3.point1().x())), to_fpt(1.0));
+ static_cast<int_x2_type>(site3.x1()) -
+ static_cast<int_x2_type>(site1.x())), to_fpt(1.0));
robust_fpt_type B(robust_cross_product(
- static_cast<int_x2_type>(site3.point1(true).y()) -
- static_cast<int_x2_type>(site3.point0(true).y()),
- static_cast<int_x2_type>(site3.point0(true).x()) -
- static_cast<int_x2_type>(site3.point1(true).x()),
- static_cast<int_x2_type>(site3.point1().y()) -
+ static_cast<int_x2_type>(site3.y0()) -
+ static_cast<int_x2_type>(site3.y1()),
+ static_cast<int_x2_type>(site3.x0()) -
+ static_cast<int_x2_type>(site3.x1()),
+ static_cast<int_x2_type>(site3.y1()) -
static_cast<int_x2_type>(site2.y()),
- static_cast<int_x2_type>(site2.x()) -
- static_cast<int_x2_type>(site3.point1().x())), to_fpt(1.0));
+ static_cast<int_x2_type>(site3.x1()) -
+ static_cast<int_x2_type>(site2.x())), to_fpt(1.0));
robust_fpt_type denom(robust_cross_product(
- static_cast<int_x2_type>(site2.y()) -
- static_cast<int_x2_type>(site1.y()),
+ static_cast<int_x2_type>(site1.y()) -
+ static_cast<int_x2_type>(site2.y()),
static_cast<int_x2_type>(site1.x()) -
static_cast<int_x2_type>(site2.x()),
- static_cast<int_x2_type>(site3.point1(true).y()) -
- static_cast<int_x2_type>(site3.point0(true).y()),
- static_cast<int_x2_type>(site3.point0(true).x()) -
- static_cast<int_x2_type>(site3.point1(true).x())), to_fpt(1.0));
+ static_cast<int_x2_type>(site3.y1()) -
+ static_cast<int_x2_type>(site3.y0()),
+ static_cast<int_x2_type>(site3.x1()) -
+ static_cast<int_x2_type>(site3.x0())), to_fpt(1.0));
robust_fpt_type inv_segm_len(to_fpt(1.0) /
get_sqrt(line_a * line_a + line_b * line_b), to_fpt(3.0));
robust_dif_type t;
@@ -1118,11 +1116,11 @@
t += teta * (A + B) / (robust_fpt_type(to_fpt(2.0)) * denom * denom);
}
robust_dif_type c_x, c_y;
- c_x += robust_fpt_type(to_fpt(0.5) * (to_fpt(site1.x()) +
- to_fpt(site2.x())));
+ c_x += robust_fpt_type(to_fpt(0.5) *
+ (to_fpt(site1.x()) + to_fpt(site2.x())));
c_x += robust_fpt_type(vec_x) * t;
- c_y += robust_fpt_type(to_fpt(0.5) * (to_fpt(site1.y()) +
- to_fpt(site2.y())));
+ c_y += robust_fpt_type(to_fpt(0.5) *
+ (to_fpt(site1.y()) + to_fpt(site2.y())));
c_y += robust_fpt_type(vec_y) * t;
robust_dif_type r, lower_x(c_x);
r -= robust_fpt_type(line_a) * robust_fpt_type(site3.x0());
@@ -1149,10 +1147,10 @@
const site_type& site3,
int point_index,
circle_type& c_event) {
- const point_type& segm_start1 = site2.point1(true);
- const point_type& segm_end1 = site2.point0(true);
- const point_type& segm_start2 = site3.point0(true);
- const point_type& segm_end2 = site3.point1(true);
+ const point_type& segm_start1 = site2.point1();
+ const point_type& segm_end1 = site2.point0();
+ const point_type& segm_start2 = site3.point0();
+ const point_type& segm_end2 = site3.point1();
fpt_type a1 = to_fpt(segm_end1.x()) - to_fpt(segm_start1.x());
fpt_type b1 = to_fpt(segm_end1.y()) - to_fpt(segm_start1.y());
fpt_type a2 = to_fpt(segm_end2.x()) - to_fpt(segm_start2.x());
@@ -1343,54 +1341,54 @@
const site_type& site2,
const site_type& site3,
circle_type& c_event) {
- robust_fpt_type a1(to_fpt(site1.x1(true)) - to_fpt(site1.x0(true)));
- robust_fpt_type b1(to_fpt(site1.y1(true)) - to_fpt(site1.y0(true)));
+ robust_fpt_type a1(to_fpt(site1.x1()) - to_fpt(site1.x0()));
+ robust_fpt_type b1(to_fpt(site1.y1()) - to_fpt(site1.y0()));
robust_fpt_type c1(robust_cross_product(
- site1.x0(true), site1.y0(true),
- site1.x1(true), site1.y1(true)), to_fpt(1.0));
+ site1.x0(), site1.y0(),
+ site1.x1(), site1.y1()), to_fpt(1.0));
- robust_fpt_type a2(to_fpt(site2.x1(true)) - to_fpt(site2.x0(true)));
- robust_fpt_type b2(to_fpt(site2.y1(true)) - to_fpt(site2.y0(true)));
+ robust_fpt_type a2(to_fpt(site2.x1()) - to_fpt(site2.x0()));
+ robust_fpt_type b2(to_fpt(site2.y1()) - to_fpt(site2.y0()));
robust_fpt_type c2(robust_cross_product(
- site2.x0(true), site2.y0(true),
- site2.x1(true), site2.y1(true)), to_fpt(1.0));
+ site2.x0(), site2.y0(),
+ site2.x1(), site2.y1()), to_fpt(1.0));
- robust_fpt_type a3(to_fpt(site3.x1(true)) - to_fpt(site3.x0(true)));
- robust_fpt_type b3(to_fpt(site3.y1(true)) - to_fpt(site3.y0(true)));
+ robust_fpt_type a3(to_fpt(site3.x1()) - to_fpt(site3.x0()));
+ robust_fpt_type b3(to_fpt(site3.y1()) - to_fpt(site3.y0()));
robust_fpt_type c3(robust_cross_product(
- site3.x0(true), site3.y0(true),
- site3.x1(true), site3.y1(true)), to_fpt(1.0));
+ site3.x0(), site3.y0(),
+ site3.x1(), site3.y1()), to_fpt(1.0));
robust_fpt_type len1 = (a1 * a1 + b1 * b1).sqrt();
robust_fpt_type len2 = (a2 * a2 + b2 * b2).sqrt();
robust_fpt_type len3 = (a3 * a3 + b3 * b3).sqrt();
robust_fpt_type cross_12(robust_cross_product(
- static_cast<int_x2_type>(site1.x1(true)) -
- static_cast<int_x2_type>(site1.x0(true)),
- static_cast<int_x2_type>(site1.y1(true)) -
- static_cast<int_x2_type>(site1.y0(true)),
- static_cast<int_x2_type>(site2.x1(true)) -
- static_cast<int_x2_type>(site2.x0(true)),
- static_cast<int_x2_type>(site2.y1(true)) -
- static_cast<int_x2_type>(site2.y0(true))), to_fpt(1.0));
+ static_cast<int_x2_type>(site1.x1()) -
+ static_cast<int_x2_type>(site1.x0()),
+ static_cast<int_x2_type>(site1.y1()) -
+ static_cast<int_x2_type>(site1.y0()),
+ static_cast<int_x2_type>(site2.x1()) -
+ static_cast<int_x2_type>(site2.x0()),
+ static_cast<int_x2_type>(site2.y1()) -
+ static_cast<int_x2_type>(site2.y0())), to_fpt(1.0));
robust_fpt_type cross_23(robust_cross_product(
- static_cast<int_x2_type>(site2.x1(true)) -
- static_cast<int_x2_type>(site2.x0(true)),
- static_cast<int_x2_type>(site2.y1(true)) -
- static_cast<int_x2_type>(site2.y0(true)),
- static_cast<int_x2_type>(site3.x1(true)) -
- static_cast<int_x2_type>(site3.x0(true)),
- static_cast<int_x2_type>(site3.y1(true)) -
- static_cast<int_x2_type>(site3.y0(true))), to_fpt(1.0));
+ static_cast<int_x2_type>(site2.x1()) -
+ static_cast<int_x2_type>(site2.x0()),
+ static_cast<int_x2_type>(site2.y1()) -
+ static_cast<int_x2_type>(site2.y0()),
+ static_cast<int_x2_type>(site3.x1()) -
+ static_cast<int_x2_type>(site3.x0()),
+ static_cast<int_x2_type>(site3.y1()) -
+ static_cast<int_x2_type>(site3.y0())), to_fpt(1.0));
robust_fpt_type cross_31(robust_cross_product(
- static_cast<int_x2_type>(site3.x1(true)) -
- static_cast<int_x2_type>(site3.x0(true)),
- static_cast<int_x2_type>(site3.y1(true)) -
- static_cast<int_x2_type>(site3.y0(true)),
- static_cast<int_x2_type>(site1.x1(true)) -
- static_cast<int_x2_type>(site1.x0(true)),
- static_cast<int_x2_type>(site1.y1(true)) -
- static_cast<int_x2_type>(site1.y0(true))), to_fpt(1.0));
+ static_cast<int_x2_type>(site3.x1()) -
+ static_cast<int_x2_type>(site3.x0()),
+ static_cast<int_x2_type>(site3.y1()) -
+ static_cast<int_x2_type>(site3.y0()),
+ static_cast<int_x2_type>(site1.x1()) -
+ static_cast<int_x2_type>(site1.x0()),
+ static_cast<int_x2_type>(site1.y1()) -
+ static_cast<int_x2_type>(site1.y0())), to_fpt(1.0));
// denom = cross_12 * len3 + cross_23 * len1 + cross_31 * len2.
robust_dif_type denom;
Modified: trunk/boost/polygon/detail/voronoi_structures.hpp
==============================================================================
--- trunk/boost/polygon/detail/voronoi_structures.hpp (original)
+++ trunk/boost/polygon/detail/voronoi_structures.hpp 2013-06-01 11:25:09 EDT (Sat, 01 Jun 2013)
@@ -130,48 +130,36 @@
(this->point1_ != that.point1_);
}
- coordinate_type x(bool oriented = false) const {
- return x0(oriented);
+ coordinate_type x() const {
+ return point0_.x();
}
- coordinate_type y(bool oriented = false) const {
- return y0(oriented);
+ coordinate_type y() const {
+ return point0_.y();
}
- coordinate_type x0(bool oriented = false) const {
- if (!oriented)
- return point0_.x();
- return is_inverse() ? point1_.x() : point0_.x();
+ coordinate_type x0() const {
+ return point0_.x();
}
- coordinate_type y0(bool oriented = false) const {
- if (!oriented)
- return point0_.y();
- return is_inverse() ? point1_.y() : point0_.y();
+ coordinate_type y0() const {
+ return point0_.y();
}
- coordinate_type x1(bool oriented = false) const {
- if (!oriented)
- return point1_.x();
- return is_inverse() ? point0_.x() : point1_.x();
+ coordinate_type x1() const {
+ return point1_.x();
}
- coordinate_type y1(bool oriented = false) const {
- if (!oriented)
- return point1_.y();
- return is_inverse() ? point0_.y() : point1_.y();
+ coordinate_type y1() const {
+ return point1_.y();
}
- const point_type& point0(bool oriented = false) const {
- if (!oriented)
- return point0_;
- return is_inverse() ? point1_ : point0_;
+ const point_type& point0() const {
+ return point0_;
}
- const point_type& point1(bool oriented = false) const {
- if (!oriented)
- return point1_;
- return is_inverse() ? point0_ : point1_;
+ const point_type& point1() const {
+ return point1_;
}
std::size_t sorted_index() const {
@@ -197,6 +185,7 @@
}
site_event& inverse() {
+ std::swap(point0_, point1_);
flags_ ^= IS_INVERSE;
return *this;
}
Modified: trunk/boost/polygon/voronoi_builder.hpp
==============================================================================
--- trunk/boost/polygon/voronoi_builder.hpp (original)
+++ trunk/boost/polygon/voronoi_builder.hpp 2013-06-01 11:25:09 EDT (Sat, 01 Jun 2013)
@@ -388,7 +388,7 @@
site_event_type site1 = it_first->first.left_site();
if (!site1.is_segment() && site3.is_segment() &&
- site3.point1(true) == site1.point0()) {
+ site3.point1() == site1.point0()) {
site3.inverse();
}
Modified: trunk/libs/polygon/test/voronoi_builder_test.cpp
==============================================================================
--- trunk/libs/polygon/test/voronoi_builder_test.cpp (original)
+++ trunk/libs/polygon/test/voronoi_builder_test.cpp 2013-06-01 11:25:09 EDT (Sat, 01 Jun 2013)
@@ -458,15 +458,6 @@
segments.push_back(segment_data<T>(point2, point3));
points.push_back(point1);
construct_voronoi(points.begin(), points.end(), segments.begin(), segments.end(), &test_output);
- using boost::polygon::detail::int32;
- using boost::polygon::detail::int64;
- using boost::polygon::detail::fpt64;
- BOOST_CHECK_EQUAL(sizeof(detail::fpt64), 8U);
- BOOST_CHECK_EQUAL(sizeof(detail::int32), 4U);
- BOOST_CHECK_EQUAL(sizeof(detail::int64), 8U);
- vd_type::vertex_type v = test_output.vertices()[0];
- BOOST_CHECK_EQUAL(v.x(), -0.25);
- BOOST_CHECK_EQUAL(v.y(), 0.0);
CHECK_OUTPUT_SIZE(test_output, 4, 2, 10);
VERIFY_NO_HALF_EDGE_INTERSECTIONS(test_output);
}
Modified: trunk/libs/polygon/test/voronoi_predicates_test.cpp
==============================================================================
--- trunk/libs/polygon/test/voronoi_predicates_test.cpp (original)
+++ trunk/libs/polygon/test/voronoi_predicates_test.cpp 2013-06-01 11:25:09 EDT (Sat, 01 Jun 2013)
@@ -55,8 +55,8 @@
BOOST_CHECK_EQUAL(event_comparison(A, B), R1); \
BOOST_CHECK_EQUAL(event_comparison(B, A), R2)
-#define CHECK_DISTANCE_PREDICATE(S1, S2, S3, RES) \
- BOOST_CHECK_EQUAL(distance_predicate(S1, S2, S3), RES)
+#define CHECK_DISTANCE_PREDICATE(S1, S2, P3, RES) \
+ BOOST_CHECK_EQUAL(distance_predicate(S1, S2, P3), RES)
#define CHECK_NODE_COMPARISON(node, nodes, res, sz) \
for (int i = 0; i < sz; ++i) { \
@@ -140,102 +140,119 @@
BOOST_AUTO_TEST_CASE(distance_predicate_test1) {
site_type site1(-5, 0);
+ site1.sorted_index(1);
site_type site2(-8, 9);
+ site2.sorted_index(0);
site_type site3(-2, 1);
- CHECK_DISTANCE_PREDICATE(site1, site2, site_type(0, 5), false);
- CHECK_DISTANCE_PREDICATE(site3, site1, site_type(0, 5), false);
- CHECK_DISTANCE_PREDICATE(site1, site2, site_type(0, 4), false);
- CHECK_DISTANCE_PREDICATE(site3, site1, site_type(0, 4), false);
- CHECK_DISTANCE_PREDICATE(site1, site2, site_type(0, 6), true);
- CHECK_DISTANCE_PREDICATE(site3, site1, site_type(0, 6), true);
+ site3.sorted_index(2);
+ CHECK_DISTANCE_PREDICATE(site1, site2, point_type(0, 5), false);
+ CHECK_DISTANCE_PREDICATE(site3, site1, point_type(0, 5), false);
+ CHECK_DISTANCE_PREDICATE(site1, site2, point_type(0, 4), false);
+ CHECK_DISTANCE_PREDICATE(site3, site1, point_type(0, 4), false);
+ CHECK_DISTANCE_PREDICATE(site1, site2, point_type(0, 6), true);
+ CHECK_DISTANCE_PREDICATE(site3, site1, point_type(0, 6), true);
}
BOOST_AUTO_TEST_CASE(distance_predicate_test2) {
site_type site1(-4, 0, -4, 20);
+ site1.sorted_index(0);
site_type site2(-2, 10);
- CHECK_DISTANCE_PREDICATE(site2, site1, site_type(0, 11), false);
- CHECK_DISTANCE_PREDICATE(site2, site1, site_type(0, 9), false);
- CHECK_DISTANCE_PREDICATE(site1, site2, site_type(0, 11), true);
- CHECK_DISTANCE_PREDICATE(site1, site2, site_type(0, 9), true);
+ site2.sorted_index(1);
+ CHECK_DISTANCE_PREDICATE(site2, site1, point_type(0, 11), false);
+ CHECK_DISTANCE_PREDICATE(site2, site1, point_type(0, 9), false);
+ CHECK_DISTANCE_PREDICATE(site1, site2, point_type(0, 11), true);
+ CHECK_DISTANCE_PREDICATE(site1, site2, point_type(0, 9), true);
}
BOOST_AUTO_TEST_CASE(disntace_predicate_test3) {
site_type site1(-5, 5, 2, -2);
+ site1.sorted_index(0);
site1.inverse();
site_type site2(-2, 4);
- CHECK_DISTANCE_PREDICATE(site1, site2, site_type(0, -1), false);
- CHECK_DISTANCE_PREDICATE(site2, site1, site_type(0, -1), false);
- CHECK_DISTANCE_PREDICATE(site1, site2, site_type(0, 1), false);
- CHECK_DISTANCE_PREDICATE(site2, site1, site_type(0, 1), false);
- CHECK_DISTANCE_PREDICATE(site1, site2, site_type(0, 4), true);
- CHECK_DISTANCE_PREDICATE(site2, site1, site_type(0, 4), false);
- CHECK_DISTANCE_PREDICATE(site1, site2, site_type(0, 5), true);
- CHECK_DISTANCE_PREDICATE(site2, site1, site_type(0, 5), false);
+ site2.sorted_index(1);
+ CHECK_DISTANCE_PREDICATE(site1, site2, point_type(0, -1), false);
+ CHECK_DISTANCE_PREDICATE(site2, site1, point_type(0, -1), false);
+ CHECK_DISTANCE_PREDICATE(site1, site2, point_type(0, 1), false);
+ CHECK_DISTANCE_PREDICATE(site2, site1, point_type(0, 1), false);
+ CHECK_DISTANCE_PREDICATE(site1, site2, point_type(0, 4), true);
+ CHECK_DISTANCE_PREDICATE(site2, site1, point_type(0, 4), false);
+ CHECK_DISTANCE_PREDICATE(site1, site2, point_type(0, 5), true);
+ CHECK_DISTANCE_PREDICATE(site2, site1, point_type(0, 5), false);
}
BOOST_AUTO_TEST_CASE(distance_predicate_test4) {
site_type site1(-5, 5, 2, -2);
+ site1.sorted_index(0);
site_type site2(-2, -4);
+ site2.sorted_index(2);
site_type site3(-4, 1);
- CHECK_DISTANCE_PREDICATE(site1, site2, site_type(0, 1), true);
- CHECK_DISTANCE_PREDICATE(site2, site1, site_type(0, 1), true);
- CHECK_DISTANCE_PREDICATE(site1, site3, site_type(0, 1), true);
- CHECK_DISTANCE_PREDICATE(site3, site1, site_type(0, 1), true);
- CHECK_DISTANCE_PREDICATE(site1, site2, site_type(0, -2), true);
- CHECK_DISTANCE_PREDICATE(site2, site1, site_type(0, -2), false);
- CHECK_DISTANCE_PREDICATE(site1, site3, site_type(0, -2), true);
- CHECK_DISTANCE_PREDICATE(site3, site1, site_type(0, -2), false);
- CHECK_DISTANCE_PREDICATE(site1, site2, site_type(0, -8), true);
- CHECK_DISTANCE_PREDICATE(site2, site1, site_type(0, -8), false);
- CHECK_DISTANCE_PREDICATE(site1, site3, site_type(0, -8), true);
- CHECK_DISTANCE_PREDICATE(site3, site1, site_type(0, -8), false);
- CHECK_DISTANCE_PREDICATE(site1, site2, site_type(0, -9), true);
- CHECK_DISTANCE_PREDICATE(site2, site1, site_type(0, -9), false);
- CHECK_DISTANCE_PREDICATE(site1, site3, site_type(0, -9), true);
- CHECK_DISTANCE_PREDICATE(site3, site1, site_type(0, -9), false);
+ site3.sorted_index(1);
+ CHECK_DISTANCE_PREDICATE(site1, site2, point_type(0, 1), true);
+ CHECK_DISTANCE_PREDICATE(site2, site1, point_type(0, 1), true);
+ CHECK_DISTANCE_PREDICATE(site1, site3, point_type(0, 1), true);
+ CHECK_DISTANCE_PREDICATE(site3, site1, point_type(0, 1), true);
+ CHECK_DISTANCE_PREDICATE(site1, site2, point_type(0, -2), true);
+ CHECK_DISTANCE_PREDICATE(site2, site1, point_type(0, -2), false);
+ CHECK_DISTANCE_PREDICATE(site1, site3, point_type(0, -2), true);
+ CHECK_DISTANCE_PREDICATE(site3, site1, point_type(0, -2), false);
+ CHECK_DISTANCE_PREDICATE(site1, site2, point_type(0, -8), true);
+ CHECK_DISTANCE_PREDICATE(site2, site1, point_type(0, -8), false);
+ CHECK_DISTANCE_PREDICATE(site1, site3, point_type(0, -8), true);
+ CHECK_DISTANCE_PREDICATE(site3, site1, point_type(0, -8), false);
+ CHECK_DISTANCE_PREDICATE(site1, site2, point_type(0, -9), true);
+ CHECK_DISTANCE_PREDICATE(site2, site1, point_type(0, -9), false);
+ CHECK_DISTANCE_PREDICATE(site1, site3, point_type(0, -9), true);
+ CHECK_DISTANCE_PREDICATE(site3, site1, point_type(0, -9), false);
}
BOOST_AUTO_TEST_CASE(disntace_predicate_test5) {
site_type site1(-5, 5, 2, -2);
+ site1.sorted_index(0);
site_type site2 = site1;
site2.inverse();
site_type site3(-2, 4);
+ site3.sorted_index(3);
site_type site4(-2, -4);
+ site4.sorted_index(2);
site_type site5(-4, 1);
- CHECK_DISTANCE_PREDICATE(site3, site2, site_type(0, 1), false);
- CHECK_DISTANCE_PREDICATE(site3, site2, site_type(0, 4), false);
- CHECK_DISTANCE_PREDICATE(site3, site2, site_type(0, 5), false);
- CHECK_DISTANCE_PREDICATE(site3, site2, site_type(0, 7), true);
- CHECK_DISTANCE_PREDICATE(site4, site1, site_type(0, -2), false);
- CHECK_DISTANCE_PREDICATE(site5, site1, site_type(0, -2), false);
- CHECK_DISTANCE_PREDICATE(site4, site1, site_type(0, -8), false);
- CHECK_DISTANCE_PREDICATE(site5, site1, site_type(0, -8), false);
- CHECK_DISTANCE_PREDICATE(site4, site1, site_type(0, -9), false);
- CHECK_DISTANCE_PREDICATE(site5, site1, site_type(0, -9), false);
- CHECK_DISTANCE_PREDICATE(site4, site1, site_type(0, -18), false);
- CHECK_DISTANCE_PREDICATE(site5, site1, site_type(0, -18), false);
- CHECK_DISTANCE_PREDICATE(site4, site1, site_type(0, -1), true);
- CHECK_DISTANCE_PREDICATE(site5, site1, site_type(0, -1), true);
+ site5.sorted_index(1);
+ CHECK_DISTANCE_PREDICATE(site3, site2, point_type(0, 1), false);
+ CHECK_DISTANCE_PREDICATE(site3, site2, point_type(0, 4), false);
+ CHECK_DISTANCE_PREDICATE(site3, site2, point_type(0, 5), false);
+ CHECK_DISTANCE_PREDICATE(site3, site2, point_type(0, 7), true);
+ CHECK_DISTANCE_PREDICATE(site4, site1, point_type(0, -2), false);
+ CHECK_DISTANCE_PREDICATE(site5, site1, point_type(0, -2), false);
+ CHECK_DISTANCE_PREDICATE(site4, site1, point_type(0, -8), false);
+ CHECK_DISTANCE_PREDICATE(site5, site1, point_type(0, -8), false);
+ CHECK_DISTANCE_PREDICATE(site4, site1, point_type(0, -9), false);
+ CHECK_DISTANCE_PREDICATE(site5, site1, point_type(0, -9), false);
+ CHECK_DISTANCE_PREDICATE(site4, site1, point_type(0, -18), false);
+ CHECK_DISTANCE_PREDICATE(site5, site1, point_type(0, -18), false);
+ CHECK_DISTANCE_PREDICATE(site4, site1, point_type(0, -1), true);
+ CHECK_DISTANCE_PREDICATE(site5, site1, point_type(0, -1), true);
}
BOOST_AUTO_TEST_CASE(distance_predicate_test6) {
site_type site1(-5, 0, 2, 7);
site_type site2 = site1;
site2.inverse();
- CHECK_DISTANCE_PREDICATE(site1, site2, site_type(2, 7), false);
- CHECK_DISTANCE_PREDICATE(site1, site2, site_type(1, 5), false);
- CHECK_DISTANCE_PREDICATE(site1, site2, site_type(-1, 5), true);
+ CHECK_DISTANCE_PREDICATE(site1, site2, point_type(2, 7), false);
+ CHECK_DISTANCE_PREDICATE(site1, site2, point_type(1, 5), false);
+ CHECK_DISTANCE_PREDICATE(site1, site2, point_type(-1, 5), true);
}
BOOST_AUTO_TEST_CASE(distance_predicate_test7) {
site_type site1(-5, 5, 2, -2);
+ site1.sorted_index(1);
site1.inverse();
site_type site2(-5, 5, 0, 6);
+ site2.sorted_index(0);
site_type site3(-2, 4, 0, 4);
- site_type site4(0, 2);
- site_type site5(0, 5);
- site_type site6(0, 6);
- site_type site7(0, 8);
+ site3.sorted_index(2);
+ point_type site4(0, 2);
+ point_type site5(0, 5);
+ point_type site6(0, 6);
+ point_type site7(0, 8);
CHECK_DISTANCE_PREDICATE(site1, site2, site4, false);
CHECK_DISTANCE_PREDICATE(site1, site2, site5, true);
CHECK_DISTANCE_PREDICATE(site1, site2, site6, true);
@@ -251,11 +268,13 @@
CHECK_DISTANCE_PREDICATE(site3, site1, site7, true);
}
-BOOST_AUTO_TEST_CASE(distatnce_predicate_test8) {
+BOOST_AUTO_TEST_CASE(distance_predicate_test8) {
site_type site1(-5, 3, -2, 2);
+ site1.sorted_index(0);
site1.inverse();
site_type site2(-5, 5, -2, 2);
- CHECK_DISTANCE_PREDICATE(site1, site2, site_type(-4, 2), false);
+ site2.sorted_index(1);
+ CHECK_DISTANCE_PREDICATE(site1, site2, point_type(-4, 2), false);
}
BOOST_AUTO_TEST_CASE(node_comparison_test1) {
@@ -377,8 +396,11 @@
BOOST_AUTO_TEST_CASE(circle_formation_predicate_test1) {
site_type site1(0, 0);
+ site1.sorted_index(1);
site_type site2(-8, 0);
+ site2.sorted_index(0);
site_type site3(0, 6);
+ site3.sorted_index(2);
CHECK_CIRCLE_FORMATION_PREDICATE(site1, site2, site3, -4.0, 3.0, 1.0);
}
@@ -386,78 +408,109 @@
int min_int = (std::numeric_limits<int>::min)();
int max_int = (std::numeric_limits<int>::max)();
site_type site1(min_int, min_int);
+ site1.sorted_index(0);
site_type site2(min_int, max_int);
+ site2.sorted_index(1);
site_type site3(max_int-1, max_int-1);
+ site3.sorted_index(2);
site_type site4(max_int, max_int);
+ site4.sorted_index(3);
CHECK_CIRCLE_EXISTENCE(site1, site2, site4, true);
CHECK_CIRCLE_EXISTENCE(site1, site3, site4, false);
}
BOOST_AUTO_TEST_CASE(circle_formation_predicate_test3) {
site_type site1(-4, 0);
+ site1.sorted_index(0);
site_type site2(0, 4);
+ site2.sorted_index(4);
site_type site3(site1.point0(), site2.point0());
+ site3.sorted_index(1);
CHECK_CIRCLE_EXISTENCE(site1, site3, site2, false);
site_type site4(-2, 0);
+ site4.sorted_index(2);
site_type site5(0, 2);
+ site5.sorted_index(3);
CHECK_CIRCLE_EXISTENCE(site3, site4, site5, false);
CHECK_CIRCLE_EXISTENCE(site4, site5, site3, false);
}
BOOST_AUTO_TEST_CASE(circle_formation_predicate_test4) {
site_type site1(-4, 0, -4, 20);
+ site1.sorted_index(0);
site_type site2(-2, 10);
+ site2.sorted_index(1);
site_type site3(4, 10);
+ site3.sorted_index(2);
CHECK_CIRCLE_FORMATION_PREDICATE(site1, site2, site3, 1.0, 6.0, 6.0);
CHECK_CIRCLE_FORMATION_PREDICATE(site3, site2, site1, 1.0, 14.0, 6.0);
}
BOOST_AUTO_TEST_CASE(circle_formation_predicate_test5) {
site_type site1(1, 0, 7, 0);
+ site1.sorted_index(2);
site1.inverse();
site_type site2(-2, 4, 10, 4);
+ site2.sorted_index(0);
site_type site3(6, 2);
+ site3.sorted_index(3);
site_type site4(1, 0);
+ site4.sorted_index(1);
CHECK_CIRCLE_FORMATION_PREDICATE(site3, site1, site2, 4.0, 2.0, 6.0);
CHECK_CIRCLE_FORMATION_PREDICATE(site4, site2, site1, 1.0, 2.0, 3.0);
}
BOOST_AUTO_TEST_CASE(circle_formation_predicate_test6) {
site_type site1(-1, 2, 8, -10);
+ site1.sorted_index(1);
site1.inverse();
site_type site2(-1, 0, 8, 12);
+ site2.sorted_index(0);
site_type site3(1, 1);
+ site3.sorted_index(2);
CHECK_CIRCLE_FORMATION_PREDICATE(site3, site2, site1, 6.0, 1.0, 11.0);
}
BOOST_AUTO_TEST_CASE(circle_formation_predicate_test7) {
site_type site1(1, 0, 6, 0);
+ site1.sorted_index(2);
site1.inverse();
site_type site2(-6, 4, 0, 12);
+ site2.sorted_index(0);
site_type site3(1, 0);
+ site3.sorted_index(1);
CHECK_CIRCLE_FORMATION_PREDICATE(site3, site2, site1, 1.0, 5.0, 6.0);
}
BOOST_AUTO_TEST_CASE(circle_formation_predicate_test8) {
site_type site1(1, 0, 5, 0);
+ site1.sorted_index(2);
site1.inverse();
site_type site2(0, 12, 8, 6);
+ site2.sorted_index(0);
site_type site3(1, 0);
+ site3.sorted_index(1);
CHECK_CIRCLE_FORMATION_PREDICATE(site3, site2, site1, 1.0, 5.0, 6.0);
}
BOOST_AUTO_TEST_CASE(circle_formation_predicate_test9) {
site_type site1(0, 0, 4, 0);
+ site1.sorted_index(1);
site_type site2(0, 0, 0, 4);
+ site2.sorted_index(0);
site_type site3(0, 4, 4, 4);
+ site3.sorted_index(2);
site1.inverse();
CHECK_CIRCLE_FORMATION_PREDICATE(site1, site2, site3, 2.0, 2.0, 4.0);
}
BOOST_AUTO_TEST_CASE(circle_formation_predicate_test10) {
site_type site1(1, 0, 41, 30);
+ site1.sorted_index(1);
site_type site2(-39, 30, 1, 60);
+ site2.sorted_index(0);
site_type site3(1, 60, 41, 30);
+ site3.sorted_index(2);
site1.inverse();
CHECK_CIRCLE_FORMATION_PREDICATE(site1, site2, site3, 1.0, 30.0, 25.0);
}
Modified: trunk/libs/polygon/test/voronoi_structures_test.cpp
==============================================================================
--- trunk/libs/polygon/test/voronoi_structures_test.cpp (original)
+++ trunk/libs/polygon/test/voronoi_structures_test.cpp 2013-06-01 11:25:09 EDT (Sat, 01 Jun 2013)
@@ -27,12 +27,12 @@
BOOST_AUTO_TEST_CASE(point_2d_test1) {
point_type p(1, 2);
- BOOST_CHECK_EQUAL(p.x(), 1);
- BOOST_CHECK_EQUAL(p.y(), 2);
+ BOOST_CHECK_EQUAL(1, p.x());
+ BOOST_CHECK_EQUAL(2, p.y());
p.x(3);
- BOOST_CHECK_EQUAL(p.x(), 3);
+ BOOST_CHECK_EQUAL(3, p.x());
p.y(4);
- BOOST_CHECK_EQUAL(p.y(), 4);
+ BOOST_CHECK_EQUAL(4, p.y());
}
BOOST_AUTO_TEST_CASE(site_event_test1) {
@@ -40,14 +40,16 @@
s.sorted_index(1);
s.initial_index(2);
s.source_category(SOURCE_CATEGORY_SEGMENT_START_POINT);
- BOOST_CHECK(s.x0() == 1 && s.x1() == 1);
- BOOST_CHECK(s.y0() == 2 && s.y1() == 2);
+ BOOST_CHECK_EQUAL(1, s.x0());
+ BOOST_CHECK_EQUAL(1, s.x1());
+ BOOST_CHECK_EQUAL(2, s.y0());
+ BOOST_CHECK_EQUAL(2, s.y1());
BOOST_CHECK(s.is_point());
BOOST_CHECK(!s.is_segment());
BOOST_CHECK(!s.is_inverse());
- BOOST_CHECK(s.sorted_index() == 1);
- BOOST_CHECK(s.initial_index() == 2);
- BOOST_CHECK(s.source_category() == SOURCE_CATEGORY_SEGMENT_START_POINT);
+ BOOST_CHECK_EQUAL(1, s.sorted_index());
+ BOOST_CHECK_EQUAL(2, s.initial_index());
+ BOOST_CHECK_EQUAL(SOURCE_CATEGORY_SEGMENT_START_POINT, s.source_category());
}
BOOST_AUTO_TEST_CASE(site_event_test2) {
@@ -55,38 +57,38 @@
s.sorted_index(1);
s.initial_index(2);
s.source_category(SOURCE_CATEGORY_INITIAL_SEGMENT);
- BOOST_CHECK(s.x0(true) == 1 && s.x0() == 1);
- BOOST_CHECK(s.y0(true) == 2 && s.y0() == 2);
- BOOST_CHECK(s.x1(true) == 3 && s.x1() == 3);
- BOOST_CHECK(s.y1(true) == 4 && s.y1() == 4);
+ BOOST_CHECK_EQUAL(1, s.x0());
+ BOOST_CHECK_EQUAL(2, s.y0());
+ BOOST_CHECK_EQUAL(3, s.x1());
+ BOOST_CHECK_EQUAL(4, s.y1());
BOOST_CHECK(!s.is_point());
BOOST_CHECK(s.is_segment());
BOOST_CHECK(!s.is_inverse());
- BOOST_CHECK(s.source_category() == SOURCE_CATEGORY_INITIAL_SEGMENT);
+ BOOST_CHECK_EQUAL(SOURCE_CATEGORY_INITIAL_SEGMENT, s.source_category());
s.inverse();
- BOOST_CHECK(s.x1(true) == 1 && s.x0() == 1);
- BOOST_CHECK(s.y1(true) == 2 && s.y0() == 2);
- BOOST_CHECK(s.x0(true) == 3 && s.x1() == 3);
- BOOST_CHECK(s.y0(true) == 4 && s.y1() == 4);
+ BOOST_CHECK_EQUAL(3, s.x0());
+ BOOST_CHECK_EQUAL(4, s.y0());
+ BOOST_CHECK_EQUAL(1, s.x1());
+ BOOST_CHECK_EQUAL(2, s.y1());
BOOST_CHECK(s.is_inverse());
- BOOST_CHECK(s.source_category() == SOURCE_CATEGORY_INITIAL_SEGMENT);
+ BOOST_CHECK_EQUAL(SOURCE_CATEGORY_INITIAL_SEGMENT, s.source_category());
}
BOOST_AUTO_TEST_CASE(circle_event_test) {
circle_type c(0, 1, 2);
- BOOST_CHECK_EQUAL(c.x(), 0);
- BOOST_CHECK_EQUAL(c.y(), 1);
- BOOST_CHECK_EQUAL(c.lower_x(), 2);
- BOOST_CHECK_EQUAL(c.lower_y(), 1);
+ BOOST_CHECK_EQUAL(0, c.x());
+ BOOST_CHECK_EQUAL(1, c.y());
+ BOOST_CHECK_EQUAL(2, c.lower_x());
+ BOOST_CHECK_EQUAL(1, c.lower_y());
BOOST_CHECK(c.is_active());
c.x(3);
c.y(4);
c.lower_x(5);
- BOOST_CHECK_EQUAL(c.x(), 3);
- BOOST_CHECK_EQUAL(c.y(), 4);
- BOOST_CHECK_EQUAL(c.lower_x(), 5);
- BOOST_CHECK_EQUAL(c.lower_y(), 4);
+ BOOST_CHECK_EQUAL(3, c.x());
+ BOOST_CHECK_EQUAL(4, c.y());
+ BOOST_CHECK_EQUAL(5, c.lower_x());
+ BOOST_CHECK_EQUAL(4, c.lower_y());
c.deactivate();
BOOST_CHECK(!c.is_active());
}
@@ -101,20 +103,20 @@
*vi[i] <<= 1;
BOOST_CHECK(!q.empty());
for (int i = 0; i < 20; ++i, q.pop())
- BOOST_CHECK_EQUAL(q.top(), i << 1);
+ BOOST_CHECK_EQUAL(i << 1, q.top());
BOOST_CHECK(q.empty());
}
BOOST_AUTO_TEST_CASE(beach_line_node_key_test) {
node_key_type key(1);
- BOOST_CHECK_EQUAL(key.left_site(), 1);
- BOOST_CHECK_EQUAL(key.right_site(), 1);
+ BOOST_CHECK_EQUAL(1, key.left_site());
+ BOOST_CHECK_EQUAL(1, key.right_site());
key.left_site(2);
- BOOST_CHECK_EQUAL(key.left_site(), 2);
- BOOST_CHECK_EQUAL(key.right_site(), 1);
+ BOOST_CHECK_EQUAL(2, key.left_site());
+ BOOST_CHECK_EQUAL(1, key.right_site());
key.right_site(3);
- BOOST_CHECK_EQUAL(key.left_site(), 2);
- BOOST_CHECK_EQUAL(key.right_site(), 3);
+ BOOST_CHECK_EQUAL(2, key.left_site());
+ BOOST_CHECK_EQUAL(3, key.right_site());
}
BOOST_AUTO_TEST_CASE(beach_line_node_data_test) {