Subject: [Boost-commit] svn:boost r66219 - in sandbox/SOC/2010/sweepline: boost/sweepline boost/sweepline/detail libs/sweepline/example libs/sweepline/example/input_data libs/sweepline/example/output_data libs/sweepline/test libs/sweepline/test/voronoi_segment
From: sydorchuk.andriy_at_[hidden]
Date: 2010-10-27 14:48:01
Author: asydorchuk
Date: 2010-10-27 14:47:57 EDT (Wed, 27 Oct 2010)
New Revision: 66219
URL: http://svn.boost.org/trac/boost/changeset/66219
Log:
Added DEBUG_ dependent tests.
Added tests that cover integer range coordinates.
Added few examples.
Renamed files.
Added:
sandbox/SOC/2010/sweepline/boost/sweepline/detail/voronoi_formation.hpp
- copied, changed from r66210, /sandbox/SOC/2010/sweepline/boost/sweepline/detail/voronoi_segment_formation.hpp
sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_builder.hpp
- copied, changed from r66210, /sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_segment_builder.hpp
sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_output.hpp
- copied, changed from r66210, /sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_segment_output.hpp
sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_sweepline.hpp
- copied, changed from r66210, /sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_segment_sweepline.hpp
sandbox/SOC/2010/sweepline/libs/sweepline/example/input_data/example_016.txt
- copied unchanged from r66210, /sandbox/SOC/2010/sweepline/libs/sweepline/example/input_data/example_016_random.txt
sandbox/SOC/2010/sweepline/libs/sweepline/example/input_data/example_017.txt
- copied unchanged from r66210, /sandbox/SOC/2010/sweepline/libs/sweepline/example/input_data/example_017_random.txt
sandbox/SOC/2010/sweepline/libs/sweepline/example/input_data/example_018.txt
- copied unchanged from r66210, /sandbox/SOC/2010/sweepline/libs/sweepline/example/input_data/example_018_random.txt
sandbox/SOC/2010/sweepline/libs/sweepline/example/input_data/example_019.txt
- copied unchanged from r66210, /sandbox/SOC/2010/sweepline/libs/sweepline/example/input_data/example_019_random.txt
sandbox/SOC/2010/sweepline/libs/sweepline/example/input_data/example_044.txt (contents, props changed)
sandbox/SOC/2010/sweepline/libs/sweepline/example/input_data/example_045.txt (contents, props changed)
sandbox/SOC/2010/sweepline/libs/sweepline/example/output_data/example_016.png
- copied unchanged from r66210, /sandbox/SOC/2010/sweepline/libs/sweepline/example/output_data/example_016_random.png
sandbox/SOC/2010/sweepline/libs/sweepline/example/output_data/example_017.png
- copied unchanged from r66210, /sandbox/SOC/2010/sweepline/libs/sweepline/example/output_data/example_017_random.png
sandbox/SOC/2010/sweepline/libs/sweepline/example/output_data/example_018.png
- copied unchanged from r66210, /sandbox/SOC/2010/sweepline/libs/sweepline/example/output_data/example_018_random.png
sandbox/SOC/2010/sweepline/libs/sweepline/example/output_data/example_019.png
- copied unchanged from r66210, /sandbox/SOC/2010/sweepline/libs/sweepline/example/output_data/example_019_random.png
sandbox/SOC/2010/sweepline/libs/sweepline/example/output_data/example_044.png (contents, props changed)
sandbox/SOC/2010/sweepline/libs/sweepline/example/output_data/example_045.png (contents, props changed)
sandbox/SOC/2010/sweepline/libs/sweepline/test/benchmark_test.cpp
- copied, changed from r66210, /sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_segment/segment_voronoi_benchmark_test.cpp
sandbox/SOC/2010/sweepline/libs/sweepline/test/circle_event_creation_test.cpp
- copied, changed from r66210, /sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_segment/segment_circle_event_creation_test.cpp
sandbox/SOC/2010/sweepline/libs/sweepline/test/clipping_test.cpp
- copied, changed from r66210, /sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_segment/segment_voronoi_clipping_test.cpp
sandbox/SOC/2010/sweepline/libs/sweepline/test/event_queue_test.cpp
- copied, changed from r66210, /sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_segment/segment_event_queue_test.cpp
sandbox/SOC/2010/sweepline/libs/sweepline/test/event_types_test.cpp
- copied, changed from r66210, /sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_segment/segment_event_types_test.cpp
sandbox/SOC/2010/sweepline/libs/sweepline/test/node_comparer_test.cpp
- copied, changed from r66210, /sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_segment/segment_node_comparer_test.cpp
sandbox/SOC/2010/sweepline/libs/sweepline/test/output_verification.hpp
- copied, changed from r66210, /sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_output_verification.hpp
sandbox/SOC/2010/sweepline/libs/sweepline/test/predicates_test.cpp
- copied, changed from r66210, /sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_segment/segment_predicates_test.cpp
sandbox/SOC/2010/sweepline/libs/sweepline/test/sweepline_test.cpp
- copied, changed from r66210, /sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_segment/segment_voronoi_builder_test.cpp
Removed:
sandbox/SOC/2010/sweepline/boost/sweepline/detail/voronoi_segment_formation.hpp
sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_segment_builder.hpp
sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_segment_output.hpp
sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_segment_sweepline.hpp
sandbox/SOC/2010/sweepline/libs/sweepline/example/input_data/example_016_random.txt
sandbox/SOC/2010/sweepline/libs/sweepline/example/input_data/example_017_random.txt
sandbox/SOC/2010/sweepline/libs/sweepline/example/input_data/example_018_random.txt
sandbox/SOC/2010/sweepline/libs/sweepline/example/input_data/example_019_random.txt
sandbox/SOC/2010/sweepline/libs/sweepline/example/output_data/example_016_random.png
sandbox/SOC/2010/sweepline/libs/sweepline/example/output_data/example_017_random.png
sandbox/SOC/2010/sweepline/libs/sweepline/example/output_data/example_018_random.png
sandbox/SOC/2010/sweepline/libs/sweepline/example/output_data/example_019_random.png
sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_output_verification.hpp
sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_segment/
Text files modified:
sandbox/SOC/2010/sweepline/boost/sweepline/detail/voronoi_formation.hpp | 519 ++++++++++++++++++++-------------------
sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_builder.hpp | 4
sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_output.hpp | 430 ++++++++++++++++----------------
sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_sweepline.hpp | 8
sandbox/SOC/2010/sweepline/libs/sweepline/example/voronoi_visualizer.cpp | 64 ++--
sandbox/SOC/2010/sweepline/libs/sweepline/test/Jamfile.v2 | 21
sandbox/SOC/2010/sweepline/libs/sweepline/test/benchmark_test.cpp | 20 +
sandbox/SOC/2010/sweepline/libs/sweepline/test/circle_event_creation_test.cpp | 60 ++--
sandbox/SOC/2010/sweepline/libs/sweepline/test/clipping_test.cpp | 10
sandbox/SOC/2010/sweepline/libs/sweepline/test/event_queue_test.cpp | 6
sandbox/SOC/2010/sweepline/libs/sweepline/test/event_types_test.cpp | 6
sandbox/SOC/2010/sweepline/libs/sweepline/test/node_comparer_test.cpp | 6
sandbox/SOC/2010/sweepline/libs/sweepline/test/output_verification.hpp | 2
sandbox/SOC/2010/sweepline/libs/sweepline/test/predicates_test.cpp | 32 --
sandbox/SOC/2010/sweepline/libs/sweepline/test/sweepline_test.cpp | 68 ++++
15 files changed, 655 insertions(+), 601 deletions(-)
Copied: sandbox/SOC/2010/sweepline/boost/sweepline/detail/voronoi_formation.hpp (from r66210, /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_formation.hpp 2010-10-27 14:47:57 EDT (Wed, 27 Oct 2010)
@@ -1,4 +1,4 @@
-// Boost sweepline/voronoi_segment_formation.hpp header file
+// Boost sweepline/voronoi_formation.hpp header file
// Copyright Andrii Sydorchuk 2010.
// Distributed under the Boost Software License, Version 1.0.
@@ -54,9 +54,10 @@
typedef T coordinate_type;
typedef point_2d<T> Point2D;
- site_event() : is_segment_(false),
- is_vertical_(true),
- is_inverse_(false) {}
+ site_event() :
+ is_segment_(false),
+ is_vertical_(true),
+ is_inverse_(false) {}
site_event(coordinate_type x, coordinate_type y, int index) :
point0_(x, y),
@@ -432,6 +433,10 @@
// GEOMETRY PREDICATES ////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////
+ bool abs_equal(double a, double b, double abs_error) {
+ return fabs(a - b) < abs_error;
+ }
+
// If two floating-point numbers in the same format are ordered (x < y), then
// they are ordered the same way when their bits are reinterpreted as
// sign-magnitude integers.
@@ -505,7 +510,7 @@
}
}
- template <typename T>
+ template <typename T>
kOrientation orientation_test(T dif_x1_, T dif_y1_, T dif_x2_, T dif_y2_) {
typedef unsigned long long ull;
ull dif_x1, dif_y1, dif_x2, dif_y2;
@@ -541,16 +546,16 @@
}
}
- template <typename T>
- kOrientation orientation_test(T value) {
- if (value == static_cast<T>(0.0))
- return COLINEAR;
- return (value < static_cast<T>(0.0)) ? RIGHT_ORIENTATION : LEFT_ORIENTATION;
- }
-
- template <typename T>
- T robust_cross_product(T a1_, T b1_, T a2_, T b2_) {
- typedef unsigned long long ull;
+ template <typename T>
+ kOrientation orientation_test(T value) {
+ if (value == static_cast<T>(0.0))
+ return COLINEAR;
+ return (value < static_cast<T>(0.0)) ? RIGHT_ORIENTATION : LEFT_ORIENTATION;
+ }
+
+ template <typename T>
+ T robust_cross_product(T a1_, T b1_, T a2_, T b2_) {
+ typedef unsigned long long ull;
ull a1, b1, a2, b2;
bool a1_plus, a2_plus, b1_plus, b2_plus;
INT_PREDICATE_CONVERT_65_BIT(a1_, a1, a1_plus);
@@ -558,12 +563,12 @@
INT_PREDICATE_CONVERT_65_BIT(a2_, a2, a2_plus);
INT_PREDICATE_CONVERT_65_BIT(b2_, b2, b2_plus);
- ull expr_l = a1 * b2;
+ ull expr_l = a1 * b2;
bool expr_l_plus = (a1_plus == b2_plus) ? true : false;
ull expr_r = b1 * a2;
bool expr_r_plus = (a2_plus == b1_plus) ? true : false;
- if (expr_l == 0)
+ if (expr_l == 0)
expr_l_plus = true;
if (expr_r == 0)
expr_r_plus = true;
@@ -571,20 +576,20 @@
if ((expr_l_plus == expr_r_plus) && (expr_l == expr_r))
return static_cast<T>(0.0);
- if (!expr_l_plus) {
+ if (!expr_l_plus) {
if (expr_r_plus)
return -static_cast<double>(expr_l) - static_cast<double>(expr_r);
else
- return (expr_l > expr_r) ? -static_cast<double>(expr_l - expr_r) :
- static_cast<double>(expr_r - expr_l);
+ return (expr_l > expr_r) ? -static_cast<double>(expr_l - expr_r) :
+ static_cast<double>(expr_r - expr_l);
} else {
if (!expr_r_plus)
return static_cast<double>(expr_l) + static_cast<double>(expr_r);
else
- return (expr_l < expr_r) ? -static_cast<double>(expr_r - expr_l) :
- static_cast<double>(expr_l - expr_r);
- }
- }
+ return (expr_l < expr_r) ? -static_cast<double>(expr_r - expr_l) :
+ static_cast<double>(expr_l - expr_r);
+ }
+ }
enum kPredicateResult {
LESS = -1,
@@ -973,10 +978,10 @@
static_cast<double>(site2.y());
double dif_y2 = static_cast<double>(site2.y()) -
static_cast<double>(site3.y());
- double orientation = robust_cross_product(dif_x1, dif_y1, dif_x2, dif_y2);
+ double orientation = robust_cross_product(dif_x1, dif_y1, dif_x2, dif_y2);
if (orientation_test(orientation) != RIGHT_ORIENTATION)
return false;
- orientation *= 2.0;
+ orientation *= 2.0;
double b1 = dif_x1 * (site1.x() + site2.x()) + dif_y1 * (site1.y() + site2.y());
double b2 = dif_x2 * (site2.x() + site3.x()) + dif_y2 * (site2.y() + site3.y());
@@ -1015,19 +1020,19 @@
double line_b = site3.get_point0().x() - site3.get_point1().x();
double vec_x = site2.y() - site1.y();
double vec_y = site1.x() - site2.x();
- double teta = robust_cross_product(line_a, line_b, -vec_y, vec_x);
- double A = robust_cross_product(line_a, line_b,
- site3.get_point1().y() - site1.y(),
- site1.x() - site3.get_point1().x());
- double B = robust_cross_product(line_a, line_b,
- site3.get_point1().y() - site2.y(),
- site2.x() - site3.get_point1().x());
- double denom = robust_cross_product(vec_x, vec_y, line_a, line_b);
- double t;
+ double teta = robust_cross_product(line_a, line_b, -vec_y, vec_x);
+ double A = robust_cross_product(line_a, line_b,
+ site3.get_point1().y() - site1.y(),
+ site1.x() - site3.get_point1().x());
+ double B = robust_cross_product(line_a, line_b,
+ site3.get_point1().y() - site2.y(),
+ site2.x() - site3.get_point1().x());
+ double denom = robust_cross_product(vec_x, vec_y, line_a, line_b);
+ double t;
if (orientation_test(denom) == COLINEAR) {
t = (teta * teta - 4.0 * A * B) / (4.0 * teta * (A + B));;
} else {
- double det = sqrt((teta * teta + denom * denom) * A * B);
+ double det = sqrt((teta * teta + denom * denom) * A * B);
if (segment_index == 2)
det = -det;
t = (teta * (A + B) + 2.0 * det) / (2.0 * denom * denom);
@@ -1037,8 +1042,8 @@
double radius = sqrt((c_x-site2.x())*(c_x-site2.x()) +
(c_y-site2.y())*(c_y-site2.y()));
- double lower_x = (site3.is_vertical() && site3.is_inverse()) ?
- site3.get_point0().x() : c_x + radius;
+ double lower_x = (site3.is_vertical() && site3.is_inverse()) ?
+ site3.get_point0().x() : c_x + radius;
c_event = make_circle_event<double>(c_x, c_y, lower_x);
return true;
}
@@ -1055,27 +1060,27 @@
if (site2.get_site_index() == site3.get_site_index()) {
return false;
}
- const point_2d<T> &site = site1.get_point0();
+ const point_2d<T> &site = site1.get_point0();
const point_2d<T> &segm_start1 = site2.get_point1(true);
const point_2d<T> &segm_end1 = site2.get_point0(true);
const point_2d<T> &segm_start2 = site3.get_point0(true);
const point_2d<T> &segm_end2 = site3.get_point1(true);
- if (point_index != 2) {
- if (orientation_test(segm_start1, segm_start2, site) == LEFT_ORIENTATION &&
- orientation_test(segm_end1, segm_end2, site) == LEFT_ORIENTATION &&
- orientation_test(segm_start1, segm_end2, site) == LEFT_ORIENTATION &&
- orientation_test(segm_end1, segm_start2, site) == LEFT_ORIENTATION) {
- return false;
- }
- } else {
- if ((orientation_test(segm_end1, segm_start1, segm_start2) != RIGHT_ORIENTATION &&
- orientation_test(segm_end1, segm_start1, segm_end2) != RIGHT_ORIENTATION) ||
- (orientation_test(segm_start2, segm_end2, segm_start1) != RIGHT_ORIENTATION &&
- orientation_test(segm_start2, segm_end2, segm_end1) != RIGHT_ORIENTATION)) {
- return false;
- }
- }
+ if (point_index != 2) {
+ if (orientation_test(segm_start1, segm_start2, site) == LEFT_ORIENTATION &&
+ orientation_test(segm_end1, segm_end2, site) == LEFT_ORIENTATION &&
+ orientation_test(segm_start1, segm_end2, site) == LEFT_ORIENTATION &&
+ orientation_test(segm_end1, segm_start2, site) == LEFT_ORIENTATION) {
+ return false;
+ }
+ } else {
+ if ((orientation_test(segm_end1, segm_start1, segm_start2) != RIGHT_ORIENTATION &&
+ orientation_test(segm_end1, segm_start1, segm_end2) != RIGHT_ORIENTATION) ||
+ (orientation_test(segm_start2, segm_end2, segm_start1) != RIGHT_ORIENTATION &&
+ orientation_test(segm_start2, segm_end2, segm_end1) != RIGHT_ORIENTATION)) {
+ return false;
+ }
+ }
double a1 = static_cast<double>(segm_end1.x() - segm_start1.x());
double b1 = static_cast<double>(segm_end1.y() - segm_start1.y());
@@ -1094,12 +1099,12 @@
b1 * ((static_cast<double>(segm_start1.y()) +
static_cast<double>(segm_start2.y())) * 0.5 -
static_cast<double>(site1.y()));
- double c = robust_cross_product(b1, a1, segm_start2.y() - segm_start1.y(),
- segm_start2.x() - segm_start1.x());
- double det = robust_cross_product(a1, b1, site1.x() - segm_start1.x(),
- site1.y() - segm_start1.y()) *
- robust_cross_product(b1, a1, site1.y() - segm_start2.y(),
- site1.x() - segm_start2.x());
+ double c = robust_cross_product(b1, a1, segm_start2.y() - segm_start1.y(),
+ segm_start2.x() - segm_start1.x());
+ double det = robust_cross_product(a1, b1, site1.x() - segm_start1.x(),
+ site1.y() - segm_start1.y()) *
+ robust_cross_product(b1, a1, site1.y() - segm_start2.y(),
+ site1.x() - segm_start2.x());
double t = ((point_index == 2) ? (-b + sqrt(det)) : (-b - sqrt(det))) / a;
double c_x = 0.5 * (static_cast<double>(segm_start1.x() + segm_start2.x())) + a1 * t;
double c_y = 0.5 * (static_cast<double>(segm_start1.y() + segm_start2.y())) + b1 * t;
@@ -1108,8 +1113,8 @@
return true;
} else {
double c1 = robust_cross_product(b1, a1, segm_end1.y(), segm_end1.x());
- double c2 = robust_cross_product(a2, b2, segm_end2.x(), segm_end2.y());
- double denom = robust_cross_product(b1, a1, b2, a2);
+ double c2 = robust_cross_product(a2, b2, segm_end2.x(), segm_end2.y());
+ double denom = robust_cross_product(b1, a1, b2, a2);
double intersection_x = (c1 * a2 + a1 * c2) / denom;
double intersection_y = (b1 * c2 + b2 * c1) / denom;
double sqr_sum1 = sqrt(a1 * a1 + b1 * b1);
@@ -1373,36 +1378,36 @@
///////////////////////////////////////////////////////////////////////////
// VORONOI OUTPUT /////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////
- 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) {}
- };
+ 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;
@@ -1416,8 +1421,8 @@
struct voronoi_edge {
typedef T coordinate_type;
typedef point_2d<T> Point2D;
- typedef voronoi_cell<coordinate_type> voronoi_cell_type;
- typedef voronoi_vertex<coordinate_type> voronoi_vertex_type;
+ 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;
@@ -1454,15 +1459,15 @@
typedef site_event<coordinate_type> site_event_type;
typedef circle_event<coordinate_type> circle_event_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 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 voronoi_edge<coordinate_type> edge_type;
typedef voronoi_edge_clipped<coordinate_type> clipped_edge_type;
@@ -1470,8 +1475,8 @@
typedef typename voronoi_edges_type::iterator edges_iterator_type;
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;
+ 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;
@@ -1536,14 +1541,14 @@
cell_records_.end(), voronoi_cell_type(site1, &edge1)));
num_cell_records_++;
voronoi_rect_ = BRect<coordinate_type>(site1.get_point0(), site1.get_point0());
- }
- cell_iterators_[site_index1]->num_incident_edges++;
+ }
+ cell_iterators_[site_index1]->num_incident_edges++;
// Update bounding rectangle.
- voronoi_rect_.update(site2.get_point0());
- if (site2.is_segment()) {
- voronoi_rect_.update(site2.get_point1());
- }
+ 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.
@@ -1567,7 +1572,7 @@
const circle_event_type &circle,
edge_type *edge12,
edge_type *edge23) {
- //voronoi_rect_.update(circle.get_center());
+ //voronoi_rect_.update(circle.get_center());
// Update counters.
num_vertex_records_++;
num_edges_++;
@@ -1688,36 +1693,43 @@
// Iterate over all edges and remove degeneracies.
while (edge_it != edges_.end()) {
edge_it1 = edge_it;
- std::advance(edge_it, 2);
+ std::advance(edge_it, 2);
if (edge_it1->start_point && edge_it1->end_point &&
- edge_it1->start_point->vertex == edge_it1->end_point->vertex) {
+ (almost_equal(edge_it1->start_point->vertex.x(),
+ edge_it1->end_point->vertex.x(), 1024) ||
+ abs_equal(edge_it1->start_point->vertex.x(),
+ edge_it1->end_point->vertex.x(), 1E-6)) &&
+ (almost_equal(edge_it1->start_point->vertex.y(),
+ edge_it1->end_point->vertex.y(), 1024) ||
+ abs_equal(edge_it1->start_point->vertex.y(),
+ edge_it1->end_point->vertex.y(), 1E-6))) {
// Decrease number of cell incident edges.
edge_it1->cell->num_incident_edges--;
edge_it1->twin->cell->num_incident_edges--;
// To guarantee N*lon(N) time we merge vertex with
// less incident edges to the one with more.
- if (edge_it1->cell->incident_edge == &(*edge_it1)) {
- if (edge_it1->cell->incident_edge == edge_it1->next) {
- edge_it1->cell->incident_edge = NULL;
- } else {
- edge_it1->cell->incident_edge = edge_it1->next;
- }
- }
- if (edge_it1->twin->cell->incident_edge == edge_it1->twin) {
- if (edge_it1->twin->cell->incident_edge == edge_it1->twin->next) {
- edge_it1->twin->cell->incident_edge = NULL;
- } else {
- edge_it1->twin->cell->incident_edge = edge_it1->twin->next;
- }
- }
+ if (edge_it1->cell->incident_edge == &(*edge_it1)) {
+ if (edge_it1->cell->incident_edge == edge_it1->next) {
+ edge_it1->cell->incident_edge = NULL;
+ } else {
+ edge_it1->cell->incident_edge = edge_it1->next;
+ }
+ }
+ if (edge_it1->twin->cell->incident_edge == edge_it1->twin) {
+ if (edge_it1->twin->cell->incident_edge == edge_it1->twin->next) {
+ edge_it1->twin->cell->incident_edge = NULL;
+ } else {
+ edge_it1->twin->cell->incident_edge = edge_it1->twin->next;
+ }
+ }
if (edge_it1->start_point->num_incident_edges >=
- edge_it1->end_point->num_incident_edges) {
+ edge_it1->end_point->num_incident_edges) {
simplify_edge(&(*edge_it1));
- } else {
+ } else {
simplify_edge(edge_it1->twin);
- }
+ }
// Remove zero length edges.
edges_.erase(edge_it1, edge_it);
@@ -1730,27 +1742,27 @@
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;
- if (cur_edge) {
- while (cur_edge->prev != NULL) {
- cur_edge = cur_edge->prev;
-
- // Terminate if this is not a boundary cell.
- if (cur_edge == cell_it->incident_edge)
- break;
- }
-
- // Rewind incident edge pointer to the leftmost edge for the boundary cells.
- cell_it->incident_edge = cur_edge;
-
- // Set up prev/next half-edge pointers for ray edges.
- if (cur_edge->prev == NULL) {
- edge_type *last_edge = cell_it->incident_edge;
- while (last_edge->next != NULL)
- last_edge = last_edge->next;
- last_edge->next = cur_edge;
- cur_edge->prev = last_edge;
- }
- }
+ if (cur_edge) {
+ while (cur_edge->prev != NULL) {
+ cur_edge = cur_edge->prev;
+
+ // Terminate if this is not a boundary cell.
+ if (cur_edge == cell_it->incident_edge)
+ break;
+ }
+
+ // Rewind incident edge pointer to the leftmost edge for the boundary cells.
+ cell_it->incident_edge = cur_edge;
+
+ // Set up prev/next half-edge pointers for ray edges.
+ if (cur_edge->prev == NULL) {
+ edge_type *last_edge = cell_it->incident_edge;
+ while (last_edge->next != NULL)
+ last_edge = last_edge->next;
+ last_edge->next = cur_edge;
+ cur_edge->prev = last_edge;
+ }
+ }
}
}
@@ -1770,7 +1782,7 @@
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);
}
@@ -1818,13 +1830,13 @@
vertex1->incident_edge = edge->rot_prev;
// Remove second vertex from the vertex records list.
- if (vertex1->voronoi_record_it != vertex2->voronoi_record_it) {
- vertex_records_.erase(vertex2->voronoi_record_it);
- num_vertex_records_--;
- }
+ if (vertex1->voronoi_record_it != vertex2->voronoi_record_it) {
+ vertex_records_.erase(vertex2->voronoi_record_it);
+ num_vertex_records_--;
+ }
}
- void clip(const BRect<coordinate_type> &brect,
+ void clip(const BRect<coordinate_type> &brect,
voronoi_output_clipped<coordinate_type> &clipped_output) {
if (!brect.is_valid())
return;
@@ -1835,10 +1847,10 @@
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;
+ 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();
@@ -1860,107 +1872,107 @@
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;
- }
+ // 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;
+ }
}
// 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_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;
// Update cell, next/prev pointers.
- if (cur_edge) {
- clipped_edge_type *prev = NULL;
- 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);
-
- // Update prev/next pointers.
- if (prev) {
- prev->next = new_cell.incident_edge;
- new_cell.incident_edge->prev = prev;
- }
- }
- }
- clipped_output.num_edge_records >>= 1;
- }
-
- 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();
- }
+ if (cur_edge) {
+ clipped_edge_type *prev = NULL;
+ 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);
+
+ // Update prev/next pointers.
+ if (prev) {
+ prev->next = new_cell.incident_edge;
+ new_cell.incident_edge->prev = prev;
+ }
+ }
+ }
+ clipped_output.num_edge_records >>= 1;
+ }
+
+ 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_;
@@ -1982,7 +1994,6 @@
} // boost
} // detail
-#undef INV_LOG_2
#undef INT_PREDICATE_COMPUTE_DIFFERENCE
#undef INT_PREDICATE_CONVERT_65_BIT
#undef INT_PREDICATE_AVOID_CANCELLATION
Deleted: sandbox/SOC/2010/sweepline/boost/sweepline/detail/voronoi_segment_formation.hpp
==============================================================================
--- sandbox/SOC/2010/sweepline/boost/sweepline/detail/voronoi_segment_formation.hpp 2010-10-27 14:47:57 EDT (Wed, 27 Oct 2010)
+++ (empty file)
@@ -1,1990 +0,0 @@
-// Boost sweepline/voronoi_segment_formation.hpp header file
-
-// Copyright Andrii Sydorchuk 2010.
-// Distributed under the Boost Software License, Version 1.0.
-// (See accompanying file LICENSE_1_0.txt or copy at
-// http://www.boost.org/LICENSE_1_0.txt)
-
-// See http://www.boost.org for updates, documentation, and revision history.
-
-#ifndef BOOST_SWEEPLINE_VORONOI_SEGMENT_FORMATION
-#define BOOST_SWEEPLINE_VORONOI_SEGMENT_FORMATION
-
-#define INT_PREDICATE_COMPUTE_DIFFERENCE(a, b, res, sign) \
- 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<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);
-
-namespace boost {
-namespace sweepline {
-namespace detail {
-
- ///////////////////////////////////////////////////////////////////////////
- // VORONOI EVENT TYPES ////////////////////////////////////////////////////
- ///////////////////////////////////////////////////////////////////////////
-
- template <typename T>
- struct beach_line_node;
-
- template <typename T>
- struct beach_line_node_data;
-
- template <typename BeachLineNode>
- struct node_comparer;
-
- enum kOrientation {
- RIGHT_ORIENTATION = -1,
- COLINEAR = 0,
- LEFT_ORIENTATION = 1,
- };
-
- // Site event type.
- // Occurs when sweepline sweeps over one of the initial sites.
- // Contains index of a site among the other sorted sites.
- template <typename T>
- struct site_event {
- public:
- typedef T coordinate_type;
- typedef point_2d<T> Point2D;
-
- site_event() : is_segment_(false),
- is_vertical_(true),
- is_inverse_(false) {}
-
- site_event(coordinate_type x, coordinate_type y, int index) :
- point0_(x, y),
- site_index_(index),
- is_segment_(false),
- is_vertical_(true),
- is_inverse_(false) {}
-
- site_event(const Point2D &point, int index) :
- point0_(point),
- site_index_(index),
- is_segment_(false),
- is_vertical_(true),
- is_inverse_(false) {}
-
- site_event(const Point2D &point1, const Point2D &point2, int index) :
- point0_(point1),
- point1_(point2),
- site_index_(index),
- is_segment_(true),
- is_inverse_(false) {
- if (point0_ > point1_)
- (std::swap)(point0_, point1_);
- is_vertical_ = (point0_.x() == point1_.x());
- }
-
- bool operator==(const site_event &s_event) const {
- return (point0_ == s_event.point0_) &&
- ((!is_segment_ && !s_event.is_segment_) ||
- (is_segment_ && s_event.is_segment_ && (point1_ == s_event.point1_)));
- }
-
- bool operator!=(const site_event &s_event) const {
- return !((*this) == s_event);
- }
-
- // All the sites are sorted due to coordinates of the first point.
- // Point sites preceed vertical segment sites with the same first point.
- // Point sites and vertical segments preceed not vertical segments with
- // the same x coordinate of the first point.
- // Non vertical segments with the same first point are sorted counterclockwise.
- bool operator<(const site_event &s_event) const {
- // If first points have different x coordinates, compare them.
- if (this->point0_.x() != s_event.point0_.x())
- return this->point0_.x() < s_event.point0_.x();
-
- if (!(this->is_segment_)) {
- if (!s_event.is_segment_) {
- return this->point0_.y() < s_event.point0_.y();
- }
- if (s_event.is_vertical_) {
- return this->point0_.y() <= s_event.point0_.y();
- }
- return true;
- } else {
- if (!s_event.is_segment_ || s_event.is_vertical_) {
- if (this->is_vertical_) {
- return this->point0_.y() < s_event.point0_.y();
- }
- return false;
- }
- if (this->is_vertical_)
- return true;
- if (this->point0_.y() != s_event.point0_.y())
- return this->point0_.y() < s_event.point0_.y();
- // Sort by angle.
- return orientation_test(this->point1_, this->point0_, s_event.point1_) ==
- LEFT_ORIENTATION;
- }
- }
-
- bool operator<=(const site_event &s_event) const {
- return !(s_event < (*this));
- }
-
- bool operator>(const site_event &s_event) const {
- return s_event < (*this);
- }
-
- bool operator>=(const site_event &s_event) const {
- return !((*this) < s_event);
- }
-
- coordinate_type x(bool oriented = false) const {
- if (!oriented)
- return point0_.x();
- return is_inverse_ ? point1_.x() : point0_.x();
- }
-
- coordinate_type y(bool oriented = false) const {
- if (!oriented)
- return point0_.y();
- return is_inverse_ ? point1_.y() : point0_.y();
- }
-
- coordinate_type x0(bool oriented = false) const {
- if (!oriented)
- return point0_.x();
- return is_inverse_ ? point1_.x() : point0_.x();
- }
-
- coordinate_type y0(bool oriented = false) const {
- if (!oriented)
- return point0_.y();
- return is_inverse_ ? point1_.y() : point0_.y();
- }
-
- coordinate_type x1(bool oriented = false) const {
- if (!oriented)
- return point1_.x();
- return is_inverse_ ? point0_.x() : point1_.x();
- }
-
- coordinate_type y1(bool oriented = false) const {
- if (!oriented)
- return point1_.y();
- return is_inverse_ ? point0_.y() : point1_.y();
- }
-
- const Point2D &get_point0(bool oriented = false) const {
- if (!oriented)
- return point0_;
- return is_inverse_ ? point1_ : point0_;
- }
-
- const Point2D &get_point1(bool oriented = false) const {
- if (!oriented)
- return point1_;
- return is_inverse_ ? point0_ : point1_;
- }
-
- void set_site_index(int index) {
- site_index_ = index;
- }
-
- void set_inverse() {
- is_inverse_ ^= true;
- }
-
- int get_site_index() const {
- return site_index_;
- }
-
- bool is_segment() const {
- return is_segment_;
- }
-
- bool is_vertical() const {
- return is_vertical_;
- }
-
- bool is_inverse() const {
- return is_inverse_;
- }
-
- private:
- Point2D point0_;
- Point2D point1_;
- int site_index_;
- bool is_segment_;
- bool is_vertical_;
- bool is_inverse_;
- };
-
- template <typename T>
- site_event<T> make_site_event(T x, T y, int index) {
- return site_event<T>(x, y, index);
- }
-
- template <typename T>
- site_event<T> make_site_event(const point_2d<T> &point, int index) {
- return site_event<T>(point, index);
- }
-
- template <typename T>
- site_event<T> make_site_event(const point_2d<T> &point1,
- const point_2d<T> &point2, int index) {
- return site_event<T>(point1, point2, index);
- }
-
- // Circle event type. Occurs when sweepline sweeps over the bottom point of
- // the voronoi circle (with center at the bisectors intersection point).
- // Circle event contains circle center, lowest x coordinate, event state and
- // iterator to the corresponding bisectors.
- template <typename T>
- struct circle_event {
- public:
- typedef T coordinate_type;
- typedef point_2d<T> Point2D;
- typedef beach_line_node<coordinate_type> Key;
- typedef beach_line_node_data<coordinate_type> Value;
- typedef node_comparer<Key> NodeComparer;
- typedef typename std::map< Key, Value, NodeComparer >::iterator beach_line_iterator;
-
- circle_event() : is_active_(true) {}
-
- circle_event(coordinate_type c_x, coordinate_type c_y, coordinate_type lower_x) :
- center_(c_x, c_y), lower_x_(lower_x), is_active_(true) {}
-
- circle_event(const Point2D ¢er, coordinate_type lower_x) :
- center_(center), lower_x_(lower_x), is_active_(true) {}
-
- circle_event(const circle_event& c_event) {
- center_ = c_event.center_;
- lower_x_ = c_event.lower_x_;
- bisector_node_ = c_event.bisector_node_;
- is_active_ = c_event.is_active_;
- }
-
- void operator=(const circle_event& c_event) {
- center_ = c_event.center_;
- lower_x_ = c_event.lower_x_;
- bisector_node_ = c_event.bisector_node_;
- is_active_ = c_event.is_active_;
- }
-
- bool operator==(const circle_event &c_event) const {
- return (center_.y() == c_event.y()) &&
- (lower_x_ == c_event.lower_x_);
- }
-
- bool operator!=(const circle_event &c_event) const {
- return !((*this) == c_event);
- }
-
- bool operator<(const circle_event &c_event) const {
- if (lower_x_ != c_event.lower_x_)
- return lower_x_ < c_event.lower_x_;
- return center_.y() < c_event.y();
- }
-
- bool operator<=(const circle_event &c_event) const {
- return !(c_event < (*this));
- }
-
- bool operator>(const circle_event &c_event) const {
- return c_event < (*this);
- }
-
- bool operator>=(const circle_event &c_event) const {
- return !((*this) < c_event);
- }
-
- // Compares bottom voronoi circle point with site event point.
- // If circle point is less than site point return -1.
- // If circle point is equal to site point return 0.
- // If circle point is greater than site point return 1.
- int compare(const site_event<coordinate_type> &s_event) const {
- if (s_event.x() != lower_x_) {
- return (lower_x_ < s_event.x()) ? -1 : 1;
- }
- if (s_event.y() != center_.y())
- return (center_.y() < s_event.y()) ? -1 : 1;
- return 0;
- }
-
- coordinate_type x() const {
- return center_.x();
- }
-
- coordinate_type y() const {
- return center_.y();
- }
-
- const Point2D &get_center() const {
- return center_;
- }
-
- const coordinate_type &get_lower_x() const {
- return lower_x_;
- }
-
- void set_bisector(beach_line_iterator iterator) {
- bisector_node_ = iterator;
- }
-
- void deactivate() {
- is_active_ = false;
- }
-
- const beach_line_iterator &get_bisector() const {
- return bisector_node_;
- }
-
- bool is_active() const {
- return is_active_;
- }
-
- private:
- Point2D center_;
- coordinate_type lower_x_;
- beach_line_iterator bisector_node_;
- bool is_active_;
- };
-
- template <typename T>
- circle_event<T> make_circle_event(T c_x, T c_y, T lower_x) {
- return circle_event<T>(c_x, c_y, lower_x);
- }
-
- template <typename T>
- circle_event<T> make_circle_event(point_2d<T> center, T lower_x) {
- return circle_event<T>(center, lower_x);
- }
-
- ///////////////////////////////////////////////////////////////////////////
- // VORONOI CIRCLE EVENTS QUEUE ////////////////////////////////////////////
- ///////////////////////////////////////////////////////////////////////////
-
- // Event queue data structure, processes circle events.
- template <typename T>
- class circle_events_queue {
- public:
- typedef T coordinate_type;
- typedef point_2d<T> Point2D;
- typedef circle_event<T> circle_event_type;
- typedef typename std::list<circle_event_type>::iterator circle_event_type_it;
-
- circle_events_queue() {}
-
- void reset() {
- while (!circle_events_.empty())
- circle_events_.pop();
- circle_events_list_.clear();
- }
-
- bool empty() {
- remove_not_active_events();
- return circle_events_.empty();
- }
-
- const circle_event_type &top() {
- remove_not_active_events();
- return (*circle_events_.top());
- }
-
- void pop() {
- circle_event_type_it temp_it = circle_events_.top();
- circle_events_.pop();
- circle_events_list_.erase(temp_it);
- }
-
- circle_event_type_it push(const circle_event_type &c_event) {
- circle_events_list_.push_front(c_event);
- circle_events_.push(circle_events_list_.begin());
- return circle_events_list_.begin();
- }
-
- private:
- struct comparison {
- bool operator() (const circle_event_type_it &node1,
- const circle_event_type_it &node2) const {
- return (*node1) > (*node2);
- }
- };
-
- void remove_not_active_events() {
- while (!circle_events_.empty() && !circle_events_.top()->is_active())
- pop();
- }
-
- std::priority_queue< circle_event_type_it,
- std::vector<circle_event_type_it>,
- comparison > circle_events_;
- std::list<circle_event_type> circle_events_list_;
-
- //Disallow copy constructor and operator=
- circle_events_queue(const circle_events_queue&);
- void operator=(const circle_events_queue&);
- };
-
- ///////////////////////////////////////////////////////////////////////////
- // GEOMETRY PREDICATES ////////////////////////////////////////////////////
- ///////////////////////////////////////////////////////////////////////////
-
- // If two floating-point numbers in the same format are ordered (x < y), then
- // they are ordered the same way when their bits are reinterpreted as
- // sign-magnitude integers.
- bool almost_equal(double a, double b, long long maxUlps) {
- long long ll_a, ll_b;
- // Reinterpret double bits as long long.
- memcpy(&ll_a, &a, sizeof(double));
- memcpy(&ll_b, &b, sizeof(double));
-
- // Positive 0.0 is integer zero. Negative 0.0 is 0x8000000000000000.
- // Map negative zero to an integer zero representation - making it
- // identical to positive zero - and it makes it so that the smallest
- // negative number is represented by negative one, and downwards from there.
- if (ll_a < 0)
- ll_a = 0x8000000000000000LL - ll_a;
- if (ll_b < 0)
- ll_b = 0x8000000000000000LL - ll_b;
-
- // Compare long long representations of input values.
- // Difference in 1 Ulp is equivalent to a relative error of between
- // 1/4,000,000,000,000,000 and 1/8,000,000,000,000,000.
- long long dif = ll_a - ll_b;
- return (dif <= maxUlps) && (dif >= -maxUlps);
- }
-
- // TODO(asydorchuk): Make templates specification for integer coordinate type,
- // as it is actually working with integer input.
- template <typename T>
- kOrientation orientation_test(const point_2d<T> &point1,
- const point_2d<T> &point2,
- const point_2d<T> &point3) {
- typedef long long ll;
- typedef unsigned long long ull;
- ull dif_x1, dif_x2, dif_y1, dif_y2;
- bool dif_x1_plus, dif_x2_plus, dif_y1_plus, dif_y2_plus;
- INT_PREDICATE_COMPUTE_DIFFERENCE(static_cast<ll>(point1.x()),
- static_cast<ll>(point2.x()),
- dif_x1, dif_x1_plus);
- INT_PREDICATE_COMPUTE_DIFFERENCE(static_cast<ll>(point2.x()),
- static_cast<ll>(point3.x()),
- dif_x2, dif_x2_plus);
- INT_PREDICATE_COMPUTE_DIFFERENCE(static_cast<ll>(point1.y()),
- static_cast<ll>(point2.y()),
- dif_y1, dif_y1_plus);
- INT_PREDICATE_COMPUTE_DIFFERENCE(static_cast<ll>(point2.y()),
- static_cast<ll>(point3.y()),
- dif_y2, dif_y2_plus);
- ull expr_l = dif_x1 * dif_y2;
- bool expr_l_plus = (dif_x1_plus == dif_y2_plus) ? true : false;
- ull expr_r = dif_x2 * dif_y1;
- bool expr_r_plus = (dif_x2_plus == dif_y1_plus) ? true : false;
-
- if (expr_l == 0)
- expr_l_plus = true;
- if (expr_r == 0)
- expr_r_plus = true;
-
- if ((expr_l_plus == expr_r_plus) && (expr_l == expr_r))
- return COLINEAR;
-
- if (!expr_l_plus) {
- if (expr_r_plus)
- return RIGHT_ORIENTATION;
- else
- return (expr_l > expr_r) ? RIGHT_ORIENTATION : LEFT_ORIENTATION;
- } else {
- if (!expr_r_plus)
- return LEFT_ORIENTATION;
- else
- return (expr_l < expr_r) ? RIGHT_ORIENTATION : LEFT_ORIENTATION;
- }
- }
-
- template <typename T>
- kOrientation orientation_test(T dif_x1_, T dif_y1_, T dif_x2_, T dif_y2_) {
- typedef unsigned long long ull;
- ull dif_x1, dif_y1, dif_x2, dif_y2;
- bool dif_x1_plus, dif_x2_plus, dif_y1_plus, dif_y2_plus;
- INT_PREDICATE_CONVERT_65_BIT(dif_x1_, dif_x1, dif_x1_plus);
- INT_PREDICATE_CONVERT_65_BIT(dif_y1_, dif_y1, dif_y1_plus);
- INT_PREDICATE_CONVERT_65_BIT(dif_x2_, dif_x2, dif_x2_plus);
- INT_PREDICATE_CONVERT_65_BIT(dif_y2_, dif_y2, dif_y2_plus);
-
- ull expr_l = dif_x1 * dif_y2;
- bool expr_l_plus = (dif_x1_plus == dif_y2_plus) ? true : false;
- ull expr_r = dif_x2 * dif_y1;
- bool expr_r_plus = (dif_x2_plus == dif_y1_plus) ? true : false;
-
- if (expr_l == 0)
- expr_l_plus = true;
- if (expr_r == 0)
- expr_r_plus = true;
-
- if ((expr_l_plus == expr_r_plus) && (expr_l == expr_r))
- return COLINEAR;
-
- if (!expr_l_plus) {
- if (expr_r_plus)
- return RIGHT_ORIENTATION;
- else
- return (expr_l > expr_r) ? RIGHT_ORIENTATION : LEFT_ORIENTATION;
- } else {
- if (!expr_r_plus)
- return LEFT_ORIENTATION;
- else
- return (expr_l < expr_r) ? RIGHT_ORIENTATION : LEFT_ORIENTATION;
- }
- }
-
- template <typename T>
- kOrientation orientation_test(T value) {
- if (value == static_cast<T>(0.0))
- return COLINEAR;
- return (value < static_cast<T>(0.0)) ? RIGHT_ORIENTATION : LEFT_ORIENTATION;
- }
-
- template <typename T>
- T robust_cross_product(T a1_, T b1_, T a2_, T b2_) {
- typedef unsigned long long ull;
- ull a1, b1, a2, b2;
- bool a1_plus, a2_plus, b1_plus, b2_plus;
- INT_PREDICATE_CONVERT_65_BIT(a1_, a1, a1_plus);
- INT_PREDICATE_CONVERT_65_BIT(b1_, b1, b1_plus);
- INT_PREDICATE_CONVERT_65_BIT(a2_, a2, a2_plus);
- INT_PREDICATE_CONVERT_65_BIT(b2_, b2, b2_plus);
-
- ull expr_l = a1 * b2;
- bool expr_l_plus = (a1_plus == b2_plus) ? true : false;
- ull expr_r = b1 * a2;
- bool expr_r_plus = (a2_plus == b1_plus) ? true : false;
-
- if (expr_l == 0)
- expr_l_plus = true;
- if (expr_r == 0)
- expr_r_plus = true;
-
- if ((expr_l_plus == expr_r_plus) && (expr_l == expr_r))
- return static_cast<T>(0.0);
-
- if (!expr_l_plus) {
- if (expr_r_plus)
- return -static_cast<double>(expr_l) - static_cast<double>(expr_r);
- else
- return (expr_l > expr_r) ? -static_cast<double>(expr_l - expr_r) :
- static_cast<double>(expr_r - expr_l);
- } else {
- if (!expr_r_plus)
- return static_cast<double>(expr_l) + static_cast<double>(expr_r);
- else
- return (expr_l < expr_r) ? -static_cast<double>(expr_r - expr_l) :
- static_cast<double>(expr_l - expr_r);
- }
- }
-
- enum kPredicateResult {
- LESS = -1,
- UNDEFINED = 0,
- MORE = 1,
- };
-
- // Returns true if horizontal line going through new site intersects
- // right arc at first, else returns false. If horizontal line goes
- // through intersection point of the given two arcs returns false also.
- // Used during nodes comparison.
- // Let x0 be sweepline coordinate, left site coordinates be (x1, y1),
- // right site coordinates be (x2, y2). Equations of the arcs will be:
- // x1(y) = ((y - y1)^2 + x1^2 - x0^2) / (2*(x1 - x0));
- // x2(y) = ((y - y2)^2 + x2^2 - x0^2) / (2*(x2 - x0)).
- // Horizontal line going throught site (x*, y*) intersects second arc
- // at first if x2(y*) > x1(y*) or:
- // (x0-x2)*(x0-x1)*(x1-x2) + (x0-x2)*(y*-y1)^2 < (x0-x1)*(y*-y2)^2.
- template <typename T>
- kPredicateResult fast_less_predicate(const point_2d<T> &left_point,
- const point_2d<T> &right_point,
- const point_2d<T> &new_point) {
- double fast_a1 = static_cast<double>(new_point.x()) - static_cast<double>(left_point.x());
- double fast_a2 = static_cast<double>(new_point.x()) - static_cast<double>(right_point.x());
- double fast_b1 = static_cast<double>(new_point.y()) - static_cast<double>(left_point.y());
- double fast_b2 = static_cast<double>(new_point.y()) - static_cast<double>(right_point.y());
- double fast_c = static_cast<double>(left_point.x()) - static_cast<double>(right_point.x());
- double fast_left_expr = fast_a1 * fast_b2 * fast_b2;
- double fast_right_expr = fast_a2 * fast_b1 * fast_b1;
-
- // Avoid cancellation.
- INT_PREDICATE_AVOID_CANCELLATION(fast_a1 * fast_a2 * fast_c,
- fast_left_expr, fast_right_expr);
- if (!almost_equal(fast_left_expr, fast_right_expr, 5))
- return (fast_left_expr < fast_right_expr) ? LESS : MORE;
- return UNDEFINED;
- }
-
- template <typename T>
- bool less_predicate(const point_2d<T> &left_point,
- const point_2d<T> &right_point,
- const point_2d<T> &new_point) {
- kPredicateResult fast_res = fast_less_predicate(left_point, right_point, new_point);
- if (fast_res != UNDEFINED)
- return (fast_res == LESS);
-
- typedef long long ll;
- typedef unsigned long long ull;
- ull a1, a2, b1, b2, b1_sqr, b2_sqr, l_expr, r_expr;
- bool l_expr_plus, r_expr_plus;
-
- // a1 and a2 are greater than zero.
- a1 = static_cast<ull>(static_cast<ll>(new_point.x()) -
- static_cast<ll>(left_point.x()));
- a2 = static_cast<ull>(static_cast<ll>(new_point.x()) -
- static_cast<ll>(right_point.x()));
-
- // We don't need to know signs of b1 and b2, because we use their squared values.
- INT_PREDICATE_COMPUTE_DIFFERENCE(static_cast<ll>(new_point.y()),
- static_cast<ll>(left_point.y()),
- b1, l_expr_plus);
- INT_PREDICATE_COMPUTE_DIFFERENCE(static_cast<ll>(new_point.y()),
- static_cast<ll>(right_point.y()),
- b2, l_expr_plus);
- b1_sqr = b1 * b1;
- b2_sqr = b2 * b2;
- ull b1_sqr_mod = b1_sqr % a1;
- ull b2_sqr_mod = b2_sqr % a2;
-
- // Compute left expression.
- INT_PREDICATE_COMPUTE_DIFFERENCE(static_cast<ll>(left_point.x()),
- static_cast<ll>(right_point.x()),
- l_expr, l_expr_plus);
- if (b2_sqr_mod * a1 < b1_sqr_mod * a2) {
- if (!l_expr_plus)
- l_expr++;
- else if (l_expr != 0)
- l_expr--;
- else {
- l_expr++;
- l_expr_plus = false;
- }
- }
-
- // Compute right expression.
- INT_PREDICATE_COMPUTE_DIFFERENCE(b1_sqr / a1, b2_sqr / a2, r_expr, r_expr_plus);
-
- // Compare left and right expressions.
- if (!l_expr_plus && r_expr_plus)
- return true;
- if (l_expr_plus && !r_expr_plus)
- return false;
- if (l_expr_plus && r_expr_plus)
- return l_expr < r_expr;
- return l_expr > r_expr;
- }
-
- template <typename T>
- kPredicateResult fast_less_predicate(point_2d<T> site_point, site_event<T> segment_site,
- point_2d<T> new_point, bool reverse_order) {
- typedef long long ll;
- typedef unsigned long long ull;
- if (orientation_test(segment_site.get_point0(true), segment_site.get_point1(true),
- new_point) != RIGHT_ORIENTATION) {
- return (!segment_site.is_inverse()) ? LESS : MORE;
- }
-
- const point_2d<T> &segment_start = segment_site.get_point0();
- const point_2d<T> &segment_end = segment_site.get_point1();
- ll dif_x = static_cast<ll>(new_point.x()) - static_cast<ll>(site_point.x());
- ll dif_y = static_cast<ll>(new_point.y()) - static_cast<ll>(site_point.y());
- ll a = static_cast<ll>(segment_end.x()) - static_cast<ll>(segment_start.x());
- ll b = static_cast<ll>(segment_end.y()) - static_cast<ll>(segment_start.y());
-
- if (a == 0) {
- if (new_point.y() < site_point.y() && !reverse_order)
- return MORE;
- else if (new_point.y() > site_point.y() && reverse_order)
- return LESS;
- return UNDEFINED;
- } else {
- kOrientation orientation = orientation_test(a, b, dif_x, dif_y);
- if ((orientation == COLINEAR) ||
- (!segment_site.is_inverse() ^ (orientation == RIGHT_ORIENTATION))) {
- if (!segment_site.is_inverse())
- return reverse_order ? LESS : UNDEFINED;
- return reverse_order ? UNDEFINED : MORE;
- }
- }
-
- // dif_x and dif_y are integers, so there will be no cancellation issues.
- double fast_left_expr = static_cast<double>(a) *
- static_cast<double>(dif_y + dif_x) *
- static_cast<double>(dif_y - dif_x);
- double fast_right_expr = static_cast<double>(b<<1) *
- static_cast<double>(dif_x) *
- static_cast<double>(dif_y);
- if (!(almost_equal(fast_left_expr, fast_right_expr, 4))) {
- if (segment_site.is_inverse() ^ (fast_left_expr > fast_right_expr) ^ reverse_order)
- return reverse_order ? LESS : MORE;
- return UNDEFINED;
- }
-
- ull a_rob, a_sign, b_rob, b_sign, dif_x_rob, dif_x_sign, dif_y_rob, dif_y_sign;
- INT_PREDICATE_CONVERT_65_BIT(a, a_rob, a_sign);
- INT_PREDICATE_CONVERT_65_BIT(b, b_rob, b_sign);
- INT_PREDICATE_CONVERT_65_BIT(dif_x, dif_x_rob, dif_x_sign);
- INT_PREDICATE_CONVERT_65_BIT(dif_y, dif_y_rob, dif_y_sign);
-
- ull dif_x_sqr = dif_x_rob * dif_x_rob;
- ull dif_y_sqr = dif_y_rob * dif_y_rob;
- ull left_expr_div = dif_y_sqr / dif_x_sqr + 1;
- ull left_expr_mod = dif_y_sqr % dif_x_sqr;
-
- ull right_expr_denom = a_rob * dif_x_rob;
- ull right_expr = b_rob * dif_y_rob;
- ull right_expr_div = right_expr / right_expr_denom;
- ull right_expr_mod = right_expr % right_expr_denom;
-
- bool comparison_result;
- if ((b_sign != dif_y_sign) && right_expr_div)
- comparison_result = true;
- else {
- if (b_sign != dif_y_sign && right_expr_mod)
- right_expr_mod = right_expr_denom - right_expr_mod;
- else
- right_expr_div++;
- bool left_expr_odd = (left_expr_div % 2 == 1);
- left_expr_div >>= 1;
- if (left_expr_div != right_expr_div) {
- comparison_result = (left_expr_div > right_expr_div);
- } else {
- ull temp_right = right_expr_denom - right_expr_mod;
- if (temp_right > right_expr_mod) {
- if (left_expr_odd)
- comparison_result = true;
- else
- right_expr_mod <<= 1;
- } else {
- if (!left_expr_odd)
- comparison_result = false;
- else
- right_expr_mod = right_expr_mod - temp_right;
- }
- left_expr_div = left_expr_mod / dif_x_rob;
- right_expr_div = right_expr_mod / a_rob;
- if (left_expr_div != right_expr_div)
- comparison_result = (left_expr_div > right_expr_div);
- else {
- left_expr_mod = left_expr_mod % dif_x_rob;
- right_expr_mod = right_expr_mod % a_rob;
- comparison_result = (left_expr_mod * a_rob > right_expr_mod * dif_x_rob);
- }
- }
- }
-
- if (segment_site.is_inverse() ^ comparison_result ^ reverse_order)
- return reverse_order ? LESS : MORE;
- return UNDEFINED;
- }
-
-#ifdef USE_MULTI_PRECISION_LIBRARY
- template<typename T>
- bool mpz_less_predicate(point_2d<T> segment_start, point_2d<T> segment_end,
- point_2d<T> site_point, point_2d<T> new_point, bool reverse_order) {
- mpz_class segment_start_x, segment_start_y, segment_end_x, segment_end_y,
- site_point_x, site_point_y, new_point_x, new_point_y;
- segment_start_x = static_cast<int>(segment_start.x());
- segment_start_y = static_cast<int>(segment_start.y());
- segment_end_x = static_cast<int>(segment_end.x());
- segment_end_y = static_cast<int>(segment_end.y());
- site_point_x = static_cast<int>(site_point.x());
- site_point_y = static_cast<int>(site_point.y());
- new_point_x = static_cast<int>(new_point.x());
- new_point_y = static_cast<int>(new_point.y());
-
- mpz_class dif_x, dif_y, a, b, mul1, mul2, temp, left_expr, right_expr;
- dif_x = new_point_x - site_point_x;
- dif_y = new_point_y - site_point_y;
- a = segment_end_x - segment_start_x;
- b = segment_end_y - segment_start_y;
- mul1 = new_point_x - segment_end_x;
- mul2 = new_point_y - segment_end_y;
- temp = dif_x * dif_x + dif_y * dif_y;
- left_expr = (a * a + b * b) * temp * temp;
- right_expr = (2.0 * dif_x * (b * mul1 - a * mul2) - b * temp);
- right_expr = right_expr * right_expr;
-
- return (!reverse_order) ? (left_expr > right_expr) : (left_expr < right_expr);
- }
-#endif
-
- // Returns true if horizontal line going through new site intersects
- // right arc at first, else returns false. If horizontal line goes
- // through intersection point of the given two arcs returns false also.
- // Used during nodes comparison.
- // If reverse order is false we are comparing (point, segment) intersection
- // point and new point, else (segment, point) intersection point.
- // (point, segment) and (segment, point) are two distinct points, except
- // case of vertical segment.
- template <typename T>
- bool less_predicate(point_2d<T> site_point, site_event<T> segment_site,
- point_2d<T> new_point, bool reverse_order) {
- kPredicateResult fast_res = fast_less_predicate(
- site_point, segment_site, new_point, reverse_order);
- if (fast_res != UNDEFINED) {
- return (fast_res == LESS);
- }
-
- const point_2d<T> &segment_start = segment_site.get_point0();
- const point_2d<T> &segment_end = segment_site.get_point1();
- double dif_x = static_cast<double>(new_point.x()) -
- static_cast<double>(site_point.x());
- double dif_y = static_cast<double>(new_point.y()) -
- static_cast<double>(site_point.y());
- double a = static_cast<double>(segment_end.x()) -
- static_cast<double>(segment_start.x());
- double b = static_cast<double>(segment_end.y()) -
- static_cast<double>(segment_start.y());
-
- double mul1 = static_cast<double>(new_point.x()) - static_cast<double>(segment_end.x());
- double mul2 = static_cast<double>(new_point.y()) - static_cast<double>(segment_end.y());
- double temp = dif_x * dif_x + dif_y * dif_y;
- double a_sqr = a * a;
- double b_sqr = b * b;
- double left_expr = (a_sqr * temp + (4.0 * dif_x * mul1) * b_sqr) * temp;
- double right_expr = (4.0 * dif_x * dif_x) * ((mul1 * mul1) * b_sqr + (mul2 * mul2) * a_sqr);
- double common_expr = (4.0 * dif_x * a) * (b * mul2);
- INT_PREDICATE_AVOID_CANCELLATION(common_expr * temp, right_expr, left_expr);
- INT_PREDICATE_AVOID_CANCELLATION(common_expr * (2.0 * dif_x * mul1), left_expr, right_expr);
-
- if (!almost_equal(left_expr, right_expr, 18)) {
- if (!reverse_order)
- return left_expr > right_expr;
- return left_expr < right_expr;
- }
-
-#ifndef USE_MULTI_PRECISION_LIBRARY
- return (!reverse_order) ? (left_expr > right_expr) : (left_expr < right_expr);
-#else
- return mpz_less_predicate(segment_start, segment_end, site_point,
- new_point, reverse_order);
-#endif
- }
-
- template <typename T>
- 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) == LEFT_ORIENTATION;
- }
-
- const point_2d<T> segment1_start = left_site.get_point1();
- const point_2d<T> segment1_end = left_site.get_point0();
- const point_2d<T> segment2_start = right_site.get_point1();
- const point_2d<T> segment2_end = right_site.get_point0();
- double intersection_x1 = 0.0;
- double intersection_x2 = 0.0;
-
- double a1 = static_cast<double>(segment1_end.x()) -
- static_cast<double>(segment1_start.x());
- if (a1 == 0.0) {
- // Avoid cancellation.
- intersection_x2 += (static_cast<double>(new_point.x()) -
- static_cast<double>(segment1_end.x())) * 0.5;
- } else {
- double b1 = static_cast<double>(segment1_end.y()) -
- static_cast<double>(segment1_start.y());
- double c1 = b1 * (static_cast<double>(new_point.x()) -
- static_cast<double>(segment1_start.x())) +
- a1 * segment1_start.y();
- double mul1 = sqrt(a1 * a1 + b1 * b1);
- if (left_site.is_inverse()) {
- if (b1 >= 0.0) {
- mul1 = 1.0 / (b1 + mul1);
- } else {
- mul1 = (-b1 + mul1) / (a1 * a1);
- }
- } else {
- if (b1 >= 0.0) {
- mul1 = (-b1 - mul1) / (a1 * a1);
- } else {
- mul1 = 1.0 / (b1 - mul1);
- }
- }
- INT_PREDICATE_AVOID_CANCELLATION(a1 * mul1 * static_cast<double>(new_point.y()),
- intersection_x1, intersection_x2);
- INT_PREDICATE_AVOID_CANCELLATION(-c1 * mul1, intersection_x1, intersection_x2);
- }
-
- double a2 = static_cast<double>(segment2_end.x()) -
- static_cast<double>(segment2_start.x());
- if (a2 == 0.0) {
- // Avoid cancellation.
- intersection_x1 += (static_cast<double>(new_point.x()) -
- static_cast<double>(segment2_end.x())) * 0.5;
- } else {
- double b2 = static_cast<double>(segment2_end.y()) -
- static_cast<double>(segment2_start.y());
- double c2 = b2 * (static_cast<double>(new_point.x()) -
- static_cast<double>(segment2_start.x())) +
- a2 * segment2_start.y();
- double mul2 = sqrt(a2 * a2 + b2 * b2);
- if (right_site.is_inverse()) {
- if (b2 >= 0.0) {
- mul2 = 1.0 / (b2 + mul2);
- } else {
- mul2 = (-b2 + mul2) / (a2 * a2);
- }
- } else {
- if (b2 >= 0.0) {
- mul2 = (-b2 - mul2) / (a2 * a2);
- } else {
- mul2 = 1.0 / (b2 - mul2);
- }
- }
- INT_PREDICATE_AVOID_CANCELLATION(a2 * static_cast<double>(new_point.y()) * mul2,
- intersection_x2, intersection_x1);
- INT_PREDICATE_AVOID_CANCELLATION(-c2 * mul2, intersection_x2, intersection_x1);
- }
-
- if (!almost_equal(intersection_x1, intersection_x2, 20)) {
- return intersection_x1 < intersection_x2;
- }
-
- // TODO(asydorchuk): Add mpl support there.
- return intersection_x1 < intersection_x2;
- }
-
- ///////////////////////////////////////////////////////////////////////////
- // CIRCLE EVENTS CREATION /////////////////////////////////////////////////
- ///////////////////////////////////////////////////////////////////////////
-
- // Create circle event from three point sites.
- // TODO (asydorchuk): make precision optimizations.
- template <typename T>
- static bool create_circle_event_ppp(const site_event<T> &site1,
- const site_event<T> &site2,
- const site_event<T> &site3,
- circle_event<T> &c_event) {
- double dif_x1 = static_cast<double>(site1.x()) -
- static_cast<double>(site2.x());
- double dif_x2 = static_cast<double>(site2.x()) -
- static_cast<double>(site3.x());
- double dif_y1 = static_cast<double>(site1.y()) -
- static_cast<double>(site2.y());
- double dif_y2 = static_cast<double>(site2.y()) -
- static_cast<double>(site3.y());
- double orientation = robust_cross_product(dif_x1, dif_y1, dif_x2, dif_y2);
- if (orientation_test(orientation) != RIGHT_ORIENTATION)
- return false;
- orientation *= 2.0;
- double b1 = dif_x1 * (site1.x() + site2.x()) + dif_y1 * (site1.y() + site2.y());
- double b2 = dif_x2 * (site2.x() + site3.x()) + dif_y2 * (site2.y() + site3.y());
-
- // Create new circle event.
- double c_x = (b1*dif_y2 - b2*dif_y1) / orientation;
- double c_y = (b2*dif_x1 - b1*dif_x2) / orientation;
- double radius = sqrt((c_x-site2.x())*(c_x-site2.x()) +
- (c_y-site2.y())*(c_y-site2.y()));
- c_event = make_circle_event<double>(c_x, c_y, c_x + radius);
- return true;
- }
-
- // Create circle event from two point sites and one segment site.
- // TODO (asydorchuk): make_precision optimizations.
- template <typename T>
- static bool create_circle_event_pps(const site_event<T> &site1,
- const site_event<T> &site2,
- const site_event<T> &site3,
- int segment_index,
- circle_event<T> &c_event) {
- if (segment_index != 2) {
- if (orientation_test(site3.get_point0(), site1.get_point0(),
- site2.get_point0()) != RIGHT_ORIENTATION &&
- detail::orientation_test(site3.get_point1(), site1.get_point0(),
- site2.get_point0()) != RIGHT_ORIENTATION)
- return false;
- } else {
- if (orientation_test(site1.get_point0(), site3.get_point0(),
- site2.get_point0()) != RIGHT_ORIENTATION &&
- detail::orientation_test(site1.get_point0(), site3.get_point1(),
- site2.get_point0()) != RIGHT_ORIENTATION)
- return false;
- }
-
- double line_a = site3.get_point1().y() - site3.get_point0().y();
- double line_b = site3.get_point0().x() - site3.get_point1().x();
- double vec_x = site2.y() - site1.y();
- double vec_y = site1.x() - site2.x();
- double teta = robust_cross_product(line_a, line_b, -vec_y, vec_x);
- double A = robust_cross_product(line_a, line_b,
- site3.get_point1().y() - site1.y(),
- site1.x() - site3.get_point1().x());
- double B = robust_cross_product(line_a, line_b,
- site3.get_point1().y() - site2.y(),
- site2.x() - site3.get_point1().x());
- double denom = robust_cross_product(vec_x, vec_y, line_a, line_b);
- double t;
- if (orientation_test(denom) == COLINEAR) {
- t = (teta * teta - 4.0 * A * B) / (4.0 * teta * (A + B));;
- } else {
- double det = sqrt((teta * teta + denom * denom) * A * B);
- if (segment_index == 2)
- det = -det;
- t = (teta * (A + B) + 2.0 * det) / (2.0 * denom * denom);
- }
- double c_x = 0.5 * (site1.x() + site2.x()) + t * vec_x;
- double c_y = 0.5 * (site1.y() + site2.y()) + t * vec_y;
-
- double radius = sqrt((c_x-site2.x())*(c_x-site2.x()) +
- (c_y-site2.y())*(c_y-site2.y()));
- double lower_x = (site3.is_vertical() && site3.is_inverse()) ?
- site3.get_point0().x() : c_x + radius;
- c_event = make_circle_event<double>(c_x, c_y, lower_x);
- return true;
- }
-
- // Create circle event from one point site and two segment sites.
- // TODO (asydorchuk): make precision optimizations.
- template <typename T>
- static bool create_circle_event_pss(const site_event<T> &site1,
- const site_event<T> &site2,
- const site_event<T> &site3,
- int point_index,
- circle_event<T> &c_event) {
- // Intersection check.
- if (site2.get_site_index() == site3.get_site_index()) {
- return false;
- }
- const point_2d<T> &site = site1.get_point0();
- const point_2d<T> &segm_start1 = site2.get_point1(true);
- const point_2d<T> &segm_end1 = site2.get_point0(true);
- const point_2d<T> &segm_start2 = site3.get_point0(true);
- const point_2d<T> &segm_end2 = site3.get_point1(true);
-
- if (point_index != 2) {
- if (orientation_test(segm_start1, segm_start2, site) == LEFT_ORIENTATION &&
- orientation_test(segm_end1, segm_end2, site) == LEFT_ORIENTATION &&
- orientation_test(segm_start1, segm_end2, site) == LEFT_ORIENTATION &&
- orientation_test(segm_end1, segm_start2, site) == LEFT_ORIENTATION) {
- return false;
- }
- } else {
- if ((orientation_test(segm_end1, segm_start1, segm_start2) != RIGHT_ORIENTATION &&
- orientation_test(segm_end1, segm_start1, segm_end2) != RIGHT_ORIENTATION) ||
- (orientation_test(segm_start2, segm_end2, segm_start1) != RIGHT_ORIENTATION &&
- orientation_test(segm_start2, segm_end2, segm_end1) != RIGHT_ORIENTATION)) {
- return false;
- }
- }
-
- double a1 = static_cast<double>(segm_end1.x() - segm_start1.x());
- double b1 = static_cast<double>(segm_end1.y() - segm_start1.y());
- double a2 = static_cast<double>(segm_end2.x() - segm_start2.x());
- double b2 = static_cast<double>(segm_end2.y() - segm_start2.y());
-
- kOrientation segm_orient = orientation_test(
- static_cast<long long>(a1), static_cast<long long>(b1),
- static_cast<long long>(a2), static_cast<long long>(b2));
-
- if (segm_orient == COLINEAR) {
- double a = a1 * a1 + b1 * b1;
- double b = a1 * ((static_cast<double>(segm_start1.x()) +
- static_cast<double>(segm_start2.x())) * 0.5 -
- static_cast<double>(site1.x())) +
- b1 * ((static_cast<double>(segm_start1.y()) +
- static_cast<double>(segm_start2.y())) * 0.5 -
- static_cast<double>(site1.y()));
- double c = robust_cross_product(b1, a1, segm_start2.y() - segm_start1.y(),
- segm_start2.x() - segm_start1.x());
- double det = robust_cross_product(a1, b1, site1.x() - segm_start1.x(),
- site1.y() - segm_start1.y()) *
- robust_cross_product(b1, a1, site1.y() - segm_start2.y(),
- site1.x() - segm_start2.x());
- double t = ((point_index == 2) ? (-b + sqrt(det)) : (-b - sqrt(det))) / a;
- double c_x = 0.5 * (static_cast<double>(segm_start1.x() + segm_start2.x())) + a1 * t;
- double c_y = 0.5 * (static_cast<double>(segm_start1.y() + segm_start2.y())) + b1 * t;
- double radius = 0.5 * fabs(c) / sqrt(a);
- c_event = make_circle_event<double>(c_x, c_y, c_x + radius);
- return true;
- } else {
- double c1 = robust_cross_product(b1, a1, segm_end1.y(), segm_end1.x());
- double c2 = robust_cross_product(a2, b2, segm_end2.x(), segm_end2.y());
- double denom = robust_cross_product(b1, a1, b2, a2);
- double intersection_x = (c1 * a2 + a1 * c2) / denom;
- double intersection_y = (b1 * c2 + b2 * c1) / denom;
- double sqr_sum1 = sqrt(a1 * a1 + b1 * b1);
- double sqr_sum2 = sqrt(a2 * a2 + b2 * b2);
- double vec_x = a1 * sqr_sum2 + a2 * sqr_sum1;
- double vec_y = b1 * sqr_sum2 + b2 * sqr_sum1;
- double dx = intersection_x - site1.get_point0().x();
- double dy = intersection_y - site1.get_point0().y();
- double a = robust_cross_product(a1, b1, -b2, a2) + sqr_sum1 * sqr_sum2;
- double b = dx * vec_x + dy * vec_y;
- double det = fabs(-2.0 * a * (b1 * dx - a1 * dy) * (b2 * dx - a2 * dy));
- double t = ((point_index == 2) ? (-b + sqrt(det)) : (-b - sqrt(det))) / (a * a);
- double c_x = intersection_x + vec_x * t;
- double c_y = intersection_y + vec_y * t;
- double radius = fabs(denom * t);
- c_event = make_circle_event<double>(c_x, c_y, c_x + radius);
- return true;
- }
- }
-
- // Create circle event from three segment sites.
- template <typename T>
- static bool create_circle_event_sss(const site_event<T> &site1,
- const site_event<T> &site2,
- const site_event<T> &site3,
- circle_event<T> &c_event) {
- if (site1.get_site_index() == site2.get_site_index() ||
- site2.get_site_index() == site3.get_site_index()) {
- return false;
- }
- double a1 = static_cast<double>(site1.x1(true) - site1.x0(true));
- double b1 = static_cast<double>(site1.y1(true) - site1.y0(true));
- double c1 = b1 * static_cast<double>(site1.x0(true)) -
- a1 * static_cast<double>(site1.y0(true));
- double a2 = static_cast<double>(site2.x1(true) - site2.x0(true));
- double b2 = static_cast<double>(site2.y1(true) - site2.y0(true));
- double c2 = b2 * static_cast<double>(site2.x0(true)) -
- a2 * static_cast<double>(site2.y0(true));
- double a3 = static_cast<double>(site3.x1(true) - site3.x0(true));
- double b3 = static_cast<double>(site3.y1(true) - site3.y0(true));
- double c3 = b3 * static_cast<double>(site3.x0(true)) -
- a3 * static_cast<double>(site3.y0(true));
- double sqr_sum1 = sqrt(a1 * a1 + b1 * b1);
- double sqr_sum2 = sqrt(a2 * a2 + b2 * b2);
- double sqr_sum3 = sqrt(a3 * a3 + b3 * b3);
- double vec_a1 = -a1 * sqr_sum2 + a2 * sqr_sum1;
- double vec_b1 = -b1 * sqr_sum2 + b2 * sqr_sum1;
- double vec_c1 = -c1 * sqr_sum2 + c2 * sqr_sum1;
- double vec_a2 = -a2 * sqr_sum3 + a3 * sqr_sum2;
- double vec_b2 = -b2 * sqr_sum3 + b3 * sqr_sum2;
- double vec_c2 = -c2 * sqr_sum3 + c3 * sqr_sum2;
- double det = vec_a1 * vec_b2 - vec_b1 * vec_a2;
- double c_x = (vec_a1 * vec_c2 - vec_c1 * vec_a2) / det;
- double c_y = (vec_b1 * vec_c2 - vec_c1 * vec_b2) / det;
- double radius = fabs(-b2 * c_x + a2 * c_y + c2) / sqr_sum2;
- c_event = make_circle_event<double>(c_x, c_y, c_x + radius);
- return true;
- }
-
- ///////////////////////////////////////////////////////////////////////////
- // VORONOI BEACH LINE TYPES ///////////////////////////////////////////////
- ///////////////////////////////////////////////////////////////////////////
-
- // Represents bisector made by two arcs that correspond to the left and
- // right sites. Arc is defined as curve with points equidistant from the
- // site and from the sweepline.
- // Let sweepline sweep from left to right and it's current coordinate
- // be x0, site coordinates be (x1, y1). In this case equation of the arc
- // may be written as: (x-x0)^2 = (x-x1)^2 + (y-y1)^2, or
- // x = ((y - y1)^2 + x1^2 - x0^2) / (2*(x1 - x0)).
- // In general case two arcs will create two different bisectors. That's why
- // the order of arcs is important to define unique bisector.
- template <typename T>
- struct beach_line_node {
- public:
- typedef T coordinate_type;
- typedef point_2d<T> Point2D;
- typedef site_event<T> site_event_type;
-
- beach_line_node() {}
-
- // Constructs degenerate bisector, used to search arc that is above
- // given site. The input to the constructor is the site event point.
- explicit beach_line_node(const site_event_type &new_point) {
- left_site_ = new_point;
- right_site_ = new_point;
- }
-
- // Constructs new bisector. The input to the constructor is two sites
- // that create bisector. The order of sites is important.
- beach_line_node(const site_event_type &left_point,
- const site_event_type &right_point) {
- left_site_ = left_point;
- right_site_ = right_point;
- }
-
- // Returns the left site of the bisector.
- const site_event_type &get_left_site() const {
- return left_site_;
- }
-
- // Returns the right site of the bisector.
- const site_event_type &get_right_site() const {
- return right_site_;
- }
-
- void set_left_site(const site_event_type &site) {
- left_site_ = site;
- }
-
- void set_right_site(const site_event_type &site) {
- right_site_ = site;
- }
-
- void set_left_site_inverse() {
- left_site_.set_inverse();
- }
-
- void set_right_site_inverse() {
- right_site_.set_inverse();
- }
-
- coordinate_type get_comparison_x() const {
- return (left_site_.get_site_index() >= right_site_.get_site_index()) ?
- left_site_.x() : right_site_.x();
- }
-
- std::pair<coordinate_type, int> get_comparison_y(bool is_new_node = true) const {
- if (left_site_.get_site_index() == right_site_.get_site_index()) {
- return std::make_pair(left_site_.y(), 0);
- }
- if (left_site_.get_site_index() > right_site_.get_site_index()) {
- if (!is_new_node && left_site_.is_segment() && left_site_.is_vertical()) {
- return std::make_pair(left_site_.y1(), 1);
- }
- return std::make_pair(left_site_.y(), 1);
- }
- return std::make_pair(right_site_.y(), -1);
- }
-
- int get_comparison_index() const {
- return (left_site_.get_site_index() > right_site_.get_site_index()) ?
- left_site_.get_site_index() : right_site_.get_site_index();
- }
-
- const site_event_type &get_comparison_site() const {
- return (left_site_.get_site_index() >= right_site_.get_site_index()) ?
- left_site_ : right_site_;
- }
-
- bool less(const Point2D &new_site) const {
- if (!left_site_.is_segment()) {
- return (!right_site_.is_segment()) ? less_pp(new_site) : less_ps(new_site);
- } else {
- return (!right_site_.is_segment()) ? less_sp(new_site) : less_ss(new_site);
- }
- }
-
- bool less_pp(const Point2D &new_site) const {
- if (left_site_.x() > right_site_.x()) {
- if (new_site.y() <= left_site_.y())
- return false;
- return less_predicate(left_site_.get_point0(), right_site_.get_point0(), new_site);
- } else if (left_site_.x() < right_site_.x()) {
- if (new_site.y() >= right_site_.y())
- return true;
- return less_predicate(left_site_.get_point0(), right_site_.get_point0(), new_site);
- } else {
- return left_site_.y() + right_site_.y() <
- static_cast<coordinate_type>(2.0) * new_site.y();
- }
- }
-
- bool less_ps(const Point2D &new_site) const {
- return less_predicate(left_site_.get_point0(), right_site_, new_site, false);
- }
-
- bool less_sp(const Point2D &new_site) const {
- return less_predicate(right_site_.get_point0(), left_site_, new_site, true);
- }
-
- bool less_ss(const Point2D &new_site) const {
- return less_predicate(left_site_, right_site_, new_site);
- }
-
- private:
- site_event_type left_site_;
- site_event_type right_site_;
- };
-
- template <typename T>
- 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 {
- 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(voronoi_edge<T> *new_edge) :
- edge(new_edge),
- contains_circle_event(false) {}
-
- void activate_circle_event(typename circle_events_queue<T>::circle_event_type_it it) {
- circle_event_it = it;
- contains_circle_event = true;
- }
-
- void deactivate_circle_event() {
- if (contains_circle_event)
- circle_event_it->deactivate();
- contains_circle_event = false;
- }
- };
-
- template <typename BeachLineNode>
- struct node_comparer {
- public:
- typedef typename BeachLineNode::coordinate_type coordinate_type;
-
- // Compares nodes in the balanced binary search tree. Nodes are
- // compared based on the y coordinates of the arcs intersection points.
- // Nodes with less y coordinate of the intersection point go first.
- // Comparison is only called during site events processing. That's why
- // one of the nodes will always lie on the sweepline. Comparison won't
- // work fine for nodes situated above sweepline.
- bool operator() (const BeachLineNode &node1,
- const BeachLineNode &node2) const {
- // Get x coordinate of the righmost site from both nodes.
- coordinate_type node1_x = node1.get_comparison_x();
- coordinate_type node2_x = node2.get_comparison_x();
-
- if (node1_x < node2_x) {
- return node1.less(node2.get_comparison_site().get_point0());
- } else if (node1_x > node2_x) {
- return !node2.less(node1.get_comparison_site().get_point0());
- } else {
- if (node1.get_comparison_index() == node2.get_comparison_index()) {
- return node1.get_comparison_y() < node2.get_comparison_y();
- } else if (node1.get_comparison_index() < node2.get_comparison_index()) {
- std::pair<coordinate_type, int> y1 = node1.get_comparison_y(false);
- std::pair<coordinate_type, int> y2 = node2.get_comparison_y();
- if (y1.first != y2.first) {
- return y1.first < y2.first;
- }
- return (!node1.get_comparison_site().is_segment()) ? (y1.second < 0) : false;
- } else {
- std::pair<coordinate_type, int> y1 = node1.get_comparison_y();
- std::pair<coordinate_type, int> y2 = node2.get_comparison_y(false);
- if (y1.first != y2.first) {
- return y1.first < y2.first;
- }
- return (!node2.get_comparison_site().is_segment()) ? (y2.second > 0) : true;
- }
- }
- }
- };
-
- ///////////////////////////////////////////////////////////////////////////
- // VORONOI OUTPUT /////////////////////////////////////////////////////////
- ///////////////////////////////////////////////////////////////////////////
- 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;
- // 2) pointers to start/end vertices of half-edge;
- // 3) pointers to previous/next half-edges(CCW);
- // 4) pointers to previous/next half-edges rotated
- // around start point;
- // 5) pointer to twin half-edge;
- // 6) pointer to clipped edge during clipping.
- template <typename T>
- struct voronoi_edge {
- typedef T coordinate_type;
- typedef point_2d<T> Point2D;
- 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;
-
- voronoi_edge() :
- cell(NULL),
- start_point(NULL),
- end_point(NULL),
- prev(NULL),
- next(NULL),
- rot_prev(NULL),
- rot_next(NULL),
- twin(NULL),
- clipped_edge(NULL) {}
- };
-
- // Voronoi output data structure based on the half-edges.
- // Contains vector of voronoi cells, doubly linked list of
- // voronoi vertices and voronoi edges.
- template <typename T>
- class voronoi_output {
- public:
- typedef T coordinate_type;
- typedef point_2d<T> Point2D;
- typedef site_event<coordinate_type> site_event_type;
- typedef circle_event<coordinate_type> circle_event_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 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;
-
- 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;
- num_edges_ = 0;
- num_vertex_records_ = 0;
- }
-
- void init(int num_sites) {
- cell_iterators_.reserve(num_sites);
- num_cell_records_ = 0;
- num_edges_ = 0;
- num_vertex_records_ = 0;
- }
-
- void reset() {
- cell_iterators_.clear();
- cell_records_.clear();
- vertex_records_.clear();
- edges_.clear();
-
- num_cell_records_ = 0;
- num_edges_ = 0;
- num_vertex_records_ = 0;
- }
-
- // Update voronoi output in case of single site input.
- void process_single_site(const site_event_type &site) {
- // Update counters.
- num_cell_records_++;
-
- // Update bounding rectangle.
- voronoi_rect_ = BRect<coordinate_type>(site.get_point0(), site.get_point0());
-
- // Update cell records.
- cell_records_.push_back(voronoi_cell_type(site, NULL));
- }
-
- // Inserts new half-edge into the output data structure during site
- // event processing. Takes as input left and right sites of the new
- // beach line node and returns pointer to the new half-edge.
- edge_type *insert_new_edge(const site_event_type &site1,
- const site_event_type &site2) {
- // Update counters.
- num_cell_records_++;
- num_edges_++;
-
- // Get indices of sites.
- int site_index1 = site1.get_site_index();
- int site_index2 = site2.get_site_index();
-
- // Create new half-edge that belongs to the first site.
- edges_.push_back(edge_type());
- edge_type &edge1 = edges_.back();
-
- // Create new half-edge that belongs to the second site.
- edges_.push_back(edge_type());
- edge_type &edge2 = edges_.back();
-
- // Add initial cell during first edge insertion.
- if (cell_records_.empty()) {
- cell_iterators_.push_back(cell_records_.insert(
- cell_records_.end(), voronoi_cell_type(site1, &edge1)));
- num_cell_records_++;
- voronoi_rect_ = BRect<coordinate_type>(site1.get_point0(), site1.get_point0());
- }
- cell_iterators_[site_index1]->num_incident_edges++;
-
- // Update bounding rectangle.
- 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_cell_type(site2, &edge2)));
- cell_records_.back().num_incident_edges++;
-
- // Update pointers to cells.
- edge1.cell = &(*cell_iterators_[site_index1]);
- edge2.cell = &(*cell_iterators_[site_index2]);
-
- // Update twin pointers.
- edge1.twin = &edge2;
- edge2.twin = &edge1;
-
- return &edge1;
- }
-
- edge_type *insert_new_edge(const site_event_type &site1,
- const site_event_type &site3,
- const circle_event_type &circle,
- edge_type *edge12,
- edge_type *edge23) {
- //voronoi_rect_.update(circle.get_center());
- // Update counters.
- num_vertex_records_++;
- num_edges_++;
-
- // Update bounding rectangle.
- //voronoi_rect_.update(circle.get_center());
-
- // Add new voronoi vertex with point at center of the circle.
- vertex_records_.push_back(voronoi_vertex_type(circle.get_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--;
-
- // Update two input bisectors and their twin half-edges with
- // new voronoi vertex.
- edge12->start_point = &new_vertex;
- edge12->twin->end_point = &new_vertex;
- edge23->start_point = &new_vertex;
- edge23->twin->end_point = &new_vertex;
-
- // Add new half-edge.
- edges_.push_back(edge_type());
- edge_type &new_edge1 = edges_.back();
- new_edge1.cell = &(*cell_iterators_[site1.get_site_index()]);
- new_edge1.cell->num_incident_edges++;
- new_edge1.end_point = &new_vertex;
-
- // Add new half-edge.
- edges_.push_back(edge_type());
- edge_type &new_edge2 = edges_.back();
- new_edge2.cell = &(*cell_iterators_[site3.get_site_index()]);
- new_edge2.cell->num_incident_edges++;
- new_edge2.start_point = &new_vertex;
-
- // Update twin pointers of the new half-edges.
- new_edge1.twin = &new_edge2;
- new_edge2.twin = &new_edge1;
-
- // Update voronoi prev/next pointers of all half-edges incident
- // to the new voronoi vertex.
- edge12->prev = &new_edge1;
- new_edge1.next = edge12;
- edge12->twin->next = edge23;
- edge23->prev = edge12->twin;
- edge23->twin->next = &new_edge2;
- new_edge2.prev = edge23->twin;
-
- // Update voronoi vertices incident edges pointers.
- edge12->rot_next = &new_edge2;
- new_edge2.rot_prev = edge12;
- edge23->rot_next = edge12;
- edge12->rot_prev = edge23;
- new_edge2.rot_next = edge23;
- edge23->rot_prev = &new_edge2;
-
- return &new_edge1;
- }
-
- const voronoi_cells_type &get_cell_records() const {
- return cell_records_;
- }
-
- const voronoi_vertices_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_;
- }
-
- const BRect<coordinate_type> &get_bounding_rectangle() const {
- return voronoi_rect_;
- }
-
- void simplify() {
- edges_iterator_type edge_it1;
- edges_iterator_type edge_it = edges_.begin();
-
- // Return in case of collinear sites input.
- if (num_vertex_records_ == 0) {
- if (edge_it == edges_.end())
- return;
-
- edge_type *edge1 = &(*edge_it);
- edge1->next = edge1->prev = edge1;
- edge_it++;
- edge1 = &(*edge_it);
- edge_it++;
-
- while (edge_it != edges_.end()) {
- edge_type *edge2 = &(*edge_it);
- edge_it++;
-
- edge1->next = edge1->prev = edge2;
- edge2->next = edge2->prev = edge1;
-
- edge1 = &(*edge_it);
- edge_it++;
- }
-
- edge1->next = edge1->prev = edge1;
- return;
- }
-
- // Iterate over all edges and remove degeneracies.
- while (edge_it != edges_.end()) {
- edge_it1 = edge_it;
- std::advance(edge_it, 2);
-
- if (edge_it1->start_point && edge_it1->end_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--;
-
- // To guarantee N*lon(N) time we merge vertex with
- // less incident edges to the one with more.
- if (edge_it1->cell->incident_edge == &(*edge_it1)) {
- if (edge_it1->cell->incident_edge == edge_it1->next) {
- edge_it1->cell->incident_edge = NULL;
- } else {
- edge_it1->cell->incident_edge = edge_it1->next;
- }
- }
- if (edge_it1->twin->cell->incident_edge == edge_it1->twin) {
- if (edge_it1->twin->cell->incident_edge == edge_it1->twin->next) {
- edge_it1->twin->cell->incident_edge = NULL;
- } else {
- edge_it1->twin->cell->incident_edge = edge_it1->twin->next;
- }
- }
- if (edge_it1->start_point->num_incident_edges >=
- edge_it1->end_point->num_incident_edges) {
- simplify_edge(&(*edge_it1));
- } else {
- simplify_edge(edge_it1->twin);
- }
-
- // Remove zero length edges.
- edges_.erase(edge_it1, edge_it);
- num_edges_--;
- }
- }
-
- // Make some post processing.
- 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;
- if (cur_edge) {
- while (cur_edge->prev != NULL) {
- cur_edge = cur_edge->prev;
-
- // Terminate if this is not a boundary cell.
- if (cur_edge == cell_it->incident_edge)
- break;
- }
-
- // Rewind incident edge pointer to the leftmost edge for the boundary cells.
- cell_it->incident_edge = cur_edge;
-
- // Set up prev/next half-edge pointers for ray edges.
- if (cur_edge->prev == NULL) {
- edge_type *last_edge = cell_it->incident_edge;
- while (last_edge->next != NULL)
- last_edge = last_edge->next;
- last_edge->next = cur_edge;
- cur_edge->prev = last_edge;
- }
- }
- }
- }
-
- void clip(voronoi_output_clipped<coordinate_type> &clipped_output) {
- coordinate_type x_len = (voronoi_rect_.x_max - voronoi_rect_.x_min);
- coordinate_type y_len = (voronoi_rect_.y_max - voronoi_rect_.y_min);
- coordinate_type x_mid = (voronoi_rect_.x_max + voronoi_rect_.x_min) /
- static_cast<coordinate_type>(2);
- coordinate_type y_mid = (voronoi_rect_.y_max + voronoi_rect_.y_min) /
- static_cast<coordinate_type>(2);
-
- coordinate_type offset = x_len;
- if (offset < y_len)
- offset = y_len;
-
- 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);
- clip(new_brect, clipped_output);
- }
-
- private:
- // Simplify degenerate edge.
- void simplify_edge(edge_type *edge) {
- 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;
-
- // Update second vertex incident edges start and end points.
- edge_type *updated_edge = edge->twin->rot_next;
- while (updated_edge != edge->twin) {
- updated_edge->start_point = vertex1;
- updated_edge->twin->end_point = vertex1;
- updated_edge = updated_edge->rot_next;
- }
-
- edge_type *edge1 = edge;
- edge_type *edge2 = edge->twin;
-
- edge_type *edge1_rot_prev = edge1->rot_prev;
- edge_type *edge1_rot_next = edge1->rot_next;
-
- edge_type *edge2_rot_prev = edge2->rot_prev;
- edge_type *edge2_rot_next = edge2->rot_next;
-
- // Update prev and next pointers of incident edges.
- edge1_rot_next->twin->next = edge2_rot_prev;
- edge2_rot_prev->prev = edge1_rot_next->twin;
- edge1_rot_prev->prev = edge2_rot_next->twin;
- edge2_rot_next->twin->next = edge1_rot_prev;
-
- // Update rotation prev and next pointers of incident edges.
- edge1_rot_prev->rot_next = edge2_rot_next;
- edge2_rot_next->rot_prev = edge1_rot_prev;
- edge1_rot_next->rot_prev = edge2_rot_prev;
- edge2_rot_prev->rot_next = edge1_rot_next;
-
- // Change incident edge pointer of a vertex if it correspongs to the
- // degenerate edge.
- if (vertex1->incident_edge == edge)
- vertex1->incident_edge = edge->rot_prev;
-
- // Remove second vertex from the vertex records list.
- if (vertex1->voronoi_record_it != vertex2->voronoi_record_it) {
- vertex_records_.erase(vertex2->voronoi_record_it);
- num_vertex_records_--;
- }
- }
-
- 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;
- }
- }
-
- // 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;
-
- // Update cell, next/prev pointers.
- if (cur_edge) {
- clipped_edge_type *prev = NULL;
- 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);
-
- // Update prev/next pointers.
- if (prev) {
- prev->next = new_cell.incident_edge;
- new_cell.incident_edge->prev = prev;
- }
- }
- }
- clipped_output.num_edge_records >>= 1;
- }
-
- 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_;
- int num_edges_;
-
- BRect<coordinate_type> voronoi_rect_;
-
- // Disallow copy constructor and operator=
- voronoi_output(const voronoi_output&);
- void operator=(const voronoi_output&);
- };
-
-} // sweepline
-} // boost
-} // detail
-
-#undef INV_LOG_2
-#undef INT_PREDICATE_COMPUTE_DIFFERENCE
-#undef INT_PREDICATE_CONVERT_65_BIT
-#undef INT_PREDICATE_AVOID_CANCELLATION
-
-#endif
Copied: sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_builder.hpp (from r66210, /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_builder.hpp 2010-10-27 14:47:57 EDT (Wed, 27 Oct 2010)
@@ -1,4 +1,4 @@
-// Boost sweepline/voronoi_segment_builder.hpp header file
+// Boost sweepline/voronoi_builder.hpp header file
// Copyright Andrii Sydorchuk 2010.
// Distributed under the Boost Software License, Version 1.0.
@@ -154,7 +154,7 @@
}
// Clip using defined rectangle.
- // TODO(asydorchuk): Define what exactly it means to clip some region of voronoi diagram.
+ // 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);
//}
Copied: sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_output.hpp (from r66210, /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_output.hpp 2010-10-27 14:47:57 EDT (Wed, 27 Oct 2010)
@@ -1,4 +1,4 @@
-// Boost sweepline/voronoi_segment_output.hpp header file
+// Boost sweepline/voronoi_output.hpp header file
// Copyright Andrii Sydorchuk 2010.
// Distributed under the Boost Software License, Version 1.0.
@@ -81,10 +81,10 @@
///////////////////////////////////////////////////////////////////////////
// VORONOI OUTPUT TYPES ///////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////
- namespace detail {
- template <typename T>
- struct site_event;
- }
+ namespace detail {
+ template <typename T>
+ struct site_event;
+ }
// Bounding rectangle data structure.
template <typename T>
@@ -131,70 +131,70 @@
}
};
- 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()));
+ template <typename T>
+ class Helper {
+ public:
+ typedef T coordinate_type;
- return fT0_used && fT1_used;
- }
+ 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;
+ }
static void fill_intermediate_points(point_2d<coordinate_type> point_site,
point_2d<coordinate_type> segment_site_start,
@@ -241,48 +241,48 @@
}
intermediate_points.push_back(last_point);
}
-
- 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;
- }
+
+ 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;
+ }
static double get_point_projection(point_2d<coordinate_type> point,
point_2d<coordinate_type> segment_start,
@@ -309,56 +309,56 @@
double sqr_len = vec_x * vec_x + vec_y * vec_y;
return static_cast<int>(log(sqr_len) * 3.4 + 1E-6);
}
- };
+ };
template <typename T>
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),
- num_incident_edges(0),
- site(new_site) {}
-
- 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) {}
- };
+ 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),
+ num_incident_edges(0),
+ site(new_site) {}
+
+ 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;
@@ -371,10 +371,10 @@
struct voronoi_edge_clipped {
typedef T coordinate_type;
typedef point_2d<T> Point2D;
- typedef voronoi_cell_clipped<coordinate_type> voronoi_cell_type;
- typedef voronoi_vertex_clipped<coordinate_type> voronoi_vertex_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;
+ typedef detail::site_event<coordinate_type> site_event_type;
voronoi_cell_type *cell;
voronoi_vertex_type *start_point;
@@ -395,54 +395,54 @@
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);
+ 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);
Helper<T>::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;
- }
+ } 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>
@@ -450,25 +450,25 @@
public:
typedef T coordinate_type;
typedef point_2d<T> Point2D;
- typedef detail::site_event<T> site_event_type;
+ typedef detail::site_event<T> site_event_type;
- typedef voronoi_cell_clipped<coordinate_type> voronoi_cell_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 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 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 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;
-
+ BRect<coordinate_type> bounding_rectangle;
+
int num_cell_records;
int num_vertex_records;
int num_edge_records;
Deleted: sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_segment_builder.hpp
==============================================================================
--- sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_segment_builder.hpp 2010-10-27 14:47:57 EDT (Wed, 27 Oct 2010)
+++ (empty file)
@@ -1,446 +0,0 @@
-// Boost sweepline/voronoi_segment_builder.hpp header file
-
-// Copyright Andrii Sydorchuk 2010.
-// Distributed under the Boost Software License, Version 1.0.
-// (See accompanying file LICENSE_1_0.txt or copy at
-// http://www.boost.org/LICENSE_1_0.txt)
-
-// See http://www.boost.org for updates, documentation, and revision history.
-
-#ifndef BOOST_SWEEPLINE_VORONOI_SEGMENT_BUILDER
-#define BOOST_SWEEPLINE_VORONOI_SEGMENT_BUILDER
-
-namespace boost {
-namespace sweepline {
-
- // Voronoi diagram builder. Sweepline sweeps from left to right.
- template <typename T>
- class voronoi_builder {
- public:
- typedef T coordinate_type;
- typedef point_2d<coordinate_type> Point2D;
- typedef std::pair<Point2D, Point2D> Segment2D;
- typedef voronoi_output_clipped<coordinate_type> ClippedOutput;
- typedef typename detail::site_event<coordinate_type> site_event_type;
- typedef typename detail::circle_event<coordinate_type> circle_event_type;
-
- voronoi_builder() {
- // Set sites iterator.
- site_events_iterator_ = site_events_.begin();
- }
-
- void init(std::vector<Point2D> &points) {
- std::vector<Segment2D> empty_vec;
- init(points, empty_vec);
- }
-
- void init(std::vector<Segment2D> &segments) {
- std::vector<Point2D> empty_vec;
- init(empty_vec, segments);
- }
-
- // Init beach line before sweepline run.
- // In case of a few first sites situated on the same
- // vertical line, we init beach line with all of them.
- // In other case just use the first two sites for the initialization.
- void init(std::vector<Point2D> &points, std::vector<Segment2D> &segments) {
- // Clear all data structures.
- reset();
-
- // TODO(asydorchuk): Add segments intersection check.
-
- // Avoid additional memory reallocations.
- site_events_.reserve(points.size() + segments.size() * 3);
-
- // Create site events from point sites.
- for (typename std::vector<Point2D>::const_iterator it = points.begin();
- it != points.end(); it++) {
- site_events_.push_back(detail::make_site_event(it->x(), it->y(), 0));
- }
-
- // Create site events from end points of segment sites and segment itself.
- for (typename std::vector<Segment2D>::const_iterator it = segments.begin();
- it != segments.end(); it++) {
- site_events_.push_back(detail::make_site_event(it->first, 0));
- site_events_.push_back(detail::make_site_event(it->second, 0));
- site_events_.push_back(detail::make_site_event(it->first, it->second, 0));
- }
-
- // Sort site events.
- sort(site_events_.begin(), site_events_.end());
-
- // Remove duplicates.
- site_events_.erase(unique(site_events_.begin(), site_events_.end()),
- site_events_.end());
-
- // Number sites.
- for (int cur_index = 0; cur_index < static_cast<int>(site_events_.size()); cur_index++)
- site_events_[cur_index].set_site_index(cur_index);
-
- // Set site iterator.
- site_events_iterator_ = site_events_.begin();
-
- // Init output with number of site events.
- // There will be one site event for each input point and three site events
- // for each input segment: both ends of a segment and the segment itself.
- output_.init(site_events_.size());
- }
-
- void reset() {
- output_.reset();
- circle_events_.reset();
- beach_line_.clear();
- site_events_.clear();
- site_events_iterator_ = site_events_.begin();
- }
-
- void run_sweepline() {
- // Init beach line.
- if (site_events_.empty()) {
- return;
- } else if (site_events_.size() == 1) {
- // Handle one input site case.
- output_.process_single_site(site_events_[0]);
- site_events_iterator_++;
- } else {
- int skip = 0;
- // Init beach line.
- while(site_events_iterator_ != site_events_.end() &&
- site_events_iterator_->x() == site_events_.begin()->x() &&
- site_events_iterator_->is_vertical()) {
- site_events_iterator_++;
- skip++;
- }
-
- if (skip == 1) {
- // Init beach line with two sites.
- init_beach_line();
- } else {
- // Init beach line with sites situated on the same vertical line.
- init_beach_line_collinear_sites();
- }
- }
-
- // Algorithm stops when there are no events to process.
- while (!circle_events_.empty() ||
- !(site_events_iterator_ == site_events_.end())) {
- if (circle_events_.empty()) {
- process_site_event();
- } else if (site_events_iterator_ == site_events_.end()) {
- process_circle_event();
- } else {
- if (circle_events_.top().compare(*site_events_iterator_) > 0) {
- process_site_event();
- } else {
- process_circle_event();
- }
- }
- }
-
- // Simplify output.
- output_.simplify();
- }
-
- // Returns output bounding rectangle that includes all the vertices and sites
- // of the voronoi diagram.
- const BRect<coordinate_type> &get_bounding_rectangle() const {
- return output_.get_bounding_rectangle();
- }
-
- // Clip using bounding rectangle that includes all the vertices and sites
- // of the voronoi diagram.
- void clip(ClippedOutput &clipped_output) {
- output_.clip(clipped_output);
- }
-
- // Clip using defined rectangle.
- // 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;
-
- typedef detail::voronoi_output<coordinate_type> Output;
- typedef typename Output::edge_type edge_type;
-
- typedef typename detail::circle_events_queue<coordinate_type> CircleEventsQueue;
- typedef typename detail::beach_line_node<coordinate_type> Key;
- typedef typename detail::beach_line_node_data<coordinate_type> Value;
- typedef typename detail::node_comparer<Key> NodeComparer;
- typedef std::map< Key, Value, NodeComparer > BeachLine;
- typedef typename std::map< Key, Value, NodeComparer >::iterator beach_line_iterator;
- typedef typename std::pair<Point2D, beach_line_iterator> end_point_type;
-
- void init_beach_line() {
- // The first site is always a point.
- // Get the first and the second site events.
- site_events_iterator_type it_first = site_events_.begin();
- site_events_iterator_type it_second = site_events_.begin();
- it_second++;
-
- // Insert new nodes.
- insert_new_arc(*it_first, *it_first, *it_second, beach_line_.begin());
-
- // The second site has been already processed.
- site_events_iterator_++;
- }
-
- // Insert bisectors for all collinear initial sites.
- // There should be at least two colinear sites.
- void init_beach_line_collinear_sites() {
- site_events_iterator_type it_first = site_events_.begin();
- site_events_iterator_type it_second = site_events_.begin();
- it_second++;
- while (it_second != site_events_iterator_) {
- // Create new beach line node.
- Key new_node(*it_first, *it_second);
-
- // Update output.
- edge_type *edge = output_.insert_new_edge(*it_first, *it_second);
-
- // Insert new node into the binary search tree.
- beach_line_.insert(std::pair<Key, Value>(new_node, Value(edge)));
-
- // Update iterators.
- it_first++;
- it_second++;
- }
- }
-
- // Uses special comparison function for the lower bound and insertion
- // operations.
- void process_site_event() {
- site_event_type site_event = *site_events_iterator_;
- site_events_iterator_++;
-
- // If new site is end point of some segment, remove temporary nodes from
- // beach line data structure.
- if (!site_event.is_segment()) {
- while (!end_points_.empty() && end_points_.top().first == site_event.get_point0()) {
- beach_line_.erase(end_points_.top().second);
- end_points_.pop();
- }
- }
-
- // Find the node in the binary search tree with left arc
- // lying above the new site point.
- Key new_key(site_event);
- beach_line_iterator it = beach_line_.lower_bound(new_key);
- int it_dist = site_event.is_segment() ? 2 : 1;
-
- if (it == beach_line_.end()) {
- it--;
- const site_event_type &site_arc = it->first.get_right_site();
-
- // Insert new arc into the sweepline.
- beach_line_iterator new_node_it = insert_new_arc(site_arc, site_arc, site_event, it);
- std::advance(new_node_it, -it_dist);
-
- // Add candidate circle to the event queue.
- activate_circle_event(it->first.get_left_site(), it->first.get_right_site(),
- site_event, new_node_it);
- } else if (it == beach_line_.begin()) {
- const site_event_type &site_arc = it->first.get_left_site();
-
- // Insert new arc into the sweepline.
- insert_new_arc(site_arc, site_arc, site_event, it);
-
- // Add candidate circle to the event queue.
- if (site_event.is_segment()) {
- site_event.set_inverse();
- }
- activate_circle_event(site_event, it->first.get_left_site(),
- it->first.get_right_site(), it);
- } else {
- const site_event_type &site_arc2 = it->first.get_left_site();
- const site_event_type &site3 = it->first.get_right_site();
-
- // Remove candidate circle from the event queue.
- it->second.deactivate_circle_event();
- it--;
- const site_event_type &site_arc1 = it->first.get_right_site();
- const site_event_type &site1 = it->first.get_left_site();
-
- // Insert new arc into the sweepline.
- beach_line_iterator new_node_it =
- insert_new_arc(site_arc1, site_arc2, site_event, it);
-
- // Add candidate circles to the event queue.
- std::advance(new_node_it, -it_dist);
- activate_circle_event(site1, site_arc1, site_event, new_node_it);
- if (site_event.is_segment()) {
- site_event.set_inverse();
- }
- std::advance(new_node_it, it_dist + 1);
- activate_circle_event(site_event, site_arc2, site3, new_node_it);
- }
- }
-
- // Doesn't use special comparison function as it works fine only for
- // the site events processing.
- void process_circle_event() {
- const circle_event_type &circle_event = circle_events_.top();
-
- // Retrieve the second bisector node that corresponds to the given
- // circle event.
- beach_line_iterator it_first = circle_event.get_bisector();
- beach_line_iterator it_last = it_first;
-
- // Get the the third site.
- site_event_type site3 = it_first->first.get_right_site();
-
- // Get second bisector;
- edge_type *bisector2 = it_first->second.edge;
-
- // Get first bisector;
- it_first--;
- edge_type *bisector1 = it_first->second.edge;
-
- // Get the first site that creates given circle event.
- site_event_type site1 = it_first->first.get_left_site();
-
- // Let circle event sites be A, B, C, two bisectors that define
- // circle event be (A, B), (B, C). During circle event processing
- // we remove (A, B), (B, C) and insert (A, C). As beach line nodes
- // comparer doesn't work fine for the circle events we only remove
- // (B, C) bisector and change (A, B) bisector to the (A, C). That's
- // why we use const_cast there and take all the responsibility that
- // map data structure keeps correct ordering.
- const_cast<Key &>(it_first->first).set_right_site(site3);
- if (site1.is_segment() && site1.get_point0(true) == site3.get_point0(true)) {
- const_cast<Key &>(it_first->first).set_left_site_inverse();
- }
- if (site3.is_segment() && site3.get_point1(true) == site1.get_point0(true)) {
- const_cast<Key &>(it_first->first).set_right_site_inverse();
- }
- it_first->second.edge = output_.insert_new_edge(site1, site3, circle_event,
- bisector1, bisector2);
- beach_line_.erase(it_last);
- it_last = it_first;
-
- // Pop circle event from the event queue, before we might
- // insert new events in it.
- circle_events_.pop();
-
- // Check the new triplets formed by the neighboring arcs
- // for potential circle events. Check left.
- if (it_first != beach_line_.begin()) {
- it_first->second.deactivate_circle_event();
- it_first--;
- const site_event_type &site_l1 = it_first->first.get_left_site();
- activate_circle_event(site_l1, site1, site3, it_last);
- }
-
- // Check the new triplets formed by the neighboring arcs
- // for potential circle events. Check right.
- it_last++;
- if (it_last != beach_line_.end()) {
- it_last->second.deactivate_circle_event();
- const site_event_type &site_r1 = it_last->first.get_right_site();
- activate_circle_event(site1, site3, site_r1, it_last);
- }
-
- }
-
- // Insert new arc below site arc into the beach line.
- beach_line_iterator insert_new_arc(const site_event_type &site_arc1,
- const site_event_type &site_arc2,
- const site_event_type &site_event,
- const beach_line_iterator &position) {
- // Create two new nodes.
- Key new_left_node(site_arc1, site_event);
- Key new_right_node(site_event, site_arc2);
- if (site_event.is_segment()) {
- new_right_node.set_left_site_inverse();
- }
-
- // Insert two new nodes into the binary search tree.
- // Update output.
- edge_type *edge = output_.insert_new_edge(site_arc2, site_event);
- beach_line_iterator it = beach_line_.insert(position,
- std::pair<Key, Value>(new_right_node, Value(edge->twin)));
- if (site_event.is_segment()) {
- Key new_node(site_event, site_event);
- new_node.set_right_site_inverse();
- beach_line_iterator temp_it = beach_line_.insert(position,
- std::pair<Key, Value>(new_node, Value(NULL)));
- end_points_.push(std::make_pair(site_event.get_point1(), temp_it));
- }
- beach_line_.insert(position, std::pair<Key, Value>(new_left_node, Value(edge)));
- return it;
- }
-
- // Create circle event from the given three points.
- bool create_circle_event(const site_event_type &site1,
- const site_event_type &site2,
- const site_event_type &site3,
- circle_event_type &c_event) const {
- if (!site1.is_segment()) {
- if (!site2.is_segment()) {
- if (!site3.is_segment()) {
- return detail::create_circle_event_ppp(site1, site2, site3, c_event);
- } else {
- return detail::create_circle_event_pps(site1, site2, site3, 3, c_event);
- }
- } else {
- if (!site3.is_segment()) {
- return detail::create_circle_event_pps(site1, site3, site2, 2, c_event);
- } else {
- return detail::create_circle_event_pss(site1, site2, site3, 1, c_event);
- }
- }
- } else {
- if (!site2.is_segment()) {
- if (!site3.is_segment()) {
- return detail::create_circle_event_pps(site2, site3, site1, 1, c_event);
- } else {
- return detail::create_circle_event_pss(site2, site1, site3, 2, c_event);
- }
- } else {
- if (!site3.is_segment()) {
- return detail::create_circle_event_pss(site3, site1, site2, 3, c_event);
- } else {
- return detail::create_circle_event_sss(site1, site2, site3, c_event);
- }
- }
- }
- }
-
- // Add new circle event to the event queue.
- void activate_circle_event(const site_event_type &site1,
- const site_event_type &site2,
- const site_event_type &site3,
- beach_line_iterator bisector_node) {
- circle_event_type c_event;
- if (create_circle_event(site1, site2, site3, c_event)) {
- c_event.set_bisector(bisector_node);
- bisector_node->second.activate_circle_event(circle_events_.push(c_event));
- }
- }
-
- private:
- struct end_point_comparison {
- bool operator() (const end_point_type &end1, const end_point_type &end2) const {
- return end1.first > end2.first;
- }
- };
-
- std::vector<site_event_type> site_events_;
- site_events_iterator_type site_events_iterator_;
- std::priority_queue< end_point_type, std::vector<end_point_type>,
- end_point_comparison > end_points_;
- CircleEventsQueue circle_events_;
- BeachLine beach_line_;
- Output output_;
-
- //Disallow copy constructor and operator=
- voronoi_builder(const voronoi_builder&);
- void operator=(const voronoi_builder&);
- };
-
-} // sweepline
-} // boost
-
-#endif
Deleted: sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_segment_output.hpp
==============================================================================
--- sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_segment_output.hpp 2010-10-27 14:47:57 EDT (Wed, 27 Oct 2010)
+++ (empty file)
@@ -1,500 +0,0 @@
-// Boost sweepline/voronoi_segment_output.hpp header file
-
-// Copyright Andrii Sydorchuk 2010.
-// Distributed under the Boost Software License, Version 1.0.
-// (See accompanying file LICENSE_1_0.txt or copy at
-// http://www.boost.org/LICENSE_1_0.txt)
-
-// See http://www.boost.org for updates, documentation, and revision history.
-
-#ifndef BOOST_SWEEPLINE_VORONOI_SEGMENT_OUTPUT
-#define BOOST_SWEEPLINE_VORONOI_SEGMENT_OUTPUT
-
-namespace boost {
-namespace sweepline {
- template <typename T>
- struct point_2d {
- public:
- typedef T coordinate_type;
-
- point_2d() {}
-
- point_2d(T x, T y) {
- x_ = x;
- y_ = y;
- }
-
- bool operator==(const point_2d &point) const {
- return (this->x_ == point.x()) && (this->y_ == point.y());
- }
-
- bool operator!=(const point_2d &point) const {
- return (this->x_ != point.x()) || (this->y_ != point.y());
- }
-
- // This comparator actually defines sweepline movement direction.
- bool operator<(const point_2d &point) const {
- // Sweepline sweeps from left to right.
- if (this->x_ != point.x_)
- return this->x_ < point.x_;
- return this->y_ < point.y_;
- }
-
- bool operator<=(const point_2d &point) const {
- return !(point < (*this));
- }
-
- bool operator>(const point_2d &point) const {
- return point < (*this);
- }
-
- bool operator>=(const point_2d &point) const {
- return !((*this) < point);
- }
-
- coordinate_type x() const {
- return this->x_;
- }
-
- coordinate_type y() const {
- return this->y_;
- }
-
- void x(coordinate_type x) {
- x_ = x;
- }
-
- void y(coordinate_type y) {
- y_ = y;
- }
-
- private:
- coordinate_type x_;
- coordinate_type y_;
- };
-
- template <typename T>
- point_2d<T> make_point_2d(T x, T y) {
- return point_2d<T>(x,y);
- }
-
- ///////////////////////////////////////////////////////////////////////////
- // VORONOI OUTPUT TYPES ///////////////////////////////////////////////////
- ///////////////////////////////////////////////////////////////////////////
- namespace detail {
- template <typename T>
- struct site_event;
- }
-
- // Bounding rectangle data structure.
- template <typename T>
- struct BRect {
- public:
- typedef T coordinate_type;
- typedef point_2d<T> Point2D;
-
- coordinate_type x_min;
- coordinate_type y_min;
- coordinate_type x_max;
- coordinate_type y_max;
-
- BRect() {}
-
- BRect(const Point2D &p1, const Point2D &p2) {
- x_min = (std::min)(p1.x(), p2.x());
- y_min = (std::min)(p1.y(), p2.y());
- x_max = (std::max)(p1.x(), p2.x());
- y_max = (std::max)(p1.y(), p2.y());
- }
-
- BRect(coordinate_type x_mn, coordinate_type y_mn,
- coordinate_type x_mx, coordinate_type y_mx) {
- x_min = (std::min)(x_mn, x_mx);
- y_min = (std::min)(y_mn, y_mx);
- x_max = (std::max)(x_mn, x_mx);
- y_max = (std::max)(y_mn, y_mx);
- }
-
- void update(const Point2D &p) {
- x_min = (std::min)(x_min, p.x());
- y_min = (std::min)(y_min, p.y());
- x_max = (std::max)(x_max, p.x());
- y_max = (std::max)(y_max, p.y());
- }
-
- bool contains(const Point2D &p) const {
- return p.x() > x_min && p.x() < x_max && p.y() > y_min && p.y() < y_max;
- }
-
- bool is_valid() const {
- return (x_min < x_max) && (y_min < y_max);
- }
- };
-
- 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;
- }
-
- static void fill_intermediate_points(point_2d<coordinate_type> point_site,
- point_2d<coordinate_type> segment_site_start,
- point_2d<coordinate_type> segment_site_end,
- std::vector< point_2d<double> > &intermediate_points) {
- int num_inter_points = get_intermediate_points_count(
- intermediate_points[0], intermediate_points[1]);
- if (num_inter_points <= 0 ||
- point_site == segment_site_start ||
- point_site == segment_site_end) {
- 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);
- }
-
- 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;
- }
-
- static double get_point_projection(point_2d<coordinate_type> point,
- point_2d<coordinate_type> segment_start,
- point_2d<coordinate_type> 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;
- }
-
- static int get_intermediate_points_count(point_2d<coordinate_type> point1,
- point_2d<coordinate_type> 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) * 3.4 + 1E-6);
- }
- };
-
- template <typename T>
- 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),
- num_incident_edges(0),
- site(new_site) {}
-
- 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;
- // 2) pointers to start/end vertices of half-edge;
- // 3) pointers to previous/next half-edges(CCW);
- // 4) pointers to previous/next half-edges rotated
- // around start point;
- // 5) pointer to twin half-edge.
- template <typename T>
- struct voronoi_edge_clipped {
- typedef T coordinate_type;
- typedef point_2d<T> Point2D;
- 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_edge_clipped() :
- cell(NULL),
- start_point(NULL),
- end_point(NULL),
- prev(NULL),
- next(NULL),
- 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);
- Helper<T>::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>
- struct voronoi_output_clipped {
- public:
- typedef T coordinate_type;
- typedef point_2d<T> Point2D;
- 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_edge_records = 0;
- }
-
- void reset() {
- cell_records.clear();
- vertex_records.clear();
- edge_records.clear();
-
- num_cell_records = 0;
- num_vertex_records = 0;
- num_edge_records = 0;
- }
- };
-
-} // sweepline
-} // boost
-
-#endif
Deleted: sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_segment_sweepline.hpp
==============================================================================
--- sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_segment_sweepline.hpp 2010-10-27 14:47:57 EDT (Wed, 27 Oct 2010)
+++ (empty file)
@@ -1,32 +0,0 @@
-// Boost sweepline/voronoi_segment_sweepline.hpp header file
-
-// Copyright Andrii Sydorchuk 2010.
-// Distributed under the Boost Software License, Version 1.0.
-// (See accompanying file LICENSE_1_0.txt or copy at
-// http://www.boost.org/LICENSE_1_0.txt)
-
-// See http://www.boost.org for updates, documentation, and revision history.
-
-#ifndef BOOST_SWEEPLINE_VORONOI_SEGMENT_SWEEPLINE
-#define BOOST_SWEEPLINE_VORONOI_SEGMENT_SWEEPLINE
-
-#include <algorithm>
-#include <cmath>
-#include <cstring>
-#include <list>
-#include <map>
-#include <queue>
-#include <vector>
-
-#ifdef USE_MULTI_PRECISION_LIBRARY
- #pragma warning( disable : 4800 )
- #include "gmpxx.h"
-#endif
-
-#include "voronoi_segment_output.hpp"
-
-#include "detail/voronoi_segment_formation.hpp"
-
-#include "voronoi_segment_builder.hpp"
-
-#endif
Copied: sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_sweepline.hpp (from r66210, /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_sweepline.hpp 2010-10-27 14:47:57 EDT (Wed, 27 Oct 2010)
@@ -1,4 +1,4 @@
-// Boost sweepline/voronoi_segment_sweepline.hpp header file
+// Boost sweepline/voronoi_sweepline.hpp header file
// Copyright Andrii Sydorchuk 2010.
// Distributed under the Boost Software License, Version 1.0.
@@ -23,10 +23,10 @@
#include "gmpxx.h"
#endif
-#include "voronoi_segment_output.hpp"
+#include "voronoi_output.hpp"
-#include "detail/voronoi_segment_formation.hpp"
+#include "detail/voronoi_formation.hpp"
-#include "voronoi_segment_builder.hpp"
+#include "voronoi_builder.hpp"
#endif
Deleted: sandbox/SOC/2010/sweepline/libs/sweepline/example/input_data/example_016_random.txt
==============================================================================
--- sandbox/SOC/2010/sweepline/libs/sweepline/example/input_data/example_016_random.txt 2010-10-27 14:47:57 EDT (Wed, 27 Oct 2010)
+++ (empty file)
@@ -1,11 +0,0 @@
-10
-9 1
-4 3
-9 6
-9 8
-3 9
-6 8
-0 5
-9 5
-3 0
-2 1
\ No newline at end of file
Deleted: sandbox/SOC/2010/sweepline/libs/sweepline/example/input_data/example_017_random.txt
==============================================================================
--- sandbox/SOC/2010/sweepline/libs/sweepline/example/input_data/example_017_random.txt 2010-10-27 14:47:57 EDT (Wed, 27 Oct 2010)
+++ (empty file)
@@ -1,11 +0,0 @@
-10
-9 9
-2 6
-3 1
-6 4
-9 1
-9 7
-6 2
-2 4
-3 7
-6 7
\ No newline at end of file
Deleted: sandbox/SOC/2010/sweepline/libs/sweepline/example/input_data/example_018_random.txt
==============================================================================
--- sandbox/SOC/2010/sweepline/libs/sweepline/example/input_data/example_018_random.txt 2010-10-27 14:47:57 EDT (Wed, 27 Oct 2010)
+++ (empty file)
@@ -1,11 +0,0 @@
-10
-4 1
-5 4
-5 5
-2 6
-3 4
-0 7
-2 5
-8 9
-0 4
-2 7
\ No newline at end of file
Deleted: sandbox/SOC/2010/sweepline/libs/sweepline/example/input_data/example_019_random.txt
==============================================================================
--- sandbox/SOC/2010/sweepline/libs/sweepline/example/input_data/example_019_random.txt 2010-10-27 14:47:57 EDT (Wed, 27 Oct 2010)
+++ (empty file)
@@ -1,101 +0,0 @@
-100
-29 76
-99 94
-74 20
-53 26
-95 55
-94 21
-50 70
-19 93
-31 30
-73 61
-87 23
-60 66
-51 29
-82 51
-74 40
-31 77
-1 82
-43 0
-58 67
-63 32
-19 90
-68 31
-49 63
-76 83
-72 20
-70 11
-80 23
-4 90
-32 56
-63 75
-51 71
-62 10
-80 57
-71 47
-2 8
-67 85
-64 72
-85 6
-53 91
-92 25
-95 79
-24 6
-1 10
-10 85
-11 30
-22 14
-48 55
-82 8
-14 54
-84 60
-33 91
-85 60
-65 81
-60 23
-10 44
-29 32
-21 11
-90 15
-73 71
-41 62
-9 36
-44 80
-27 39
-41 38
-25 23
-86 15
-4 76
-52 6
-39 97
-42 25
-93 93
-97 24
-13 16
-58 62
-48 78
-43 74
-99 85
-13 42
-8 82
-13 9
-51 50
-85 83
-30 11
-58 42
-44 32
-88 74
-37 21
-65 28
-79 94
-50 94
-38 83
-82 13
-30 88
-16 92
-73 66
-24 0
-40 82
-57 25
-55 88
-13 33
\ No newline at end of file
Added: sandbox/SOC/2010/sweepline/libs/sweepline/example/input_data/example_044.txt
==============================================================================
--- (empty file)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/example/input_data/example_044.txt 2010-10-27 14:47:57 EDT (Wed, 27 Oct 2010)
@@ -0,0 +1,101 @@
+100
+-901943112 1116691472
+2104533928 1889785568
+1030792128 -1288490160
+128849016 -1030792128
+1932735240 214748360
+1889785568 -1245540488
+0 858993440
+-1331439832 1846835896
+-816043768 -858993440
+987842456 472446392
+1589137864 -1159641144
+429496720 687194752
+42949672 -901943112
+1374389504 42949672
+1030792128 -429496720
+-816043768 1159641144
+-2104533928 1374389504
+-300647704 -2147483600
+343597376 730144424
+558345736 -773094096
+-1331439832 1717986880
+773094096 -816043768
+-42949672 558345736
+1116691472 1417339176
+944892784 -1288490160
+858993440 -1675037208
+1288490160 -1159641144
+-1975684912 1717986880
+-773094096 257698032
+558345736 1073741800
+42949672 901943112
+515396064 -1717986880
+1288490160 300647704
+901943112 -128849016
+-2061584256 -1803886224
+730144424 1503238520
+601295408 944892784
+1503238520 -1889785568
+128849016 1760936552
+1803886224 -1073741800
+1932735240 1245540488
+-1116691472 -1889785568
+-2104533928 -1717986880
+-1717986880 1503238520
+-1675037208 -858993440
+-1202590816 -1546188192
+-85899344 214748360
+1374389504 -1803886224
+-1546188192 171798688
+1460288848 429496720
+-730144424 1760936552
+1503238520 429496720
+644245080 1331439832
+429496720 -1159641144
+-1717986880 -257698032
+-901943112 -773094096
+-1245540488 -1675037208
+1717986880 -1503238520
+987842456 901943112
+-386547048 515396064
+-1760936552 -601295408
+-257698032 1288490160
+-987842456 -472446392
+-386547048 -515396064
+-1073741800 -1159641144
+1546188192 -1503238520
+-1975684912 1116691472
+85899344 -1889785568
+-472446392 2018634584
+-343597376 -1073741800
+1846835896 1846835896
+2018634584 -1116691472
+-1589137864 -1460288848
+343597376 515396064
+-85899344 1202590816
+-300647704 1030792128
+2104533928 1503238520
+-1589137864 -343597376
+-1803886224 1374389504
+-1589137864 -1760936552
+42949672 0
+1503238520 1417339176
+-858993440 -1675037208
+343597376 -343597376
+-257698032 -773094096
+1632087536 1030792128
+-558345736 -1245540488
+644245080 -944892784
+1245540488 1889785568
+0 1889785568
+-515396064 1417339176
+1374389504 -1589137864
+-858993440 1632087536
+-1460288848 1803886224
+987842456 687194752
+-1116691472 -2147483600
+-429496720 1374389504
+300647704 -1073741800
+214748360 1632087536
+-1589137864 -730144424
\ No newline at end of file
Added: sandbox/SOC/2010/sweepline/libs/sweepline/example/input_data/example_045.txt
==============================================================================
--- (empty file)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/example/input_data/example_045.txt 2010-10-27 14:47:57 EDT (Wed, 27 Oct 2010)
@@ -0,0 +1,11 @@
+10
+858993458 1717986916
+-429496729 1288490187
+-2147483645 -1288490187
+-2147483645 -858993458
+-1717986916 858993458
+-2147483645 -429496729
+429496729 -2147483645
+858993458 -429496729
+-429496729 1717986916
+1717986916 -858993458
\ No newline at end of file
Deleted: sandbox/SOC/2010/sweepline/libs/sweepline/example/output_data/example_016_random.png
==============================================================================
Binary file. No diff available.
Deleted: sandbox/SOC/2010/sweepline/libs/sweepline/example/output_data/example_017_random.png
==============================================================================
Binary file. No diff available.
Deleted: sandbox/SOC/2010/sweepline/libs/sweepline/example/output_data/example_018_random.png
==============================================================================
Binary file. No diff available.
Deleted: sandbox/SOC/2010/sweepline/libs/sweepline/example/output_data/example_019_random.png
==============================================================================
Binary file. No diff available.
Added: sandbox/SOC/2010/sweepline/libs/sweepline/example/output_data/example_044.png
==============================================================================
Binary file. No diff available.
Added: sandbox/SOC/2010/sweepline/libs/sweepline/example/output_data/example_045.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-27 14:47:57 EDT (Wed, 27 Oct 2010)
@@ -10,7 +10,7 @@
#include <QtOpenGL/QGLWidget>
#include <QtGui/QtGui>
-#include "boost/sweepline/voronoi_segment_sweepline.hpp"
+#include "boost/sweepline/voronoi_sweepline.hpp"
using namespace boost::sweepline;
class GLWidget : public QGLWidget {
@@ -26,7 +26,7 @@
void build(QString file_path) {
std::vector<Point2D> point_sites;
- std::vector<Segment2D> segment_sites;
+ std::vector<Segment2D> segment_sites;
// Open file.
QFile data(file_path);
@@ -37,19 +37,19 @@
// Read points from the file.
QTextStream in_stream(&data);
int num_point_sites = 0;
- int num_edge_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 >> 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.
@@ -72,15 +72,15 @@
voronoi_cells_type cells = voronoi_output_.cell_records;
voronoi_cell_const_iterator_type it;
glColor3f(0.0f, 0.0f, 1.0f);
- glPointSize(9);
+ glPointSize(9);
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();
- glPointSize(6);
- glLineWidth(2.7f);
+ glPointSize(6);
+ glLineWidth(2.7f);
glBegin(GL_LINES);
for (it = cells.begin(); it != cells.end(); it++) {
if (it->is_segment()) {
@@ -89,7 +89,7 @@
}
}
glEnd();
- glLineWidth(1.0);
+ glLineWidth(1.0);
}
// Draw voronoi vertices.
@@ -133,20 +133,20 @@
void update_view_port() {
glMatrixMode(GL_PROJECTION);
glLoadIdentity();
- glOrtho(brect_.x_min, brect_.x_max, brect_.y_min, brect_.y_max, -1.0, 1.0);
+ glOrtho(brect_.x_min, brect_.x_max, brect_.y_min, brect_.y_max, -1.0, 1.0);
glMatrixMode(GL_MODELVIEW);
}
typedef double coordinate_type;
typedef point_2d<coordinate_type> Point2D;
- typedef voronoi_builder<coordinate_type>::Segment2D Segment2D;
+ 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
+ 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 voronoi_output_clipped<coordinate_type>::voronoi_cell_const_iterator_type
+ 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;
@@ -163,7 +163,7 @@
MainWindow() {
glWidget_ = new GLWidget();
file_dir_ = QDir(QDir::currentPath(), tr("*.txt"));
- file_name_ = tr("");
+ file_name_ = tr("");
QHBoxLayout *centralLayout = new QHBoxLayout;
centralLayout->addWidget(glWidget_);
@@ -171,7 +171,7 @@
setLayout(centralLayout);
update_file_list();
- setWindowTitle(tr("Voronoi Visualizer"));
+ setWindowTitle(tr("Voronoi Visualizer"));
layout()->setSizeConstraint( QLayout::SetFixedSize );
}
@@ -185,14 +185,14 @@
update_file_list();
}
- void print_scr() {
- if (!file_name_.isEmpty()) {
- QImage screenshot = glWidget_->grabFrameBuffer(true);
- QString output_file = file_dir_.absolutePath() + tr("/") +
- file_name_.left(file_name_.indexOf('.')) + tr(".png");
- screenshot.save(output_file, 0, -1);
- }
- }
+ void print_scr() {
+ if (!file_name_.isEmpty()) {
+ QImage screenshot = glWidget_->grabFrameBuffer(true);
+ QString output_file = file_dir_.absolutePath() + tr("/") +
+ file_name_.left(file_name_.indexOf('.')) + tr(".png");
+ screenshot.save(output_file, 0, -1);
+ }
+ }
void build() {
file_name_ = file_list_->currentItem()->text();
@@ -217,14 +217,14 @@
connect(browse_button, SIGNAL(clicked()), this, SLOT(browse()));
browse_button->setMinimumHeight(50);
- QPushButton *print_scr_button = new QPushButton(tr("Make Screenshot"));
- connect(print_scr_button, SIGNAL(clicked()), this, SLOT(print_scr()));
- print_scr_button->setMinimumHeight(50);
+ QPushButton *print_scr_button = new QPushButton(tr("Make Screenshot"));
+ connect(print_scr_button, SIGNAL(clicked()), this, SLOT(print_scr()));
+ print_scr_button->setMinimumHeight(50);
file_layout->addWidget(message_label_, 0, 0);
file_layout->addWidget(file_list_, 1, 0);
file_layout->addWidget(browse_button, 2, 0);
- file_layout->addWidget(print_scr_button, 3, 0);
+ file_layout->addWidget(print_scr_button, 3, 0);
return file_layout;
}
@@ -242,7 +242,7 @@
}
QDir file_dir_;
- QString file_name_;
+ QString file_name_;
GLWidget *glWidget_;
QListWidget *file_list_;
QLabel *message_label_;
Modified: sandbox/SOC/2010/sweepline/libs/sweepline/test/Jamfile.v2
==============================================================================
--- sandbox/SOC/2010/sweepline/libs/sweepline/test/Jamfile.v2 (original)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/test/Jamfile.v2 2010-10-27 14:47:57 EDT (Wed, 27 Oct 2010)
@@ -10,18 +10,19 @@
<library>$(BOOST_ROOT)/libs/test/build//boost_unit_test_framework
;
-test-suite "sweepline_benchmark"
+
+test-suite "sweepline"
:
- [ run voronoi_segment/segment_voronoi_benchmark_test.cpp ]
+ [ run circle_event_creation_test.cpp ]
+ [ run clipping_test.cpp ]
+ [ run event_queue_test.cpp ]
+ [ run event_types_test.cpp ]
+ [ run node_comparer_test.cpp ]
+ [ run predicates_test.cpp ]
+ [ run sweepline_test.cpp ]
;
-test-suite "sweepline_segment"
+test-suite "sweepline_benchmark"
:
- [ run voronoi_segment/segment_circle_event_creation_test.cpp ]
- [ run voronoi_segment/segment_event_queue_test.cpp ]
- [ run voronoi_segment/segment_event_types_test.cpp ]
- [ run voronoi_segment/segment_node_comparer_test.cpp ]
- [ run voronoi_segment/segment_predicates_test.cpp ]
- [ run voronoi_segment/segment_voronoi_builder_test.cpp ]
- [ run voronoi_segment/segment_voronoi_clipping_test.cpp ]
+ [ run benchmark_test.cpp ]
;
\ No newline at end of file
Copied: sandbox/SOC/2010/sweepline/libs/sweepline/test/benchmark_test.cpp (from r66210, /sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_segment/segment_voronoi_benchmark_test.cpp)
==============================================================================
--- /sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_segment/segment_voronoi_benchmark_test.cpp (original)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/test/benchmark_test.cpp 2010-10-27 14:47:57 EDT (Wed, 27 Oct 2010)
@@ -1,4 +1,4 @@
-// Boost sweepline library segment_voronoi_benchmark_test.cpp file
+// Boost sweepline library benchmark_test.cpp file
// Copyright Andrii Sydorchuk 2010.
// Distributed under the Boost Software License, Version 1.0.
@@ -12,13 +12,17 @@
#include <stdlib.h>
#include <time.h>
-#include "../test_type_list.hpp"
-#include "boost/sweepline/voronoi_segment_sweepline.hpp"
+#include "test_type_list.hpp"
+#include "boost/sweepline/voronoi_sweepline.hpp"
using namespace boost::sweepline;
#define BOOST_TEST_MODULE voronoi_benchmark_test
#include <boost/test/test_case_template.hpp>
+#ifdef WIN32
+#pragma warning( disable : 4996 )
+#endif
+
BOOST_AUTO_TEST_CASE_TEMPLATE(benchmark_test1, T, test_types) {
typedef T coordinate_type;
srand(static_cast<unsigned int>(time(NULL)));
@@ -29,12 +33,18 @@
FILE *bench_file = fopen("benchmark.txt", "a");
fprintf(bench_file, "Voronoi Segment Sweepline Benchmark Test (time in seconds):\n");
- for (int num_points = 10; num_points <= 1000000; num_points *= 10) {
+#ifdef _DEBUG
+ int max_points = 1000;
+#else
+ int max_points = 100000;
+#endif
+
+ for (int num_points = 10; num_points <= max_points; num_points *= 10) {
std::vector< point_2d<coordinate_type> > points;
points.reserve(num_points);
time_t start_time = time(NULL);
- int num_times = 1000000 / num_points;
+ int num_times = max_points / num_points;
for (int cur = 0; cur < num_times; cur++) {
for (int cur_point = 0; cur_point < num_points; cur_point++) {
points.push_back(make_point_2d<coordinate_type>(
Copied: sandbox/SOC/2010/sweepline/libs/sweepline/test/circle_event_creation_test.cpp (from r66210, /sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_segment/segment_circle_event_creation_test.cpp)
==============================================================================
--- /sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_segment/segment_circle_event_creation_test.cpp (original)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/test/circle_event_creation_test.cpp 2010-10-27 14:47:57 EDT (Wed, 27 Oct 2010)
@@ -1,4 +1,4 @@
-// Boost sweepline library segment_circle_event_creation_test.cpp file
+// Boost sweepline library circle_event_creation_test.cpp file
// Copyright Andrii Sydorchuk 2010.
// Distributed under the Boost Software License, Version 1.0.
@@ -7,17 +7,17 @@
// See http://www.boost.org for updates, documentation, and revision history.
-#include "../test_type_list.hpp"
-#include "boost/sweepline/voronoi_segment_sweepline.hpp"
+#include "test_type_list.hpp"
+#include "boost/sweepline/voronoi_sweepline.hpp"
using namespace boost::sweepline;
#define BOOST_TEST_MODULE circle_event_creation
#include <boost/test/test_case_template.hpp>
#define CHECK_CIRCLE_EVENT(c_e, c_x, c_y, l_x) \
- BOOST_CHECK_EQUAL(c_e.get_center().x() == static_cast<T>(c_x), true); \
- BOOST_CHECK_EQUAL(c_e.get_center().y() == static_cast<T>(c_y), true); \
- BOOST_CHECK_EQUAL(c_e.get_lower_x() == static_cast<T>(l_x), true)
+ BOOST_CHECK_EQUAL(detail::almost_equal(c_e.get_center().x(), static_cast<T>(c_x), 10), true); \
+ BOOST_CHECK_EQUAL(detail::almost_equal(c_e.get_center().y(), static_cast<T>(c_y), 10), true); \
+ BOOST_CHECK_EQUAL(detail::almost_equal(c_e.get_lower_x(), static_cast<T>(l_x), 10), true)
// Test for (point, point, point) case.
BOOST_AUTO_TEST_CASE_TEMPLATE(circle_event_creation_ppp_test1, T, test_types) {
@@ -88,24 +88,24 @@
// Test for (point, segment, segment) case.
BOOST_AUTO_TEST_CASE_TEMPLATE(circle_event_creation_pss_test1, T, test_types) {
typedef typename detail::site_event<T> site_event_type;
- point_2d<T> segm1_start(static_cast<T>(0), static_cast<T>(0));
- point_2d<T> segm1_end(static_cast<T>(6), static_cast<T>(0));
+ point_2d<T> segm1_start(static_cast<T>(1), static_cast<T>(0));
+ point_2d<T> segm1_end(static_cast<T>(7), static_cast<T>(0));
site_event_type segm_site1(segm1_start, segm1_end, 0);
segm_site1.set_inverse();
- point_2d<T> segm2_start(static_cast<T>(-3), static_cast<T>(4));
- point_2d<T> segm2_end(static_cast<T>(9), static_cast<T>(4));
+ point_2d<T> segm2_start(static_cast<T>(-2), static_cast<T>(4));
+ point_2d<T> segm2_end(static_cast<T>(10), static_cast<T>(4));
site_event_type segm_site2(segm2_start, segm2_end, 1);
typename detail::circle_event<T> c_event;
- site_event_type site1(static_cast<T>(5), static_cast<T>(2), 2);
+ site_event_type site1(static_cast<T>(6), static_cast<T>(2), 2);
bool is_event = detail::create_circle_event_pss(site1, segm_site1, segm_site2, 3, c_event);
BOOST_CHECK_EQUAL(is_event, true);
- CHECK_CIRCLE_EVENT(c_event, 3, 2, 5);
+ CHECK_CIRCLE_EVENT(c_event, 4, 2, 6);
- site_event_type site2(static_cast<T>(0), static_cast<T>(0), 2);
+ site_event_type site2(static_cast<T>(1), static_cast<T>(0), 2);
is_event = detail::create_circle_event_pss(site2, segm_site1, segm_site2, 2, c_event);
BOOST_CHECK_EQUAL(is_event, true);
- CHECK_CIRCLE_EVENT(c_event, 0, 2, 2);
+ CHECK_CIRCLE_EVENT(c_event, 1, 2, 3);
}
BOOST_AUTO_TEST_CASE_TEMPLATE(circle_event_creation_pss_test2, T, test_types) {
@@ -126,26 +126,26 @@
BOOST_AUTO_TEST_CASE_TEMPLATE(circle_event_creation_pss_test3, T, test_types) {
typedef typename detail::site_event<T> site_event_type;
- point_2d<T> segm1_start(static_cast<T>(0), static_cast<T>(0));
- point_2d<T> segm1_end(static_cast<T>(5), static_cast<T>(0));
+ point_2d<T> segm1_start(static_cast<T>(1), static_cast<T>(0));
+ point_2d<T> segm1_end(static_cast<T>(6), static_cast<T>(0));
site_event_type segm_site1(segm1_start, segm1_end, 0);
segm_site1.set_inverse();
- point_2d<T> segm2_start(static_cast<T>(-7), static_cast<T>(4));
- point_2d<T> segm2_end(static_cast<T>(-1), static_cast<T>(12));
+ point_2d<T> segm2_start(static_cast<T>(-6), static_cast<T>(4));
+ point_2d<T> segm2_end(static_cast<T>(0), static_cast<T>(12));
site_event_type segm_site2(segm2_start, segm2_end, 1);
typename detail::circle_event<T> c_event;
- site_event_type site1(static_cast<T>(0), static_cast<T>(0), 2);
+ site_event_type site1(static_cast<T>(1), static_cast<T>(0), 2);
bool is_event = detail::create_circle_event_pss(site1, segm_site1, segm_site2, 2, c_event);
BOOST_CHECK_EQUAL(is_event, true);
- CHECK_CIRCLE_EVENT(c_event, 0, 5, 5);
+ CHECK_CIRCLE_EVENT(c_event, 1, 5, 6);
}
BOOST_AUTO_TEST_CASE_TEMPLATE(circle_event_creation_pss_test4, T, test_types) {
typedef typename detail::site_event<T> site_event_type;
- point_2d<T> point1(static_cast<T>(0), static_cast<T>(0));
- point_2d<T> point2(static_cast<T>(4), static_cast<T>(0));
- point_2d<T> point3(static_cast<T>(7), static_cast<T>(6));
- point_2d<T> point4(static_cast<T>(-1), static_cast<T>(12));
+ point_2d<T> point1(static_cast<T>(1), static_cast<T>(0));
+ point_2d<T> point2(static_cast<T>(5), static_cast<T>(0));
+ point_2d<T> point3(static_cast<T>(8), static_cast<T>(6));
+ point_2d<T> point4(static_cast<T>(0), static_cast<T>(12));
site_event_type segm_site1(point1, point2, 0);
segm_site1.set_inverse();
site_event_type segm_site2(point3, point4, 1);
@@ -154,7 +154,7 @@
bool is_event = detail::create_circle_event_pss(
point_site, segm_site1, segm_site2, 2, c_event);
BOOST_CHECK_EQUAL(is_event, true);
- CHECK_CIRCLE_EVENT(c_event, 0, 5, 5);
+ CHECK_CIRCLE_EVENT(c_event, 1, 5, 6);
}
// Test for (segment, segment, segment) case.
@@ -176,10 +176,10 @@
BOOST_AUTO_TEST_CASE_TEMPLATE(circle_event_creation_sss_test2, T, test_types) {
typedef typename detail::site_event<T> site_event_type;
- point_2d<T> point1(static_cast<T>(40), static_cast<T>(30));
- point_2d<T> point2(static_cast<T>(0), static_cast<T>(0));
- point_2d<T> point3(static_cast<T>(-40), static_cast<T>(30));
- point_2d<T> point4(static_cast<T>(0), static_cast<T>(60));
+ point_2d<T> point1(static_cast<T>(41), static_cast<T>(30));
+ point_2d<T> point2(static_cast<T>(1), static_cast<T>(0));
+ point_2d<T> point3(static_cast<T>(-39), static_cast<T>(30));
+ point_2d<T> point4(static_cast<T>(1), static_cast<T>(60));
site_event_type segm_site1(point1, point2, 0);
segm_site1.set_inverse();
site_event_type segm_site2(point3, point4, 1);
@@ -187,5 +187,5 @@
typename detail::circle_event<T> c_event;
bool is_event = detail::create_circle_event_sss(segm_site1, segm_site2, segm_site3, c_event);
BOOST_CHECK_EQUAL(is_event, true);
- CHECK_CIRCLE_EVENT(c_event, 0, 30, 24);
+ CHECK_CIRCLE_EVENT(c_event, 1, 30, 25);
}
Copied: sandbox/SOC/2010/sweepline/libs/sweepline/test/clipping_test.cpp (from r66210, /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/clipping_test.cpp 2010-10-27 14:47:57 EDT (Wed, 27 Oct 2010)
@@ -1,4 +1,4 @@
-// Boost sweepline library segment_voronoi_clipping_test.cpp file
+// Boost sweepline library clipping_test.cpp file
// Copyright Andrii Sydorchuk 2010.
// Distributed under the Boost Software License, Version 1.0.
@@ -10,8 +10,8 @@
#include <stdlib.h>
#include <time.h>
-#include "../test_type_list.hpp"
-#include "boost/sweepline/voronoi_segment_sweepline.hpp"
+#include "test_type_list.hpp"
+#include "boost/sweepline/voronoi_sweepline.hpp"
using namespace boost::sweepline;
#define BOOST_TEST_MODULE voronoi_clipping_test
@@ -42,14 +42,14 @@
intersections.clear();
Helper<T>::find_intersections(test_origin, test_direction1_2,
- Helper<T>::SEGMENT, test_rect, intersections);
+ 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();
Helper<T>::find_intersections(test_origin, test_direction1_3,
- Helper<T>::SEGMENT, test_rect, intersections);
+ Helper<T>::SEGMENT, test_rect, intersections);
BOOST_CHECK_EQUAL(intersections.empty(), true);
intersections.clear();
Copied: sandbox/SOC/2010/sweepline/libs/sweepline/test/event_queue_test.cpp (from r66210, /sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_segment/segment_event_queue_test.cpp)
==============================================================================
--- /sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_segment/segment_event_queue_test.cpp (original)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/test/event_queue_test.cpp 2010-10-27 14:47:57 EDT (Wed, 27 Oct 2010)
@@ -1,4 +1,4 @@
-// Boost sweepline library segment_event_queue_test.cpp file
+// Boost sweepline library event_queue_test.cpp file
// Copyright Andrii Sydorchuk 2010.
// Distributed under the Boost Software License, Version 1.0.
@@ -9,8 +9,8 @@
#include <cmath>
-#include "../test_type_list.hpp"
-#include "boost/sweepline/voronoi_segment_sweepline.hpp"
+#include "test_type_list.hpp"
+#include "boost/sweepline/voronoi_sweepline.hpp"
using namespace boost::sweepline;
#define BOOST_TEST_MODULE event_queue_test
Copied: sandbox/SOC/2010/sweepline/libs/sweepline/test/event_types_test.cpp (from r66210, /sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_segment/segment_event_types_test.cpp)
==============================================================================
--- /sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_segment/segment_event_types_test.cpp (original)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/test/event_types_test.cpp 2010-10-27 14:47:57 EDT (Wed, 27 Oct 2010)
@@ -1,4 +1,4 @@
-// Boost sweepline library segment_event_types_test.cpp file
+// Boost sweepline library event_types_test.cpp file
// Copyright Andrii Sydorchuk 2010.
// Distributed under the Boost Software License, Version 1.0.
@@ -7,8 +7,8 @@
// See http://www.boost.org for updates, documentation, and revision history.
-#include "../test_type_list.hpp"
-#include "boost/sweepline/voronoi_segment_sweepline.hpp"
+#include "test_type_list.hpp"
+#include "boost/sweepline/voronoi_sweepline.hpp"
using namespace boost::sweepline;
using namespace boost::sweepline::detail;
Copied: sandbox/SOC/2010/sweepline/libs/sweepline/test/node_comparer_test.cpp (from r66210, /sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_segment/segment_node_comparer_test.cpp)
==============================================================================
--- /sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_segment/segment_node_comparer_test.cpp (original)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/test/node_comparer_test.cpp 2010-10-27 14:47:57 EDT (Wed, 27 Oct 2010)
@@ -1,4 +1,4 @@
-// Boost sweepline library segment_node_comparer_test.cpp file
+// Boost sweepline library node_comparer_test.cpp file
// Copyright Andrii Sydorchuk 2010.
// Distributed under the Boost Software License, Version 1.0.
@@ -7,8 +7,8 @@
// See http://www.boost.org for updates, documentation, and revision history.
-#include "../test_type_list.hpp"
-#include "boost/sweepline/voronoi_segment_sweepline.hpp"
+#include "test_type_list.hpp"
+#include "boost/sweepline/voronoi_sweepline.hpp"
using namespace boost::sweepline;
using namespace boost::sweepline::detail;
Copied: sandbox/SOC/2010/sweepline/libs/sweepline/test/output_verification.hpp (from r66210, /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/output_verification.hpp 2010-10-27 14:47:57 EDT (Wed, 27 Oct 2010)
@@ -1,4 +1,4 @@
-// Boost sweepline library voronoi_output_verification.hpp file
+// Boost sweepline library output_verification.hpp file
// Copyright Andrii Sydorchuk 2010.
// Distributed under the Boost Software License, Version 1.0.
Copied: sandbox/SOC/2010/sweepline/libs/sweepline/test/predicates_test.cpp (from r66210, /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/predicates_test.cpp 2010-10-27 14:47:57 EDT (Wed, 27 Oct 2010)
@@ -1,4 +1,4 @@
-// Boost sweepline library segment_predicates_test.cpp file
+// Boost sweepline library predicates_test.cpp file
// Copyright Andrii Sydorchuk 2010.
// Distributed under the Boost Software License, Version 1.0.
@@ -7,8 +7,8 @@
// See http://www.boost.org for updates, documentation, and revision history.
-#include "../test_type_list.hpp"
-#include "boost/sweepline/voronoi_segment_sweepline.hpp"
+#include "test_type_list.hpp"
+#include "boost/sweepline/voronoi_sweepline.hpp"
using namespace boost::sweepline;
#define BOOST_TEST_MODULE predicates_test
@@ -283,29 +283,3 @@
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
Copied: sandbox/SOC/2010/sweepline/libs/sweepline/test/sweepline_test.cpp (from r66210, /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/sweepline_test.cpp 2010-10-27 14:47:57 EDT (Wed, 27 Oct 2010)
@@ -1,4 +1,4 @@
-// Boost sweepline library segment_voronoi_builder_test.cpp file
+// Boost sweepline library builder_test.cpp file
// Copyright Andrii Sydorchuk 2010.
// Distributed under the Boost Software License, Version 1.0.
@@ -10,9 +10,9 @@
#include <stdlib.h>
#include <time.h>
-#include "../test_type_list.hpp"
-#include "../voronoi_output_verification.hpp"
-#include "boost/sweepline/voronoi_segment_sweepline.hpp"
+#include "test_type_list.hpp"
+#include "output_verification.hpp"
+#include "boost/sweepline/voronoi_sweepline.hpp"
using namespace boost::sweepline;
#define BOOST_TEST_MODULE voronoi_builder_test
@@ -24,6 +24,10 @@
#define VERIFY_VORONOI_OUTPUT(output, mask) BOOST_CHECK_EQUAL(verify_output(output, mask), true)
+#define ALMOST_EQUAL_TEST(a, b, ULP_ERR, ABS_ERR) \
+ BOOST_CHECK_EQUAL(detail::almost_equal(a, b, ULP_ERR) || \
+ detail::abs_equal(a, b, ABS_ERR), true);
+
// Sites: (0, 0).
BOOST_AUTO_TEST_CASE_TEMPLATE(single_site_test, T, test_types) {
typedef T coordinate_type;
@@ -316,7 +320,7 @@
}
// Sites: (0, 0), (0, 1), (1, 0), (1, 1).
-BOOST_AUTO_TEST_CASE_TEMPLATE(square_test3, T, test_types) {
+BOOST_AUTO_TEST_CASE_TEMPLATE(square_test1, T, test_types) {
typedef T coordinate_type;
typedef typename voronoi_output_clipped<coordinate_type>::voronoi_edge_type voronoi_edge_type;
typedef typename voronoi_output_clipped<coordinate_type>::voronoi_vertex_const_iterator_type
@@ -454,6 +458,7 @@
BOOST_CHECK_EQUAL(test_output.num_edge_records, 2112);
}
+#ifndef _DEBUG
// Sites: {(x, y) | x = 0 .. 100, y = 0 .. 100}.
BOOST_AUTO_TEST_CASE_TEMPLATE(grid_test4, T, test_types) {
typedef T coordinate_type;
@@ -474,7 +479,9 @@
BOOST_CHECK_EQUAL(test_output.num_vertex_records, 9801);
BOOST_CHECK_EQUAL(test_output.num_edge_records, 19800);
}
+#endif
+#ifndef _DEBUG
// Sites: {(x, y) | x = 0 .. 333, y = 0 .. 333}.
BOOST_AUTO_TEST_CASE_TEMPLATE(grid_test5, T, test_types) {
typedef T coordinate_type;
@@ -495,7 +502,9 @@
BOOST_CHECK_EQUAL(test_output.num_vertex_records, 110224);
BOOST_CHECK_EQUAL(test_output.num_edge_records, 221112);
}
+#endif
+#ifndef _DEBUG
// Generate 10 random sites 10000 times.
BOOST_AUTO_TEST_CASE_TEMPLATE(random_test1, T, test_types) {
typedef T coordinate_type;
@@ -516,7 +525,9 @@
test_beach_line.reset();
}
}
+#endif
+#ifndef _DEBUG
// Generate 100 random sites 1000 times.
BOOST_AUTO_TEST_CASE_TEMPLATE(random_test2, T, test_types) {
typedef T coordinate_type;
@@ -537,7 +548,9 @@
test_beach_line.reset();
}
}
+#endif
+#ifndef _DEBUG
// Generate 1000 random sites 100 times.
BOOST_AUTO_TEST_CASE_TEMPLATE(random_test3, T, test_types) {
typedef T coordinate_type;
@@ -558,7 +571,9 @@
test_beach_line.reset();
}
}
+#endif
+#ifndef _DEBUG
// Generate 10000 random sites 10 times.
BOOST_AUTO_TEST_CASE_TEMPLATE(random_test4, T, test_types) {
typedef T coordinate_type;
@@ -579,7 +594,9 @@
test_beach_line.reset();
}
}
+#endif
+#ifndef _DEBUG
// Generate 100000 random sites.
BOOST_AUTO_TEST_CASE_TEMPLATE(random_test5, T, test_types) {
typedef T coordinate_type;
@@ -600,7 +617,9 @@
test_beach_line.reset();
}
}
+#endif
+#ifndef _DEBUG
// Generate 1000000 random sites.
BOOST_AUTO_TEST_CASE_TEMPLATE(random_test6, T, test_types) {
typedef T coordinate_type;
@@ -621,6 +640,45 @@
test_beach_line.reset();
}
}
+#endif
+
+#ifndef _DEBUG
+BOOST_AUTO_TEST_CASE_TEMPLATE(random_test7, T, test_types) {
+ typedef typename voronoi_output_clipped<T>::voronoi_vertex_const_iterator_type
+ voronoi_vertex_const_iterator_type;
+ srand(static_cast<unsigned int>(time(NULL)));
+ voronoi_builder<T> test_builder;
+ voronoi_output_clipped<T> test_output_small, test_output_large;
+ std::vector< point_2d<T> > points_small, points_large;
+ int num_points = 27;
+ int half_num_points = num_points >> 1;
+ int koef = std::numeric_limits<int>::max() / half_num_points;
+ for (int i = 0; i < 10000; i++) {
+ points_small.clear();
+ points_large.clear();
+ for (int j = 0; j < num_points; j++) {
+ T x_small = static_cast<T>(rand() % num_points - half_num_points);
+ T y_small = static_cast<T>(rand() % num_points - half_num_points);
+ T x_large = x_small * koef;
+ T y_large = y_small * koef;
+ points_small.push_back(make_point_2d(x_small, y_small));
+ points_large.push_back(make_point_2d(x_large, y_large));
+ }
+ test_builder.init(points_small);
+ test_builder.run_sweepline();
+ test_builder.clip(test_output_small);
+ test_builder.init(points_large);
+ test_builder.run_sweepline();
+ test_builder.clip(test_output_large);
+ VERIFY_VORONOI_OUTPUT(test_output_small, COMPLETE_VERIFICATION);
+ VERIFY_VORONOI_OUTPUT(test_output_large, COMPLETE_VERIFICATION);
+ BOOST_CHECK_EQUAL(test_output_small.num_cell_records, test_output_large.num_cell_records);
+ BOOST_CHECK_EQUAL(test_output_small.num_vertex_records, test_output_large.num_vertex_records);
+ BOOST_CHECK_EQUAL(test_output_small.num_edge_records, test_output_large.num_edge_records);
+ test_builder.reset();
+ }
+}
+#endif
BOOST_AUTO_TEST_CASE_TEMPLATE(segment_sites_test1, T, test_types) {
typedef T coordinate_type;
Deleted: sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_output_verification.hpp
==============================================================================
--- sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_output_verification.hpp 2010-10-27 14:47:57 EDT (Wed, 27 Oct 2010)
+++ (empty file)
@@ -1,192 +0,0 @@
-// Boost sweepline library voronoi_output_verification.hpp file
-
-// Copyright Andrii Sydorchuk 2010.
-// Distributed under the Boost Software License, Version 1.0.
-// (See accompanying file LICENSE_1_0.txt or copy at
-// http://www.boost.org/LICENSE_1_0.txt)
-
-// See http://www.boost.org for updates, documentation, and revision history.
-
-#ifndef VORONOI_OUTPUT_VERIFICATION
-#define VORONOI_OUTPUT_VERIFICATION
-
-#include <map>
-#include <vector>
-
-enum kOrientation {
- RIGHT_ORIENTATION = -1,
- COLLINEAR = 0,
- LEFT_ORIENTATION = 1,
-};
-
-template <typename Point2D>
-kOrientation get_orientation(const Point2D &point1,
- const Point2D &point2,
- const Point2D &point3) {
- typename Point2D::coordinate_type a = (point2.x() - point1.x()) * (point3.y() - point2.y());
- typename Point2D::coordinate_type b = (point2.y() - point1.y()) * (point3.x() - point2.x());
- if (a == b)
- return COLLINEAR;
- return (a < b) ? RIGHT_ORIENTATION : LEFT_ORIENTATION;
-}
-
-template <typename Output>
-bool verify_half_edge_orientation(const Output &output) {
- typedef typename Output::Point2D Point2D;
- 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_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;
- }
- }
- return true;
-}
-
-template <typename Output>
-bool verify_cell_convexity(const Output &output) {
- typedef typename Output::Point2D Point2D;
- 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)
- return false;
- if (edge->cell != &(*cell_it))
- return false;
- if (edge->start_point != NULL &&
- edge->end_point != NULL &&
- edge->end_point == edge->next->start_point &&
- edge->next->end_point != NULL) {
- const Point2D &vertex1 = edge->start_point->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;
- }
- edge = edge->next;
- } while(edge != cell_it->incident_edge);
- }
- return true;
-}
-
-template <typename Output>
-bool verify_incident_edges_ccw_order(const Output &output) {
- typedef typename Output::Point2D Point2D;
- 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::voronoi_edge_type *edge = vertex_it->incident_edge;
- do {
- 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;
-
- edge = edge->rot_next;
- } while (edge != vertex_it->incident_edge);
- }
- return true;
-}
-
-template <typename Output>
-bool verfiy_no_half_edge_intersections(const Output &output) {
- // Create map from edges with first point less than the second one.
- // Key is the first point of the edge, value is a vector of second points
- // with the same first point.
- typedef typename Output::Point2D Point2D;
- std::map< Point2D, std::vector<Point2D> > edge_map;
- typedef typename std::map< Point2D, std::vector<Point2D> >::const_iterator
- edge_map_iterator;
- 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->vertex;
- const Point2D &end_point = edge_it->end_point->vertex;
- if (start_point < end_point)
- edge_map[start_point].push_back(end_point);
- }
- }
-
- // Iterate over map of edges and check if there are any intersections.
- // All the edges are stored by the low x value. That's why we iterate
- // left to right checking for intersections between all pairs of edges
- // that overlap in the x dimension.
- // Complexity. Approximately N*sqrt(N). Worst case N^2.
- typedef typename std::vector<Point2D>::size_type size_type;
- edge_map_iterator edge_map_it1, edge_map_it2, edge_map_it_bound;
- for (edge_map_it1 = edge_map.begin();
- edge_map_it1 != edge_map.end(); edge_map_it1++) {
- const Point2D &point1 = edge_map_it1->first;
- for (size_type i = 0; i < edge_map_it1->second.size(); i++) {
- const Point2D &point2 = edge_map_it1->second[i];
- typename Output::coordinate_type min_y1 = std::min(point1.y(), point2.y());
- typename Output::coordinate_type max_y1 = std::max(point1.y(), point2.y());
-
- // Find the first edge with greater or equal first point.
- edge_map_it_bound = edge_map.lower_bound(point2);
-
- edge_map_it2 = edge_map_it1;
- edge_map_it2++;
- for (; edge_map_it2 != edge_map_it_bound; edge_map_it2++) {
- const Point2D &point3 = edge_map_it2->first;
- for (size_type j = 0; j < edge_map_it2->second.size(); j++) {
- const Point2D &point4 = edge_map_it2->second[j];
- typename Output::coordinate_type min_y2 = std::min(point3.y(), point4.y());
- typename Output::coordinate_type max_y2 = std::max(point3.y(), point4.y());
-
- // In most cases it is enought to make
- // simple intersection check in the y dimension.
- if (!(max_y1 > min_y2 && max_y2 > min_y1))
- continue;
-
- // Intersection check.
- if (get_orientation(point1, point2, point3) *
- get_orientation(point1, point2, point4) == -1 &&
- get_orientation(point3, point4, point1) *
- get_orientation(point3, point4, point2) == -1)
- return false;
- }
- }
- }
- }
- return true;
-}
-
-enum kVerification {
- HALF_EDGE_ORIENTATION = 1,
- CELL_CONVEXITY = 2,
- INCIDENT_EDGES_CCW_ORDER = 4,
- NO_HALF_EDGE_INTERSECTIONS = 8,
- FAST_VERIFICATION = 7,
- COMPLETE_VERIFICATION = 15,
-};
-
-template <typename Output>
-bool verify_output(const Output &output, kVerification mask) {
- bool result = true;
- if (mask & HALF_EDGE_ORIENTATION)
- result &= verify_half_edge_orientation(output);
- if (mask & CELL_CONVEXITY)
- result &= verify_cell_convexity(output);
- if (mask & INCIDENT_EDGES_CCW_ORDER)
- result &= verify_incident_edges_ccw_order(output);
- if (mask & NO_HALF_EDGE_INTERSECTIONS)
- result &= verfiy_no_half_edge_intersections(output);
- return result;
-}
-
-#endif