Subject: [Boost-commit] svn:boost r64160 - in sandbox/SOC/2010/sweepline: boost/sweepline boost/sweepline/detail libs/sweepline/example libs/sweepline/test
From: sydorchuk.andriy_at_[hidden]
Date: 2010-07-19 11:18:14
Author: asydorchuk
Date: 2010-07-19 11:18:12 EDT (Mon, 19 Jul 2010)
New Revision: 64160
URL: http://svn.boost.org/trac/boost/changeset/64160
Log:
Fixed algorithm to work correctly for large input data sets.
Changed circle events data structure.
Added visual examples and test cases.
Added:
sandbox/SOC/2010/sweepline/libs/sweepline/example/example_013.txt (contents, props changed)
sandbox/SOC/2010/sweepline/libs/sweepline/example/example_014.txt (contents, props changed)
sandbox/SOC/2010/sweepline/libs/sweepline/example/example_015.txt (contents, props changed)
sandbox/SOC/2010/sweepline/libs/sweepline/example/example_016_random.txt (contents, props changed)
sandbox/SOC/2010/sweepline/libs/sweepline/example/example_017_random.txt (contents, props changed)
sandbox/SOC/2010/sweepline/libs/sweepline/example/example_018_random.txt (contents, props changed)
sandbox/SOC/2010/sweepline/libs/sweepline/example/example_019_random.txt (contents, props changed)
Text files modified:
sandbox/SOC/2010/sweepline/boost/sweepline/detail/voronoi_formation.hpp | 165 +++++++++++------
sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_builder.hpp | 117 ++++++++----
sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_output.hpp | 4
sandbox/SOC/2010/sweepline/libs/sweepline/example/voronoi_visualizer.cpp | 4
sandbox/SOC/2010/sweepline/libs/sweepline/test/event_queue_test.cpp | 14 -
sandbox/SOC/2010/sweepline/libs/sweepline/test/event_types_test.cpp | 12
sandbox/SOC/2010/sweepline/libs/sweepline/test/node_comparer_test.cpp | 76 +++----
sandbox/SOC/2010/sweepline/libs/sweepline/test/test_type_list.hpp | 2
sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_builder_test.cpp | 357 ++++++++++++++++++++++++---------------
9 files changed, 451 insertions(+), 300 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-19 11:18:12 EDT (Mon, 19 Jul 2010)
@@ -27,7 +27,7 @@
struct beach_line_node;
template <typename T>
- struct half_edge;
+ struct beach_line_node_data;
template <typename BeachLineNode>
struct node_comparer;
@@ -120,22 +120,23 @@
typedef T coordinate_type;
typedef point_2d<T> Point2D;
typedef beach_line_node<coordinate_type> Key;
- typedef half_edge<coordinate_type>* Value;
+ typedef beach_line_node_data<coordinate_type> Value;
typedef node_comparer<Key> NodeComparer;
typedef typename std::map< Key, Value, NodeComparer >::iterator beach_line_iterator;
- circle_event() {}
+ circle_event() : is_active_(true) {}
circle_event(coordinate_type c_x, coordinate_type c_y, coordinate_type sqr_r) :
- center_(c_x, c_y), sqr_radius_(sqr_r) {}
+ center_(c_x, c_y), sqr_radius_(sqr_r), is_active_(true) {}
circle_event(const Point2D ¢er, coordinate_type sqr_r) :
- center_(center), sqr_radius_(sqr_r) {}
+ center_(center), sqr_radius_(sqr_r), is_active_(true) {}
circle_event(const circle_event& c_event) {
center_ = c_event.center_;
sqr_radius_ = c_event.sqr_radius_;
bisector_node_ = c_event.bisector_node_;
+ is_active_ = c_event.is_active_;
for (int i = 0; i < 3; i++)
sites_[i] = c_event.sites_[i];
}
@@ -144,6 +145,7 @@
center_ = c_event.center_;
sqr_radius_ = c_event.sqr_radius_;
bisector_node_ = c_event.bisector_node_;
+ is_active_ = c_event.is_active_;
for (int i = 0; i < 3; i++)
sites_[i] = c_event.sites_[i];
}
@@ -157,20 +159,22 @@
}
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])
+ if (center_.y() != c_event.y())
return false;
- if (center_.y() != c_event.y())
+ if (center_.x() > c_event.x() && sqr_radius_ > c_event.get_sqr_radius() ||
+ center_.x() < c_event.x() && sqr_radius_ < c_event.get_sqr_radius())
+ return false;
+
+ coordinate_type sqr_dif_x = (center_.x() - c_event.x()) * (center_.x() - c_event.x());
+ coordinate_type sum_r_sqr = sqr_radius_ + c_event.get_sqr_radius();
+
+ if (sqr_dif_x > sum_r_sqr)
return false;
- coordinate_type sqr_dif_x = (center_.x() - c_event.x()) *
- (center_.x() - c_event.x());
- coordinate_type sum_r_sqr = sqr_radius_ + c_event.sqr_radius_;
coordinate_type value_left = (sum_r_sqr - sqr_dif_x) * (sum_r_sqr - sqr_dif_x);
coordinate_type value_right = static_cast<coordinate_type>(4) * sqr_radius_ *
- c_event.sqr_radius_;
+ c_event.get_sqr_radius();
return value_left == value_right;
}
@@ -299,27 +303,31 @@
bisector_node_ = iterator;
}
- void set_sites(const site_event<coordinate_type> &site1,
- const site_event<coordinate_type> &site2,
- const site_event<coordinate_type> &site3) {
+ void set_sites(int site1, int site2, int site3) {
sites_[0] = site1;
sites_[1] = site2;
sites_[2] = site3;
}
+ void deactivate() {
+ is_active_ = false;
+ }
+
const beach_line_iterator &get_bisector() const {
return bisector_node_;
}
- const site_event<coordinate_type>* get_sites() const {
- return sites_;
+ bool is_active() const {
+ return is_active_;
}
+
private:
Point2D center_;
coordinate_type sqr_radius_;
beach_line_iterator bisector_node_;
- site_event<coordinate_type> sites_[3];
+ int sites_[3];
+ bool is_active_;
};
template <typename T>
@@ -343,55 +351,55 @@
typedef T coordinate_type;
typedef point_2d<T> Point2D;
typedef circle_event<T> circle_event_type;
+ typedef typename std::list<circle_event_type>::iterator circle_event_type_it;
circle_events_queue() {}
void reset() {
while (!circle_events_.empty())
circle_events_.pop();
- while (!deactivated_events_.empty())
- deactivated_events_.pop();
+ circle_events_list_.clear();
}
bool empty() {
remove_not_active_events();
- if (!circle_events_.empty())
- return false;
- return true;
+ return circle_events_.empty();
}
const circle_event_type &top() {
remove_not_active_events();
- return circle_events_.top();
+ return (*circle_events_.top());
}
void pop() {
+ circle_event_type_it temp_it = circle_events_.top();
circle_events_.pop();
+ circle_events_list_.erase(temp_it);
}
- void push(const circle_event_type &c_event) {
- circle_events_.push(c_event);
- }
-
- void deactivate_event(const circle_event_type &c_event) {
- deactivated_events_.push(c_event);
+ circle_event_type_it push(const circle_event_type &c_event) {
+ circle_events_list_.push_front(c_event);
+ circle_events_.push(circle_events_list_.begin());
+ return circle_events_list_.begin();
}
private:
- void remove_not_active_events() {
- while (!circle_events_.empty() && !deactivated_events_.empty() &&
- circle_events_.top().equals(deactivated_events_.top())) {
- circle_events_.pop();
- deactivated_events_.pop();
+ struct comparison {
+ bool operator() (const circle_event_type_it &node1,
+ const circle_event_type_it &node2) const {
+ return (*node1) > (*node2);
}
+ };
+
+ void remove_not_active_events() {
+ while (!circle_events_.empty() && !circle_events_.top()->is_active())
+ pop();
}
- std::priority_queue< circle_event_type,
- std::vector<circle_event_type>,
- std::greater<circle_event_type> > circle_events_;
- std::priority_queue< circle_event_type,
- std::vector<circle_event_type>,
- std::greater<circle_event_type> > deactivated_events_;
+ std::priority_queue< circle_event_type_it,
+ std::vector<circle_event_type_it>,
+ comparison > circle_events_;
+ std::list<circle_event_type> circle_events_list_;
//Disallow copy constructor and operator=
circle_events_queue(const circle_events_queue&);
@@ -453,11 +461,6 @@
right_site_ = site;
}
- // Returns x coordinate of the rightmost site.
- coordinate_type get_sweepline_coord() const {
- return (std::max)(left_site_.x(), right_site_.x());
- }
-
// Returns the rightmost site.
const site_event_type& get_new_site() const {
if (left_site_.x() > right_site_.x())
@@ -475,16 +478,34 @@
// 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
+ // (x2-x0)*(x1-x0)*(x1-x2) + (x2-x0)*(y*-y1)^2 < (x1-x0)*(y*-y2)^2.
bool less(const site_event_type &new_site) const {
- coordinate_type sweepline_coord = new_site.x();
- coordinate_type new_node_coord = new_site.y();
- coordinate_type a1 = left_site_.x() - sweepline_coord;
- coordinate_type a2 = right_site_.x() - sweepline_coord;
- coordinate_type b1 = new_node_coord - left_site_.y();
- coordinate_type b2 = new_node_coord - right_site_.y();
- coordinate_type c = left_site_.x() - right_site_.x();
- return a1 * a2 * c + a2 * b1 * b1 < a1 * b2 * b2;
+ 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)
+ return true;
+ if (l_expr > 0 && r_expr < 0)
+ 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;
+
+ /*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());
+ b1 = static_cast<int>(new_site.y() - left_site.y());
+ b2 = static_cast<int>(new_site.y() - right_site.y());
+ c = static_cast<int>(left_site.x() - right_site.x());
+ return a1 * a2 * c + a1 * b2 * b2 < a2 * b1 * b1;*/
}
private:
@@ -492,6 +513,33 @@
site_event_type right_site_;
};
+ template <typename T>
+ struct half_edge;
+
+ // Represents edge data sturcture (bisector segment), which is
+ // associated with beach line node key in the binary search tree.
+ template <typename T>
+ struct beach_line_node_data {
+ half_edge<T> *edge;
+ typename circle_events_queue<T>::circle_event_type_it circle_event_it;
+ bool contains_circle_event;
+
+ explicit beach_line_node_data(half_edge<T> *new_edge) :
+ edge(new_edge),
+ contains_circle_event(false) {}
+
+ void activate_circle_event(typename circle_events_queue<T>::circle_event_type_it it) {
+ circle_event_it = it;
+ contains_circle_event = true;
+ }
+
+ void deactivate_circle_event() {
+ if (contains_circle_event)
+ circle_event_it->deactivate();
+ contains_circle_event = false;
+ }
+ };
+
template <typename BeachLineNode>
struct node_comparer {
public:
@@ -506,8 +554,8 @@
bool operator() (const BeachLineNode &node1,
const BeachLineNode &node2) const {
// Get x coordinate of the righmost site from both nodes.
- coordinate_type node1_line = node1.get_sweepline_coord();
- coordinate_type node2_line = node2.get_sweepline_coord();
+ coordinate_type node1_line = node1.get_new_site().x();
+ coordinate_type node2_line = node2.get_new_site().x();
if (node1_line < node2_line) {
coordinate_type left_site_x = node1.get_left_site().x();
@@ -632,6 +680,7 @@
template <typename T>
class voronoi_output {
public:
+
typedef T coordinate_type;
typedef point_2d<T> Point2D;
typedef typename detail::site_event<coordinate_type> site_event_type;
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-19 11:18:12 EDT (Mon, 19 Jul 2010)
@@ -20,9 +20,10 @@
class voronoi_builder {
public:
typedef T coordinate_type;
- typedef point_2d<T> Point2D;
+ typedef point_2d<coordinate_type> Point2D;
typedef detail::voronoi_output<coordinate_type> Output;
typedef typename Output::edge_type edge_type;
+ typedef voronoi_output_clipped<coordinate_type> ClippedOutput;
voronoi_builder() {
// Set sites iterator.
@@ -44,7 +45,9 @@
int sz = sites.size();
for (int i = 0; i < sz; i++) {
if (!i || sites[i] != sites[i-1]) {
- site_events_.push_back(detail::make_site_event(sites[i], site_event_index));
+ site_events_.push_back(detail::make_site_event(
+ static_cast<coordinate_type>(sites[i].x()),
+ static_cast<coordinate_type>(sites[i].y()), site_event_index));
site_event_index++;
}
}
@@ -97,7 +100,7 @@
else if (site_events_iterator_ == site_events_.end())
process_circle_event();
else {
- if (circle_events_.top().compare(*site_events_iterator_) >= 0)
+ if (circle_events_.top().compare(*site_events_iterator_) > 0)
process_site_event();
else
process_circle_event();
@@ -112,12 +115,11 @@
return output_.get_bounding_rectangle();
}
- void clip(voronoi_output_clipped<coordinate_type> &clipped_output) {
+ void clip(ClippedOutput &clipped_output) {
output_.clip(clipped_output);
}
- void clip(const BRect<coordinate_type> &brect,
- voronoi_output_clipped<coordinate_type> &clipped_output) {
+ void clip(const BRect<coordinate_type> &brect, ClippedOutput &clipped_output) {
output_.clip(brect, clipped_output);
}
@@ -128,7 +130,7 @@
typedef typename detail::circle_events_queue<coordinate_type> CircleEventsQueue;
typedef typename detail::beach_line_node<coordinate_type> Key;
- typedef typename detail::half_edge<coordinate_type>* Value;
+ typedef typename detail::beach_line_node_data<coordinate_type> Value;
typedef typename detail::node_comparer<Key> NodeComparer;
typedef std::map< Key, Value, NodeComparer > BeachLine;
typedef typename std::map< Key, Value, NodeComparer >::iterator beach_line_iterator;
@@ -213,11 +215,12 @@
site_arc = it->first.get_left_site();
const site_event_type &site2 = it->first.get_left_site();
const site_event_type &site3 = it->first.get_right_site();
+
+ // Remove candidate circle from the event queue.
+ it->second.deactivate_circle_event();
it--;
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);
@@ -246,11 +249,11 @@
site_event_type site3 = it_first->first.get_right_site();
// Get second bisector;
- Value bisector2 = it_first->second;
+ edge_type *bisector2 = it_first->second.edge;
// Get first bisector;
it_first--;
- Value bisector1 = it_first->second;
+ edge_type *bisector1 = it_first->second.edge;
// Get the first site that creates given circle event.
site_event_type site1 = it_first->first.get_left_site();
@@ -263,9 +266,8 @@
// 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(site3);
- edge_type *edge = output_.insert_new_edge(site1, site2, site3, circle_event,
- bisector1, bisector2);
- it_first->second = edge;
+ it_first->second.edge = output_.insert_new_edge(site1, site2, site3, circle_event,
+ bisector1, bisector2);
beach_line_.erase(it_last);
it_last = it_first;
@@ -276,9 +278,9 @@
// Check the new triplets formed by the neighboring arcs
// for potential circle events. Check left.
if (it_first != beach_line_.begin()) {
+ it_first->second.deactivate_circle_event();
it_first--;
const site_event_type &site_l1 = it_first->first.get_left_site();
- deactivate_circle_event(site_l1, site1, site2);
activate_circle_event(site_l1, site1, site3, it_last);
}
@@ -286,8 +288,8 @@
// for potential circle events. Check right.
it_last++;
if (it_last != beach_line_.end()) {
+ it_last->second.deactivate_circle_event();
const site_event_type &site_r1 = it_last->first.get_right_site();
- deactivate_circle_event(site2, site3, site_r1);
activate_circle_event(site1, site3, site_r1, it_last);
}
@@ -312,24 +314,68 @@
const site_event_type &site2,
const site_event_type &site3,
circle_event_type &c_event) const {
- coordinate_type a = (site1.x() - site2.x()) * (site2.y() - site3.y()) -
- (site1.y() - site2.y()) * (site2.x() - site3.x());
+ //mpz_class dif_x1, dif_x2, dif_y1, dif_y2, a;
+ //dif_x1 = static_cast<int>(site1.x() - site2.x());
+ //dif_x2 = static_cast<int>(site2.x() - site3.x());
+ //dif_y1 = static_cast<int>(site1.y() - site2.y());
+ //dif_y2 = static_cast<int>(site2.y() - site3.y());
+ //a = (dif_x1 * dif_y2 - dif_y1 * dif_x2) * 2;
+ //
+ //// Check if bisectors intersect.
+ //if (a >= 0)
+ // return false;
+
+ //mpz_class sum_x1, sum_x2, sum_y1, sum_y2, b1, b2;
+ //sum_x1 = static_cast<int>(site1.x() + site2.x());
+ //sum_x2 = static_cast<int>(site2.x() + site3.x());
+ //sum_y1 = static_cast<int>(site1.y() + site2.y());
+ //sum_y2 = static_cast<int>(site2.y() + site3.y());
+ //b1 = dif_x1 * sum_x1 + dif_y1 * sum_y1;
+ //b2 = dif_x2 * sum_x2 + dif_y2 * sum_y2;
+
+ //mpq_class c_x(b1 * dif_y2 - b2 * dif_y1, a);
+ //c_x.canonicalize();
+ //mpq_class c_y(b2 * dif_x1 - b1 * dif_x2, a);
+ //c_y.canonicalize();
+ //mpq_class temp_x(c_x - site1.x());
+ //mpq_class temp_y(c_y - site1.y());
+ //mpq_class sqr_radius(temp_x * temp_x + temp_y * temp_y);
+
+ //// Create new circle event;
+ //c_event = detail::make_circle_event<coordinate_type>(c_x.get_d(),
+ // c_y.get_d(),
+ // sqr_radius.get_d());
+ //c_event.set_sites(site1.get_site_index(),
+ // site2.get_site_index(),
+ // 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 >= static_cast<coordinate_type>(0))
+ if (a >= 0)
return false;
- 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 *
- static_cast<coordinate_type>(0.5);
- coordinate_type c_y = (b2*(site1.x() - site2.x()) - b1*(site2.x() - site3.x())) / a *
- static_cast<coordinate_type>(0.5);
+ 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 sqr_radius = (c_x-site1.x())*(c_x-site1.x()) +
(c_y-site1.y())*(c_y-site1.y());
- // Create new circle event;
c_event = detail::make_circle_event<coordinate_type>(c_x, c_y, sqr_radius);
- c_event.set_sites(site1, site2, site3);
+ c_event.set_sites(site1.get_site_index(),
+ site2.get_site_index(),
+ site3.get_site_index());
return true;
}
@@ -341,19 +387,10 @@
circle_event_type c_event;
if (create_circle_event(site1, site2, site3, c_event)) {
c_event.set_bisector(bisector_node);
- circle_events_.push(c_event);
+ bisector_node->second.activate_circle_event(circle_events_.push(c_event));
}
}
- // Remove circle event from the event queue.
- void deactivate_circle_event(const site_event_type &point1,
- const site_event_type &point2,
- const site_event_type &point3) {
- circle_event_type c_event;
- if (create_circle_event(point1, point2, point3, c_event))
- circle_events_.deactivate_event(c_event);
- }
-
private:
std::vector<site_event_type> site_events_;
site_events_iterator site_events_iterator_;
Modified: sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_output.hpp
==============================================================================
--- sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_output.hpp (original)
+++ sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_output.hpp 2010-07-19 11:18:12 EDT (Mon, 19 Jul 2010)
@@ -14,9 +14,11 @@
#include <map>
#include <vector>
+//#pragma warning( disable : 4800 )
+//#include "gmpxx.h"
+
namespace boost {
namespace sweepline {
-
template <typename T>
struct point_2d {
public:
Added: sandbox/SOC/2010/sweepline/libs/sweepline/example/example_013.txt
==============================================================================
--- (empty file)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/example/example_013.txt 2010-07-19 11:18:12 EDT (Mon, 19 Jul 2010)
@@ -0,0 +1,14 @@
+13
+0 5
+0 -5
+-4 -3
+4 -3
+4 3
+-4 3
+3 -4
+-3 4
+-3 -4
+3 4
+-5 0
+5 0
+0 0
\ No newline at end of file
Added: sandbox/SOC/2010/sweepline/libs/sweepline/example/example_014.txt
==============================================================================
--- (empty file)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/example/example_014.txt 2010-07-19 11:18:12 EDT (Mon, 19 Jul 2010)
@@ -0,0 +1,13 @@
+12
+0 5
+0 -5
+-4 -3
+4 -3
+4 3
+-4 3
+3 -4
+-3 4
+-3 -4
+3 4
+-5 0
+5 0
\ No newline at end of file
Added: sandbox/SOC/2010/sweepline/libs/sweepline/example/example_015.txt
==============================================================================
--- (empty file)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/example/example_015.txt 2010-07-19 11:18:12 EDT (Mon, 19 Jul 2010)
@@ -0,0 +1,5 @@
+4
+4 3
+4 8
+9 2
+9 9
\ No newline at end of file
Added: sandbox/SOC/2010/sweepline/libs/sweepline/example/example_016_random.txt
==============================================================================
--- (empty file)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/example/example_016_random.txt 2010-07-19 11:18:12 EDT (Mon, 19 Jul 2010)
@@ -0,0 +1,11 @@
+10
+9 1
+4 3
+9 6
+9 8
+3 9
+6 8
+0 5
+9 5
+3 0
+2 1
\ No newline at end of file
Added: sandbox/SOC/2010/sweepline/libs/sweepline/example/example_017_random.txt
==============================================================================
--- (empty file)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/example/example_017_random.txt 2010-07-19 11:18:12 EDT (Mon, 19 Jul 2010)
@@ -0,0 +1,11 @@
+10
+9 9
+2 6
+3 1
+6 4
+9 1
+9 7
+6 2
+2 4
+3 7
+6 7
\ No newline at end of file
Added: sandbox/SOC/2010/sweepline/libs/sweepline/example/example_018_random.txt
==============================================================================
--- (empty file)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/example/example_018_random.txt 2010-07-19 11:18:12 EDT (Mon, 19 Jul 2010)
@@ -0,0 +1,11 @@
+10
+4 1
+5 4
+5 5
+2 6
+3 4
+0 7
+2 5
+8 9
+0 4
+2 7
\ No newline at end of file
Added: sandbox/SOC/2010/sweepline/libs/sweepline/example/example_019_random.txt
==============================================================================
--- (empty file)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/example/example_019_random.txt 2010-07-19 11:18:12 EDT (Mon, 19 Jul 2010)
@@ -0,0 +1,101 @@
+100
+29 76
+99 94
+74 20
+53 26
+95 55
+94 21
+50 70
+19 93
+31 30
+73 61
+87 23
+60 66
+51 29
+82 51
+74 40
+31 77
+1 82
+43 0
+58 67
+63 32
+19 90
+68 31
+49 63
+76 83
+72 20
+70 11
+80 23
+4 90
+32 56
+63 75
+51 71
+62 10
+80 57
+71 47
+2 8
+67 85
+64 72
+85 6
+53 91
+92 25
+95 79
+24 6
+1 10
+10 85
+11 30
+22 14
+48 55
+82 8
+14 54
+84 60
+33 91
+85 60
+65 81
+60 23
+10 44
+29 32
+21 11
+90 15
+73 71
+41 62
+9 36
+44 80
+27 39
+41 38
+25 23
+86 15
+4 76
+52 6
+39 97
+42 25
+93 93
+97 24
+13 16
+58 62
+48 78
+43 74
+99 85
+13 42
+8 82
+13 9
+51 50
+85 83
+30 11
+58 42
+44 32
+88 74
+37 21
+65 28
+79 94
+50 94
+38 83
+82 13
+30 88
+16 92
+73 66
+24 0
+40 82
+57 25
+55 88
+13 33
\ No newline at end of file
Modified: sandbox/SOC/2010/sweepline/libs/sweepline/example/voronoi_visualizer.cpp
==============================================================================
--- sandbox/SOC/2010/sweepline/libs/sweepline/example/voronoi_visualizer.cpp (original)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/example/voronoi_visualizer.cpp 2010-07-19 11:18:12 EDT (Mon, 19 Jul 2010)
@@ -34,7 +34,7 @@
QTextStream in_stream(&data);
int num_sites;
in_stream >> num_sites;
- double x, y;
+ coordinate_type x, y;
for (int i = 0; i < num_sites; i++) {
in_stream >> x >> y;
sites.push_back(boost::sweepline::make_point_2d(x, y));
@@ -125,7 +125,7 @@
public:
MainWindow() {
glWidget_ = new GLWidget();
- file_dir_ = QDir(QDir::currentPath(), tr("*.pts"));
+ file_dir_ = QDir(QDir::currentPath(), tr("*.txt"));
QHBoxLayout *centralLayout = new QHBoxLayout;
centralLayout->addWidget(glWidget_);
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-07-19 11:18:12 EDT (Mon, 19 Jul 2010)
@@ -52,16 +52,10 @@
T x = static_cast<T>(10-i);
T y = static_cast<T>(10-i);
circle_event_type c = detail::make_circle_event<T>(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);
- circle_event_type c = detail::make_circle_event<T>(x, y, static_cast<T>(0));
- c.set_sites(temp_site, temp_site, temp_site);
- event_q.deactivate_event(c);
+ if (i&1) {
+ event_q.push(c)->deactivate();
+ } else
+ event_q.push(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-07-19 11:18:12 EDT (Mon, 19 Jul 2010)
@@ -69,7 +69,7 @@
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);
+ circle1.set_sites(0, 0, 0);
circle_event<T> circle2;
BOOST_CHECK_EQUAL(circle1.x(), static_cast<T>(1));
@@ -77,28 +77,28 @@
BOOST_CHECK_EQUAL(circle1.get_sqr_radius(), static_cast<T>(4));
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);
+ circle2.set_sites(0, 0, 0);
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);
+ circle2.set_sites(0, 0, 0);
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);
+ circle2.set_sites(0, 0, 0);
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(temp_site, temp_site, temp_site);
+ circle2.set_sites(0, 0, 0);
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);
+ circle2.set_sites(0, 0, 0);
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-07-19 11:18:12 EDT (Mon, 19 Jul 2010)
@@ -80,13 +80,12 @@
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));
+ bline_node new_node1(make_site_event<T>(static_cast<T>(2), static_cast<T>(-10), 2));
+ bline_node new_node2(make_site_event<T>(static_cast<T>(2), static_cast<T>(-1), 3));
+ bline_node new_node3(make_site_event<T>(static_cast<T>(2), static_cast<T>(0), 4));
+ bline_node new_node4(make_site_event<T>(static_cast<T>(2), static_cast<T>(1), 4));
+ bline_node new_node5(make_site_event<T>(static_cast<T>(2), static_cast<T>(2), 4));
+ bline_node new_node6(make_site_event<T>(static_cast<T>(2), static_cast<T>(3), 4));
BOOST_CHECK_EQUAL(node_comparer_test(initial_node, new_node1), false);
@@ -95,7 +94,6 @@
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);
@@ -104,7 +102,6 @@
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) {
@@ -116,16 +113,16 @@
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));
+ bline_node new_node1(make_site_event<T>(static_cast<T>(2), static_cast<T>(-3), 2));
+ bline_node new_node2(make_site_event<T>(static_cast<T>(2), static_cast<T>(-2), 3));
+ bline_node new_node3(make_site_event<T>(static_cast<T>(2), static_cast<T>(-1), 4));
+ bline_node new_node4(make_site_event<T>(static_cast<T>(2), static_cast<T>(0), 4));
+ bline_node new_node5(make_site_event<T>(static_cast<T>(2), static_cast<T>(1), 4));
+ bline_node new_node6(make_site_event<T>(static_cast<T>(2), static_cast<T>(3), 4));
+ bline_node new_node7(make_site_event<T>(static_cast<T>(2), static_cast<T>(10), 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_node2), true);
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);
@@ -133,7 +130,7 @@
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_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);
BOOST_CHECK_EQUAL(node_comparer_test(new_node5, initial_node), false);
@@ -150,31 +147,28 @@
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));
+ bline_node new_node1(make_site_event<T>(static_cast<T>(2), static_cast<T>(-10), 2));
+ bline_node new_node2(make_site_event<T>(static_cast<T>(2), static_cast<T>(0), 3));
+ bline_node new_node3(make_site_event<T>(static_cast<T>(2), static_cast<T>(1), 4));
+ bline_node new_node4(make_site_event<T>(static_cast<T>(2), static_cast<T>(2), 4));
+ bline_node new_node5(make_site_event<T>(static_cast<T>(2), static_cast<T>(5), 4));
+ bline_node new_node6(make_site_event<T>(static_cast<T>(2), 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_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), 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_test6, T, test_types) {
@@ -186,20 +180,20 @@
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));
+ bline_node new_node1(make_site_event<T>(static_cast<T>(2), static_cast<T>(-3), 2));
+ bline_node new_node2(make_site_event<T>(static_cast<T>(2), static_cast<T>(-2), 3));
+ bline_node new_node3(make_site_event<T>(static_cast<T>(2), static_cast<T>(0), 4));
+ bline_node new_node4(make_site_event<T>(static_cast<T>(2), static_cast<T>(1), 4));
+ bline_node new_node5(make_site_event<T>(static_cast<T>(2), static_cast<T>(2), 4));
+ bline_node new_node6(make_site_event<T>(static_cast<T>(2), static_cast<T>(3), 4));
+ bline_node new_node7(make_site_event<T>(static_cast<T>(2), static_cast<T>(5), 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_node6), false);
BOOST_CHECK_EQUAL(node_comparer_test(initial_node, new_node7), true);
BOOST_CHECK_EQUAL(node_comparer_test(new_node1, initial_node), true);
@@ -207,7 +201,7 @@
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_node6, initial_node), true);
BOOST_CHECK_EQUAL(node_comparer_test(new_node7, initial_node), false);
}
@@ -223,20 +217,14 @@
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) {
Modified: sandbox/SOC/2010/sweepline/libs/sweepline/test/test_type_list.hpp
==============================================================================
--- sandbox/SOC/2010/sweepline/libs/sweepline/test/test_type_list.hpp (original)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/test/test_type_list.hpp 2010-07-19 11:18:12 EDT (Mon, 19 Jul 2010)
@@ -12,6 +12,6 @@
#include <boost/mpl/list.hpp>
-typedef boost::mpl::list<double, long double> test_types;
+typedef boost::mpl::list<double> test_types;
#endif
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-19 11:18:12 EDT (Mon, 19 Jul 2010)
@@ -17,26 +17,32 @@
#define BOOST_TEST_MODULE voronoi_builder_test
#include <boost/test/test_case_template.hpp>
+#define CHECK_EQUAL_POINTS(p1, p2) \
+ BOOST_CHECK_EQUAL(p1.x() == static_cast<coordinate_type>(p2.x()) && \
+ p1.y() == static_cast<coordinate_type>(p2.y()), true)
+
// Sites: (0, 0).
BOOST_AUTO_TEST_CASE_TEMPLATE(single_site_test, T, test_types) {
- typedef typename voronoi_output_clipped<T>::voronoi_const_iterator_type
+ typedef T coordinate_type;
+ typedef typename voronoi_output_clipped<coordinate_type>::voronoi_const_iterator_type
voronoi_const_iterator_type;
- voronoi_builder<T> test_voronoi_builder;
- std::vector< point_2d<T> > points;
- points.push_back(make_point_2d<T>(static_cast<T>(0), static_cast<T>(0)));
+ voronoi_builder<coordinate_type> test_voronoi_builder;
+ std::vector< point_2d<coordinate_type> > points;
+ points.push_back(make_point_2d<coordinate_type>(static_cast<coordinate_type>(0),
+ static_cast<coordinate_type>(0)));
test_voronoi_builder.init(points);
test_voronoi_builder.run_sweepline();
- voronoi_output_clipped<T> test_output;
+ voronoi_output_clipped<coordinate_type> test_output;
test_voronoi_builder.clip(test_output);
BOOST_CHECK_EQUAL(test_output.check(), true);
- BRect<T> bounding_rectangle = test_voronoi_builder.get_bounding_rectangle();
- BOOST_CHECK_EQUAL(bounding_rectangle.x_min == static_cast<T>(0) &&
- bounding_rectangle.y_min == static_cast<T>(0) &&
- bounding_rectangle.x_max == static_cast<T>(0) &&
- bounding_rectangle.y_max == static_cast<T>(0), true);
+ BRect<coordinate_type> bounding_rectangle = test_voronoi_builder.get_bounding_rectangle();
+ BOOST_CHECK_EQUAL(bounding_rectangle.x_min == static_cast<coordinate_type>(0) &&
+ bounding_rectangle.y_min == static_cast<coordinate_type>(0) &&
+ bounding_rectangle.x_max == static_cast<coordinate_type>(0) &&
+ bounding_rectangle.y_max == static_cast<coordinate_type>(0), true);
BOOST_CHECK_EQUAL(static_cast<int>(test_output.get_voronoi_cells().size()), 1);
BOOST_CHECK_EQUAL(static_cast<int>(test_output.get_voronoi_vertices().size()), 0);
@@ -53,26 +59,29 @@
// Sites: (0, 0), (0, 1).
BOOST_AUTO_TEST_CASE_TEMPLATE(collinear_sites_test1, T, test_types) {
- typedef typename voronoi_output_clipped<T>::edge_type edge_type;
- typedef typename voronoi_output_clipped<T>::voronoi_const_iterator_type
+ typedef T coordinate_type;
+ typedef typename voronoi_output_clipped<coordinate_type>::edge_type edge_type;
+ typedef typename voronoi_output_clipped<coordinate_type>::voronoi_const_iterator_type
voronoi_const_iterator_type;
- voronoi_builder<T> test_voronoi_builder;
- std::vector< point_2d<T> > points;
- points.push_back(make_point_2d<T>(static_cast<T>(0), static_cast<T>(0)));
- points.push_back(make_point_2d<T>(static_cast<T>(0), static_cast<T>(1)));
+ voronoi_builder<coordinate_type> test_voronoi_builder;
+ std::vector< point_2d<coordinate_type> > points;
+ points.push_back(make_point_2d<coordinate_type>(static_cast<coordinate_type>(0),
+ static_cast<coordinate_type>(0)));
+ points.push_back(make_point_2d<coordinate_type>(static_cast<coordinate_type>(0),
+ static_cast<coordinate_type>(1)));
test_voronoi_builder.init(points);
test_voronoi_builder.run_sweepline();
- voronoi_output_clipped<T> test_output;
+ voronoi_output_clipped<coordinate_type> test_output;
test_voronoi_builder.clip(test_output);
BOOST_CHECK_EQUAL(test_output.check(), true);
- BRect<T> bounding_rectangle = test_voronoi_builder.get_bounding_rectangle();
- BOOST_CHECK_EQUAL(bounding_rectangle.x_min == static_cast<T>(0) &&
- bounding_rectangle.y_min == static_cast<T>(0) &&
- bounding_rectangle.x_max == static_cast<T>(0) &&
- bounding_rectangle.y_max == static_cast<T>(1), true);
+ BRect<coordinate_type> bounding_rectangle = test_voronoi_builder.get_bounding_rectangle();
+ BOOST_CHECK_EQUAL(bounding_rectangle.x_min == static_cast<coordinate_type>(0) &&
+ bounding_rectangle.y_min == static_cast<coordinate_type>(0) &&
+ bounding_rectangle.x_max == static_cast<coordinate_type>(0) &&
+ bounding_rectangle.y_max == static_cast<coordinate_type>(1), true);
BOOST_CHECK_EQUAL(static_cast<int>(test_output.get_voronoi_cells().size()), 2);
BOOST_CHECK_EQUAL(static_cast<int>(test_output.get_voronoi_vertices().size()), 2);
@@ -106,27 +115,31 @@
// Sites: (0, 0), (1, 1), (2, 2).
BOOST_AUTO_TEST_CASE_TEMPLATE(collinear_sites_test2, T, test_types) {
- typedef typename voronoi_output_clipped<T>::edge_type edge_type;
- typedef typename voronoi_output_clipped<T>::voronoi_const_iterator_type
+ typedef T coordinate_type;
+ typedef typename voronoi_output_clipped<coordinate_type>::edge_type edge_type;
+ typedef typename voronoi_output_clipped<coordinate_type>::voronoi_const_iterator_type
voronoi_const_iterator_type;
- voronoi_builder<T> test_voronoi_builder;
- std::vector< point_2d<T> > points;
- points.push_back(make_point_2d<T>(static_cast<T>(0), static_cast<T>(0)));
- points.push_back(make_point_2d<T>(static_cast<T>(1), static_cast<T>(1)));
- points.push_back(make_point_2d<T>(static_cast<T>(2), static_cast<T>(2)));
+ voronoi_builder<coordinate_type> test_voronoi_builder;
+ std::vector< point_2d<coordinate_type> > points;
+ points.push_back(make_point_2d<coordinate_type>(static_cast<coordinate_type>(0),
+ static_cast<coordinate_type>(0)));
+ points.push_back(make_point_2d<coordinate_type>(static_cast<coordinate_type>(1),
+ static_cast<coordinate_type>(1)));
+ points.push_back(make_point_2d<coordinate_type>(static_cast<coordinate_type>(2),
+ static_cast<coordinate_type>(2)));
test_voronoi_builder.init(points);
test_voronoi_builder.run_sweepline();
- voronoi_output_clipped<T> test_output;
+ voronoi_output_clipped<coordinate_type> test_output;
test_voronoi_builder.clip(test_output);
BOOST_CHECK_EQUAL(test_output.check(), true);
- BRect<T> bounding_rectangle = test_voronoi_builder.get_bounding_rectangle();
- BOOST_CHECK_EQUAL(bounding_rectangle.x_min == static_cast<T>(0) &&
- bounding_rectangle.y_min == static_cast<T>(0) &&
- bounding_rectangle.x_max == static_cast<T>(2) &&
- bounding_rectangle.y_max == static_cast<T>(2), true);
+ BRect<coordinate_type> bounding_rectangle = test_voronoi_builder.get_bounding_rectangle();
+ BOOST_CHECK_EQUAL(bounding_rectangle.x_min == static_cast<coordinate_type>(0) &&
+ bounding_rectangle.y_min == static_cast<coordinate_type>(0) &&
+ bounding_rectangle.x_max == static_cast<coordinate_type>(2) &&
+ bounding_rectangle.y_max == static_cast<coordinate_type>(2), true);
BOOST_CHECK_EQUAL(static_cast<int>(test_output.get_voronoi_cells().size()), 3);
BOOST_CHECK_EQUAL(static_cast<int>(test_output.get_voronoi_vertices().size()), 4);
@@ -163,54 +176,58 @@
// Sites: (0, 0), (0, 4), (2, 1).
BOOST_AUTO_TEST_CASE_TEMPLATE(triangle_test1, T, test_types) {
- typedef typename voronoi_output_clipped<T>::edge_type edge_type;
- typedef typename voronoi_output_clipped<T>::voronoi_const_iterator_type
+ typedef T coordinate_type;
+ typedef typename voronoi_output_clipped<coordinate_type>::edge_type edge_type;
+ typedef typename voronoi_output_clipped<coordinate_type>::voronoi_const_iterator_type
voronoi_const_iterator_type;
- voronoi_builder<T> test_beach_line;
- point_2d<T> point1 = make_point_2d<T>(static_cast<T>(0), static_cast<T>(0));
- point_2d<T> point2 = make_point_2d<T>(static_cast<T>(0), static_cast<T>(4));
- point_2d<T> point3 = make_point_2d<T>(static_cast<T>(2), static_cast<T>(1));
+ voronoi_builder<coordinate_type> test_beach_line;
+ point_2d<coordinate_type> point1 = make_point_2d<coordinate_type>(
+ static_cast<coordinate_type>(0), static_cast<coordinate_type>(0));
+ point_2d<coordinate_type> point2 = make_point_2d<coordinate_type>(
+ static_cast<coordinate_type>(0), static_cast<coordinate_type>(4));
+ point_2d<coordinate_type> point3 = make_point_2d<coordinate_type>(
+ static_cast<coordinate_type>(2), static_cast<coordinate_type>(1));
- std::vector< point_2d<T> > points;
+ std::vector< point_2d<coordinate_type> > points;
points.push_back(point1);
points.push_back(point2);
points.push_back(point3);
test_beach_line.init(points);
test_beach_line.run_sweepline();
- voronoi_output_clipped<T> test_output;
+ voronoi_output_clipped<coordinate_type> test_output;
test_beach_line.clip(test_output);
BOOST_CHECK_EQUAL(test_output.check(), true);
- BRect<T> bounding_rectangle = test_beach_line.get_bounding_rectangle();
- BOOST_CHECK_EQUAL(bounding_rectangle.x_min == static_cast<T>(0) &&
- bounding_rectangle.y_min == static_cast<T>(0) &&
- bounding_rectangle.x_max == static_cast<T>(2) &&
- bounding_rectangle.y_max == static_cast<T>(4), true);
+ BRect<coordinate_type> bounding_rectangle = test_beach_line.get_bounding_rectangle();
+ BOOST_CHECK_EQUAL(bounding_rectangle.x_min == static_cast<coordinate_type>(0) &&
+ bounding_rectangle.y_min == static_cast<coordinate_type>(0) &&
+ bounding_rectangle.x_max == static_cast<coordinate_type>(2) &&
+ bounding_rectangle.y_max == static_cast<coordinate_type>(4), true);
BOOST_CHECK_EQUAL(static_cast<int>(test_output.get_voronoi_cells().size()), 3);
BOOST_CHECK_EQUAL(static_cast<int>(test_output.get_voronoi_vertices().size()), 4);
voronoi_const_iterator_type it = test_output.get_voronoi_vertices().begin();
BOOST_CHECK_EQUAL(it->num_incident_edges, 3);
- BOOST_CHECK_EQUAL(it->voronoi_point.x() == static_cast<T>(0.25) &&
- it->voronoi_point.y() == static_cast<T>(2.0), true);
+ BOOST_CHECK_EQUAL(it->voronoi_point.x() == static_cast<coordinate_type>(0.25) &&
+ it->voronoi_point.y() == static_cast<coordinate_type>(2.0), true);
edge_type *edge1_1 = it->incident_edge;
edge_type *edge1_2 = edge1_1->twin;
- BOOST_CHECK_EQUAL(edge1_1->cell->voronoi_point == point3, true);
- BOOST_CHECK_EQUAL(edge1_2->cell->voronoi_point == point1, true);
+ CHECK_EQUAL_POINTS(edge1_1->cell->voronoi_point, point3);
+ CHECK_EQUAL_POINTS(edge1_2->cell->voronoi_point, point1);
edge_type *edge2_1 = edge1_1->rot_prev;
edge_type *edge2_2 = edge2_1->twin;
- BOOST_CHECK_EQUAL(edge2_1->cell->voronoi_point == point1, true);
- BOOST_CHECK_EQUAL(edge2_2->cell->voronoi_point == point2, true);
+ CHECK_EQUAL_POINTS(edge2_1->cell->voronoi_point, point1);
+ CHECK_EQUAL_POINTS(edge2_2->cell->voronoi_point, point2);
edge_type *edge3_1 = edge2_1->rot_prev;
edge_type *edge3_2 = edge3_1->twin;
- BOOST_CHECK_EQUAL(edge3_1->cell->voronoi_point == point2, true);
- BOOST_CHECK_EQUAL(edge3_2->cell->voronoi_point == point3, true);
+ CHECK_EQUAL_POINTS(edge3_1->cell->voronoi_point, point2);
+ CHECK_EQUAL_POINTS(edge3_2->cell->voronoi_point, point3);
BOOST_CHECK_EQUAL(edge1_2->twin == edge1_1, true);
BOOST_CHECK_EQUAL(edge2_2->twin == edge2_1, true);
@@ -231,23 +248,27 @@
// Sites: (0, 1), (2, 0), (2, 4).
BOOST_AUTO_TEST_CASE_TEMPLATE(triangle_test2, T, test_types) {
- typedef typename voronoi_output_clipped<T>::edge_type edge_type;
- typedef typename voronoi_output_clipped<T>::voronoi_const_iterator_type
+ typedef T coordinate_type;
+ typedef typename voronoi_output_clipped<coordinate_type>::edge_type edge_type;
+ typedef typename voronoi_output_clipped<coordinate_type>::voronoi_const_iterator_type
voronoi_const_iterator_type;
- voronoi_builder<T> test_beach_line;
- point_2d<T> point1 = make_point_2d<T>(static_cast<T>(0), static_cast<T>(1));
- point_2d<T> point2 = make_point_2d<T>(static_cast<T>(2), static_cast<T>(0));
- point_2d<T> point3 = make_point_2d<T>(static_cast<T>(2), static_cast<T>(4));
+ voronoi_builder<coordinate_type> test_beach_line;
+ point_2d<coordinate_type> point1 = make_point_2d<coordinate_type>(
+ static_cast<coordinate_type>(0), static_cast<coordinate_type>(1));
+ point_2d<coordinate_type> point2 = make_point_2d<coordinate_type>(
+ static_cast<coordinate_type>(2), static_cast<coordinate_type>(0));
+ point_2d<coordinate_type> point3 = make_point_2d<coordinate_type>(
+ static_cast<coordinate_type>(2), static_cast<coordinate_type>(4));
- std::vector< point_2d<T> > points;
+ std::vector< point_2d<coordinate_type> > points;
points.push_back(point1);
points.push_back(point2);
points.push_back(point3);
test_beach_line.init(points);
test_beach_line.run_sweepline();
- voronoi_output_clipped<T> test_output;
+ voronoi_output_clipped<coordinate_type> test_output;
test_beach_line.clip(test_output);
BOOST_CHECK_EQUAL(test_output.check(), true);
@@ -256,23 +277,23 @@
voronoi_const_iterator_type it = test_output.get_voronoi_vertices().begin();
BOOST_CHECK_EQUAL(it->num_incident_edges, 3);
- BOOST_CHECK_EQUAL(it->voronoi_point.x() == static_cast<T>(1.75) &&
- it->voronoi_point.y() == static_cast<T>(2.0), true);
+ BOOST_CHECK_EQUAL(it->voronoi_point.x() == static_cast<coordinate_type>(1.75) &&
+ it->voronoi_point.y() == static_cast<coordinate_type>(2.0), true);
edge_type *edge1_1 = it->incident_edge;
edge_type *edge1_2 = edge1_1->twin;
- BOOST_CHECK_EQUAL(edge1_1->cell->voronoi_point == point2, true);
- BOOST_CHECK_EQUAL(edge1_2->cell->voronoi_point == point1, true);
+ CHECK_EQUAL_POINTS(edge1_1->cell->voronoi_point, point2);
+ CHECK_EQUAL_POINTS(edge1_2->cell->voronoi_point, point1);
edge_type *edge2_1 = edge1_1->rot_prev;
edge_type *edge2_2 = edge2_1->twin;
- BOOST_CHECK_EQUAL(edge2_1->cell->voronoi_point == point1, true);
- BOOST_CHECK_EQUAL(edge2_2->cell->voronoi_point == point3, true);
+ CHECK_EQUAL_POINTS(edge2_1->cell->voronoi_point, point1);
+ CHECK_EQUAL_POINTS(edge2_2->cell->voronoi_point, point3);
edge_type *edge3_1 = edge2_1->rot_prev;
edge_type *edge3_2 = edge3_1->twin;
- BOOST_CHECK_EQUAL(edge3_1->cell->voronoi_point == point3, true);
- BOOST_CHECK_EQUAL(edge3_2->cell->voronoi_point == point2, true);
+ CHECK_EQUAL_POINTS(edge3_1->cell->voronoi_point, point3);
+ CHECK_EQUAL_POINTS(edge3_2->cell->voronoi_point, point2);
BOOST_CHECK_EQUAL(edge1_2->twin == edge1_1, true);
BOOST_CHECK_EQUAL(edge2_2->twin == edge2_1, true);
@@ -293,25 +314,30 @@
// Sites: (0, 0), (0, 1), (1, 0), (1, 1).
BOOST_AUTO_TEST_CASE_TEMPLATE(square_test3, T, test_types) {
- typedef typename voronoi_output_clipped<T>::edge_type edge_type;
- typedef typename voronoi_output_clipped<T>::voronoi_const_iterator_type
+ typedef T coordinate_type;
+ typedef typename voronoi_output_clipped<coordinate_type>::edge_type edge_type;
+ typedef typename voronoi_output_clipped<coordinate_type>::voronoi_const_iterator_type
voronoi_const_iterator_type;
- voronoi_builder<T> test_beach_line;
- std::vector< point_2d<T> > points;
- points.push_back(make_point_2d<T>(static_cast<T>(0), static_cast<T>(0)));
- points.push_back(make_point_2d<T>(static_cast<T>(0), static_cast<T>(1)));
- points.push_back(make_point_2d<T>(static_cast<T>(1), static_cast<T>(0)));
- points.push_back(make_point_2d<T>(static_cast<T>(1), static_cast<T>(1)));
+ voronoi_builder<coordinate_type> test_beach_line;
+ std::vector< point_2d<coordinate_type> > points;
+ points.push_back(make_point_2d<coordinate_type>(static_cast<coordinate_type>(0),
+ static_cast<coordinate_type>(0)));
+ points.push_back(make_point_2d<coordinate_type>(static_cast<coordinate_type>(0),
+ static_cast<coordinate_type>(1)));
+ points.push_back(make_point_2d<coordinate_type>(static_cast<coordinate_type>(1),
+ static_cast<coordinate_type>(0)));
+ points.push_back(make_point_2d<coordinate_type>(static_cast<coordinate_type>(1),
+ static_cast<coordinate_type>(1)));
test_beach_line.init(points);
test_beach_line.run_sweepline();
- voronoi_output_clipped<T> test_output;
+ voronoi_output_clipped<coordinate_type> test_output;
test_beach_line.clip(test_output);
BOOST_CHECK_EQUAL(test_output.check(), true);
- BOOST_CHECK_EQUAL(static_cast<T>(test_output.get_voronoi_cells().size()), 4);
- BOOST_CHECK_EQUAL(static_cast<T>(test_output.get_voronoi_vertices().size()), 5);
+ BOOST_CHECK_EQUAL(static_cast<coordinate_type>(test_output.get_voronoi_cells().size()), 4);
+ BOOST_CHECK_EQUAL(static_cast<coordinate_type>(test_output.get_voronoi_vertices().size()), 5);
BOOST_CHECK_EQUAL(test_output.get_num_voronoi_cells(), 4);
BOOST_CHECK_EQUAL(test_output.get_num_voronoi_vertices(), 1);
BOOST_CHECK_EQUAL(test_output.get_num_voronoi_edges(), 4);
@@ -319,29 +345,29 @@
// Check voronoi vertex.
voronoi_const_iterator_type it = test_output.get_voronoi_vertices().begin();
BOOST_CHECK_EQUAL(it->num_incident_edges, 4);
- BOOST_CHECK_EQUAL(it->voronoi_point.x() == static_cast<T>(0.5) &&
- it->voronoi_point.y() == static_cast<T>(0.5), true);
+ BOOST_CHECK_EQUAL(it->voronoi_point.x() == static_cast<coordinate_type>(0.5) &&
+ it->voronoi_point.y() == static_cast<coordinate_type>(0.5), true);
// Check voronoi edges.
edge_type *edge1_1 = it->incident_edge;
edge_type *edge1_2 = edge1_1->twin;
- BOOST_CHECK_EQUAL(edge1_1->cell->voronoi_point == points[2], true);
- BOOST_CHECK_EQUAL(edge1_2->cell->voronoi_point == points[0], true);
+ CHECK_EQUAL_POINTS(edge1_1->cell->voronoi_point, points[2]);
+ CHECK_EQUAL_POINTS(edge1_2->cell->voronoi_point, points[0]);
edge_type *edge2_1 = edge1_1->rot_prev;
edge_type *edge2_2 = edge2_1->twin;
- BOOST_CHECK_EQUAL(edge2_1->cell->voronoi_point == points[0], true);
- BOOST_CHECK_EQUAL(edge2_2->cell->voronoi_point == points[1], true);
+ CHECK_EQUAL_POINTS(edge2_1->cell->voronoi_point, points[0]);
+ CHECK_EQUAL_POINTS(edge2_2->cell->voronoi_point, points[1]);
edge_type *edge3_1 = edge2_1->rot_prev;
edge_type *edge3_2 = edge3_1->twin;
- BOOST_CHECK_EQUAL(edge3_1->cell->voronoi_point == points[1], true);
- BOOST_CHECK_EQUAL(edge3_2->cell->voronoi_point == points[3], true);
+ CHECK_EQUAL_POINTS(edge3_1->cell->voronoi_point, points[1]);
+ CHECK_EQUAL_POINTS(edge3_2->cell->voronoi_point, points[3]);
edge_type *edge4_1 = edge3_1->rot_prev;
edge_type *edge4_2 = edge4_1->twin;
- BOOST_CHECK_EQUAL(edge4_1->cell->voronoi_point == points[3], true);
- BOOST_CHECK_EQUAL(edge4_2->cell->voronoi_point == points[2], true);
+ CHECK_EQUAL_POINTS(edge4_1->cell->voronoi_point, points[3]);
+ CHECK_EQUAL_POINTS(edge4_2->cell->voronoi_point, points[2]);
BOOST_CHECK_EQUAL(edge1_2->twin == edge1_1, true);
BOOST_CHECK_EQUAL(edge2_2->twin == edge2_1, true);
@@ -366,16 +392,17 @@
// Sites: {(x, y) | x = 0 .. 3, y = 0 .. 3}.
BOOST_AUTO_TEST_CASE_TEMPLATE(grid_test1, T, test_types) {
- voronoi_builder<T> test_beach_line;
- std::vector< point_2d<T> > points;
+ typedef T coordinate_type;
+ voronoi_builder<coordinate_type> test_beach_line;
+ std::vector< point_2d<coordinate_type> > 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)));
+ points.push_back(make_point_2d<coordinate_type>(
+ static_cast<coordinate_type>(i), static_cast<coordinate_type>(j)));
test_beach_line.init(points);
test_beach_line.run_sweepline();
- voronoi_output_clipped<T> test_output;
+ voronoi_output_clipped<coordinate_type> test_output;
test_beach_line.clip(test_output);
BOOST_CHECK_EQUAL(test_output.check(), true);
@@ -386,16 +413,17 @@
// Sites: {(x, y) | x = 0 .. 9, y = 0 .. 9}.
BOOST_AUTO_TEST_CASE_TEMPLATE(grid_test2, T, test_types) {
- voronoi_builder<T> test_beach_line;
- std::vector< point_2d<T> > points;
+ typedef T coordinate_type;
+ voronoi_builder<coordinate_type> test_beach_line;
+ std::vector< point_2d<coordinate_type> > 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)));
+ points.push_back(make_point_2d<coordinate_type>(
+ static_cast<coordinate_type>(i), static_cast<coordinate_type>(j)));
test_beach_line.init(points);
test_beach_line.run_sweepline();
- voronoi_output_clipped<T> test_output;
+ voronoi_output_clipped<coordinate_type> test_output;
test_beach_line.clip(test_output);
BOOST_CHECK_EQUAL(test_output.check(), true);
@@ -406,16 +434,17 @@
// Sites: {(x, y) | x = 0 .. 33, y = 0 .. 33}.
BOOST_AUTO_TEST_CASE_TEMPLATE(grid_test3, T, test_types) {
- voronoi_builder<T> test_beach_line;
- std::vector< point_2d<T> > points;
+ typedef T coordinate_type;
+ voronoi_builder<coordinate_type> test_beach_line;
+ std::vector< point_2d<coordinate_type> > 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)));
+ points.push_back(make_point_2d<coordinate_type>(
+ static_cast<coordinate_type>(i), static_cast<coordinate_type>(j)));
test_beach_line.init(points);
test_beach_line.run_sweepline();
- voronoi_output_clipped<T> test_output;
+ voronoi_output_clipped<coordinate_type> test_output;
test_beach_line.clip(test_output);
BOOST_CHECK_EQUAL(test_output.check(), true);
@@ -426,16 +455,17 @@
// Sites: {(x, y) | x = 0 .. 100, y = 0 .. 100}.
BOOST_AUTO_TEST_CASE_TEMPLATE(grid_test4, T, test_types) {
- voronoi_builder<T> test_beach_line;
- std::vector< point_2d<T> > points;
+ typedef T coordinate_type;
+ voronoi_builder<coordinate_type> test_beach_line;
+ std::vector< point_2d<coordinate_type> > 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)));
+ points.push_back(make_point_2d<coordinate_type>(
+ static_cast<coordinate_type>(i), static_cast<coordinate_type>(j)));
test_beach_line.init(points);
test_beach_line.run_sweepline();
- voronoi_output_clipped<T> test_output;
+ voronoi_output_clipped<coordinate_type> test_output;
test_beach_line.clip(test_output);
BOOST_CHECK_EQUAL(test_output.check(), true);
@@ -446,16 +476,17 @@
// Sites: {(x, y) | x = 0 .. 333, y = 0 .. 333}.
BOOST_AUTO_TEST_CASE_TEMPLATE(grid_test5, T, test_types) {
- voronoi_builder<T> test_beach_line;
- std::vector< point_2d<T> > points;
+ typedef T coordinate_type;
+ voronoi_builder<coordinate_type> test_beach_line;
+ std::vector< point_2d<coordinate_type> > 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>(i),
- static_cast<T>(j)));
+ points.push_back(make_point_2d<coordinate_type>(
+ static_cast<coordinate_type>(i), static_cast<coordinate_type>(j)));
test_beach_line.init(points);
test_beach_line.run_sweepline();
- voronoi_output_clipped<T> test_output;
+ voronoi_output_clipped<coordinate_type> test_output;
test_beach_line.clip(test_output);
BOOST_CHECK_EQUAL(test_output.check(), true);
@@ -466,15 +497,17 @@
// Generate 10 random sites 10000 times.
BOOST_AUTO_TEST_CASE_TEMPLATE(random_test1, T, test_types) {
+ typedef T coordinate_type;
srand(static_cast<unsigned int>(time(NULL)));
- voronoi_builder<T> test_beach_line;
- voronoi_output_clipped<T> test_output;
- std::vector< point_2d<T> > points;
+ voronoi_builder<coordinate_type> test_beach_line;
+ voronoi_output_clipped<coordinate_type> test_output;
+ std::vector< point_2d<coordinate_type> > points;
for (int i = 0; i < 10000; i++) {
points.clear();
for (int j = 0; j < 10; j++)
- points.push_back(make_point_2d<T>(static_cast<T>(rand() % 10),
- static_cast<T>(rand() % 10)));
+ points.push_back(make_point_2d<coordinate_type>(
+ static_cast<coordinate_type>(rand() % 10),
+ static_cast<coordinate_type>(rand() % 10)));
test_beach_line.init(points);
test_beach_line.run_sweepline();
test_beach_line.clip(test_output);
@@ -485,15 +518,17 @@
// Generate 100 random sites 1000 times.
BOOST_AUTO_TEST_CASE_TEMPLATE(random_test2, T, test_types) {
+ typedef T coordinate_type;
srand(static_cast<unsigned int>(time(NULL)));
- voronoi_builder<T> test_beach_line;
- voronoi_output_clipped<T> test_output;
- std::vector< point_2d<T> > points;
+ voronoi_builder<coordinate_type> test_beach_line;
+ voronoi_output_clipped<coordinate_type> test_output;
+ std::vector< point_2d<coordinate_type> > points;
for (int i = 0; i < 1000; 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)));
+ points.push_back(make_point_2d<coordinate_type>(
+ static_cast<coordinate_type>(rand() % 100),
+ static_cast<coordinate_type>(rand() % 100)));
test_beach_line.init(points);
test_beach_line.run_sweepline();
test_beach_line.clip(test_output);
@@ -504,15 +539,17 @@
// Generate 1000 random sites 100 times.
BOOST_AUTO_TEST_CASE_TEMPLATE(random_test3, T, test_types) {
+ typedef T coordinate_type;
srand(static_cast<unsigned int>(time(NULL)));
- voronoi_builder<T> test_beach_line;
- voronoi_output_clipped<T> test_output;
- std::vector< point_2d<T> > points;
+ voronoi_builder<coordinate_type> test_beach_line;
+ voronoi_output_clipped<coordinate_type> test_output;
+ std::vector< point_2d<coordinate_type> > points;
for (int i = 0; i < 100; 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)));
+ points.push_back(make_point_2d<coordinate_type>(
+ static_cast<coordinate_type>(rand() % 100),
+ static_cast<coordinate_type>(rand() % 100)));
test_beach_line.init(points);
test_beach_line.run_sweepline();
test_beach_line.clip(test_output);
@@ -523,15 +560,38 @@
// Generate 10000 random sites 10 times.
BOOST_AUTO_TEST_CASE_TEMPLATE(random_test4, T, test_types) {
+ typedef T coordinate_type;
srand(static_cast<unsigned int>(time(NULL)));
- voronoi_builder<T> test_beach_line;
- voronoi_output_clipped<T> test_output;
- std::vector< point_2d<T> > points;
+ voronoi_builder<coordinate_type> test_beach_line;
+ voronoi_output_clipped<coordinate_type> test_output;
+ std::vector< point_2d<coordinate_type> > points;
for (int i = 0; i < 10; i++) {
points.clear();
for (int j = 0; j < 10000; j++)
- points.push_back(make_point_2d<T>(static_cast<T>(rand() % 1000),
- static_cast<T>(rand() % 1000)));
+ points.push_back(make_point_2d<coordinate_type>(\
+ static_cast<coordinate_type>(rand() % 1000),
+ static_cast<coordinate_type>(rand() % 1000)));
+ test_beach_line.init(points);
+ test_beach_line.run_sweepline();
+ test_beach_line.clip(test_output);
+ BOOST_CHECK_EQUAL(test_output.check(), true);
+ test_beach_line.reset();
+ }
+}
+
+// Generate 100000 random sites.
+BOOST_AUTO_TEST_CASE_TEMPLATE(random_test5, T, test_types) {
+ typedef T coordinate_type;
+ srand(static_cast<unsigned int>(time(NULL)));
+ voronoi_builder<coordinate_type> test_beach_line;
+ voronoi_output_clipped<coordinate_type> test_output;
+ std::vector< point_2d<coordinate_type> > points;
+ for (int i = 0; i < 1; i++) {
+ 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)));
test_beach_line.init(points);
test_beach_line.run_sweepline();
test_beach_line.clip(test_output);
@@ -539,3 +599,24 @@
test_beach_line.reset();
}
}
+
+// Generate 1000000 random sites.
+BOOST_AUTO_TEST_CASE_TEMPLATE(random_test6, T, test_types) {
+ typedef T coordinate_type;
+ srand(static_cast<unsigned int>(time(NULL)));
+ voronoi_builder<coordinate_type> test_beach_line;
+ voronoi_output_clipped<coordinate_type> test_output;
+ std::vector< point_2d<coordinate_type> > points;
+ for (int i = 0; i < 1; i++) {
+ 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)));
+ test_beach_line.init(points);
+ test_beach_line.run_sweepline();
+ test_beach_line.clip(test_output);
+ BOOST_CHECK_EQUAL(test_output.check(), true);
+ test_beach_line.reset();
+ }
+}
\ No newline at end of file