libs/geometry/test/algorithms/overlay/get_turn_info.cpp

   1 // Boost.Geometry (aka GGL, Generic Geometry Library)
   2 // Unit Test
   3
   4 // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
   5
   6 // This file was modified by Oracle on 2017.
   7 // Modifications copyright (c) 2017, Oracle and/or its affiliates.
   8 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
   9
  10 // Use, modification and distribution is subject to the Boost Software License,
  11 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
  12 // http://www.boost.org/LICENSE_1_0.txt)
  13
  14 #include <iostream>
  15
  16 #include <geometry_test_common.hpp>
  17
  18 #include <boost/array.hpp>
  19 #include <boost/foreach.hpp>
  20
  21 #include <boost/geometry/algorithms/intersection.hpp>
  22 #include <boost/geometry/algorithms/make.hpp>
  23
  24 #include <boost/geometry/algorithms/detail/overlay/get_turn_info.hpp>
  25 #include <boost/geometry/algorithms/detail/overlay/debug_turn_info.hpp>
  26 #include <boost/geometry/geometries/point_xy.hpp>
  27
  28 #if defined(TEST_WITH_SVG)
  29 #  include <boost/geometry/io/svg/svg_mapper.hpp>
  30 #endif
  31
  32
  33 // For test purposes, returns the point specified in the constructor
  34 template <typename Point>
  35 struct sub_range_from_points
  36 {
  37     typedef Point point_type;
  38
  39     sub_range_from_points(Point const& i, Point const& j, Point const& k)
  40     {
  41         m_points[0] = i;
  42         m_points[1] = j;
  43         m_points[2] = k;
  44     }
  45
  46     static inline bool is_first_segment() { return false; }
  47     static inline bool is_last_segment() { return false; }
  48
  49     static inline std::size_t size() { return 3; }
  50
  51     inline Point const& at(std::size_t index) const
  52     {
  53         return m_points[index % 3];
  54     }
  55
  56 private :
  57     boost::array<Point, 3> m_points;
  58 };
  59
  60 template <typename P, typename T>
  61 void test_with_point(std::string const& caseid,
  62                 T pi_x, T pi_y, T pj_x, T pj_y, T pk_x, T pk_y,
  63                 T qi_x, T qi_y, T qj_x, T qj_y, T qk_x, T qk_y,
  64                 bg::detail::overlay::method_type expected_method,
  65                 bool expected_touch_only,
  66                 T ip_x, T ip_y,
  67                 std::string const& expected,
  68                 T ip_x2, T ip_y2)
  69 {
  70     P pi = bg::make<P>(pi_x, pi_y);
  71     P pj = bg::make<P>(pj_x, pj_y);
  72     P pk = bg::make<P>(pk_x, pk_y);
  73     P qi = bg::make<P>(qi_x, qi_y);
  74     P qj = bg::make<P>(qj_x, qj_y);
  75     P qk = bg::make<P>(qk_x, qk_y);
  76
  77     typedef typename bg::strategy::intersection::services::default_strategy
  78         <
  79             typename bg::cs_tag<P>::type
  80         >::type strategy_type;
  81
  82     typedef typename bg::detail::no_rescale_policy rescale_policy_type;
  83
  84     typedef bg::detail::overlay::turn_info
  85         <
  86             P,
  87             typename bg::detail::segment_ratio_type<P, rescale_policy_type>::type
  88         > turn_info;
  89     typedef std::vector<turn_info> tp_vector;
  90     turn_info model;
  91     tp_vector info;
  92     strategy_type strategy;
  93     rescale_policy_type rescale_policy;
  94     sub_range_from_points<P> sub_range_p(pi, pj, pk);
  95     sub_range_from_points<P> sub_range_q(qi, qj, qk);
  96     bg::detail::overlay::get_turn_info
  97         <
  98             bg::detail::overlay::assign_null_policy
  99         >::apply(sub_range_p, sub_range_q, model, strategy, rescale_policy, std::back_inserter(info));
 100
 101     if (info.size() == 0)
 102     {
 103         BOOST_CHECK_EQUAL(expected_method,
 104                 bg::detail::overlay::method_none);
 105     }
 106
 107     std::string detected;
 108     std::string method;
 109     for (typename tp_vector::const_iterator it = info.begin(); it != info.end(); ++it)
 110     {
 111         for (int t = 0; t < 2; t++)
 112         {
 113             detected += bg::operation_char(it->operations[t].operation);
 114             method += bg::method_char(it->method);
 115         }
 116     }
 117
 118     BOOST_CHECK_MESSAGE(detected == expected,
 119         caseid
 120             << (caseid.find("_") == std::string::npos ? "  " : "")
 121             << " method: " << method
 122             << " detected: " << detected
 123             << " expected: " << expected);
 124
 125
 126     if (! info.empty())
 127     {
 128         BOOST_CHECK_EQUAL(info[0].method, expected_method);
 129         BOOST_CHECK_MESSAGE(info[0].touch_only == expected_touch_only,
 130                 caseid
 131                 << " detected: " << info[0].touch_only
 132                 << " expected: " << expected_touch_only);
 133         BOOST_CHECK_CLOSE(bg::get<0>(info[0].point), ip_x, 0.001);
 134         BOOST_CHECK_CLOSE(bg::get<1>(info[0].point), ip_y, 0.001);
 135
 136         if (info.size() > 1)
 137         {
 138             BOOST_CHECK_EQUAL(info.size(), 2u);
 139             BOOST_CHECK_EQUAL(info[1].method, expected_method);
 140             BOOST_CHECK_CLOSE(bg::get<0>(info[1].point), ip_x2, 0.001);
 141             BOOST_CHECK_CLOSE(bg::get<1>(info[1].point), ip_y2, 0.001);
 142         }
 143     }
 144
 145 #if defined(TEST_WITH_SVG)
 146     {
 147         std::ostringstream filename;
 148         filename << "get_turn_info_" << caseid
 149             << "_" << string_from_type<typename bg::coordinate_type<P>::type>::name()
 150             << ".svg";
 151
 152         std::ofstream svg(filename.str().c_str());
 153
 154         bg::svg_mapper<P> mapper(svg, 500, 500);
 155         mapper.add(bg::make<P>(0, 0));
 156         mapper.add(bg::make<P>(10, 10));
 157
 158         bg::model::linestring<P> p; p.push_back(pi); p.push_back(pj); p.push_back(pk);
 159         bg::model::linestring<P> q; q.push_back(qi); q.push_back(qj); q.push_back(qk);
 160         mapper.map(p, "opacity:0.8;stroke:rgb(0,192,0);stroke-width:3");
 161         mapper.map(q, "opacity:0.8;stroke:rgb(0,0,255);stroke-width:3");
 162
 163         std::string style =  ";font-family='Verdana';font-weight:bold";
 164         std::string align = ";text-anchor:end;text-align:end";
 165         int offset = 8;
 166
 167         mapper.text(pi, "pi", "fill:rgb(0,192,0)" + style, offset, offset);
 168         mapper.text(pj, "pj", "fill:rgb(0,192,0)" + style, offset, offset);
 169         mapper.text(pk, "pk", "fill:rgb(0,192,0)" + style, offset, offset);
 170
 171         mapper.text(qi, "qi", "fill:rgb(0,0,255)" + style + align, -offset, offset);
 172         mapper.text(qj, "qj", "fill:rgb(0,0,255)" + style + align, -offset, offset);
 173         mapper.text(qk, "qk", "fill:rgb(0,0,255)" + style + align, -offset, offset);
 174
 175
 176         int factor = 1; // second info, if any, will go left by factor -1
 177         int ch = '1';
 178         for (typename tp_vector::const_iterator it = info.begin();
 179             it != info.end();
 180             ++it, factor *= -1, ch++)
 181         {
 182             bool at_j = it->method == bg::detail::overlay::method_crosses;
 183             std::string op;
 184             op += bg::operation_char(it->operations[0].operation);
 185             align = ";text-anchor:middle;text-align:center";
 186             mapper.text(at_j ? pj : pk, op, "fill:rgb(255,128,0)" + style + align, offset * factor, -offset);
 187
 188             op.clear();
 189             op += bg::operation_char(it->operations[1].operation);
 190             mapper.text(at_j ? qj : qk, op, "fill:rgb(255,128,0)" + style + align, offset * factor, -offset);
 191
 192             // Map intersection point + method
 193             mapper.map(it->point, "opacity:0.8;fill:rgb(255,0,0);stroke:rgb(0,0,100);stroke-width:1");
 194
 195             op.clear();
 196             op += bg::method_char(it->method);
 197             op += ' ';
 198             op += (it->touch_only ? 'o' : '*');
 199             if (info.size() != 1)
 200             {
 201                 op += ch;
 202                 op += " p:"; op += bg::operation_char(it->operations[0].operation);
 203                 op += " q:"; op += bg::operation_char(it->operations[1].operation);
 204             }
 205             mapper.text(it->point, op, "fill:rgb(255,0,0)" + style, offset, -offset);
 206         }
 207     }
 208 #endif
 209
 210 }
 211
 212 template <typename P, typename T>
 213 void test_both(std::string const& caseid,
 214                 T pi_x, T pi_y, T pj_x, T pj_y, T pk_x, T pk_y,
 215                 T qi_x, T qi_y, T qj_x, T qj_y, T qk_x, T qk_y,
 216                 bg::detail::overlay::method_type method
 217                     = bg::detail::overlay::method_none,
 218                 bool expected_touch_only = false,
 219                 T ip_x = -1, T ip_y = -1,
 220                 std::string const& expected = "",
 221                 T ip_x2 = -1, T ip_y2 = -1)
 222 {
 223     test_with_point<P, double>(caseid,
 224             pi_x, pi_y, pj_x, pj_y, pk_x, pk_y,
 225             qi_x, qi_y, qj_x, qj_y, qk_x, qk_y,
 226             method, expected_touch_only, ip_x, ip_y, expected, ip_x2, ip_y2);
 227
 228     std::string reversed(expected.rbegin(), expected.rend());
 229
 230     if (ip_x2 >= 0 && ip_y2 >= 0)
 231     {
 232         std::swap(ip_x, ip_x2);
 233         std::swap(ip_y, ip_y2);
 234     }
 235
 236     test_with_point<P, double>(caseid + "_r",
 237             qi_x, qi_y, qj_x, qj_y, qk_x, qk_y, // q
 238             pi_x, pi_y, pj_x, pj_y, pk_x, pk_y, // p
 239             method, expected_touch_only, ip_x, ip_y, reversed, ip_x2, ip_y2);
 240 }
 241
 242
 243 template <typename P>
 244 void test_all()
 245 {
 246     using namespace bg::detail::overlay;
 247
 248     // See powerpoint "doc/testcases/get_turn_info.ppt"
 249
 250
 251     // ------------------------------------------------------------------------
 252     // "Real" intersections ("i"), or, crossing
 253     // ------------------------------------------------------------------------
 254     test_both<P, double>("il1",
 255             5, 1,   5, 6,   7, 8, // p
 256             3, 3,   7, 5,   8, 3, // q
 257             method_crosses, false, 5, 4, "ui");
 258
 259     test_both<P, double>("il2",
 260             5, 1,   5, 6,   7, 8, // p
 261             3, 5,   7, 5,   3, 3, // q
 262             method_crosses, false, 5, 5, "ui");
 263
 264     test_both<P, double>("il3",
 265             5, 1,   5, 6,   7, 8, // p
 266             3, 3,   7, 5,   3, 5, // q
 267             method_crosses, false, 5, 4, "ui");
 268
 269     test_both<P, double>("il4",
 270             5, 1,   5, 6,   7, 8, // p
 271             3, 3,   7, 5,   4, 8, // q
 272             method_crosses, false, 5, 4, "ui");
 273
 274     test_both<P, double>("ir1",
 275             5, 1,   5, 6,   7, 8, // p
 276             7, 5,   3, 3,   2, 5, // q
 277             method_crosses, false, 5, 4, "iu");
 278
 279
 280     // ------------------------------------------------------------------------
 281     // TOUCH INTERIOR or touch in the middle ("m")
 282     // ------------------------------------------------------------------------
 283     test_both<P, double>("ml1",
 284             5, 1,   5, 6,   7, 8, // p
 285             3, 3,   5, 4,   7, 3, // q
 286             method_touch_interior, false, 5, 4, "ui");
 287
 288     test_both<P, double>("ml2",
 289             5, 1,   5, 6,   7, 8, // p
 290             3, 3,   5, 4,   3, 6, // q
 291             method_touch_interior, true, 5, 4, "iu");
 292
 293     test_both<P, double>("ml3",
 294             5, 1,   5, 6,   7, 8, // p
 295             3, 6,   5, 4,   3, 3, // q
 296             method_touch_interior, true, 5, 4, "uu");
 297
 298     test_both<P, double>("mr1",
 299             5, 1,   5, 6,   7, 8, // p
 300             7, 3,   5, 4,   3, 3, // q
 301             method_touch_interior, false, 5, 4, "iu");
 302
 303     test_both<P, double>("mr2",
 304             5, 1,   5, 6,   7, 8, // p
 305             7, 3,   5, 4,   7, 6, // q
 306             method_touch_interior, true, 5, 4, "ui");
 307
 308     test_both<P, double>("mr3",
 309             5, 1,   5, 6,   7, 8, // p
 310             7, 6,   5, 4,   7, 3, // q
 311             method_touch_interior, true, 5, 4, "ii");
 312
 313     test_both<P, double>("mcl",
 314             5, 1,   5, 6,   7, 8, // p
 315             3, 2,   5, 3,   5, 5, // q
 316             method_touch_interior, false, 5, 3, "cc");
 317
 318     test_both<P, double>("mcr",
 319             5, 1,   5, 6,   7, 8, // p
 320             7, 2,   5, 3,   5, 5, // q
 321             method_touch_interior, false, 5, 3, "cc");
 322
 323     test_both<P, double>("mclo",
 324             5, 1,   5, 6,   7, 8, // p
 325             3, 4,   5, 5,   5, 3, // q
 326             method_touch_interior, false, 5, 5, "ux");
 327
 328     test_both<P, double>("mcro",
 329             5, 1,   5, 6,   7, 8, // p
 330             7, 4,   5, 5,   5, 3, // q
 331             method_touch_interior, false, 5, 5, "ix");
 332
 333     // ------------------------------------------------------------------------
 334     // COLLINEAR
 335     // ------------------------------------------------------------------------
 336     test_both<P, double>("cll1",
 337             5, 1,   5, 6,   3, 8, // p
 338             5, 5,   5, 7,   3, 8, // q
 339             method_collinear, false, 5, 6, "ui");
 340     test_both<P, double>("cll2",
 341             5, 1,   5, 6,   3, 8, // p
 342             5, 3,   5, 5,   3, 6, // q
 343             method_collinear, false, 5, 5, "iu");
 344     test_both<P, double>("clr1",
 345             5, 1,   5, 6,   3, 8, // p
 346             5, 5,   5, 7,   6, 8, // q
 347             method_collinear, false, 5, 6, "ui");
 348     test_both<P, double>("clr2",
 349             5, 1,   5, 6,   3, 8, // p
 350             5, 3,   5, 5,   6, 6, // q
 351             method_collinear, false, 5, 5, "ui");
 352
 353     test_both<P, double>("crl1",
 354             5, 1,   5, 6,   7, 8, // p
 355             5, 5,   5, 7,   3, 8, // q
 356             method_collinear, false, 5, 6, "iu");
 357     test_both<P, double>("crl2",
 358             5, 1,   5, 6,   7, 8, // p
 359             5, 3,   5, 5,   3, 6, // q
 360             method_collinear, false, 5, 5, "iu");
 361     test_both<P, double>("crr1",
 362             5, 1,   5, 6,   7, 8, // p
 363             5, 5,   5, 7,   6, 8, // q
 364             method_collinear, false, 5, 6, "iu");
 365     test_both<P, double>("crr2",
 366             5, 1,   5, 6,   7, 8, // p
 367             5, 3,   5, 5,   6, 6, // q
 368             method_collinear, false, 5, 5, "ui");
 369
 370     // The next two cases are changed (BSG 2013-09-24), they contain turn info (#buffer_rt_g)
 371     // In new approach they are changed back (BSG 2013-10-20)
 372     test_both<P, double>("ccx1",
 373             5, 1,   5, 6,   5, 8, // p
 374             5, 5,   5, 7,   3, 8, // q
 375             method_collinear, false, 5, 6, "cc"); // "iu");
 376     test_both<P, double>("cxc1",
 377             5, 1,   5, 6,   7, 8, // p
 378             5, 3,   5, 5,   5, 7, // q
 379             method_collinear, false, 5, 5, "cc"); // "iu");
 380
 381     // Bug in case #54 of "overlay_cases.hpp"
 382     test_both<P, double>("c_bug1",
 383             5, 0,   2, 0,   2, 2, // p
 384             4, 0,   1, 0,   1, 2, // q
 385             method_collinear, false, 2, 0, "iu");
 386
 387
 388     // ------------------------------------------------------------------------
 389     // COLLINEAR OPPOSITE
 390     // ------------------------------------------------------------------------
 391
 392     test_both<P, double>("clo1",
 393             5, 2,   5, 6,   3, 8, // p
 394             5, 7,   5, 5,   3, 3, // q
 395             method_collinear, false, 5, 6, "ixxu", 5, 5);
 396     test_both<P, double>("clo2",
 397             5, 2,   5, 6,   3, 8, // p
 398             5, 7,   5, 5,   5, 2, // q
 399             method_collinear, false, 5, 6, "ix");
 400                 // actually "xxix", xx is skipped everywhere
 401     test_both<P, double>("clo3",
 402             5, 2,   5, 6,   3, 8, // p
 403             5, 7,   5, 5,   7, 3, // q
 404             method_collinear, false, 5, 6, "ixxi", 5, 5);
 405
 406     test_both<P, double>("cco1",
 407             5, 2,   5, 6,   5, 8, // p
 408             5, 7,   5, 5,   3, 3, // q
 409             method_collinear, false, 5, 5, "xu"); // "xuxx"
 410     test_both<P, double>("cco2",
 411             5, 2,   5, 6,   5, 8, // p
 412             5, 7,   5, 5,   5, 2); // q "xxxx"
 413     test_both<P, double>("cco3",
 414             5, 2,   5, 6,   5, 8, // p
 415             5, 7,   5, 5,   7, 3, // q
 416             method_collinear, false, 5, 5, "xi"); // "xixx"
 417
 418
 419     test_both<P, double>("cro1",
 420             5, 2,   5, 6,   7, 8, // p
 421             5, 7,   5, 5,   3, 3, // q
 422             method_collinear, false, 5, 6, "uxxu", 5, 5);
 423     test_both<P, double>("cro2",
 424             5, 2,   5, 6,   7, 8, // p
 425             5, 7,   5, 5,   5, 2, // q
 426             method_collinear, false, 5, 6, "ux"); // "xxux"
 427     test_both<P, double>("cro3",
 428             5, 2,   5, 6,   7, 8, // p
 429             5, 7,   5, 5,   7, 3, // q
 430             method_collinear, false, 5, 6, "uxxi", 5, 5);
 431
 432     test_both<P, double>("cxo1",
 433             5, 2,   5, 6,   3, 8, // p
 434             5, 5,   5, 3,   3, 1, // q
 435             method_collinear, false, 5, 3, "xu");
 436     test_both<P, double>("cxo2",
 437             5, 2,   5, 6,   3, 8, // p
 438             5, 5,   5, 3,   5, 0); // q   "xx"
 439     test_both<P, double>("cxo3",
 440             5, 2,   5, 6,   3, 8, // p
 441             5, 5,   5, 3,   7, 1, // q
 442             method_collinear, false, 5, 3, "xi");
 443
 444     test_both<P, double>("cxo4",
 445             5, 2,   5, 6,   3, 8, // p
 446             5, 7,   5, 1,   3, 0, // q
 447             method_collinear, false, 5, 6, "ix");
 448     test_both<P, double>("cxo5",
 449             5, 2,   5, 6,   5, 8, // p
 450             5, 7,   5, 1,   3, 0); // q  "xx"
 451     test_both<P, double>("cxo6",
 452             5, 2,   5, 6,   7, 8, // p
 453             5, 7,   5, 1,   3, 0, // q
 454             method_collinear, false, 5, 6, "ux");
 455
 456
 457     // Verify
 458     test_both<P, double>("cvo1",
 459             5, 3,   5, 7,   7, 9, // p
 460             5, 5,   5, 3,   3, 1 // q
 461             );
 462     test_both<P, double>("cvo2",
 463             5, 3,   5, 7,   7, 9, // p
 464             5, 4,   5, 2,   3, 0 // q
 465             );
 466
 467
 468     // ------------------------------------------------------------------------
 469     // TOUCH - both same
 470     // ------------------------------------------------------------------------
 471     // Both left, Q turns right
 472     test_both<P, double>("blr1",
 473             5, 1,   5, 6,   4, 4, // p
 474             3, 7,   5, 6,   3, 5, // q
 475             method_touch, true, 5, 6, "ui");
 476     test_both<P, double>("blr2",
 477             5, 1,   5, 6,   1, 4, // p
 478             3, 7,   5, 6,   3, 5, // q
 479             method_touch, false, 5, 6, "cc");
 480     test_both<P, double>("blr3",
 481             5, 1,   5, 6,   3, 6, // p
 482             3, 7,   5, 6,   3, 5, // q
 483             method_touch, false, 5, 6, "iu");
 484     test_both<P, double>("blr4",
 485             5, 1,   5, 6,   1, 8, // p
 486             3, 7,   5, 6,   3, 5, // q
 487             method_touch, false, 5, 6, "xu");
 488     test_both<P, double>("blr5",
 489             5, 1,   5, 6,   4, 8, // p
 490             3, 7,   5, 6,   3, 5, // q
 491             method_touch, true, 5, 6, "uu");
 492     test_both<P, double>("blr6",
 493             5, 1,   5, 6,   6, 4, // p
 494             3, 7,   5, 6,   3, 5, // q
 495             method_touch, true, 5, 6, "uu");
 496
 497     test_both<P, double>("blr7",
 498             5, 1,   5, 6,   3, 6, // p
 499             3, 7,   5, 6,   5, 3, // q
 500             method_touch, false, 5, 6, "ix");
 501     test_both<P, double>("blr8",
 502             5, 1,   5, 6,   3, 6, // p
 503             3, 6,   5, 6,   5, 3, // q
 504             method_touch, false, 5, 6, "xx");
 505     test_both<P, double>("blr9",
 506             5, 1,   5, 6,   3, 6, // p
 507             3, 5,   5, 6,   5, 3, // q
 508             method_touch, false, 5, 6, "ux");
 509
 510     // Variants
 511     test_both<P, double>("blr7-a",
 512             5, 1,   5, 6,   3, 6, // p
 513             5, 8,   5, 6,   5, 3, // q
 514             method_touch, false, 5, 6, "ix");
 515     test_both<P, double>("blr7-b", // in fact NOT "both-left"
 516             5, 1,   5, 6,   3, 6, // p
 517             6, 8,   5, 6,   5, 3, // q
 518             method_touch, false, 5, 6, "ix");
 519
 520     // To check if "collinear-check" on other side
 521     // does not apply to this side
 522     test_both<P, double>("blr6-c1",
 523             5, 1,   5, 6,   7, 5, // p
 524             3, 7,   5, 6,   3, 5, // q
 525             method_touch, true, 5, 6, "uu");
 526     test_both<P, double>("blr6-c2",
 527             5, 1,   5, 6,   7, 7, // p
 528             3, 7,   5, 6,   3, 5, // q
 529             method_touch, true, 5, 6, "uu");
 530
 531
 532
 533     // Both right, Q turns right
 534     test_both<P, double>("brr1",
 535             5, 1,   5, 6,   6, 4, // p
 536             7, 5,   5, 6,   7, 7, // q
 537             method_touch, true, 5, 6, "uu");
 538     test_both<P, double>("brr2",
 539             5, 1,   5, 6,   9, 4, // p
 540             7, 5,   5, 6,   7, 7, // q
 541             method_touch, false, 5, 6, "xu");
 542     test_both<P, double>("brr3",
 543             5, 1,   5, 6,   7, 6, // p
 544             7, 5,   5, 6,   7, 7, // q
 545             method_touch, false, 5, 6, "iu");
 546     test_both<P, double>("brr4",
 547             5, 1,   5, 6,   9, 8, // p
 548             7, 5,   5, 6,   7, 7, // q
 549             method_touch, false, 5, 6, "cc");
 550     test_both<P, double>("brr5",
 551             5, 1,   5, 6,   6, 8, // p
 552             7, 5,   5, 6,   7, 7, // q
 553             method_touch, true, 5, 6, "ui");
 554     test_both<P, double>("brr6",
 555             5, 1,   5, 6,   4, 4, // p
 556             7, 5,   5, 6,   7, 7, // q
 557             method_touch, true, 5, 6, "ui");
 558
 559     // Both right, Q turns left
 560     test_both<P, double>("brl1",
 561             5, 1,   5, 6,   6, 4, // p
 562             7, 7,   5, 6,   7, 5, // q
 563             method_touch, true, 5, 6, "iu");
 564     test_both<P, double>("brl2",
 565             5, 1,   5, 6,   9, 4, // p
 566             7, 7,   5, 6,   7, 5, // q
 567             method_touch, false, 5, 6, "cc");
 568     test_both<P, double>("brl3",
 569             5, 1,   5, 6,   7, 6, // p
 570             7, 7,   5, 6,   7, 5, // q
 571             method_touch, false, 5, 6, "ui");
 572     test_both<P, double>("brl4",
 573             5, 1,   5, 6,   9, 8, // p
 574             7, 7,   5, 6,   7, 5, // q
 575             method_touch, false, 5, 6, "xi");
 576     test_both<P, double>("brl5",
 577             5, 1,   5, 6,   6, 8, // p
 578             7, 7,   5, 6,   7, 5, // q
 579             method_touch, true, 5, 6, "ii");
 580     test_both<P, double>("brl6",
 581             5, 1,   5, 6,   4, 4, // p
 582             7, 7,   5, 6,   7, 5, // q
 583             method_touch, true, 5, 6, "ii");
 584     test_both<P, double>("brl7",
 585             5, 1,   5, 6,   7, 6, // p
 586             7, 7,   5, 6,   5, 3, // q
 587             method_touch, false, 5, 6, "ux");
 588     test_both<P, double>("brl8",
 589             5, 1,   5, 6,   7, 6, // p
 590             7, 6,   5, 6,   5, 3, // q
 591             method_touch, false, 5, 6, "xx");
 592     test_both<P, double>("brl9",
 593             5, 1,   5, 6,   7, 6, // p
 594             7, 5,   5, 6,   5, 3, // q
 595             method_touch, false, 5, 6, "ix");
 596
 597     // Variants
 598     test_both<P, double>("brl7-a",
 599             5, 1,   5, 6,   7, 6, // p
 600             5, 8,   5, 6,   5, 3, // q
 601             method_touch, false, 5, 6, "ux");
 602     test_both<P, double>("brl7-b", // in fact NOT "both right"
 603             5, 1,   5, 6,   7, 6, // p
 604             4, 8,   5, 6,   5, 3, // q
 605             method_touch, false, 5, 6, "ux");
 606
 607
 608
 609     // Both left, Q turns left
 610     test_both<P, double>("bll1",
 611             5, 1,   5, 6,   4, 4, // p
 612             3, 5,   5, 6,   3, 7, // q
 613             method_touch, true, 5, 6, "ii");
 614     test_both<P, double>("bll2",
 615             5, 1,   5, 6,   1, 4, // p
 616             3, 5,   5, 6,   3, 7, // q
 617             method_touch, false, 5, 6, "xi");
 618     test_both<P, double>("bll3",
 619             5, 1,   5, 6,   3, 6, // p
 620             3, 5,   5, 6,   3, 7, // q
 621             method_touch, false, 5, 6, "ui");
 622     test_both<P, double>("bll4",
 623             5, 1,   5, 6,   1, 8, // p
 624             3, 5,   5, 6,   3, 7, // q
 625             method_touch, false, 5, 6, "cc");
 626     test_both<P, double>("bll5",
 627             5, 1,   5, 6,   4, 8, // p
 628             3, 5,   5, 6,   3, 7, // q
 629             method_touch, true, 5, 6, "iu");
 630     test_both<P, double>("bll6",
 631             5, 1,   5, 6,   6, 4, // p
 632             3, 5,   5, 6,   3, 7, // q
 633             method_touch, true, 5, 6, "iu");
 634
 635     // TOUCH - COLLINEAR + one side
 636     // Collinear/left, Q turns right
 637     test_both<P, double>("t-clr1",
 638             5, 1,   5, 6,   4, 4, // p
 639             5, 8,   5, 6,   3, 5, // q
 640             method_touch, true, 5, 6, "ui");
 641     test_both<P, double>("t-clr2",
 642             5, 1,   5, 6,   1, 4, // p
 643             5, 8,   5, 6,   3, 5, // q
 644             method_touch, false, 5, 6, "cc");
 645     test_both<P, double>("t-clr3",
 646             5, 1,   5, 6,   3, 6, // p
 647             5, 8,   5, 6,   3, 5, // q
 648             method_touch, false, 5, 6, "iu");
 649     test_both<P, double>("t-clr4",
 650             5, 1,   5, 6,   5, 8, // p
 651             5, 8,   5, 6,   3, 5, // q
 652             method_touch, false, 5, 6, "xu");
 653     // 5 n.a.
 654     test_both<P, double>("t-clr6",
 655             5, 1,   5, 6,   6, 4, // p
 656             5, 8,   5, 6,   3, 5, // q
 657             method_touch, true, 5, 6, "uu");
 658
 659     // Collinear/right, Q turns right
 660     test_both<P, double>("t-crr1",
 661             5, 1,   5, 6,   6, 4, // p
 662             7, 5,   5, 6,   5, 8, // q
 663             method_touch, true, 5, 6, "uu");
 664     test_both<P, double>("t-crr2",
 665             5, 1,   5, 6,   9, 4, // p
 666             7, 5,   5, 6,   5, 8, // q
 667             method_touch, false, 5, 6, "xu");
 668     test_both<P, double>("t-crr3",
 669             5, 1,   5, 6,   7, 6, // p
 670             7, 5,   5, 6,   5, 8, // q
 671             method_touch, false, 5, 6, "iu");
 672     test_both<P, double>("t-crr4",
 673             5, 1,   5, 6,   5, 9, // p
 674             7, 5,   5, 6,   5, 8, // q
 675             method_touch, false, 5, 6, "cc");
 676     // 5 n.a.
 677     test_both<P, double>("t-crr6",
 678             5, 1,   5, 6,   4, 4, // p
 679             7, 5,   5, 6,   5, 8, // q
 680             method_touch, true, 5, 6, "ui");
 681
 682     // Collinear/right, Q turns left
 683     test_both<P, double>("t-crl1",
 684             5, 1,   5, 6,   6, 4, // p
 685             5, 7,   5, 6,   7, 5, // q
 686             method_touch, true, 5, 6, "iu");
 687     test_both<P, double>("t-crl2",
 688             5, 1,   5, 6,   9, 4, // p
 689             5, 7,   5, 6,   7, 5, // q
 690             method_touch, false, 5, 6, "cc");
 691     test_both<P, double>("t-crl3",
 692             5, 1,   5, 6,   7, 6, // p
 693             5, 7,   5, 6,   7, 5, // q
 694             method_touch, false, 5, 6, "ui");
 695     test_both<P, double>("t-crl4",
 696             5, 1,   5, 6,   5, 8, // p
 697             5, 7,   5, 6,   7, 5, // q
 698             method_touch, false, 5, 6, "xi");
 699     // 5 n.a.
 700     test_both<P, double>("t-crl6",
 701             5, 1,   5, 6,   4, 4, // p
 702             5, 7,   5, 6,   7, 5, // q
 703             method_touch, true, 5, 6, "ii");
 704
 705     // Collinear/left, Q turns left
 706     test_both<P, double>("t-cll1",
 707             5, 1,   5, 6,   4, 4, // p
 708             3, 5,   5, 6,   5, 8, // q
 709             method_touch, true, 5, 6, "ii");
 710     test_both<P, double>("t-cll2",
 711             5, 1,   5, 6,   1, 4, // p
 712             3, 5,   5, 6,   5, 8, // q
 713             method_touch, false, 5, 6, "xi");
 714     test_both<P, double>("t-cll3",
 715             5, 1,   5, 6,   3, 6, // p
 716             3, 5,   5, 6,   5, 8, // q
 717             method_touch, false, 5, 6, "ui");
 718     test_both<P, double>("t-cll4",
 719             5, 1,   5, 6,   5, 9, // p
 720             3, 5,   5, 6,   5, 8, // q
 721             method_touch, false, 5, 6, "cc");
 722     // 5 n.a.
 723     test_both<P, double>("t-cll6",
 724             5, 1,   5, 6,   6, 4, // p
 725             3, 5,   5, 6,   5, 8, // q
 726             method_touch, true, 5, 6, "iu");
 727
 728     // Left to right
 729     test_both<P, double>("lr1",
 730             5, 1,   5, 6,   3, 3, // p
 731             1, 5,   5, 6,   9, 5, // q
 732             method_touch, true, 5, 6, "ii");
 733     test_both<P, double>("lr2",
 734             5, 1,   5, 6,   1, 5, // p
 735             1, 5,   5, 6,   9, 5, // q
 736             method_touch, false, 5, 6, "xi");
 737     test_both<P, double>("lr3",
 738             5, 1,   5, 6,   4, 8, // p
 739             1, 5,   5, 6,   9, 5, // q
 740             method_touch, false, 5, 6, "ui");
 741     test_both<P, double>("lr4",
 742             5, 1,   5, 6,   9, 5, // p
 743             1, 5,   5, 6,   9, 5, // q
 744             method_touch, false, 5, 6, "cc");
 745     test_both<P, double>("lr5",
 746             5, 1,   5, 6,   7, 3, // p
 747             1, 5,   5, 6,   9, 5, // q
 748             method_touch, true, 5, 6, "iu");
 749     // otherwise case more thoroughly
 750     test_both<P, double>("lr3a",
 751             5, 1,   5, 6,   1, 6, // p
 752             1, 5,   5, 6,   9, 5, // q
 753             method_touch, false, 5, 6, "ui");
 754     test_both<P, double>("lr3b",
 755             5, 1,   5, 6,   5, 10, // p
 756             1, 5,   5, 6,   9, 5, // q
 757             method_touch, false, 5, 6, "ui");
 758     test_both<P, double>("lr3c",
 759             5, 1,   5, 6,   8, 9, // p
 760             1, 5,   5, 6,   9, 5, // q
 761             method_touch, false, 5, 6, "ui");
 762     test_both<P, double>("lr3d",
 763             5, 1,   5, 6,   9, 7, // p
 764             1, 5,   5, 6,   9, 5, // q
 765             method_touch, false, 5, 6, "ui");
 766     test_both<P, double>("lr3e",
 767             5, 1,   5, 6,   9, 6, // p
 768             1, 5,   5, 6,   9, 5, // q
 769             method_touch, false, 5, 6, "ui");
 770
 771     // Right to left
 772     test_both<P, double>("rl1",
 773             5, 1,   5, 6,   3, 3, // p
 774             9, 5,   5, 6,   1, 5, // q
 775             method_touch, true, 5, 6, "ui");
 776     test_both<P, double>("rl2",
 777             5, 1,   5, 6,   1, 5, // p
 778             9, 5,   5, 6,   1, 5, // q
 779             method_touch, false, 5, 6, "cc");
 780     test_both<P, double>("rl3",
 781             5, 1,   5, 6,   4, 8, // p
 782             9, 5,   5, 6,   1, 5, // q
 783             method_touch, false, 5, 6, "iu");
 784     test_both<P, double>("rl4",
 785             5, 1,   5, 6,   9, 5, // p
 786             9, 5,   5, 6,   1, 5, // q
 787             method_touch, false, 5, 6, "xu");
 788     test_both<P, double>("rl5",
 789             5, 1,   5, 6,   7, 3, // p
 790             9, 5,   5, 6,   1, 5, // q
 791             method_touch, true, 5, 6, "uu");
 792
 793     // Equal (p1/q1 are equal)
 794     test_both<P, double>("ebl1",
 795             5, 1,   5, 6,   3, 4, // p
 796             5, 1,   5, 6,   3, 8, // q
 797             method_equal, false, 5, 6, "ui");
 798     test_both<P, double>("ebl2",
 799             5, 1,   5, 6,   3, 8, // p
 800             5, 1,   5, 6,   3, 4, // q
 801             method_equal, false, 5, 6, "iu");
 802     test_both<P, double>("ebl3",
 803             5, 1,   5, 6,   3, 8, // p
 804             5, 1,   5, 6,   3, 8, // q
 805             method_equal, false, 5, 6, "cc");
 806
 807     test_both<P, double>("ebl3-c1",
 808             5, 1,   5, 6,   10, 1, // p
 809             5, 1,   5, 6,   3, 8, // q
 810             method_equal, false, 5, 6, "iu");
 811
 812     test_both<P, double>("ebr1",
 813             5, 1,   5, 6,   7, 4, // p
 814             5, 1,   5, 6,   7, 8, // q
 815             method_equal, false, 5, 6, "iu");
 816     test_both<P, double>("ebr2",
 817             5, 1,   5, 6,   7, 8, // p
 818             5, 1,   5, 6,   7, 4, // q
 819             method_equal, false, 5, 6, "ui");
 820     test_both<P, double>("ebr3",
 821             5, 1,   5, 6,   7, 8, // p
 822             5, 1,   5, 6,   7, 8, // q
 823             method_equal, false, 5, 6, "cc");
 824
 825     test_both<P, double>("ebr3-c1",
 826             5, 1,   5, 6,   0, 1, // p
 827             5, 1,   5, 6,   7, 8, // q
 828             method_equal, false, 5, 6, "ui");
 829
 830     test_both<P, double>("elr1",
 831             5, 1,   5, 6,   7, 8, // p
 832             5, 1,   5, 6,   3, 8, // q
 833             method_equal, false, 5, 6, "iu");
 834     test_both<P, double>("elr2",
 835             5, 1,   5, 6,   3, 8, // p
 836             5, 1,   5, 6,   7, 8, // q
 837             method_equal, false, 5, 6, "ui");
 838     test_both<P, double>("ec1",
 839             5, 1,   5, 6,   5, 8, // p
 840             5, 1,   5, 6,   5, 8, // q
 841             method_equal, false, 5, 6, "cc");
 842     test_both<P, double>("ec2",
 843             5, 1,   5, 6,   5, 8, // p
 844             5, 1,   5, 6,   5, 7, // q
 845             method_equal, false, 5, 6, "cc");
 846
 847     test_both<P, double>("snl-1",
 848             0, 3,   2, 3,   4, 3, // p
 849             4, 3,   2, 3,   0, 3, // q
 850             method_touch, false, 2, 3, "xx");
 851
 852     // BSG 2012-05-26 to be decided what's the problem here and what it tests...
 853     // Anyway, test results are not filled out.
 854     //test_both<P, double>("issue_buffer_mill",
 855     //        5.1983614873206241 , 6.7259025813913107 , 5.0499999999999998 , 6.4291796067500622 , 5.1983614873206241 , 6.7259025813913107, // p
 856     //        5.0499999999999998 , 6.4291796067500622 , 5.0499999999999998 , 6.4291796067500622 , 5.1983614873206241 , 6.7259025813913107, // q
 857     //        method_collinear, false, 2, 0, "tt");
 858
 859 }
 860
 861
 862 /***
 863 #include <boost/geometry/geometries/adapted/c_array.hpp>
 864 BOOST_GEOMETRY_REGISTER_C_ARRAY_CS(cs::cartesian)
 865
 866 template <typename G>
 867 void test2(G const& geometry)
 868 {
 869     typedef typename bg::point_type<G>::type P;
 870     typedef typename bg::tag<G>::type T;
 871     typedef typename bg::tag<P>::type PT;
 872     std::cout << typeid(G).name() << std::endl;
 873     std::cout << typeid(T).name() << std::endl;
 874     std::cout << typeid(P).name() << std::endl;
 875     std::cout << typeid(PT).name() << std::endl;
 876
 877
 878     std::cout << bg::length(geometry) << std::endl;
 879
 880     typedef bg::model::point<float, 3, bg::cs::cartesian> P2;
 881     bg::model::linestring<P2> out;
 882     bg::strategy::transform::scale_transformer<float[3], P2> scaler(5);
 883     bg::transform(geometry, out, scaler);
 884     std::cout << bg::dsv(out) << std::endl;
 885 }
 886
 887 void test_f3()
 888 {
 889     float vertices[][3] = {
 890         {-1, -1,  1}, {1, -1,  1}, {1, 1,  1}, {-1, 1,  1},
 891         {-1, -1, -1}, {1, -1, -1}, {1, 1, -1}, {-1, 1, -1}
 892         };
 893     test2(vertices);
 894 }
 895 ***/
 896
 897 int test_main(int, char* [])
 898 {
 899     test_all<bg::model::d2::point_xy<double> >();
 900     return 0;
 901 }