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