Subject: [Boost-commit] svn:boost r63999 - in sandbox/SOC/2010/sweepline: boost/sweepline boost/sweepline/detail libs/sweepline/example libs/sweepline/test
From: sydorchuk.andriy_at_[hidden]
Date: 2010-07-13 17:29:08
Author: asydorchuk
Date: 2010-07-13 17:29:05 EDT (Tue, 13 Jul 2010)
New Revision: 63999
URL: http://svn.boost.org/trac/boost/changeset/63999
Log:
Fixed clipping.
Added clipping unit tests.
Added graphical interface.
Added examples to graphical interface.
Updated algorithm for collinear input data sets.
Added collinear unit tests.
Added:
sandbox/SOC/2010/sweepline/libs/sweepline/example/example_001.txt (contents, props changed)
sandbox/SOC/2010/sweepline/libs/sweepline/example/example_002.txt (contents, props changed)
sandbox/SOC/2010/sweepline/libs/sweepline/example/example_003.txt (contents, props changed)
sandbox/SOC/2010/sweepline/libs/sweepline/example/example_004.txt (contents, props changed)
sandbox/SOC/2010/sweepline/libs/sweepline/example/example_005.txt (contents, props changed)
sandbox/SOC/2010/sweepline/libs/sweepline/example/example_006.txt (contents, props changed)
sandbox/SOC/2010/sweepline/libs/sweepline/example/example_007.txt (contents, props changed)
sandbox/SOC/2010/sweepline/libs/sweepline/example/example_008.txt (contents, props changed)
sandbox/SOC/2010/sweepline/libs/sweepline/example/example_009.txt (contents, props changed)
sandbox/SOC/2010/sweepline/libs/sweepline/example/example_010.txt (contents, props changed)
sandbox/SOC/2010/sweepline/libs/sweepline/example/example_011.txt (contents, props changed)
sandbox/SOC/2010/sweepline/libs/sweepline/example/example_012.txt (contents, props changed)
sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_clipping_test.cpp (contents, props changed)
Properties modified:
sandbox/SOC/2010/sweepline/libs/sweepline/example/ (props changed)
Text files modified:
sandbox/SOC/2010/sweepline/boost/sweepline/detail/voronoi_formation.hpp | 263 +++++++++++++++++++++++++++------------
sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_builder.hpp | 32 ++--
sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_output.hpp | 76 ++++++-----
sandbox/SOC/2010/sweepline/libs/sweepline/example/voronoi_visualizer.cpp | 19 +-
sandbox/SOC/2010/sweepline/libs/sweepline/test/Jamfile.v2 | 1
sandbox/SOC/2010/sweepline/libs/sweepline/test/event_queue_test.cpp | 21 +-
sandbox/SOC/2010/sweepline/libs/sweepline/test/event_types_test.cpp | 67 +++------
sandbox/SOC/2010/sweepline/libs/sweepline/test/node_comparer_test.cpp | 132 ++++++++++----------
sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_builder_test.cpp | 202 ++++++++++++++++++++++++++----
9 files changed, 520 insertions(+), 293 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-13 17:29:05 EDT (Tue, 13 Jul 2010)
@@ -23,11 +23,11 @@
// VORONOI EVENT TYPES ////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////
- template <typename Point2D>
+ template <typename T>
struct beach_line_node;
- template <typename Point2D>
- struct beach_line_node_data;
+ template <typename T>
+ struct half_edge;
template <typename BeachLineNode>
struct node_comparer;
@@ -35,10 +35,11 @@
// Site event type.
// Occurs when sweepline sweeps over one of the initial sites.
// Contains index of a site below the other sorted sites.
- template <typename Point2D>
+ template <typename T>
struct site_event {
public:
- typedef typename Point2D::coordinate_type coordinate_type;
+ typedef T coordinate_type;
+ typedef point_2d<T> Point2D;
site_event() {}
@@ -93,16 +94,14 @@
int site_index_;
};
- template <typename Point2D>
- site_event<Point2D> make_site_event(typename Point2D::coordinate_type x,
- typename Point2D::coordinate_type y,
- int index) {
- return site_event<Point2D>(x, y, index);
+ template <typename T>
+ site_event<T> make_site_event(T x, T y, int index) {
+ return site_event<T>(x, y, index);
}
- template <typename Point2D>
- site_event<Point2D> make_site_event(const Point2D &point, int index) {
- return site_event<Point2D>(point, index);
+ template <typename T>
+ site_event<T> make_site_event(const point_2d<T> &point, int index) {
+ return site_event<T>(point, index);
}
// Circle event type. Occurs when sweepline sweeps over the bottom point of
@@ -115,12 +114,13 @@
// Bottom point of the voronoi circle will be defined as (x + sqrt(r), y).
// Contains reference to the second bisector node (ordered from left to
// right in the beach line) that creates given circle event.
- template <typename Point2D>
+ template <typename T>
struct circle_event {
public:
- typedef typename Point2D::coordinate_type coordinate_type;
- typedef beach_line_node<Point2D> Key;
- typedef beach_line_node_data<Point2D> Value;
+ typedef T coordinate_type;
+ typedef point_2d<T> Point2D;
+ typedef beach_line_node<coordinate_type> Key;
+ typedef half_edge<coordinate_type>* Value;
typedef node_comparer<Key> NodeComparer;
typedef typename std::map< Key, Value, NodeComparer >::iterator beach_line_iterator;
@@ -267,7 +267,7 @@
// If circle point is less then site point return -1.
// If circle point is equal to site point return 0.
// If circle point is greater then site point return 1.
- int compare(const site_event<Point2D> &s_event) const {
+ int compare(const site_event<coordinate_type> &s_event) const {
if (s_event.x() < center_.x())
return 1;
coordinate_type sqr_dif_x = (s_event.x() - center_.x()) * (s_event.x() - center_.x());
@@ -299,9 +299,9 @@
bisector_node_ = iterator;
}
- void set_sites(const site_event<Point2D> site1,
- const site_event<Point2D> site2,
- const site_event<Point2D> site3) {
+ void set_sites(const site_event<coordinate_type> &site1,
+ const site_event<coordinate_type> &site2,
+ const site_event<coordinate_type> &site3) {
sites_[0] = site1;
sites_[1] = site2;
sites_[2] = site3;
@@ -311,7 +311,7 @@
return bisector_node_;
}
- const site_event<Point2D>* get_sites() const {
+ const site_event<coordinate_type>* get_sites() const {
return sites_;
}
@@ -319,21 +319,17 @@
Point2D center_;
coordinate_type sqr_radius_;
beach_line_iterator bisector_node_;
- site_event<Point2D> sites_[3];
+ site_event<coordinate_type> sites_[3];
};
- template <typename Point2D>
- circle_event<Point2D> make_circle_event(
- typename Point2D::coordinate_type c_x,
- typename Point2D::coordinate_type c_y,
- typename Point2D::coordinate_type sqr_radius) {
- return circle_event<Point2D>(c_x, c_y, sqr_radius);
+ template <typename T>
+ circle_event<T> make_circle_event(T c_x, T c_y, T sqr_radius) {
+ return circle_event<T>(c_x, c_y, sqr_radius);
}
- template <typename Point2D>
- circle_event<Point2D> make_circle_event(Point2D center,
- typename Point2D::coordinate_type sqr_radius) {
- return circle_event<Point2D>(center, sqr_radius);
+ template <typename T>
+ circle_event<T> make_circle_event(point_2d<T> center, T sqr_radius) {
+ return circle_event<T>(center, sqr_radius);
}
///////////////////////////////////////////////////////////////////////////
@@ -341,11 +337,12 @@
///////////////////////////////////////////////////////////////////////////
// Event queue data structure, processes circle events.
- template <typename Point2D>
+ template <typename T>
class circle_events_queue {
public:
- typedef typename Point2D::coordinate_type coordinate_type;
- typedef circle_event<Point2D> circle_event_type;
+ typedef T coordinate_type;
+ typedef point_2d<T> Point2D;
+ typedef circle_event<T> circle_event_type;
circle_events_queue() {}
@@ -414,11 +411,12 @@
// x = ((y - y1)^2 + x1^2 - x0^2) / (2*(x1 - x0)).
// In general case two arcs will create two different bisectors. That's why
// the order of arcs is important to define unique bisector.
- template <typename Point2D>
+ template <typename T>
struct beach_line_node {
public:
- typedef typename Point2D::coordinate_type coordinate_type;
- typedef site_event<Point2D> site_event_type;
+ typedef T coordinate_type;
+ typedef point_2d<T> Point2D;
+ typedef site_event<T> site_event_type;
beach_line_node() {}
@@ -494,18 +492,6 @@
site_event_type right_site_;
};
- template <typename Point2D>
- struct half_edge;
-
- // Represents edge data sturcture (bisector segment), which is
- // associated with beach line node key in the binary search tree.
- template <typename Point2D>
- struct beach_line_node_data {
- half_edge<Point2D> *edge;
-
- explicit beach_line_node_data(half_edge<Point2D> *new_edge) : edge(new_edge) {}
- };
-
template <typename BeachLineNode>
struct node_comparer {
public:
@@ -586,14 +572,17 @@
// Voronoi record data structure. May represent voronoi cell or
// voronoi vertex. Contains pointer to any incident edge, point
// coordinates and number of incident edges.
- template <typename Point2D>
+ template <typename T>
struct voronoi_record {
- half_edge<Point2D> *incident_edge;
+ typedef T coordinate_type;
+ typedef point_2d<T> Point2D;
+
+ half_edge<coordinate_type> *incident_edge;
Point2D voronoi_point;
int num_incident_edges;
- typename std::list< voronoi_record<Point2D> >::iterator voronoi_record_it;
+ typename std::list< voronoi_record<coordinate_type> >::iterator voronoi_record_it;
- voronoi_record(const Point2D &point, half_edge<Point2D>* edge) :
+ voronoi_record(const Point2D &point, half_edge<coordinate_type>* edge) :
incident_edge(edge),
voronoi_point(point),
num_incident_edges(0) {}
@@ -607,11 +596,13 @@
// around start point;
// 5) pointer to twin half-edge;
// 6) pointer to clipped edge during clipping.
- template <typename Point2D>
+ template <typename T>
struct half_edge {
- typedef voronoi_record<Point2D> voronoi_record_type;
- typedef half_edge<Point2D> half_edge_type;
- typedef half_edge_clipped<Point2D> half_edge_clipped_type;
+ typedef T coordinate_type;
+ typedef point_2d<T> Point2D;
+ typedef voronoi_record<coordinate_type> voronoi_record_type;
+ typedef half_edge<coordinate_type> half_edge_type;
+ typedef half_edge_clipped<coordinate_type> half_edge_clipped_type;
voronoi_record_type *cell;
voronoi_record_type *start_point;
@@ -638,23 +629,26 @@
// Voronoi output data structure based on the half-edges.
// Contains vector of voronoi cells, doubly linked list of
// voronoi vertices and voronoi edges.
- template <typename Point2D>
+ template <typename T>
class voronoi_output {
public:
- typedef typename Point2D::coordinate_type coordinate_type;
- typedef typename detail::site_event<Point2D> site_event_type;
- typedef typename detail::circle_event<Point2D> circle_event_type;
-
- typedef voronoi_record<Point2D> voronoi_record_type;
- typedef voronoi_record_clipped<Point2D> clipped_voronoi_record_type;
- typedef half_edge<Point2D> edge_type;
- typedef half_edge_clipped<Point2D> clipped_edge_type;
+ typedef T coordinate_type;
+ typedef point_2d<T> Point2D;
+ typedef typename detail::site_event<coordinate_type> site_event_type;
+ typedef typename detail::circle_event<coordinate_type> circle_event_type;
+ typedef voronoi_record<coordinate_type> voronoi_record_type;
+ typedef voronoi_record_clipped<coordinate_type> clipped_voronoi_record_type;
typedef std::list<voronoi_record_type> voronoi_records_type;
- typedef std::list<edge_type> voronoi_edges_type;
typedef typename voronoi_records_type::iterator voronoi_iterator_type;
typedef typename voronoi_records_type::const_iterator voronoi_const_iterator_type;
+ typedef half_edge<coordinate_type> edge_type;
+ typedef half_edge_clipped<coordinate_type> clipped_edge_type;
+ typedef std::list<edge_type> voronoi_edges_type;
+ typedef typename voronoi_edges_type::iterator edges_iterator_type;
+
+
enum kEdgeType {
SEGMENT = 0,
RAY = 1,
@@ -685,6 +679,18 @@
num_vertex_records_ = 0;
}
+ // Update voronoi output in case of single site input.
+ void process_single_site(const site_event_type &site) {
+ // Update counters.
+ num_cell_records_++;
+
+ // Update bounding rectangle.
+ voronoi_rect_ = BRect<coordinate_type>(site.get_point(), site.get_point());
+
+ // Update cell records.
+ cell_records_.push_back(voronoi_record_type(site.get_point(), NULL));
+ }
+
// Inserts new half-edge into the output data structure during site
// event processing. Takes as input left and right sites of the new
// beach line node and returns pointer to the new half-edge.
@@ -712,7 +718,7 @@
cell_records_.end(), voronoi_record_type(site1.get_point(), &edge1)));
cell_records_.back().num_incident_edges++;
num_cell_records_++;
- voronoi_rect_ = BRect<Point2D>(site1.get_point(), site1.get_point());
+ voronoi_rect_ = BRect<coordinate_type>(site1.get_point(), site1.get_point());
}
// Update bounding rectangle.
@@ -824,13 +830,39 @@
return num_edges_;
}
- const BRect<Point2D> &get_bounding_rectangle() const {
+ const BRect<coordinate_type> &get_bounding_rectangle() const {
return voronoi_rect_;
}
void simplify() {
- typename std::list<edge_type>::iterator edge_it1;
- typename std::list<edge_type>::iterator edge_it = edges_.begin();
+ edges_iterator_type edge_it1;
+ edges_iterator_type edge_it = edges_.begin();
+
+ // Return in case of collinear sites input.
+ if (num_vertex_records_ == 0) {
+ if (edge_it == edges_.end())
+ return;
+
+ edge_type *edge1 = &(*edge_it);
+ edge1->next = edge1->prev = edge1;
+ edge_it++;
+ edge1 = &(*edge_it);
+ edge_it++;
+
+ while (edge_it != edges_.end()) {
+ edge_type *edge2 = &(*edge_it);
+ edge_it++;
+
+ edge1->next = edge1->prev = edge2;
+ edge2->next = edge2->prev = edge1;
+
+ edge1 = &(*edge_it);
+ edge_it++;
+ }
+
+ edge1->next = edge1->prev = edge1;
+ return;
+ }
// Iterate over all edges and remove degeneracies.
while (edge_it != edges_.end()) {
@@ -890,7 +922,7 @@
}
- void clip(voronoi_output_clipped<Point2D> &clipped_output) const {
+ void clip(voronoi_output_clipped<coordinate_type> &clipped_output) {
coordinate_type x_len = (voronoi_rect_.x_max - voronoi_rect_.x_min);
coordinate_type y_len = (voronoi_rect_.y_max - voronoi_rect_.y_min);
coordinate_type x_mid = (voronoi_rect_.x_max + voronoi_rect_.x_min) /
@@ -902,18 +934,77 @@
if (offset < y_len)
offset = y_len;
offset *= static_cast<coordinate_type>(0.55);
- BRect<Point2D> new_brect(x_mid - offset, y_mid - offset,
+
+ if (offset == static_cast<coordinate_type>(0))
+ offset = 0.5;
+
+ BRect<coordinate_type> new_brect(x_mid - offset, y_mid - offset,
x_mid + offset, y_mid + offset);
clip(new_brect, clipped_output);
}
- void clip(const BRect<Point2D> &brect,
- voronoi_output_clipped<Point2D> &clipped_output) const {
+ void clip(const BRect<coordinate_type> &brect,
+ voronoi_output_clipped<coordinate_type> &clipped_output) {
if (!brect.valid())
return;
clipped_output.reset();
clipped_output.set_bounding_rectangle(brect);
+
+ // collinear input sites case.
+ if (num_vertex_records_ == 0) {
+ // Return in case of single site input.
+ if (num_cell_records_ == 1) {
+ clipped_output.add_cell(cell_records_.begin()->voronoi_point);
+ return;
+ }
+
+ edges_iterator_type edge_it = edges_.begin();
+ while (edge_it != edges_.end()) {
+ edge_type *cur_edge = &(*edge_it);
+ edge_it++;
+ edge_type *cur_twin_edge = &(*edge_it);
+ edge_it++;
+
+ std::vector<Point2D> intersections;
+ const Point2D &site1 = cur_edge->cell->voronoi_point;
+ const Point2D &site2 = cur_twin_edge->cell->voronoi_point;
+ Point2D origin((site1.x() + site2.x()) * static_cast<coordinate_type>(0.5),
+ (site1.y() + site2.y()) * static_cast<coordinate_type>(0.5));
+ Point2D direction(site1.y() - site2.y(), site2.x() - site1.x());
+ find_intersections(origin, direction, LINE, brect, intersections);
+ if (intersections.size() == 2) {
+ // Add new clipped edges.
+ clipped_edge_type &new_edge = clipped_output.add_edge();
+ clipped_edge_type &new_twin_edge = clipped_output.add_edge();
+
+ // Update twin pointers.
+ new_edge.twin = &new_twin_edge;
+ new_twin_edge.twin = &new_edge;
+
+ // Update clipped edge pointers.
+ cur_edge->clipped_edge = &new_edge;
+ cur_twin_edge->clipped_edge = &new_twin_edge;
+ // Add new boundary vertex.
+ clipped_voronoi_record_type &new_vertex1 =
+ clipped_output.add_boundary_vertex(intersections[0]);
+ new_vertex1.incident_edge = &new_edge;
+ new_vertex1.num_incident_edges = 1;
+
+ // Add new boundary vertex
+ clipped_voronoi_record_type &new_vertex2 =
+ clipped_output.add_boundary_vertex(intersections[1]);
+ new_vertex2.incident_edge = &new_twin_edge;
+ new_vertex2.num_incident_edges = 1;
+
+ // Update edge pointers.
+ new_edge.start_point = new_twin_edge.end_point = &new_vertex1;
+ new_edge.end_point = new_twin_edge.start_point = &new_vertex2;
+ new_edge.rot_next = new_edge.rot_prev = &new_edge;
+ new_twin_edge.rot_next = new_twin_edge.rot_prev = &new_twin_edge;
+ }
+ }
+ } else {
// Iterate over all voronoi vertices.
for (voronoi_const_iterator_type vertex_it = vertex_records_.begin();
vertex_it != vertex_records_.end(); vertex_it++) {
@@ -1003,10 +1094,11 @@
// Find all intersections of the current
// edge with bounding box of the clipped output.
- find_intersections(cur_vertex_point, direction, etype, brect, intersections);
+ bool corner_intersection = find_intersections(cur_vertex_point, direction,
+ etype, brect, intersections);
// Process edge if there are any intersections.
- if (!intersections.empty()) {
+ if (!corner_intersection && !intersections.empty()) {
// Add new vertex to the clipped output.
clipped_voronoi_record_type &new_vertex =
clipped_output.add_boundary_vertex(intersections[0]);
@@ -1051,6 +1143,7 @@
} while (cur_edge != vertex_it->incident_edge);
}
}
+ }
// Iterate over all voronoi cells.
for (voronoi_const_iterator_type cell_it = cell_records_.begin();
@@ -1090,8 +1183,8 @@
}
// Find edge(segment, ray, line) rectangle intersetion points.
- void find_intersections(const Point2D &origin, const Point2D &direction,
- kEdgeType edge_type, const BRect<Point2D> &brect,
+ bool find_intersections(const Point2D &origin, const Point2D &direction,
+ kEdgeType edge_type, const BRect<coordinate_type> &brect,
std::vector<Point2D> &intersections) const {
coordinate_type half = static_cast<coordinate_type>(0.5);
@@ -1117,7 +1210,7 @@
// Intersection check.
if (lexpr > rexpr)
- return;
+ return false;
// Intersection parameters:
// origin + fT[i] * direction = intersections point, i = 0 .. 1.
@@ -1135,9 +1228,11 @@
if (fT0_used && check_extent(fT0, edge_type))
intersections.push_back(make_point_2d(origin.x() + fT0 * direction.x(),
origin.y() + fT0 * direction.y()));
- if (fT1_used && check_extent(fT1, edge_type))
+ if (fT1_used && fT0 != fT1 && check_extent(fT1, edge_type))
intersections.push_back(make_point_2d(origin.x() + fT1 * direction.x(),
origin.y() + fT1 * direction.y()));
+
+ return fT0_used && fT1_used && (fT0 == fT1);
}
private:
@@ -1234,7 +1329,7 @@
int num_vertex_records_;
int num_edges_;
- BRect<Point2D> voronoi_rect_;
+ BRect<coordinate_type> voronoi_rect_;
// Disallow copy constructor and operator=
voronoi_output(const voronoi_output&);
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-13 17:29:05 EDT (Tue, 13 Jul 2010)
@@ -19,9 +19,9 @@
template <typename T>
class voronoi_builder {
public:
+ typedef T coordinate_type;
typedef point_2d<T> Point2D;
- typedef typename Point2D::coordinate_type coordinate_type;
- typedef detail::voronoi_output<Point2D> Output;
+ typedef detail::voronoi_output<coordinate_type> Output;
typedef typename Output::edge_type edge_type;
voronoi_builder() {
@@ -57,6 +57,7 @@
int skip = 0;
if (site_events_.size() == 1) {
+ output_.process_single_site(site_events_[0]);
skip = 1;
site_events_iterator_++;
} else {
@@ -74,7 +75,7 @@
site_events_iterator_++;
} else {
// Init beach line with sites situated on the same vertical line.
- init_beach_line_colinear_sites();
+ init_beach_line_collinear_sites();
}
}
}
@@ -107,26 +108,27 @@
output_.simplify();
}
- const BRect<Point2D> &get_bounding_rectangle() const {
+ const BRect<coordinate_type> &get_bounding_rectangle() const {
return output_.get_bounding_rectangle();
}
- void clip(voronoi_output_clipped<Point2D> &clipped_output) {
+ void clip(voronoi_output_clipped<coordinate_type> &clipped_output) {
output_.clip(clipped_output);
}
- void clip(const BRect<Point2D> &brect, voronoi_output_clipped<Point2D> &clipped_output) {
+ void clip(const BRect<coordinate_type> &brect,
+ voronoi_output_clipped<coordinate_type> &clipped_output) {
output_.clip(brect, clipped_output);
}
protected:
- typedef typename detail::site_event<Point2D> site_event_type;
- typedef typename detail::circle_event<Point2D> circle_event_type;
+ typedef typename detail::site_event<coordinate_type> site_event_type;
+ typedef typename detail::circle_event<coordinate_type> circle_event_type;
typedef typename std::vector<site_event_type>::const_iterator site_events_iterator;
- typedef typename detail::circle_events_queue<Point2D> CircleEventsQueue;
- typedef typename detail::beach_line_node<Point2D> Key;
- typedef typename detail::beach_line_node_data<Point2D> Value;
+ 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::node_comparer<Key> NodeComparer;
typedef std::map< Key, Value, NodeComparer > BeachLine;
typedef typename std::map< Key, Value, NodeComparer >::iterator beach_line_iterator;
@@ -148,7 +150,7 @@
beach_line_.insert(std::pair<Key, Value>(new_right_node, Value(edge->twin)));
}
- void init_beach_line_colinear_sites() {
+ void init_beach_line_collinear_sites() {
site_events_iterator it_first = site_events_.begin();
site_events_iterator it_second = site_events_.begin();
it_second++;
@@ -262,8 +264,8 @@
// 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.edge, bisector2.edge);
- it_first->second.edge = edge;
+ bisector1, bisector2);
+ it_first->second = edge;
beach_line_.erase(it_last);
it_last = it_first;
@@ -326,7 +328,7 @@
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<Point2D>(c_x, c_y, sqr_radius);
+ c_event = detail::make_circle_event<coordinate_type>(c_x, c_y, sqr_radius);
c_event.set_sites(site1, site2, site3);
return true;
}
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-13 17:29:05 EDT (Tue, 13 Jul 2010)
@@ -88,10 +88,11 @@
///////////////////////////////////////////////////////////////////////////
// Bounding rectangle data structure.
- template <typename Point2D>
+ template <typename T>
struct BRect {
public:
- typedef typename Point2D::coordinate_type coordinate_type;
+ typedef T coordinate_type;
+ typedef point_2d<T> Point2D;
coordinate_type x_min;
coordinate_type y_min;
@@ -131,19 +132,22 @@
}
};
- template <typename Point2D>
+ template <typename T>
struct half_edge_clipped;
// Voronoi record data structure. May represent voronoi cell or
// voronoi vertex. Contains pointer to any incident edge, point
// coordinates and number of incident edges.
- template <typename Point2D>
+ template <typename T>
struct voronoi_record_clipped {
- half_edge_clipped<Point2D> *incident_edge;
+ typedef T coordinate_type;
+ typedef point_2d<T> Point2D;
+
+ half_edge_clipped<coordinate_type> *incident_edge;
Point2D voronoi_point;
int num_incident_edges;
- voronoi_record_clipped(const Point2D &point, half_edge_clipped<Point2D>* edge) :
+ voronoi_record_clipped(const Point2D &point, half_edge_clipped<coordinate_type>* edge) :
incident_edge(edge),
voronoi_point(point),
num_incident_edges(0) {}
@@ -156,10 +160,12 @@
// 4) pointers to previous/next half-edges rotated
// around start point;
// 5) pointer to twin half-edge.
- template <typename Point2D>
+ template <typename T>
struct half_edge_clipped {
- typedef voronoi_record_clipped<Point2D> voronoi_record_type;
- typedef half_edge_clipped<Point2D> half_edge_type;
+ typedef T coordinate_type;
+ typedef point_2d<T> Point2D;
+ typedef voronoi_record_clipped<coordinate_type> voronoi_record_type;
+ typedef half_edge_clipped<coordinate_type> half_edge_type;
voronoi_record_type *cell;
voronoi_record_type *start_point;
@@ -181,15 +187,16 @@
twin(NULL) {}
};
- template <typename Point2D>
+ template <typename T>
class voronoi_output_clipped {
public:
- typedef typename Point2D::coordinate_type coordinate_type;
- typedef voronoi_record_clipped<Point2D> voronoi_record_type;
- typedef half_edge_clipped<Point2D> edge_type;
+ typedef T coordinate_type;
+ typedef point_2d<T> Point2D;
+ typedef voronoi_record_clipped<coordinate_type> voronoi_record_type;
typedef std::list<voronoi_record_type> voronoi_records_type;
typedef typename voronoi_records_type::iterator voronoi_iterator_type;
typedef typename voronoi_records_type::const_iterator voronoi_const_iterator_type;
+ typedef half_edge_clipped<coordinate_type> edge_type;
typedef std::list<edge_type> voronoi_edges_type;
typedef typename voronoi_edges_type::iterator edges_iterator_type;
typedef typename voronoi_edges_type::const_iterator edges_const_iterator_type;
@@ -210,11 +217,11 @@
num_edges_ = 0;
}
- void set_bounding_rectangle(const BRect<Point2D> &brect) {
+ void set_bounding_rectangle(const BRect<coordinate_type> &brect) {
brect_ = brect;
}
- const BRect<Point2D> &get_bounding_rectangle() {
+ const BRect<coordinate_type> &get_bounding_rectangle() {
return brect_;
}
@@ -290,23 +297,24 @@
voronoi_const_iterator_type cell_it;
for (cell_it = cell_records_.begin(); cell_it != cell_records_.end(); cell_it++) {
const edge_type *edge = cell_it->incident_edge;
- do {
- if (edge->next->prev != edge)
- return false;
- if (edge->cell != &(*cell_it))
- return false;
- if (edge->start_point != NULL &&
- edge->end_point != NULL &&
- edge->end_point == edge->next->start_point &&
- edge->next->end_point != NULL) {
- const Point2D &vertex1 = edge->start_point->voronoi_point;
- const Point2D &vertex2 = edge->end_point->voronoi_point;
- const Point2D &vertex3 = edge->next->end_point->voronoi_point;
- if (check_orientation(vertex1, vertex2, vertex3) != LEFT_ORIENTATION)
+ if (edge)
+ do {
+ if (edge->next->prev != edge)
return false;
- }
- edge = edge->next;
- } while(edge != cell_it->incident_edge);
+ if (edge->cell != &(*cell_it))
+ return false;
+ if (edge->start_point != NULL &&
+ edge->end_point != NULL &&
+ edge->end_point == edge->next->start_point &&
+ edge->next->end_point != NULL) {
+ const Point2D &vertex1 = edge->start_point->voronoi_point;
+ const Point2D &vertex2 = edge->end_point->voronoi_point;
+ const Point2D &vertex3 = edge->next->end_point->voronoi_point;
+ if (check_orientation(vertex1, vertex2, vertex3) != LEFT_ORIENTATION)
+ return false;
+ }
+ edge = edge->next;
+ } while(edge != cell_it->incident_edge);
}
return true;
}
@@ -410,7 +418,7 @@
enum kOrientation {
LEFT_ORIENTATION = 1,
RIGHT_ORIENTATION = -1,
- COLINEAR = 0,
+ collinear = 0,
};
int check_orientation(const Point2D &point1,
@@ -422,7 +430,7 @@
return LEFT_ORIENTATION;
else if (a < b)
return RIGHT_ORIENTATION;
- return COLINEAR;
+ return collinear;
}
voronoi_records_type cell_records_;
@@ -433,7 +441,7 @@
int num_vertex_records_;
int num_edges_;
- BRect<Point2D> brect_;
+ BRect<coordinate_type> brect_;
// Disallow copy constructor and operator=
voronoi_output_clipped(const voronoi_output_clipped&);
Added: sandbox/SOC/2010/sweepline/libs/sweepline/example/example_001.txt
==============================================================================
--- (empty file)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/example/example_001.txt 2010-07-13 17:29:05 EDT (Tue, 13 Jul 2010)
@@ -0,0 +1,2 @@
+1
+0 0
\ No newline at end of file
Added: sandbox/SOC/2010/sweepline/libs/sweepline/example/example_002.txt
==============================================================================
--- (empty file)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/example/example_002.txt 2010-07-13 17:29:05 EDT (Tue, 13 Jul 2010)
@@ -0,0 +1,3 @@
+2
+0 0
+1 0
\ No newline at end of file
Added: sandbox/SOC/2010/sweepline/libs/sweepline/example/example_003.txt
==============================================================================
--- (empty file)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/example/example_003.txt 2010-07-13 17:29:05 EDT (Tue, 13 Jul 2010)
@@ -0,0 +1,3 @@
+2
+0 0
+0 1
\ No newline at end of file
Added: sandbox/SOC/2010/sweepline/libs/sweepline/example/example_004.txt
==============================================================================
--- (empty file)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/example/example_004.txt 2010-07-13 17:29:05 EDT (Tue, 13 Jul 2010)
@@ -0,0 +1,3 @@
+2
+0 0
+1 1
\ No newline at end of file
Added: sandbox/SOC/2010/sweepline/libs/sweepline/example/example_005.txt
==============================================================================
--- (empty file)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/example/example_005.txt 2010-07-13 17:29:05 EDT (Tue, 13 Jul 2010)
@@ -0,0 +1,11 @@
+10
+0 0
+0 1
+0 2
+0 3
+0 4
+0 -1
+0 -2
+0 -3
+0 -4
+0 -5
\ No newline at end of file
Added: sandbox/SOC/2010/sweepline/libs/sweepline/example/example_006.txt
==============================================================================
--- (empty file)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/example/example_006.txt 2010-07-13 17:29:05 EDT (Tue, 13 Jul 2010)
@@ -0,0 +1,11 @@
+10
+0 0
+1 0
+2 0
+3 0
+4 0
+5 0
+-1 0
+-2 0
+-3 0
+-4 0
\ No newline at end of file
Added: sandbox/SOC/2010/sweepline/libs/sweepline/example/example_007.txt
==============================================================================
--- (empty file)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/example/example_007.txt 2010-07-13 17:29:05 EDT (Tue, 13 Jul 2010)
@@ -0,0 +1,12 @@
+10
+0 0
+1 1
+2 2
+3 3
+4 4
+5 5
+6 6
+7 7
+8 8
+9 9
+10 10
\ No newline at end of file
Added: sandbox/SOC/2010/sweepline/libs/sweepline/example/example_008.txt
==============================================================================
--- (empty file)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/example/example_008.txt 2010-07-13 17:29:05 EDT (Tue, 13 Jul 2010)
@@ -0,0 +1,11 @@
+10
+-4.6 -3.7
+-4.0 -3.0
+-3.4 -2.3
+-2.8 -1.6
+-2.2 -0.9
+-1.6 -0.2
+-1.0 0.5
+-0.4 1.2
+0.2 1.9
+0.8 2.6
\ No newline at end of file
Added: sandbox/SOC/2010/sweepline/libs/sweepline/example/example_009.txt
==============================================================================
--- (empty file)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/example/example_009.txt 2010-07-13 17:29:05 EDT (Tue, 13 Jul 2010)
@@ -0,0 +1,11 @@
+10
+0.33333 0.11111
+0.66666 0.0
+0.99999 -0.11111
+1.33332 -0.22222
+1.66665 -0.33333
+1.99998 -0.44444
+2.33331 -0.55555
+2.66664 -0.66666
+2.99997 -0.77777
+3.33330 -0.88888
\ No newline at end of file
Added: sandbox/SOC/2010/sweepline/libs/sweepline/example/example_010.txt
==============================================================================
--- (empty file)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/example/example_010.txt 2010-07-13 17:29:05 EDT (Tue, 13 Jul 2010)
@@ -0,0 +1,4 @@
+3
+0 0
+200.5 200.5
+1002.5 1002.5
\ No newline at end of file
Added: sandbox/SOC/2010/sweepline/libs/sweepline/example/example_011.txt
==============================================================================
--- (empty file)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/example/example_011.txt 2010-07-13 17:29:05 EDT (Tue, 13 Jul 2010)
@@ -0,0 +1,4 @@
+3
+0 0
+0 4
+1 1
\ No newline at end of file
Added: sandbox/SOC/2010/sweepline/libs/sweepline/example/example_012.txt
==============================================================================
--- (empty file)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/example/example_012.txt 2010-07-13 17:29:05 EDT (Tue, 13 Jul 2010)
@@ -0,0 +1,5 @@
+4
+0 0
+0 1
+1 0
+1 1
\ 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-13 17:29:05 EDT (Tue, 13 Jul 2010)
@@ -1,4 +1,4 @@
-// Boost sweepline library visualizer_main.cpp file
+// Boost sweepline library voronoi_visualizer.cpp file
// Copyright Andrii Sydorchuk 2010.
// Distributed under the Boost Software License, Version 1.0.
@@ -105,18 +105,19 @@
glMatrixMode(GL_MODELVIEW);
}
- typedef boost::sweepline::point_2d<double> Point2D;
- typedef boost::sweepline::voronoi_output_clipped<Point2D>::voronoi_records_type
+ typedef double coordinate_type;
+ typedef boost::sweepline::point_2d<coordinate_type> Point2D;
+ typedef boost::sweepline::voronoi_output_clipped<coordinate_type>::voronoi_records_type
voronoi_records_type;
- typedef boost::sweepline::voronoi_output_clipped<Point2D>::voronoi_edges_type
+ typedef boost::sweepline::voronoi_output_clipped<coordinate_type>::voronoi_edges_type
voronoi_edges_type;
- typedef boost::sweepline::voronoi_output_clipped<Point2D>::voronoi_const_iterator_type
+ typedef boost::sweepline::voronoi_output_clipped<coordinate_type>::voronoi_const_iterator_type
voronoi_const_iterator_type;
- typedef boost::sweepline::voronoi_output_clipped<Point2D>::edges_const_iterator_type
+ typedef boost::sweepline::voronoi_output_clipped<coordinate_type>::edges_const_iterator_type
edges_const_iterator_type;
- boost::sweepline::voronoi_builder<double> voronoi_builder_;
- boost::sweepline::BRect<Point2D> brect_;
- boost::sweepline::voronoi_output_clipped<Point2D> voronoi_output_;
+ boost::sweepline::voronoi_builder<coordinate_type> voronoi_builder_;
+ boost::sweepline::BRect<coordinate_type> brect_;
+ boost::sweepline::voronoi_output_clipped<coordinate_type> voronoi_output_;
};
class MainWindow : public QWidget {
Modified: sandbox/SOC/2010/sweepline/libs/sweepline/test/Jamfile.v2
==============================================================================
--- sandbox/SOC/2010/sweepline/libs/sweepline/test/Jamfile.v2 (original)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/test/Jamfile.v2 2010-07-13 17:29:05 EDT (Tue, 13 Jul 2010)
@@ -15,5 +15,6 @@
[ run event_queue_test.cpp ]
[ run event_types_test.cpp ]
[ run node_comparer_test.cpp ]
+ [ run voronoi_clipping_test.cpp ]
[ run voronoi_builder_test.cpp ]
;
\ No newline at end of file
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-13 17:29:05 EDT (Tue, 13 Jul 2010)
@@ -22,9 +22,7 @@
TOP.y() == static_cast<T>(Y), true)
BOOST_AUTO_TEST_CASE_TEMPLATE(event_queue_test1, T, test_types) {
- typedef point_2d<T> Point2D;
-
- detail::circle_events_queue< point_2d<T> > event_q;
+ detail::circle_events_queue<T> event_q;
BOOST_CHECK_EQUAL(event_q.empty(), true);
event_q.reset();
@@ -32,7 +30,7 @@
for (int i = 0; i < 10; i++) {
T x = static_cast<T>(-i);
T y = static_cast<T>(10-i);
- event_q.push(detail::make_circle_event<Point2D>(x, y, static_cast<T>(100)));
+ event_q.push(detail::make_circle_event<T>(x, y, static_cast<T>(100)));
}
for (int i = 0; i < 10; i++) {
@@ -44,19 +42,16 @@
}
BOOST_AUTO_TEST_CASE_TEMPLATE(event_queue_test2, T, test_types) {
- typedef point_2d<T> Point2D;
- typedef detail::circle_event<Point2D> circle_event_type;
+ typedef detail::circle_event<T> circle_event_type;
- detail::circle_events_queue< point_2d<T> > event_q;
- detail::site_event<Point2D> temp_site =
- detail::make_site_event<Point2D>(static_cast<T>(0),
- static_cast<T>(0),
- 0);
+ detail::circle_events_queue<T> event_q;
+ detail::site_event<T> temp_site =
+ detail::make_site_event<T>(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);
- circle_event_type c = detail::make_circle_event<Point2D>(x, y, static_cast<T>(0));
+ 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);
}
@@ -64,7 +59,7 @@
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<Point2D>(x, y, static_cast<T>(0));
+ 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);
}
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-13 17:29:05 EDT (Tue, 13 Jul 2010)
@@ -44,102 +44,83 @@
}
BOOST_AUTO_TEST_CASE_TEMPLATE(site_event_test1, T, test_types) {
- typedef point_2d<T> Point2D;
-
- site_event<Point2D> site1 = make_site_event<Point2D>(static_cast<T>(1),
- static_cast<T>(1.05),
- 0);
- site_event<Point2D> site2;
+ site_event<T> site1 = make_site_event<T>(static_cast<T>(1), static_cast<T>(1.05), 0);
+ site_event<T> site2;
BOOST_CHECK_EQUAL(site1.x(), static_cast<T>(1));
BOOST_CHECK_EQUAL(site1.y(), static_cast<T>(1.05));
BOOST_CHECK_EQUAL(site1.get_site_index(), 0);
- site2 = make_site_event<Point2D>(static_cast<T>(0.999999), static_cast<T>(1), 1);
+ site2 = make_site_event<T>(static_cast<T>(0.999999), static_cast<T>(1), 1);
bool arr1[] = { false, true, false, true, false, true };
EVENT_TYPES_CHECK_COMPARISON(site1, site2, arr1);
- site2 = make_site_event<Point2D>(static_cast<T>(1), static_cast<T>(1.1), 1);
+ site2 = make_site_event<T>(static_cast<T>(1), static_cast<T>(1.1), 1);
bool arr2[] = { true, false, true, false, false, true };
EVENT_TYPES_CHECK_COMPARISON(site1, site2, arr2);
- site2 = make_site_event<Point2D>(static_cast<T>(1), static_cast<T>(1.05), 1);
+ site2 = make_site_event<T>(static_cast<T>(1), static_cast<T>(1.05), 1);
bool arr3[] = { false, false, true, true, true, false };
EVENT_TYPES_CHECK_COMPARISON(site1, site2, arr3);
}
BOOST_AUTO_TEST_CASE_TEMPLATE(circle_event_test1, T, test_types) {
- typedef point_2d<T> Point2D;
-
- circle_event<Point2D> circle1 = make_circle_event<Point2D>(static_cast<T>(1),
- static_cast<T>(2),
- static_cast<T>(4));
- site_event<Point2D> temp_site = make_site_event<Point2D>(static_cast<T>(0),
- static_cast<T>(0),
- 0);
+ 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<Point2D> circle2;
+ circle_event<T> circle2;
BOOST_CHECK_EQUAL(circle1.x(), static_cast<T>(1));
BOOST_CHECK_EQUAL(circle1.y(), static_cast<T>(2));
BOOST_CHECK_EQUAL(circle1.get_sqr_radius(), static_cast<T>(4));
- circle2 = make_circle_event<Point2D>(static_cast<T>(1),
- static_cast<T>(2),
- 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);
bool arr1[] = { false, false, true, true, true, false };
EVENT_TYPES_CHECK_COMPARISON(circle1, circle2, arr1);
- circle2 = make_circle_event<Point2D>(static_cast<T>(1),
- static_cast<T>(3),
- static_cast<T>(4));
+ 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<Point2D>(static_cast<T>(1),
- static_cast<T>(2),
- static_cast<T>(5));
+ 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);
- circle2 = make_circle_event<Point2D>(static_cast<T>(0),
- static_cast<T>(2),
- static_cast<T>(4));
+ 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<Point2D>(static_cast<T>(0),
- static_cast<T>(0),
- static_cast<T>(10));
+ 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);
}
BOOST_AUTO_TEST_CASE_TEMPLATE(circle_event_test2, T, test_types) {
- typedef point_2d<T> Point2D;
- circle_event<Point2D> circle = make_circle_event<Point2D>(static_cast<T>(1),
- static_cast<T>(2),
- static_cast<T>(4));
- site_event<Point2D> site;
+ circle_event<T> circle = make_circle_event<T>(static_cast<T>(1),
+ static_cast<T>(2),
+ static_cast<T>(4));
+ site_event<T> site;
- site = make_site_event<Point2D>(0, 100, 0);
+ site = make_site_event<T>(static_cast<T>(0), static_cast<T>(100), 0);
BOOST_CHECK_EQUAL(circle.compare(site), 1);
- site = make_site_event<Point2D>(3, 0, 0);
+ site = make_site_event<T>(static_cast<T>(3), static_cast<T>(0), 0);
BOOST_CHECK_EQUAL(circle.compare(site), 1);
- site = make_site_event<Point2D>(3, 2, 0);
+ site = make_site_event<T>(static_cast<T>(3), static_cast<T>(2), 0);
BOOST_CHECK_EQUAL(circle.compare(site), 0);
- site = make_site_event<Point2D>(3, 2, 0);
+ site = make_site_event<T>(static_cast<T>(3), static_cast<T>(2), 0);
BOOST_CHECK_EQUAL(circle.compare(site), 0);
- site = make_site_event<Point2D>(4, 2, 0);
+ site = make_site_event<T>(static_cast<T>(4), static_cast<T>(2), 0);
BOOST_CHECK_EQUAL(circle.compare(site), -1);
}
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-13 17:29:05 EDT (Tue, 13 Jul 2010)
@@ -17,19 +17,19 @@
BOOST_AUTO_TEST_CASE_TEMPLATE(node_comparer_test1, T, test_types) {
typedef point_2d<T> Point2D;
- typedef site_event<Point2D> site_event_type;
- typedef beach_line_node< point_2d<T> > bline_node;
+ typedef site_event<T> site_event_type;
+ typedef beach_line_node<T> bline_node;
typedef typename 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_type site1 = make_site_event<Point2D>(static_cast<T>(0), static_cast<T>(0), 0);
- site_event_type site2 = make_site_event<Point2D>(static_cast<T>(0), static_cast<T>(2), 1);
+ site_event_type site1 = make_site_event<T>(static_cast<T>(0), static_cast<T>(0), 0);
+ site_event_type site2 = make_site_event<T>(static_cast<T>(0), static_cast<T>(2), 1);
bline_node initial_node(site1, site2);
test_beach_line[initial_node] = 2;
- site_event_type site3 = make_site_event<Point2D>(static_cast<T>(1), static_cast<T>(0), 2);
+ site_event_type site3 = make_site_event<T>(static_cast<T>(1), static_cast<T>(0), 2);
bline_node node1(site1, site3);
bline_node node2(site3, site1);
test_beach_line.insert(std::pair< bline_node, int>(node1, 0));
@@ -44,16 +44,16 @@
BOOST_AUTO_TEST_CASE_TEMPLATE(node_comparer_test2, T, test_types) {
typedef point_2d<T> Point2D;
- typedef site_event<Point2D> site_event_type;
- typedef beach_line_node< point_2d<T> > bline_node;
+ typedef site_event<T> site_event_type;
+ typedef beach_line_node<T> bline_node;
typedef typename 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_type site1 = make_site_event<Point2D>(static_cast<T>(0), static_cast<T>(1), 0);
- site_event_type site2 = make_site_event<Point2D>(static_cast<T>(2), static_cast<T>(0), 1);
- site_event_type site3 = make_site_event<Point2D>(static_cast<T>(2), static_cast<T>(4), 2);
+ site_event_type site1 = make_site_event<T>(static_cast<T>(0), static_cast<T>(1), 0);
+ site_event_type site2 = make_site_event<T>(static_cast<T>(2), static_cast<T>(0), 1);
+ site_event_type site3 = make_site_event<T>(static_cast<T>(2), static_cast<T>(4), 2);
bline_node initial_node1(site1, site2);
bline_node initial_node2(site2, site1);
test_beach_line[initial_node1] = 0;
@@ -73,20 +73,20 @@
BOOST_AUTO_TEST_CASE_TEMPLATE(node_comparer_test3, T, test_types) {
typedef point_2d<T> Point2D;
- typedef beach_line_node< point_2d<T> > bline_node;
+ typedef beach_line_node<T> bline_node;
node_comparer<bline_node> node_comparer_test;
bline_node initial_node(
- make_site_event<Point2D>(static_cast<T>(1), static_cast<T>(0), 0),
- make_site_event<Point2D>(static_cast<T>(0), static_cast<T>(2), 1));
+ 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<Point2D>(static_cast<T>(1.5), static_cast<T>(-10), 2));
- bline_node new_node2(make_site_event<Point2D>(static_cast<T>(1.5), static_cast<T>(-0.5), 3));
- bline_node new_node3(make_site_event<Point2D>(static_cast<T>(1.5), static_cast<T>(0), 4));
- bline_node new_node4(make_site_event<Point2D>(static_cast<T>(1.5), static_cast<T>(0.5), 4));
- bline_node new_node5(make_site_event<Point2D>(static_cast<T>(1.5), static_cast<T>(1.0), 4));
- bline_node new_node6(make_site_event<Point2D>(static_cast<T>(1.5), static_cast<T>(3.0), 4));
- bline_node new_node7(make_site_event<Point2D>(static_cast<T>(2.0), static_cast<T>(1.0), 4));
+ 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);
@@ -109,20 +109,20 @@
BOOST_AUTO_TEST_CASE_TEMPLATE(node_comparer_test4, T, test_types) {
typedef point_2d<T> Point2D;
- typedef beach_line_node< point_2d<T> > bline_node;
+ typedef beach_line_node<T> bline_node;
node_comparer<bline_node> node_comparer_test;
bline_node initial_node(
- make_site_event<Point2D>(static_cast<T>(0), static_cast<T>(1), 0),
- make_site_event<Point2D>(static_cast<T>(1), static_cast<T>(0), 1));
+ 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<Point2D>(static_cast<T>(1.5), static_cast<T>(-3), 2));
- bline_node new_node2(make_site_event<Point2D>(static_cast<T>(1.5), static_cast<T>(-1.8), 3));
- bline_node new_node3(make_site_event<Point2D>(static_cast<T>(1.5), static_cast<T>(-1.7), 4));
- bline_node new_node4(make_site_event<Point2D>(static_cast<T>(1.5), static_cast<T>(0.0), 4));
- bline_node new_node5(make_site_event<Point2D>(static_cast<T>(1.5), static_cast<T>(1.0), 4));
- bline_node new_node6(make_site_event<Point2D>(static_cast<T>(1.5), static_cast<T>(3.0), 4));
- bline_node new_node7(make_site_event<Point2D>(static_cast<T>(1.5), static_cast<T>(10.0), 4));
+ 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);
@@ -143,20 +143,20 @@
BOOST_AUTO_TEST_CASE_TEMPLATE(node_comparer_test5, T, test_types) {
typedef point_2d<T> Point2D;
- typedef beach_line_node< point_2d<T> > bline_node;
+ typedef beach_line_node<T> bline_node;
node_comparer<bline_node> node_comparer_test;
bline_node initial_node(
- make_site_event<Point2D>(static_cast<T>(0), static_cast<T>(0), 0),
- make_site_event<Point2D>(static_cast<T>(1), static_cast<T>(2), 1));
+ 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<Point2D>(static_cast<T>(1.5), static_cast<T>(-10), 2));
- bline_node new_node2(make_site_event<Point2D>(static_cast<T>(1.5), static_cast<T>(0), 3));
- bline_node new_node3(make_site_event<Point2D>(static_cast<T>(1.5), static_cast<T>(1.05), 4));
- bline_node new_node4(make_site_event<Point2D>(static_cast<T>(1.5), static_cast<T>(1.1), 4));
- bline_node new_node5(make_site_event<Point2D>(static_cast<T>(1.5), static_cast<T>(2), 4));
- bline_node new_node6(make_site_event<Point2D>(static_cast<T>(1.5), static_cast<T>(5), 4));
- bline_node new_node7(make_site_event<Point2D>(static_cast<T>(1.5), static_cast<T>(20), 4));
+ 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);
@@ -179,20 +179,20 @@
BOOST_AUTO_TEST_CASE_TEMPLATE(node_comparer_test6, T, test_types) {
typedef point_2d<T> Point2D;
- typedef beach_line_node< point_2d<T> > bline_node;
+ typedef beach_line_node<T> bline_node;
node_comparer<bline_node> node_comparer_test;
bline_node initial_node(
- make_site_event<Point2D>(static_cast<T>(1), static_cast<T>(1), 0),
- make_site_event<Point2D>(static_cast<T>(0), static_cast<T>(0), 1));
+ 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<Point2D>(static_cast<T>(1.5), static_cast<T>(-3), 2));
- bline_node new_node2(make_site_event<Point2D>(static_cast<T>(1.5), static_cast<T>(-1.75), 3));
- bline_node new_node3(make_site_event<Point2D>(static_cast<T>(1.5), static_cast<T>(0.0), 4));
- bline_node new_node4(make_site_event<Point2D>(static_cast<T>(1.5), static_cast<T>(0.28), 4));
- bline_node new_node5(make_site_event<Point2D>(static_cast<T>(1.5), static_cast<T>(2.7), 4));
- bline_node new_node6(make_site_event<Point2D>(static_cast<T>(1.5), static_cast<T>(2.8), 4));
- bline_node new_node7(make_site_event<Point2D>(static_cast<T>(1.5), static_cast<T>(5.0), 4));
+ 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);
@@ -213,18 +213,18 @@
BOOST_AUTO_TEST_CASE_TEMPLATE(node_comparer_test7, T, test_types) {
typedef point_2d<T> Point2D;
- typedef beach_line_node< point_2d<T> > bline_node;
+ typedef beach_line_node<T> bline_node;
node_comparer<bline_node> node_comparer_test;
bline_node initial_node(
- make_site_event<Point2D>(static_cast<T>(0), static_cast<T>(0), 0),
- make_site_event<Point2D>(static_cast<T>(0), static_cast<T>(2), 1));
+ 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<Point2D>(static_cast<T>(1), static_cast<T>(0), 2));
- bline_node new_node2(make_site_event<Point2D>(static_cast<T>(1), static_cast<T>(1), 3));
- bline_node new_node3(make_site_event<Point2D>(static_cast<T>(1), static_cast<T>(2), 4));
- bline_node new_node4(make_site_event<Point2D>(static_cast<T>(1), static_cast<T>(1.000001), 5));
- bline_node new_node5(make_site_event<Point2D>(static_cast<T>(1), static_cast<T>(0.999999), 6));
+ 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);
@@ -241,19 +241,19 @@
BOOST_AUTO_TEST_CASE_TEMPLATE(node_comparer_test8, T, test_types) {
typedef point_2d<T> Point2D;
- typedef beach_line_node< point_2d<T> > bline_node;
+ typedef beach_line_node<T> bline_node;
node_comparer<bline_node> node_comparer_test;
bline_node initial_node(
- make_site_event<Point2D>(static_cast<T>(0), static_cast<T>(0), 0),
- make_site_event<Point2D>(static_cast<T>(1), static_cast<T>(1), 1));
+ 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<Point2D>(static_cast<T>(1), static_cast<T>(0), 2));
- bline_node new_node2(make_site_event<Point2D>(static_cast<T>(1), static_cast<T>(1), 1));
- bline_node new_node3(make_site_event<Point2D>(static_cast<T>(1), static_cast<T>(2), 3));
+ 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<Point2D>(static_cast<T>(1), static_cast<T>(1), 1),
- make_site_event<Point2D>(static_cast<T>(0), static_cast<T>(0), 0));
+ 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);
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-13 17:29:05 EDT (Tue, 13 Jul 2010)
@@ -17,16 +17,160 @@
#define BOOST_TEST_MODULE voronoi_builder_test
#include <boost/test/test_case_template.hpp>
+// Sites: (0, 0).
+BOOST_AUTO_TEST_CASE_TEMPLATE(single_site_test, T, test_types) {
+ typedef typename voronoi_output_clipped<T>::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)));
+
+ test_voronoi_builder.init(points);
+ test_voronoi_builder.run_sweepline();
+ voronoi_output_clipped<T> 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);
+
+ 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);
+ BOOST_CHECK_EQUAL(static_cast<int>(test_output.get_voronoi_edges().size()), 0);
+
+ BOOST_CHECK_EQUAL(test_output.get_num_voronoi_cells(), 1);
+ BOOST_CHECK_EQUAL(test_output.get_num_voronoi_vertices(), 0);
+ BOOST_CHECK_EQUAL(test_output.get_num_voronoi_edges(), 0);
+
+ voronoi_const_iterator_type it = test_output.get_voronoi_cells().begin();
+ BOOST_CHECK_EQUAL(it->num_incident_edges, 0);
+ BOOST_CHECK_EQUAL(it->incident_edge == NULL, true);
+}
+
+// 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
+ 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)));
+
+ test_voronoi_builder.init(points);
+ test_voronoi_builder.run_sweepline();
+ voronoi_output_clipped<T> 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);
+
+ 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);
+ BOOST_CHECK_EQUAL(static_cast<int>(test_output.get_voronoi_edges().size()), 2);
+
+ BOOST_CHECK_EQUAL(test_output.get_num_voronoi_cells(), 2);
+ BOOST_CHECK_EQUAL(test_output.get_num_voronoi_vertices(), 0);
+ BOOST_CHECK_EQUAL(test_output.get_num_voronoi_edges(), 1);
+
+ voronoi_const_iterator_type cell_it = test_output.get_voronoi_cells().begin();
+ BOOST_CHECK_EQUAL(cell_it->num_incident_edges, 1);
+ cell_it++;
+ BOOST_CHECK_EQUAL(cell_it->num_incident_edges, 1);
+
+ edge_type *edge1_1 = cell_it->incident_edge;
+ edge_type *edge1_2 = edge1_1->twin;
+
+ BOOST_CHECK_EQUAL(edge1_1->twin == edge1_2, true);
+ BOOST_CHECK_EQUAL(edge1_2->twin == edge1_1, true);
+
+ BOOST_CHECK_EQUAL(edge1_1->next == edge1_1, true);
+ BOOST_CHECK_EQUAL(edge1_1->prev == edge1_1, true);
+ BOOST_CHECK_EQUAL(edge1_1->rot_next == edge1_1, true);
+ BOOST_CHECK_EQUAL(edge1_1->rot_prev == edge1_1, true);
+
+ BOOST_CHECK_EQUAL(edge1_2->next == edge1_2, true);
+ BOOST_CHECK_EQUAL(edge1_2->prev == edge1_2, true);
+ BOOST_CHECK_EQUAL(edge1_2->rot_next == edge1_2, true);
+ BOOST_CHECK_EQUAL(edge1_2->rot_prev == edge1_2, true);
+}
+
+// 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
+ 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)));
+
+ test_voronoi_builder.init(points);
+ test_voronoi_builder.run_sweepline();
+ voronoi_output_clipped<T> 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);
+
+ 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);
+ BOOST_CHECK_EQUAL(static_cast<int>(test_output.get_voronoi_edges().size()), 4);
+
+ BOOST_CHECK_EQUAL(test_output.get_num_voronoi_cells(), 3);
+ BOOST_CHECK_EQUAL(test_output.get_num_voronoi_vertices(), 0);
+ BOOST_CHECK_EQUAL(test_output.get_num_voronoi_edges(), 2);
+
+ voronoi_const_iterator_type cell_it = test_output.get_voronoi_cells().begin();
+ BOOST_CHECK_EQUAL(cell_it->num_incident_edges, 1);
+ edge_type *edge1_1 = cell_it->incident_edge;
+ edge_type *edge1_2 = edge1_1->twin;
+ cell_it++;
+ BOOST_CHECK_EQUAL(cell_it->num_incident_edges, 2);
+ cell_it++;
+ BOOST_CHECK_EQUAL(cell_it->num_incident_edges, 1);
+ edge_type *edge2_2 = cell_it->incident_edge;
+ edge_type *edge2_1 = edge2_2->twin;
+
+ BOOST_CHECK_EQUAL(edge1_1->twin == edge1_2 && edge1_2->twin == edge1_1, true);
+ BOOST_CHECK_EQUAL(edge2_1->twin == edge2_2 && edge2_2->twin == edge2_1, true);
+
+ BOOST_CHECK_EQUAL(edge1_1->next == edge1_1 && edge1_1->prev == edge1_1, true);
+ BOOST_CHECK_EQUAL(edge1_1->rot_next == edge1_1 && edge1_1->rot_prev == edge1_1, true);
+ BOOST_CHECK_EQUAL(edge1_2->rot_next == edge1_2 && edge1_2->rot_prev == edge1_2, true);
+ BOOST_CHECK_EQUAL(edge2_1->rot_next == edge2_1 && edge2_1->rot_prev == edge2_1, true);
+ BOOST_CHECK_EQUAL(edge2_2->next == edge2_2 && edge2_2->prev == edge2_2, true);
+ BOOST_CHECK_EQUAL(edge2_2->rot_next == edge2_2 && edge2_2->rot_prev == edge2_2, true);
+
+ BOOST_CHECK_EQUAL(edge1_2->next == edge2_1 && edge1_2->prev == edge2_1, true);
+ BOOST_CHECK_EQUAL(edge2_1->next == edge1_2 && edge2_1->prev == edge1_2, true);
+}
+
// Sites: (0, 0), (0, 4), (2, 1).
BOOST_AUTO_TEST_CASE_TEMPLATE(triangle_test1, T, test_types) {
- typedef typename voronoi_output_clipped< point_2d<T> >::edge_type edge_type;
- typedef typename voronoi_output_clipped< point_2d<T> >::voronoi_const_iterator_type
+ typedef typename voronoi_output_clipped<T>::edge_type edge_type;
+ typedef typename voronoi_output_clipped<T>::voronoi_const_iterator_type
voronoi_const_iterator_type;
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, 4);
- point_2d<T> point3 = make_point_2d<T>(2, 1);
+ 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));
std::vector< point_2d<T> > points;
points.push_back(point1);
@@ -35,11 +179,11 @@
test_beach_line.init(points);
test_beach_line.run_sweepline();
- voronoi_output_clipped< point_2d<T> > test_output;
+ voronoi_output_clipped<T> test_output;
test_beach_line.clip(test_output);
BOOST_CHECK_EQUAL(test_output.check(), true);
- BRect< point_2d<T> > bounding_rectangle = test_beach_line.get_bounding_rectangle();
+ 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) &&
@@ -87,14 +231,14 @@
// Sites: (0, 1), (2, 0), (2, 4).
BOOST_AUTO_TEST_CASE_TEMPLATE(triangle_test2, T, test_types) {
- typedef typename voronoi_output_clipped< point_2d<T> >::edge_type edge_type;
- typedef typename voronoi_output_clipped< point_2d<T> >::voronoi_const_iterator_type
+ typedef typename voronoi_output_clipped<T>::edge_type edge_type;
+ typedef typename voronoi_output_clipped<T>::voronoi_const_iterator_type
voronoi_const_iterator_type;
voronoi_builder<T> test_beach_line;
- point_2d<T> point1 = make_point_2d<T>(0, 1);
- point_2d<T> point2 = make_point_2d<T>(2, 0);
- point_2d<T> point3 = make_point_2d<T>(2, 4);
+ 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));
std::vector< point_2d<T> > points;
points.push_back(point1);
@@ -103,7 +247,7 @@
test_beach_line.init(points);
test_beach_line.run_sweepline();
- voronoi_output_clipped< point_2d<T> > test_output;
+ voronoi_output_clipped<T> test_output;
test_beach_line.clip(test_output);
BOOST_CHECK_EQUAL(test_output.check(), true);
@@ -149,20 +293,20 @@
// Sites: (0, 0), (0, 1), (1, 0), (1, 1).
BOOST_AUTO_TEST_CASE_TEMPLATE(square_test3, T, test_types) {
- typedef typename voronoi_output_clipped< point_2d<T> >::edge_type edge_type;
- typedef typename voronoi_output_clipped< point_2d<T> >::voronoi_const_iterator_type
+ typedef typename voronoi_output_clipped<T>::edge_type edge_type;
+ typedef typename voronoi_output_clipped<T>::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>(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));
+ 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)));
test_beach_line.init(points);
test_beach_line.run_sweepline();
- voronoi_output_clipped< point_2d<T> > test_output;
+ voronoi_output_clipped<T> test_output;
test_beach_line.clip(test_output);
BOOST_CHECK_EQUAL(test_output.check(), true);
@@ -231,7 +375,7 @@
test_beach_line.init(points);
test_beach_line.run_sweepline();
- voronoi_output_clipped< point_2d<T> > test_output;
+ voronoi_output_clipped<T> test_output;
test_beach_line.clip(test_output);
BOOST_CHECK_EQUAL(test_output.check(), true);
@@ -251,7 +395,7 @@
test_beach_line.init(points);
test_beach_line.run_sweepline();
- voronoi_output_clipped< point_2d<T> > test_output;
+ voronoi_output_clipped<T> test_output;
test_beach_line.clip(test_output);
BOOST_CHECK_EQUAL(test_output.check(), true);
@@ -271,7 +415,7 @@
test_beach_line.init(points);
test_beach_line.run_sweepline();
- voronoi_output_clipped< point_2d<T> > test_output;
+ voronoi_output_clipped<T> test_output;
test_beach_line.clip(test_output);
BOOST_CHECK_EQUAL(test_output.check(), true);
@@ -291,7 +435,7 @@
test_beach_line.init(points);
test_beach_line.run_sweepline();
- voronoi_output_clipped< point_2d<T> > test_output;
+ voronoi_output_clipped<T> test_output;
test_beach_line.clip(test_output);
BOOST_CHECK_EQUAL(test_output.check(), true);
@@ -311,7 +455,7 @@
test_beach_line.init(points);
test_beach_line.run_sweepline();
- voronoi_output_clipped< point_2d<T> > test_output;
+ voronoi_output_clipped<T> test_output;
test_beach_line.clip(test_output);
BOOST_CHECK_EQUAL(test_output.check(), true);
@@ -324,7 +468,7 @@
BOOST_AUTO_TEST_CASE_TEMPLATE(random_test1, T, test_types) {
srand(static_cast<unsigned int>(time(NULL)));
voronoi_builder<T> test_beach_line;
- voronoi_output_clipped< point_2d<T> > test_output;
+ voronoi_output_clipped<T> test_output;
std::vector< point_2d<T> > points;
for (int i = 0; i < 10000; i++) {
points.clear();
@@ -343,7 +487,7 @@
BOOST_AUTO_TEST_CASE_TEMPLATE(random_test2, T, test_types) {
srand(static_cast<unsigned int>(time(NULL)));
voronoi_builder<T> test_beach_line;
- voronoi_output_clipped< point_2d<T> > test_output;
+ voronoi_output_clipped<T> test_output;
std::vector< point_2d<T> > points;
for (int i = 0; i < 1000; i++) {
points.clear();
@@ -362,7 +506,7 @@
BOOST_AUTO_TEST_CASE_TEMPLATE(random_test3, T, test_types) {
srand(static_cast<unsigned int>(time(NULL)));
voronoi_builder<T> test_beach_line;
- voronoi_output_clipped< point_2d<T> > test_output;
+ voronoi_output_clipped<T> test_output;
std::vector< point_2d<T> > points;
for (int i = 0; i < 100; i++) {
points.clear();
@@ -381,7 +525,7 @@
BOOST_AUTO_TEST_CASE_TEMPLATE(random_test4, T, test_types) {
srand(static_cast<unsigned int>(time(NULL)));
voronoi_builder<T> test_beach_line;
- voronoi_output_clipped< point_2d<T> > test_output;
+ voronoi_output_clipped<T> test_output;
std::vector< point_2d<T> > points;
for (int i = 0; i < 10; i++) {
points.clear();
Added: sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_clipping_test.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_clipping_test.cpp 2010-07-13 17:29:05 EDT (Tue, 13 Jul 2010)
@@ -0,0 +1,296 @@
+// Boost sweepline library voronoi_clipping_test.cpp file
+
+// Copyright Andrii Sydorchuk 2010.
+// Distributed under the Boost Software License, Version 1.0.
+// (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+// 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_sweepline.hpp"
+using namespace boost::sweepline;
+
+#define BOOST_TEST_MODULE voronoi_clipping_test
+#include <boost/test/test_case_template.hpp>
+
+// Test segment clipping.
+BOOST_AUTO_TEST_CASE_TEMPLATE(segment_clipping_test1, T, test_types) {
+ BRect<T> test_rect(static_cast<T>(0.0), static_cast<T>(-1.0),
+ static_cast<T>(4.0), static_cast<T>(2.0));
+ detail::voronoi_output<T> test_output;
+ point_2d<T> test_origin(static_cast<T>(-1), static_cast<T>(3));
+ point_2d<T> test_direction1_1(static_cast<T>(8), static_cast<T>(-8));
+ point_2d<T> test_direction1_2(static_cast<T>(2), static_cast<T>(-2));
+ point_2d<T> test_direction1_3(static_cast<T>(0.5), static_cast<T>(-0.5));
+ point_2d<T> test_direction2(static_cast<T>(2), static_cast<T>(-4));
+ point_2d<T> test_direction3(static_cast<T>(2), static_cast<T>(-1));
+ point_2d<T> test_direction4(static_cast<T>(1), static_cast<T>(-4));
+ point_2d<T> test_direction5(static_cast<T>(5), static_cast<T>(-1));
+
+ std::vector< point_2d<T> > intersections;
+ test_output.find_intersections(test_origin, test_direction1_1,
+ detail::voronoi_output<T>::SEGMENT,
+ test_rect, intersections);
+ BOOST_CHECK_EQUAL(static_cast<int>(intersections.size()), 2);
+ BOOST_CHECK_EQUAL(intersections[0].x() == static_cast<T>(0) &&
+ intersections[0].y() == static_cast<T>(2), true);
+ BOOST_CHECK_EQUAL(intersections[1].x() == static_cast<T>(3) &&
+ intersections[1].y() == static_cast<T>(-1), true);
+
+ intersections.clear();
+ test_output.find_intersections(test_origin, test_direction1_2,
+ detail::voronoi_output<T>::SEGMENT,
+ test_rect, intersections);
+ BOOST_CHECK_EQUAL(static_cast<int>(intersections.size()), 1);
+ BOOST_CHECK_EQUAL(intersections[0].x() == static_cast<T>(0) &&
+ intersections[0].y() == static_cast<T>(2), true);
+
+ intersections.clear();
+ test_output.find_intersections(test_origin, test_direction1_3,
+ detail::voronoi_output<T>::SEGMENT,
+ test_rect, intersections);
+ BOOST_CHECK_EQUAL(intersections.empty(), true);
+
+ intersections.clear();
+ test_output.find_intersections(test_origin, test_direction2,
+ detail::voronoi_output<T>::SEGMENT,
+ test_rect, intersections);
+ BOOST_CHECK_EQUAL(static_cast<int>(intersections.size()), 2);
+ BOOST_CHECK_EQUAL(intersections[0].x() == static_cast<T>(0) &&
+ intersections[0].y() == static_cast<T>(1), true);
+ BOOST_CHECK_EQUAL(intersections[1].x() == static_cast<T>(1) &&
+ intersections[1].y() == static_cast<T>(-1), true);
+
+ intersections.clear();
+ test_output.find_intersections(test_origin, test_direction3,
+ detail::voronoi_output<T>::SEGMENT,
+ test_rect, intersections);
+ BOOST_CHECK_EQUAL(static_cast<int>(intersections.size()), 1);
+ BOOST_CHECK_EQUAL(intersections[0].x() == static_cast<T>(1) &&
+ intersections[0].y() == static_cast<T>(2), true);
+
+ intersections.clear();
+ test_output.find_intersections(test_origin, test_direction4,
+ detail::voronoi_output<T>::SEGMENT,
+ test_rect, intersections);
+ BOOST_CHECK_EQUAL(static_cast<int>(intersections.size()), 1);
+ BOOST_CHECK_EQUAL(intersections[0].x() == static_cast<T>(0) &&
+ intersections[0].y() == static_cast<T>(-1), true);
+
+ intersections.clear();
+ test_output.find_intersections(test_origin, test_direction5,
+ detail::voronoi_output<T>::SEGMENT,
+ test_rect, intersections);
+ BOOST_CHECK_EQUAL(static_cast<int>(intersections.size()), 1);
+ BOOST_CHECK_EQUAL(intersections[0].x() == static_cast<T>(4) &&
+ intersections[0].y() == static_cast<T>(2), true);
+}
+
+BOOST_AUTO_TEST_CASE_TEMPLATE(segment_clipping_test2, T, test_types) {
+ BRect<T> test_rect(static_cast<T>(0.0), static_cast<T>(-1.0),
+ static_cast<T>(4.0), static_cast<T>(3.0));
+ detail::voronoi_output<T> test_output;
+ std::vector< point_2d<T> > intersections;
+ srand(static_cast<unsigned int>(time(NULL)));
+ point_2d<T> test_origin(2, 1);
+
+ for (int i = -50; i <= 50; i++)
+ for (int j = -50; j <= 50; j++) {
+ intersections.clear();
+ point_2d<T> test_direction(static_cast<T>(i), static_cast<T>(j));
+ test_output.find_intersections(test_origin, test_direction,
+ detail::voronoi_output<T>::SEGMENT,
+ test_rect, intersections);
+ if (abs(i) >= 2 || abs(j) >= 2)
+ BOOST_CHECK_EQUAL(static_cast<int>(intersections.size()), 1);
+ else
+ BOOST_CHECK_EQUAL(static_cast<int>(intersections.size()), 0);
+ }
+}
+
+BOOST_AUTO_TEST_CASE_TEMPLATE(segment_clipping_test3, T, test_types) {
+ BRect<T> test_rect(static_cast<T>(0.0), static_cast<T>(-1.0),
+ static_cast<T>(4.0), static_cast<T>(3.0));
+ detail::voronoi_output<T> test_output;
+ std::vector< point_2d<T> > intersections;
+ srand(static_cast<unsigned int>(time(NULL)));
+ point_2d<T> test_origin(2, 1);
+
+ for (int i = -50; i <= 50; i++)
+ for (int j = -50; j <= 50; j++) {
+ intersections.clear();
+ T x = static_cast<T>(i) / static_cast<T>(26);
+ T y = static_cast<T>(j) / static_cast<T>(26);
+ point_2d<T> test_direction(x, y);
+ test_output.find_intersections(test_origin, test_direction,
+ detail::voronoi_output<T>::SEGMENT,
+ test_rect, intersections);
+ BOOST_CHECK_EQUAL(static_cast<int>(intersections.size()), 0);
+ }
+}
+
+// Test ray clipping.
+BOOST_AUTO_TEST_CASE_TEMPLATE(ray_clipping_test1, T, test_types) {
+ BRect<T> test_rect(static_cast<T>(0.0), static_cast<T>(-1.0),
+ static_cast<T>(4.0), static_cast<T>(2.0));
+ detail::voronoi_output<T> test_output;
+ point_2d<T> test_origin(static_cast<T>(-1), static_cast<T>(3));
+ point_2d<T> test_direction1(static_cast<T>(2), static_cast<T>(-2));
+ point_2d<T> test_direction2(static_cast<T>(2), static_cast<T>(-4));
+ point_2d<T> test_direction3(static_cast<T>(2), static_cast<T>(-1));
+ point_2d<T> test_direction4(static_cast<T>(1), static_cast<T>(-4));
+ point_2d<T> test_direction5(static_cast<T>(5), static_cast<T>(-1));
+
+ std::vector< point_2d<T> > intersections;
+ test_output.find_intersections(test_origin, test_direction1,
+ detail::voronoi_output<T>::RAY,
+ test_rect, intersections);
+ BOOST_CHECK_EQUAL(static_cast<int>(intersections.size()), 2);
+ BOOST_CHECK_EQUAL(intersections[0].x() == static_cast<T>(0) &&
+ intersections[0].y() == static_cast<T>(2), true);
+ BOOST_CHECK_EQUAL(intersections[1].x() == static_cast<T>(3) &&
+ intersections[1].y() == static_cast<T>(-1), true);
+
+ intersections.clear();
+ test_output.find_intersections(test_origin, test_direction2,
+ detail::voronoi_output<T>::RAY,
+ test_rect, intersections);
+ BOOST_CHECK_EQUAL(static_cast<int>(intersections.size()), 2);
+ BOOST_CHECK_EQUAL(intersections[0].x() == static_cast<T>(0) &&
+ intersections[0].y() == static_cast<T>(1), true);
+ BOOST_CHECK_EQUAL(intersections[1].x() == static_cast<T>(1) &&
+ intersections[1].y() == static_cast<T>(-1), true);
+
+ intersections.clear();
+ test_output.find_intersections(test_origin, test_direction3,
+ detail::voronoi_output<T>::RAY,
+ test_rect, intersections);
+ BOOST_CHECK_EQUAL(static_cast<int>(intersections.size()), 2);
+ BOOST_CHECK_EQUAL(intersections[0].x() == static_cast<T>(1) &&
+ intersections[0].y() == static_cast<T>(2), true);
+ BOOST_CHECK_EQUAL(intersections[1].x() == static_cast<T>(4) &&
+ intersections[1].y() == static_cast<T>(0.5), true);
+
+ intersections.clear();
+ test_output.find_intersections(test_origin, test_direction4,
+ detail::voronoi_output<T>::RAY,
+ test_rect, intersections);
+ BOOST_CHECK_EQUAL(static_cast<int>(intersections.size()), 1);
+ BOOST_CHECK_EQUAL(intersections[0].x() == static_cast<T>(0) &&
+ intersections[0].y() == static_cast<T>(-1), true);
+
+ intersections.clear();
+ test_output.find_intersections(test_origin, test_direction5,
+ detail::voronoi_output<T>::RAY,
+ test_rect, intersections);
+ BOOST_CHECK_EQUAL(static_cast<int>(intersections.size()), 1);
+ BOOST_CHECK_EQUAL(intersections[0].x() == static_cast<T>(4) &&
+ intersections[0].y() == static_cast<T>(2), true);
+}
+
+BOOST_AUTO_TEST_CASE_TEMPLATE(ray_clipping_test2, T, test_types) {
+ BRect<T> test_rect(static_cast<T>(0.0), static_cast<T>(-1.0),
+ static_cast<T>(4.0), static_cast<T>(3.0));
+ detail::voronoi_output<T> test_output;
+ std::vector< point_2d<T> > intersections;
+ srand(static_cast<unsigned int>(time(NULL)));
+ point_2d<T> test_origin(2, 1);
+
+ for (int i = -50; i <= 50; i++)
+ for (int j = -50; j <= 50; j++) {
+ intersections.clear();
+ T x = static_cast<T>(i) / static_cast<T>(26);
+ T y = static_cast<T>(j) / static_cast<T>(26);
+ point_2d<T> test_direction(x, y);
+ test_output.find_intersections(test_origin, test_direction,
+ detail::voronoi_output<T>::RAY,
+ test_rect, intersections);
+ if (i && j)
+ BOOST_CHECK_EQUAL(static_cast<int>(intersections.size()), 1);
+ }
+}
+
+// Test line clipping.
+BOOST_AUTO_TEST_CASE_TEMPLATE(line_clipping_test1, T, test_types) {
+ BRect<T> test_rect(static_cast<T>(0.0), static_cast<T>(-1.0),
+ static_cast<T>(4.0), static_cast<T>(2.0));
+ detail::voronoi_output<T> test_output;
+ point_2d<T> test_origin(static_cast<T>(-1), static_cast<T>(3));
+ point_2d<T> test_direction1(static_cast<T>(-1), static_cast<T>(1));
+ point_2d<T> test_direction2(static_cast<T>(-1), static_cast<T>(2));
+ point_2d<T> test_direction3(static_cast<T>(-2), static_cast<T>(1));
+ point_2d<T> test_direction4(static_cast<T>(-1), static_cast<T>(4));
+ point_2d<T> test_direction5(static_cast<T>(-5), static_cast<T>(1));
+
+ std::vector< point_2d<T> > intersections;
+ test_output.find_intersections(test_origin, test_direction1,
+ detail::voronoi_output<T>::LINE,
+ test_rect, intersections);
+ BOOST_CHECK_EQUAL(static_cast<int>(intersections.size()), 2);
+ BOOST_CHECK_EQUAL(intersections[0].x() == static_cast<T>(3) &&
+ intersections[0].y() == static_cast<T>(-1), true);
+ BOOST_CHECK_EQUAL(intersections[1].x() == static_cast<T>(0) &&
+ intersections[1].y() == static_cast<T>(2), true);
+
+ intersections.clear();
+ test_output.find_intersections(test_origin, test_direction2,
+ detail::voronoi_output<T>::LINE,
+ test_rect, intersections);
+ BOOST_CHECK_EQUAL(static_cast<int>(intersections.size()), 2);
+ BOOST_CHECK_EQUAL(intersections[0].x() == static_cast<T>(1) &&
+ intersections[0].y() == static_cast<T>(-1), true);
+ BOOST_CHECK_EQUAL(intersections[1].x() == static_cast<T>(0) &&
+ intersections[1].y() == static_cast<T>(1), true);
+
+ intersections.clear();
+ test_output.find_intersections(test_origin, test_direction3,
+ detail::voronoi_output<T>::LINE,
+ test_rect, intersections);
+ BOOST_CHECK_EQUAL(static_cast<int>(intersections.size()), 2);
+ BOOST_CHECK_EQUAL(intersections[0].x() == static_cast<T>(4) &&
+ intersections[0].y() == static_cast<T>(0.5), true);
+ BOOST_CHECK_EQUAL(intersections[1].x() == static_cast<T>(1) &&
+ intersections[1].y() == static_cast<T>(2), true);
+
+ intersections.clear();
+ test_output.find_intersections(test_origin, test_direction4,
+ detail::voronoi_output<T>::LINE,
+ test_rect, intersections);
+ BOOST_CHECK_EQUAL(static_cast<int>(intersections.size()), 1);
+ BOOST_CHECK_EQUAL(intersections[0].x() == static_cast<T>(0) &&
+ intersections[0].y() == static_cast<T>(-1), true);
+
+ intersections.clear();
+ test_output.find_intersections(test_origin, test_direction5,
+ detail::voronoi_output<T>::LINE,
+ test_rect, intersections);
+ BOOST_CHECK_EQUAL(static_cast<int>(intersections.size()), 1);
+ BOOST_CHECK_EQUAL(intersections[0].x() == static_cast<T>(4) &&
+ intersections[0].y() == static_cast<T>(2), true);
+}
+
+BOOST_AUTO_TEST_CASE_TEMPLATE(line_clipping_test2, T, test_types) {
+ BRect<T> test_rect(static_cast<T>(0.0), static_cast<T>(-1.0),
+ static_cast<T>(4.0), static_cast<T>(3.0));
+ detail::voronoi_output<T> test_output;
+ std::vector< point_2d<T> > intersections;
+ srand(static_cast<unsigned int>(time(NULL)));
+ point_2d<T> test_origin(2, 1);
+
+ for (int i = -50; i <= 50; i++)
+ for (int j = -50; j <= 50; j++) {
+ intersections.clear();
+ T x = static_cast<T>(i) / static_cast<T>(26);
+ T y = static_cast<T>(j) / static_cast<T>(26);
+ point_2d<T> test_direction(x, y);
+ test_output.find_intersections(test_origin, test_direction,
+ detail::voronoi_output<T>::LINE,
+ test_rect, intersections);
+ if (i && j)
+ BOOST_CHECK_EQUAL(static_cast<int>(intersections.size()), 2);
+ }
+}
\ No newline at end of file