Subject: [Boost-commit] svn:boost r67068 - in sandbox/SOC/2010/sweepline: boost/sweepline boost/sweepline/detail libs/sweepline/example/input_data libs/sweepline/example/output_data libs/sweepline/test
From: sydorchuk.andriy_at_[hidden]
Date: 2010-12-06 10:06:10
Author: asydorchuk
Date: 2010-12-06 10:05:28 EST (Mon, 06 Dec 2010)
New Revision: 67068
URL: http://svn.boost.org/trac/boost/changeset/67068
Log:
Updated output data structure (reduced memory consumption by 20%).
Made event creation fixes.
Updated tests.
Added:
sandbox/SOC/2010/sweepline/libs/sweepline/example/input_data/example_051.txt (contents, props changed)
sandbox/SOC/2010/sweepline/libs/sweepline/example/input_data/example_052.txt (contents, props changed)
sandbox/SOC/2010/sweepline/libs/sweepline/example/input_data/example_053.txt (contents, props changed)
sandbox/SOC/2010/sweepline/libs/sweepline/example/input_data/example_054.txt (contents, props changed)
sandbox/SOC/2010/sweepline/libs/sweepline/example/output_data/example_051.png (contents, props changed)
sandbox/SOC/2010/sweepline/libs/sweepline/example/output_data/example_052.png (contents, props changed)
sandbox/SOC/2010/sweepline/libs/sweepline/example/output_data/example_053.png (contents, props changed)
sandbox/SOC/2010/sweepline/libs/sweepline/example/output_data/example_054.png (contents, props changed)
Text files modified:
sandbox/SOC/2010/sweepline/boost/sweepline/detail/voronoi_formation.hpp | 44
sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_output.hpp | 201 ++++---
sandbox/SOC/2010/sweepline/libs/sweepline/test/benchmark_test.cpp | 6
sandbox/SOC/2010/sweepline/libs/sweepline/test/sweepline_test.cpp | 978 +++++++++++++++++++--------------------
4 files changed, 610 insertions(+), 619 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-12-06 10:05:28 EST (Mon, 06 Dec 2010)
@@ -816,6 +816,16 @@
static bool less_predicate(const point_2d<T> &left_point,
const point_2d<T> &right_point,
const point_2d<T> &new_point) {
+ if (left_point.x() > right_point.x()) {
+ if (new_point.y() <= left_point.y())
+ return false;
+ } else if (left_point.x() < right_point.x()) {
+ if (new_point.y() >= right_point.y())
+ return true;
+ } else {
+ return left_point.y() + right_point.y() < 2.0 * new_point.y();
+ }
+
kPredicateResult fast_res = fast_less_predicate(left_point, right_point, new_point);
if (fast_res != UNDEFINED)
return (fast_res == LESS);
@@ -1146,7 +1156,6 @@
}
// Create circle event from three point sites.
- // TODO (asydorchuk): make precision optimizations.
template <typename T>
static bool create_circle_event_ppp(const site_event<T> &site1,
const site_event<T> &site2,
@@ -1185,7 +1194,6 @@
}
// Create circle event from two point sites and one segment site.
- // TODO (asydorchuk): make_precision optimizations.
template <typename T>
static bool create_circle_event_pps(const site_event<T> &site1,
const site_event<T> &site2,
@@ -1193,11 +1201,19 @@
int segment_index,
circle_event<T> &c_event) {
if (segment_index != 2) {
- if (orientation_test(site3.get_point0(), site1.get_point0(),
- site2.get_point0()) != RIGHT_ORIENTATION &&
- detail::orientation_test(site3.get_point1(), site1.get_point0(),
- site2.get_point0()) != RIGHT_ORIENTATION)
+ kOrientation orient1 = orientation_test(site1.get_point0(),
+ site2.get_point0(), site3.get_point0(true));
+ kOrientation orient2 = orientation_test(site1.get_point0(),
+ site2.get_point0(), site3.get_point1(true));
+ if (segment_index == 1 && site1.x0() >= site2.x0()) {
+ if (orient1 != RIGHT_ORIENTATION)
+ return false;
+ } else if (segment_index == 3 && site2.x0() >= site1.x0()) {
+ if (orient2 != RIGHT_ORIENTATION)
+ return false;
+ } else if (orient1 != RIGHT_ORIENTATION && orient2 != RIGHT_ORIENTATION) {
return false;
+ }
} else {
if (site3.get_point0(true) == site1.get_point0() &&
site3.get_point1(true) == site2.get_point0())
@@ -1247,7 +1263,6 @@
}
// Create circle event from one point site and two segment sites.
- // TODO (asydorchuk): make precision optimizations.
template <typename T>
static bool create_circle_event_pss(const site_event<T> &site1,
const site_event<T> &site2,
@@ -1267,7 +1282,6 @@
if (!site2.is_inverse() && site3.is_inverse())
return false;
if (site2.is_inverse() == site3.is_inverse() &&
- //orientation_test(orientation) != RIGHT_ORIENTATION)
orientation_test(segm_end1, site1.get_point0(), segm_end2) != RIGHT_ORIENTATION)
return false;
}
@@ -1500,17 +1514,7 @@
}
bool less_pp(const Point2D &new_site) const {
- if (left_site_.x() > right_site_.x()) {
- if (new_site.y() <= left_site_.y())
- return false;
- return less_predicate(left_site_.get_point0(), right_site_.get_point0(), new_site);
- } else if (left_site_.x() < right_site_.x()) {
- if (new_site.y() >= right_site_.y())
- return true;
- return less_predicate(left_site_.get_point0(), right_site_.get_point0(), new_site);
- } else {
- return left_site_.y() + right_site_.y() < 2.0 * new_site.y();
- }
+ return less_predicate(left_site_.get_point0(), right_site_.get_point0(), new_site);
}
bool less_ps(const Point2D &new_site) const {
@@ -1630,7 +1634,7 @@
const std::vector< std::pair< point_2d<iType>, point_2d<iType> > > &segments) {
typedef std::pair< point_2d<iType>, point_2d<iType> > iSegment2D;
// Clear all data structures.
- output_.reset();
+ output_.clear();
// TODO(asydorchuk): Add segments intersection check.
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-12-06 10:05:28 EST (Mon, 06 Dec 2010)
@@ -414,6 +414,11 @@
typedef T coordinate_type;
typedef detail::site_event<T> site_event_type;
typedef voronoi_edge<T> voronoi_edge_type;
+
+ voronoi_cell(const site_event_type &new_site, voronoi_edge_type *edge) :
+ site_(new_site),
+ incident_edge_(edge),
+ num_incident_edges_(0) {}
bool contains_segment() const {
return site_.is_segment();
@@ -439,18 +444,31 @@
return num_incident_edges_;
}
- voronoi_cell(const site_event_type &new_site, voronoi_edge_type *edge) :
- site_(new_site),
- incident_edge_(edge),
- num_incident_edges_(0) {}
-
private:
friend class voronoi_output<T>;
+
+ void incident_edge(voronoi_edge_type *e) { incident_edge_ = e; }
+ void inc_num_incident_edges() { num_incident_edges_++; }
+ void dec_num_incident_edges() { num_incident_edges_--; }
site_event_type site_;
voronoi_edge_type *incident_edge_;
int num_incident_edges_;
};
+
+ template <typename T>
+ struct robust_voronoi_vertex {
+ detail::epsilon_robust_comparator<T> center_x;
+ detail::epsilon_robust_comparator<T> center_y;
+ detail::epsilon_robust_comparator<T> denom;
+
+ robust_voronoi_vertex(const detail::epsilon_robust_comparator<T> &c_x,
+ const detail::epsilon_robust_comparator<T> &c_y,
+ const detail::epsilon_robust_comparator<T> &den) :
+ center_x(c_x),
+ center_y(c_y),
+ denom(den) {}
+ };
template <typename T>
class voronoi_vertex {
@@ -458,26 +476,22 @@
typedef T coordinate_type;
typedef voronoi_edge<T> voronoi_edge_type;
- detail::epsilon_robust_comparator<T> center_x;
- detail::epsilon_robust_comparator<T> center_y;
- detail::epsilon_robust_comparator<T> denom;
- typename std::list< voronoi_vertex<coordinate_type> >::iterator voronoi_record_it;
-
- voronoi_vertex(const detail::epsilon_robust_comparator<T> &c_x,
- const detail::epsilon_robust_comparator<T> &c_y,
- const detail::epsilon_robust_comparator<T> &den,
+ voronoi_vertex(robust_voronoi_vertex<T> *robust_vertex,
voronoi_edge_type *edge) :
- center_x(c_x),
- center_y(c_y),
- denom(den),
- vertex_(c_x.dif() / den.dif(), c_y.dif() / den.dif()),
+ robust_vertex_(robust_vertex),
+ vertex_(robust_vertex->center_x.dif() / robust_vertex->denom.dif(),
+ robust_vertex->center_y.dif() / robust_vertex->denom.dif()),
incident_edge_(edge),
- num_incident_edges_(0) {}
+ num_incident_edges_(3) {}
const point_2d<T> &vertex() const {
return vertex_;
}
+ const robust_voronoi_vertex<T> *robust_vertex() const {
+ return robust_vertex_;
+ }
+
voronoi_edge_type *incident_edge() {
return incident_edge_;
}
@@ -492,7 +506,11 @@
private:
friend class voronoi_output<T>;
+
+ void incident_edge(voronoi_edge_type *e) { incident_edge_ = e; }
+ void num_incident_edges(int n) { num_incident_edges_ = n; }
+ robust_voronoi_vertex<T> *robust_vertex_;
point_2d<T> vertex_;
voronoi_edge_type *incident_edge_;
int num_incident_edges_;
@@ -538,18 +556,26 @@
const voronoi_edge_type *prev() const { return prev_; }
voronoi_edge_type *rot_next() {
- if (prev_)
+ if (vertex_)
return prev_->twin();
return NULL;
}
const voronoi_edge_type *rot_next() const {
- if (prev_)
+ if (vertex_)
return prev_->twin();
return NULL;
}
- voronoi_edge_type *rot_prev() { return twin_->next(); }
- const voronoi_edge_type *rot_prev() const { return twin_->next(); }
+ voronoi_edge_type *rot_prev() {
+ if (vertex_)
+ return twin_->next();
+ return NULL;
+ }
+ const voronoi_edge_type *rot_prev() const {
+ if (vertex_)
+ return twin_->next();
+ return NULL;
+ }
private:
friend class voronoi_output<T>;
@@ -559,7 +585,7 @@
void vertex1(voronoi_vertex_type *v) { twin_->vertex0(v); }
void twin(voronoi_edge_type *e) { twin_ = e; }
void next(voronoi_edge_type *e) { next_ = e; }
- void prev(voronoi_edge_type *e) { prev_ = e; }
+ void prev(voronoi_edge_type *e) { prev_ = e; }
voronoi_cell_type *cell_;
voronoi_vertex_type *vertex_;
@@ -600,8 +626,9 @@
num_vertex_records_ = 0;
}
- void reset() {
- cell_records_.clear();
+ void clear() {
+ robust_vertices_.clear();
+ voronoi_cells_type().swap(cell_records_);
vertex_records_.clear();
edge_records_.clear();
@@ -650,9 +677,6 @@
// 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_point0(), site.get_point0());
@@ -665,10 +689,6 @@
// beach line node and returns pointer to the new half-edge.
voronoi_edge_type *insert_new_edge(const site_event_type &site1,
const site_event_type &site2) {
- // Update counters.
- num_cell_records_++;
- num_edge_records_++;
-
// Get indices of sites.
int site_index1 = site1.get_site_index();
int site_index2 = site2.get_site_index();
@@ -684,10 +704,9 @@
// Add initial cell during first edge insertion.
if (cell_records_.empty()) {
cell_records_.push_back(voronoi_cell_type(site1, &edge1));
- num_cell_records_++;
voronoi_rect_ = BRect<coordinate_type>(site1.get_point0(), site1.get_point0());
}
- cell_records_[site_index1].num_incident_edges_++;
+ cell_records_[site_index1].inc_num_incident_edges();
// Update bounding rectangle.
voronoi_rect_.update(site2.get_point0());
@@ -698,7 +717,7 @@
// Second site represents new site during site event processing.
// Add new cell to the cell records vector.
cell_records_.push_back(voronoi_cell_type(site2, &edge2));
- cell_records_.back().num_incident_edges_++;
+ cell_records_.back().inc_num_incident_edges();
// Update pointers to cells.
edge1.cell(&cell_records_[site_index1]);
@@ -716,20 +735,14 @@
const circle_event_type &circle,
voronoi_edge_type *edge12,
voronoi_edge_type *edge23) {
- // Update counters.
- num_vertex_records_++;
- num_edge_records_++;
-
// Update bounding rectangle.
//voronoi_rect_.update(circle.get_center());
// Add new voronoi vertex with point at center of the circle.
- vertex_records_.push_back(voronoi_vertex_type(
- circle.get_erc_x(), circle.get_erc_y(), circle.get_erc_denom(), edge12));
+ robust_vertices_.push_back(robust_voronoi_vertex<T>(
+ circle.get_erc_x(), circle.get_erc_y(), circle.get_erc_denom()));
+ vertex_records_.push_back(voronoi_vertex_type(&robust_vertices_.back(), edge12));
voronoi_vertex_type &new_vertex = vertex_records_.back();
- new_vertex.num_incident_edges_ = 3;
- new_vertex.voronoi_record_it = vertex_records_.end();
- new_vertex.voronoi_record_it--;
// Update two input bisectors and their twin half-edges with
// new voronoi vertex.
@@ -740,13 +753,13 @@
edge_records_.push_back(voronoi_edge_type());
voronoi_edge_type &new_edge1 = edge_records_.back();
new_edge1.cell(&cell_records_[site1.get_site_index()]);
- new_edge1.cell_->num_incident_edges_++;
+ new_edge1.cell()->inc_num_incident_edges();
// Add new half-edge.
edge_records_.push_back(voronoi_edge_type());
voronoi_edge_type &new_edge2 = edge_records_.back();
new_edge2.cell(&cell_records_[site3.get_site_index()]);
- new_edge2.cell_->num_incident_edges_++;
+ new_edge2.cell()->inc_num_incident_edges();
// Update twin pointers of the new half-edges.
new_edge1.twin(&new_edge2);
@@ -757,9 +770,9 @@
// to the new voronoi vertex.
edge12->prev(&new_edge1);
new_edge1.next(edge12);
- edge12->twin_->next(edge23);
+ edge12->twin()->next(edge23);
edge23->prev(edge12->twin());
- edge23->twin_->next(&new_edge2);
+ edge23->twin()->next(&new_edge2);
new_edge2.prev(edge23->twin());
return &new_edge1;
@@ -768,9 +781,11 @@
void simplify() {
voronoi_edge_iterator_type edge_it1;
voronoi_edge_iterator_type edge_it = edge_records_.begin();
+ num_cell_records_ = cell_records_.size();
// Return in case of collinear sites input.
- if (num_vertex_records_ == 0) {
+ if (vertex_records_.empty()) {
+ num_edge_records_ = num_cell_records_ - 1;
if (edge_it == edge_records_.end())
return;
@@ -804,47 +819,61 @@
edge_it1 = edge_it;
std::advance(edge_it, 2);
- if (!edge_it1->vertex0() || !edge_it1->vertex1())
+ if (!edge_it1->vertex0() || !edge_it1->vertex1()) {
+ num_edge_records_++;
continue;
+ }
- const voronoi_vertex_type *p1 = edge_it1->vertex0();
- const voronoi_vertex_type *p2 = edge_it1->vertex1();
- detail::epsilon_robust_comparator<T> lhs1(p1->center_x * p2->denom);
- detail::epsilon_robust_comparator<T> rhs1(p1->denom * p2->center_x);
- detail::epsilon_robust_comparator<T> lhs2(p1->center_y * p2->denom);
- detail::epsilon_robust_comparator<T> rhs2(p1->denom * p2->center_y);
+ const robust_voronoi_vertex<T> *v1 = edge_it1->vertex0()->robust_vertex();
+ const robust_voronoi_vertex<T> *v2 = edge_it1->vertex1()->robust_vertex();
+ detail::epsilon_robust_comparator<T> lhs1(v1->center_x * v2->denom);
+ detail::epsilon_robust_comparator<T> rhs1(v1->denom * v2->center_x);
+ detail::epsilon_robust_comparator<T> lhs2(v1->center_y * v2->denom);
+ detail::epsilon_robust_comparator<T> rhs2(v1->denom * v2->center_y);
if (lhs1.compares_undefined(rhs1, 64) && lhs2.compares_undefined(rhs2, 64)) {
// Decrease number of cell incident edges.
- edge_it1->cell_->num_incident_edges_--;
- edge_it1->twin_->cell_->num_incident_edges_--;
+ edge_it1->cell()->dec_num_incident_edges();
+ edge_it1->twin()->cell()->dec_num_incident_edges();
// To guarantee N*lon(N) time we merge vertex with
// less incident edges to the one with more.
- if (edge_it1->cell_->incident_edge_ == &(*edge_it1)) {
- if (edge_it1->cell_->incident_edge_ == edge_it1->next_) {
- edge_it1->cell_->incident_edge_ = NULL;
+ if (edge_it1->cell()->incident_edge() == &(*edge_it1)) {
+ if (edge_it1->cell()->incident_edge() == edge_it1->next()) {
+ edge_it1->cell()->incident_edge(NULL);
} else {
- edge_it1->cell_->incident_edge_ = edge_it1->next_;
+ edge_it1->cell()->incident_edge(edge_it1->next());
}
}
- if (edge_it1->twin_->cell_->incident_edge_ == edge_it1->twin_) {
- if (edge_it1->twin_->cell_->incident_edge_ == edge_it1->twin_->next_) {
- edge_it1->twin_->cell_->incident_edge_ = NULL;
+ if (edge_it1->twin()->cell()->incident_edge() == edge_it1->twin()) {
+ if (edge_it1->twin()->cell()->incident_edge() == edge_it1->twin()->next()) {
+ edge_it1->twin()->cell()->incident_edge(NULL);
} else {
- edge_it1->twin_->cell_->incident_edge_ = edge_it1->twin_->next_;
+ edge_it1->twin()->cell()->incident_edge(edge_it1->twin()->next());
}
}
- if (edge_it1->vertex0()->num_incident_edges_ >=
- edge_it1->vertex1()->num_incident_edges_) {
+ if (edge_it1->vertex0()->num_incident_edges() >=
+ edge_it1->vertex1()->num_incident_edges()) {
simplify_edge(&(*edge_it1));
} else {
- simplify_edge(edge_it1->twin_);
+ simplify_edge(edge_it1->twin());
}
// Remove zero length edges.
edge_records_.erase(edge_it1, edge_it);
- num_edge_records_--;
+ } else {
+ num_edge_records_++;
+ }
+ }
+ robust_vertices_.clear();
+
+ for (voronoi_vertex_iterator_type vertex_it = vertex_records_.begin();
+ vertex_it != vertex_records_.end();) {
+ if (vertex_it->incident_edge() == NULL) {
+ vertex_it = vertex_records_.erase(vertex_it);
+ } else {
+ vertex_it++;
+ num_vertex_records_++;
}
}
@@ -852,24 +881,24 @@
for (voronoi_cell_iterator_type cell_it = cell_records_.begin();
cell_it != cell_records_.end(); cell_it++) {
// Move to the previous edge while it is possible in the CW direction.
- voronoi_edge_type *cur_edge = cell_it->incident_edge_;
+ voronoi_edge_type *cur_edge = cell_it->incident_edge();
if (cur_edge) {
- while (cur_edge->prev_ != NULL) {
- cur_edge = cur_edge->prev_;
+ while (cur_edge->prev() != NULL) {
+ cur_edge = cur_edge->prev();
// Terminate if this is not a boundary cell.
- if (cur_edge == cell_it->incident_edge_)
+ if (cur_edge == cell_it->incident_edge())
break;
}
// Rewind incident edge pointer to the leftmost edge for the boundary cells.
- cell_it->incident_edge_ = cur_edge;
+ cell_it->incident_edge(cur_edge);
// Set up prev/next half-edge pointers for ray edges.
- if (cur_edge->prev_ == NULL) {
- voronoi_edge_type *last_edge = cell_it->incident_edge_;
- while (last_edge->next_ != NULL)
- last_edge = last_edge->next_;
+ if (cur_edge->prev() == NULL) {
+ voronoi_edge_type *last_edge = cell_it->incident_edge();
+ while (last_edge->next() != NULL)
+ last_edge = last_edge->next();
last_edge->next(cur_edge);
cur_edge->prev(last_edge);
}
@@ -883,7 +912,8 @@
voronoi_vertex_type *vertex2 = edge->vertex1();
// Update number of incident edges.
- vertex1->num_incident_edges_ += vertex2->num_incident_edges_ - 2;
+ vertex1->num_incident_edges(
+ vertex1->num_incident_edges() + vertex2->num_incident_edges() - 2);
// Update second vertex incident edges start and end points.
voronoi_edge_type *updated_edge = edge->twin()->rot_next();
@@ -909,16 +939,17 @@
// Change incident edge pointer of a vertex if it corresponds to the
// degenerate edge.
- if (vertex1->incident_edge() == edge)
- vertex1->incident_edge_ = edge->rot_prev();
+ if (vertex1->incident_edge() == edge) {
+ vertex1->incident_edge(edge->rot_prev());
+ }
// Remove second vertex from the vertex records list.
- if (vertex1->voronoi_record_it != vertex2->voronoi_record_it) {
- vertex_records_.erase(vertex2->voronoi_record_it);
- num_vertex_records_--;
+ if (vertex1 != vertex2) {
+ vertex2->incident_edge(NULL);
}
}
+ std::list< robust_voronoi_vertex<T> > robust_vertices_;
voronoi_cells_type cell_records_;
voronoi_vertices_type vertex_records_;
voronoi_edges_type edge_records_;
Added: sandbox/SOC/2010/sweepline/libs/sweepline/example/input_data/example_051.txt
==============================================================================
--- (empty file)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/example/input_data/example_051.txt 2010-12-06 10:05:28 EST (Mon, 06 Dec 2010)
@@ -0,0 +1,5 @@
+0
+3
+14 76 38 29
+37 47 61 50
+39 37 41 35
Added: sandbox/SOC/2010/sweepline/libs/sweepline/example/input_data/example_052.txt
==============================================================================
--- (empty file)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/example/input_data/example_052.txt 2010-12-06 10:05:28 EST (Mon, 06 Dec 2010)
@@ -0,0 +1,5 @@
+2
+2 -5
+3 -3
+1
+0 0 2 -7
\ No newline at end of file
Added: sandbox/SOC/2010/sweepline/libs/sweepline/example/input_data/example_053.txt
==============================================================================
--- (empty file)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/example/input_data/example_053.txt 2010-12-06 10:05:28 EST (Mon, 06 Dec 2010)
@@ -0,0 +1,5 @@
+1
+-35 -49
+2
+-48 -29 -46 -78
+-46 -46 -45 -42
\ No newline at end of file
Added: sandbox/SOC/2010/sweepline/libs/sweepline/example/input_data/example_054.txt
==============================================================================
--- (empty file)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/example/input_data/example_054.txt 2010-12-06 10:05:28 EST (Mon, 06 Dec 2010)
@@ -0,0 +1,11 @@
+0
+9
+-50 -29 -49 -73
+-48 -29 -46 -78
+-46 -46 -45 -42
+-35 -49 -34 -49
+-30 -2 -29 3
+-43 16 -40 6
+-36 38 -34 49
+-35 39 -31 37
+-28 34 -27 -9
\ No newline at end of file
Added: sandbox/SOC/2010/sweepline/libs/sweepline/example/output_data/example_051.png
==============================================================================
Binary file. No diff available.
Added: sandbox/SOC/2010/sweepline/libs/sweepline/example/output_data/example_052.png
==============================================================================
Binary file. No diff available.
Added: sandbox/SOC/2010/sweepline/libs/sweepline/example/output_data/example_053.png
==============================================================================
Binary file. No diff available.
Added: sandbox/SOC/2010/sweepline/libs/sweepline/example/output_data/example_054.png
==============================================================================
Binary file. No diff available.
Modified: sandbox/SOC/2010/sweepline/libs/sweepline/test/benchmark_test.cpp
==============================================================================
--- sandbox/SOC/2010/sweepline/libs/sweepline/test/benchmark_test.cpp (original)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/test/benchmark_test.cpp 2010-12-06 10:05:28 EST (Mon, 06 Dec 2010)
@@ -41,7 +41,7 @@
std::vector< point_2d<T> > points;
points.reserve(num_points);
- time_t start_time = time(NULL);
+ clock_t start_time = clock();
int num_times = max_points / num_points;
for (int cur = 0; cur < num_times; cur++) {
for (int cur_point = 0; cur_point < num_points; cur_point++) {
@@ -52,8 +52,8 @@
build_voronoi(points, test_output);
points.clear();
}
- time_t end_time = time(NULL);
- double running_time = static_cast<double>(end_time - start_time) / num_times;
+ clock_t end_time = clock();
+ double running_time = static_cast<double>(end_time - start_time) / CLOCKS_PER_SEC / num_times;
fprintf(bench_file,
"Number of points = %8d; Overall time = %2d; Time per one input = %9.6f.\n",
Modified: sandbox/SOC/2010/sweepline/libs/sweepline/test/sweepline_test.cpp
==============================================================================
--- sandbox/SOC/2010/sweepline/libs/sweepline/test/sweepline_test.cpp (original)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/test/sweepline_test.cpp 2010-12-06 10:05:28 EST (Mon, 06 Dec 2010)
@@ -59,338 +59,321 @@
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 T coordinate_type;
-// typedef typename voronoi_output_clipped<coordinate_type>::voronoi_edge_type voronoi_edge_type;
-// typedef typename voronoi_output_clipped<coordinate_type>::voronoi_cell_const_iterator_type
-// voronoi_cell_const_iterator_type;
-//
-// 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<coordinate_type> test_output;
-// test_voronoi_builder.clip(test_output);
-// VERIFY_VORONOI_OUTPUT(test_output, COMPLETE_VERIFICATION);
-//
-// 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.cell_records.size()), 2);
-// BOOST_CHECK_EQUAL(static_cast<int>(test_output.vertex_records.size()), 0);
-// BOOST_CHECK_EQUAL(static_cast<int>(test_output.edge_records.size()), 2);
-//
-// BOOST_CHECK_EQUAL(test_output.num_cell_records, 2);
-// BOOST_CHECK_EQUAL(test_output.num_vertex_records, 0);
-// BOOST_CHECK_EQUAL(test_output.num_edge_records, 1);
-//
-// voronoi_cell_const_iterator_type cell_it = test_output.cell_records.begin();
-// BOOST_CHECK_EQUAL(cell_it->num_incident_edges, 1);
-// cell_it++;
-// BOOST_CHECK_EQUAL(cell_it->num_incident_edges, 1);
-//
-// voronoi_edge_type *edge1_1 = cell_it->incident_edge;
-// voronoi_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 == NULL, true);
-// BOOST_CHECK_EQUAL(edge1_1->rot_prev == NULL, 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 == NULL, true);
-// BOOST_CHECK_EQUAL(edge1_2->rot_prev == NULL, true);
-//}
-//
-//// Sites: (0, 0), (1, 1), (2, 2).
-//BOOST_AUTO_TEST_CASE_TEMPLATE(collinear_sites_test2, T, test_types) {
-// typedef T coordinate_type;
-// typedef typename voronoi_output_clipped<coordinate_type>::voronoi_edge_type voronoi_edge_type;
-// typedef typename voronoi_output_clipped<coordinate_type>::voronoi_cell_const_iterator_type
-// voronoi_cell_const_iterator_type;
-//
-// 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<coordinate_type> test_output;
-// test_voronoi_builder.clip(test_output);
-// VERIFY_VORONOI_OUTPUT(test_output, COMPLETE_VERIFICATION);
-//
-// 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.cell_records.size()), 3);
-// BOOST_CHECK_EQUAL(static_cast<int>(test_output.vertex_records.size()), 0);
-// BOOST_CHECK_EQUAL(static_cast<int>(test_output.edge_records.size()), 4);
-//
-// BOOST_CHECK_EQUAL(test_output.num_cell_records, 3);
-// BOOST_CHECK_EQUAL(test_output.num_vertex_records, 0);
-// BOOST_CHECK_EQUAL(test_output.num_edge_records, 2);
-//
-// voronoi_cell_const_iterator_type cell_it = test_output.cell_records.begin();
-// BOOST_CHECK_EQUAL(cell_it->num_incident_edges, 1);
-// voronoi_edge_type *edge1_1 = cell_it->incident_edge;
-// voronoi_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);
-// voronoi_edge_type *edge2_2 = cell_it->incident_edge;
-// voronoi_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 == NULL && edge1_1->rot_prev == NULL, true);
-// BOOST_CHECK_EQUAL(edge1_2->rot_next == NULL && edge1_2->rot_prev == NULL, true);
-// BOOST_CHECK_EQUAL(edge2_1->rot_next == NULL && edge2_1->rot_prev == NULL, true);
-// BOOST_CHECK_EQUAL(edge2_2->next == edge2_2 && edge2_2->prev == edge2_2, true);
-// BOOST_CHECK_EQUAL(edge2_2->rot_next == NULL && edge2_2->rot_prev == NULL, 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 T coordinate_type;
-// typedef typename voronoi_output_clipped<coordinate_type>::voronoi_edge_type voronoi_edge_type;
-// typedef typename voronoi_output_clipped<coordinate_type>::voronoi_vertex_const_iterator_type
-// voronoi_vertex_const_iterator_type;
-//
-// 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<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<coordinate_type> test_output;
-// test_beach_line.clip(test_output);
-// VERIFY_VORONOI_OUTPUT(test_output, COMPLETE_VERIFICATION);
-//
-// 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.cell_records.size()), 3);
-// BOOST_CHECK_EQUAL(static_cast<int>(test_output.vertex_records.size()), 1);
-//
-// voronoi_vertex_const_iterator_type it = test_output.vertex_records.begin();
-// BOOST_CHECK_EQUAL(it->num_incident_edges, 3);
-// BOOST_CHECK_EQUAL(it->vertex.x() == static_cast<coordinate_type>(0.25) &&
-// it->vertex.y() == static_cast<coordinate_type>(2.0), true);
-//
-// voronoi_edge_type *edge1_1 = it->incident_edge;
-// voronoi_edge_type *edge1_2 = edge1_1->twin;
-// CHECK_EQUAL_POINTS(edge1_1->cell->get_point0(), point3);
-// CHECK_EQUAL_POINTS(edge1_2->cell->get_point0(), point1);
-//
-// voronoi_edge_type *edge2_1 = edge1_1->rot_prev;
-// voronoi_edge_type *edge2_2 = edge2_1->twin;
-// CHECK_EQUAL_POINTS(edge2_1->cell->get_point0(), point1);
-// CHECK_EQUAL_POINTS(edge2_2->cell->get_point0(), point2);
-//
-// voronoi_edge_type *edge3_1 = edge2_1->rot_prev;
-// voronoi_edge_type *edge3_2 = edge3_1->twin;
-// CHECK_EQUAL_POINTS(edge3_1->cell->get_point0(), point2);
-// CHECK_EQUAL_POINTS(edge3_2->cell->get_point0(), point3);
-//
-// BOOST_CHECK_EQUAL(edge1_2->twin == edge1_1, true);
-// BOOST_CHECK_EQUAL(edge2_2->twin == edge2_1, true);
-// BOOST_CHECK_EQUAL(edge3_2->twin == edge3_1, true);
-//
-// BOOST_CHECK_EQUAL(edge1_1->prev == edge3_2 && edge1_1->next == edge3_2, true);
-// BOOST_CHECK_EQUAL(edge2_1->prev == edge1_2 && edge2_1->next == edge1_2, true);
-// BOOST_CHECK_EQUAL(edge3_1->prev == edge2_2 && edge3_1->next == edge2_2, true);
-//
-// BOOST_CHECK_EQUAL(edge1_2->next == edge2_1 && edge1_2->prev == edge2_1, true);
-// BOOST_CHECK_EQUAL(edge2_2->next == edge3_1 && edge2_2->prev == edge3_1, true);
-// BOOST_CHECK_EQUAL(edge3_2->next == edge1_1 && edge3_2->prev == edge1_1, true);
-//
-// BOOST_CHECK_EQUAL(edge1_1->rot_next == edge3_1, true);
-// BOOST_CHECK_EQUAL(edge3_1->rot_next == edge2_1, true);
-// BOOST_CHECK_EQUAL(edge2_1->rot_next == edge1_1, true);
-//}
-//
-//// Sites: (0, 1), (2, 0), (2, 4).
-//BOOST_AUTO_TEST_CASE_TEMPLATE(triangle_test2, T, test_types) {
-// typedef T coordinate_type;
-// typedef typename voronoi_output_clipped<coordinate_type>::voronoi_edge_type voronoi_edge_type;
-// typedef typename voronoi_output_clipped<coordinate_type>::voronoi_vertex_const_iterator_type
-// voronoi_vertex_const_iterator_type;
-//
-// 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<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<coordinate_type> test_output;
-// test_beach_line.clip(test_output);
-// VERIFY_VORONOI_OUTPUT(test_output, COMPLETE_VERIFICATION);
-//
-// BOOST_CHECK_EQUAL(static_cast<int>(test_output.cell_records.size()), 3);
-// BOOST_CHECK_EQUAL(static_cast<int>(test_output.vertex_records.size()), 1);
-//
-// voronoi_vertex_const_iterator_type it = test_output.vertex_records.begin();
-// BOOST_CHECK_EQUAL(it->num_incident_edges, 3);
-// BOOST_CHECK_EQUAL(it->vertex.x() == static_cast<coordinate_type>(1.75) &&
-// it->vertex.y() == static_cast<coordinate_type>(2.0), true);
-//
-// voronoi_edge_type *edge1_1 = it->incident_edge;
-// voronoi_edge_type *edge1_2 = edge1_1->twin;
-// CHECK_EQUAL_POINTS(edge1_1->cell->get_point0(), point2);
-// CHECK_EQUAL_POINTS(edge1_2->cell->get_point0(), point1);
-//
-// voronoi_edge_type *edge2_1 = edge1_1->rot_prev;
-// voronoi_edge_type *edge2_2 = edge2_1->twin;
-// CHECK_EQUAL_POINTS(edge2_1->cell->get_point0(), point1);
-// CHECK_EQUAL_POINTS(edge2_2->cell->get_point0(), point3);
-//
-// voronoi_edge_type *edge3_1 = edge2_1->rot_prev;
-// voronoi_edge_type *edge3_2 = edge3_1->twin;
-// CHECK_EQUAL_POINTS(edge3_1->cell->get_point0(), point3);
-// CHECK_EQUAL_POINTS(edge3_2->cell->get_point0(), point2);
-//
-// BOOST_CHECK_EQUAL(edge1_2->twin == edge1_1, true);
-// BOOST_CHECK_EQUAL(edge2_2->twin == edge2_1, true);
-// BOOST_CHECK_EQUAL(edge3_2->twin == edge3_1, true);
-//
-// BOOST_CHECK_EQUAL(edge1_1->prev == edge3_2 && edge1_1->next == edge3_2, true);
-// BOOST_CHECK_EQUAL(edge2_1->prev == edge1_2 && edge2_1->next == edge1_2, true);
-// BOOST_CHECK_EQUAL(edge3_1->prev == edge2_2 && edge3_1->next == edge2_2, true);
-//
-// BOOST_CHECK_EQUAL(edge1_2->next == edge2_1 && edge1_2->prev == edge2_1, true);
-// BOOST_CHECK_EQUAL(edge2_2->next == edge3_1 && edge2_2->prev == edge3_1, true);
-// BOOST_CHECK_EQUAL(edge3_2->next == edge1_1 && edge3_2->prev == edge1_1, true);
-//
-// BOOST_CHECK_EQUAL(edge1_1->rot_next == edge3_1, true);
-// BOOST_CHECK_EQUAL(edge3_1->rot_next == edge2_1, true);
-// BOOST_CHECK_EQUAL(edge2_1->rot_next == edge1_1, true);
-//}
-//
-//// Sites: (0, 0), (0, 1), (1, 0), (1, 1).
-//BOOST_AUTO_TEST_CASE_TEMPLATE(square_test1, T, test_types) {
-// typedef T coordinate_type;
-// typedef typename voronoi_output_clipped<coordinate_type>::voronoi_edge_type voronoi_edge_type;
-// typedef typename voronoi_output_clipped<coordinate_type>::voronoi_vertex_const_iterator_type
-// voronoi_vertex_const_iterator_type;
-//
-// 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<coordinate_type> test_output;
-// test_beach_line.clip(test_output);
-// VERIFY_VORONOI_OUTPUT(test_output, COMPLETE_VERIFICATION);
-//
-// BOOST_CHECK_EQUAL(test_output.num_cell_records, 4);
-// BOOST_CHECK_EQUAL(test_output.num_vertex_records, 1);
-// BOOST_CHECK_EQUAL(test_output.num_edge_records, 4);
-//
-// // Check voronoi vertex.
-// voronoi_vertex_const_iterator_type it = test_output.vertex_records.begin();
-// BOOST_CHECK_EQUAL(it->num_incident_edges, 4);
-// BOOST_CHECK_EQUAL(it->vertex.x() == static_cast<coordinate_type>(0.5) &&
-// it->vertex.y() == static_cast<coordinate_type>(0.5), true);
-//
-// // Check voronoi edges.
-// voronoi_edge_type *edge1_1 = it->incident_edge;
-// voronoi_edge_type *edge1_2 = edge1_1->twin;
-// CHECK_EQUAL_POINTS(edge1_1->cell->get_point0(), points[1]);
-// CHECK_EQUAL_POINTS(edge1_2->cell->get_point0(), points[3]);
-//
-// voronoi_edge_type *edge2_1 = edge1_1->rot_prev;
-// voronoi_edge_type *edge2_2 = edge2_1->twin;
-// CHECK_EQUAL_POINTS(edge2_1->cell->get_point0(), points[3]);
-// CHECK_EQUAL_POINTS(edge2_2->cell->get_point0(), points[2]);
-//
-// voronoi_edge_type *edge3_1 = edge2_1->rot_prev;
-// voronoi_edge_type *edge3_2 = edge3_1->twin;
-// CHECK_EQUAL_POINTS(edge3_1->cell->get_point0(), points[2]);
-// CHECK_EQUAL_POINTS(edge3_2->cell->get_point0(), points[0]);
-//
-// voronoi_edge_type *edge4_1 = edge3_1->rot_prev;
-// voronoi_edge_type *edge4_2 = edge4_1->twin;
-// CHECK_EQUAL_POINTS(edge4_1->cell->get_point0(), points[0]);
-// CHECK_EQUAL_POINTS(edge4_2->cell->get_point0(), points[1]);
-//
-// BOOST_CHECK_EQUAL(edge1_2->twin == edge1_1, true);
-// BOOST_CHECK_EQUAL(edge2_2->twin == edge2_1, true);
-// BOOST_CHECK_EQUAL(edge3_2->twin == edge3_1, true);
-// BOOST_CHECK_EQUAL(edge4_2->twin == edge4_1, true);
-//
-// BOOST_CHECK_EQUAL(edge1_1->prev == edge4_2 && edge1_1->next == edge4_2, true);
-// BOOST_CHECK_EQUAL(edge2_1->prev == edge1_2 && edge2_1->next == edge1_2, true);
-// BOOST_CHECK_EQUAL(edge3_1->prev == edge2_2 && edge3_1->next == edge2_2, true);
-// BOOST_CHECK_EQUAL(edge4_1->prev == edge3_2 && edge4_1->next == edge3_2, true);
-//
-// BOOST_CHECK_EQUAL(edge1_2->next == edge2_1 && edge1_2->prev == edge2_1, true);
-// BOOST_CHECK_EQUAL(edge2_2->next == edge3_1 && edge2_2->prev == edge3_1, true);
-// BOOST_CHECK_EQUAL(edge3_2->next == edge4_1 && edge3_2->prev == edge4_1, true);
-// BOOST_CHECK_EQUAL(edge4_2->next == edge1_1 && edge4_2->prev == edge1_1, true);
-//
-// BOOST_CHECK_EQUAL(edge1_1->rot_next == edge4_1, true);
-// BOOST_CHECK_EQUAL(edge4_1->rot_next == edge3_1, true);
-// BOOST_CHECK_EQUAL(edge3_1->rot_next == edge2_1, true);
-// BOOST_CHECK_EQUAL(edge2_1->rot_next == edge1_1, true);
-//}
-//
+
+// Sites: (0, 0), (0, 1).
+BOOST_AUTO_TEST_CASE_TEMPLATE(collinear_sites_test1, T, test_types) {
+ typedef T coordinate_type;
+ typedef typename voronoi_output<coordinate_type>::voronoi_edge_type voronoi_edge_type;
+ typedef typename voronoi_output<coordinate_type>::voronoi_cell_const_iterator_type
+ voronoi_cell_const_iterator_type;
+
+ 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)));
+ voronoi_output<coordinate_type> test_output;
+ build_voronoi(points, test_output);
+ VERIFY_VORONOI_OUTPUT(test_output, COMPLETE_VERIFICATION);
+
+ BRect<coordinate_type> bounding_rectangle = test_output.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.cell_records().size()), 2);
+ BOOST_CHECK_EQUAL(static_cast<int>(test_output.vertex_records().size()), 0);
+ BOOST_CHECK_EQUAL(static_cast<int>(test_output.edge_records().size()), 2);
+
+ BOOST_CHECK_EQUAL(test_output.num_cell_records(), 2);
+ BOOST_CHECK_EQUAL(test_output.num_vertex_records(), 0);
+ BOOST_CHECK_EQUAL(test_output.num_edge_records(), 1);
+
+ voronoi_cell_const_iterator_type cell_it = test_output.cell_records().begin();
+ BOOST_CHECK_EQUAL(cell_it->num_incident_edges(), 1);
+ cell_it++;
+ BOOST_CHECK_EQUAL(cell_it->num_incident_edges(), 1);
+
+ const voronoi_edge_type *edge1_1 = cell_it->incident_edge();
+ const voronoi_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() == NULL, true);
+ BOOST_CHECK_EQUAL(edge1_1->rot_prev() == NULL, 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() == NULL, true);
+ BOOST_CHECK_EQUAL(edge1_2->rot_prev() == NULL, true);
+}
+
+// Sites: (0, 0), (1, 1), (2, 2).
+BOOST_AUTO_TEST_CASE_TEMPLATE(collinear_sites_test2, T, test_types) {
+ typedef T coordinate_type;
+ typedef typename voronoi_output<coordinate_type>::voronoi_edge_type voronoi_edge_type;
+ typedef typename voronoi_output<coordinate_type>::voronoi_cell_const_iterator_type
+ voronoi_cell_const_iterator_type;
+
+ 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)));
+ voronoi_output<coordinate_type> test_output;
+ build_voronoi(points, test_output);
+ VERIFY_VORONOI_OUTPUT(test_output, COMPLETE_VERIFICATION);
+
+ BRect<coordinate_type> bounding_rectangle = test_output.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.cell_records().size()), 3);
+ BOOST_CHECK_EQUAL(static_cast<int>(test_output.vertex_records().size()), 0);
+ BOOST_CHECK_EQUAL(static_cast<int>(test_output.edge_records().size()), 4);
+
+ BOOST_CHECK_EQUAL(test_output.num_cell_records(), 3);
+ BOOST_CHECK_EQUAL(test_output.num_vertex_records(), 0);
+ BOOST_CHECK_EQUAL(test_output.num_edge_records(), 2);
+
+ voronoi_cell_const_iterator_type cell_it = test_output.cell_records().begin();
+ BOOST_CHECK_EQUAL(cell_it->num_incident_edges(), 1);
+ const voronoi_edge_type *edge1_1 = cell_it->incident_edge();
+ const voronoi_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);
+ const voronoi_edge_type *edge2_2 = cell_it->incident_edge();
+ const voronoi_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() == NULL && edge1_1->rot_prev() == NULL, true);
+ BOOST_CHECK_EQUAL(edge1_2->rot_next() == NULL && edge1_2->rot_prev() == NULL, true);
+ BOOST_CHECK_EQUAL(edge2_1->rot_next() == NULL && edge2_1->rot_prev() == NULL, true);
+ BOOST_CHECK_EQUAL(edge2_2->next() == edge2_2 && edge2_2->prev() == edge2_2, true);
+ BOOST_CHECK_EQUAL(edge2_2->rot_next() == NULL && edge2_2->rot_prev() == NULL, 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 T coordinate_type;
+ typedef typename voronoi_output<coordinate_type>::voronoi_edge_type voronoi_edge_type;
+ typedef typename voronoi_output<coordinate_type>::voronoi_vertex_const_iterator_type
+ voronoi_vertex_const_iterator_type;
+
+ 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<coordinate_type> > points;
+ points.push_back(point1);
+ points.push_back(point2);
+ points.push_back(point3);
+
+ voronoi_output<coordinate_type> test_output;
+ build_voronoi(points, test_output);
+ VERIFY_VORONOI_OUTPUT(test_output, COMPLETE_VERIFICATION);
+
+ BRect<coordinate_type> bounding_rectangle = test_output.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.cell_records().size()), 3);
+ BOOST_CHECK_EQUAL(static_cast<int>(test_output.vertex_records().size()), 1);
+
+ voronoi_vertex_const_iterator_type it = test_output.vertex_records().begin();
+ BOOST_CHECK_EQUAL(it->num_incident_edges(), 3);
+ BOOST_CHECK_EQUAL(it->vertex().x() == static_cast<coordinate_type>(0.25) &&
+ it->vertex().y() == static_cast<coordinate_type>(2.0), true);
+
+ const voronoi_edge_type *edge1_1 = it->incident_edge();
+ const voronoi_edge_type *edge1_2 = edge1_1->twin();
+ CHECK_EQUAL_POINTS(edge1_1->cell()->get_point0(), point3);
+ CHECK_EQUAL_POINTS(edge1_2->cell()->get_point0(), point1);
+
+ const voronoi_edge_type *edge2_1 = edge1_1->rot_prev();
+ const voronoi_edge_type *edge2_2 = edge2_1->twin();
+ CHECK_EQUAL_POINTS(edge2_1->cell()->get_point0(), point1);
+ CHECK_EQUAL_POINTS(edge2_2->cell()->get_point0(), point2);
+
+ const voronoi_edge_type *edge3_1 = edge2_1->rot_prev();
+ const voronoi_edge_type *edge3_2 = edge3_1->twin();
+ CHECK_EQUAL_POINTS(edge3_1->cell()->get_point0(), point2);
+ CHECK_EQUAL_POINTS(edge3_2->cell()->get_point0(), point3);
+
+ BOOST_CHECK_EQUAL(edge1_2->twin() == edge1_1, true);
+ BOOST_CHECK_EQUAL(edge2_2->twin() == edge2_1, true);
+ BOOST_CHECK_EQUAL(edge3_2->twin() == edge3_1, true);
+
+ BOOST_CHECK_EQUAL(edge1_1->prev() == edge3_2 && edge1_1->next() == edge3_2, true);
+ BOOST_CHECK_EQUAL(edge2_1->prev() == edge1_2 && edge2_1->next() == edge1_2, true);
+ BOOST_CHECK_EQUAL(edge3_1->prev() == edge2_2 && edge3_1->next() == edge2_2, true);
+
+ BOOST_CHECK_EQUAL(edge1_2->next() == edge2_1 && edge1_2->prev() == edge2_1, true);
+ BOOST_CHECK_EQUAL(edge2_2->next() == edge3_1 && edge2_2->prev() == edge3_1, true);
+ BOOST_CHECK_EQUAL(edge3_2->next() == edge1_1 && edge3_2->prev() == edge1_1, true);
+
+ BOOST_CHECK_EQUAL(edge1_1->rot_next() == edge3_1, true);
+ BOOST_CHECK_EQUAL(edge3_1->rot_next() == edge2_1, true);
+ BOOST_CHECK_EQUAL(edge2_1->rot_next() == edge1_1, true);
+}
+
+// Sites: (0, 1), (2, 0), (2, 4).
+BOOST_AUTO_TEST_CASE_TEMPLATE(triangle_test2, T, test_types) {
+ typedef T coordinate_type;
+ typedef typename voronoi_output<coordinate_type>::voronoi_edge_type voronoi_edge_type;
+ typedef typename voronoi_output<coordinate_type>::voronoi_vertex_const_iterator_type
+ voronoi_vertex_const_iterator_type;
+
+ 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<coordinate_type> > points;
+ points.push_back(point1);
+ points.push_back(point2);
+ points.push_back(point3);
+
+ voronoi_output<coordinate_type> test_output;
+ build_voronoi(points, test_output);
+ VERIFY_VORONOI_OUTPUT(test_output, COMPLETE_VERIFICATION);
+
+ BOOST_CHECK_EQUAL(static_cast<int>(test_output.cell_records().size()), 3);
+ BOOST_CHECK_EQUAL(static_cast<int>(test_output.vertex_records().size()), 1);
+
+ voronoi_vertex_const_iterator_type it = test_output.vertex_records().begin();
+ BOOST_CHECK_EQUAL(it->num_incident_edges(), 3);
+ BOOST_CHECK_EQUAL(it->vertex().x() == static_cast<coordinate_type>(1.75) &&
+ it->vertex().y() == static_cast<coordinate_type>(2.0), true);
+
+ const voronoi_edge_type *edge1_1 = it->incident_edge();
+ const voronoi_edge_type *edge1_2 = edge1_1->twin();
+ CHECK_EQUAL_POINTS(edge1_1->cell()->get_point0(), point2);
+ CHECK_EQUAL_POINTS(edge1_2->cell()->get_point0(), point1);
+
+ const voronoi_edge_type *edge2_1 = edge1_1->rot_prev();
+ const voronoi_edge_type *edge2_2 = edge2_1->twin();
+ CHECK_EQUAL_POINTS(edge2_1->cell()->get_point0(), point1);
+ CHECK_EQUAL_POINTS(edge2_2->cell()->get_point0(), point3);
+
+ const voronoi_edge_type *edge3_1 = edge2_1->rot_prev();
+ const voronoi_edge_type *edge3_2 = edge3_1->twin();
+ CHECK_EQUAL_POINTS(edge3_1->cell()->get_point0(), point3);
+ CHECK_EQUAL_POINTS(edge3_2->cell()->get_point0(), point2);
+
+ BOOST_CHECK_EQUAL(edge1_2->twin() == edge1_1, true);
+ BOOST_CHECK_EQUAL(edge2_2->twin() == edge2_1, true);
+ BOOST_CHECK_EQUAL(edge3_2->twin() == edge3_1, true);
+
+ BOOST_CHECK_EQUAL(edge1_1->prev() == edge3_2 && edge1_1->next() == edge3_2, true);
+ BOOST_CHECK_EQUAL(edge2_1->prev() == edge1_2 && edge2_1->next() == edge1_2, true);
+ BOOST_CHECK_EQUAL(edge3_1->prev() == edge2_2 && edge3_1->next() == edge2_2, true);
+
+ BOOST_CHECK_EQUAL(edge1_2->next() == edge2_1 && edge1_2->prev() == edge2_1, true);
+ BOOST_CHECK_EQUAL(edge2_2->next() == edge3_1 && edge2_2->prev() == edge3_1, true);
+ BOOST_CHECK_EQUAL(edge3_2->next() == edge1_1 && edge3_2->prev() == edge1_1, true);
+
+ BOOST_CHECK_EQUAL(edge1_1->rot_next() == edge3_1, true);
+ BOOST_CHECK_EQUAL(edge3_1->rot_next() == edge2_1, true);
+ BOOST_CHECK_EQUAL(edge2_1->rot_next() == edge1_1, true);
+}
+
+// Sites: (0, 0), (0, 1), (1, 0), (1, 1).
+BOOST_AUTO_TEST_CASE_TEMPLATE(square_test1, T, test_types) {
+ typedef T coordinate_type;
+ typedef typename voronoi_output<coordinate_type>::voronoi_edge_type voronoi_edge_type;
+ typedef typename voronoi_output<coordinate_type>::voronoi_vertex_const_iterator_type
+ voronoi_vertex_const_iterator_type;
+
+ 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)));
+
+ voronoi_output<coordinate_type> test_output;
+ build_voronoi(points, test_output);
+ VERIFY_VORONOI_OUTPUT(test_output, COMPLETE_VERIFICATION);
+
+ BOOST_CHECK_EQUAL(test_output.num_cell_records(), 4);
+ BOOST_CHECK_EQUAL(test_output.num_vertex_records(), 1);
+ BOOST_CHECK_EQUAL(test_output.num_edge_records(), 4);
+
+ // Check voronoi vertex.
+ voronoi_vertex_const_iterator_type it = test_output.vertex_records().begin();
+ BOOST_CHECK_EQUAL(it->num_incident_edges(), 4);
+ BOOST_CHECK_EQUAL(it->vertex().x() == static_cast<coordinate_type>(0.5) &&
+ it->vertex().y() == static_cast<coordinate_type>(0.5), true);
+
+ // Check voronoi edges.
+ const voronoi_edge_type *edge1_1 = it->incident_edge();
+ const voronoi_edge_type *edge1_2 = edge1_1->twin();
+ CHECK_EQUAL_POINTS(edge1_1->cell()->get_point0(), points[1]);
+ CHECK_EQUAL_POINTS(edge1_2->cell()->get_point0(), points[3]);
+
+ const voronoi_edge_type *edge2_1 = edge1_1->rot_prev();
+ const voronoi_edge_type *edge2_2 = edge2_1->twin();
+ CHECK_EQUAL_POINTS(edge2_1->cell()->get_point0(), points[3]);
+ CHECK_EQUAL_POINTS(edge2_2->cell()->get_point0(), points[2]);
+
+ const voronoi_edge_type *edge3_1 = edge2_1->rot_prev();
+ const voronoi_edge_type *edge3_2 = edge3_1->twin();
+ CHECK_EQUAL_POINTS(edge3_1->cell()->get_point0(), points[2]);
+ CHECK_EQUAL_POINTS(edge3_2->cell()->get_point0(), points[0]);
+
+ const voronoi_edge_type *edge4_1 = edge3_1->rot_prev();
+ const voronoi_edge_type *edge4_2 = edge4_1->twin();
+ CHECK_EQUAL_POINTS(edge4_1->cell()->get_point0(), points[0]);
+ CHECK_EQUAL_POINTS(edge4_2->cell()->get_point0(), points[1]);
+
+ BOOST_CHECK_EQUAL(edge1_2->twin() == edge1_1, true);
+ BOOST_CHECK_EQUAL(edge2_2->twin() == edge2_1, true);
+ BOOST_CHECK_EQUAL(edge3_2->twin() == edge3_1, true);
+ BOOST_CHECK_EQUAL(edge4_2->twin() == edge4_1, true);
+
+ BOOST_CHECK_EQUAL(edge1_1->prev() == edge4_2 && edge1_1->next() == edge4_2, true);
+ BOOST_CHECK_EQUAL(edge2_1->prev() == edge1_2 && edge2_1->next() == edge1_2, true);
+ BOOST_CHECK_EQUAL(edge3_1->prev() == edge2_2 && edge3_1->next() == edge2_2, true);
+ BOOST_CHECK_EQUAL(edge4_1->prev() == edge3_2 && edge4_1->next() == edge3_2, true);
+
+ BOOST_CHECK_EQUAL(edge1_2->next() == edge2_1 && edge1_2->prev() == edge2_1, true);
+ BOOST_CHECK_EQUAL(edge2_2->next() == edge3_1 && edge2_2->prev() == edge3_1, true);
+ BOOST_CHECK_EQUAL(edge3_2->next() == edge4_1 && edge3_2->prev() == edge4_1, true);
+ BOOST_CHECK_EQUAL(edge4_2->next() == edge1_1 && edge4_2->prev() == edge1_1, true);
+
+ BOOST_CHECK_EQUAL(edge1_1->rot_next() == edge4_1, true);
+ BOOST_CHECK_EQUAL(edge4_1->rot_next() == edge3_1, true);
+ BOOST_CHECK_EQUAL(edge3_1->rot_next() == edge2_1, true);
+ BOOST_CHECK_EQUAL(edge2_1->rot_next() == edge1_1, true);
+}
+
#ifdef NDEBUG
BOOST_AUTO_TEST_CASE_TEMPLATE(grid_test, T, test_types) {
voronoi_output<T> test_output_small, test_output_large;
@@ -465,179 +448,153 @@
VERIFY_VORONOI_OUTPUT(test_output, FAST_VERIFICATION);
}
#endif
-//
-//BOOST_AUTO_TEST_CASE_TEMPLATE(segment_sites_test1, T, test_types) {
-// typedef T coordinate_type;
-// voronoi_builder<coordinate_type> test_builder;
-// voronoi_output_clipped<coordinate_type> test_output;
-// std::vector< typename voronoi_builder<coordinate_type>::Segment2D > segm_vec;
-// point_2d<T> point1 = make_point_2d<T>(0, 0);
-// point_2d<T> point2 = make_point_2d<T>(1, 1);
-// segm_vec.push_back(std::make_pair< point_2d<T>, point_2d<T> >(point1, point2));
-// test_builder.init(segm_vec);
-// test_builder.run_sweepline();
-// test_builder.clip(test_output);
-// BOOST_CHECK_EQUAL(test_output.num_cell_records, 3);
-// BOOST_CHECK_EQUAL(test_output.num_vertex_records, 0);
-// BOOST_CHECK_EQUAL(test_output.num_edge_records, 2);
-// VERIFY_VORONOI_OUTPUT(test_output, NO_HALF_EDGE_INTERSECTIONS);
-//}
-//
-//BOOST_AUTO_TEST_CASE_TEMPLATE(segment_sites_test2, T, test_types) {
-// typedef T coordinate_type;
-// voronoi_builder<coordinate_type> test_builder;
-// voronoi_output_clipped<coordinate_type> test_output;
-// std::vector< point_2d<T> > point_vec;
-// std::vector< typename voronoi_builder<coordinate_type>::Segment2D > segm_vec;
-// point_2d<T> point1 = make_point_2d<T>(0, 0);
-// point_2d<T> point2 = make_point_2d<T>(4, 4);
-// point_2d<T> point3 = make_point_2d<T>(3, 1);
-// point_2d<T> point4 = make_point_2d<T>(1, 3);
-// segm_vec.push_back(std::make_pair< point_2d<T>, point_2d<T> >(point1, point2));
-// point_vec.push_back(point3);
-// point_vec.push_back(point4);
-// test_builder.init(point_vec, segm_vec);
-// test_builder.run_sweepline();
-// test_builder.clip(test_output);
-// BOOST_CHECK_EQUAL(test_output.num_cell_records, 5);
-// BOOST_CHECK_EQUAL(test_output.num_vertex_records, 4);
-// BOOST_CHECK_EQUAL(test_output.num_edge_records, 8);
-// VERIFY_VORONOI_OUTPUT(test_output, NO_HALF_EDGE_INTERSECTIONS);
-//}
-//
-//BOOST_AUTO_TEST_CASE_TEMPLATE(segment_sites_test3, T, test_types) {
-// typedef T coordinate_type;
-// voronoi_builder<coordinate_type> test_builder;
-// voronoi_output_clipped<coordinate_type> test_output;
-// std::vector< point_2d<T> > point_vec;
-// std::vector< typename voronoi_builder<coordinate_type>::Segment2D > segm_vec;
-// point_2d<T> point1 = make_point_2d<T>(4, 0);
-// point_2d<T> point2 = make_point_2d<T>(0, 4);
-// point_2d<T> point3 = make_point_2d<T>(3, 3);
-// point_2d<T> point4 = make_point_2d<T>(1, 1);
-// segm_vec.push_back(std::make_pair< point_2d<T>, point_2d<T> >(point1, point2));
-// point_vec.push_back(point3);
-// point_vec.push_back(point4);
-// test_builder.init(point_vec, segm_vec);
-// test_builder.run_sweepline();
-// test_builder.clip(test_output);
-// BOOST_CHECK_EQUAL(test_output.num_cell_records, 5);
-// BOOST_CHECK_EQUAL(test_output.num_vertex_records, 4);
-// BOOST_CHECK_EQUAL(test_output.num_edge_records, 8);
-// VERIFY_VORONOI_OUTPUT(test_output, NO_HALF_EDGE_INTERSECTIONS);
-//}
-//
-//BOOST_AUTO_TEST_CASE_TEMPLATE(segment_sites_test4, T, test_types) {
-// typedef T coordinate_type;
-// voronoi_builder<coordinate_type> test_builder;
-// voronoi_output_clipped<coordinate_type> test_output;
-// std::vector< point_2d<T> > point_vec;
-// std::vector< typename voronoi_builder<coordinate_type>::Segment2D > segm_vec;
-// point_2d<T> point1 = make_point_2d<T>(4, 0);
-// point_2d<T> point2 = make_point_2d<T>(0, 4);
-// point_2d<T> point3 = make_point_2d<T>(3, 2);
-// point_2d<T> point4 = make_point_2d<T>(2, 3);
-// segm_vec.push_back(std::make_pair< point_2d<T>, point_2d<T> >(point1, point2));
-// point_vec.push_back(point3);
-// point_vec.push_back(point4);
-// test_builder.init(point_vec, segm_vec);
-// test_builder.run_sweepline();
-// test_builder.clip(test_output);
-// BOOST_CHECK_EQUAL(test_output.num_cell_records, 5);
-// BOOST_CHECK_EQUAL(test_output.num_vertex_records, 3);
-// BOOST_CHECK_EQUAL(test_output.num_edge_records, 7);
-// VERIFY_VORONOI_OUTPUT(test_output, NO_HALF_EDGE_INTERSECTIONS);
-//}
-//
-//BOOST_AUTO_TEST_CASE_TEMPLATE(segment_site_test5, T, test_types) {
-// typedef T coordinate_type;
-// voronoi_builder<coordinate_type> test_builder;
-// voronoi_output_clipped<coordinate_type> test_output;
-// std::vector< point_2d<T> > point_vec;
-// std::vector< typename voronoi_builder<coordinate_type>::Segment2D > segm_vec;
-// point_2d<T> point1 = make_point_2d<T>(0, 0);
-// point_2d<T> point2 = make_point_2d<T>(0, 8);
-// point_2d<T> point3 = make_point_2d<T>(-2, -2);
-// point_2d<T> point4 = make_point_2d<T>(-2, 4);
-// point_2d<T> point5 = make_point_2d<T>(-2, 10);
-// segm_vec.push_back(std::make_pair< point_2d<T>, point_2d<T> >(point1, point2));
-// point_vec.push_back(point3);
-// point_vec.push_back(point4);
-// point_vec.push_back(point5);
-// test_builder.init(point_vec, segm_vec);
-// test_builder.run_sweepline();
-// test_builder.clip(test_output);
-// BOOST_CHECK_EQUAL(test_output.num_cell_records, 6);
-// BOOST_CHECK_EQUAL(test_output.num_vertex_records, 4);
-// BOOST_CHECK_EQUAL(test_output.num_edge_records, 9);
-// VERIFY_VORONOI_OUTPUT(test_output, NO_HALF_EDGE_INTERSECTIONS);
-//}
-//
-//BOOST_AUTO_TEST_CASE_TEMPLATE(segment_site_test6, T, test_types) {
-// typedef T coordinate_type;
-// voronoi_builder<coordinate_type> test_builder;
-// voronoi_output_clipped<coordinate_type> test_output;
-// std::vector< point_2d<T> > point_vec;
-// std::vector< typename voronoi_builder<coordinate_type>::Segment2D > segm_vec;
-// point_2d<T> point1 = make_point_2d<T>(-1, 1);
-// point_2d<T> point2 = make_point_2d<T>(1, 0);
-// point_2d<T> point3 = make_point_2d<T>(1, 2);
-// segm_vec.push_back(std::make_pair< point_2d<T>, point_2d<T> >(point2, point3));
-// point_vec.push_back(point1);
-// test_builder.init(point_vec, segm_vec);
-// test_builder.run_sweepline();
-// test_builder.clip(test_output);
-// BOOST_CHECK_EQUAL(test_output.num_cell_records, 4);
-// BOOST_CHECK_EQUAL(test_output.num_vertex_records, 2);
-// BOOST_CHECK_EQUAL(test_output.num_edge_records, 5);
-// VERIFY_VORONOI_OUTPUT(test_output, NO_HALF_EDGE_INTERSECTIONS);
-//}
-//
-//BOOST_AUTO_TEST_CASE_TEMPLATE(segment_site_test7, T, test_types) {
-// typedef T coordinate_type;
-// voronoi_builder<coordinate_type> test_builder;
-// voronoi_output_clipped<coordinate_type> test_output;
-// std::vector< point_2d<T> > point_vec;
-// std::vector< typename voronoi_builder<coordinate_type>::Segment2D > segm_vec;
-// point_2d<T> point1 = make_point_2d<T>(0, 0);
-// point_2d<T> point2 = make_point_2d<T>(4, 0);
-// point_2d<T> point3 = make_point_2d<T>(0, 4);
-// point_2d<T> point4 = make_point_2d<T>(4, 4);
-// segm_vec.push_back(std::make_pair(point1, point2));
-// segm_vec.push_back(std::make_pair(point2, point3));
-// segm_vec.push_back(std::make_pair(point3, point4));
-// test_builder.init(segm_vec);
-// test_builder.run_sweepline();
-// test_builder.clip(test_output);
-// BOOST_CHECK_EQUAL(test_output.num_cell_records, 7);
-// BOOST_CHECK_EQUAL(test_output.num_vertex_records, 6);
-// BOOST_CHECK_EQUAL(test_output.num_edge_records, 12);
-// VERIFY_VORONOI_OUTPUT(test_output, NO_HALF_EDGE_INTERSECTIONS);
-//
-//}
-//
-//BOOST_AUTO_TEST_CASE_TEMPLATE(segment_site_test8, T, test_types) {
-// typedef T coordinate_type;
-// voronoi_builder<coordinate_type> test_builder;
-// voronoi_output_clipped<coordinate_type> test_output;
-// std::vector< point_2d<T> > point_vec;
-// std::vector< typename voronoi_builder<coordinate_type>::Segment2D > segm_vec;
-// point_2d<T> point1 = make_point_2d<T>(0, 0);
-// point_2d<T> point2 = make_point_2d<T>(4, 0);
-// point_2d<T> point3 = make_point_2d<T>(4, 4);
-// point_2d<T> point4 = make_point_2d<T>(0, 4);
-// segm_vec.push_back(std::make_pair(point1, point2));
-// segm_vec.push_back(std::make_pair(point2, point3));
-// segm_vec.push_back(std::make_pair(point3, point4));
-// segm_vec.push_back(std::make_pair(point4, point1));
-// test_builder.init(segm_vec);
-// test_builder.run_sweepline();
-// test_builder.clip(test_output);
-// BOOST_CHECK_EQUAL(test_output.num_cell_records, 8);
-// BOOST_CHECK_EQUAL(test_output.num_vertex_records, 5);
-// BOOST_CHECK_EQUAL(test_output.num_edge_records, 12);
-// VERIFY_VORONOI_OUTPUT(test_output, NO_HALF_EDGE_INTERSECTIONS);
-//}
+
+BOOST_AUTO_TEST_CASE_TEMPLATE(segment_sites_test1, T, test_types) {
+ typedef T coordinate_type;
+ voronoi_output<coordinate_type> test_output;
+ std::vector< std::pair< point_2d<T>, point_2d<T> > > segm_vec;
+ point_2d<T> point1 = make_point_2d<T>(0, 0);
+ point_2d<T> point2 = make_point_2d<T>(1, 1);
+ segm_vec.push_back(std::make_pair< point_2d<T>, point_2d<T> >(point1, point2));
+ build_voronoi(segm_vec, test_output);
+ BOOST_CHECK_EQUAL(test_output.num_cell_records(), 3);
+ BOOST_CHECK_EQUAL(test_output.num_vertex_records(), 0);
+ BOOST_CHECK_EQUAL(test_output.num_edge_records(), 2);
+ VERIFY_VORONOI_OUTPUT(test_output, NO_HALF_EDGE_INTERSECTIONS);
+}
+
+BOOST_AUTO_TEST_CASE_TEMPLATE(segment_sites_test2, T, test_types) {
+ typedef T coordinate_type;
+ voronoi_output<coordinate_type> test_output;
+ std::vector< point_2d<T> > point_vec;
+ std::vector< std::pair< point_2d<T>, point_2d<T> > > segm_vec;
+ point_2d<T> point1 = make_point_2d<T>(0, 0);
+ point_2d<T> point2 = make_point_2d<T>(4, 4);
+ point_2d<T> point3 = make_point_2d<T>(3, 1);
+ point_2d<T> point4 = make_point_2d<T>(1, 3);
+ segm_vec.push_back(std::make_pair< point_2d<T>, point_2d<T> >(point1, point2));
+ point_vec.push_back(point3);
+ point_vec.push_back(point4);
+ build_voronoi(point_vec, segm_vec, test_output);
+ BOOST_CHECK_EQUAL(test_output.num_cell_records(), 5);
+ BOOST_CHECK_EQUAL(test_output.num_vertex_records(), 4);
+ BOOST_CHECK_EQUAL(test_output.num_edge_records(), 8);
+ VERIFY_VORONOI_OUTPUT(test_output, NO_HALF_EDGE_INTERSECTIONS);
+}
+
+BOOST_AUTO_TEST_CASE_TEMPLATE(segment_sites_test3, T, test_types) {
+ typedef T coordinate_type;
+ voronoi_output<coordinate_type> test_output;
+ std::vector< point_2d<T> > point_vec;
+ std::vector< std::pair< point_2d<T>, point_2d<T> > > segm_vec;
+ point_2d<T> point1 = make_point_2d<T>(4, 0);
+ point_2d<T> point2 = make_point_2d<T>(0, 4);
+ point_2d<T> point3 = make_point_2d<T>(3, 3);
+ point_2d<T> point4 = make_point_2d<T>(1, 1);
+ segm_vec.push_back(std::make_pair< point_2d<T>, point_2d<T> >(point1, point2));
+ point_vec.push_back(point3);
+ point_vec.push_back(point4);
+ build_voronoi(point_vec, segm_vec, test_output);
+ BOOST_CHECK_EQUAL(test_output.num_cell_records(), 5);
+ BOOST_CHECK_EQUAL(test_output.num_vertex_records(), 4);
+ BOOST_CHECK_EQUAL(test_output.num_edge_records(), 8);
+ VERIFY_VORONOI_OUTPUT(test_output, NO_HALF_EDGE_INTERSECTIONS);
+}
+
+BOOST_AUTO_TEST_CASE_TEMPLATE(segment_sites_test4, T, test_types) {
+ typedef T coordinate_type;
+ voronoi_output<coordinate_type> test_output;
+ std::vector< point_2d<T> > point_vec;
+ std::vector< std::pair< point_2d<T>, point_2d<T> > > segm_vec;
+ point_2d<T> point1 = make_point_2d<T>(4, 0);
+ point_2d<T> point2 = make_point_2d<T>(0, 4);
+ point_2d<T> point3 = make_point_2d<T>(3, 2);
+ point_2d<T> point4 = make_point_2d<T>(2, 3);
+ segm_vec.push_back(std::make_pair< point_2d<T>, point_2d<T> >(point1, point2));
+ point_vec.push_back(point3);
+ point_vec.push_back(point4);
+ build_voronoi(point_vec, segm_vec, test_output);
+ BOOST_CHECK_EQUAL(test_output.num_cell_records(), 5);
+ BOOST_CHECK_EQUAL(test_output.num_vertex_records(), 3);
+ BOOST_CHECK_EQUAL(test_output.num_edge_records(), 7);
+ VERIFY_VORONOI_OUTPUT(test_output, NO_HALF_EDGE_INTERSECTIONS);
+}
+
+BOOST_AUTO_TEST_CASE_TEMPLATE(segment_site_test5, T, test_types) {
+ typedef T coordinate_type;
+ voronoi_output<coordinate_type> test_output;
+ std::vector< point_2d<T> > point_vec;
+ std::vector< std::pair< point_2d<T>, point_2d<T> > > segm_vec;
+ point_2d<T> point1 = make_point_2d<T>(0, 0);
+ point_2d<T> point2 = make_point_2d<T>(0, 8);
+ point_2d<T> point3 = make_point_2d<T>(-2, -2);
+ point_2d<T> point4 = make_point_2d<T>(-2, 4);
+ point_2d<T> point5 = make_point_2d<T>(-2, 10);
+ segm_vec.push_back(std::make_pair< point_2d<T>, point_2d<T> >(point1, point2));
+ point_vec.push_back(point3);
+ point_vec.push_back(point4);
+ point_vec.push_back(point5);
+ build_voronoi(point_vec, segm_vec, test_output);
+ BOOST_CHECK_EQUAL(test_output.num_cell_records(), 6);
+ BOOST_CHECK_EQUAL(test_output.num_vertex_records(), 4);
+ BOOST_CHECK_EQUAL(test_output.num_edge_records(), 9);
+ VERIFY_VORONOI_OUTPUT(test_output, NO_HALF_EDGE_INTERSECTIONS);
+}
+
+BOOST_AUTO_TEST_CASE_TEMPLATE(segment_site_test6, T, test_types) {
+ typedef T coordinate_type;
+ voronoi_output<coordinate_type> test_output;
+ std::vector< point_2d<T> > point_vec;
+ std::vector< std::pair< point_2d<T>, point_2d<T> > > segm_vec;
+ point_2d<T> point1 = make_point_2d<T>(-1, 1);
+ point_2d<T> point2 = make_point_2d<T>(1, 0);
+ point_2d<T> point3 = make_point_2d<T>(1, 2);
+ segm_vec.push_back(std::make_pair< point_2d<T>, point_2d<T> >(point2, point3));
+ point_vec.push_back(point1);
+ build_voronoi(point_vec, segm_vec, test_output);
+ BOOST_CHECK_EQUAL(test_output.num_cell_records(), 4);
+ BOOST_CHECK_EQUAL(test_output.num_vertex_records(), 2);
+ BOOST_CHECK_EQUAL(test_output.num_edge_records(), 5);
+ VERIFY_VORONOI_OUTPUT(test_output, NO_HALF_EDGE_INTERSECTIONS);
+}
+
+BOOST_AUTO_TEST_CASE_TEMPLATE(segment_site_test7, T, test_types) {
+ typedef T coordinate_type;
+ voronoi_output<coordinate_type> test_output;
+ std::vector< std::pair< point_2d<T>, point_2d<T> > > segm_vec;
+ point_2d<T> point1 = make_point_2d<T>(0, 0);
+ point_2d<T> point2 = make_point_2d<T>(4, 0);
+ point_2d<T> point3 = make_point_2d<T>(0, 4);
+ point_2d<T> point4 = make_point_2d<T>(4, 4);
+ segm_vec.push_back(std::make_pair(point1, point2));
+ segm_vec.push_back(std::make_pair(point2, point3));
+ segm_vec.push_back(std::make_pair(point3, point4));
+ build_voronoi(segm_vec, test_output);
+ BOOST_CHECK_EQUAL(test_output.num_cell_records(), 7);
+ BOOST_CHECK_EQUAL(test_output.num_vertex_records(), 6);
+ BOOST_CHECK_EQUAL(test_output.num_edge_records(), 12);
+ VERIFY_VORONOI_OUTPUT(test_output, NO_HALF_EDGE_INTERSECTIONS);
+
+}
+
+BOOST_AUTO_TEST_CASE_TEMPLATE(segment_site_test8, T, test_types) {
+ typedef T coordinate_type;
+ voronoi_output<coordinate_type> test_output;
+ std::vector< std::pair< point_2d<T>, point_2d<T> > > segm_vec;
+ point_2d<T> point1 = make_point_2d<T>(0, 0);
+ point_2d<T> point2 = make_point_2d<T>(4, 0);
+ point_2d<T> point3 = make_point_2d<T>(4, 4);
+ point_2d<T> point4 = make_point_2d<T>(0, 4);
+ segm_vec.push_back(std::make_pair(point1, point2));
+ segm_vec.push_back(std::make_pair(point2, point3));
+ segm_vec.push_back(std::make_pair(point3, point4));
+ segm_vec.push_back(std::make_pair(point4, point1));
+ build_voronoi(segm_vec, test_output);
+ BOOST_CHECK_EQUAL(test_output.num_cell_records(), 8);
+ BOOST_CHECK_EQUAL(test_output.num_vertex_records(), 5);
+ BOOST_CHECK_EQUAL(test_output.num_edge_records(), 12);
+ VERIFY_VORONOI_OUTPUT(test_output, NO_HALF_EDGE_INTERSECTIONS);
+}
#ifdef NDEBUG
BOOST_AUTO_TEST_CASE_TEMPLATE(segment_grid_test, T, test_types) {
@@ -685,11 +642,11 @@
srand(static_cast<unsigned int>(time(NULL)));
voronoi_output<T> test_output_small, test_output_large;
std::vector< std::pair< point_2d<T>, point_2d<T> > > segm_vec;
- int num_segments[] = {10, 100, 1000, 10000, 100000};
- int num_runs[] = {10000, 1000, 100, 10, 1};
- int mod_koef1[] = {10, 100, 100, 1000, 4000};
- int mod_koef2[] = {10, 100, 100, 100, 100};
- int max_value[] = {10, 100, 100, 550, 2050};
+ int num_segments[] = {10, 100, 1000, 10000};
+ int num_runs[] = {1000, 100, 10, 1};
+ int mod_koef1[] = {100, 1000, 10000, 100000};
+ int mod_koef2[] = {100, 200, 300, 400};
+ int max_value[] = {100, 600, 5150, 50200};
int array_length = sizeof(num_segments) / sizeof(int);
for (int k = 0; k < array_length; k++) {
int koef = std::numeric_limits<int>::max() / max_value[k];
@@ -718,7 +675,6 @@
}
build_voronoi(segm_vec, test_output_large);
VERIFY_VORONOI_OUTPUT(test_output_small, NO_HALF_EDGE_INTERSECTIONS);
- VERIFY_VORONOI_OUTPUT(test_output_large, NO_HALF_EDGE_INTERSECTIONS);
BOOST_CHECK_EQUAL(test_output_small.num_cell_records(),
test_output_large.num_cell_records());
BOOST_CHECK_EQUAL(test_output_small.num_vertex_records(),