ceph/src/boost/libs/polygon/test/voronoi_predicates_test.cpp

   1 // Boost.Polygon library voronoi_predicates_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
  10 #include <boost/core/lightweight_test.hpp>
  11 #include <boost/polygon/detail/voronoi_ctypes.hpp>
  12 #include <boost/polygon/detail/voronoi_predicates.hpp>
  13 #include <boost/polygon/detail/voronoi_structures.hpp>
  14 #include <boost/polygon/voronoi_geometry_type.hpp>
  15 #include <limits>
  16 #include <map>
  17
  18 using namespace boost::polygon::detail;
  19 using namespace boost::polygon;
  20
  21 ulp_comparison<double> ulp_cmp;
  22
  23 typedef voronoi_predicates< voronoi_ctype_traits<int> > VP;
  24 typedef point_2d<int> point_type;
  25 typedef site_event<int> site_type;
  26 typedef circle_event<double> circle_type;
  27 VP::event_comparison_predicate<site_type, circle_type> event_comparison;
  28
  29 typedef beach_line_node_key<site_type> key_type;
  30 typedef VP::distance_predicate<site_type> distance_predicate_type;
  31 typedef VP::node_comparison_predicate<key_type> node_comparison_type;
  32 typedef std::map<key_type, int, node_comparison_type> beach_line_type;
  33 typedef beach_line_type::iterator bieach_line_iterator;
  34 distance_predicate_type distance_predicate;
  35 node_comparison_type node_comparison;
  36
  37 typedef VP::circle_existence_predicate<site_type> CEP_type;
  38 typedef VP::mp_circle_formation_functor<site_type, circle_type> MP_CFF_type;
  39 typedef VP::lazy_circle_formation_functor<site_type, circle_type> lazy_CFF_type;
  40 VP::circle_formation_predicate<site_type, circle_type, CEP_type, MP_CFF_type> mp_predicate;
  41 VP::circle_formation_predicate<site_type, circle_type, CEP_type, lazy_CFF_type> lazy_predicate;
  42
  43 #define CHECK_ORIENTATION(P1, P2, P3, R1, R2) \
  44     BOOST_TEST_EQ(VP::ot::eval(P1, P2, P3) == R1, true); \
  45     BOOST_TEST_EQ(VP::ot::eval(P1, P3, P2) == R2, true); \
  46     BOOST_TEST_EQ(VP::ot::eval(P2, P1, P3) == R2, true); \
  47     BOOST_TEST_EQ(VP::ot::eval(P2, P3, P1) == R1, true); \
  48     BOOST_TEST_EQ(VP::ot::eval(P3, P1, P2) == R1, true); \
  49     BOOST_TEST_EQ(VP::ot::eval(P3, P2, P1) == R2, true)
  50
  51 #define CHECK_EVENT_COMPARISON(A, B, R1, R2) \
  52     BOOST_TEST_EQ(event_comparison(A, B), R1); \
  53     BOOST_TEST_EQ(event_comparison(B, A), R2)
  54
  55 #define CHECK_DISTANCE_PREDICATE(S1, S2, P3, RES) \
  56     BOOST_TEST_EQ(distance_predicate(S1, S2, P3), RES)
  57
  58 #define CHECK_NODE_COMPARISON(node, nodes, res, sz) \
  59     for (int i = 0; i < sz; ++i) { \
  60       BOOST_TEST_EQ(node_comparison(node, nodes[i]), res[i]); \
  61       BOOST_TEST_EQ(node_comparison(nodes[i], node), !res[i]); \
  62     }
  63
  64 #define CHECK_CIRCLE(circle, c_x, c_y, l_x) \
  65     BOOST_TEST_EQ(ulp_cmp(c1.x(), c_x, 10), ulp_comparison<double>::EQUAL); \
  66     BOOST_TEST_EQ(ulp_cmp(c1.y(), c_y, 10), ulp_comparison<double>::EQUAL); \
  67     BOOST_TEST_EQ(ulp_cmp(c1.lower_x(), l_x, 10), ulp_comparison<double>::EQUAL)
  68
  69 #define CHECK_CIRCLE_EXISTENCE(s1, s2, s3, RES) \
  70   { circle_type c1; \
  71     BOOST_TEST_EQ(lazy_predicate(s1, s2, s3, c1), RES); }
  72
  73 #define CHECK_CIRCLE_FORMATION_PREDICATE(s1, s2, s3, c_x, c_y, l_x) \
  74   { circle_type c1, c2; \
  75     BOOST_TEST_EQ(mp_predicate(s1, s2, s3, c1), true); \
  76     BOOST_TEST_EQ(lazy_predicate(s1, s2, s3, c2), true); \
  77     CHECK_CIRCLE(c1, c_x, c_y, l_x); \
  78     CHECK_CIRCLE(c2, c_x, c_y, l_x); }
  79
  80 void orientation_test()
  81 {
  82   int min_int = (std::numeric_limits<int>::min)();
  83   int max_int = (std::numeric_limits<int>::max)();
  84   point_type point1(min_int, min_int);
  85   point_type point2(0, 0);
  86   point_type point3(max_int, max_int);
  87   point_type point4(min_int, max_int);
  88   point_type point5(max_int-1, max_int);
  89   CHECK_ORIENTATION(point1, point2, point3, VP::ot::COLLINEAR, VP::ot::COLLINEAR);
  90   CHECK_ORIENTATION(point1, point4, point3, VP::ot::RIGHT, VP::ot::LEFT);
  91   CHECK_ORIENTATION(point1, point5, point3, VP::ot::RIGHT, VP::ot::LEFT);
  92 }
  93
  94 void event_comparison_test1()
  95 {
  96   site_type site(1, 2);
  97   CHECK_EVENT_COMPARISON(site, site_type(0, 2), false, true);
  98   CHECK_EVENT_COMPARISON(site, site_type(1, 3), true, false);
  99   CHECK_EVENT_COMPARISON(site, site_type(1, 2), false, false);
 100 }
 101
 102 void event_comparison_test2()
 103 {
 104   site_type site(0, 0, 0, 2);
 105   CHECK_EVENT_COMPARISON(site, site_type(0, 2), true, false);
 106   CHECK_EVENT_COMPARISON(site, site_type(0, 0), false, true);
 107   CHECK_EVENT_COMPARISON(site, site_type(0, -2, 0, -1), false, true);
 108   CHECK_EVENT_COMPARISON(site, site_type(0, -2, 1, 1), true, false);
 109   CHECK_EVENT_COMPARISON(site, site_type(0, 0, 1, 1), true, false);
 110 }
 111
 112 void event_comparison_test3()
 113 {
 114   site_type site(0, 0, 10, 10);
 115   CHECK_EVENT_COMPARISON(site, site_type(0, 0), false, true);
 116   CHECK_EVENT_COMPARISON(site, site_type(0, -1), false, true);
 117   CHECK_EVENT_COMPARISON(site, site_type(0, 1), false, true);
 118   CHECK_EVENT_COMPARISON(site, site_type(0, 1, 0, 10), false, true);
 119   CHECK_EVENT_COMPARISON(site, site_type(0, -10, 0, -1), false, true);
 120   CHECK_EVENT_COMPARISON(site, site_type(0, 0, 10, 9), true, false);
 121   CHECK_EVENT_COMPARISON(site, site_type(0, 0, 9, 10), false, true);
 122 }
 123
 124 void event_comparison_test4()
 125 {
 126   circle_type circle(1, 2, 3);
 127   CHECK_EVENT_COMPARISON(circle, circle_type(1, 2, 3), false, false);
 128   CHECK_EVENT_COMPARISON(circle, circle_type(1, 3, 3), true, false);
 129   CHECK_EVENT_COMPARISON(circle, circle_type(1, 2, 4), true, false);
 130   CHECK_EVENT_COMPARISON(circle, circle_type(0, 2, 2), false, true);
 131   CHECK_EVENT_COMPARISON(circle, circle_type(-1, 2, 3), false, false);
 132 }
 133
 134 void event_comparison_test5()
 135 {
 136   circle_type circle(1, 2, 3);
 137   CHECK_EVENT_COMPARISON(circle, site_type(0, 100), false, true);
 138   CHECK_EVENT_COMPARISON(circle, site_type(3, 0), false, false);
 139   CHECK_EVENT_COMPARISON(circle, site_type(3, 2), false, false);
 140   CHECK_EVENT_COMPARISON(circle, site_type(3, 3), false, false);
 141   CHECK_EVENT_COMPARISON(circle, site_type(4, 2), true, false);
 142 }
 143
 144 void distance_predicate_test1()
 145 {
 146   site_type site1(-5, 0);
 147   site1.sorted_index(1);
 148   site_type site2(-8, 9);
 149   site2.sorted_index(0);
 150   site_type site3(-2, 1);
 151   site3.sorted_index(2);
 152   CHECK_DISTANCE_PREDICATE(site1, site2, point_type(0, 5), false);
 153   CHECK_DISTANCE_PREDICATE(site3, site1, point_type(0, 5), false);
 154   CHECK_DISTANCE_PREDICATE(site1, site2, point_type(0, 4), false);
 155   CHECK_DISTANCE_PREDICATE(site3, site1, point_type(0, 4), false);
 156   CHECK_DISTANCE_PREDICATE(site1, site2, point_type(0, 6), true);
 157   CHECK_DISTANCE_PREDICATE(site3, site1, point_type(0, 6), true);
 158 }
 159
 160 void distance_predicate_test2()
 161 {
 162   site_type site1(-4, 0, -4, 20);
 163   site1.sorted_index(0);
 164   site_type site2(-2, 10);
 165   site2.sorted_index(1);
 166   CHECK_DISTANCE_PREDICATE(site2, site1, point_type(0, 11), false);
 167   CHECK_DISTANCE_PREDICATE(site2, site1, point_type(0, 9), false);
 168   CHECK_DISTANCE_PREDICATE(site1, site2, point_type(0, 11), true);
 169   CHECK_DISTANCE_PREDICATE(site1, site2, point_type(0, 9), true);
 170 }
 171
 172 void distance_predicate_test3()
 173 {
 174   site_type site1(-5, 5, 2, -2);
 175   site1.sorted_index(0);
 176   site1.inverse();
 177   site_type site2(-2, 4);
 178   site2.sorted_index(1);
 179   CHECK_DISTANCE_PREDICATE(site1, site2, point_type(0, -1), false);
 180   CHECK_DISTANCE_PREDICATE(site2, site1, point_type(0, -1), false);
 181   CHECK_DISTANCE_PREDICATE(site1, site2, point_type(0, 1), false);
 182   CHECK_DISTANCE_PREDICATE(site2, site1, point_type(0, 1), false);
 183   CHECK_DISTANCE_PREDICATE(site1, site2, point_type(0, 4), true);
 184   CHECK_DISTANCE_PREDICATE(site2, site1, point_type(0, 4), false);
 185   CHECK_DISTANCE_PREDICATE(site1, site2, point_type(0, 5), true);
 186   CHECK_DISTANCE_PREDICATE(site2, site1, point_type(0, 5), false);
 187 }
 188
 189 void distance_predicate_test4()
 190 {
 191   site_type site1(-5, 5, 2, -2);
 192   site1.sorted_index(0);
 193   site_type site2(-2, -4);
 194   site2.sorted_index(2);
 195   site_type site3(-4, 1);
 196   site3.sorted_index(1);
 197   CHECK_DISTANCE_PREDICATE(site1, site2, point_type(0, 1), true);
 198   CHECK_DISTANCE_PREDICATE(site2, site1, point_type(0, 1), true);
 199   CHECK_DISTANCE_PREDICATE(site1, site3, point_type(0, 1), true);
 200   CHECK_DISTANCE_PREDICATE(site3, site1, point_type(0, 1), true);
 201   CHECK_DISTANCE_PREDICATE(site1, site2, point_type(0, -2), true);
 202   CHECK_DISTANCE_PREDICATE(site2, site1, point_type(0, -2), false);
 203   CHECK_DISTANCE_PREDICATE(site1, site3, point_type(0, -2), true);
 204   CHECK_DISTANCE_PREDICATE(site3, site1, point_type(0, -2), false);
 205   CHECK_DISTANCE_PREDICATE(site1, site2, point_type(0, -8), true);
 206   CHECK_DISTANCE_PREDICATE(site2, site1, point_type(0, -8), false);
 207   CHECK_DISTANCE_PREDICATE(site1, site3, point_type(0, -8), true);
 208   CHECK_DISTANCE_PREDICATE(site3, site1, point_type(0, -8), false);
 209   CHECK_DISTANCE_PREDICATE(site1, site2, point_type(0, -9), true);
 210   CHECK_DISTANCE_PREDICATE(site2, site1, point_type(0, -9), false);
 211   CHECK_DISTANCE_PREDICATE(site1, site3, point_type(0, -9), true);
 212   CHECK_DISTANCE_PREDICATE(site3, site1, point_type(0, -9), false);
 213 }
 214
 215 void distance_predicate_test5()
 216 {
 217   site_type site1(-5, 5, 2, -2);
 218   site1.sorted_index(0);
 219   site_type site2 = site1;
 220   site2.inverse();
 221   site_type site3(-2, 4);
 222   site3.sorted_index(3);
 223   site_type site4(-2, -4);
 224   site4.sorted_index(2);
 225   site_type site5(-4, 1);
 226   site5.sorted_index(1);
 227   CHECK_DISTANCE_PREDICATE(site3, site2, point_type(0, 1), false);
 228   CHECK_DISTANCE_PREDICATE(site3, site2, point_type(0, 4), false);
 229   CHECK_DISTANCE_PREDICATE(site3, site2, point_type(0, 5), false);
 230   CHECK_DISTANCE_PREDICATE(site3, site2, point_type(0, 7), true);
 231   CHECK_DISTANCE_PREDICATE(site4, site1, point_type(0, -2), false);
 232   CHECK_DISTANCE_PREDICATE(site5, site1, point_type(0, -2), false);
 233   CHECK_DISTANCE_PREDICATE(site4, site1, point_type(0, -8), false);
 234   CHECK_DISTANCE_PREDICATE(site5, site1, point_type(0, -8), false);
 235   CHECK_DISTANCE_PREDICATE(site4, site1, point_type(0, -9), false);
 236   CHECK_DISTANCE_PREDICATE(site5, site1, point_type(0, -9), false);
 237   CHECK_DISTANCE_PREDICATE(site4, site1, point_type(0, -18), false);
 238   CHECK_DISTANCE_PREDICATE(site5, site1, point_type(0, -18), false);
 239   CHECK_DISTANCE_PREDICATE(site4, site1, point_type(0, -1), true);
 240   CHECK_DISTANCE_PREDICATE(site5, site1, point_type(0, -1), true);
 241 }
 242
 243 void distance_predicate_test6()
 244 {
 245   site_type site1(-5, 0, 2, 7);
 246   site_type site2 = site1;
 247   site2.inverse();
 248   CHECK_DISTANCE_PREDICATE(site1, site2, point_type(2, 7), false);
 249   CHECK_DISTANCE_PREDICATE(site1, site2, point_type(1, 5), false);
 250   CHECK_DISTANCE_PREDICATE(site1, site2, point_type(-1, 5), true);
 251 }
 252
 253 void distance_predicate_test7()
 254 {
 255   site_type site1(-5, 5, 2, -2);
 256   site1.sorted_index(1);
 257   site1.inverse();
 258   site_type site2(-5, 5, 0, 6);
 259   site2.sorted_index(0);
 260   site_type site3(-2, 4, 0, 4);
 261   site3.sorted_index(2);
 262   point_type site4(0, 2);
 263   point_type site5(0, 5);
 264   point_type site6(0, 6);
 265   point_type site7(0, 8);
 266   CHECK_DISTANCE_PREDICATE(site1, site2, site4, false);
 267   CHECK_DISTANCE_PREDICATE(site1, site2, site5, true);
 268   CHECK_DISTANCE_PREDICATE(site1, site2, site6, true);
 269   CHECK_DISTANCE_PREDICATE(site1, site2, site7, true);
 270   CHECK_DISTANCE_PREDICATE(site1, site3, site4, false);
 271   CHECK_DISTANCE_PREDICATE(site1, site3, site5, true);
 272   CHECK_DISTANCE_PREDICATE(site1, site3, site6, true);
 273   CHECK_DISTANCE_PREDICATE(site1, site3, site7, true);
 274   site3.inverse();
 275   CHECK_DISTANCE_PREDICATE(site3, site1, site4, false);
 276   CHECK_DISTANCE_PREDICATE(site3, site1, site5, false);
 277   CHECK_DISTANCE_PREDICATE(site3, site1, site6, false);
 278   CHECK_DISTANCE_PREDICATE(site3, site1, site7, true);
 279 }
 280
 281 void distance_predicate_test8()
 282 {
 283   site_type site1(-5, 3, -2, 2);
 284   site1.sorted_index(0);
 285   site1.inverse();
 286   site_type site2(-5, 5, -2, 2);
 287   site2.sorted_index(1);
 288   CHECK_DISTANCE_PREDICATE(site1, site2, point_type(-4, 2), false);
 289 }
 290
 291 void node_comparison_test1()
 292 {
 293   beach_line_type beach_line;
 294   site_type site1(0, 0);
 295   site1.sorted_index(0);
 296   site_type site2(0, 2);
 297   site2.sorted_index(1);
 298   site_type site3(1, 0);
 299   site3.sorted_index(2);
 300   beach_line[key_type(site1, site2)] = 2;
 301   beach_line[key_type(site1, site3)] = 0;
 302   beach_line[key_type(site3, site1)] = 1;
 303   int cur_index = 0;
 304   for (bieach_line_iterator it = beach_line.begin();
 305        it != beach_line.end(); ++it, ++cur_index) {
 306     BOOST_TEST_EQ(it->second, cur_index);
 307   }
 308 }
 309
 310 void node_comparison_test2()
 311 {
 312   beach_line_type beach_line;
 313   site_type site1(0, 1);
 314   site1.sorted_index(0);
 315   site_type site2(2, 0);
 316   site2.sorted_index(1);
 317   site_type site3(2, 4);
 318   site3.sorted_index(2);
 319   beach_line[key_type(site1, site2)] = 0;
 320   beach_line[key_type(site2, site1)] = 1;
 321   beach_line[key_type(site1, site3)] = 2;
 322   beach_line[key_type(site3, site1)] = 3;
 323   int cur_index = 0;
 324   for (bieach_line_iterator it = beach_line.begin();
 325        it != beach_line.end(); ++it, ++cur_index) {
 326     BOOST_TEST_EQ(it->second, cur_index);
 327   }
 328 }
 329
 330 void node_comparison_test3()
 331 {
 332   key_type node(site_type(1, 0).sorted_index(1), site_type(0, 2).sorted_index(0));
 333   key_type nodes[] = {
 334     key_type(site_type(2, -10).sorted_index(2)),
 335     key_type(site_type(2, -1).sorted_index(2)),
 336     key_type(site_type(2, 0).sorted_index(2)),
 337     key_type(site_type(2, 1).sorted_index(2)),
 338     key_type(site_type(2, 2).sorted_index(2)),
 339     key_type(site_type(2, 3).sorted_index(2)),
 340   };
 341   bool res[] = {false, false, false, false, true, true};
 342   CHECK_NODE_COMPARISON(node, nodes, res, 6);
 343 }
 344
 345 void node_comparison_test4()
 346 {
 347   key_type node(site_type(0, 1).sorted_index(0), site_type(1, 0).sorted_index(1));
 348   key_type nodes[] = {
 349     key_type(site_type(2, -3).sorted_index(2)),
 350     key_type(site_type(2, -2).sorted_index(2)),
 351     key_type(site_type(2, -1).sorted_index(2)),
 352     key_type(site_type(2, 0).sorted_index(2)),
 353     key_type(site_type(2, 1).sorted_index(2)),
 354     key_type(site_type(2, 3).sorted_index(2)),
 355   };
 356   bool res[] = {false, true, true, true, true, true};
 357   CHECK_NODE_COMPARISON(node, nodes, res, 6);
 358 }
 359
 360 void node_comparison_test5()
 361 {
 362   key_type node(site_type(0, 0).sorted_index(0), site_type(1, 2).sorted_index(1));
 363   key_type nodes[] = {
 364     key_type(site_type(2, -10).sorted_index(2)),
 365     key_type(site_type(2, 0).sorted_index(2)),
 366     key_type(site_type(2, 1).sorted_index(2)),
 367     key_type(site_type(2, 2).sorted_index(2)),
 368     key_type(site_type(2, 5).sorted_index(2)),
 369     key_type(site_type(2, 20).sorted_index(2)),
 370   };
 371   bool res[] = {false, false, true, true, true, true};
 372   CHECK_NODE_COMPARISON(node, nodes, res, 6);
 373 }
 374
 375 void node_comparison_test6()
 376 {
 377   key_type node(site_type(1, 1).sorted_index(1), site_type(0, 0).sorted_index(0));
 378   key_type nodes[] = {
 379     key_type(site_type(2, -3).sorted_index(2)),
 380     key_type(site_type(2, -2).sorted_index(2)),
 381     key_type(site_type(2, 0).sorted_index(2)),
 382     key_type(site_type(2, 1).sorted_index(2)),
 383     key_type(site_type(2, 2).sorted_index(2)),
 384     key_type(site_type(2, 3).sorted_index(2)),
 385     key_type(site_type(2, 5).sorted_index(2)),
 386   };
 387   bool res[] = {false, false, false, false, false, false, true};
 388   CHECK_NODE_COMPARISON(node, nodes, res, 7);
 389 }
 390
 391 void node_comparison_test7()
 392 {
 393   key_type node(site_type(0, 0).sorted_index(0), site_type(0, 2).sorted_index(1));
 394   key_type nodes[] = {
 395     key_type(site_type(1, 0).sorted_index(2)),
 396     key_type(site_type(1, 1).sorted_index(2)),
 397     key_type(site_type(1, 2).sorted_index(2)),
 398   };
 399   bool res[] = {false, false, true};
 400   CHECK_NODE_COMPARISON(node, nodes, res, 3);
 401 }
 402
 403 void node_comparison_test8()
 404 {
 405   key_type node(site_type(0, 0).sorted_index(0), site_type(1, 1).sorted_index(2));
 406   key_type nodes[] = {
 407     key_type(site_type(1, 0).sorted_index(1)),
 408     key_type(site_type(1, 1).sorted_index(2)),
 409     key_type(site_type(1, 2).sorted_index(3)),
 410     key_type(site_type(1, 1).sorted_index(2), site_type(0, 0).sorted_index(0)),
 411   };
 412   bool res[] = {false, true, true, true};
 413   CHECK_NODE_COMPARISON(node, nodes, res, 4);
 414 }
 415
 416 void circle_formation_predicate_test1()
 417 {
 418   site_type site1(0, 0);
 419   site1.sorted_index(1);
 420   site_type site2(-8, 0);
 421   site2.sorted_index(0);
 422   site_type site3(0, 6);
 423   site3.sorted_index(2);
 424   CHECK_CIRCLE_FORMATION_PREDICATE(site1, site2, site3, -4.0, 3.0, 1.0);
 425 }
 426
 427 void circle_formation_predicate_test2()
 428 {
 429   int min_int = (std::numeric_limits<int>::min)();
 430   int max_int = (std::numeric_limits<int>::max)();
 431   site_type site1(min_int, min_int);
 432   site1.sorted_index(0);
 433   site_type site2(min_int, max_int);
 434   site2.sorted_index(1);
 435   site_type site3(max_int-1, max_int-1);
 436   site3.sorted_index(2);
 437   site_type site4(max_int, max_int);
 438   site4.sorted_index(3);
 439   CHECK_CIRCLE_EXISTENCE(site1, site2, site4, true);
 440   CHECK_CIRCLE_EXISTENCE(site1, site3, site4, false);
 441 }
 442
 443 void circle_formation_predicate_test3()
 444 {
 445   site_type site1(-4, 0);
 446   site1.sorted_index(0);
 447   site_type site2(0, 4);
 448   site2.sorted_index(4);
 449   site_type site3(site1.point0(), site2.point0());
 450   site3.sorted_index(1);
 451   CHECK_CIRCLE_EXISTENCE(site1, site3, site2, false);
 452   site_type site4(-2, 0);
 453   site4.sorted_index(2);
 454   site_type site5(0, 2);
 455   site5.sorted_index(3);
 456   CHECK_CIRCLE_EXISTENCE(site3, site4, site5, false);
 457   CHECK_CIRCLE_EXISTENCE(site4, site5, site3, false);
 458 }
 459
 460 void circle_formation_predicate_test4()
 461 {
 462   site_type site1(-4, 0, -4, 20);
 463   site1.sorted_index(0);
 464   site_type site2(-2, 10);
 465   site2.sorted_index(1);
 466   site_type site3(4, 10);
 467   site3.sorted_index(2);
 468   CHECK_CIRCLE_FORMATION_PREDICATE(site1, site2, site3, 1.0, 6.0, 6.0);
 469   CHECK_CIRCLE_FORMATION_PREDICATE(site3, site2, site1, 1.0, 14.0, 6.0);
 470 }
 471
 472 void circle_formation_predicate_test5()
 473 {
 474   site_type site1(1, 0, 7, 0);
 475   site1.sorted_index(2);
 476   site1.inverse();
 477   site_type site2(-2, 4, 10, 4);
 478   site2.sorted_index(0);
 479   site_type site3(6, 2);
 480   site3.sorted_index(3);
 481   site_type site4(1, 0);
 482   site4.sorted_index(1);
 483   CHECK_CIRCLE_FORMATION_PREDICATE(site3, site1, site2, 4.0, 2.0, 6.0);
 484   CHECK_CIRCLE_FORMATION_PREDICATE(site4, site2, site1, 1.0, 2.0, 3.0);
 485 }
 486
 487 void circle_formation_predicate_test6()
 488 {
 489   site_type site1(-1, 2, 8, -10);
 490   site1.sorted_index(1);
 491   site1.inverse();
 492   site_type site2(-1, 0, 8, 12);
 493   site2.sorted_index(0);
 494   site_type site3(1, 1);
 495   site3.sorted_index(2);
 496   CHECK_CIRCLE_FORMATION_PREDICATE(site3, site2, site1, 6.0, 1.0, 11.0);
 497 }
 498
 499 void circle_formation_predicate_test7()
 500 {
 501   site_type site1(1, 0, 6, 0);
 502   site1.sorted_index(2);
 503   site1.inverse();
 504   site_type site2(-6, 4, 0, 12);
 505   site2.sorted_index(0);
 506   site_type site3(1, 0);
 507   site3.sorted_index(1);
 508   CHECK_CIRCLE_FORMATION_PREDICATE(site3, site2, site1, 1.0, 5.0, 6.0);
 509 }
 510
 511 void circle_formation_predicate_test8()
 512 {
 513   site_type site1(1, 0, 5, 0);
 514   site1.sorted_index(2);
 515   site1.inverse();
 516   site_type site2(0, 12, 8, 6);
 517   site2.sorted_index(0);
 518   site_type site3(1, 0);
 519   site3.sorted_index(1);
 520   CHECK_CIRCLE_FORMATION_PREDICATE(site3, site2, site1, 1.0, 5.0, 6.0);
 521 }
 522
 523 void circle_formation_predicate_test9()
 524 {
 525   site_type site1(0, 0, 4, 0);
 526   site1.sorted_index(1);
 527   site_type site2(0, 0, 0, 4);
 528   site2.sorted_index(0);
 529   site_type site3(0, 4, 4, 4);
 530   site3.sorted_index(2);
 531   site1.inverse();
 532   CHECK_CIRCLE_FORMATION_PREDICATE(site1, site2, site3, 2.0, 2.0, 4.0);
 533 }
 534
 535 void circle_formation_predicate_test10()
 536 {
 537   site_type site1(1, 0, 41, 30);
 538   site1.sorted_index(1);
 539   site_type site2(-39, 30, 1, 60);
 540   site2.sorted_index(0);
 541   site_type site3(1, 60, 41, 30);
 542   site3.sorted_index(2);
 543   site1.inverse();
 544   CHECK_CIRCLE_FORMATION_PREDICATE(site1, site2, site3, 1.0, 30.0, 25.0);
 545 }
 546
 547 void circle_formation_predicate_test11()
 548 {
 549   site_type site1(0, 0, 0, 10);
 550   site1.sorted_index(2);
 551   site1.inverse();
 552   site_type site2(-8, 10);
 553   site2.sorted_index(0);
 554   site_type site3(-7, 14, -1, 14);
 555   site3.sorted_index(1);
 556   CHECK_CIRCLE_FORMATION_PREDICATE(site1, site2, site3, -4.0, 10.0, 0.0);
 557 }
 558
 559 void circle_formation_predicate_test12()
 560 {
 561   site_type site1(0, 0, 0, 10);
 562   site1.sorted_index(2);
 563   site1.inverse();
 564   site_type site2(-8, 10);
 565   site2.sorted_index(0);
 566   site_type site3(-7, 15, -1, 15);
 567   site3.sorted_index(1);
 568   CHECK_CIRCLE_EXISTENCE(site1, site2, site3, false);
 569 }
 570
 571 void circle_formation_predicate_test13()
 572 {
 573   site_type site1(0, 0, 0, 10);
 574   site1.sorted_index(2);
 575   site1.inverse();
 576   site_type site2(-7, -4, -1, -4);
 577   site2.sorted_index(1);
 578   site2.inverse();
 579   site_type site3(-8, 0);
 580   site3.sorted_index(0);
 581   CHECK_CIRCLE_FORMATION_PREDICATE(site1, site2, site3, -4.0, 0.0, 0.0);
 582 }
 583
 584 void circle_formation_predicate_test14()
 585 {
 586   site_type site1(0, 0, 0, 10);
 587   site1.sorted_index(2);
 588   site1.inverse();
 589   site_type site2(-7, -5, -1, -5);
 590   site2.sorted_index(1);
 591   site2.inverse();
 592   site_type site3(-8, 0);
 593   site3.sorted_index(0);
 594   CHECK_CIRCLE_EXISTENCE(site1, site2, site3, false);
 595 }
 596
 597 int main()
 598 {
 599     orientation_test();
 600     event_comparison_test1();
 601     event_comparison_test2();
 602     event_comparison_test3();
 603     event_comparison_test4();
 604     event_comparison_test5();
 605     distance_predicate_test1();
 606     distance_predicate_test2();
 607     distance_predicate_test3();
 608     distance_predicate_test4();
 609     distance_predicate_test5();
 610     distance_predicate_test6();
 611     distance_predicate_test7();
 612     distance_predicate_test8();
 613     node_comparison_test1();
 614     node_comparison_test2();
 615     node_comparison_test3();
 616     node_comparison_test4();
 617     node_comparison_test5();
 618     node_comparison_test6();
 619     node_comparison_test7();
 620     node_comparison_test8();
 621     circle_formation_predicate_test1();
 622     circle_formation_predicate_test2();
 623     circle_formation_predicate_test3();
 624     circle_formation_predicate_test4();
 625     circle_formation_predicate_test5();
 626     circle_formation_predicate_test6();
 627     circle_formation_predicate_test7();
 628     circle_formation_predicate_test8();
 629     circle_formation_predicate_test9();
 630     circle_formation_predicate_test10();
 631     circle_formation_predicate_test11();
 632     circle_formation_predicate_test12();
 633     circle_formation_predicate_test13();
 634     circle_formation_predicate_test14();
 635     return boost::report_errors();
 636 }