Boost logo

Boost-Commit :

Subject: [Boost-commit] svn:boost r74922 - sandbox/gtl/libs/polygon/test
From: sydorchuk.andriy_at_[hidden]
Date: 2011-10-11 18:21:43


Author: asydorchuk
Date: 2011-10-11 18:21:42 EDT (Tue, 11 Oct 2011)
New Revision: 74922
URL: http://svn.boost.org/trac/boost/changeset/74922

Log:
Integrated voronoi_builder test.
Added:
   sandbox/gtl/libs/polygon/test/voronoi_builder_test.cpp (contents, props changed)
   sandbox/gtl/libs/polygon/test/voronoi_test_helper.hpp (contents, props changed)
Text files modified:
   sandbox/gtl/libs/polygon/test/Jamfile.v2 | 5 +++--
   sandbox/gtl/libs/polygon/test/voronoi_internal_structures_test.cpp | 2 +-
   2 files changed, 4 insertions(+), 3 deletions(-)

Modified: sandbox/gtl/libs/polygon/test/Jamfile.v2
==============================================================================
--- sandbox/gtl/libs/polygon/test/Jamfile.v2 (original)
+++ sandbox/gtl/libs/polygon/test/Jamfile.v2 2011-10-11 18:21:42 EDT (Tue, 11 Oct 2011)
@@ -18,7 +18,7 @@
 
 alias "polygon-unit"
     :
- [ run gtl_boost_unit_test.cpp ]
+ [ run gtl_boost_unit_test.cpp ]
     ;
 
 alias "benchmark"
@@ -28,7 +28,8 @@
 
 alias "voronoi-unit"
     :
- [ run voronoi_internal_structures_test.cpp ]
+ [ run voronoi_internal_structures_test.cpp ]
+ [ run voronoi_builder_test.cpp ]
     ;
 
 

Added: sandbox/gtl/libs/polygon/test/voronoi_builder_test.cpp
==============================================================================
--- (empty file)
+++ sandbox/gtl/libs/polygon/test/voronoi_builder_test.cpp 2011-10-11 18:21:42 EDT (Tue, 11 Oct 2011)
@@ -0,0 +1,671 @@
+// Boost.Polygon library voronoi_builder_test.cpp file
+
+// Copyright Andrii Sydorchuk 2010-2011.
+// Distributed under the Boost Software License, Version 1.0.
+// (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+// See http://www.boost.org for updates, documentation, and revision history.
+
+#include <ctime>
+
+#define BOOST_TEST_MODULE voronoi_builder_test
+#include <boost/mpl/list.hpp>
+#include <boost/random/mersenne_twister.hpp>
+#include <boost/test/test_case_template.hpp>
+
+#include "boost/polygon/voronoi.hpp"
+using namespace boost::polygon;
+#include "voronoi_test_helper.hpp"
+
+typedef boost::mpl::list<int> test_types;
+
+#define CHECK_EQUAL_POINTS(p1, p2) \
+ BOOST_CHECK_EQUAL(p1.x() == static_cast<T>(p2.x()), true); \
+ BOOST_CHECK_EQUAL(p1.y() == static_cast<T>(p2.y()), true)
+
+#define CHECK_BRECT(brect, xmin, ymin, xmax, ymax) \
+ BOOST_CHECK_EQUAL(brect.x_min() == static_cast<coordinate_type>(xmin), true); \
+ BOOST_CHECK_EQUAL(brect.y_min() == static_cast<coordinate_type>(ymin), true); \
+ BOOST_CHECK_EQUAL(brect.x_max() == static_cast<coordinate_type>(xmax), true); \
+ BOOST_CHECK_EQUAL(brect.y_max() == static_cast<coordinate_type>(ymax), true)
+
+#define CHECK_OUTPUT_SIZE(output, cells, vertices, edges) \
+ BOOST_CHECK_EQUAL(output.cell_records().size() == static_cast<unsigned int>(cells), true); \
+ BOOST_CHECK_EQUAL(output.num_cell_records() == cells, true); \
+ BOOST_CHECK_EQUAL(output.vertex_records().size() == static_cast<unsigned int>(vertices), true); \
+ BOOST_CHECK_EQUAL(output.num_vertex_records() == vertices, true); \
+ BOOST_CHECK_EQUAL(output.edge_records().size() == static_cast<unsigned int>(edges << 1), true); \
+ BOOST_CHECK_EQUAL(output.num_edge_records() == edges, true)
+
+#define VERIFY_OUTPUT(output) \
+ BOOST_CHECK_EQUAL(voronoi_test_helper::verify_output(output, \
+ voronoi_test_helper::HALF_EDGE_ORIENTATION), true); \
+ BOOST_CHECK_EQUAL(voronoi_test_helper::verify_output(output, \
+ voronoi_test_helper::CELL_CONVEXITY), true); \
+ BOOST_CHECK_EQUAL(voronoi_test_helper::verify_output(output, \
+ voronoi_test_helper::INCIDENT_EDGES_CCW_ORDER), true); \
+ BOOST_CHECK_EQUAL(voronoi_test_helper::verify_output(output, \
+ voronoi_test_helper::NO_HALF_EDGE_INTERSECTIONS), true)
+
+#define VERIFY_NO_HALF_EDGE_INTERSECTIONS(output) \
+ BOOST_CHECK_EQUAL(voronoi_test_helper::verify_output(output, \
+ voronoi_test_helper::NO_HALF_EDGE_INTERSECTIONS), true)
+
+// Sites: (0, 0).
+BOOST_AUTO_TEST_CASE_TEMPLATE(single_site_test, T, test_types) {
+ typedef double coordinate_type;
+ typedef typename voronoi_diagram<coordinate_type>::voronoi_cell_const_iterator_type
+ voronoi_cell_const_iterator_type;
+
+ std::vector< point_data<T> > points;
+ points.push_back(point_data<T>(0, 0));
+ voronoi_diagram<coordinate_type> test_output;
+ construct_voronoi_points<T>(points, test_output);
+ VERIFY_OUTPUT(test_output);
+
+ CHECK_BRECT(test_output.bounding_rectangle(), 0, 0, 0, 0);
+ CHECK_OUTPUT_SIZE(test_output, 1, 0, 0);
+
+ voronoi_cell_const_iterator_type it = test_output.cell_records().begin();
+ BOOST_CHECK_EQUAL(it->num_incident_edges(), 0);
+ BOOST_CHECK_EQUAL(it->incident_edge() == NULL, true);
+}
+
+// Sites: (0, 0), (0, 1).
+BOOST_AUTO_TEST_CASE_TEMPLATE(collinear_sites_test1, T, test_types) {
+ typedef double coordinate_type;
+ typedef typename voronoi_diagram<coordinate_type>::voronoi_edge_type voronoi_edge_type;
+ typedef typename voronoi_diagram<coordinate_type>::voronoi_cell_const_iterator_type
+ voronoi_cell_const_iterator_type;
+
+ std::vector< point_data<T> > points;
+ points.push_back(point_data<T>(0, 0));
+ points.push_back(point_data<T>(0, 1));
+ voronoi_diagram<coordinate_type> test_output;
+ construct_voronoi_points<T>(points, test_output);
+ VERIFY_OUTPUT(test_output);
+
+ CHECK_BRECT(test_output.bounding_rectangle(), 0, 0, 0, 1);
+ CHECK_OUTPUT_SIZE(test_output, 2, 0, 1);
+
+ voronoi_cell_const_iterator_type cell_it = test_output.cell_records().begin();
+ BOOST_CHECK_EQUAL(cell_it->num_incident_edges(), 1);
+ cell_it++;
+ BOOST_CHECK_EQUAL(cell_it->num_incident_edges(), 1);
+
+ const voronoi_edge_type *edge1_1 = cell_it->incident_edge();
+ const voronoi_edge_type *edge1_2 = edge1_1->twin();
+
+ BOOST_CHECK_EQUAL(edge1_1->twin() == edge1_2, true);
+ BOOST_CHECK_EQUAL(edge1_2->twin() == edge1_1, true);
+
+ BOOST_CHECK_EQUAL(edge1_1->next() == edge1_1, true);
+ BOOST_CHECK_EQUAL(edge1_1->prev() == edge1_1, true);
+ BOOST_CHECK_EQUAL(edge1_1->rot_next() == NULL, true);
+ BOOST_CHECK_EQUAL(edge1_1->rot_prev() == NULL, true);
+
+ BOOST_CHECK_EQUAL(edge1_2->next() == edge1_2, true);
+ BOOST_CHECK_EQUAL(edge1_2->prev() == edge1_2, true);
+ BOOST_CHECK_EQUAL(edge1_2->rot_next() == NULL, true);
+ BOOST_CHECK_EQUAL(edge1_2->rot_prev() == NULL, true);
+}
+
+// Sites: (0, 0), (1, 1), (2, 2).
+BOOST_AUTO_TEST_CASE_TEMPLATE(collinear_sites_test2, T, test_types) {
+ typedef double coordinate_type;
+ typedef typename voronoi_diagram<coordinate_type>::voronoi_edge_type voronoi_edge_type;
+ typedef typename voronoi_diagram<coordinate_type>::voronoi_cell_const_iterator_type
+ voronoi_cell_const_iterator_type;
+
+ std::vector< point_data<T> > points;
+ points.push_back(point_data<T>(0, 0));
+ points.push_back(point_data<T>(1, 1));
+ points.push_back(point_data<T>(2, 2));
+ voronoi_diagram<coordinate_type> test_output;
+ construct_voronoi_points<T>(points, test_output);
+ VERIFY_OUTPUT(test_output);
+
+ CHECK_BRECT(test_output.bounding_rectangle(), 0, 0, 2, 2);
+ CHECK_OUTPUT_SIZE(test_output, 3, 0, 2);
+
+ voronoi_cell_const_iterator_type cell_it = test_output.cell_records().begin();
+ BOOST_CHECK_EQUAL(cell_it->num_incident_edges(), 1);
+ const voronoi_edge_type *edge1_1 = cell_it->incident_edge();
+ const voronoi_edge_type *edge1_2 = edge1_1->twin();
+ cell_it++;
+ BOOST_CHECK_EQUAL(cell_it->num_incident_edges(), 2);
+ cell_it++;
+ BOOST_CHECK_EQUAL(cell_it->num_incident_edges(), 1);
+ const voronoi_edge_type *edge2_2 = cell_it->incident_edge();
+ const voronoi_edge_type *edge2_1 = edge2_2->twin();
+
+ BOOST_CHECK_EQUAL(edge1_1->twin() == edge1_2 && edge1_2->twin() == edge1_1, true);
+ BOOST_CHECK_EQUAL(edge2_1->twin() == edge2_2 && edge2_2->twin() == edge2_1, true);
+
+ BOOST_CHECK_EQUAL(edge1_1->next() == edge1_1 && edge1_1->prev() == edge1_1, true);
+ BOOST_CHECK_EQUAL(edge1_1->rot_next() == NULL && edge1_1->rot_prev() == NULL, true);
+ BOOST_CHECK_EQUAL(edge1_2->rot_next() == NULL && edge1_2->rot_prev() == NULL, true);
+ BOOST_CHECK_EQUAL(edge2_1->rot_next() == NULL && edge2_1->rot_prev() == NULL, true);
+ BOOST_CHECK_EQUAL(edge2_2->next() == edge2_2 && edge2_2->prev() == edge2_2, true);
+ BOOST_CHECK_EQUAL(edge2_2->rot_next() == NULL && edge2_2->rot_prev() == NULL, true);
+
+ BOOST_CHECK_EQUAL(edge1_2->next() == edge2_1 && edge1_2->prev() == edge2_1, true);
+ BOOST_CHECK_EQUAL(edge2_1->next() == edge1_2 && edge2_1->prev() == edge1_2, true);
+}
+
+// Sites: (0, 0), (0, 4), (2, 1).
+BOOST_AUTO_TEST_CASE_TEMPLATE(triangle_test1, T, test_types) {
+ typedef double coordinate_type;
+ typedef typename voronoi_diagram<coordinate_type>::voronoi_edge_type voronoi_edge_type;
+ typedef typename voronoi_diagram<coordinate_type>::voronoi_vertex_const_iterator_type
+ voronoi_vertex_const_iterator_type;
+
+ point_data<T> point1(0, 0);
+ point_data<T> point2(0, 4);
+ point_data<T> point3(2, 1);
+ std::vector< point_data<T> > points;
+ points.push_back(point1);
+ points.push_back(point2);
+ points.push_back(point3);
+ voronoi_diagram<coordinate_type> test_output;
+ construct_voronoi_points<T>(points, test_output);
+ VERIFY_OUTPUT(test_output);
+
+ CHECK_BRECT(test_output.bounding_rectangle(), 0, 0, 2, 4);
+ CHECK_OUTPUT_SIZE(test_output, 3, 1, 3);
+
+ voronoi_vertex_const_iterator_type it = test_output.vertex_records().begin();
+ BOOST_CHECK_EQUAL(it->vertex().x() == static_cast<coordinate_type>(0.25) &&
+ it->vertex().y() == static_cast<coordinate_type>(2.0), true);
+
+ const voronoi_edge_type *edge1_1 = it->incident_edge();
+ const voronoi_edge_type *edge1_2 = edge1_1->twin();
+ CHECK_EQUAL_POINTS(edge1_1->cell()->point0(), point3);
+ CHECK_EQUAL_POINTS(edge1_2->cell()->point0(), point1);
+
+ const voronoi_edge_type *edge2_1 = edge1_1->rot_prev();
+ const voronoi_edge_type *edge2_2 = edge2_1->twin();
+ CHECK_EQUAL_POINTS(edge2_1->cell()->point0(), point1);
+ CHECK_EQUAL_POINTS(edge2_2->cell()->point0(), point2);
+
+ const voronoi_edge_type *edge3_1 = edge2_1->rot_prev();
+ const voronoi_edge_type *edge3_2 = edge3_1->twin();
+ CHECK_EQUAL_POINTS(edge3_1->cell()->point0(), point2);
+ CHECK_EQUAL_POINTS(edge3_2->cell()->point0(), point3);
+
+ BOOST_CHECK_EQUAL(edge1_2->twin() == edge1_1, true);
+ BOOST_CHECK_EQUAL(edge2_2->twin() == edge2_1, true);
+ BOOST_CHECK_EQUAL(edge3_2->twin() == edge3_1, true);
+
+ BOOST_CHECK_EQUAL(edge1_1->prev() == edge3_2 && edge1_1->next() == edge3_2, true);
+ BOOST_CHECK_EQUAL(edge2_1->prev() == edge1_2 && edge2_1->next() == edge1_2, true);
+ BOOST_CHECK_EQUAL(edge3_1->prev() == edge2_2 && edge3_1->next() == edge2_2, true);
+
+ BOOST_CHECK_EQUAL(edge1_2->next() == edge2_1 && edge1_2->prev() == edge2_1, true);
+ BOOST_CHECK_EQUAL(edge2_2->next() == edge3_1 && edge2_2->prev() == edge3_1, true);
+ BOOST_CHECK_EQUAL(edge3_2->next() == edge1_1 && edge3_2->prev() == edge1_1, true);
+
+ BOOST_CHECK_EQUAL(edge1_1->rot_next() == edge3_1, true);
+ BOOST_CHECK_EQUAL(edge3_1->rot_next() == edge2_1, true);
+ BOOST_CHECK_EQUAL(edge2_1->rot_next() == edge1_1, true);
+}
+
+// Sites: (0, 1), (2, 0), (2, 4).
+BOOST_AUTO_TEST_CASE_TEMPLATE(triangle_test2, T, test_types) {
+ typedef double coordinate_type;
+ typedef typename voronoi_diagram<coordinate_type>::voronoi_edge_type voronoi_edge_type;
+ typedef typename voronoi_diagram<coordinate_type>::voronoi_vertex_const_iterator_type
+ voronoi_vertex_const_iterator_type;
+
+ point_data<T> point1(0, 1);
+ point_data<T> point2(2, 0);
+ point_data<T> point3(2, 4);
+ std::vector< point_data<T> > points;
+ points.push_back(point1);
+ points.push_back(point2);
+ points.push_back(point3);
+ voronoi_diagram<coordinate_type> test_output;
+ construct_voronoi_points<T>(points, test_output);
+ VERIFY_OUTPUT(test_output);
+
+ CHECK_BRECT(test_output.bounding_rectangle(), 0, 0, 2, 4);
+ CHECK_OUTPUT_SIZE(test_output, 3, 1, 3);
+
+ voronoi_vertex_const_iterator_type it = test_output.vertex_records().begin();
+ BOOST_CHECK_EQUAL(it->vertex().x() == static_cast<coordinate_type>(1.75) &&
+ it->vertex().y() == static_cast<coordinate_type>(2.0), true);
+
+ const voronoi_edge_type *edge1_1 = it->incident_edge();
+ const voronoi_edge_type *edge1_2 = edge1_1->twin();
+ CHECK_EQUAL_POINTS(edge1_1->cell()->point0(), point2);
+ CHECK_EQUAL_POINTS(edge1_2->cell()->point0(), point1);
+
+ const voronoi_edge_type *edge2_1 = edge1_1->rot_prev();
+ const voronoi_edge_type *edge2_2 = edge2_1->twin();
+ CHECK_EQUAL_POINTS(edge2_1->cell()->point0(), point1);
+ CHECK_EQUAL_POINTS(edge2_2->cell()->point0(), point3);
+
+ const voronoi_edge_type *edge3_1 = edge2_1->rot_prev();
+ const voronoi_edge_type *edge3_2 = edge3_1->twin();
+ CHECK_EQUAL_POINTS(edge3_1->cell()->point0(), point3);
+ CHECK_EQUAL_POINTS(edge3_2->cell()->point0(), point2);
+
+ BOOST_CHECK_EQUAL(edge1_2->twin() == edge1_1, true);
+ BOOST_CHECK_EQUAL(edge2_2->twin() == edge2_1, true);
+ BOOST_CHECK_EQUAL(edge3_2->twin() == edge3_1, true);
+
+ BOOST_CHECK_EQUAL(edge1_1->prev() == edge3_2 && edge1_1->next() == edge3_2, true);
+ BOOST_CHECK_EQUAL(edge2_1->prev() == edge1_2 && edge2_1->next() == edge1_2, true);
+ BOOST_CHECK_EQUAL(edge3_1->prev() == edge2_2 && edge3_1->next() == edge2_2, true);
+
+ BOOST_CHECK_EQUAL(edge1_2->next() == edge2_1 && edge1_2->prev() == edge2_1, true);
+ BOOST_CHECK_EQUAL(edge2_2->next() == edge3_1 && edge2_2->prev() == edge3_1, true);
+ BOOST_CHECK_EQUAL(edge3_2->next() == edge1_1 && edge3_2->prev() == edge1_1, true);
+
+ BOOST_CHECK_EQUAL(edge1_1->rot_next() == edge3_1, true);
+ BOOST_CHECK_EQUAL(edge3_1->rot_next() == edge2_1, true);
+ BOOST_CHECK_EQUAL(edge2_1->rot_next() == edge1_1, true);
+}
+
+// Sites: (0, 0), (0, 1), (1, 0), (1, 1).
+BOOST_AUTO_TEST_CASE_TEMPLATE(square_test1, T, test_types) {
+ typedef double coordinate_type;
+ typedef typename voronoi_diagram<coordinate_type>::voronoi_edge_type voronoi_edge_type;
+ typedef typename voronoi_diagram<coordinate_type>::voronoi_vertex_const_iterator_type
+ voronoi_vertex_const_iterator_type;
+
+ point_data<T> point1(0, 0);
+ point_data<T> point2(0, 1);
+ point_data<T> point3(1, 0);
+ point_data<T> point4(1, 1);
+ std::vector< point_data<T> > points;
+ points.push_back(point1);
+ points.push_back(point2);
+ points.push_back(point3);
+ points.push_back(point4);
+ voronoi_diagram<coordinate_type> test_output;
+ construct_voronoi_points<T>(points, test_output);
+ VERIFY_OUTPUT(test_output);
+
+ CHECK_BRECT(test_output.bounding_rectangle(), 0, 0, 1, 1);
+ CHECK_OUTPUT_SIZE(test_output, 4, 1, 4);
+
+ // Check voronoi vertex.
+ voronoi_vertex_const_iterator_type it = test_output.vertex_records().begin();
+ BOOST_CHECK_EQUAL(it->vertex().x() == static_cast<coordinate_type>(0.5) &&
+ it->vertex().y() == static_cast<coordinate_type>(0.5), true);
+
+ // Check voronoi edges.
+ const voronoi_edge_type *edge1_1 = it->incident_edge();
+ const voronoi_edge_type *edge1_2 = edge1_1->twin();
+ CHECK_EQUAL_POINTS(edge1_1->cell()->point0(), points[1]);
+ CHECK_EQUAL_POINTS(edge1_2->cell()->point0(), points[3]);
+
+ const voronoi_edge_type *edge2_1 = edge1_1->rot_prev();
+ const voronoi_edge_type *edge2_2 = edge2_1->twin();
+ CHECK_EQUAL_POINTS(edge2_1->cell()->point0(), points[3]);
+ CHECK_EQUAL_POINTS(edge2_2->cell()->point0(), points[2]);
+
+ const voronoi_edge_type *edge3_1 = edge2_1->rot_prev();
+ const voronoi_edge_type *edge3_2 = edge3_1->twin();
+ CHECK_EQUAL_POINTS(edge3_1->cell()->point0(), points[2]);
+ CHECK_EQUAL_POINTS(edge3_2->cell()->point0(), points[0]);
+
+ const voronoi_edge_type *edge4_1 = edge3_1->rot_prev();
+ const voronoi_edge_type *edge4_2 = edge4_1->twin();
+ CHECK_EQUAL_POINTS(edge4_1->cell()->point0(), points[0]);
+ CHECK_EQUAL_POINTS(edge4_2->cell()->point0(), points[1]);
+
+ BOOST_CHECK_EQUAL(edge1_2->twin() == edge1_1, true);
+ BOOST_CHECK_EQUAL(edge2_2->twin() == edge2_1, true);
+ BOOST_CHECK_EQUAL(edge3_2->twin() == edge3_1, true);
+ BOOST_CHECK_EQUAL(edge4_2->twin() == edge4_1, true);
+
+ BOOST_CHECK_EQUAL(edge1_1->prev() == edge4_2 && edge1_1->next() == edge4_2, true);
+ BOOST_CHECK_EQUAL(edge2_1->prev() == edge1_2 && edge2_1->next() == edge1_2, true);
+ BOOST_CHECK_EQUAL(edge3_1->prev() == edge2_2 && edge3_1->next() == edge2_2, true);
+ BOOST_CHECK_EQUAL(edge4_1->prev() == edge3_2 && edge4_1->next() == edge3_2, true);
+
+ BOOST_CHECK_EQUAL(edge1_2->next() == edge2_1 && edge1_2->prev() == edge2_1, true);
+ BOOST_CHECK_EQUAL(edge2_2->next() == edge3_1 && edge2_2->prev() == edge3_1, true);
+ BOOST_CHECK_EQUAL(edge3_2->next() == edge4_1 && edge3_2->prev() == edge4_1, true);
+ BOOST_CHECK_EQUAL(edge4_2->next() == edge1_1 && edge4_2->prev() == edge1_1, true);
+
+ BOOST_CHECK_EQUAL(edge1_1->rot_next() == edge4_1, true);
+ BOOST_CHECK_EQUAL(edge4_1->rot_next() == edge3_1, true);
+ BOOST_CHECK_EQUAL(edge3_1->rot_next() == edge2_1, true);
+ BOOST_CHECK_EQUAL(edge2_1->rot_next() == edge1_1, true);
+}
+
+#ifdef NDEBUG
+BOOST_AUTO_TEST_CASE_TEMPLATE(grid_test, T, test_types) {
+ voronoi_diagram<double> test_output_small, test_output_large;
+ std::vector< point_data<T> > point_vec_small, point_vec_large;
+ int grid_size[4] = {10, 33, 101, 163};
+ int max_value[4] = {10, 33, 101, 163};
+ int array_length = sizeof(grid_size) / sizeof(int);
+ for (int k = 0; k < array_length; k++) {
+ point_vec_small.clear();
+ point_vec_large.clear();
+ int koef = std::numeric_limits<int>::max() / max_value[k];
+ for (int i = 0; i < grid_size[k]; i++)
+ for (int j = 0; j < grid_size[k]; j++) {
+ point_vec_small.push_back(point_data<T>(i, j));
+ point_vec_large.push_back(point_data<T>(koef * i, koef * j));
+ }
+ construct_voronoi_points<T>(point_vec_small, test_output_small);
+ construct_voronoi_points<T>(point_vec_large, test_output_large);
+ VERIFY_OUTPUT(test_output_small);
+ VERIFY_OUTPUT(test_output_large);
+ int num_cells = grid_size[k] * grid_size[k];
+ int num_vertices = num_cells - 2 * grid_size[k] + 1;
+ int num_edges = 2 * num_cells - 2 * grid_size[k];
+ CHECK_OUTPUT_SIZE(test_output_small, num_cells, num_vertices, num_edges);
+ CHECK_OUTPUT_SIZE(test_output_large, num_cells, num_vertices, num_edges);
+ }
+}
+#endif
+
+#ifdef NDEBUG
+BOOST_AUTO_TEST_CASE_TEMPLATE(random_test, T, test_types) {
+ boost::mt19937 gen(static_cast<unsigned int>(time(NULL)));
+ voronoi_diagram<double> test_output_small, test_output_large;
+ std::vector< point_data<T> > point_vec_small, point_vec_large;
+ int num_points[] = {5, 100, 1000, 10000, 100000};
+ int num_runs[] = {10000, 1000, 100, 10, 1};
+ int mod_koef[] = {10, 100, 100, 1000, 10000};
+ int max_value[] = {5, 50, 50, 5000, 5000};
+ int array_length = sizeof(num_points) / sizeof(int);
+ for (int k = 0; k < array_length; k++) {
+ int koef = std::numeric_limits<int>::max() / max_value[k];
+ for (int i = 0; i < num_runs[k]; i++) {
+ point_vec_small.clear();
+ point_vec_large.clear();
+ for (int j = 0; j < num_points[k]; j++) {
+ T x = gen() % mod_koef[k] - mod_koef[k] / 2;
+ T y = gen() % mod_koef[k] - mod_koef[k] / 2;
+ point_vec_small.push_back(point_data<T>(x, y));
+ point_vec_large.push_back(point_data<T>(koef * x, koef * y));
+ }
+ construct_voronoi_points<T>(point_vec_small, test_output_small);
+ construct_voronoi_points<T>(point_vec_large, test_output_large);
+ VERIFY_OUTPUT(test_output_small);
+ VERIFY_OUTPUT(test_output_large);
+ 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());
+ }
+ }
+}
+#endif
+
+#ifdef NDEBUG
+BOOST_AUTO_TEST_CASE_TEMPLATE(enormous_random_test, T, test_types) {
+ boost::mt19937 gen(static_cast<unsigned int>(time(NULL)));
+ voronoi_diagram<double> test_output;
+ std::vector< point_data<T> > point_vec;
+ for (int i = 0; i < 1000000; i++)
+ point_vec.push_back(point_data<T>(gen() % 10000 - 5000, gen() % 10000 - 5000));
+ construct_voronoi_points<T>(point_vec, test_output);
+ BOOST_CHECK_EQUAL(voronoi_test_helper::verify_output(test_output,
+ voronoi_test_helper::FAST_VERIFICATION), true);
+}
+#endif
+
+BOOST_AUTO_TEST_CASE_TEMPLATE(segment_sites_test1, T, test_types) {
+ typedef T coordinate_type;
+ voronoi_diagram<double> test_output;
+ directed_line_segment_set_data<T> segments;
+ point_data<T> point1(0, 0);
+ point_data<T> point2(1, 1);
+ segments.insert(directed_line_segment_data<T>(point1, point2));
+ construct_voronoi_segments<T>(segments, test_output);
+ CHECK_OUTPUT_SIZE(test_output, 3, 0, 2);
+ VERIFY_NO_HALF_EDGE_INTERSECTIONS(test_output);
+}
+
+BOOST_AUTO_TEST_CASE_TEMPLATE(segment_sites_test2, T, test_types) {
+ typedef T coordinate_type;
+ voronoi_diagram<double> test_output;
+ std::vector< point_data<T> > points;
+ directed_line_segment_set_data<T> segments;
+ point_data<T> point1(0, 0);
+ point_data<T> point2(4, 4);
+ point_data<T> point3(3, 1);
+ point_data<T> point4(1, 3);
+ segments.insert(directed_line_segment_data<T>(point1, point2));
+ points.push_back(point3);
+ points.push_back(point4);
+ construct_voronoi<T>(points, segments, test_output);
+ CHECK_OUTPUT_SIZE(test_output, 5, 4, 8);
+ VERIFY_NO_HALF_EDGE_INTERSECTIONS(test_output);
+}
+
+BOOST_AUTO_TEST_CASE_TEMPLATE(segment_sites_test3, T, test_types) {
+ typedef T coordinate_type;
+ voronoi_diagram<double> test_output;
+ std::vector< point_data<T> > points;
+ directed_line_segment_set_data<T> segments;
+ point_data<T> point1(4, 0);
+ point_data<T> point2(0, 4);
+ point_data<T> point3(3, 3);
+ point_data<T> point4(1, 1);
+ segments.insert(directed_line_segment_data<T>(point1, point2));
+ points.push_back(point3);
+ points.push_back(point4);
+ construct_voronoi<T>(points, segments, test_output);
+ CHECK_OUTPUT_SIZE(test_output, 5, 4, 8);
+ VERIFY_NO_HALF_EDGE_INTERSECTIONS(test_output);
+}
+
+BOOST_AUTO_TEST_CASE_TEMPLATE(segment_sites_test4, T, test_types) {
+ typedef T coordinate_type;
+ voronoi_diagram<double> test_output;
+ std::vector< point_data<T> > points;
+ directed_line_segment_set_data<T> segments;
+ point_data<T> point1(4, 0);
+ point_data<T> point2(0, 4);
+ point_data<T> point3(3, 2);
+ point_data<T> point4(2, 3);
+ segments.insert(directed_line_segment_data<T>(point1, point2));
+ points.push_back(point3);
+ points.push_back(point4);
+ construct_voronoi<T>(points, segments, test_output);
+ CHECK_OUTPUT_SIZE(test_output, 5, 3, 7);
+ VERIFY_NO_HALF_EDGE_INTERSECTIONS(test_output);
+}
+
+BOOST_AUTO_TEST_CASE_TEMPLATE(segment_site_test5, T, test_types) {
+ typedef T coordinate_type;
+ voronoi_diagram<double> test_output;
+ std::vector< point_data<T> > points;
+ directed_line_segment_set_data<T> segments;
+ point_data<T> point1(0, 0);
+ point_data<T> point2(0, 8);
+ point_data<T> point3(-2, -2);
+ point_data<T> point4(-2, 4);
+ point_data<T> point5(-2, 10);
+ segments.insert(directed_line_segment_data<T>(point1, point2));
+ points.push_back(point3);
+ points.push_back(point4);
+ points.push_back(point5);
+ construct_voronoi<T>(points, segments, test_output);
+ CHECK_OUTPUT_SIZE(test_output, 6, 4, 9);
+ VERIFY_NO_HALF_EDGE_INTERSECTIONS(test_output);
+}
+
+BOOST_AUTO_TEST_CASE_TEMPLATE(segment_site_test6, T, test_types) {
+ typedef T coordinate_type;
+ voronoi_diagram<double> test_output;
+ std::vector< point_data<T> > points;
+ directed_line_segment_set_data<T> segments;
+ point_data<T> point1(-1, 1);
+ point_data<T> point2(1, 0);
+ point_data<T> point3(1, 2);
+ segments.insert(directed_line_segment_data<T>(point2, point3));
+ points.push_back(point1);
+ construct_voronoi<T>(points, segments, test_output);
+ CHECK_OUTPUT_SIZE(test_output, 4, 2, 5);
+ VERIFY_NO_HALF_EDGE_INTERSECTIONS(test_output);
+}
+
+BOOST_AUTO_TEST_CASE_TEMPLATE(segment_site_test7, T, test_types) {
+ typedef T coordinate_type;
+ voronoi_diagram<double> test_output;
+ directed_line_segment_set_data<T> segments;
+ point_data<T> point1(0, 0);
+ point_data<T> point2(4, 0);
+ point_data<T> point3(0, 4);
+ point_data<T> point4(4, 4);
+ segments.insert(directed_line_segment_data<T>(point1, point2));
+ segments.insert(directed_line_segment_data<T>(point2, point3));
+ segments.insert(directed_line_segment_data<T>(point3, point4));
+ construct_voronoi_segments<T>(segments, test_output);
+ CHECK_OUTPUT_SIZE(test_output, 7, 6, 12);
+ VERIFY_NO_HALF_EDGE_INTERSECTIONS(test_output);
+}
+
+BOOST_AUTO_TEST_CASE_TEMPLATE(segment_site_test8, T, test_types) {
+ typedef T coordinate_type;
+ voronoi_diagram<double> test_output;
+ directed_line_segment_set_data<T> segments;
+ point_data<T> point1(0, 0);
+ point_data<T> point2(4, 0);
+ point_data<T> point3(4, 4);
+ point_data<T> point4(0, 4);
+ segments.insert(directed_line_segment_data<T>(point1, point2));
+ segments.insert(directed_line_segment_data<T>(point2, point3));
+ segments.insert(directed_line_segment_data<T>(point3, point4));
+ segments.insert(directed_line_segment_data<T>(point4, point1));
+ construct_voronoi_segments<T>(segments, test_output);
+ CHECK_OUTPUT_SIZE(test_output, 8, 5, 12);
+ VERIFY_NO_HALF_EDGE_INTERSECTIONS(test_output);
+}
+
+#ifdef NDEBUG
+BOOST_AUTO_TEST_CASE_TEMPLATE(segment_grid_test, T, test_types) {
+ voronoi_diagram<double> test_output_small, test_output_large;
+ directed_line_segment_set_data<T> segments_small, segments_large;
+ int grid_size[] = {10, 33, 100};
+ int max_value[] = {100, 330, 1000};
+ int array_length = sizeof(grid_size) / sizeof(int);
+ for (int k = 0; k < array_length; k++) {
+ segments_small.clear();
+ segments_large.clear();
+ int cur_sz = grid_size[k];
+ int koef = std::numeric_limits<int>::max() / max_value[k];
+ for (int i = 0; i < cur_sz + 1; i++)
+ for (int j = 0; j < cur_sz; j++) {
+ point_data<T> point1_1(10 * i, 10 * j);
+ point_data<T> point1_2(koef * 10 * i, koef * 10 * j);
+ point_data<T> point2_1(10 * i, 10 * j + 10);
+ point_data<T> point2_2(koef * 10 * i, koef * (10 * j + 10));
+ segments_small.insert(directed_line_segment_data<T>(point1_1, point2_1));
+ segments_large.insert(directed_line_segment_data<T>(point1_2, point2_2));
+ point_data<T> point3_1(10 * j, 10 * i);
+ point_data<T> point3_2(koef * 10 * j, koef * 10 * i);
+ point_data<T> point4_1(10 * j + 10, 10 * i);
+ point_data<T> point4_2(koef * (10 * j + 10), koef * 10 * i);
+ segments_small.insert(directed_line_segment_data<T>(point3_1, point4_1));
+ segments_large.insert(directed_line_segment_data<T>(point3_2, point4_2));
+ }
+ construct_voronoi_segments<T>(segments_small, test_output_small);
+ construct_voronoi_segments<T>(segments_large, test_output_large);
+ VERIFY_NO_HALF_EDGE_INTERSECTIONS(test_output_small);
+ VERIFY_NO_HALF_EDGE_INTERSECTIONS(test_output_large);
+ 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());
+ }
+}
+#endif
+
+#ifdef NDEBUG
+BOOST_AUTO_TEST_CASE_TEMPLATE(segment_random_test1, T, test_types) {
+ boost::mt19937 gen(static_cast<unsigned int>(time(NULL)));
+ voronoi_diagram<double> test_output;
+ std::vector< point_data<T> > points;
+ directed_line_segment_set_data<T> segments;
+ int num_runs = 1000;
+ int num_segments = 10;
+ points.push_back(point_data<T>(-100, -100));
+ points.push_back(point_data<T>(-100, 100));
+ points.push_back(point_data<T>(100, -100));
+ points.push_back(point_data<T>(100, 100));
+ for (int i = 0; i < num_runs; i++) {
+ segments.clear();
+ for (int j = 0; j < num_segments; j++) {
+ T x1 = 0, y1 = 0, x2 = 0, y2 = 0;
+ while (x1 == x2 && y1 == y2) {
+ x1 = (gen() % 100) - 50;
+ y1 = (gen() % 100) - 50;
+ x2 = (gen() % 100) - 50;
+ y2 = (gen() % 100) - 50;
+ }
+ point_data<T> point1(x1, y1);
+ point_data<T> point2(x2, y2);
+ segments.insert(directed_line_segment_data<T>(point1, point2));
+ }
+ segments.clean();
+ construct_voronoi<T>(points, segments, test_output);
+ VERIFY_NO_HALF_EDGE_INTERSECTIONS(test_output);
+ }
+}
+#endif
+
+#ifdef NDEBUG
+BOOST_AUTO_TEST_CASE_TEMPLATE(segment_random_test2, T, test_types) {
+ boost::mt19937 gen(static_cast<unsigned int>(time(NULL)));
+ voronoi_diagram<double> test_output_small, test_output_large;
+ directed_line_segment_set_data<T> segments_small, segments_large;
+ int num_segments[] = {5, 25, 125, 625};
+ int num_runs[] = {1000, 100, 10, 1};
+ int mod_koef1[] = {10, 100, 200, 300};
+ int mod_koef2[] = {10, 20, 50, 100};
+ int max_value[] = {10, 60, 125, 200};
+ int array_length = sizeof(num_segments) / sizeof(int);
+ for (int k = 0; k < array_length; k++) {
+ int koef = std::numeric_limits<int>::max() / max_value[k];
+ for (int i = 0; i < num_runs[k]; i++) {
+ segments_small.clear();
+ segments_large.clear();
+ for (int j = 0; j < num_segments[k]; j++) {
+ T x1 = (gen() % mod_koef1[k]) - mod_koef1[k] / 2;
+ T y1 = (gen() % mod_koef1[k]) - mod_koef1[k] / 2;
+ T dx = 0, dy = 0;
+ while (dx == 0 && dy == 0) {
+ dx = (gen() % mod_koef2[k]) - mod_koef2[k] / 2;
+ dy = (gen() % mod_koef2[k]) - mod_koef2[k] / 2;
+ }
+ T x2 = x1 + dx;
+ T y2 = y1 + dy;
+ point_data<T> point1_small(x1, y1);
+ point_data<T> point2_small(x2, y2);
+ segments_small.insert(directed_line_segment_data<T>(point1_small, point2_small));
+ }
+ segments_small.clean();
+ for (typename directed_line_segment_set_data<T>::iterator_type it = segments_small.begin();
+ it != segments_small.end(); ++it) {
+ T x1 = it->low().x() * koef;
+ T y1 = it->low().y() * koef;
+ T x2 = it->high().x() * koef;
+ T y2 = it->high().y() * koef;
+ point_data<T> point1_large(x1, y1);
+ point_data<T> point2_large(x2, y2);
+ segments_large.insert(directed_line_segment_data<T>(point1_large, point2_large));
+ }
+ construct_voronoi_segments<T>(segments_small, test_output_small);
+ construct_voronoi_segments<T>(segments_large, test_output_large);
+ VERIFY_NO_HALF_EDGE_INTERSECTIONS(test_output_small);
+ VERIFY_NO_HALF_EDGE_INTERSECTIONS(test_output_large);
+ 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());
+ }
+ }
+}
+#endif

Modified: sandbox/gtl/libs/polygon/test/voronoi_internal_structures_test.cpp
==============================================================================
--- sandbox/gtl/libs/polygon/test/voronoi_internal_structures_test.cpp (original)
+++ sandbox/gtl/libs/polygon/test/voronoi_internal_structures_test.cpp 2011-10-11 18:21:42 EDT (Tue, 11 Oct 2011)
@@ -18,7 +18,7 @@
 typedef circle_event<int> circle_type;
 typedef ordered_queue<int, std::greater<int> > ordered_queue_type;
 typedef beach_line_node_key<int> node_key_type;
-typedef beach_line_node_data<int> node_data_type;
+typedef beach_line_node_data<int, int> node_data_type;
 
 BOOST_AUTO_TEST_CASE(point_2d_test) {
     point_type p(1, 2);

Added: sandbox/gtl/libs/polygon/test/voronoi_test_helper.hpp
==============================================================================
--- (empty file)
+++ sandbox/gtl/libs/polygon/test/voronoi_test_helper.hpp 2011-10-11 18:21:42 EDT (Tue, 11 Oct 2011)
@@ -0,0 +1,226 @@
+// Boost.Polygon library voronoi_test_helper.hpp file
+
+// Copyright Andrii Sydorchuk 2010-2011.
+// 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_TEST_HELPER
+#define VORONOI_TEST_HELPER
+
+#include <iostream>
+#include <fstream>
+#include <map>
+#include <vector>
+
+namespace voronoi_test_helper {
+
+enum kOrientation {
+ RIGHT = -1,
+ COLLINEAR = 0,
+ LEFT = 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 : LEFT;
+}
+
+template <typename Output>
+bool verify_half_edge_orientation(const Output &output) {
+ typedef typename Output::point_type point_type;
+ 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->is_bounded()) {
+ const point_type &site_point = edge_it->cell()->point0();
+ const point_type &start_point = edge_it->vertex0()->vertex();
+ const point_type &end_point = edge_it->vertex1()->vertex();
+ if (get_orientation(start_point, end_point, site_point) != LEFT)
+ return false;
+ }
+ }
+ return true;
+}
+
+template <typename Output>
+bool verify_cell_convexity(const Output &output) {
+ typedef typename Output::point_type point_type;
+ 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->vertex0() != NULL &&
+ edge->vertex1() != NULL &&
+ edge->vertex1() == edge->next()->vertex0() &&
+ edge->next()->vertex1() != NULL) {
+ const point_type &vertex1 = edge->vertex0()->vertex();
+ const point_type &vertex2 = edge->vertex1()->vertex();
+ const point_type &vertex3 = edge->next()->vertex1()->vertex();
+ if (get_orientation(vertex1, vertex2, vertex3) != LEFT)
+ 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::point_type point_type;
+ typedef typename Output::voronoi_edge_type voronoi_edge_type;
+ 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;
+ const voronoi_edge_type *edge = vertex_it->incident_edge();
+ do {
+ const voronoi_edge_type *edge_next1 = edge->rot_next();
+ const voronoi_edge_type *edge_next2 = edge_next1->rot_next();
+ const point_type &site1 = edge->cell()->point0();
+ const point_type &site2 = edge_next1->cell()->point0();
+ const point_type &site3 = edge_next2->cell()->point0();
+
+ if (get_orientation(site1, site2, site3) != LEFT)
+ return false;
+
+ edge = edge->rot_next();
+ } while (edge != vertex_it->incident_edge());
+ }
+ return true;
+}
+
+template <typename Output>
+bool verfiy_no_line_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::point_type point_type;
+ std::map< point_type, std::vector<point_type> > edge_map;
+ 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->is_bounded()) {
+ const point_type &vertex0 = edge_it->vertex0()->vertex();
+ const point_type &vertex1 = edge_it->vertex1()->vertex();
+ if (vertex0 < vertex1)
+ edge_map[vertex0].push_back(vertex1);
+ }
+ }
+ return !intersection_check(edge_map);
+}
+
+template <typename Point2D>
+bool intersection_check(const std::map< Point2D, std::vector<Point2D> > &edge_map) {
+ // 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 Point2D point_type;
+ typedef typename point_type::coordinate_type coordinate_type;
+ typedef typename std::map< point_type, std::vector<point_type> >::const_iterator
+ edge_map_iterator;
+ typedef typename std::vector<point_type>::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 point_type &point1 = edge_map_it1->first;
+ for (size_type i = 0; i < edge_map_it1->second.size(); i++) {
+ const point_type &point2 = edge_map_it1->second[i];
+ coordinate_type min_y1 = std::min(point1.y(), point2.y());
+ 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 point_type &point3 = edge_map_it2->first;
+ for (size_type j = 0; j < edge_map_it2->second.size(); j++) {
+ const point_type &point4 = edge_map_it2->second[j];
+ coordinate_type min_y2 = std::min(point3.y(), point4.y());
+ 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) == RIGHT &&
+ get_orientation(point3, point4, point1) *
+ get_orientation(point3, point4, point2) == RIGHT)
+ return true;
+ }
+ }
+ }
+ }
+ return false;
+}
+
+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_line_edge_intersections(output);
+ return result;
+}
+
+template <typename T>
+void save_voronoi_input(const std::vector< point_data<T> > &points, const char *file_name) {
+ std::ofstream ofs(file_name);
+ ofs << points.size() << std::endl;
+ for (int i = 0; i < (int)points.size(); ++i)
+ ofs << points[i].x() << " " << points[i].y() << std::endl;
+ ofs.close();
+}
+
+template <typename T>
+void save_voronoi_input(const directed_line_segment_set_data<T> &segments, const char *file_name) {
+ std::ofstream ofs(file_name);
+ //ofs << segments.size() << std::endl;
+ for (directed_line_segment_set_data<T>::iterator_type it = segments.begin();
+ it != segments.end(); ++it) {
+ ofs << it->low().x() << " " << it->low().y() << " ";
+ ofs << it->high().x() << " " << it->high().y() << std::endl;
+ }
+ ofs.close();
+}
+
+}
+
+#endif


Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk