|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r64196 - in sandbox/SOC/2010/sweepline: boost/sweepline boost/sweepline/detail libs/sweepline/test
From: sydorchuk.andriy_at_[hidden]
Date: 2010-07-20 09:10:14
Author: asydorchuk
Date: 2010-07-20 09:10:13 EDT (Tue, 20 Jul 2010)
New Revision: 64196
URL: http://svn.boost.org/trac/boost/changeset/64196
Log:
Upgraded integer predicates to cover -2^31 - 2^31 - 1 range.
Text files modified:
sandbox/SOC/2010/sweepline/boost/sweepline/detail/voronoi_formation.hpp | 69 ++++++++++++++++++++++++++++----------
sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_builder.hpp | 72 ++++++++++++++++++++++++++++++----------
sandbox/SOC/2010/sweepline/libs/sweepline/test/event_types_test.cpp | 1
sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_builder_test.cpp | 24 ++++++------
4 files changed, 117 insertions(+), 49 deletions(-)
Modified: sandbox/SOC/2010/sweepline/boost/sweepline/detail/voronoi_formation.hpp
==============================================================================
--- sandbox/SOC/2010/sweepline/boost/sweepline/detail/voronoi_formation.hpp (original)
+++ sandbox/SOC/2010/sweepline/boost/sweepline/detail/voronoi_formation.hpp 2010-07-20 09:10:13 EDT (Tue, 20 Jul 2010)
@@ -15,6 +15,10 @@
#include <queue>
#include <vector>
+#define INT_PREDICATE_COMPUTE_DIFFERENCE(a, b, res, sign) \
+ if (a >= b) { res = static_cast<ull>(a - b); sign = true; } \
+ else { res = static_cast<ull>(b - a); sign = false; }
+
namespace boost {
namespace sweepline {
namespace detail {
@@ -478,27 +482,56 @@
// x2(y) = ((y - y2)^2 + x2^2 - x0^2) / (2*(x2 - x0)).
// Horizontal line going throught site (x*, y*) intersects second arc
// at first if x2(y*) > x1(y*) or:
- // (x2-x0)*(x1-x0)*(x1-x2) + (x2-x0)*(y*-y1)^2 < (x1-x0)*(y*-y2)^2.
+ // (x0-x2)*(x0-x1)*(x1-x2) + (x0-x2)*(y*-y1)^2 < (x0-x1)*(y*-y2)^2.
bool less(const site_event_type &new_site) const {
- long long a1 = static_cast<long long>(new_site.x() - left_site_.x());
- long long a2 = static_cast<long long>(new_site.x() - right_site_.x());
- long long b1 = static_cast<long long>(new_site.y() - left_site_.y());
- long long b2 = static_cast<long long>(new_site.y() - right_site_.y());
- long long c = static_cast<long long>(left_site_.x() - right_site_.x());
- long long l_expr = a2 * c + b2 * b2;
- long long r_expr = b1 * b1;
- if (l_expr < 0 && r_expr > 0)
+ typedef long long ll;
+ typedef unsigned long long ull;
+ ull a1, a2, b1, b2, b1_sqr, b2_sqr, l_expr, r_expr;
+ bool l_expr_plus, r_expr_plus;
+
+ // a1 and a2 are greater than zero.
+ a1 = static_cast<ull>(static_cast<ll>(new_site.x()) -
+ static_cast<ll>(left_site_.x()));
+ a2 = static_cast<ull>(static_cast<ll>(new_site.x()) -
+ static_cast<ll>(right_site_.x()));
+
+ // We don't need to know signs of b1 and b2, because we use their squared values.
+ INT_PREDICATE_COMPUTE_DIFFERENCE(static_cast<ll>(new_site.y()),
+ static_cast<ll>(left_site_.y()),
+ b1, l_expr_plus);
+ INT_PREDICATE_COMPUTE_DIFFERENCE(static_cast<ll>(new_site.y()),
+ static_cast<ll>(right_site_.y()),
+ b2, l_expr_plus);
+ b1_sqr = b1 * b1;
+ b2_sqr = b2 * b2;
+ ull b1_sqr_mod = b1_sqr % a1;
+ ull b2_sqr_mod = b2_sqr % a2;
+
+ // Compute left expression.
+ INT_PREDICATE_COMPUTE_DIFFERENCE(static_cast<ll>(left_site_.x()),
+ static_cast<ll>(right_site_.x()),
+ l_expr, l_expr_plus);
+ if (b2_sqr_mod * a1 < b1_sqr_mod * a2) {
+ if (!l_expr_plus)
+ l_expr++;
+ else if (l_expr != 0)
+ l_expr--;
+ else {
+ l_expr++;
+ l_expr_plus = false;
+ }
+ }
+
+ // Compute right expression.
+ INT_PREDICATE_COMPUTE_DIFFERENCE(b1_sqr / a1, b2_sqr / a2, r_expr, r_expr_plus);
+ if (!l_expr_plus && r_expr_plus)
return true;
- if (l_expr > 0 && r_expr < 0)
+ if (l_expr_plus && !r_expr_plus)
return false;
- long long l_expr_div = l_expr / a2;
- long long r_expr_div = r_expr / a1;
- if (l_expr_div != r_expr_div)
- return l_expr_div < r_expr_div;
- long long l_expr_mod = l_expr % a2;
- long long r_expr_mod = r_expr % a1;
- return l_expr_mod < r_expr_mod;
-
+ if (l_expr_plus && r_expr_plus)
+ return l_expr < r_expr;
+ return l_expr > r_expr;
+
/*mpz_class a1, a2, b1, b2, c, left_expr, right_expr;
a1 = static_cast<int>(new_site.x() - left_site.x());
a2 = static_cast<int>(new_site.x() - right_site.x());
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 2010-07-20 09:10:13 EDT (Tue, 20 Jul 2010)
@@ -309,6 +309,48 @@
return beach_line_.insert(std::pair<Key, Value>(new_right_node, Value(edge->twin))).first;
}
+ bool bisectors_intersect(const Point2D &point1,
+ const Point2D &point2,
+ const Point2D &point3) const {
+ typedef long long ll;
+ typedef unsigned long long ull;
+ ull dif_x1, dif_x2, dif_y1, dif_y2;
+ bool dif_x1_plus, dif_x2_plus, dif_y1_plus, dif_y2_plus;
+ INT_PREDICATE_COMPUTE_DIFFERENCE(static_cast<ll>(point1.x()),
+ static_cast<ll>(point2.x()),
+ dif_x1, dif_x1_plus);
+ INT_PREDICATE_COMPUTE_DIFFERENCE(static_cast<ll>(point2.x()),
+ static_cast<ll>(point3.x()),
+ dif_x2, dif_x2_plus);
+ INT_PREDICATE_COMPUTE_DIFFERENCE(static_cast<ll>(point1.y()),
+ static_cast<ll>(point2.y()),
+ dif_y1, dif_y1_plus);
+ INT_PREDICATE_COMPUTE_DIFFERENCE(static_cast<ll>(point2.y()),
+ static_cast<ll>(point3.y()),
+ dif_y2, dif_y2_plus);
+ ull expr_l = dif_x1 * dif_y2;
+ bool expr_l_plus = (dif_x1_plus == dif_y2_plus) ? true : false;
+ ull expr_r = dif_x2 * dif_y1;
+ bool expr_r_plus = (dif_x2_plus == dif_y1_plus) ? true : false;
+
+ if (expr_l == 0)
+ expr_l_plus = true;
+ if (expr_r == 0)
+ expr_r_plus = true;
+
+ if (!expr_l_plus) {
+ if (expr_r_plus)
+ return true;
+ else
+ return expr_l > expr_r;
+ } else {
+ if (!expr_r_plus)
+ return false;
+ else
+ return expr_l < expr_r;
+ }
+ }
+
// Create circle event from the given three points.
bool create_circle_event(const site_event_type &site1,
const site_event_type &site2,
@@ -350,26 +392,20 @@
// site3.get_site_index());
//return true;
- long long a = (static_cast<long long>(site1.x() - site2.x()) *
- static_cast<long long>(site2.y() - site3.y()) -
- static_cast<long long>(site1.y() - site2.y()) *
- static_cast<long long>(site2.x() - site3.x())) << 1;
-
// Check if bisectors intersect.
- if (a >= 0)
+ if (!bisectors_intersect(site1.get_point(), site2.get_point(), site3.get_point()))
return false;
- long long b1 = static_cast<long long>(site1.x() - site2.x()) *
- static_cast<long long>(site1.x() + site2.x()) +
- static_cast<long long>(site1.y() - site2.y()) *
- static_cast<long long>(site1.y() + site2.y());
- long long b2 = static_cast<long long>(site2.x() - site3.x()) *
- static_cast<long long>(site2.x() + site3.x()) +
- static_cast<long long>(site2.y() - site3.y()) *
- static_cast<long long>(site2.y() + site3.y());
- coordinate_type c_x = (static_cast<coordinate_type>(b1)*(site2.y() - site3.y()) -
- static_cast<coordinate_type>(b2)*(site1.y() - site2.y())) / a;
- coordinate_type c_y = (static_cast<coordinate_type>(b2)*(site1.x() - site2.x()) -
- static_cast<coordinate_type>(b1)*(site2.x() - site3.x())) / a;
+
+ coordinate_type a = ((site1.x() - site2.x()) * (site2.y() - site3.y()) -
+ (site1.y() - site2.y()) * (site2.x() - site3.x())) *
+ static_cast<coordinate_type>(2.0);
+
+ coordinate_type b1 = (site1.x() - site2.x()) * (site1.x() + site2.x()) +
+ (site1.y() - site2.y()) * (site1.y() + site2.y());
+ coordinate_type b2 = (site2.x() - site3.x()) * (site2.x() + site3.x()) +
+ (site2.y() - site3.y()) * (site2.y() + site3.y());
+ coordinate_type c_x = (b1*(site2.y() - site3.y()) - b2*(site1.y() - site2.y())) / a;
+ coordinate_type c_y = (b2*(site1.x() - site2.x()) - b1*(site2.x() - site3.x())) / a;
coordinate_type sqr_radius = (c_x-site1.x())*(c_x-site1.x()) +
(c_y-site1.y())*(c_y-site1.y());
c_event = detail::make_circle_event<coordinate_type>(c_x, c_y, sqr_radius);
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 2010-07-20 09:10:13 EDT (Tue, 20 Jul 2010)
@@ -91,7 +91,6 @@
bool arr3[] = { true, false, true, false, false, true };
EVENT_TYPES_CHECK_COMPARISON(circle1, circle2, arr3);
-
circle2 = make_circle_event<T>(static_cast<T>(0), static_cast<T>(2), static_cast<T>(4));
circle2.set_sites(0, 0, 0);
bool arr4[] = { false, true, false, true, false, true };
Modified: sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_builder_test.cpp
==============================================================================
--- sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_builder_test.cpp (original)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_builder_test.cpp 2010-07-20 09:10:13 EDT (Tue, 20 Jul 2010)
@@ -506,8 +506,8 @@
points.clear();
for (int j = 0; j < 10; j++)
points.push_back(make_point_2d<coordinate_type>(
- static_cast<coordinate_type>(rand() % 10),
- static_cast<coordinate_type>(rand() % 10)));
+ static_cast<coordinate_type>(rand() % 5 - 5),
+ static_cast<coordinate_type>(rand() % 5 - 5)));
test_beach_line.init(points);
test_beach_line.run_sweepline();
test_beach_line.clip(test_output);
@@ -527,8 +527,8 @@
points.clear();
for (int j = 0; j < 100; j++)
points.push_back(make_point_2d<coordinate_type>(
- static_cast<coordinate_type>(rand() % 100),
- static_cast<coordinate_type>(rand() % 100)));
+ static_cast<coordinate_type>(rand() % 50 - 50),
+ static_cast<coordinate_type>(rand() % 50 - 50)));
test_beach_line.init(points);
test_beach_line.run_sweepline();
test_beach_line.clip(test_output);
@@ -548,8 +548,8 @@
points.clear();
for (int j = 0; j < 1000; j++)
points.push_back(make_point_2d<coordinate_type>(
- static_cast<coordinate_type>(rand() % 100),
- static_cast<coordinate_type>(rand() % 100)));
+ static_cast<coordinate_type>(rand() % 50 - 50),
+ static_cast<coordinate_type>(rand() % 50 - 50)));
test_beach_line.init(points);
test_beach_line.run_sweepline();
test_beach_line.clip(test_output);
@@ -569,8 +569,8 @@
points.clear();
for (int j = 0; j < 10000; j++)
points.push_back(make_point_2d<coordinate_type>(\
- static_cast<coordinate_type>(rand() % 1000),
- static_cast<coordinate_type>(rand() % 1000)));
+ static_cast<coordinate_type>(rand() % 500 - 500),
+ static_cast<coordinate_type>(rand() % 500 - 500)));
test_beach_line.init(points);
test_beach_line.run_sweepline();
test_beach_line.clip(test_output);
@@ -590,8 +590,8 @@
points.clear();
for (int j = 0; j < 100000; j++)
points.push_back(make_point_2d<coordinate_type>(
- static_cast<coordinate_type>(rand() % 1000),
- static_cast<coordinate_type>(rand() % 1000)));
+ static_cast<coordinate_type>(rand() % 500 - 500),
+ static_cast<coordinate_type>(rand() % 500 - 500)));
test_beach_line.init(points);
test_beach_line.run_sweepline();
test_beach_line.clip(test_output);
@@ -611,8 +611,8 @@
points.clear();
for (int j = 0; j < 1000000; j++)
points.push_back(make_point_2d<coordinate_type>(
- static_cast<coordinate_type>(rand() % 1000),
- static_cast<coordinate_type>(rand() % 1000)));
+ static_cast<coordinate_type>(rand() % 5000 - 5000),
+ static_cast<coordinate_type>(rand() % 5000 - 5000)));
test_beach_line.init(points);
test_beach_line.run_sweepline();
test_beach_line.clip(test_output);
Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk