]> git.proxmox.com Git - ceph.git/blame - ceph/src/boost/libs/polygon/test/voronoi_builder_test.cpp
projects / ceph.git / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
import new upstream nautilus stable release 14.2.8
[ceph.git] / ceph / src / boost / libs / polygon / test / voronoi_builder_test.cpp
CommitLineData
7c673cae
FG		 1// Boost.Polygon library voronoi_builder_test.cpp file
2
3// Copyright Andrii Sydorchuk 2010-2012.
4// Distributed under the Boost Software License, Version 1.0.
5// (See accompanying file LICENSE_1_0.txt or copy at
6// http://www.boost.org/LICENSE_1_0.txt)
7
8// See http://www.boost.org for updates, documentation, and revision history.
9
92f5a8d4
TL		 10#include "voronoi_test_helper.hpp"
11#include <boost/core/lightweight_test.hpp>
12#include <boost/polygon/polygon.hpp>
13#include <boost/polygon/voronoi.hpp>
14#include <boost/random/mersenne_twister.hpp>
7c673cae
FG		 15#include <limits>
16#include <list>
17#include <vector>
92f5a8d4 18#include <ctime>
7c673cae 19
7c673cae
FG		 20using boost::polygon::voronoi_builder;
21using boost::polygon::voronoi_diagram;
22
7c673cae
FG		 23typedef voronoi_diagram<double> vd_type;
24typedef vd_type::coordinate_type coordinate_type;
25typedef vd_type::edge_type voronoi_edge_type;
26typedef vd_type::const_cell_iterator const_cell_iterator;
27typedef vd_type::const_vertex_iterator const_vertex_iterator;
28
29#define CHECK_OUTPUT_SIZE(output, cells, vertices, edges) \
92f5a8d4
TL		 30 BOOST_TEST_EQ(output.num_cells(), (std::size_t)cells); \
31 BOOST_TEST_EQ(output.num_vertices(), (std::size_t)vertices); \
32 BOOST_TEST_EQ(output.num_edges(), (std::size_t)edges)
7c673cae
FG		 33
34#define VERIFY_OUTPUT(output) \
92f5a8d4 35 BOOST_TEST(voronoi_test_helper::verify_output(output, \
7c673cae 36 voronoi_test_helper::CELL_CONVEXITY)); \
92f5a8d4 37 BOOST_TEST(voronoi_test_helper::verify_output(output, \
7c673cae 38 voronoi_test_helper::INCIDENT_EDGES_CCW_ORDER)); \
92f5a8d4 39 BOOST_TEST(voronoi_test_helper::verify_output(output, \
7c673cae
FG		 40 voronoi_test_helper::NO_HALF_EDGE_INTERSECTIONS))
41
42#define VERIFY_NO_HALF_EDGE_INTERSECTIONS(output) \
92f5a8d4 43 BOOST_TEST(voronoi_test_helper::verify_output(output, \
7c673cae
FG		 44 voronoi_test_helper::NO_HALF_EDGE_INTERSECTIONS))
45
46// Sites: (0, 0).
92f5a8d4
TL		 47void single_site_test()
48{
49 std::vector< point_data<int> > points;
50 points.push_back(point_data<int>(0, 0));
7c673cae
FG		 51 vd_type test_output;
52 construct_voronoi(points.begin(), points.end(), &test_output);
53 VERIFY_OUTPUT(test_output);
54
92f5a8d4 55 BOOST_TEST(test_output.cells().size() == 1);
7c673cae
FG		 56 CHECK_OUTPUT_SIZE(test_output, 1, 0, 0);
57
58 const_cell_iterator it = test_output.cells().begin();
92f5a8d4 59 BOOST_TEST(it->incident_edge() == NULL);
7c673cae
FG		 60}
61
62// Sites: (0, 0), (0, 1).
92f5a8d4
TL		 63void collinear_sites_test1()
64{
65 std::vector< point_data<int> > points;
66 points.push_back(point_data<int>(0, 0));
67 points.push_back(point_data<int>(0, 1));
7c673cae
FG		 68 vd_type test_output;
69 construct_voronoi(points.begin(), points.end(), &test_output);
70 VERIFY_OUTPUT(test_output);
71 CHECK_OUTPUT_SIZE(test_output, 2, 0, 2);
72
73 const_cell_iterator cell_it = test_output.cells().begin();
74 cell_it++;
75
76 const voronoi_edge_type* edge1_1 = cell_it->incident_edge();
77 const voronoi_edge_type* edge1_2 = edge1_1->twin();
78
92f5a8d4
TL		 79 BOOST_TEST(edge1_1->twin() == edge1_2);
80 BOOST_TEST(edge1_2->twin() == edge1_1);
7c673cae 81
92f5a8d4
TL		 82 BOOST_TEST(edge1_1->next() == edge1_1);
83 BOOST_TEST(edge1_1->prev() == edge1_1);
84 BOOST_TEST(edge1_1->rot_next() == edge1_2);
85 BOOST_TEST(edge1_1->rot_prev() == edge1_2);
7c673cae 86
92f5a8d4
TL		 87 BOOST_TEST(edge1_2->next() == edge1_2);
88 BOOST_TEST(edge1_2->prev() == edge1_2);
89 BOOST_TEST(edge1_2->rot_next() == edge1_1);
90 BOOST_TEST(edge1_2->rot_prev() == edge1_1);
7c673cae
FG		 91}
92
93// Sites: (0, 0), (1, 1), (2, 2).
92f5a8d4
TL		 94void collinear_sites_test2()
95{
96 std::vector< point_data<int> > points;
97 points.push_back(point_data<int>(0, 0));
98 points.push_back(point_data<int>(1, 1));
99 points.push_back(point_data<int>(2, 2));
7c673cae
FG		 100 vd_type test_output;
101 construct_voronoi(points.begin(), points.end(), &test_output);
102 VERIFY_OUTPUT(test_output);
103 CHECK_OUTPUT_SIZE(test_output, 3, 0, 4);
104
105 const_cell_iterator cell_it = test_output.cells().begin();
106 const voronoi_edge_type* edge1_1 = cell_it->incident_edge();
107 const voronoi_edge_type* edge1_2 = edge1_1->twin();
108 cell_it++;
109 cell_it++;
110 const voronoi_edge_type* edge2_2 = cell_it->incident_edge();
111 const voronoi_edge_type* edge2_1 = edge2_2->twin();
112
92f5a8d4
TL		 113 BOOST_TEST(edge1_1->twin() == edge1_2 && edge1_2->twin() == edge1_1);
114 BOOST_TEST(edge2_1->twin() == edge2_2 && edge2_2->twin() == edge2_1);
7c673cae 115
92f5a8d4
TL		 116 BOOST_TEST(edge1_1->next() == edge1_1 && edge1_1->prev() == edge1_1);
117 BOOST_TEST(edge1_2->next() == edge2_1 && edge1_2->prev() == edge2_1);
118 BOOST_TEST(edge2_1->next() == edge1_2 && edge2_1->prev() == edge1_2);
119 BOOST_TEST(edge2_2->next() == edge2_2 && edge2_2->prev() == edge2_2);
7c673cae 120
92f5a8d4
TL		 121 BOOST_TEST(edge1_1->rot_next() == edge1_2 && edge1_1->rot_prev() == edge2_1);
122 BOOST_TEST(edge1_2->rot_next() == edge2_2 && edge1_2->rot_prev() == edge1_1);
123 BOOST_TEST(edge2_1->rot_next() == edge1_1 && edge2_1->rot_prev() == edge2_2);
124 BOOST_TEST(edge2_2->rot_next() == edge2_1 && edge2_2->rot_prev() == edge1_2);
7c673cae 125
92f5a8d4
TL		 126 BOOST_TEST(edge1_2->next() == edge2_1 && edge1_2->prev() == edge2_1);
127 BOOST_TEST(edge2_1->next() == edge1_2 && edge2_1->prev() == edge1_2);
7c673cae
FG		 128}
129
130// Sites: (0, 0), (0, 4), (2, 1).
92f5a8d4
TL		 131void triangle_test1()
132{
133 point_data<int> point1(0, 0);
134 point_data<int> point2(0, 4);
135 point_data<int> point3(2, 1);
136 std::vector< point_data<int> > points;
7c673cae
FG		 137 points.push_back(point1);
138 points.push_back(point2);
139 points.push_back(point3);
140 vd_type test_output;
141 construct_voronoi(points.begin(), points.end(), &test_output);
142 VERIFY_OUTPUT(test_output);
143 CHECK_OUTPUT_SIZE(test_output, 3, 1, 6);
144
145 const_vertex_iterator it = test_output.vertices().begin();
92f5a8d4
TL		 146 BOOST_TEST_EQ(it->x(), 0.25);
147 BOOST_TEST_EQ(it->y(), 2.0);
7c673cae
FG		 148
149 const voronoi_edge_type* edge1_1 = it->incident_edge();
150 const voronoi_edge_type* edge1_2 = edge1_1->twin();
92f5a8d4
TL		 151 BOOST_TEST(edge1_1->cell()->source_index() == 1);
152 BOOST_TEST(edge1_2->cell()->source_index() == 2);
7c673cae
FG		 153
154 const voronoi_edge_type* edge2_1 = edge1_1->rot_prev();
155 const voronoi_edge_type* edge2_2 = edge2_1->twin();
92f5a8d4
TL		 156 BOOST_TEST(edge2_1->cell()->source_index() == 2);
157 BOOST_TEST(edge2_2->cell()->source_index() == 0);
7c673cae
FG		 158
159 const voronoi_edge_type* edge3_1 = edge2_1->rot_prev();
160 const voronoi_edge_type* edge3_2 = edge3_1->twin();
92f5a8d4
TL		 161 BOOST_TEST(edge3_1->cell()->source_index() == 0);
162 BOOST_TEST(edge3_2->cell()->source_index() == 1);
7c673cae 163
92f5a8d4
TL		 164 BOOST_TEST(edge1_2->twin() == edge1_1);
165 BOOST_TEST(edge2_2->twin() == edge2_1);
166 BOOST_TEST(edge3_2->twin() == edge3_1);
7c673cae 167
92f5a8d4
TL		 168 BOOST_TEST(edge1_1->prev() == edge3_2 && edge1_1->next() == edge3_2);
169 BOOST_TEST(edge2_1->prev() == edge1_2 && edge2_1->next() == edge1_2);
170 BOOST_TEST(edge3_1->prev() == edge2_2 && edge3_1->next() == edge2_2);
7c673cae 171
92f5a8d4
TL		 172 BOOST_TEST(edge1_2->next() == edge2_1 && edge1_2->prev() == edge2_1);
173 BOOST_TEST(edge2_2->next() == edge3_1 && edge2_2->prev() == edge3_1);
174 BOOST_TEST(edge3_2->next() == edge1_1 && edge3_2->prev() == edge1_1);
7c673cae 175
92f5a8d4
TL		 176 BOOST_TEST(edge1_1->rot_next() == edge3_1);
177 BOOST_TEST(edge3_1->rot_next() == edge2_1);
178 BOOST_TEST(edge2_1->rot_next() == edge1_1);
7c673cae 179
92f5a8d4
TL		 180 BOOST_TEST(edge1_2->rot_next() == edge2_2);
181 BOOST_TEST(edge2_2->rot_next() == edge3_2);
182 BOOST_TEST(edge3_2->rot_next() == edge1_2);
7c673cae
FG		 183}
184
185// Sites: (0, 1), (2, 0), (2, 4).
92f5a8d4
TL		 186void triangle_test2()
187{
188 point_data<int> point1(0, 1);
189 point_data<int> point2(2, 0);
190 point_data<int> point3(2, 4);
191 std::vector< point_data<int> > points;
7c673cae
FG		 192 points.push_back(point1);
193 points.push_back(point2);
194 points.push_back(point3);
195 vd_type test_output;
196 construct_voronoi(points.begin(), points.end(), &test_output);
197 VERIFY_OUTPUT(test_output);
198 CHECK_OUTPUT_SIZE(test_output, 3, 1, 6);
199
200 const_vertex_iterator it = test_output.vertices().begin();
92f5a8d4
TL		 201 BOOST_TEST_EQ(it->x(), 1.75);
202 BOOST_TEST_EQ(it->y(), 2.0);
7c673cae
FG		 203
204 const voronoi_edge_type* edge1_1 = it->incident_edge();
205 const voronoi_edge_type* edge1_2 = edge1_1->twin();
92f5a8d4
TL		 206 BOOST_TEST(edge1_1->cell()->source_index() == 2);
207 BOOST_TEST(edge1_2->cell()->source_index() == 1);
7c673cae
FG		 208
209 const voronoi_edge_type* edge2_1 = edge1_1->rot_prev();
210 const voronoi_edge_type* edge2_2 = edge2_1->twin();
92f5a8d4
TL		 211 BOOST_TEST(edge2_1->cell()->source_index() == 1);
212 BOOST_TEST(edge2_2->cell()->source_index() == 0);
7c673cae
FG		 213
214 const voronoi_edge_type* edge3_1 = edge2_1->rot_prev();
215 const voronoi_edge_type* edge3_2 = edge3_1->twin();
92f5a8d4
TL		 216 BOOST_TEST(edge3_1->cell()->source_index() == 0);
217 BOOST_TEST(edge3_2->cell()->source_index() == 2);
7c673cae 218
92f5a8d4
TL		 219 BOOST_TEST(edge1_2->twin() == edge1_1);
220 BOOST_TEST(edge2_2->twin() == edge2_1);
221 BOOST_TEST(edge3_2->twin() == edge3_1);
7c673cae 222
92f5a8d4
TL		 223 BOOST_TEST(edge1_1->prev() == edge3_2 && edge1_1->next() == edge3_2);
224 BOOST_TEST(edge2_1->prev() == edge1_2 && edge2_1->next() == edge1_2);
225 BOOST_TEST(edge3_1->prev() == edge2_2 && edge3_1->next() == edge2_2);
7c673cae 226
92f5a8d4
TL		 227 BOOST_TEST(edge1_2->next() == edge2_1 && edge1_2->prev() == edge2_1);
228 BOOST_TEST(edge2_2->next() == edge3_1 && edge2_2->prev() == edge3_1);
229 BOOST_TEST(edge3_2->next() == edge1_1 && edge3_2->prev() == edge1_1);
7c673cae 230
92f5a8d4
TL		 231 BOOST_TEST(edge1_1->rot_next() == edge3_1);
232 BOOST_TEST(edge3_1->rot_next() == edge2_1);
233 BOOST_TEST(edge2_1->rot_next() == edge1_1);
7c673cae 234
92f5a8d4
TL		 235 BOOST_TEST(edge1_2->rot_next() == edge2_2);
236 BOOST_TEST(edge2_2->rot_next() == edge3_2);
237 BOOST_TEST(edge3_2->rot_next() == edge1_2);
7c673cae
FG		 238}
239
240// Sites: (0, 0), (0, 1), (1, 0), (1, 1).
92f5a8d4
TL		 241void square_test1()
242{
243 point_data<int> point1(0, 0);
244 point_data<int> point2(0, 1);
245 point_data<int> point3(1, 0);
246 point_data<int> point4(1, 1);
247 std::vector< point_data<int> > points;
7c673cae
FG		 248 points.push_back(point1);
249 points.push_back(point2);
250 points.push_back(point3);
251 points.push_back(point4);
252 vd_type test_output;
253 construct_voronoi(points.begin(), points.end(), &test_output);
254 VERIFY_OUTPUT(test_output);
255 CHECK_OUTPUT_SIZE(test_output, 4, 1, 8);
256
257 // Check voronoi vertex.
258 const_vertex_iterator it = test_output.vertices().begin();
92f5a8d4
TL		 259 BOOST_TEST_EQ(it->x(), 0.5);
260 BOOST_TEST_EQ(it->y(), 0.5);
7c673cae
FG		 261
262 // Check voronoi edges.
263 const voronoi_edge_type* edge1_1 = it->incident_edge();
264 const voronoi_edge_type* edge1_2 = edge1_1->twin();
92f5a8d4
TL		 265 BOOST_TEST(edge1_1->cell()->source_index() == 3);
266 BOOST_TEST(edge1_2->cell()->source_index() == 2);
7c673cae
FG		 267
268 const voronoi_edge_type* edge2_1 = edge1_1->rot_prev();
269 const voronoi_edge_type* edge2_2 = edge2_1->twin();
92f5a8d4
TL		 270 BOOST_TEST(edge2_1->cell()->source_index() == 2);
271 BOOST_TEST(edge2_2->cell()->source_index() == 0);
7c673cae
FG		 272
273 const voronoi_edge_type* edge3_1 = edge2_1->rot_prev();
274 const voronoi_edge_type* edge3_2 = edge3_1->twin();
92f5a8d4
TL		 275 BOOST_TEST(edge3_1->cell()->source_index() == 0);
276 BOOST_TEST(edge3_2->cell()->source_index() == 1);
7c673cae
FG		 277
278 const voronoi_edge_type* edge4_1 = edge3_1->rot_prev();
279 const voronoi_edge_type* edge4_2 = edge4_1->twin();
92f5a8d4
TL		 280 BOOST_TEST(edge4_1->cell()->source_index() == 1);
281 BOOST_TEST(edge4_2->cell()->source_index() == 3);
282
283 BOOST_TEST(edge1_2->twin() == edge1_1);
284 BOOST_TEST(edge2_2->twin() == edge2_1);
285 BOOST_TEST(edge3_2->twin() == edge3_1);
286 BOOST_TEST(edge4_2->twin() == edge4_1);
287
288 BOOST_TEST(edge1_1->prev() == edge4_2 && edge1_1->next() == edge4_2);
289 BOOST_TEST(edge2_1->prev() == edge1_2 && edge2_1->next() == edge1_2);
290 BOOST_TEST(edge3_1->prev() == edge2_2 && edge3_1->next() == edge2_2);
291 BOOST_TEST(edge4_1->prev() == edge3_2 && edge4_1->next() == edge3_2);
292
293 BOOST_TEST(edge1_2->next() == edge2_1 && edge1_2->prev() == edge2_1);
294 BOOST_TEST(edge2_2->next() == edge3_1 && edge2_2->prev() == edge3_1);
295 BOOST_TEST(edge3_2->next() == edge4_1 && edge3_2->prev() == edge4_1);
296 BOOST_TEST(edge4_2->next() == edge1_1 && edge4_2->prev() == edge1_1);
297
298 BOOST_TEST(edge1_1->rot_next() == edge4_1);
299 BOOST_TEST(edge4_1->rot_next() == edge3_1);
300 BOOST_TEST(edge3_1->rot_next() == edge2_1);
301 BOOST_TEST(edge2_1->rot_next() == edge1_1);
302
303 BOOST_TEST(edge1_2->rot_next() == edge2_2);
304 BOOST_TEST(edge2_2->rot_next() == edge3_2);
305 BOOST_TEST(edge3_2->rot_next() == edge4_2);
306 BOOST_TEST(edge4_2->rot_next() == edge1_2);
7c673cae
FG		 307}
308
309#ifdef NDEBUG
92f5a8d4
TL		 310void grid_test()
311{
7c673cae 312 vd_type test_output_small, test_output_large;
92f5a8d4 313 std::vector< point_data<int> > point_vec_small, point_vec_large;
7c673cae
FG		 314 int grid_size[] = {10, 33, 101};
315 int max_value[] = {10, 33, 101};
316 int array_length = sizeof(grid_size) / sizeof(int);
317 for (int k = 0; k < array_length; k++) {
318 test_output_small.clear();
319 test_output_large.clear();
320 point_vec_small.clear();
321 point_vec_large.clear();
322 int koef = (std::numeric_limits<int>::max)() / max_value[k];
323 for (int i = 0; i < grid_size[k]; i++) {
324 for (int j = 0; j < grid_size[k]; j++) {
92f5a8d4
TL		 325 point_vec_small.push_back(point_data<int>(i, j));
326 point_vec_large.push_back(point_data<int>(koef * i, koef * j));
7c673cae
FG		 327 }
328 }
329 construct_voronoi(point_vec_small.begin(), point_vec_small.end(), &test_output_small);
330 construct_voronoi(point_vec_large.begin(), point_vec_large.end(), &test_output_large);
331 VERIFY_OUTPUT(test_output_small);
332 VERIFY_OUTPUT(test_output_large);
333 unsigned int num_cells = grid_size[k] * grid_size[k];
334 unsigned int num_vertices = num_cells - 2 * grid_size[k] + 1;
335 unsigned int num_edges = 4 * num_cells - 4 * grid_size[k];
336 CHECK_OUTPUT_SIZE(test_output_small, num_cells, num_vertices, num_edges);
337 CHECK_OUTPUT_SIZE(test_output_large, num_cells, num_vertices, num_edges);
338 }
339}
340#endif
341
342#ifdef NDEBUG
92f5a8d4
TL		 343void random_test()
344{
7c673cae
FG		 345 boost::mt19937 gen(static_cast<unsigned int>(time(NULL)));
346 vd_type test_output_small, test_output_large;
92f5a8d4 347 std::vector< point_data<int> > point_vec_small, point_vec_large;
7c673cae
FG		 348 int num_points[] = {10, 100, 1000, 10000};
349 int num_runs[] = {1000, 100, 10, 1};
350 int mod_koef[] = {10, 100, 100, 1000};
351 int max_value[] = {5, 50, 50, 5000};
352 int array_length = sizeof(num_points) / sizeof(int);
353 for (int k = 0; k < array_length; k++) {
354 int koef = (std::numeric_limits<int>::max)() / max_value[k];
355 for (int i = 0; i < num_runs[k]; i++) {
356 test_output_small.clear();
357 test_output_large.clear();
358 point_vec_small.clear();
359 point_vec_large.clear();
360 for (int j = 0; j < num_points[k]; j++) {
92f5a8d4
TL		 361 int x = gen() % mod_koef[k] - mod_koef[k] / 2;
362 int y = gen() % mod_koef[k] - mod_koef[k] / 2;
363 point_vec_small.push_back(point_data<int>(x, y));
364 point_vec_large.push_back(point_data<int>(koef * x, koef * y));
7c673cae
FG		 365 }
366 construct_voronoi(point_vec_small.begin(), point_vec_small.end(), &test_output_small);
367 construct_voronoi(point_vec_large.begin(), point_vec_large.end(), &test_output_large);
368 VERIFY_OUTPUT(test_output_small);
369 VERIFY_OUTPUT(test_output_large);
92f5a8d4
TL		 370 BOOST_TEST_EQ(test_output_small.num_cells(), test_output_large.num_cells());
371 BOOST_TEST_EQ(test_output_small.num_vertices(), test_output_large.num_vertices());
372 BOOST_TEST_EQ(test_output_small.num_edges(), test_output_large.num_edges());
7c673cae
FG		 373 }
374 }
375}
376#endif
377
92f5a8d4
TL		 378void segment_sites_test1()
379{
7c673cae 380 vd_type test_output;
92f5a8d4
TL		 381 std::vector< segment_data<int> > segments;
382 point_data<int> point1(0, 0);
383 point_data<int> point2(1, 1);
384 segments.push_back(segment_data<int>(point1, point2));
7c673cae
FG		 385 construct_voronoi(segments.begin(), segments.end(), &test_output);
386 CHECK_OUTPUT_SIZE(test_output, 3, 0, 4);
387 VERIFY_NO_HALF_EDGE_INTERSECTIONS(test_output);
388}
389
92f5a8d4
TL		 390void segment_sites_test2()
391{
7c673cae 392 vd_type test_output;
92f5a8d4
TL		 393 std::vector< point_data<int> > points;
394 std::vector< segment_data<int> > segments;
395 point_data<int> point1(0, 0);
396 point_data<int> point2(4, 4);
397 point_data<int> point3(3, 1);
398 point_data<int> point4(1, 3);
399 segments.push_back(segment_data<int>(point1, point2));
7c673cae
FG		 400 points.push_back(point3);
401 points.push_back(point4);
402 construct_voronoi(points.begin(), points.end(), segments.begin(), segments.end(), &test_output);
403 CHECK_OUTPUT_SIZE(test_output, 5, 4, 16);
404 VERIFY_NO_HALF_EDGE_INTERSECTIONS(test_output);
405}
406
92f5a8d4
TL		 407void segment_sites_test3()
408{
7c673cae 409 vd_type test_output;
92f5a8d4
TL		 410 std::vector< point_data<int> > points;
411 std::vector< segment_data<int> > segments;
412 point_data<int> point1(4, 0);
413 point_data<int> point2(0, 4);
414 point_data<int> point3(3, 3);
415 point_data<int> point4(1, 1);
416 segments.push_back(segment_data<int>(point1, point2));
7c673cae
FG		 417 points.push_back(point3);
418 points.push_back(point4);
419 construct_voronoi(points.begin(), points.end(), segments.begin(), segments.end(), &test_output);
420 CHECK_OUTPUT_SIZE(test_output, 5, 4, 16);
421 VERIFY_NO_HALF_EDGE_INTERSECTIONS(test_output);
422}
423
92f5a8d4
TL		 424void segment_sites_test4()
425{
7c673cae 426 vd_type test_output;
92f5a8d4
TL		 427 std::vector< point_data<int> > points;
428 std::vector< segment_data<int> > segments;
429 point_data<int> point1(4, 0);
430 point_data<int> point2(0, 4);
431 point_data<int> point3(3, 2);
432 point_data<int> point4(2, 3);
433 segments.push_back(segment_data<int>(point1, point2));
7c673cae
FG		 434 points.push_back(point3);
435 points.push_back(point4);
436 construct_voronoi(points.begin(), points.end(), segments.begin(), segments.end(), &test_output);
437 CHECK_OUTPUT_SIZE(test_output, 5, 3, 14);
438 VERIFY_NO_HALF_EDGE_INTERSECTIONS(test_output);
439}
440
92f5a8d4
TL		 441void segment_site_test5()
442{
7c673cae 443 vd_type test_output;
92f5a8d4
TL		 444 std::vector< point_data<int> > points;
445 std::vector< segment_data<int> > segments;
446 point_data<int> point1(0, 0);
447 point_data<int> point2(0, 8);
448 point_data<int> point3(-2, -2);
449 point_data<int> point4(-2, 4);
450 point_data<int> point5(-2, 10);
451 segments.push_back(segment_data<int>(point1, point2));
7c673cae
FG		 452 points.push_back(point3);
453 points.push_back(point4);
454 points.push_back(point5);
455 construct_voronoi(points.begin(), points.end(), segments.begin(), segments.end(), &test_output);
456 CHECK_OUTPUT_SIZE(test_output, 6, 4, 18);
457 VERIFY_NO_HALF_EDGE_INTERSECTIONS(test_output);
458}
459
92f5a8d4
TL		 460void segment_site_test6()
461{
7c673cae 462 vd_type test_output;
92f5a8d4
TL		 463 std::vector< point_data<int> > points;
464 std::vector< segment_data<int> > segments;
465 point_data<int> point1(-1, 1);
466 point_data<int> point2(1, 0);
467 point_data<int> point3(1, 2);
468 segments.push_back(segment_data<int>(point2, point3));
7c673cae
FG		 469 points.push_back(point1);
470 construct_voronoi(points.begin(), points.end(), segments.begin(), segments.end(), &test_output);
471 CHECK_OUTPUT_SIZE(test_output, 4, 2, 10);
472 VERIFY_NO_HALF_EDGE_INTERSECTIONS(test_output);
473}
474
92f5a8d4
TL		 475void segment_site_test7()
476{
7c673cae 477 vd_type test_output;
92f5a8d4
TL		 478 std::vector< segment_data<int> > segments;
479 point_data<int> point1(0, 0);
480 point_data<int> point2(4, 0);
481 point_data<int> point3(0, 4);
482 point_data<int> point4(4, 4);
483 segments.push_back(segment_data<int>(point1, point2));
484 segments.push_back(segment_data<int>(point2, point3));
485 segments.push_back(segment_data<int>(point3, point4));
7c673cae
FG		 486 construct_voronoi(segments.begin(), segments.end(), &test_output);
487 CHECK_OUTPUT_SIZE(test_output, 7, 6, 24);
488 VERIFY_NO_HALF_EDGE_INTERSECTIONS(test_output);
489}
490
92f5a8d4
TL		 491void segment_site_test8()
492{
7c673cae 493 vd_type test_output;
92f5a8d4
TL		 494 std::vector< segment_data<int> > segments;
495 point_data<int> point1(0, 0);
496 point_data<int> point2(4, 0);
497 point_data<int> point3(4, 4);
498 point_data<int> point4(0, 4);
499 segments.push_back(segment_data<int>(point1, point2));
500 segments.push_back(segment_data<int>(point2, point3));
501 segments.push_back(segment_data<int>(point3, point4));
502 segments.push_back(segment_data<int>(point4, point1));
7c673cae
FG		 503 construct_voronoi(segments.begin(), segments.end(), &test_output);
504 CHECK_OUTPUT_SIZE(test_output, 8, 5, 24);
505 VERIFY_NO_HALF_EDGE_INTERSECTIONS(test_output);
506}
507
92f5a8d4
TL		 508void segment_site_test9()
509{
7c673cae 510 vd_type test_output;
92f5a8d4
TL		 511 std::vector< segment_data<int> > segments;
512 point_data<int> point1(0, 0);
513 point_data<int> point2(2, 0);
514 point_data<int> point3(4, 0);
515 segments.push_back(segment_data<int>(point1, point2));
516 segments.push_back(segment_data<int>(point2, point3));
7c673cae
FG		 517 construct_voronoi(segments.begin(), segments.end(), &test_output);
518 CHECK_OUTPUT_SIZE(test_output, 5, 0, 8);
519 VERIFY_NO_HALF_EDGE_INTERSECTIONS(test_output);
520}
521
522#ifdef NDEBUG
92f5a8d4
TL		 523void segment_grid_test()
524{
7c673cae 525 vd_type test_output_small, test_output_large;
92f5a8d4 526 std::vector< segment_data<int> > segments_small, segments_large;
7c673cae
FG		 527 int grid_size[] = {10, 27, 53};
528 int max_value[] = {100, 330, 1000};
529 int array_length = sizeof(grid_size) / sizeof(int);
530 for (int k = 0; k < array_length; k++) {
531 test_output_small.clear();
532 test_output_large.clear();
533 segments_small.clear();
534 segments_large.clear();
535 int cur_sz = grid_size[k];
536 int koef = (std::numeric_limits<int>::max)() / max_value[k];
537 for (int i = 0; i < cur_sz + 1; i++)
538 for (int j = 0; j < cur_sz; j++) {
92f5a8d4
TL		 539 point_data<int> point1_1(10 * i, 10 * j);
540 point_data<int> point1_2(koef * 10 * i, koef * 10 * j);
541 point_data<int> point2_1(10 * i, 10 * j + 10);
542 point_data<int> point2_2(koef * 10 * i, koef * (10 * j + 10));
543 segments_small.push_back(segment_data<int>(point1_1, point2_1));
544 segments_large.push_back(segment_data<int>(point1_2, point2_2));
545 point_data<int> point3_1(10 * j, 10 * i);
546 point_data<int> point3_2(koef * 10 * j, koef * 10 * i);
547 point_data<int> point4_1(10 * j + 10, 10 * i);
548 point_data<int> point4_2(koef * (10 * j + 10), koef * 10 * i);
549 segments_small.push_back(segment_data<int>(point3_1, point4_1));
550 segments_large.push_back(segment_data<int>(point3_2, point4_2));
7c673cae
FG		 551 }
552 construct_voronoi(segments_small.begin(), segments_small.end(), &test_output_small);
553 construct_voronoi(segments_large.begin(), segments_large.end(), &test_output_large);
554 VERIFY_NO_HALF_EDGE_INTERSECTIONS(test_output_small);
555 VERIFY_NO_HALF_EDGE_INTERSECTIONS(test_output_large);
92f5a8d4
TL		 556 BOOST_TEST_EQ(test_output_small.num_cells(), test_output_large.num_cells());
557 BOOST_TEST_EQ(test_output_small.num_vertices(), test_output_large.num_vertices());
558 BOOST_TEST_EQ(test_output_small.num_edges(), test_output_large.num_edges());
7c673cae
FG		 559 }
560}
561#endif
562
563#ifdef NDEBUG
92f5a8d4
TL		 564void segment_random_test1()
565{
7c673cae
FG		 566 boost::mt19937 gen(static_cast<unsigned int>(time(NULL)));
567 vd_type test_output;
92f5a8d4
TL		 568 std::vector< point_data<int> > points;
569 std::vector< segment_data<int> > segments;
7c673cae
FG		 570 int num_runs = 1000;
571 int num_segments = 10;
92f5a8d4
TL		 572 points.push_back(point_data<int>(-100, -100));
573 points.push_back(point_data<int>(-100, 100));
574 points.push_back(point_data<int>(100, -100));
575 points.push_back(point_data<int>(100, 100));
7c673cae
FG		 576 for (int i = 0; i < num_runs; i++) {
577 test_output.clear();
578 segments.clear();
579 for (int j = 0; j < num_segments; j++) {
92f5a8d4 580 int x1 = 0, y1 = 0, x2 = 0, y2 = 0;
7c673cae
FG		 581 while (x1 == x2 && y1 == y2) {
582 x1 = (gen() % 100) - 50;
583 y1 = (gen() % 100) - 50;
584 x2 = (gen() % 100) - 50;
585 y2 = (gen() % 100) - 50;
586 }
92f5a8d4
TL		 587 point_data<int> point1(x1, y1);
588 point_data<int> point2(x2, y2);
589 segments.push_back(segment_data<int>(point1, point2));
7c673cae
FG		 590 }
591 voronoi_test_helper::clean_segment_set(segments);
592 construct_voronoi(points.begin(), points.end(), segments.begin(), segments.end(), &test_output);
593 VERIFY_NO_HALF_EDGE_INTERSECTIONS(test_output);
594 }
595}
596#endif
597
598#ifdef NDEBUG
92f5a8d4
TL		 599void segment_random_test2()
600{
7c673cae
FG		 601 boost::mt19937 gen(static_cast<unsigned int>(time(NULL)));
602 vd_type test_output_small, test_output_large;
92f5a8d4 603 std::vector< segment_data<int> > segments_small, segments_large;
7c673cae
FG		 604 int num_segments[] = {5, 25, 125, 625};
605 int num_runs[] = {1000, 100, 10, 1};
606 int mod_koef1[] = {10, 100, 200, 300};
607 int mod_koef2[] = {10, 20, 50, 100};
608 int max_value[] = {10, 60, 125, 200};
609 int array_length = sizeof(num_segments) / sizeof(int);
610 for (int k = 0; k < array_length; k++) {
611 int koef = (std::numeric_limits<int>::max)() / max_value[k];
612 for (int i = 0; i < num_runs[k]; i++) {
613 test_output_small.clear();
614 test_output_large.clear();
615 segments_small.clear();
616 segments_large.clear();
617 for (int j = 0; j < num_segments[k]; j++) {
92f5a8d4
TL		 618 int x1 = (gen() % mod_koef1[k]) - mod_koef1[k] / 2;
619 int y1 = (gen() % mod_koef1[k]) - mod_koef1[k] / 2;
620 int dx = 0, dy = 0;
7c673cae
FG		 621 while (dx == 0 && dy == 0) {
622 dx = (gen() % mod_koef2[k]) - mod_koef2[k] / 2;
623 dy = (gen() % mod_koef2[k]) - mod_koef2[k] / 2;
624 }
92f5a8d4
TL		 625 int x2 = x1 + dx;
626 int y2 = y1 + dy;
627 point_data<int> point1_small(x1, y1);
628 point_data<int> point2_small(x2, y2);
629 segments_small.push_back(segment_data<int>(point1_small, point2_small));
7c673cae
FG		 630 }
631 voronoi_test_helper::clean_segment_set(segments_small);
92f5a8d4 632 for (std::vector< segment_data<int> >::iterator it = segments_small.begin();
7c673cae 633 it != segments_small.end(); ++it) {
92f5a8d4
TL		 634 int x1 = it->low().x() * koef;
635 int y1 = it->low().y() * koef;
636 int x2 = it->high().x() * koef;
637 int y2 = it->high().y() * koef;
638 point_data<int> point1_large(x1, y1);
639 point_data<int> point2_large(x2, y2);
640 segments_large.push_back(segment_data<int>(point1_large, point2_large));
7c673cae
FG		 641 }
642 construct_voronoi(segments_small.begin(), segments_small.end(), &test_output_small);
643 construct_voronoi(segments_large.begin(), segments_large.end(), &test_output_large);
644 VERIFY_NO_HALF_EDGE_INTERSECTIONS(test_output_small);
645 VERIFY_NO_HALF_EDGE_INTERSECTIONS(test_output_large);
92f5a8d4
TL		 646 BOOST_TEST_EQ(test_output_small.num_cells(), test_output_large.num_cells());
647 BOOST_TEST_EQ(test_output_small.num_vertices(), test_output_large.num_vertices());
648 BOOST_TEST_EQ(test_output_small.num_edges(), test_output_large.num_edges());
7c673cae
FG		 649 }
650 }
651}
652#endif
92f5a8d4
TL		 653
654int main()
655{
656 single_site_test();
657 collinear_sites_test1();
658 collinear_sites_test2();
659 triangle_test1();
660 triangle_test2();
661 square_test1();
662#ifdef NDEBUG
663 grid_test();
664 random_test();
665#endif
666 segment_sites_test1();
667 segment_sites_test2();
668 segment_sites_test3();
669 segment_sites_test4();
670 segment_site_test5();
671 segment_site_test6();
672 segment_site_test7();
673 segment_site_test8();
674 segment_site_test9();
675#ifdef NDEBUG
676 segment_grid_test();
677 segment_random_test1();
678 segment_random_test2();
679#endif
680 return boost::report_errors();
681}
Ceph