|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r65957 - in sandbox/SOC/2010/sweepline: boost/sweepline boost/sweepline/detail libs/sweepline/example libs/sweepline/example/output_data libs/sweepline/test libs/sweepline/test/voronoi_segment
From: sydorchuk.andriy_at_[hidden]
Date: 2010-10-14 11:25:23
Author: asydorchuk
Date: 2010-10-14 11:25:19 EDT (Thu, 14 Oct 2010)
New Revision: 65957
URL: http://svn.boost.org/trac/boost/changeset/65957
Log:
Finished output refactoring.
Finished beta version of segment voronoi.
Made helper class for voronoi clipping.
Added new examples.
Added:
sandbox/SOC/2010/sweepline/libs/sweepline/example/output_data/example_021.png (contents, props changed)
sandbox/SOC/2010/sweepline/libs/sweepline/example/output_data/example_022.png (contents, props changed)
sandbox/SOC/2010/sweepline/libs/sweepline/example/output_data/example_023.png (contents, props changed)
sandbox/SOC/2010/sweepline/libs/sweepline/example/output_data/example_024.png (contents, props changed)
sandbox/SOC/2010/sweepline/libs/sweepline/example/output_data/example_025.png (contents, props changed)
sandbox/SOC/2010/sweepline/libs/sweepline/example/output_data/example_026.png (contents, props changed)
sandbox/SOC/2010/sweepline/libs/sweepline/example/output_data/example_027.png (contents, props changed)
sandbox/SOC/2010/sweepline/libs/sweepline/example/output_data/example_028.png (contents, props changed)
sandbox/SOC/2010/sweepline/libs/sweepline/example/output_data/example_029.png (contents, props changed)
sandbox/SOC/2010/sweepline/libs/sweepline/example/output_data/example_030.png (contents, props changed)
Text files modified:
sandbox/SOC/2010/sweepline/boost/sweepline/detail/voronoi_segment_formation.hpp | 702 +++++++++++++++++----------------------
sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_segment_builder.hpp | 7
sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_segment_output.hpp | 384 ++++++++++++++-------
sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_segment_sweepline.hpp | 1
sandbox/SOC/2010/sweepline/libs/sweepline/example/voronoi_visualizer.cpp | 128 ++++--
sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_output_verification.hpp | 56 +-
sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_segment/segment_predicates_test.cpp | 32 +
sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_segment/segment_voronoi_builder_test.cpp | 277 ++++++++-------
sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_segment/segment_voronoi_clipping_test.cpp | 105 ++---
9 files changed, 882 insertions(+), 810 deletions(-)
Modified: sandbox/SOC/2010/sweepline/boost/sweepline/detail/voronoi_segment_formation.hpp
==============================================================================
--- sandbox/SOC/2010/sweepline/boost/sweepline/detail/voronoi_segment_formation.hpp (original)
+++ sandbox/SOC/2010/sweepline/boost/sweepline/detail/voronoi_segment_formation.hpp 2010-10-14 11:25:19 EDT (Thu, 14 Oct 2010)
@@ -11,17 +11,19 @@
#define BOOST_SWEEPLINE_VORONOI_SEGMENT_FORMATION
#define INT_PREDICATE_COMPUTE_DIFFERENCE(a, b, res, sign) \
- if (a >= b) { res = static_cast<ull>(a - b); sign = true; } \
- else { res = static_cast<ull>(b - a); sign = false; }
+ if (a >= b) { res = static_cast<unsigned long long>(a - b); sign = true; } \
+ else { res = static_cast<unsigned long long>(b - a); sign = false; }
#define INT_PREDICATE_CONVERT_65_BIT(a, res, sign) \
- if (a >= 0) { res = static_cast<ull>(a); sign = true; } \
- else { res = static_cast<ull>(-a); sign = false; }
+ if (a >= 0) { res = static_cast<unsigned long long>(a); sign = true; } \
+ else { res = static_cast<unsigned long long>(-a); sign = false; }
#define INT_PREDICATE_AVOID_CANCELLATION(val, first_expr, second_expr) \
if ((val) >= 0) first_expr += (val); \
else second_expr -= (val);
+#define INV_LOG_2 1.4426950408889634
+
namespace boost {
namespace sweepline {
namespace detail {
@@ -47,7 +49,7 @@
// Site event type.
// Occurs when sweepline sweeps over one of the initial sites.
- // Contains index of a site below the other sorted sites.
+ // Contains index of a site among the other sorted sites.
template <typename T>
struct site_event {
public:
@@ -541,6 +543,76 @@
}
}
+ template<typename T>
+ double get_point_projection(point_2d<T> point, point_2d<T> segment_start,
+ point_2d<T> segment_end) {
+ double segment_vec_x = static_cast<double>(segment_end.x()) -
+ static_cast<double>(segment_start.x());
+ double segment_vec_y = static_cast<double>(segment_end.y()) -
+ static_cast<double>(segment_start.y());
+ double point_vec_x = static_cast<double>(point.x()) -
+ static_cast<double>(segment_start.x());
+ double point_vec_y = static_cast<double>(point.y()) -
+ static_cast<double>(segment_start.y());
+ double sqr_segment_length = segment_vec_x * segment_vec_x +
+ segment_vec_y * segment_vec_y;
+ double vec_dot = segment_vec_x * point_vec_x +
+ segment_vec_y * point_vec_y;
+ return vec_dot / sqr_segment_length;
+ }
+
+ template<typename T>
+ int get_intermediate_points_count(point_2d<T> point1, point_2d<T> point2) {
+ double vec_x = static_cast<double>(point1.x()) - static_cast<double>(point2.x());
+ double vec_y = static_cast<double>(point1.y()) - static_cast<double>(point2.y());
+ double sqr_len = vec_x * vec_x + vec_y * vec_y;
+ return static_cast<int>(log(sqr_len) * INV_LOG_2 * 2 + 1E-6);
+ }
+
+ template<typename T>
+ void fill_intermediate_points(point_2d<T> point_site, point_2d<T> segment_site_start,
+ point_2d<T> segment_site_end, std::vector< point_2d<T> > &intermediate_points) {
+ int num_inter_points = get_intermediate_points_count(
+ intermediate_points[0], intermediate_points[1]);
+ if (num_inter_points <= 0 ||
+ orientation_test(point_site, segment_site_start, segment_site_end) == COLINEAR) {
+ return;
+ }
+ intermediate_points.reserve(2 + num_inter_points);
+ double segm_vec_x = static_cast<double>(segment_site_end.x()) -
+ static_cast<double>(segment_site_start.x());
+ double segm_vec_y = static_cast<double>(segment_site_end.y()) -
+ static_cast<double>(segment_site_start.y());
+ double sqr_segment_length = segm_vec_x * segm_vec_x + segm_vec_y * segm_vec_y;
+ double projection_start =
+ get_point_projection(intermediate_points[0], segment_site_start, segment_site_end);
+ double projection_end =
+ get_point_projection(intermediate_points[1], segment_site_start, segment_site_end);
+ double step = (projection_end - projection_start) *
+ sqr_segment_length / (num_inter_points + 1);
+ double point_vec_x = static_cast<double>(point_site.x()) -
+ static_cast<double>(segment_site_start.x());
+ double point_vec_y = static_cast<double>(point_site.y()) -
+ static_cast<double>(segment_site_start.y());
+ double point_rot_x = segm_vec_x * point_vec_x + segm_vec_y * point_vec_y;
+ double point_rot_y = segm_vec_x * point_vec_y - segm_vec_y * point_vec_x;
+ double projection_cur_x = projection_start * sqr_segment_length + step;
+ point_2d<T> last_point = intermediate_points.back();
+ intermediate_points.pop_back();
+ for (int i = 0; i < num_inter_points; i++, projection_cur_x += step) {
+ double inter_rot_x = projection_cur_x;
+ double inter_rot_y =
+ ((inter_rot_x - point_rot_x) * (inter_rot_x - point_rot_x) +
+ point_rot_y * point_rot_y) / (2.0 * point_rot_y);
+ double new_point_x = (segm_vec_x * inter_rot_x - segm_vec_y * inter_rot_y) /
+ sqr_segment_length + static_cast<double>(segment_site_start.x());
+ double new_point_y = (segm_vec_x * inter_rot_y + segm_vec_y * inter_rot_x) /
+ sqr_segment_length + static_cast<double>(segment_site_start.y());
+ intermediate_points.push_back(make_point_2d(new_point_x, new_point_y));
+ }
+ intermediate_points.push_back(last_point);
+ }
+
enum kPredicateResult {
LESS = -1,
UNDEFINED = 0,
@@ -829,7 +901,7 @@
bool less_predicate(site_event<T> left_site, site_event<T> right_site, point_2d<T> new_point) {
if (left_site.get_site_index() == right_site.get_site_index()) {
return orientation_test(left_site.get_point0(), left_site.get_point1(),
- new_point) == RIGHT_ORIENTATION;
+ new_point) == LEFT_ORIENTATION;
}
const point_2d<T> segment1_start = left_site.get_point1();
@@ -1254,17 +1326,17 @@
};
template <typename T>
- struct half_edge;
+ struct voronoi_edge;
// Represents edge data sturcture (bisector segment), which is
// associated with beach line node key in the binary search tree.
template <typename T>
struct beach_line_node_data {
- half_edge<T> *edge;
+ voronoi_edge<T> *edge;
typename circle_events_queue<T>::circle_event_type_it circle_event_it;
bool contains_circle_event;
- explicit beach_line_node_data(half_edge<T> *new_edge) :
+ explicit beach_line_node_data(voronoi_edge<T> *new_edge) :
edge(new_edge),
contains_circle_event(false) {}
@@ -1325,25 +1397,37 @@
///////////////////////////////////////////////////////////////////////////
// VORONOI OUTPUT /////////////////////////////////////////////////////////
- ///////////////////////////////////////////////////////////////////////////
- // 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 T>
- struct voronoi_record {
- 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<coordinate_type> >::iterator voronoi_record_it;
-
- voronoi_record(const Point2D &point, half_edge<coordinate_type>* edge) :
- incident_edge(edge),
- voronoi_point(point),
- num_incident_edges(0) {}
- };
+ ///////////////////////////////////////////////////////////////////////////
+ template <typename T>
+ struct voronoi_cell {
+ typedef T coordinate_type;
+ typedef site_event<T> site_event_type;
+
+ voronoi_edge<coordinate_type> *incident_edge;
+ site_event_type site;
+ int num_incident_edges;
+
+ voronoi_cell(const site_event_type &new_site, voronoi_edge<coordinate_type>* edge) :
+ incident_edge(edge),
+ site(new_site),
+ num_incident_edges(0) {}
+ };
+
+ template <typename T>
+ struct voronoi_vertex {
+ typedef T coordinate_type;
+ typedef point_2d<T> Point2D;
+
+ voronoi_edge<coordinate_type> *incident_edge;
+ Point2D vertex;
+ int num_incident_edges;
+ typename std::list< voronoi_vertex<coordinate_type> >::iterator voronoi_record_it;
+
+ voronoi_vertex(const Point2D &point, voronoi_edge<coordinate_type>* edge) :
+ incident_edge(edge),
+ vertex(point),
+ num_incident_edges(0) {}
+ };
// Half-edge data structure. Represents voronoi edge.
// Contains: 1) pointer to cell records;
@@ -1354,24 +1438,25 @@
// 5) pointer to twin half-edge;
// 6) pointer to clipped edge during clipping.
template <typename T>
- struct half_edge {
+ struct voronoi_edge {
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;
- voronoi_record_type *end_point;
- half_edge_type *prev;
- half_edge_type *next;
- half_edge_type *rot_prev;
- half_edge_type *rot_next;
- half_edge_type *twin;
- half_edge_clipped_type *clipped_edge;
+ typedef voronoi_cell<coordinate_type> voronoi_cell_type;
+ typedef voronoi_vertex<coordinate_type> voronoi_vertex_type;
+ typedef voronoi_edge<coordinate_type> voronoi_edge_type;
+ typedef voronoi_edge_clipped<coordinate_type> voronoi_edge_clipped_type;
+
+ voronoi_cell_type *cell;
+ voronoi_vertex_type *start_point;
+ voronoi_vertex_type *end_point;
+ voronoi_edge_type *prev;
+ voronoi_edge_type *next;
+ voronoi_edge_type *rot_prev;
+ voronoi_edge_type *rot_next;
+ voronoi_edge_type *twin;
+ voronoi_edge_clipped_type *clipped_edge;
- half_edge() :
+ voronoi_edge() :
cell(NULL),
start_point(NULL),
end_point(NULL),
@@ -1389,29 +1474,29 @@
template <typename T>
class voronoi_output {
public:
-
typedef T coordinate_type;
typedef point_2d<T> Point2D;
- typedef typename detail::site_event<coordinate_type> site_event_type;
- typedef typename detail::circle_event<coordinate_type> circle_event_type;
+ typedef site_event<coordinate_type> site_event_type;
+ typedef 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 typename voronoi_records_type::iterator voronoi_iterator_type;
- typedef typename voronoi_records_type::const_iterator voronoi_const_iterator_type;
+ typedef voronoi_cell<coordinate_type> voronoi_cell_type;
+ typedef std::list<voronoi_cell_type> voronoi_cells_type;
+ typedef typename voronoi_cells_type::iterator voronoi_cell_iterator_type;
+ typedef typename voronoi_cells_type::const_iterator voronoi_cell_const_iterator_type;
+
+ typedef voronoi_vertex<coordinate_type> voronoi_vertex_type;
+ typedef std::list<voronoi_vertex_type> voronoi_vertices_type;
+ typedef typename voronoi_vertices_type::iterator voronoi_vertex_iterator_type;
+ typedef typename voronoi_vertices_type::const_iterator voronoi_vertex_const_iterator_type;
- typedef half_edge<coordinate_type> edge_type;
- typedef half_edge_clipped<coordinate_type> clipped_edge_type;
+ typedef voronoi_edge<coordinate_type> edge_type;
+ typedef voronoi_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,
- LINE = 2,
- };
+ typedef voronoi_cell_clipped<coordinate_type> clipped_voronoi_cell_type;
+ typedef voronoi_vertex_clipped<coordinate_type> clipped_voronoi_vertex_type;
+ typedef voronoi_edge_clipped<coordinate_type> clipped_voronoi_edge_type;
voronoi_output() {
num_cell_records_ = 0;
@@ -1446,7 +1531,7 @@
voronoi_rect_ = BRect<coordinate_type>(site.get_point0(), site.get_point0());
// Update cell records.
- cell_records_.push_back(voronoi_record_type(site.get_point0(), NULL));
+ cell_records_.push_back(voronoi_cell_type(site, NULL));
}
// Inserts new half-edge into the output data structure during site
@@ -1473,19 +1558,22 @@
// Add initial cell during first edge insertion.
if (cell_records_.empty()) {
cell_iterators_.push_back(cell_records_.insert(
- cell_records_.end(), voronoi_record_type(site1.get_point0(), &edge1)));
+ cell_records_.end(), voronoi_cell_type(site1, &edge1)));
cell_records_.back().num_incident_edges++;
num_cell_records_++;
voronoi_rect_ = BRect<coordinate_type>(site1.get_point0(), site1.get_point0());
}
// Update bounding rectangle.
- voronoi_rect_.update(site2.get_point0());
+ voronoi_rect_.update(site2.get_point0());
+ if (site2.is_segment()) {
+ voronoi_rect_.update(site2.get_point1());
+ }
// Second site represents new site during site event processing.
// Add new cell to the cell records vector.
cell_iterators_.push_back(cell_records_.insert(
- cell_records_.end(), voronoi_record_type(site2.get_point0(), &edge2)));
+ cell_records_.end(), voronoi_cell_type(site2, &edge2)));
cell_records_.back().num_incident_edges++;
// Update pointers to cells.
@@ -1513,8 +1601,8 @@
voronoi_rect_.update(circle.get_center());
// Add new voronoi vertex with point at center of the circle.
- vertex_records_.push_back(voronoi_record_type(circle.get_center(), edge12));
- voronoi_record_type &new_vertex = vertex_records_.back();
+ vertex_records_.push_back(voronoi_vertex_type(circle.get_center(), 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--;
@@ -1564,11 +1652,11 @@
return &new_edge1;
}
- const voronoi_records_type &get_cell_records() const {
+ const voronoi_cells_type &get_cell_records() const {
return cell_records_;
}
- const voronoi_records_type &get_voronoi_vertices() const {
+ const voronoi_vertices_type &get_voronoi_vertices() const {
return vertex_records_;
}
@@ -1625,12 +1713,10 @@
// Iterate over all edges and remove degeneracies.
while (edge_it != edges_.end()) {
edge_it1 = edge_it;
- edge_it++;
- edge_it++;
+ std::advance(edge_it, 2);
if (edge_it1->start_point && edge_it1->end_point &&
- edge_it1->start_point->voronoi_point ==
- edge_it1->end_point->voronoi_point) {
+ edge_it1->start_point->vertex == edge_it1->end_point->vertex) {
// Decrease number of cell incident edges.
edge_it1->cell->num_incident_edges--;
edge_it1->twin->cell->num_incident_edges--;
@@ -1653,7 +1739,7 @@
}
// Make some post processing.
- for (voronoi_iterator_type cell_it = cell_records_.begin();
+ 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.
edge_type *cur_edge = cell_it->incident_edge;
@@ -1691,313 +1777,21 @@
coordinate_type offset = x_len;
if (offset < y_len)
offset = y_len;
- offset *= static_cast<coordinate_type>(0.55);
+ offset *= static_cast<coordinate_type>(1.0);
if (offset == static_cast<coordinate_type>(0.0))
offset = 0.5;
BRect<coordinate_type> new_brect(x_mid - offset, y_mid - offset,
- x_mid + offset, y_mid + offset);
+ x_mid + offset, y_mid + offset);
clip(new_brect, clipped_output);
}
- void clip(const BRect<coordinate_type> &brect,
- voronoi_output_clipped<coordinate_type> &clipped_output) {
- if (!brect.is_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++) {
- edge_type *cur_edge = vertex_it->incident_edge;
- const Point2D &cur_vertex_point = vertex_it->voronoi_point;
-
- // Check if bounding rectangle of clipped output contains current voronoi vertex.
- if (brect.contains(cur_vertex_point)) {
- // Add current voronoi vertex to clipped output.
- clipped_voronoi_record_type &new_vertex =
- clipped_output.add_vertex(cur_vertex_point);
- new_vertex.num_incident_edges = vertex_it->num_incident_edges;
- clipped_edge_type *rot_prev_edge = NULL;
-
- // Process all half-edges incident to the current voronoi vertex.
- do {
- // Add new edge to the clipped output.
- clipped_edge_type &new_edge = clipped_output.add_edge();
- new_edge.start_point = &new_vertex;
- cur_edge->clipped_edge = &new_edge;
-
- // Ray edges with no start point don't correspond to any voronoi vertex.
- // That's why ray edges are processed during their twin edge processing.
- if (cur_edge->end_point == NULL) {
- // Add new twin edge.
- clipped_edge_type &new_twin_edge = clipped_output.add_edge();
- cur_edge->twin->clipped_edge = &new_twin_edge;
-
- // Add boundary vertex.
- std::vector<Point2D> intersections;
- const Point2D &site1 = cur_edge->cell->voronoi_point;
- const Point2D &site2 = cur_edge->twin->cell->voronoi_point;
- Point2D direction(site1.y() - site2.y(), site2.x() - site1.x());
- find_intersections(cur_vertex_point, direction, RAY, brect, intersections);
- clipped_voronoi_record_type &boundary_vertex =
- clipped_output.add_boundary_vertex(intersections[0]);
- boundary_vertex.incident_edge = &new_twin_edge;
- boundary_vertex.num_incident_edges = 1;
-
- // Update new twin edge pointers.
- new_twin_edge.start_point = &boundary_vertex;
- new_twin_edge.rot_next = &new_twin_edge;
- new_twin_edge.rot_prev = &new_twin_edge;
- }
-
- // Update twin and end point pointers.
- clipped_edge_type *twin = cur_edge->twin->clipped_edge;
- if (twin != NULL) {
- new_edge.twin = twin;
- twin->twin = &new_edge;
- new_edge.end_point = twin->start_point;
- twin->end_point = new_edge.start_point;
- }
-
- // Update rotation prev/next pointers.
- if (rot_prev_edge != NULL) {
- new_edge.rot_prev = rot_prev_edge;
- rot_prev_edge->rot_next = &new_edge;
- }
-
- rot_prev_edge = &new_edge;
- cur_edge = cur_edge->rot_next;
- } while(cur_edge != vertex_it->incident_edge);
-
- // Update rotation prev/next pointers.
- cur_edge->clipped_edge->rot_prev = rot_prev_edge;
- rot_prev_edge->rot_next = cur_edge->clipped_edge;
- new_vertex.incident_edge = cur_edge->clipped_edge;
- } else {
- do {
- std::vector<Point2D> intersections;
- Point2D direction;
- kEdgeType etype;
- if (cur_edge->end_point != NULL) {
- const Point2D &end_point = cur_edge->end_point->voronoi_point;
- direction = make_point_2d<coordinate_type> (
- end_point.x() - cur_vertex_point.x(),
- end_point.y() - cur_vertex_point.y());
- etype = SEGMENT;
- } else {
- const Point2D &site1 = cur_edge->cell->voronoi_point;
- const Point2D &site2 = cur_edge->twin->cell->voronoi_point;
- direction = make_point_2d<coordinate_type> (
- site1.y() - site2.y(), site2.x() - site1.x());
- etype = RAY;
- }
-
- // Find all intersections of the current
- // edge with bounding box of the clipped output.
- bool corner_intersection = find_intersections(cur_vertex_point, direction,
- etype, brect, intersections);
-
- // Process edge if there are any intersections.
- 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]);
- new_vertex.num_incident_edges = 1;
-
- // Add new edge to the clipped output.
- clipped_edge_type &new_edge = clipped_output.add_edge();
- new_edge.start_point = &new_vertex;
- cur_edge->clipped_edge = &new_edge;
-
- // Process twin ray edge with no start point.
- if (cur_edge->end_point == NULL && intersections.size() == 2) {
- clipped_edge_type &new_twin_edge = clipped_output.add_edge();
- cur_edge->twin->clipped_edge = &new_twin_edge;
-
- clipped_voronoi_record_type &boundary_vertex =
- clipped_output.add_boundary_vertex(intersections[1]);
- boundary_vertex.incident_edge = &new_twin_edge;
- boundary_vertex.num_incident_edges = 1;
-
- new_twin_edge.start_point = &boundary_vertex;
- new_twin_edge.rot_next = &new_twin_edge;
- new_twin_edge.rot_prev = &new_twin_edge;
- }
-
- // Update twin and end point pointers.
- clipped_edge_type *twin = cur_edge->twin->clipped_edge;
- if (twin != NULL) {
- new_edge.twin = twin;
- twin->twin = &new_edge;
- new_edge.end_point = twin->start_point;
- twin->end_point = new_edge.start_point;
- }
-
- // Update rotation prev/next pointers.
- new_edge.rot_next = &new_edge;
- new_edge.rot_prev = &new_edge;
-
- new_vertex.incident_edge = cur_edge->clipped_edge;
- }
- cur_edge = cur_edge->rot_next;
- } while (cur_edge != vertex_it->incident_edge);
- }
- }
- }
-
- // Iterate over all voronoi cells.
- for (voronoi_const_iterator_type cell_it = cell_records_.begin();
- cell_it != cell_records_.end(); cell_it++) {
- // Add new cell to the clipped output.
- clipped_voronoi_record_type &new_cell =
- clipped_output.add_cell(cell_it->voronoi_point);
- edge_type *cur_edge = cell_it->incident_edge;
- clipped_edge_type *prev = NULL;
-
- // Update cell, next/prev pointers.
- do {
- clipped_edge_type *new_edge = cur_edge->clipped_edge;
- if (new_edge) {
- if (prev) {
- new_edge->prev = prev;
- prev->next = new_edge;
- }
- new_edge->cell = &new_cell;
- if (new_cell.incident_edge == NULL)
- new_cell.incident_edge = cur_edge->clipped_edge;
- new_cell.num_incident_edges++;
- prev = new_edge;
- cur_edge->clipped_edge = NULL;
- }
- cur_edge = cur_edge->next;
- } while(cur_edge != cell_it->incident_edge);
-
- if (new_cell.incident_edge == NULL)
- clipped_output.pop_cell();
- else {
- // Update prev/next pointers.
- prev->next = new_cell.incident_edge;
- new_cell.incident_edge->prev = prev;
- }
- }
- }
-
- // Find edge(segment, ray, line) rectangle intersetion points.
- 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);
-
- // Find rectangle center.
- coordinate_type center_x = (brect.x_min + brect.x_max) * half;
- coordinate_type center_y = (brect.y_min + brect.y_max) * half;
-
- // Find rectangle half-diagonal vector.
- coordinate_type len_x = brect.x_max - center_x;
- coordinate_type len_y = brect.y_max - center_y;
-
- // Find distance between origin and center of rectangle.
- coordinate_type diff_x = origin.x() - center_x;
- coordinate_type diff_y = origin.y() - center_y;
-
- // Find direction perpendicular to the current.
- coordinate_type perp_x = direction.y();
- coordinate_type perp_y = -direction.x();
-
- // Compare projections of distances.
- coordinate_type lexpr = magnitude(perp_x * diff_x + perp_y * diff_y);
- coordinate_type rexpr = magnitude(perp_x * len_x) + magnitude(perp_y * len_y);
-
- // Intersection check.
- if (lexpr > rexpr)
- return false;
-
- // Intersection parameters:
- // origin + fT[i] * direction = intersections point, i = 0 .. 1.
- bool fT0_used = false;
- bool fT1_used = false;
- coordinate_type fT0 = static_cast<coordinate_type>(0);
- coordinate_type fT1 = static_cast<coordinate_type>(0);
-
- // Find intersections with lines going through sides of a bounding rectangle.
- clip(+direction.x(), -diff_x - len_x, fT0_used, fT1_used, fT0, fT1);
- clip(-direction.x(), +diff_x - len_x, fT0_used, fT1_used, fT0, fT1);
- clip(+direction.y(), -diff_y - len_y, fT0_used, fT1_used, fT0, fT1);
- clip(-direction.y(), +diff_y - len_y, fT0_used, fT1_used, fT0, fT1);
-
- 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 && 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:
// Simplify degenerate edge.
void simplify_edge(edge_type *edge) {
- voronoi_record_type *vertex1 = edge->start_point;
- voronoi_record_type *vertex2 = edge->end_point;
+ voronoi_vertex_type *vertex1 = edge->start_point;
+ voronoi_vertex_type *vertex2 = edge->end_point;
// Update number of incident edges.
vertex1->num_incident_edges += vertex2->num_incident_edges - 2;
@@ -2040,48 +1834,149 @@
vertex_records_.erase(vertex2->voronoi_record_it);
}
- bool check_extent(coordinate_type extent, kEdgeType etype) const {
- switch (etype) {
- case SEGMENT: return extent >= static_cast<coordinate_type>(0) &&
- extent <= static_cast<coordinate_type>(1);
- case RAY: return extent >= static_cast<coordinate_type>(0);
- case LINE: return true;
+ void clip(const BRect<coordinate_type> &brect,
+ voronoi_output_clipped<coordinate_type> &clipped_output) {
+ if (!brect.is_valid())
+ return;
+ clipped_output.reset();
+ clipped_output.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.cell_records.push_back(
+ clipped_voronoi_cell_type(cell_records_.back().site, NULL));
+ clipped_output.num_cell_records++;
+ 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++;
+ // Add new clipped edges.
+ clipped_edge_type &new_edge = add_clipped_edge(clipped_output);
+ clipped_edge_type &new_twin_edge = add_clipped_edge(clipped_output);
+
+ // 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;
+ }
+ } else {
+ // Iterate over all voronoi vertices.
+ for (voronoi_vertex_const_iterator_type vertex_it = vertex_records_.begin();
+ vertex_it != vertex_records_.end(); vertex_it++) {
+ edge_type *cur_edge = vertex_it->incident_edge;
+ const Point2D &cur_vertex_point = vertex_it->vertex;
+
+ // Add current voronoi vertex to clipped output.
+ clipped_output.vertex_records.push_back(
+ clipped_voronoi_vertex_type(cur_vertex_point, NULL));
+ clipped_output.num_vertex_records++;
+ clipped_voronoi_vertex_type &new_vertex = clipped_output.vertex_records.back();
+ new_vertex.num_incident_edges = vertex_it->num_incident_edges;
+ clipped_edge_type *rot_prev_edge = NULL;
+
+ // Process all half-edges incident to the current voronoi vertex.
+ do {
+ // Add new edge to the clipped output.
+ clipped_edge_type &new_edge = add_clipped_edge(clipped_output);
+ new_edge.start_point = &new_vertex;
+ cur_edge->clipped_edge = &new_edge;
+
+ // Ray edges with no start point don't correspond to any voronoi vertex.
+ // That's why ray edges are processed during their twin edge processing.
+ if (cur_edge->end_point == NULL) {
+ // Add new twin edge.
+ clipped_edge_type &new_twin_edge = add_clipped_edge(clipped_output);
+ cur_edge->twin->clipped_edge = &new_twin_edge;
+ }
+
+ // Update twin and end point pointers.
+ clipped_edge_type *twin = cur_edge->twin->clipped_edge;
+ if (twin != NULL) {
+ new_edge.twin = twin;
+ twin->twin = &new_edge;
+ new_edge.end_point = twin->start_point;
+ twin->end_point = new_edge.start_point;
+ }
+
+ // Update rotation prev/next pointers.
+ if (rot_prev_edge != NULL) {
+ new_edge.rot_prev = rot_prev_edge;
+ rot_prev_edge->rot_next = &new_edge;
+ }
+
+ rot_prev_edge = &new_edge;
+ cur_edge = cur_edge->rot_next;
+ } while(cur_edge != vertex_it->incident_edge);
+
+ // Update rotation prev/next pointers.
+ cur_edge->clipped_edge->rot_prev = rot_prev_edge;
+ rot_prev_edge->rot_next = cur_edge->clipped_edge;
+ new_vertex.incident_edge = cur_edge->clipped_edge;
+ }
}
- return true;
- }
- coordinate_type magnitude(coordinate_type value) const {
- if (value >= static_cast<coordinate_type>(0))
- return value;
- return -value;
- }
+ // Iterate over all voronoi cells.
+ for (voronoi_cell_const_iterator_type cell_it = cell_records_.begin();
+ cell_it != cell_records_.end(); cell_it++) {
+ // Add new cell to the clipped output.
+ clipped_output.cell_records.push_back(
+ clipped_voronoi_cell_type(cell_it->site, NULL));
+ clipped_output.num_cell_records++;
+ clipped_voronoi_cell_type &new_cell = clipped_output.cell_records.back();
+ edge_type *cur_edge = cell_it->incident_edge;
+ clipped_edge_type *prev = NULL;
- bool clip(coordinate_type denom, coordinate_type numer, bool &fT0_used, bool &fT1_used,
- coordinate_type &fT0, coordinate_type &fT1) const {
- if (denom > static_cast<coordinate_type>(0)) {
- if (fT1_used && numer > denom * fT1)
- return false;
- if (!fT0_used || numer > denom * fT0) {
- fT0_used = true;
- fT0 = numer / denom;
- }
- return true;
- } else if (denom < static_cast<coordinate_type>(0)) {
- if (fT0_used && numer > denom * fT0)
- return false;
- if (!fT1_used || numer > denom * fT1) {
- fT1_used = true;
- fT1 = numer / denom;
+ // Update cell, next/prev pointers.
+ do {
+ clipped_edge_type *new_edge = cur_edge->clipped_edge;
+ if (new_edge) {
+ if (prev) {
+ new_edge->prev = prev;
+ prev->next = new_edge;
+ }
+ new_edge->cell = &new_cell;
+ if (new_cell.incident_edge == NULL)
+ new_cell.incident_edge = cur_edge->clipped_edge;
+ new_cell.num_incident_edges++;
+ prev = new_edge;
+ cur_edge->clipped_edge = NULL;
+ }
+ cur_edge = cur_edge->next;
+ } while(cur_edge != cell_it->incident_edge);
+
+ if (new_cell.incident_edge == NULL) {
+ clipped_output.cell_records.pop_back();
+ clipped_output.num_cell_records--;
+ } else {
+ // Update prev/next pointers.
+ prev->next = new_cell.incident_edge;
+ new_cell.incident_edge->prev = prev;
}
- return true;
}
- return false;
+ clipped_output.num_edge_records >>= 1;
}
- std::vector<voronoi_iterator_type> cell_iterators_;
- voronoi_records_type cell_records_;
- voronoi_records_type vertex_records_;
- std::list<edge_type> edges_;
+ inline clipped_voronoi_edge_type &add_clipped_edge(
+ voronoi_output_clipped<coordinate_type> &clipped_output) {
+ clipped_output.edge_records.push_back(clipped_voronoi_edge_type());
+ clipped_output.num_edge_records++;
+ return clipped_output.edge_records.back();
+ }
+
+ std::vector<voronoi_cell_iterator_type> cell_iterators_;
+ voronoi_cells_type cell_records_;
+ voronoi_vertices_type vertex_records_;
+ voronoi_edges_type edges_;
int num_cell_records_;
int num_vertex_records_;
@@ -2098,6 +1993,7 @@
} // boost
} // detail
+#undef INV_LOG_2
#undef INT_PREDICATE_COMPUTE_DIFFERENCE
#undef INT_PREDICATE_CONVERT_65_BIT
#undef INT_PREDICATE_AVOID_CANCELLATION
Modified: sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_segment_builder.hpp
==============================================================================
--- sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_segment_builder.hpp (original)
+++ sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_segment_builder.hpp 2010-10-14 11:25:19 EDT (Thu, 14 Oct 2010)
@@ -154,9 +154,10 @@
}
// Clip using defined rectangle.
- void clip(const BRect<coordinate_type> &brect, ClippedOutput &clipped_output) {
- output_.clip(brect, clipped_output);
- }
+ // TODO(asydorchuk): Define what exactly it means to clip some region of voronoi diagram.
+ //void clip(const BRect<coordinate_type> &brect, ClippedOutput &clipped_output) {
+ // output_.clip(brect, clipped_output);
+ //}
protected:
typedef typename std::vector<site_event_type>::const_iterator site_events_iterator_type;
Modified: sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_segment_output.hpp
==============================================================================
--- sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_segment_output.hpp (original)
+++ sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_segment_output.hpp 2010-10-14 11:25:19 EDT (Thu, 14 Oct 2010)
@@ -81,6 +81,10 @@
///////////////////////////////////////////////////////////////////////////
// VORONOI OUTPUT TYPES ///////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////
+ namespace detail {
+ template <typename T>
+ struct site_event;
+ }
// Bounding rectangle data structure.
template <typename T>
@@ -127,26 +131,162 @@
}
};
- template <typename T>
- struct half_edge_clipped;
+ template <typename T>
+ class Helper {
+ public:
+ typedef T coordinate_type;
+
+ enum kEdgeType {
+ SEGMENT = 0,
+ RAY = 1,
+ LINE = 2,
+ };
+
+ // Find edge(segment, ray, line) rectangle intersetion points.
+ static bool find_intersections(const point_2d<coordinate_type> &origin,
+ const point_2d<coordinate_type> &direction,
+ kEdgeType edge_type, const BRect<coordinate_type> &brect,
+ std::vector< point_2d<coordinate_type> > &intersections) {
+ coordinate_type half = static_cast<coordinate_type>(0.5);
+
+ // Find rectangle center.
+ coordinate_type center_x = (brect.x_min + brect.x_max) * half;
+ coordinate_type center_y = (brect.y_min + brect.y_max) * half;
+
+ // Find rectangle half-diagonal vector.
+ coordinate_type len_x = brect.x_max - center_x;
+ coordinate_type len_y = brect.y_max - center_y;
+
+ // Find distance between origin and center of rectangle.
+ coordinate_type diff_x = origin.x() - center_x;
+ coordinate_type diff_y = origin.y() - center_y;
+
+ // Find direction perpendicular to the current.
+ coordinate_type perp_x = direction.y();
+ coordinate_type perp_y = -direction.x();
+
+ // Compare projections of distances.
+ coordinate_type lexpr = magnitude(perp_x * diff_x + perp_y * diff_y);
+ coordinate_type rexpr = magnitude(perp_x * len_x) + magnitude(perp_y * len_y);
+
+ // Intersection check.
+ if (lexpr > rexpr)
+ return false;
+
+ // Intersection parameters:
+ // origin + fT[i] * direction = intersections point, i = 0 .. 1.
+ bool fT0_used = false;
+ bool fT1_used = false;
+ double fT0 = 0.0;
+ double fT1 = 0.0;
+
+ // Find intersections with lines going through sides of a bounding rectangle.
+ clip_line(+direction.x(), -diff_x - len_x, fT0_used, fT1_used, fT0, fT1);
+ clip_line(-direction.x(), +diff_x - len_x, fT0_used, fT1_used, fT0, fT1);
+ clip_line(+direction.y(), -diff_y - len_y, fT0_used, fT1_used, fT0, fT1);
+ clip_line(-direction.y(), +diff_y - len_y, fT0_used, fT1_used, fT0, fT1);
+
+ 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 && 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;
+ }
+
+ private:
+ Helper();
+
+ static bool check_extent(double extent, kEdgeType etype) {
+ switch (etype) {
+ case SEGMENT: return extent >= 0.0 && extent <= 1.0;
+ case RAY: return extent >= 0.0;
+ case LINE: return true;
+ }
+ return true;
+ }
+
+ static coordinate_type magnitude(coordinate_type value) {
+ if (value >= static_cast<coordinate_type>(0))
+ return value;
+ return -value;
+ }
+
+ static bool clip_line(coordinate_type denom,
+ coordinate_type numer,
+ bool &fT0_used, bool &fT1_used,
+ double &fT0, double &fT1) {
+ if (denom > static_cast<coordinate_type>(0)) {
+ if (fT1_used && numer > denom * fT1)
+ return false;
+ if (!fT0_used || numer > denom * fT0) {
+ fT0_used = true;
+ fT0 = numer / denom;
+ }
+ return true;
+ } else if (denom < static_cast<coordinate_type>(0)) {
+ if (fT0_used && numer > denom * fT0)
+ return false;
+ if (!fT1_used || numer > denom * fT1) {
+ fT1_used = true;
+ fT1 = numer / denom;
+ }
+ return true;
+ }
+ return false;
+ }
+ };
- // 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 T>
- struct voronoi_record_clipped {
- 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<coordinate_type>* edge) :
- incident_edge(edge),
- voronoi_point(point),
- num_incident_edges(0) {}
- };
+ struct voronoi_edge_clipped;
+
+ template <typename T>
+ struct voronoi_cell_clipped {
+ typedef T coordinate_type;
+ typedef detail::site_event<T> site_event_type;
+
+ voronoi_edge_clipped<coordinate_type> *incident_edge;
+ int num_incident_edges;
+
+ voronoi_cell_clipped(const site_event_type &new_site,
+ voronoi_edge_clipped<coordinate_type>* edge) :
+ incident_edge(edge),
+ site(new_site),
+ num_incident_edges(0) {}
+
+ bool is_segment() const {
+ return site.is_segment();
+ }
+
+ point_2d<T> get_point0() const {
+ return site.get_point0();
+ }
+
+ point_2d<T> get_point1() const {
+ return site.get_point1();
+ }
+
+ private:
+ site_event_type site;
+
+ };
+
+ template <typename T>
+ struct voronoi_vertex_clipped {
+ typedef T coordinate_type;
+ typedef point_2d<T> Point2D;
+
+ voronoi_edge_clipped<coordinate_type> *incident_edge;
+ Point2D vertex;
+ int num_incident_edges;
+
+ voronoi_vertex_clipped(const Point2D &point, voronoi_edge_clipped<coordinate_type>* edge) :
+ incident_edge(edge),
+ vertex(point),
+ num_incident_edges(0) {}
+ };
// Half-edge data structure. Represents voronoi edge.
// Contains: 1) pointer to cell records;
@@ -156,22 +296,24 @@
// around start point;
// 5) pointer to twin half-edge.
template <typename T>
- struct half_edge_clipped {
+ struct voronoi_edge_clipped {
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;
+ typedef voronoi_cell_clipped<coordinate_type> voronoi_cell_type;
+ typedef voronoi_vertex_clipped<coordinate_type> voronoi_vertex_type;
+ typedef voronoi_edge_clipped<coordinate_type> voronoi_edge_type;
+ typedef detail::site_event<coordinate_type> site_event_type;
+
+ voronoi_cell_type *cell;
+ voronoi_vertex_type *start_point;
+ voronoi_vertex_type *end_point;
+ voronoi_edge_type *prev;
+ voronoi_edge_type *next;
+ voronoi_edge_type *rot_prev;
+ voronoi_edge_type *rot_next;
+ voronoi_edge_type *twin;
- voronoi_record_type *cell;
- voronoi_record_type *start_point;
- voronoi_record_type *end_point;
- half_edge_type *prev;
- half_edge_type *next;
- half_edge_type *rot_prev;
- half_edge_type *rot_next;
- half_edge_type *twin;
-
- half_edge_clipped() :
+ voronoi_edge_clipped() :
cell(NULL),
start_point(NULL),
end_point(NULL),
@@ -180,112 +322,104 @@
rot_prev(NULL),
rot_next(NULL),
twin(NULL) {}
+
+ std::vector<Point2D> get_intermediate_points(BRect<T> &brect) const {
+ const voronoi_cell_type *cell1 = cell;
+ const voronoi_cell_type *cell2 = twin->cell;
+ std::vector<Point2D> edge_points;
+ if (!(cell1->is_segment() ^ cell2->is_segment())) {
+ if (start_point != NULL && end_point != NULL) {
+ edge_points.push_back(start_point->vertex);
+ edge_points.push_back(end_point->vertex);
+ } else {
+ const Point2D &site1 = cell1->get_point0();
+ const Point2D &site2 = cell2->get_point0();
+ 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());
+ Helper<T>::find_intersections(origin, direction, Helper<T>::LINE,
+ brect, edge_points);
+ if (end_point != NULL)
+ edge_points[1] = end_point->vertex;
+ if (start_point != NULL)
+ edge_points[0] = start_point->vertex;
+ }
+ } else {
+ const Point2D &point1 = (cell1->is_segment()) ?
+ cell2->get_point0() : cell1->get_point0();
+ const Point2D &point2 = (cell1->is_segment()) ?
+ cell1->get_point0() : cell2->get_point0();
+ const Point2D &point3 = (cell1->is_segment()) ?
+ cell1->get_point1() : cell2->get_point1();
+ if (start_point != NULL && end_point != NULL) {
+ edge_points.push_back(start_point->vertex);
+ edge_points.push_back(end_point->vertex);
+ fill_intermediate_points(point1, point2, point3, edge_points);
+ } else {
+ coordinate_type dir_x = (cell1->is_segment() ^ (point1 == point3)) ?
+ point3.y() - point2.y() : point2.y() - point3.y();
+ coordinate_type dir_y = (cell1->is_segment() ^ (point1 == point3)) ?
+ point2.x() - point3.x() : point3.x() - point2.x();
+ Point2D direction(dir_x, dir_y);
+ Helper<T>::find_intersections(point1, direction, Helper<T>::LINE,
+ brect, edge_points);
+ if (end_point != NULL)
+ edge_points[1] = end_point->vertex;
+ if (start_point != NULL)
+ edge_points[0] = start_point->vertex;
+ }
+ }
+ return edge_points;
+ }
};
template <typename T>
- class voronoi_output_clipped {
+ struct voronoi_output_clipped {
public:
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;
+ typedef detail::site_event<T> site_event_type;
+
+ typedef voronoi_cell_clipped<coordinate_type> voronoi_cell_type;
+ typedef std::list<voronoi_cell_type> voronoi_cells_type;
+ typedef typename voronoi_cells_type::iterator voronoi_cell_iterator_type;
+ typedef typename voronoi_cells_type::const_iterator voronoi_cell_const_iterator_type;
+
+ typedef voronoi_vertex_clipped<coordinate_type> voronoi_vertex_type;
+ typedef std::list<voronoi_vertex_type> voronoi_vertices_type;
+ typedef typename voronoi_vertices_type::iterator voronoi_vertex_iterator_type;
+ typedef typename voronoi_vertices_type::const_iterator voronoi_vertex_const_iterator_type;
+
+ typedef voronoi_edge_clipped<coordinate_type> voronoi_edge_type;
+ typedef std::list<voronoi_edge_type> voronoi_edges_type;
+ typedef typename voronoi_edges_type::iterator voronoi_edge_iterator_type;
+ typedef typename voronoi_edges_type::const_iterator voronoi_edge_const_iterator_type;
+
+ BRect<coordinate_type> bounding_rectangle;
+
+ int num_cell_records;
+ int num_vertex_records;
+ int num_edge_records;
+
+ voronoi_cells_type cell_records;
+ voronoi_vertices_type vertex_records;
+ voronoi_edges_type edge_records;
voronoi_output_clipped() {
- num_cell_records_ = 0;
- num_vertex_records_ = 0;
- num_edges_ = 0;
+ num_cell_records = 0;
+ num_vertex_records = 0;
+ num_edge_records = 0;
}
void reset() {
- cell_records_.clear();
- vertex_records_.clear();
- edges_.clear();
-
- num_cell_records_ = 0;
- num_vertex_records_ = 0;
- num_edges_ = 0;
- }
-
- void set_bounding_rectangle(const BRect<coordinate_type> &brect) {
- brect_ = brect;
- }
-
- const BRect<coordinate_type> &get_bounding_rectangle() {
- return brect_;
- }
-
- voronoi_record_type &add_vertex(const Point2D &vertex_point) {
- vertex_records_.push_back(voronoi_record_type(vertex_point, NULL));
- num_vertex_records_++;
- return vertex_records_.back();
- }
-
- voronoi_record_type &add_boundary_vertex(const Point2D &boundary_point) {
- vertex_records_.push_back(voronoi_record_type(boundary_point, NULL));
- return vertex_records_.back();
- }
-
- edge_type &add_edge() {
- edges_.push_back(edge_type());
- num_edges_++;
- return edges_.back();
+ cell_records.clear();
+ vertex_records.clear();
+ edge_records.clear();
+
+ num_cell_records = 0;
+ num_vertex_records = 0;
+ num_edge_records = 0;
}
-
- voronoi_record_type &add_cell(const Point2D &site_point) {
- cell_records_.push_back(voronoi_record_type(site_point, NULL));
- num_cell_records_++;
- return cell_records_.back();
- }
-
- void pop_cell() {
- cell_records_.pop_back();
- num_cell_records_--;
- }
-
- const voronoi_records_type &get_voronoi_cells() const {
- return cell_records_;
- }
-
- const voronoi_records_type &get_voronoi_vertices() const {
- return vertex_records_;
- }
-
- const voronoi_edges_type &get_voronoi_edges() const {
- return edges_;
- }
-
- int get_num_voronoi_cells() const {
- return num_cell_records_;
- }
-
- int get_num_voronoi_vertices() const {
- return num_vertex_records_;
- }
-
- int get_num_voronoi_edges() const {
- return num_edges_ / 2;
- }
-
- private:
- voronoi_records_type cell_records_;
- voronoi_records_type vertex_records_;
- voronoi_edges_type edges_;
-
- int num_cell_records_;
- int num_vertex_records_;
- int num_edges_;
-
- BRect<coordinate_type> brect_;
-
- // Disallow copy constructor and operator=
- voronoi_output_clipped(const voronoi_output_clipped&);
- void operator=(const voronoi_output_clipped&);
};
} // sweepline
Modified: sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_segment_sweepline.hpp
==============================================================================
--- sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_segment_sweepline.hpp (original)
+++ sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_segment_sweepline.hpp 2010-10-14 11:25:19 EDT (Thu, 14 Oct 2010)
@@ -11,7 +11,6 @@
#define BOOST_SWEEPLINE_VORONOI_SEGMENT_SWEEPLINE
#include <algorithm>
-#include <assert.h>
#include <cmath>
#include <cstring>
#include <list>
Added: sandbox/SOC/2010/sweepline/libs/sweepline/example/output_data/example_021.png
==============================================================================
Binary file. No diff available.
Added: sandbox/SOC/2010/sweepline/libs/sweepline/example/output_data/example_022.png
==============================================================================
Binary file. No diff available.
Added: sandbox/SOC/2010/sweepline/libs/sweepline/example/output_data/example_023.png
==============================================================================
Binary file. No diff available.
Added: sandbox/SOC/2010/sweepline/libs/sweepline/example/output_data/example_024.png
==============================================================================
Binary file. No diff available.
Added: sandbox/SOC/2010/sweepline/libs/sweepline/example/output_data/example_025.png
==============================================================================
Binary file. No diff available.
Added: sandbox/SOC/2010/sweepline/libs/sweepline/example/output_data/example_026.png
==============================================================================
Binary file. No diff available.
Added: sandbox/SOC/2010/sweepline/libs/sweepline/example/output_data/example_027.png
==============================================================================
Binary file. No diff available.
Added: sandbox/SOC/2010/sweepline/libs/sweepline/example/output_data/example_028.png
==============================================================================
Binary file. No diff available.
Added: sandbox/SOC/2010/sweepline/libs/sweepline/example/output_data/example_029.png
==============================================================================
Binary file. No diff available.
Added: sandbox/SOC/2010/sweepline/libs/sweepline/example/output_data/example_030.png
==============================================================================
Binary file. No diff available.
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-10-14 11:25:19 EDT (Thu, 14 Oct 2010)
@@ -10,7 +10,8 @@
#include <QtOpenGL/QGLWidget>
#include <QtGui/QtGui>
-#include "boost/sweepline/voronoi_sweepline.hpp"
+#include "boost/sweepline/voronoi_segment_sweepline.hpp"
+using namespace boost::sweepline;
class GLWidget : public QGLWidget {
Q_OBJECT
@@ -22,7 +23,8 @@
}
void build(QString file_path) {
- std::vector<Point2D> sites;
+ std::vector<Point2D> point_sites;
+ std::vector<Segment2D> segment_sites;
// Open file.
QFile data(file_path);
@@ -32,20 +34,27 @@
// Read points from the file.
QTextStream in_stream(&data);
- int num_sites;
- in_stream >> num_sites;
- coordinate_type x, y;
- for (int i = 0; i < num_sites; i++) {
- in_stream >> x >> y;
- sites.push_back(boost::sweepline::make_point_2d(x, y));
+ int num_point_sites = 0;
+ int num_edge_sites = 0;
+ coordinate_type x1, y1, x2, y2;
+ in_stream >> num_point_sites;
+ for (int i = 0; i < num_point_sites; i++) {
+ in_stream >> x1 >> y1;
+ point_sites.push_back(make_point_2d(x1, y1));
}
+ in_stream >> num_edge_sites;
+ for (int i = 0; i < num_edge_sites; i++) {
+ in_stream >> x1 >> y1 >> x2 >> y2;
+ segment_sites.push_back(std::make_pair(
+ make_point_2d(x1, y1), make_point_2d(x2, y2)));
+ }
in_stream.flush();
// Build voronoi diagram.
- voronoi_builder_.init(sites);
+ voronoi_builder_.init(point_sites, segment_sites);
voronoi_builder_.run_sweepline();
voronoi_builder_.clip(voronoi_output_);
- brect_ = voronoi_output_.get_bounding_rectangle();
+ brect_ = voronoi_output_.bounding_rectangle;
// Update view.
update_view_port();
@@ -62,34 +71,52 @@
glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);
// Draw voronoi sites.
- voronoi_records_type cells = voronoi_output_.get_voronoi_cells();
- voronoi_const_iterator_type it;
- glColor3f(0.0f, 0.0f, 1.0f);
- glBegin(GL_POINTS);
- for (it = cells.begin(); it != cells.end(); it++)
- glVertex2f(it->voronoi_point.x(), it->voronoi_point.y());
- glEnd();
+ {
+ voronoi_cells_type cells = voronoi_output_.cell_records;
+ voronoi_cell_const_iterator_type it;
+ glColor3f(0.0f, 0.0f, 1.0f);
+ glBegin(GL_POINTS);
+ for (it = cells.begin(); it != cells.end(); it++) {
+ if (!it->is_segment())
+ glVertex2f(it->get_point0().x(), it->get_point0().y());
+ }
+ glEnd();
+ glBegin(GL_LINES);
+ for (it = cells.begin(); it != cells.end(); it++) {
+ if (it->is_segment()) {
+ glVertex2f(it->get_point0().x(), it->get_point0().y());
+ glVertex2f(it->get_point1().x(), it->get_point1().y());
+ }
+ }
+ glEnd();
+ }
// Draw voronoi vertices.
- voronoi_records_type vertices = voronoi_output_.get_voronoi_vertices();
- glColor3f(0.0f, 1.0f, 0.0f);
- glBegin(GL_POINTS);
- for (it = vertices.begin(); it != vertices.end(); it++)
- glVertex2f(it->voronoi_point.x(), it->voronoi_point.y());
- glEnd();
+ {
+ voronoi_vertices_type vertices = voronoi_output_.vertex_records;
+ voronoi_vertex_const_iterator_type it;
+ glColor3f(0.0f, 1.0f, 0.0f);
+ glBegin(GL_POINTS);
+ for (it = vertices.begin(); it != vertices.end(); it++)
+ glVertex2f(it->vertex.x(), it->vertex.y());
+ glEnd();
+ }
// Draw voronoi edges.
- voronoi_edges_type edges = voronoi_output_.get_voronoi_edges();
- edges_const_iterator_type edge_it;
- glColor3f(0.0f, 1.0f, 0.0f);
- glBegin(GL_LINES);
- for (edge_it = edges.begin(); edge_it != edges.end(); edge_it++) {
- glVertex2f(edge_it->start_point->voronoi_point.x(),
- edge_it->start_point->voronoi_point.y());
- glVertex2f(edge_it->end_point->voronoi_point.x(),
- edge_it->end_point->voronoi_point.y());
- }
- glEnd();
+ {
+ voronoi_edges_type edges = voronoi_output_.edge_records;
+ voronoi_edge_const_iterator_type it;
+ glColor3f(0.0f, 1.0f, 0.0f);
+ glBegin(GL_LINES);
+ for (it = edges.begin(); it != edges.end(); it++) {
+ std::vector<Point2D> temp_v = it->get_intermediate_points(brect_);
+ for (int i = 0; i < static_cast<int>(temp_v.size()) - 1; i++) {
+ glVertex2f(temp_v[i].x(), temp_v[i].y());
+ glVertex2f(temp_v[i+1].x(), temp_v[i+1].y());
+ }
+ }
+ glEnd();
+ }
}
void resizeGL(int width, int height) {
@@ -106,18 +133,23 @@
}
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<coordinate_type>::voronoi_edges_type
+ typedef point_2d<coordinate_type> Point2D;
+ typedef voronoi_builder<coordinate_type>::Segment2D Segment2D;
+ typedef voronoi_output_clipped<coordinate_type>::voronoi_cells_type
+ voronoi_cells_type;
+ typedef voronoi_output_clipped<coordinate_type>::voronoi_vertices_type
+ voronoi_vertices_type;
+ typedef voronoi_output_clipped<coordinate_type>::voronoi_edges_type
voronoi_edges_type;
- typedef boost::sweepline::voronoi_output_clipped<coordinate_type>::voronoi_const_iterator_type
- voronoi_const_iterator_type;
- typedef boost::sweepline::voronoi_output_clipped<coordinate_type>::edges_const_iterator_type
- edges_const_iterator_type;
- boost::sweepline::voronoi_builder<coordinate_type> voronoi_builder_;
- boost::sweepline::BRect<coordinate_type> brect_;
- boost::sweepline::voronoi_output_clipped<coordinate_type> voronoi_output_;
+ typedef voronoi_output_clipped<coordinate_type>::voronoi_cell_const_iterator_type
+ voronoi_cell_const_iterator_type;
+ typedef voronoi_output_clipped<coordinate_type>::voronoi_vertex_const_iterator_type
+ voronoi_vertex_const_iterator_type;
+ typedef voronoi_output_clipped<coordinate_type>::voronoi_edge_const_iterator_type
+ voronoi_edge_const_iterator_type;
+ voronoi_builder<coordinate_type> voronoi_builder_;
+ BRect<coordinate_type> brect_;
+ voronoi_output_clipped<coordinate_type> voronoi_output_;
};
class MainWindow : public QWidget {
@@ -132,7 +164,7 @@
centralLayout->addLayout(create_file_layout());
setLayout(centralLayout);
- update_file_list_();
+ update_file_list();
setWindowTitle(tr("Voronoi Visualizer"));
layout()->setSizeConstraint( QLayout::SetFixedSize );
}
@@ -144,7 +176,7 @@
if (new_path.isEmpty())
return;
file_dir_.setPath(new_path);
- update_file_list_();
+ update_file_list();
}
void build() {
@@ -177,7 +209,7 @@
return file_layout;
}
- void update_file_list_() {
+ void update_file_list() {
QFileInfoList list = file_dir_.entryInfoList();
file_list_->clear();
if (file_dir_.count() == 0)
Modified: sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_output_verification.hpp
==============================================================================
--- sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_output_verification.hpp (original)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_output_verification.hpp 2010-10-14 11:25:19 EDT (Thu, 14 Oct 2010)
@@ -33,14 +33,14 @@
template <typename Output>
bool verify_half_edge_orientation(const Output &output) {
typedef typename Output::Point2D Point2D;
- typename Output::edges_const_iterator_type edge_it;
- for (edge_it = output.get_voronoi_edges().begin();
- edge_it != output.get_voronoi_edges().end(); edge_it++) {
+ typename Output::voronoi_edge_const_iterator_type edge_it;
+ for (edge_it = output.edge_records.begin();
+ edge_it != output.edge_records.end(); edge_it++) {
if (edge_it->start_point != NULL && edge_it->end_point != NULL) {
- const Point2D &site = edge_it->cell->voronoi_point;
- const Point2D &start_point = edge_it->start_point->voronoi_point;
- const Point2D &end_point = edge_it->end_point->voronoi_point;
- if (get_orientation(start_point, end_point, site) != LEFT_ORIENTATION)
+ const Point2D &site_point = edge_it->cell->get_point0();
+ const Point2D &start_point = edge_it->start_point->vertex;
+ const Point2D &end_point = edge_it->end_point->vertex;
+ if (get_orientation(start_point, end_point, site_point) != LEFT_ORIENTATION)
return false;
}
}
@@ -50,10 +50,10 @@
template <typename Output>
bool verify_cell_convexity(const Output &output) {
typedef typename Output::Point2D Point2D;
- typename Output::voronoi_const_iterator_type cell_it;
- for (cell_it = output.get_voronoi_cells().begin();
- cell_it != output.get_voronoi_cells().end(); cell_it++) {
- const typename Output::edge_type *edge = cell_it->incident_edge;
+ typename Output::voronoi_cell_const_iterator_type cell_it;
+ for (cell_it = output.cell_records.begin();
+ cell_it != output.cell_records.end(); cell_it++) {
+ const typename Output::voronoi_edge_type *edge = cell_it->incident_edge;
if (edge)
do {
if (edge->next->prev != edge)
@@ -64,9 +64,9 @@
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;
+ const Point2D &vertex1 = edge->start_point->vertex;
+ const Point2D &vertex2 = edge->end_point->vertex;
+ const Point2D &vertex3 = edge->next->end_point->vertex;
if (get_orientation(vertex1, vertex2, vertex3) != LEFT_ORIENTATION)
return false;
}
@@ -79,18 +79,18 @@
template <typename Output>
bool verify_incident_edges_ccw_order(const Output &output) {
typedef typename Output::Point2D Point2D;
- typename Output::voronoi_const_iterator_type vertex_it;
- for (vertex_it = output.get_voronoi_vertices().begin();
- vertex_it != output.get_voronoi_vertices().end(); vertex_it++) {
+ typename Output::voronoi_vertex_const_iterator_type vertex_it;
+ for (vertex_it = output.vertex_records.begin();
+ vertex_it != output.vertex_records.end(); vertex_it++) {
if (vertex_it->num_incident_edges < 3)
continue;
- typename Output::edge_type *edge = vertex_it->incident_edge;
+ typename Output::voronoi_edge_type *edge = vertex_it->incident_edge;
do {
- typename Output::edge_type *edge_next1 = edge->rot_next;
- typename Output::edge_type *edge_next2 = edge_next1->rot_next;
- const Point2D &site1 = edge->cell->voronoi_point;
- const Point2D &site2 = edge_next1->cell->voronoi_point;
- const Point2D &site3 = edge_next2->cell->voronoi_point;
+ typename Output::voronoi_edge_type *edge_next1 = edge->rot_next;
+ typename Output::voronoi_edge_type *edge_next2 = edge_next1->rot_next;
+ const Point2D &site1 = edge->cell->get_point0();
+ const Point2D &site2 = edge_next1->cell->get_point0();
+ const Point2D &site3 = edge_next2->cell->get_point0();
if (get_orientation(site1, site2, site3) != LEFT_ORIENTATION)
return false;
@@ -110,12 +110,12 @@
std::map< Point2D, std::vector<Point2D> > edge_map;
typedef typename std::map< Point2D, std::vector<Point2D> >::const_iterator
edge_map_iterator;
- typename Output::edges_const_iterator_type edge_it;
- for (edge_it = output.get_voronoi_edges().begin();
- edge_it != output.get_voronoi_edges().end(); edge_it++) {
+ typename Output::voronoi_edge_const_iterator_type edge_it;
+ for (edge_it = output.edge_records.begin();
+ edge_it != output.edge_records.end(); edge_it++) {
if (edge_it->start_point != NULL && edge_it->end_point != NULL) {
- const Point2D &start_point = edge_it->start_point->voronoi_point;
- const Point2D &end_point = edge_it->end_point->voronoi_point;
+ const Point2D &start_point = edge_it->start_point->vertex;
+ const Point2D &end_point = edge_it->end_point->vertex;
if (start_point < end_point)
edge_map[start_point].push_back(end_point);
}
Modified: sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_segment/segment_predicates_test.cpp
==============================================================================
--- sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_segment/segment_predicates_test.cpp (original)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_segment/segment_predicates_test.cpp 2010-10-14 11:25:19 EDT (Thu, 14 Oct 2010)
@@ -236,13 +236,13 @@
segm_site1_2.set_inverse();
// New sites.
- point_2d<T> new_site1 = make_point_2d<T>(static_cast<T>(0), static_cast<T>(5));
+ point_2d<T> new_site1 = make_point_2d<T>(static_cast<T>(2), static_cast<T>(7));
point_2d<T> new_site2 = make_point_2d<T>(static_cast<T>(1), static_cast<T>(5));
point_2d<T> new_site3 = make_point_2d<T>(static_cast<T>(-1), static_cast<T>(5));
CHECK_LESS_PREDICATE_SS(segm_site1_1, segm_site1_2, new_site1, false);
- CHECK_LESS_PREDICATE_SS(segm_site1_1, segm_site1_2, new_site2, true);
- CHECK_LESS_PREDICATE_SS(segm_site1_1, segm_site1_2, new_site3, false);
+ CHECK_LESS_PREDICATE_SS(segm_site1_1, segm_site1_2, new_site2, false);
+ CHECK_LESS_PREDICATE_SS(segm_site1_1, segm_site1_2, new_site3, true);
}
BOOST_AUTO_TEST_CASE_TEMPLATE(less_predicate_segment_segment_test2, T, test_types) {
@@ -283,3 +283,29 @@
CHECK_LESS_PREDICATE_SS(segm_site3, segm_site1_2, new_site3, false);
CHECK_LESS_PREDICATE_SS(segm_site3, segm_site1_2, new_site4, true);
}
+
+//BOOST_AUTO_TEST_CASE_TEMPLATE(point_projection_test1, T, test_types) {
+// point_2d<T> segm_start = make_point_2d<T>(static_cast<T>(0), static_cast<T>(0));
+// point_2d<T> segm_end = make_point_2d<T>(static_cast<T>(5), static_cast<T>(-3));
+// point_2d<T> point1 = make_point_2d<T>(static_cast<T>(4), static_cast<T>(1));
+// point_2d<T> point2 = make_point_2d<T>(static_cast<T>(1), static_cast<T>(-4));
+// double projection1 = detail::get_point_projection(point1, segm_start, segm_end);
+// BOOST_CHECK_EQUAL(projection1 == 0.5, true);
+// double projection2 = detail::get_point_projection(point2, segm_start, segm_end);
+// BOOST_CHECK_EQUAL(projection2 == 0.5, true);
+//}
+//
+//BOOST_AUTO_TEST_CASE_TEMPLATE(compute_intermediate_points_test1, T, test_types) {
+// point_2d<T> point_site = make_point_2d<T>(static_cast<T>(5), static_cast<T>(-7));
+// point_2d<T> segm_site_start = make_point_2d<T>(static_cast<T>(1), static_cast<T>(-2));
+// point_2d<T> segm_site_end = make_point_2d<T>(static_cast<T>(1), static_cast<T>(-12));
+// std::vector< point_2d<T> > intermediate_points;
+// intermediate_points.push_back(make_point_2d<T>(static_cast<T>(5), static_cast<T>(-3)));
+// intermediate_points.push_back(make_point_2d<T>(static_cast<T>(5), static_cast<T>(-11)));
+// detail::fill_intermediate_points(point_site, segm_site_start, segm_site_end,
+// intermediate_points);
+// BOOST_CHECK_EQUAL(intermediate_points.size() == 5, true);
+// BOOST_CHECK_EQUAL(intermediate_points[1] == make_point_2d(3.5, -5.0), true);
+// BOOST_CHECK_EQUAL(intermediate_points[2] == make_point_2d(3.0, -7.0), true);
+// BOOST_CHECK_EQUAL(intermediate_points[3] == make_point_2d(3.5, -9.0), true);
+//}
\ No newline at end of file
Modified: sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_segment/segment_voronoi_builder_test.cpp
==============================================================================
--- sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_segment/segment_voronoi_builder_test.cpp (original)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_segment/segment_voronoi_builder_test.cpp 2010-10-14 11:25:19 EDT (Thu, 14 Oct 2010)
@@ -27,8 +27,8 @@
// Sites: (0, 0).
BOOST_AUTO_TEST_CASE_TEMPLATE(single_site_test, T, test_types) {
typedef T coordinate_type;
- typedef typename voronoi_output_clipped<coordinate_type>::voronoi_const_iterator_type
- voronoi_const_iterator_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;
@@ -47,15 +47,15 @@
bounding_rectangle.x_max == static_cast<coordinate_type>(0) &&
bounding_rectangle.y_max == static_cast<coordinate_type>(0), true);
- BOOST_CHECK_EQUAL(static_cast<int>(test_output.get_voronoi_cells().size()), 1);
- BOOST_CHECK_EQUAL(static_cast<int>(test_output.get_voronoi_vertices().size()), 0);
- 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);
+ BOOST_CHECK_EQUAL(static_cast<int>(test_output.cell_records.size()), 1);
+ BOOST_CHECK_EQUAL(static_cast<int>(test_output.vertex_records.size()), 0);
+ BOOST_CHECK_EQUAL(static_cast<int>(test_output.edge_records.size()), 0);
+
+ BOOST_CHECK_EQUAL(test_output.num_cell_records, 1);
+ BOOST_CHECK_EQUAL(test_output.num_vertex_records, 0);
+ BOOST_CHECK_EQUAL(test_output.num_edge_records, 0);
- voronoi_const_iterator_type it = test_output.get_voronoi_cells().begin();
+ voronoi_cell_const_iterator_type it = test_output.cell_records.begin();
BOOST_CHECK_EQUAL(it->num_incident_edges, 0);
BOOST_CHECK_EQUAL(it->incident_edge == NULL, true);
}
@@ -63,9 +63,9 @@
// 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>::edge_type edge_type;
- typedef typename voronoi_output_clipped<coordinate_type>::voronoi_const_iterator_type
- voronoi_const_iterator_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;
@@ -86,42 +86,42 @@
bounding_rectangle.x_max == static_cast<coordinate_type>(0) &&
bounding_rectangle.y_max == static_cast<coordinate_type>(1), true);
- BOOST_CHECK_EQUAL(static_cast<int>(test_output.get_voronoi_cells().size()), 2);
- BOOST_CHECK_EQUAL(static_cast<int>(test_output.get_voronoi_vertices().size()), 2);
- 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);
+ 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_const_iterator_type cell_it = test_output.get_voronoi_cells().begin();
+ 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);
- edge_type *edge1_1 = cell_it->incident_edge;
- edge_type *edge1_2 = edge1_1->twin;
+ 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 == edge1_1, true);
- BOOST_CHECK_EQUAL(edge1_1->rot_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 == edge1_2, true);
- BOOST_CHECK_EQUAL(edge1_2->rot_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>::edge_type edge_type;
- typedef typename voronoi_output_clipped<coordinate_type>::voronoi_const_iterator_type
- voronoi_const_iterator_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;
@@ -144,34 +144,34 @@
bounding_rectangle.x_max == static_cast<coordinate_type>(2) &&
bounding_rectangle.y_max == static_cast<coordinate_type>(2), true);
- BOOST_CHECK_EQUAL(static_cast<int>(test_output.get_voronoi_cells().size()), 3);
- BOOST_CHECK_EQUAL(static_cast<int>(test_output.get_voronoi_vertices().size()), 4);
- 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);
+ 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_const_iterator_type cell_it = test_output.get_voronoi_cells().begin();
+ voronoi_cell_const_iterator_type cell_it = test_output.cell_records.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;
+ 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);
- edge_type *edge2_2 = cell_it->incident_edge;
- edge_type *edge2_1 = edge2_2->twin;
+ 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 == 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(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 == edge2_2 && edge2_2->rot_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);
@@ -180,9 +180,9 @@
// 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>::edge_type edge_type;
- typedef typename voronoi_output_clipped<coordinate_type>::voronoi_const_iterator_type
- voronoi_const_iterator_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>(
@@ -209,28 +209,28 @@
bounding_rectangle.x_max == static_cast<coordinate_type>(2) &&
bounding_rectangle.y_max == static_cast<coordinate_type>(4), true);
- BOOST_CHECK_EQUAL(static_cast<int>(test_output.get_voronoi_cells().size()), 3);
- BOOST_CHECK_EQUAL(static_cast<int>(test_output.get_voronoi_vertices().size()), 4);
+ 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_const_iterator_type it = test_output.get_voronoi_vertices().begin();
+ voronoi_vertex_const_iterator_type it = test_output.vertex_records.begin();
BOOST_CHECK_EQUAL(it->num_incident_edges, 3);
- BOOST_CHECK_EQUAL(it->voronoi_point.x() == static_cast<coordinate_type>(0.25) &&
- it->voronoi_point.y() == static_cast<coordinate_type>(2.0), true);
+ BOOST_CHECK_EQUAL(it->vertex.x() == static_cast<coordinate_type>(0.25) &&
+ it->vertex.y() == static_cast<coordinate_type>(2.0), true);
- edge_type *edge1_1 = it->incident_edge;
- edge_type *edge1_2 = edge1_1->twin;
- CHECK_EQUAL_POINTS(edge1_1->cell->voronoi_point, point3);
- CHECK_EQUAL_POINTS(edge1_2->cell->voronoi_point, point1);
-
- edge_type *edge2_1 = edge1_1->rot_prev;
- edge_type *edge2_2 = edge2_1->twin;
- CHECK_EQUAL_POINTS(edge2_1->cell->voronoi_point, point1);
- CHECK_EQUAL_POINTS(edge2_2->cell->voronoi_point, point2);
-
- edge_type *edge3_1 = edge2_1->rot_prev;
- edge_type *edge3_2 = edge3_1->twin;
- CHECK_EQUAL_POINTS(edge3_1->cell->voronoi_point, point2);
- CHECK_EQUAL_POINTS(edge3_2->cell->voronoi_point, point3);
+ 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);
@@ -252,9 +252,9 @@
// 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>::edge_type edge_type;
- typedef typename voronoi_output_clipped<coordinate_type>::voronoi_const_iterator_type
- voronoi_const_iterator_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>(
@@ -275,28 +275,28 @@
test_beach_line.clip(test_output);
VERIFY_VORONOI_OUTPUT(test_output, COMPLETE_VERIFICATION);
- 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.cell_records.size()), 3);
+ BOOST_CHECK_EQUAL(static_cast<int>(test_output.vertex_records.size()), 1);
- voronoi_const_iterator_type it = test_output.get_voronoi_vertices().begin();
+ voronoi_vertex_const_iterator_type it = test_output.vertex_records.begin();
BOOST_CHECK_EQUAL(it->num_incident_edges, 3);
- BOOST_CHECK_EQUAL(it->voronoi_point.x() == static_cast<coordinate_type>(1.75) &&
- it->voronoi_point.y() == static_cast<coordinate_type>(2.0), true);
+ BOOST_CHECK_EQUAL(it->vertex.x() == static_cast<coordinate_type>(1.75) &&
+ it->vertex.y() == static_cast<coordinate_type>(2.0), true);
- edge_type *edge1_1 = it->incident_edge;
- edge_type *edge1_2 = edge1_1->twin;
- CHECK_EQUAL_POINTS(edge1_1->cell->voronoi_point, point2);
- CHECK_EQUAL_POINTS(edge1_2->cell->voronoi_point, point1);
-
- edge_type *edge2_1 = edge1_1->rot_prev;
- edge_type *edge2_2 = edge2_1->twin;
- CHECK_EQUAL_POINTS(edge2_1->cell->voronoi_point, point1);
- CHECK_EQUAL_POINTS(edge2_2->cell->voronoi_point, point3);
-
- edge_type *edge3_1 = edge2_1->rot_prev;
- edge_type *edge3_2 = edge3_1->twin;
- CHECK_EQUAL_POINTS(edge3_1->cell->voronoi_point, point3);
- CHECK_EQUAL_POINTS(edge3_2->cell->voronoi_point, point2);
+ 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);
@@ -318,9 +318,9 @@
// Sites: (0, 0), (0, 1), (1, 0), (1, 1).
BOOST_AUTO_TEST_CASE_TEMPLATE(square_test3, T, test_types) {
typedef T coordinate_type;
- typedef typename voronoi_output_clipped<coordinate_type>::edge_type edge_type;
- typedef typename voronoi_output_clipped<coordinate_type>::voronoi_const_iterator_type
- voronoi_const_iterator_type;
+ 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;
@@ -339,38 +339,36 @@
test_beach_line.clip(test_output);
VERIFY_VORONOI_OUTPUT(test_output, COMPLETE_VERIFICATION);
- BOOST_CHECK_EQUAL(static_cast<coordinate_type>(test_output.get_voronoi_cells().size()), 4);
- BOOST_CHECK_EQUAL(static_cast<coordinate_type>(test_output.get_voronoi_vertices().size()), 5);
- BOOST_CHECK_EQUAL(test_output.get_num_voronoi_cells(), 4);
- BOOST_CHECK_EQUAL(test_output.get_num_voronoi_vertices(), 1);
- BOOST_CHECK_EQUAL(test_output.get_num_voronoi_edges(), 4);
+ 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_const_iterator_type it = test_output.get_voronoi_vertices().begin();
+ voronoi_vertex_const_iterator_type it = test_output.vertex_records.begin();
BOOST_CHECK_EQUAL(it->num_incident_edges, 4);
- BOOST_CHECK_EQUAL(it->voronoi_point.x() == static_cast<coordinate_type>(0.5) &&
- it->voronoi_point.y() == static_cast<coordinate_type>(0.5), true);
+ 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.
- edge_type *edge1_1 = it->incident_edge;
- edge_type *edge1_2 = edge1_1->twin;
- CHECK_EQUAL_POINTS(edge1_1->cell->voronoi_point, points[1]);
- CHECK_EQUAL_POINTS(edge1_2->cell->voronoi_point, points[3]);
-
- edge_type *edge2_1 = edge1_1->rot_prev;
- edge_type *edge2_2 = edge2_1->twin;
- CHECK_EQUAL_POINTS(edge2_1->cell->voronoi_point, points[3]);
- CHECK_EQUAL_POINTS(edge2_2->cell->voronoi_point, points[2]);
-
- edge_type *edge3_1 = edge2_1->rot_prev;
- edge_type *edge3_2 = edge3_1->twin;
- CHECK_EQUAL_POINTS(edge3_1->cell->voronoi_point, points[2]);
- CHECK_EQUAL_POINTS(edge3_2->cell->voronoi_point, points[0]);
-
- edge_type *edge4_1 = edge3_1->rot_prev;
- edge_type *edge4_2 = edge4_1->twin;
- CHECK_EQUAL_POINTS(edge4_1->cell->voronoi_point, points[0]);
- CHECK_EQUAL_POINTS(edge4_2->cell->voronoi_point, points[1]);
+ 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);
@@ -409,9 +407,9 @@
test_beach_line.clip(test_output);
VERIFY_VORONOI_OUTPUT(test_output, COMPLETE_VERIFICATION);
- BOOST_CHECK_EQUAL(test_output.get_num_voronoi_cells(), 9);
- BOOST_CHECK_EQUAL(test_output.get_num_voronoi_vertices(), 4);
- BOOST_CHECK_EQUAL(test_output.get_num_voronoi_edges(), 12);
+ BOOST_CHECK_EQUAL(test_output.num_cell_records, 9);
+ BOOST_CHECK_EQUAL(test_output.num_vertex_records, 4);
+ BOOST_CHECK_EQUAL(test_output.num_edge_records, 12);
}
// Sites: {(x, y) | x = 0 .. 9, y = 0 .. 9}.
@@ -430,9 +428,9 @@
test_beach_line.clip(test_output);
VERIFY_VORONOI_OUTPUT(test_output, COMPLETE_VERIFICATION);
- BOOST_CHECK_EQUAL(test_output.get_num_voronoi_cells(), 100);
- BOOST_CHECK_EQUAL(test_output.get_num_voronoi_vertices(), 81);
- BOOST_CHECK_EQUAL(test_output.get_num_voronoi_edges(), 180);
+ BOOST_CHECK_EQUAL(test_output.num_cell_records, 100);
+ BOOST_CHECK_EQUAL(test_output.num_vertex_records, 81);
+ BOOST_CHECK_EQUAL(test_output.num_edge_records, 180);
}
// Sites: {(x, y) | x = 0 .. 33, y = 0 .. 33}.
@@ -451,9 +449,9 @@
test_beach_line.clip(test_output);
VERIFY_VORONOI_OUTPUT(test_output, COMPLETE_VERIFICATION);
- BOOST_CHECK_EQUAL(test_output.get_num_voronoi_cells(), 1089);
- BOOST_CHECK_EQUAL(test_output.get_num_voronoi_vertices(), 1024);
- BOOST_CHECK_EQUAL(test_output.get_num_voronoi_edges(), 2112);
+ BOOST_CHECK_EQUAL(test_output.num_cell_records, 1089);
+ BOOST_CHECK_EQUAL(test_output.num_vertex_records, 1024);
+ BOOST_CHECK_EQUAL(test_output.num_edge_records, 2112);
}
// Sites: {(x, y) | x = 0 .. 100, y = 0 .. 100}.
@@ -472,9 +470,9 @@
test_beach_line.clip(test_output);
VERIFY_VORONOI_OUTPUT(test_output, COMPLETE_VERIFICATION);
- BOOST_CHECK_EQUAL(test_output.get_num_voronoi_cells(), 10000);
- BOOST_CHECK_EQUAL(test_output.get_num_voronoi_vertices(), 9801);
- BOOST_CHECK_EQUAL(test_output.get_num_voronoi_edges(), 19800);
+ BOOST_CHECK_EQUAL(test_output.num_cell_records, 10000);
+ BOOST_CHECK_EQUAL(test_output.num_vertex_records, 9801);
+ BOOST_CHECK_EQUAL(test_output.num_edge_records, 19800);
}
// Sites: {(x, y) | x = 0 .. 333, y = 0 .. 333}.
@@ -493,9 +491,9 @@
test_beach_line.clip(test_output);
VERIFY_VORONOI_OUTPUT(test_output, COMPLETE_VERIFICATION);
- BOOST_CHECK_EQUAL(test_output.get_num_voronoi_cells(), 110889);
- BOOST_CHECK_EQUAL(test_output.get_num_voronoi_vertices(), 110224);
- BOOST_CHECK_EQUAL(test_output.get_num_voronoi_edges(), 221112);
+ BOOST_CHECK_EQUAL(test_output.num_cell_records, 110889);
+ BOOST_CHECK_EQUAL(test_output.num_vertex_records, 110224);
+ BOOST_CHECK_EQUAL(test_output.num_edge_records, 221112);
}
// Generate 10 random sites 10000 times.
@@ -633,6 +631,8 @@
segm_vec.push_back(std::make_pair< point_2d<T>, point_2d<T> >(point1, point2));
test_voronoi_builder.init(segm_vec);
test_voronoi_builder.run_sweepline();
+
+ // TODO(asydorchuk): Add output checks there.
}
BOOST_AUTO_TEST_CASE_TEMPLATE(segment_sites_test2, T, test_types) {
@@ -649,7 +649,6 @@
point_vec.push_back(point4);
test_voronoi_builder.init(point_vec, segm_vec);
test_voronoi_builder.run_sweepline();
-
// TODO(asydorchuk): Add output checks there.
}
@@ -721,6 +720,8 @@
point_vec.push_back(point1);
test_voronoi_builder.init(point_vec, segm_vec);
test_voronoi_builder.run_sweepline();
+
+ // TODO(asydorchuk): Add output checks there.
}
BOOST_AUTO_TEST_CASE_TEMPLATE(segment_site_test7, T, test_types) {
@@ -737,6 +738,8 @@
segm_vec.push_back(std::make_pair(point3, point4));
test_voronoi_builder.init(segm_vec);
test_voronoi_builder.run_sweepline();
+
+ // TODO(asydorchuk): Add output checks there.
}
BOOST_AUTO_TEST_CASE_TEMPLATE(segment_site_test8, T, test_types) {
@@ -754,4 +757,6 @@
segm_vec.push_back(std::make_pair(point4, point1));
test_voronoi_builder.init(segm_vec);
test_voronoi_builder.run_sweepline();
+
+ // TODO(asydorchuk): Add output checks there.
}
Modified: sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_segment/segment_voronoi_clipping_test.cpp
==============================================================================
--- sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_segment/segment_voronoi_clipping_test.cpp (original)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_segment/segment_voronoi_clipping_test.cpp 2010-10-14 11:25:19 EDT (Thu, 14 Oct 2010)
@@ -32,9 +32,8 @@
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);
+ Helper<T>::find_intersections(test_origin, test_direction1_1,
+ Helper<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);
@@ -42,23 +41,20 @@
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);
+ Helper<T>::find_intersections(test_origin, test_direction1_2,
+ Helper<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);
+ Helper<T>::find_intersections(test_origin, test_direction1_3,
+ Helper<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);
+ Helper<T>::find_intersections(test_origin, test_direction2,
+ Helper<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);
@@ -66,25 +62,22 @@
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);
+ Helper<T>::find_intersections(test_origin, test_direction3,
+ Helper<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);
+ Helper<T>::find_intersections(test_origin, test_direction4,
+ Helper<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);
+ Helper<T>::find_intersections(test_origin, test_direction5,
+ Helper<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);
@@ -102,9 +95,8 @@
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);
+ Helper<T>::find_intersections(test_origin, test_direction,
+ Helper<T>::SEGMENT, test_rect, intersections);
if (abs(i) >= 2 || abs(j) >= 2)
BOOST_CHECK_EQUAL(static_cast<int>(intersections.size()), 1);
else
@@ -126,9 +118,8 @@
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);
+ Helper<T>::find_intersections(test_origin, test_direction,
+ Helper<T>::SEGMENT, test_rect, intersections);
BOOST_CHECK_EQUAL(static_cast<int>(intersections.size()), 0);
}
}
@@ -146,9 +137,8 @@
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);
+ Helper<T>::find_intersections(test_origin, test_direction1,
+ Helper<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);
@@ -156,9 +146,8 @@
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);
+ Helper<T>::find_intersections(test_origin, test_direction2,
+ Helper<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);
@@ -166,9 +155,8 @@
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);
+ Helper<T>::find_intersections(test_origin, test_direction3,
+ Helper<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);
@@ -176,17 +164,15 @@
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);
+ Helper<T>::find_intersections(test_origin, test_direction4,
+ Helper<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);
+ Helper<T>::find_intersections(test_origin, test_direction5,
+ Helper<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);
@@ -206,9 +192,8 @@
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);
+ Helper<T>::find_intersections(test_origin, test_direction,
+ Helper<T>::RAY, test_rect, intersections);
if (i && j)
BOOST_CHECK_EQUAL(static_cast<int>(intersections.size()), 1);
}
@@ -227,9 +212,8 @@
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);
+ Helper<T>::find_intersections(test_origin, test_direction1,
+ Helper<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);
@@ -237,9 +221,8 @@
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);
+ Helper<T>::find_intersections(test_origin, test_direction2,
+ Helper<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);
@@ -247,9 +230,8 @@
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);
+ Helper<T>::find_intersections(test_origin, test_direction3,
+ Helper<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);
@@ -257,17 +239,15 @@
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);
+ Helper<T>::find_intersections(test_origin, test_direction4,
+ Helper<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);
+ Helper<T>::find_intersections(test_origin, test_direction5,
+ Helper<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);
@@ -287,9 +267,8 @@
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);
+ Helper<T>::find_intersections(test_origin, test_direction,
+ Helper<T>::LINE, test_rect, intersections);
if (i && j)
BOOST_CHECK_EQUAL(static_cast<int>(intersections.size()), 2);
}
Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk