Subject: [Boost-commit] svn:boost r63255 - in sandbox/SOC/2010/sweepline: boost/sweepline boost/sweepline/detail libs/sweepline/test
From: sydorchuk.andriy_at_[hidden]
Date: 2010-06-22 19:08:40
Author: asydorchuk
Date: 2010-06-22 19:08:36 EDT (Tue, 22 Jun 2010)
New Revision: 63255
URL: http://svn.boost.org/trac/boost/changeset/63255
Log:
Added node comparer tests.
Updated node comparer algorithm.
Added new random voronoi_builder tests.
Text files modified:
sandbox/SOC/2010/sweepline/boost/sweepline/detail/voronoi_formation.hpp | 72 ++++++++++--
sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_builder.hpp | 6
sandbox/SOC/2010/sweepline/libs/sweepline/test/node_comparer_test.cpp | 228 +++++++++++++++++++++++++++++++++------
sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_builder_test.cpp | 88 ++++++++++++--
4 files changed, 324 insertions(+), 70 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-06-22 19:08:36 EDT (Tue, 22 Jun 2010)
@@ -194,9 +194,25 @@
circle_event(T c_x, T c_y, T sqr_r) :
center_(c_x, c_y), sqr_radius_(sqr_r) {}
+ circle_event(const circle_event& c_event) {
+ center_ = c_event.center_;
+ sqr_radius_ = c_event.sqr_radius_;
+ bisector_node_ = c_event.bisector_node_;
+ for (int i = 0; i < 3; i++)
+ sites_[i] = c_event.sites_[i];
+ }
+
+ void operator=(const circle_event& c_event) {
+ center_ = c_event.center_;
+ sqr_radius_ = c_event.sqr_radius_;
+ bisector_node_ = c_event.bisector_node_;
+ for (int i = 0; i < 3; i++)
+ sites_[i] = c_event.sites_[i];
+ }
+
bool equals(const circle_event &c_event) const {
return center_.x() == c_event.x() && center_.y() == c_event.y() &&
- sqr_radius_ == c_event.get_sqr_radius() &&
+ sqr_radius_ == c_event.sqr_radius_ &&
sites_[0] == c_event.sites_[0] &&
sites_[1] == c_event.sites_[1] &&
sites_[2] == c_event.sites_[2];
@@ -213,10 +229,10 @@
T sqr_dif_x = (center_.x() - c_event.x()) *
(center_.x() - c_event.x());
- T sum_r_sqr = sqr_radius_ + c_event.get_sqr_radius();
+ T sum_r_sqr = sqr_radius_ + c_event.sqr_radius_;
T value_left = (sum_r_sqr - sqr_dif_x) * (sum_r_sqr - sqr_dif_x);
T value_right = static_cast<T>(4) * sqr_radius_ *
- c_event.get_sqr_radius();
+ c_event.sqr_radius_;
return value_left == value_right;
}
@@ -357,8 +373,8 @@
return bisector_node_;
}
- const site_event<T>* get_sites() {
- return sites;
+ const site_event<T>* get_sites() const {
+ return sites_;
}
private:
@@ -588,7 +604,7 @@
return true;
}
- circle_event_type top() {
+ const circle_event_type &top() {
remove_not_active_events();
return circle_events_.top();
}
@@ -752,8 +768,44 @@
coordinate_type node1_line = node1.get_sweepline_coord();
coordinate_type node2_line = node2.get_sweepline_coord();
- // Both nodes are situated on the same vertical line.
- if (node1_line == node2_line) {
+ if (node1_line < node2_line) {
+ coordinate_type left_site_x = node1.get_left_site().x();
+ coordinate_type left_site_y = node1.get_left_site().y();
+ coordinate_type right_site_x = node1.get_right_site().x();
+ coordinate_type right_site_y = node1.get_right_site().y();
+ coordinate_type new_node_y = node2.get_new_site().y();
+ if (left_site_x > right_site_x) {
+ if (new_node_y <= left_site_y)
+ return false;
+ return node1.less(node2.get_new_site());
+ } else if (left_site_x < right_site_x) {
+ if (new_node_y >= right_site_y)
+ return true;
+ return node1.less(node2.get_new_site());
+ } else {
+ return left_site_y + right_site_y <
+ static_cast<coordinate_type>(2.0) * new_node_y;
+ }
+ } else if (node1_line > node2_line) {
+ coordinate_type left_site_x = node2.get_left_site().x();
+ coordinate_type left_site_y = node2.get_left_site().y();
+ coordinate_type right_site_x = node2.get_right_site().x();
+ coordinate_type right_site_y = node2.get_right_site().y();
+ coordinate_type new_node_y = node1.get_new_site().y();
+ if (left_site_x > right_site_x) {
+ if (new_node_y <= left_site_y)
+ return true;
+ return !node2.less(node1.get_new_site());
+ } else if (left_site_x < right_site_x) {
+ if (new_node_y >= right_site_y)
+ return false;
+ return !node2.less(node1.get_new_site());
+ } else {
+ return !(left_site_y + right_site_y <
+ static_cast<coordinate_type>(2.0) * new_node_y);
+ }
+ } else {
+ // Both nodes are situated on the same vertical line.
// Let A be the new site event point, and B the site that
// creates arc above A. In this case two new nodes are being
// inserted: (A,B) and (B,A). As intersection points for the
@@ -770,10 +822,6 @@
// Just compare coordinates of the sites situated on the sweepline.
return node1.get_new_site().y() < node2.get_new_site().y();
}
- else if (node1_line < node2_line)
- return node1.less(node2.get_new_site());
- else
- return !node2.less(node1.get_new_site());
}
};
Modified: sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_builder.hpp
==============================================================================
--- sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_builder.hpp (original)
+++ sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_builder.hpp 2010-06-22 19:08:36 EDT (Tue, 22 Jun 2010)
@@ -82,11 +82,11 @@
}
void reset() {
- site_events_.clear();
- site_events_iterator_ = site_events_.begin();
+ output_.reset();
circle_events_.reset();
beach_line_.clear();
- output_.clear();
+ site_events_.clear();
+ site_events_iterator_ = site_events_.begin();
}
void run_sweepline() {
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 2010-06-22 19:08:36 EDT (Tue, 22 Jun 2010)
@@ -20,43 +20,6 @@
std::map< bline_node, int, node_comparer<bline_node> > test_beach_line;
- bline_node initial_node(
- make_site_event<T>(static_cast<T>(0), static_cast<T>(0), 0),
- make_site_event<T>(static_cast<T>(0), static_cast<T>(2), 1));
- test_beach_line[initial_node] = 0;
- BOOST_CHECK_EQUAL(test_beach_line.size(), 1);
-
- bline_node new_node1(make_site_event<T>(static_cast<T>(1), static_cast<T>(0), 2));
- bline_node new_node2(make_site_event<T>(static_cast<T>(1), static_cast<T>(1), 3));
- bline_node new_node3(make_site_event<T>(static_cast<T>(1), static_cast<T>(2), 4));
- bline_node new_node4(make_site_event<T>(static_cast<T>(1), static_cast<T>(1.000001), 5));
- bline_node new_node5(make_site_event<T>(static_cast<T>(1), static_cast<T>(0.999999), 6));
-
- bline_it it = test_beach_line.lower_bound(new_node1);
- BOOST_CHECK_EQUAL(it == test_beach_line.begin(), true);
-
- it = test_beach_line.lower_bound(new_node2);
- BOOST_CHECK_EQUAL(it == test_beach_line.begin(), true);
-
- it = test_beach_line.lower_bound(new_node3);
- BOOST_CHECK_EQUAL(it == test_beach_line.end(), true);
-
- it = test_beach_line.lower_bound(new_node4);
- BOOST_CHECK_EQUAL(it == test_beach_line.end(), true);
-
- it = test_beach_line.lower_bound(new_node5);
- BOOST_CHECK_EQUAL(it == test_beach_line.begin(), true);
-
- it = test_beach_line.lower_bound(initial_node);
- BOOST_CHECK_EQUAL(it == test_beach_line.begin(), true);
-}
-
-BOOST_AUTO_TEST_CASE_TEMPLATE(node_comparer_test2, T, test_types) {
- typedef beach_line_node< point_2d<T> > bline_node;
- typedef std::map< bline_node, int, node_comparer<bline_node> >::const_iterator bline_it;
-
- std::map< bline_node, int, node_comparer<bline_node> > test_beach_line;
-
site_event<T> site1 = make_site_event<T>(static_cast<T>(0), static_cast<T>(0), 0);
site_event<T> site2 = make_site_event<T>(static_cast<T>(0), static_cast<T>(2), 1);
bline_node initial_node(site1, site2);
@@ -75,7 +38,7 @@
BOOST_CHECK_EQUAL(it->second, cur_value);
}
-BOOST_AUTO_TEST_CASE_TEMPLATE(node_comparer_test3, T, test_types) {
+BOOST_AUTO_TEST_CASE_TEMPLATE(node_comparer_test2, T, test_types) {
typedef beach_line_node< point_2d<T> > bline_node;
typedef std::map< bline_node, int, node_comparer<bline_node> >::const_iterator bline_it;
@@ -99,4 +62,193 @@
it != test_beach_line.end();
it++, cur_value++)
BOOST_CHECK_EQUAL(it->second, cur_value);
+}
+
+BOOST_AUTO_TEST_CASE_TEMPLATE(node_comparer_test3, T, test_types) {
+ typedef beach_line_node< point_2d<T> > bline_node;
+ node_comparer<bline_node> node_comparer_test;
+
+ bline_node initial_node(
+ make_site_event<T>(static_cast<T>(1), static_cast<T>(0), 0),
+ make_site_event<T>(static_cast<T>(0), static_cast<T>(2), 1));
+
+ bline_node new_node1(make_site_event<T>(static_cast<T>(1.5), static_cast<T>(-10), 2));
+ bline_node new_node2(make_site_event<T>(static_cast<T>(1.5), static_cast<T>(-0.5), 3));
+ bline_node new_node3(make_site_event<T>(static_cast<T>(1.5), static_cast<T>(0), 4));
+ bline_node new_node4(make_site_event<T>(static_cast<T>(1.5), static_cast<T>(0.5), 4));
+ bline_node new_node5(make_site_event<T>(static_cast<T>(1.5), static_cast<T>(1.0), 4));
+ bline_node new_node6(make_site_event<T>(static_cast<T>(1.5), static_cast<T>(3.0), 4));
+ bline_node new_node7(make_site_event<T>(static_cast<T>(2.0), static_cast<T>(1.0), 4));
+
+
+ BOOST_CHECK_EQUAL(node_comparer_test(initial_node, new_node1), false);
+ BOOST_CHECK_EQUAL(node_comparer_test(initial_node, new_node2), false);
+ BOOST_CHECK_EQUAL(node_comparer_test(initial_node, new_node3), false);
+ BOOST_CHECK_EQUAL(node_comparer_test(initial_node, new_node4), false);
+ BOOST_CHECK_EQUAL(node_comparer_test(initial_node, new_node5), true);
+ BOOST_CHECK_EQUAL(node_comparer_test(initial_node, new_node6), true);
+ BOOST_CHECK_EQUAL(node_comparer_test(initial_node, new_node7), false);
+
+
+ BOOST_CHECK_EQUAL(node_comparer_test(new_node1, initial_node), true);
+ BOOST_CHECK_EQUAL(node_comparer_test(new_node2, initial_node), true);
+ BOOST_CHECK_EQUAL(node_comparer_test(new_node3, initial_node), true);
+ BOOST_CHECK_EQUAL(node_comparer_test(new_node4, initial_node), true);
+ BOOST_CHECK_EQUAL(node_comparer_test(new_node5, initial_node), false);
+ BOOST_CHECK_EQUAL(node_comparer_test(new_node6, initial_node), false);
+ BOOST_CHECK_EQUAL(node_comparer_test(new_node7, initial_node), true);
+}
+
+BOOST_AUTO_TEST_CASE_TEMPLATE(node_comparer_test4, T, test_types) {
+ typedef beach_line_node< point_2d<T> > bline_node;
+ node_comparer<bline_node> node_comparer_test;
+
+ bline_node initial_node(
+ make_site_event<T>(static_cast<T>(0), static_cast<T>(1), 0),
+ make_site_event<T>(static_cast<T>(1), static_cast<T>(0), 1));
+
+ bline_node new_node1(make_site_event<T>(static_cast<T>(1.5), static_cast<T>(-3), 2));
+ bline_node new_node2(make_site_event<T>(static_cast<T>(1.5), static_cast<T>(-1.8), 3));
+ bline_node new_node3(make_site_event<T>(static_cast<T>(1.5), static_cast<T>(-1.7), 4));
+ bline_node new_node4(make_site_event<T>(static_cast<T>(1.5), static_cast<T>(0.0), 4));
+ bline_node new_node5(make_site_event<T>(static_cast<T>(1.5), static_cast<T>(1.0), 4));
+ bline_node new_node6(make_site_event<T>(static_cast<T>(1.5), static_cast<T>(3.0), 4));
+ bline_node new_node7(make_site_event<T>(static_cast<T>(1.5), static_cast<T>(10.0), 4));
+
+ BOOST_CHECK_EQUAL(node_comparer_test(initial_node, new_node1), false);
+ BOOST_CHECK_EQUAL(node_comparer_test(initial_node, new_node2), false);
+ BOOST_CHECK_EQUAL(node_comparer_test(initial_node, new_node3), true);
+ BOOST_CHECK_EQUAL(node_comparer_test(initial_node, new_node4), true);
+ BOOST_CHECK_EQUAL(node_comparer_test(initial_node, new_node5), true);
+ BOOST_CHECK_EQUAL(node_comparer_test(initial_node, new_node6), true);
+ BOOST_CHECK_EQUAL(node_comparer_test(initial_node, new_node7), true);
+
+ BOOST_CHECK_EQUAL(node_comparer_test(new_node1, initial_node), true);
+ BOOST_CHECK_EQUAL(node_comparer_test(new_node2, initial_node), true);
+ BOOST_CHECK_EQUAL(node_comparer_test(new_node3, initial_node), false);
+ BOOST_CHECK_EQUAL(node_comparer_test(new_node4, initial_node), false);
+ BOOST_CHECK_EQUAL(node_comparer_test(new_node5, initial_node), false);
+ BOOST_CHECK_EQUAL(node_comparer_test(new_node6, initial_node), false);
+ BOOST_CHECK_EQUAL(node_comparer_test(new_node7, initial_node), false);
+}
+
+BOOST_AUTO_TEST_CASE_TEMPLATE(node_comparer_test5, T, test_types) {
+ typedef beach_line_node< point_2d<T> > bline_node;
+ node_comparer<bline_node> node_comparer_test;
+
+ bline_node initial_node(
+ make_site_event<T>(static_cast<T>(0), static_cast<T>(0), 0),
+ make_site_event<T>(static_cast<T>(1), static_cast<T>(2), 1));
+
+ bline_node new_node1(make_site_event<T>(static_cast<T>(1.5), static_cast<T>(-10), 2));
+ bline_node new_node2(make_site_event<T>(static_cast<T>(1.5), static_cast<T>(0), 3));
+ bline_node new_node3(make_site_event<T>(static_cast<T>(1.5), static_cast<T>(1.05), 4));
+ bline_node new_node4(make_site_event<T>(static_cast<T>(1.5), static_cast<T>(1.1), 4));
+ bline_node new_node5(make_site_event<T>(static_cast<T>(1.5), static_cast<T>(2), 4));
+ bline_node new_node6(make_site_event<T>(static_cast<T>(1.5), static_cast<T>(5), 4));
+ bline_node new_node7(make_site_event<T>(static_cast<T>(1.5), static_cast<T>(20), 4));
+
+
+ BOOST_CHECK_EQUAL(node_comparer_test(initial_node, new_node1), false);
+ BOOST_CHECK_EQUAL(node_comparer_test(initial_node, new_node2), false);
+ BOOST_CHECK_EQUAL(node_comparer_test(initial_node, new_node3), false);
+ BOOST_CHECK_EQUAL(node_comparer_test(initial_node, new_node4), true);
+ BOOST_CHECK_EQUAL(node_comparer_test(initial_node, new_node5), true);
+ BOOST_CHECK_EQUAL(node_comparer_test(initial_node, new_node6), true);
+ BOOST_CHECK_EQUAL(node_comparer_test(initial_node, new_node7), true);
+
+
+ BOOST_CHECK_EQUAL(node_comparer_test(new_node1, initial_node), true);
+ BOOST_CHECK_EQUAL(node_comparer_test(new_node2, initial_node), true);
+ BOOST_CHECK_EQUAL(node_comparer_test(new_node3, initial_node), true);
+ BOOST_CHECK_EQUAL(node_comparer_test(new_node4, initial_node), false);
+ BOOST_CHECK_EQUAL(node_comparer_test(new_node5, initial_node), false);
+ BOOST_CHECK_EQUAL(node_comparer_test(new_node6, initial_node), false);
+ BOOST_CHECK_EQUAL(node_comparer_test(new_node7, initial_node), false);
+}
+
+BOOST_AUTO_TEST_CASE_TEMPLATE(node_comparer_test6, T, test_types) {
+ typedef beach_line_node< point_2d<T> > bline_node;
+ node_comparer<bline_node> node_comparer_test;
+
+ bline_node initial_node(
+ make_site_event<T>(static_cast<T>(1), static_cast<T>(1), 0),
+ make_site_event<T>(static_cast<T>(0), static_cast<T>(0), 1));
+
+ bline_node new_node1(make_site_event<T>(static_cast<T>(1.5), static_cast<T>(-3), 2));
+ bline_node new_node2(make_site_event<T>(static_cast<T>(1.5), static_cast<T>(-1.75), 3));
+ bline_node new_node3(make_site_event<T>(static_cast<T>(1.5), static_cast<T>(0.0), 4));
+ bline_node new_node4(make_site_event<T>(static_cast<T>(1.5), static_cast<T>(0.28), 4));
+ bline_node new_node5(make_site_event<T>(static_cast<T>(1.5), static_cast<T>(2.7), 4));
+ bline_node new_node6(make_site_event<T>(static_cast<T>(1.5), static_cast<T>(2.8), 4));
+ bline_node new_node7(make_site_event<T>(static_cast<T>(1.5), static_cast<T>(5.0), 4));
+
+ BOOST_CHECK_EQUAL(node_comparer_test(initial_node, new_node1), false);
+ BOOST_CHECK_EQUAL(node_comparer_test(initial_node, new_node2), false);
+ BOOST_CHECK_EQUAL(node_comparer_test(initial_node, new_node3), false);
+ BOOST_CHECK_EQUAL(node_comparer_test(initial_node, new_node4), false);
+ BOOST_CHECK_EQUAL(node_comparer_test(initial_node, new_node5), false);
+ BOOST_CHECK_EQUAL(node_comparer_test(initial_node, new_node6), true);
+ BOOST_CHECK_EQUAL(node_comparer_test(initial_node, new_node7), true);
+
+ BOOST_CHECK_EQUAL(node_comparer_test(new_node1, initial_node), true);
+ BOOST_CHECK_EQUAL(node_comparer_test(new_node2, initial_node), true);
+ BOOST_CHECK_EQUAL(node_comparer_test(new_node3, initial_node), true);
+ BOOST_CHECK_EQUAL(node_comparer_test(new_node4, initial_node), true);
+ BOOST_CHECK_EQUAL(node_comparer_test(new_node5, initial_node), true);
+ BOOST_CHECK_EQUAL(node_comparer_test(new_node6, initial_node), false);
+ BOOST_CHECK_EQUAL(node_comparer_test(new_node7, initial_node), false);
+}
+
+BOOST_AUTO_TEST_CASE_TEMPLATE(node_comparer_test7, T, test_types) {
+ typedef beach_line_node< point_2d<T> > bline_node;
+ node_comparer<bline_node> node_comparer_test;
+
+ bline_node initial_node(
+ make_site_event<T>(static_cast<T>(0), static_cast<T>(0), 0),
+ make_site_event<T>(static_cast<T>(0), static_cast<T>(2), 1));
+
+ bline_node new_node1(make_site_event<T>(static_cast<T>(1), static_cast<T>(0), 2));
+ bline_node new_node2(make_site_event<T>(static_cast<T>(1), static_cast<T>(1), 3));
+ bline_node new_node3(make_site_event<T>(static_cast<T>(1), static_cast<T>(2), 4));
+ bline_node new_node4(make_site_event<T>(static_cast<T>(1), static_cast<T>(1.000001), 5));
+ bline_node new_node5(make_site_event<T>(static_cast<T>(1), static_cast<T>(0.999999), 6));
+
+ BOOST_CHECK_EQUAL(node_comparer_test(initial_node, new_node1), false);
+ BOOST_CHECK_EQUAL(node_comparer_test(initial_node, new_node2), false);
+ BOOST_CHECK_EQUAL(node_comparer_test(initial_node, new_node3), true);
+ BOOST_CHECK_EQUAL(node_comparer_test(initial_node, new_node4), true);
+ BOOST_CHECK_EQUAL(node_comparer_test(initial_node, new_node5), false);
+
+ BOOST_CHECK_EQUAL(node_comparer_test(new_node1, initial_node), true);
+ BOOST_CHECK_EQUAL(node_comparer_test(new_node2, initial_node), true);
+ BOOST_CHECK_EQUAL(node_comparer_test(new_node3, initial_node), false);
+ BOOST_CHECK_EQUAL(node_comparer_test(new_node4, initial_node), false);
+ BOOST_CHECK_EQUAL(node_comparer_test(new_node5, initial_node), true);
+}
+
+BOOST_AUTO_TEST_CASE_TEMPLATE(node_comparer_test8, T, test_types) {
+ typedef beach_line_node< point_2d<T> > bline_node;
+ node_comparer<bline_node> node_comparer_test;
+
+ bline_node initial_node(
+ make_site_event<T>(static_cast<T>(0), static_cast<T>(0), 0),
+ make_site_event<T>(static_cast<T>(1), static_cast<T>(1), 1));
+
+ bline_node new_node1(make_site_event<T>(static_cast<T>(1), static_cast<T>(0), 2));
+ bline_node new_node2(make_site_event<T>(static_cast<T>(1), static_cast<T>(1), 1));
+ bline_node new_node3(make_site_event<T>(static_cast<T>(1), static_cast<T>(2), 3));
+ bline_node new_node4(
+ make_site_event<T>(static_cast<T>(1), static_cast<T>(1), 1),
+ make_site_event<T>(static_cast<T>(0), static_cast<T>(0), 0));
+
+ BOOST_CHECK_EQUAL(node_comparer_test(initial_node, new_node1), false);
+ BOOST_CHECK_EQUAL(node_comparer_test(initial_node, new_node2), false);
+ BOOST_CHECK_EQUAL(node_comparer_test(initial_node, new_node3), true);
+ BOOST_CHECK_EQUAL(node_comparer_test(initial_node, new_node4), true);
+
+ BOOST_CHECK_EQUAL(node_comparer_test(new_node1, initial_node), true);
+ BOOST_CHECK_EQUAL(node_comparer_test(new_node2, initial_node), false);
+ BOOST_CHECK_EQUAL(node_comparer_test(new_node3, initial_node), false);
+ BOOST_CHECK_EQUAL(node_comparer_test(new_node4, initial_node), false);
}
\ No newline at end of file
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-06-22 19:08:36 EDT (Tue, 22 Jun 2010)
@@ -162,7 +162,7 @@
BOOST_CHECK_EQUAL(test_beach_line.get_voronoi_vertices().size(), 2);
}
-// Sites: {(x, y) | x = 0 .. 9, y = 0 .. 9}.
+// Sites: {(x, y) | x = 0 .. 3, y = 0 .. 3}.
BOOST_AUTO_TEST_CASE_TEMPLATE(voronoi_builder_test4, T, test_types) {
typedef typename voronoi_builder<T>::edge_type edge_type;
typedef typename voronoi_builder<T>::edge_iterator edge_iterator;
@@ -171,6 +171,48 @@
voronoi_builder<T> test_beach_line;
std::vector< point_2d<T> > points;
+ for (int i = 0; i < 3; i++)
+ for (int j = 0; j < 3; j++)
+ points.push_back(make_point_2d<T>(static_cast<T>(i),
+ static_cast<T>(j)));
+
+ test_beach_line.init(points);
+ test_beach_line.run_sweepline();
+}
+
+// Generate 10 random sites 1000 times.
+BOOST_AUTO_TEST_CASE_TEMPLATE(voronoi_builder_test4_1, T, test_types) {
+ typedef typename voronoi_builder<T>::edge_type edge_type;
+ typedef typename voronoi_builder<T>::edge_iterator edge_iterator;
+ typedef typename voronoi_builder<T>::voronoi_vertices_iterator
+ voronoi_vertices_iterator;
+
+ srand(static_cast<unsigned int>(time(NULL)));
+ voronoi_builder<T> test_beach_line;
+ std::vector< point_2d<T> > points;
+ for (int i = 0; i < 1000; i++) {
+ points.clear();
+ for (int j = 0; j < 10; j++)
+ points.push_back(make_point_2d<T>(static_cast<T>(rand() % 100),
+ static_cast<T>(rand() % 100)));
+ test_beach_line.init(points);
+ test_beach_line.run_sweepline();
+ test_beach_line.reset();
+ }
+
+ test_beach_line.init(points);
+ test_beach_line.run_sweepline();
+}
+
+// Sites: {(x, y) | x = 0 .. 9, y = 0 .. 9}.
+BOOST_AUTO_TEST_CASE_TEMPLATE(voronoi_builder_test5, T, test_types) {
+ typedef typename voronoi_builder<T>::edge_type edge_type;
+ typedef typename voronoi_builder<T>::edge_iterator edge_iterator;
+ typedef typename voronoi_builder<T>::voronoi_vertices_iterator
+ voronoi_vertices_iterator;
+
+ voronoi_builder<T> test_beach_line;
+ std::vector< point_2d<T> > points;
for (int i = 0; i < 10; i++)
for (int j = 0; j < 10; j++)
points.push_back(make_point_2d<T>(static_cast<T>(i),
@@ -180,8 +222,8 @@
test_beach_line.run_sweepline();
}
-// Generate 100 random sites.
-BOOST_AUTO_TEST_CASE_TEMPLATE(voronoi_builder_test4_1, T, test_types) {
+// Generate 100 random sites 100 times.
+BOOST_AUTO_TEST_CASE_TEMPLATE(voronoi_builder_test5_1, T, test_types) {
typedef typename voronoi_builder<T>::edge_type edge_type;
typedef typename voronoi_builder<T>::edge_iterator edge_iterator;
typedef typename voronoi_builder<T>::voronoi_vertices_iterator
@@ -190,16 +232,22 @@
srand(static_cast<unsigned int>(time(NULL)));
voronoi_builder<T> test_beach_line;
std::vector< point_2d<T> > points;
- for (int i = 0; i < 100; i++)
- points.push_back(make_point_2d<T>(static_cast<T>(rand() % 100),
- static_cast<T>(rand() % 100)));
+ for (int i = 0; i < 100; i++) {
+ points.clear();
+ for (int j = 0; j < 100; j++)
+ points.push_back(make_point_2d<T>(static_cast<T>(rand() % 100),
+ static_cast<T>(rand() % 100)));
+ test_beach_line.init(points);
+ test_beach_line.run_sweepline();
+ test_beach_line.reset();
+ }
test_beach_line.init(points);
test_beach_line.run_sweepline();
}
// Sites: {(x, y) | x = 0 .. 33, y = 0 .. 33}.
-BOOST_AUTO_TEST_CASE_TEMPLATE(voronoi_builder_test5, T, test_types) {
+BOOST_AUTO_TEST_CASE_TEMPLATE(voronoi_builder_test6, T, test_types) {
typedef typename voronoi_builder<T>::edge_type edge_type;
typedef typename voronoi_builder<T>::edge_iterator edge_iterator;
typedef typename voronoi_builder<T>::voronoi_vertices_iterator
@@ -216,8 +264,8 @@
test_beach_line.run_sweepline();
}
-// Generate 1000 random sites.
-BOOST_AUTO_TEST_CASE_TEMPLATE(voronoi_builder_test5_1, T, test_types) {
+// Generate 1000 random sites 10 times.
+BOOST_AUTO_TEST_CASE_TEMPLATE(voronoi_builder_test6_1, T, test_types) {
typedef typename voronoi_builder<T>::edge_type edge_type;
typedef typename voronoi_builder<T>::edge_iterator edge_iterator;
typedef typename voronoi_builder<T>::voronoi_vertices_iterator
@@ -226,16 +274,22 @@
srand(static_cast<unsigned int>(time(NULL)));
voronoi_builder<T> test_beach_line;
std::vector< point_2d<T> > points;
- for (int i = 0; i < 1000; i++)
- points.push_back(make_point_2d<T>(static_cast<T>(rand() % 100),
- static_cast<T>(rand() % 100)));
+ for (int i = 0; i < 10; i++) {
+ points.clear();
+ for (int j = 0; j < 1000; j++)
+ points.push_back(make_point_2d<T>(static_cast<T>(rand() % 100),
+ static_cast<T>(rand() % 100)));
+ test_beach_line.init(points);
+ test_beach_line.run_sweepline();
+ test_beach_line.reset();
+ }
test_beach_line.init(points);
test_beach_line.run_sweepline();
}
// Sites: {(x, y) | x = 0 .. 100, y = 0 .. 100}.
-BOOST_AUTO_TEST_CASE_TEMPLATE(voronoi_builder_test6, T, test_types) {
+BOOST_AUTO_TEST_CASE_TEMPLATE(voronoi_builder_test7, T, test_types) {
typedef typename voronoi_builder<T>::edge_type edge_type;
typedef typename voronoi_builder<T>::edge_iterator edge_iterator;
typedef typename voronoi_builder<T>::voronoi_vertices_iterator
@@ -253,7 +307,7 @@
}
// Generate 10000 random sites.
-BOOST_AUTO_TEST_CASE_TEMPLATE(voronoi_builder_test6_1, T, test_types) {
+BOOST_AUTO_TEST_CASE_TEMPLATE(voronoi_builder_test7_1, T, test_types) {
typedef typename voronoi_builder<T>::edge_type edge_type;
typedef typename voronoi_builder<T>::edge_iterator edge_iterator;
typedef typename voronoi_builder<T>::voronoi_vertices_iterator
@@ -271,7 +325,7 @@
}
//// Sites: {(x, y) | x = 0 .. 333, y = 0 .. 333}.
-//BOOST_AUTO_TEST_CASE_TEMPLATE(voronoi_builder_test7, T, test_types) {
+//BOOST_AUTO_TEST_CASE_TEMPLATE(voronoi_builder_test8, T, test_types) {
// typedef typename voronoi_builder<T>::edge_type edge_type;
// typedef typename voronoi_builder<T>::edge_iterator edge_iterator;
// typedef typename voronoi_builder<T>::voronoi_vertices_iterator
@@ -280,8 +334,8 @@
// srand(static_cast<unsigned int>(time(NULL)));
// voronoi_builder<T> test_beach_line;
// std::vector< point_2d<T> > points;
-// for (int i = 0; i < 333; i++)
-// for (int j = 0; j < 333; j++)
+// for (int i = 0; i < 270; i++)
+// for (int j = 0; j < 270; j++)
// points.push_back(make_point_2d<T>(static_cast<T>(rand() % 1000),
// static_cast<T>(rand() % 1000)));
//