Subject: [Boost-commit] svn:boost r63209 - in sandbox/SOC/2010/sweepline: boost/sweepline boost/sweepline/detail libs/sweepline/test
From: sydorchuk.andriy_at_[hidden]
Date: 2010-06-21 17:49:50
Author: asydorchuk
Date: 2010-06-21 17:49:48 EDT (Mon, 21 Jun 2010)
New Revision: 63209
URL: http://svn.boost.org/trac/boost/changeset/63209
Log:
Added larger voronoi builder unit tests.
Fixed circle events queue comparison.
Changed circle events structure.
Text files modified:
sandbox/SOC/2010/sweepline/boost/sweepline/detail/voronoi_formation.hpp | 81 +++++++++++++++++----
sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_builder.hpp | 45 +++++------
sandbox/SOC/2010/sweepline/libs/sweepline/test/event_queue_test.cpp | 13 ++
sandbox/SOC/2010/sweepline/libs/sweepline/test/event_types_test.cpp | 11 ++
sandbox/SOC/2010/sweepline/libs/sweepline/test/node_comparer_test.cpp | 2
sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_builder_test.cpp | 152 ++++++++++++++++++++++++++++++++++++---
6 files changed, 246 insertions(+), 58 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-21 17:49:48 EDT (Mon, 21 Jun 2010)
@@ -196,10 +196,18 @@
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.get_sqr_radius() &&
+ sites_[0] == c_event.sites_[0] &&
+ sites_[1] == c_event.sites_[1] &&
+ sites_[2] == c_event.sites_[2];
}
bool operator==(const circle_event &c_event) const {
+ if (sites_[0] != c_event.sites_[0] ||
+ sites_[1] != c_event.sites_[1] ||
+ sites_[2] != c_event.sites_[2])
+ return false;
+
if (center_.y() != c_event.y())
return false;
@@ -234,30 +242,58 @@
if (sqr_r2 <= sqr_r1)
return false;
- if (sqr_dif_x >= sum_r_sqr)
+ if (sqr_dif_x > sum_r_sqr)
return false;
- if (value_left == value_right)
- return y1 < y2;
- else
+ if (value_left != value_right)
return value_left > value_right;
+
+ if (y1 != y2)
+ return y1 < y2;
+
+ if (sites_[0] != c_event.sites_[0])
+ return sites_[0] < c_event.sites_[0];
+
+ if (sites_[1] != c_event.sites_[1])
+ return sites_[1] < c_event.sites_[1];
+
+ return sites_[2] < c_event.sites_[2];
}
else if (x1 < x2) {
if (sqr_r1 <= sqr_r2)
return true;
- if (sqr_dif_x >= sum_r_sqr)
+ if (sqr_dif_x > sum_r_sqr)
return true;
- if (value_left == value_right)
- return y1 < y2;
- else
+ if (value_left != value_right)
return value_left < value_right;
+
+ if (y1 != y2)
+ return y1 < y2;
+
+ if (sites_[0] != c_event.sites_[0])
+ return sites_[0] < c_event.sites_[0];
+
+ if (sites_[1] != c_event.sites_[1])
+ return sites_[1] < c_event.sites_[1];
+
+ return sites_[2] < c_event.sites_[2];
}
else {
if (sqr_r1 != sqr_r2)
return sqr_r1 < sqr_r2;
- return y1 < y2;
+
+ if (y1 != y2)
+ return y1 < y2;
+
+ if (sites_[0] != c_event.sites_[0])
+ return sites_[0] < c_event.sites_[0];
+
+ if (sites_[1] != c_event.sites_[1])
+ return sites_[1] < c_event.sites_[1];
+
+ return sites_[2] < c_event.sites_[2];
}
}
@@ -309,13 +345,27 @@
bisector_node_ = iterator;
}
+ void set_sites(const site_event<T> site1,
+ const site_event<T> site2,
+ const site_event<T> site3) {
+ sites_[0] = site1;
+ sites_[1] = site2;
+ sites_[2] = site3;
+ }
+
const beach_line_iterator &get_bisector() const {
return bisector_node_;
}
+
+ const site_event<T>* get_sites() {
+ return sites;
+ }
+
private:
point_2d<T> center_;
T sqr_radius_;
beach_line_iterator bisector_node_;
+ site_event<T> sites_[3];
};
template <typename T>
@@ -538,22 +588,21 @@
return true;
}
- circle_event_type &top() {
+ circle_event_type top() {
remove_not_active_events();
return circle_events_.top();
}
void pop() {
- remove_not_active_events();
circle_events_.pop();
}
- void push(const circle_event_type &circle_event) {
- circle_events_.push(circle_event);
+ void push(const circle_event_type &c_event) {
+ circle_events_.push(c_event);
}
- void deactivate_event(const circle_event_type &circle_event) {
- deactivated_events_.push(circle_event);
+ void deactivate_event(const circle_event_type &c_event) {
+ deactivated_events_.push(c_event);
}
private:
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-21 17:49:48 EDT (Mon, 21 Jun 2010)
@@ -97,15 +97,17 @@
process_site_event(*site_events_iterator_);
site_events_iterator_++;
} else if (site_events_iterator_ == site_events_.end()) {
- process_circle_event(circle_events_.top());
+ circle_event<T> c_event = circle_events_.top();
circle_events_.pop();
+ process_circle_event(c_event);
} else {
if (circle_events_.top().compare(*site_events_iterator_) >= 0) {
process_site_event(*site_events_iterator_);
site_events_iterator_++;
} else {
- process_circle_event(circle_events_.top());
+ circle_event<T> c_event = circle_events_.top();
circle_events_.pop();
+ process_circle_event(c_event);
}
}
}
@@ -208,25 +210,24 @@
new_node_it);
} else {
site_arc = it->first.get_left_site();
-
- // Insert new arc into the sweepline.
- beach_line_iterator new_node_it = insert_new_arc(site_arc, site_event);
-
const site_event_type &site2 = it->first.get_left_site();
const site_event_type &site3 = it->first.get_right_site();
it--;
- const site_event_type &site1 = it->first.get_right_site();
-
+ const site_event_type &site1 = it->first.get_left_site();
+
// Remove candidate circle from the event queue.
deactivate_circle_event(site1, site2, site3);
+ // Insert new arc into the sweepline.
+ beach_line_iterator new_node_it = insert_new_arc(site_arc, site_event);
+
// Add candidate circles to the event queue.
new_node_it--;
activate_circle_event(site1, site2, site_event, new_node_it);
new_node_it++;
new_node_it++;
activate_circle_event(site_event, site2, site3, new_node_it);
- }
+ }
}
// Doesn't use special comparison function as it works fine only for
@@ -258,8 +259,9 @@
// (B, C) bisector and change (A, B) bisector to the (A, C). That's
// why we use const_cast there and take all the responsibility that
// map data structure keeps correct ordering.
- const_cast<Key &>(it_first->first).set_right_site(it_last->first.get_right_site());
- edge_type *edge = output_.insert_new_edge(site1, site2, site3, circle_event, bisector1.edge, bisector2.edge);
+ const_cast<Key &>(it_first->first).set_right_site(site3);
+ edge_type *edge = output_.insert_new_edge(site1, site2, site3, circle_event,
+ bisector1.edge, bisector2.edge);
const_cast<Value &>(it_first->second).change_edge(edge);
beach_line_.erase(it_last);
it_last = it_first;
@@ -269,13 +271,8 @@
if (it_first != beach_line_.begin()) {
it_first--;
const site_event_type &site_l1 = it_first->first.get_left_site();
- deactivate_circle_event(site_l1, site1, site3);
- if (it_first != beach_line_.begin()) {
- it_first--;
- const site_event_type &site_l2 = it_first->first.get_left_site();
- it_first++;
- activate_circle_event(site_l2, site_l1, site1, it_first);
- }
+ deactivate_circle_event(site_l1, site1, site2);
+ activate_circle_event(site_l1, site1, site3, it_last);
}
// Check the new triplets formed by the neighboring arcs
@@ -283,13 +280,10 @@
it_last++;
if (it_last != beach_line_.end()) {
const site_event_type &site_r1 = it_last->first.get_right_site();
- deactivate_circle_event(site1, site3, site_r1);
- it_last++;
- if (it_last != beach_line_.end()) {
- const site_event_type &site_r2 = it_last->first.get_right_site();
- activate_circle_event(site3, site_r1, site_r2, it_last);
- }
- }
+ deactivate_circle_event(site2, site3, site_r1);
+ activate_circle_event(site1, site3, site_r1, it_last);
+ }
+
}
// Insert new arc below site arc into the beach line.
@@ -330,6 +324,7 @@
(c_y-site1.y())*(c_y-site1.y());
// Create new circle event;
c_event = make_circle_event(c_x, c_y, sqr_radius);
+ c_event.set_sites(site1, site2, site3);
return true;
}
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 2010-06-21 17:49:48 EDT (Mon, 21 Jun 2010)
@@ -8,7 +8,7 @@
// See http://www.boost.org for updates, documentation, and revision history.
#include "test_type_list.hpp"
-#include <boost/sweepline/detail/voronoi_formation.hpp>
+#include "boost/sweepline/detail/voronoi_formation.hpp"
using namespace boost::sweepline::detail;
#define BOOST_TEST_MODULE event_queue_test
@@ -41,17 +41,24 @@
BOOST_AUTO_TEST_CASE_TEMPLATE(event_queue_test2, T, test_types) {
circle_events_queue< point_2d<T> > event_q;
+ site_event<T> temp_site = make_site_event(static_cast<T>(0),
+ static_cast<T>(0),
+ 0);
for (int i = 0; i < 10; i++) {
T x = static_cast<T>(10-i);
T y = static_cast<T>(10-i);
- event_q.push(make_circle_event(x, y, static_cast<T>(0)));
+ circle_event<T> &c = make_circle_event(x, y, static_cast<T>(0));
+ c.set_sites(temp_site, temp_site, temp_site);
+ event_q.push(c);
}
for (int i = 0; i < 5; i++) {
T x = static_cast<T>(10-2*i-1);
T y = static_cast<T>(10-2*i-1);
- event_q.deactivate_event(make_circle_event(x, y, static_cast<T>(0)));
+ circle_event<T> &c = make_circle_event(x, y, static_cast<T>(0));
+ c.set_sites(temp_site, temp_site, temp_site);
+ event_q.deactivate_event(c);
}
for (int i = 0; i < 5; i++) {
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-06-21 17:49:48 EDT (Mon, 21 Jun 2010)
@@ -8,7 +8,7 @@
// See http://www.boost.org for updates, documentation, and revision history.
#include "test_type_list.hpp"
-#include <boost/sweepline/detail/voronoi_formation.hpp>
+#include "boost/sweepline/detail/voronoi_formation.hpp"
using namespace boost::sweepline::detail;
#define BOOST_TEST_MODULE event_types_test
@@ -69,6 +69,10 @@
circle_event<T> circle1 = make_circle_event<T>(static_cast<T>(1),
static_cast<T>(2),
static_cast<T>(4));
+ site_event<T> temp_site = make_site_event<T>(static_cast<T>(0),
+ static_cast<T>(0),
+ 0);
+ circle1.set_sites(temp_site, temp_site, temp_site);
circle_event<T> circle2;
BOOST_CHECK_EQUAL(circle1.x(), static_cast<T>(1));
@@ -78,18 +82,21 @@
circle2 = make_circle_event<T>(static_cast<T>(1),
static_cast<T>(2),
static_cast<T>(4));
+ circle2.set_sites(temp_site, temp_site, temp_site);
bool arr1[] = { false, false, true, true, true, false };
EVENT_TYPES_CHECK_COMPARISON(circle1, circle2, arr1);
circle2 = make_circle_event<T>(static_cast<T>(1),
static_cast<T>(3),
static_cast<T>(4));
+ circle2.set_sites(temp_site, temp_site, temp_site);
bool arr2[] = { true, false, true, false, false, true };
EVENT_TYPES_CHECK_COMPARISON(circle1, circle2, arr2);
circle2 = make_circle_event<T>(static_cast<T>(1),
static_cast<T>(2),
static_cast<T>(5));
+ circle2.set_sites(temp_site, temp_site, temp_site);
bool arr3[] = { true, false, true, false, false, true };
EVENT_TYPES_CHECK_COMPARISON(circle1, circle2, arr3);
@@ -97,12 +104,14 @@
circle2 = make_circle_event<T>(static_cast<T>(0),
static_cast<T>(2),
static_cast<T>(4));
+ circle2.set_sites(temp_site, temp_site, temp_site);
bool arr4[] = { false, true, false, true, false, true };
EVENT_TYPES_CHECK_COMPARISON(circle1, circle2, arr4);
circle2 = make_circle_event<T>(static_cast<T>(0),
static_cast<T>(0),
static_cast<T>(10));
+ circle2.set_sites(temp_site, temp_site, temp_site);
bool arr5[] = { true, false, true, false, false, true };
EVENT_TYPES_CHECK_COMPARISON(circle1, circle2, arr5);
}
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-21 17:49:48 EDT (Mon, 21 Jun 2010)
@@ -8,7 +8,7 @@
// See http://www.boost.org for updates, documentation, and revision history.
#include "test_type_list.hpp"
-#include <boost/sweepline/detail/voronoi_formation.hpp>
+#include "boost/sweepline/detail/voronoi_formation.hpp"
using namespace boost::sweepline::detail;
#define BOOST_TEST_MODULE node_comparer_test
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-21 17:49:48 EDT (Mon, 21 Jun 2010)
@@ -7,13 +7,17 @@
// See http://www.boost.org for updates, documentation, and revision history.
+#include <stdlib.h>
+#include <time.h>
+
#include "test_type_list.hpp"
-#include <boost/sweepline/voronoi_builder.hpp>
+#include "boost/sweepline/voronoi_builder.hpp"
using namespace boost::sweepline;
#define BOOST_TEST_MODULE voronoi_builder_test
#include <boost/test/test_case_template.hpp>
+// Sites: (0, 0), (0, 4), (2, 1).
BOOST_AUTO_TEST_CASE_TEMPLATE(voronoi_builder_test1, T, test_types) {
typedef typename voronoi_builder<T>::edge_type edge_type;
typedef typename voronoi_builder<T>::edge_iterator edge_iterator;
@@ -76,6 +80,7 @@
}
+// Sites: (0, 1), (2, 0), (2, 4).
BOOST_AUTO_TEST_CASE_TEMPLATE(voronoi_builder_test2, T, test_types) {
typedef typename voronoi_builder<T>::edge_type edge_type;
typedef typename voronoi_builder<T>::edge_iterator edge_iterator;
@@ -137,6 +142,7 @@
BOOST_CHECK_EQUAL(edge3_2->next == edge1_1, true);
}
+// Sites: (0, 0), (0, 1), (1, 0), (1, 1).
BOOST_AUTO_TEST_CASE_TEMPLATE(voronoi_builder_test3, T, test_types) {
typedef typename voronoi_builder<T>::edge_type edge_type;
typedef typename voronoi_builder<T>::edge_iterator edge_iterator;
@@ -144,19 +150,141 @@
voronoi_vertices_iterator;
voronoi_builder<T> test_beach_line;
- point_2d<T> point1 = make_point_2d<T>(0, 0);
- point_2d<T> point2 = make_point_2d<T>(0, 1);
- point_2d<T> point3 = make_point_2d<T>(1, 0);
- point_2d<T> point4 = make_point_2d<T>(1, 1);
-
std::vector< point_2d<T> > points;
- points.push_back(point1);
- points.push_back(point2);
- points.push_back(point3);
- points.push_back(point4);
+ points.push_back(make_point_2d<T>(0, 0));
+ points.push_back(make_point_2d<T>(0, 1));
+ points.push_back(make_point_2d<T>(1, 0));
+ points.push_back(make_point_2d<T>(1, 1));
test_beach_line.init(points);
test_beach_line.run_sweepline();
BOOST_CHECK_EQUAL(test_beach_line.get_cell_records().size(), 4);
- BOOST_CHECK_EQUAL(test_beach_line.get_voronoi_vertices().size(), 1);
-}
\ No newline at end of file
+ BOOST_CHECK_EQUAL(test_beach_line.get_voronoi_vertices().size(), 2);
+}
+
+// Sites: {(x, y) | x = 0 .. 9, y = 0 .. 9}.
+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;
+ 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),
+ static_cast<T>(j)));
+
+ test_beach_line.init(points);
+ test_beach_line.run_sweepline();
+}
+
+// Generate 100 random sites.
+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 < 100; i++)
+ 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();
+}
+
+// Sites: {(x, y) | x = 0 .. 33, y = 0 .. 33}.
+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 < 33; i++)
+ for (int j = 0; j < 33; 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 1000 random sites.
+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
+ 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.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();
+}
+
+// Sites: {(x, y) | x = 0 .. 100, y = 0 .. 100}.
+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
+ voronoi_vertices_iterator;
+
+ voronoi_builder<T> test_beach_line;
+ std::vector< point_2d<T> > points;
+ for (int i = 0; i < 100; i++)
+ for (int j = 0; j < 100; 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 10000 random sites.
+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
+ 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 < 10000; i++)
+ points.push_back(make_point_2d<T>(static_cast<T>(rand() % 1000),
+ static_cast<T>(rand() % 1000)));
+
+ test_beach_line.init(points);
+ test_beach_line.run_sweepline();
+}
+
+//// Sites: {(x, y) | x = 0 .. 333, y = 0 .. 333}.
+//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
+// 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 < 333; i++)
+// for (int j = 0; j < 333; j++)
+// points.push_back(make_point_2d<T>(static_cast<T>(rand() % 1000),
+// static_cast<T>(rand() % 1000)));
+//
+// test_beach_line.init(points);
+// test_beach_line.run_sweepline();
+//}
\ No newline at end of file