ceph/src/boost/libs/geometry/include/boost/geometry/algorithms/detail/overlay/get_turn_info_la.hpp

   1 // Boost.Geometry (aka GGL, Generic Geometry Library)
   2
   3 // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
   4
   5 // This file was modified by Oracle on 2013, 2014, 2015.
   6 // Modifications copyright (c) 2013-2015 Oracle and/or its affiliates.
   7
   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 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_GET_TURN_INFO_LA_HPP
  15 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_GET_TURN_INFO_LA_HPP
  16
  17 #include <boost/geometry/core/assert.hpp>
  18
  19 #include <boost/geometry/util/condition.hpp>
  20
  21 #include <boost/geometry/algorithms/detail/overlay/get_turn_info.hpp>
  22 #include <boost/geometry/algorithms/detail/overlay/get_turn_info_for_endpoint.hpp>
  23
  24 // TEMP, for spikes detector
  25 //#include <boost/geometry/algorithms/detail/overlay/get_turn_info_ll.hpp>
  26
  27 namespace boost { namespace geometry {
  28
  29 #ifndef DOXYGEN_NO_DETAIL
  30 namespace detail { namespace overlay {
  31
  32 template<typename AssignPolicy>
  33 struct get_turn_info_linear_areal
  34 {
  35     // Currently only Linear spikes are handled
  36     // Areal spikes are ignored
  37     static const bool handle_spikes = true;
  38
  39     template
  40     <
  41         typename Point1,
  42         typename Point2,
  43         typename TurnInfo,
  44         typename RobustPolicy,
  45         typename OutputIterator
  46     >
  47     static inline OutputIterator apply(
  48                 Point1 const& pi, Point1 const& pj, Point1 const& pk,
  49                 Point2 const& qi, Point2 const& qj, Point2 const& qk,
  50                 bool is_p_first, bool is_p_last,
  51                 bool is_q_first, bool is_q_last,
  52                 TurnInfo const& tp_model,
  53                 RobustPolicy const& robust_policy,
  54                 OutputIterator out)
  55     {
  56         typedef intersection_info<Point1, Point2, typename TurnInfo::point_type, RobustPolicy>
  57             inters_info;
  58
  59         inters_info inters(pi, pj, pk, qi, qj, qk, robust_policy);
  60
  61         char const method = inters.d_info().how;
  62
  63         // Copy, to copy possibly extended fields
  64         TurnInfo tp = tp_model;
  65
  66         // Select method and apply
  67         switch(method)
  68         {
  69             case 'a' : // collinear, "at"
  70             case 'f' : // collinear, "from"
  71             case 's' : // starts from the middle
  72                 get_turn_info_for_endpoint<true, true>(
  73                     pi, pj, pk, qi, qj, qk,
  74                     is_p_first, is_p_last, is_q_first, is_q_last,
  75                     tp_model, inters, method_none, out);
  76                 break;
  77
  78             case 'd' : // disjoint: never do anything
  79                 break;
  80
  81             case 'm' :
  82             {
  83                 if ( get_turn_info_for_endpoint<false, true>(
  84                         pi, pj, pk, qi, qj, qk,
  85                         is_p_first, is_p_last, is_q_first, is_q_last,
  86                         tp_model, inters, method_touch_interior, out) )
  87                 {
  88                     // do nothing
  89                 }
  90                 else
  91                 {
  92                     typedef touch_interior
  93                         <
  94                             TurnInfo
  95                         > policy;
  96
  97                     // If Q (1) arrives (1)
  98                     if ( inters.d_info().arrival[1] == 1 )
  99                     {
 100                         policy::template apply<0>(pi, pj, pk, qi, qj, qk,
 101                                     tp, inters.i_info(), inters.d_info(),
 102                                     inters.sides());
 103                     }
 104                     else
 105                     {
 106                         // Swap p/q
 107                         side_calculator
 108                             <
 109                                 typename inters_info::cs_tag,
 110                                 typename inters_info::robust_point2_type,
 111                                 typename inters_info::robust_point1_type
 112                             > swapped_side_calc(inters.rqi(), inters.rqj(), inters.rqk(),
 113                                                 inters.rpi(), inters.rpj(), inters.rpk());
 114                         policy::template apply<1>(qi, qj, qk, pi, pj, pk,
 115                                     tp, inters.i_info(), inters.d_info(),
 116                                     swapped_side_calc);
 117                     }
 118
 119                     if ( tp.operations[1].operation == operation_blocked )
 120                     {
 121                         tp.operations[0].is_collinear = true;
 122                     }
 123
 124                     replace_method_and_operations_tm(tp.method,
 125                                                      tp.operations[0].operation,
 126                                                      tp.operations[1].operation);
 127
 128                     // this function assumes that 'u' must be set for a spike
 129                     calculate_spike_operation(tp.operations[0].operation,
 130                                               inters, is_p_last);
 131
 132                     AssignPolicy::apply(tp, pi, qi, inters);
 133
 134                     *out++ = tp;
 135                 }
 136             }
 137             break;
 138             case 'i' :
 139             {
 140                 crosses<TurnInfo>::apply(pi, pj, pk, qi, qj, qk,
 141                                          tp, inters.i_info(), inters.d_info());
 142
 143                 replace_operations_i(tp.operations[0].operation, tp.operations[1].operation);
 144
 145                 AssignPolicy::apply(tp, pi, qi, inters);
 146                 *out++ = tp;
 147             }
 148             break;
 149             case 't' :
 150             {
 151                 // Both touch (both arrive there)
 152                 if ( get_turn_info_for_endpoint<false, true>(
 153                         pi, pj, pk, qi, qj, qk,
 154                         is_p_first, is_p_last, is_q_first, is_q_last,
 155                         tp_model, inters, method_touch, out) )
 156                 {
 157                     // do nothing
 158                 }
 159                 else
 160                 {
 161                     touch<TurnInfo>::apply(pi, pj, pk, qi, qj, qk,
 162                             tp, inters.i_info(), inters.d_info(), inters.sides());
 163
 164                     if ( tp.operations[1].operation == operation_blocked )
 165                     {
 166                         tp.operations[0].is_collinear = true;
 167                     }
 168
 169                     // workarounds for touch<> not taking spikes into account starts here
 170                     // those was discovered empirically
 171                     // touch<> is not symmetrical!
 172                     // P spikes and Q spikes may produce various operations!
 173                     // Only P spikes are valid for L/A
 174                     // TODO: this is not optimal solution - think about rewriting touch<>
 175
 176                     if ( tp.operations[0].operation == operation_blocked )
 177                     {
 178                         // a spike on P on the same line with Q1
 179                         if ( inters.is_spike_p() )
 180                         {
 181                             if ( inters.sides().qk_wrt_p1() == 0 )
 182                             {
 183                                 tp.operations[0].is_collinear = true;
 184                             }
 185                             else
 186                             {
 187                                 tp.operations[0].operation = operation_union;
 188                             }
 189                         }
 190                     }
 191                     else if ( tp.operations[0].operation == operation_continue
 192                            && tp.operations[1].operation == operation_continue )
 193                     {
 194                         // P spike on the same line with Q2 (opposite)
 195                         if ( inters.sides().pk_wrt_q1() == -inters.sides().qk_wrt_q1()
 196                           && inters.is_spike_p() )
 197                         {
 198                             tp.operations[0].operation = operation_union;
 199                             tp.operations[1].operation = operation_union;
 200                         }
 201                     }
 202                     else if ( tp.operations[0].operation == operation_none
 203                            && tp.operations[1].operation == operation_none )
 204                     {
 205                         // spike not handled by touch<>
 206                         if ( inters.is_spike_p() )
 207                         {
 208                             tp.operations[0].operation = operation_intersection;
 209                             tp.operations[1].operation = operation_union;
 210
 211                             if ( inters.sides().pk_wrt_q2() == 0 )
 212                             {
 213                                 tp.operations[0].operation = operation_continue; // will be converted to i
 214                                 tp.operations[0].is_collinear = true;
 215                             }
 216                         }
 217                     }
 218
 219                     // workarounds for touch<> not taking spikes into account ends here
 220
 221                     replace_method_and_operations_tm(tp.method,
 222                                                      tp.operations[0].operation,
 223                                                      tp.operations[1].operation);
 224
 225                     bool ignore_spike
 226                         = calculate_spike_operation(tp.operations[0].operation,
 227                                                     inters, is_p_last);
 228
 229 // TODO: move this into the append_xxx and call for each turn?
 230                     AssignPolicy::apply(tp, pi, qi, inters);
 231
 232                     if ( ! BOOST_GEOMETRY_CONDITION(handle_spikes)
 233                       || ignore_spike
 234                       || ! append_opposite_spikes<append_touches>( // for 'i' or 'c' i???
 235                                 tp, inters, is_p_last, is_q_last, out) )
 236                     {
 237                         *out++ = tp;
 238                     }
 239                 }
 240             }
 241             break;
 242             case 'e':
 243             {
 244                 if ( get_turn_info_for_endpoint<true, true>(
 245                         pi, pj, pk, qi, qj, qk,
 246                         is_p_first, is_p_last, is_q_first, is_q_last,
 247                         tp_model, inters, method_equal, out) )
 248                 {
 249                     // do nothing
 250                 }
 251                 else
 252                 {
 253                     tp.operations[0].is_collinear = true;
 254
 255                     if ( ! inters.d_info().opposite )
 256                     {
 257                         // Both equal
 258                         // or collinear-and-ending at intersection point
 259                         equal<TurnInfo>::apply(pi, pj, pk, qi, qj, qk,
 260                             tp, inters.i_info(), inters.d_info(), inters.sides());
 261
 262                         turn_transformer_ec<false> transformer(method_touch);
 263                         transformer(tp);
 264
 265 // TODO: move this into the append_xxx and call for each turn?
 266                         AssignPolicy::apply(tp, pi, qi, inters);
 267
 268                         // conditionally handle spikes
 269                         if ( ! BOOST_GEOMETRY_CONDITION(handle_spikes)
 270                           || ! append_collinear_spikes(tp, inters, is_p_last, is_q_last,
 271                                                        method_touch, append_equal, out) )
 272                         {
 273                             *out++ = tp; // no spikes
 274                         }
 275                     }
 276                     else
 277                     {
 278                         equal_opposite
 279                             <
 280                                 TurnInfo,
 281                                 AssignPolicy
 282                             >::apply(pi, qi,
 283                                      tp, out, inters);
 284                     }
 285                 }
 286             }
 287             break;
 288             case 'c' :
 289             {
 290                 // Collinear
 291                 if ( get_turn_info_for_endpoint<true, true>(
 292                         pi, pj, pk, qi, qj, qk,
 293                         is_p_first, is_p_last, is_q_first, is_q_last,
 294                         tp_model, inters, method_collinear, out) )
 295                 {
 296                     // do nothing
 297                 }
 298                 else
 299                 {
 300                     tp.operations[0].is_collinear = true;
 301
 302                     if ( ! inters.d_info().opposite )
 303                     {
 304                         method_type method_replace = method_touch_interior;
 305                         append_version_c version = append_collinear;
 306
 307                         if ( inters.d_info().arrival[0] == 0 )
 308                         {
 309                             // Collinear, but similar thus handled as equal
 310                             equal<TurnInfo>::apply(pi, pj, pk, qi, qj, qk,
 311                                     tp, inters.i_info(), inters.d_info(), inters.sides());
 312
 313                             method_replace = method_touch;
 314                             version = append_equal;
 315                         }
 316                         else
 317                         {
 318                             collinear<TurnInfo>::apply(pi, pj, pk, qi, qj, qk,
 319                                     tp, inters.i_info(), inters.d_info(), inters.sides());
 320
 321                             //method_replace = method_touch_interior;
 322                             //version = append_collinear;
 323                         }
 324
 325                         turn_transformer_ec<false> transformer(method_replace);
 326                         transformer(tp);
 327
 328 // TODO: move this into the append_xxx and call for each turn?
 329                         AssignPolicy::apply(tp, pi, qi, inters);
 330
 331                         // conditionally handle spikes
 332                         if ( ! BOOST_GEOMETRY_CONDITION(handle_spikes)
 333                           || ! append_collinear_spikes(tp, inters, is_p_last, is_q_last,
 334                                                        method_replace, version, out) )
 335                         {
 336                             // no spikes
 337                             *out++ = tp;
 338                         }
 339                     }
 340                     else
 341                     {
 342                         // Is this always 'm' ?
 343                         turn_transformer_ec<false> transformer(method_touch_interior);
 344
 345                         // conditionally handle spikes
 346                         if ( BOOST_GEOMETRY_CONDITION(handle_spikes) )
 347                         {
 348                             append_opposite_spikes<append_collinear_opposite>(
 349                                     tp, inters, is_p_last, is_q_last, out);
 350                         }
 351
 352                         // TODO: ignore for spikes?
 353                         //       E.g. pass is_p_valid = !is_p_last && !is_pj_spike,
 354                         //       the same with is_q_valid
 355
 356                         collinear_opposite
 357                             <
 358                                 TurnInfo,
 359                                 AssignPolicy
 360                             >::apply(pi, pj, pk, qi, qj, qk,
 361                                 tp, out, inters,
 362                                 inters.sides(), transformer,
 363                                 !is_p_last, true); // qk is always valid
 364                     }
 365                 }
 366             }
 367             break;
 368             case '0' :
 369             {
 370                 // degenerate points
 371                 if ( BOOST_GEOMETRY_CONDITION(AssignPolicy::include_degenerate) )
 372                 {
 373                     only_convert::apply(tp, inters.i_info());
 374
 375                     if ( is_p_first
 376                       && equals::equals_point_point(pi, tp.point) )
 377                     {
 378                         tp.operations[0].position = position_front;
 379                     }
 380                     else if ( is_p_last
 381                            && equals::equals_point_point(pj, tp.point) )
 382                     {
 383                         tp.operations[0].position = position_back;
 384                     }
 385                     // tp.operations[1].position = position_middle;
 386
 387                     AssignPolicy::apply(tp, pi, qi, inters);
 388                     *out++ = tp;
 389                 }
 390             }
 391             break;
 392             default :
 393             {
 394 #if defined(BOOST_GEOMETRY_DEBUG_ROBUSTNESS)
 395                 std::cout << "TURN: Unknown method: " << method << std::endl;
 396 #endif
 397 #if ! defined(BOOST_GEOMETRY_OVERLAY_NO_THROW)
 398                 throw turn_info_exception(method);
 399 #endif
 400             }
 401             break;
 402         }
 403
 404         return out;
 405     }
 406
 407     template <typename Operation,
 408               typename IntersectionInfo>
 409     static inline bool calculate_spike_operation(Operation & op,
 410                                                  IntersectionInfo const& inters,
 411                                                  bool is_p_last)
 412     {
 413         bool is_p_spike = ( op == operation_union || op == operation_intersection )
 414                        && ! is_p_last
 415                        && inters.is_spike_p();
 416
 417         if ( is_p_spike )
 418         {
 419             int const pk_q1 = inters.sides().pk_wrt_q1();
 420
 421             bool going_in = pk_q1 < 0; // Pk on the right
 422             bool going_out = pk_q1 > 0; // Pk on the left
 423
 424             int const qk_q1 = inters.sides().qk_wrt_q1();
 425
 426             // special cases
 427             if ( qk_q1 < 0 ) // Q turning R
 428             {
 429                 // spike on the edge point
 430                 // if it's already known that the spike is going out this musn't be checked
 431                 if ( ! going_out
 432                   && equals::equals_point_point(inters.rpj(), inters.rqj()) )
 433                 {
 434                     int const pk_q2 = inters.sides().pk_wrt_q2();
 435                     going_in = pk_q1 < 0 && pk_q2 < 0; // Pk on the right of both
 436                     going_out = pk_q1 > 0 || pk_q2 > 0; // Pk on the left of one of them
 437                 }
 438             }
 439             else if ( qk_q1 > 0 ) // Q turning L
 440             {
 441                 // spike on the edge point
 442                 // if it's already known that the spike is going in this musn't be checked
 443                 if ( ! going_in
 444                   && equals::equals_point_point(inters.rpj(), inters.rqj()) )
 445                 {
 446                     int const pk_q2 = inters.sides().pk_wrt_q2();
 447                     going_in = pk_q1 < 0 || pk_q2 < 0; // Pk on the right of one of them
 448                     going_out = pk_q1 > 0 && pk_q2 > 0; // Pk on the left of both
 449                 }
 450             }
 451
 452             if ( going_in )
 453             {
 454                 op = operation_intersection;
 455                 return true;
 456             }
 457             else if ( going_out )
 458             {
 459                 op = operation_union;
 460                 return true;
 461             }
 462         }
 463
 464         return false;
 465     }
 466
 467     enum append_version_c { append_equal, append_collinear };
 468
 469     template <typename TurnInfo,
 470               typename IntersectionInfo,
 471               typename OutIt>
 472     static inline bool append_collinear_spikes(TurnInfo & tp,
 473                                                IntersectionInfo const& inters,
 474                                                bool is_p_last, bool /*is_q_last*/,
 475                                                method_type method, append_version_c version,
 476                                                OutIt out)
 477     {
 478         // method == touch || touch_interior
 479         // both position == middle
 480
 481         bool is_p_spike = ( version == append_equal ?
 482                             ( tp.operations[0].operation == operation_union
 483                            || tp.operations[0].operation == operation_intersection ) :
 484                             tp.operations[0].operation == operation_continue )
 485                        && ! is_p_last
 486                        && inters.is_spike_p();
 487
 488         // TODO: throw an exception for spike in Areal?
 489         /*bool is_q_spike = tp.operations[1].operation == operation_continue
 490                        && inters.is_spike_q();
 491
 492         // both are collinear spikes on the same IP, we can just follow both
 493         if ( is_p_spike && is_q_spike )
 494         {
 495             return false;
 496         }
 497         // spike on Linear - it's turning back on the boundary of Areal
 498         else*/
 499         if ( is_p_spike )
 500         {
 501             tp.method = method;
 502             tp.operations[0].operation = operation_blocked;
 503             tp.operations[1].operation = operation_union;
 504             *out++ = tp;
 505             tp.operations[0].operation = operation_continue; // boundary
 506             //tp.operations[1].operation = operation_union;
 507             *out++ = tp;
 508
 509             return true;
 510         }
 511         // spike on Areal - Linear is going outside
 512         /*else if ( is_q_spike )
 513         {
 514             tp.method = method;
 515             tp.operations[0].operation = operation_union;
 516             tp.operations[1].operation = operation_continue;
 517             *out++ = tp;
 518             *out++ = tp;
 519
 520             return true;
 521         }*/
 522
 523         return false;
 524     }
 525
 526     enum append_version_o { append_touches, append_collinear_opposite };
 527
 528     template <append_version_o Version,
 529               typename TurnInfo,
 530               typename IntersectionInfo,
 531               typename OutIt>
 532     static inline bool append_opposite_spikes(TurnInfo & tp,
 533                                               IntersectionInfo const& inters,
 534                                               bool is_p_last, bool /*is_q_last*/,
 535                                               OutIt out)
 536     {
 537         static const bool is_version_touches = (Version == append_touches);
 538
 539         bool is_p_spike = ( is_version_touches ?
 540                             ( tp.operations[0].operation == operation_continue
 541                            || tp.operations[0].operation == operation_intersection ) : // i ???
 542                             true )
 543                        && ! is_p_last
 544                        && inters.is_spike_p();
 545
 546         // TODO: throw an exception for spike in Areal?
 547         /*bool is_q_spike = ( ( Version == append_touches
 548                            && tp.operations[1].operation == operation_continue )
 549                          || ( Version == append_collinear_opposite
 550                            && tp.operations[1].operation == operation_none ) )
 551                        && inters.is_spike_q();
 552
 553         if ( is_p_spike && is_q_spike )
 554         {
 555             // u/u or nothing?
 556             return false;
 557         }
 558         else*/
 559         if ( is_p_spike )
 560         {
 561             if ( BOOST_GEOMETRY_CONDITION(is_version_touches)
 562               || inters.d_info().arrival[0] == 1 )
 563             {
 564                 if ( BOOST_GEOMETRY_CONDITION(is_version_touches) )
 565                 {
 566                     tp.operations[0].is_collinear = true;
 567                     //tp.operations[1].is_collinear = false;
 568                     tp.method = method_touch;
 569                 }
 570                 else
 571                 {
 572                     tp.operations[0].is_collinear = true;
 573                     //tp.operations[1].is_collinear = false;
 574
 575                     BOOST_GEOMETRY_ASSERT(inters.i_info().count > 1);
 576                     base_turn_handler::assign_point(tp, method_touch_interior, inters.i_info(), 1);
 577
 578                     AssignPolicy::apply(tp, inters.pi(), inters.qi(), inters);
 579                 }
 580
 581                 tp.operations[0].operation = operation_blocked;
 582                 tp.operations[1].operation = operation_continue; // boundary
 583                 *out++ = tp;
 584                 tp.operations[0].operation = operation_continue; // boundary
 585                 //tp.operations[1].operation = operation_continue; // boundary
 586                 *out++ = tp;
 587
 588                 return true;
 589             }
 590         }
 591         /*else if ( is_q_spike )
 592         {
 593             tp.operations[0].is_collinear = true;
 594             tp.method = is_version_touches ? method_touch : method_touch_interior;
 595             tp.operations[0].operation = operation_continue;
 596             tp.operations[1].operation = operation_continue; // boundary
 597             *out++ = tp;
 598             *out++ = tp;
 599
 600             return true;
 601         }*/
 602
 603         return false;
 604     }
 605
 606     static inline void replace_method_and_operations_tm(method_type & method,
 607                                                         operation_type & op0,
 608                                                         operation_type & op1)
 609     {
 610         if ( op0 == operation_blocked && op1 == operation_blocked )
 611         {
 612             // NOTE: probably only if methods are WRT IPs, not segments!
 613             method = (method == method_touch ? method_equal : method_collinear);
 614         }
 615
 616         // Assuming G1 is always Linear
 617         if ( op0 == operation_blocked )
 618         {
 619             op0 = operation_continue;
 620         }
 621
 622         if ( op1 == operation_blocked )
 623         {
 624             op1 = operation_continue;
 625         }
 626         else if ( op1 == operation_intersection )
 627         {
 628             op1 = operation_union;
 629         }
 630
 631         // spikes in 'm'
 632         if ( method == method_error )
 633         {
 634             method = method_touch_interior;
 635             op0 = operation_union;
 636             op1 = operation_union;
 637         }
 638     }
 639
 640     template <bool IsFront>
 641     class turn_transformer_ec
 642     {
 643     public:
 644         explicit turn_transformer_ec(method_type method_t_or_m)
 645             : m_method(method_t_or_m)
 646         {}
 647
 648         template <typename Turn>
 649         void operator()(Turn & turn) const
 650         {
 651             operation_type & op0 = turn.operations[0].operation;
 652             operation_type & op1 = turn.operations[1].operation;
 653
 654             // NOTE: probably only if methods are WRT IPs, not segments!
 655             if ( BOOST_GEOMETRY_CONDITION(IsFront)
 656               || op0 == operation_intersection || op0 == operation_union
 657               || op1 == operation_intersection || op1 == operation_union )
 658             {
 659                 turn.method = m_method;
 660             }
 661
 662             turn.operations[0].is_collinear = op0 != operation_blocked;
 663
 664             // Assuming G1 is always Linear
 665             if ( op0 == operation_blocked )
 666             {
 667                 op0 = operation_continue;
 668             }
 669
 670             if ( op1 == operation_blocked )
 671             {
 672                 op1 = operation_continue;
 673             }
 674             else if ( op1 == operation_intersection )
 675             {
 676                 op1 = operation_union;
 677             }
 678         }
 679
 680     private:
 681         method_type m_method;
 682     };
 683
 684     static inline void replace_operations_i(operation_type & /*op0*/, operation_type & op1)
 685     {
 686         // assuming Linear is always the first one
 687         op1 = operation_union;
 688     }
 689
 690     // NOTE: Spikes may NOT be handled for Linear endpoints because it's not
 691     //       possible to define a spike on an endpoint. Areal geometries must
 692     //       NOT have spikes at all. One thing that could be done is to throw
 693     //       an exception when spike is detected in Areal geometry.
 694
 695     template <bool EnableFirst,
 696               bool EnableLast,
 697               typename Point1,
 698               typename Point2,
 699               typename TurnInfo,
 700               typename IntersectionInfo,
 701               typename OutputIterator>
 702     static inline bool get_turn_info_for_endpoint(
 703                             Point1 const& pi, Point1 const& /*pj*/, Point1 const& /*pk*/,
 704                             Point2 const& qi, Point2 const& /*qj*/, Point2 const& /*qk*/,
 705                             bool is_p_first, bool is_p_last,
 706                             bool /*is_q_first*/, bool is_q_last,
 707                             TurnInfo const& tp_model,
 708                             IntersectionInfo const& inters,
 709                             method_type /*method*/,
 710                             OutputIterator out)
 711     {
 712         namespace ov = overlay;
 713         typedef ov::get_turn_info_for_endpoint<AssignPolicy, EnableFirst, EnableLast> get_info_e;
 714
 715         const std::size_t ip_count = inters.i_info().count;
 716         // no intersection points
 717         if ( ip_count == 0 )
 718             return false;
 719
 720         if ( !is_p_first && !is_p_last )
 721             return false;
 722
 723 // TODO: is_q_last could probably be replaced by false and removed from parameters
 724
 725         linear_intersections intersections(pi, qi, inters.result(), is_p_last, is_q_last);
 726         linear_intersections::ip_info const& ip0 = intersections.template get<0>();
 727         linear_intersections::ip_info const& ip1 = intersections.template get<1>();
 728
 729         const bool opposite = inters.d_info().opposite;
 730
 731         // ANALYSE AND ASSIGN FIRST
 732
 733         // IP on the first point of Linear Geometry
 734         bool was_first_point_handled = false;
 735         if ( BOOST_GEOMETRY_CONDITION(EnableFirst)
 736           && is_p_first && ip0.is_pi && !ip0.is_qi ) // !q0i prevents duplication
 737         {
 738             TurnInfo tp = tp_model;
 739             tp.operations[0].position = position_front;
 740             tp.operations[1].position = position_middle;
 741
 742             if ( opposite ) // opposite -> collinear
 743             {
 744                 tp.operations[0].operation = operation_continue;
 745                 tp.operations[1].operation = operation_union;
 746                 tp.method = ip0.is_qj ? method_touch : method_touch_interior;
 747             }
 748             else
 749             {
 750                 method_type replaced_method = method_touch_interior;
 751
 752                 if ( ip0.is_qj )
 753                 {
 754                     side_calculator
 755                         <
 756                             typename IntersectionInfo::cs_tag,
 757                             typename IntersectionInfo::robust_point1_type,
 758                             typename IntersectionInfo::robust_point2_type,
 759                             typename IntersectionInfo::robust_point2_type
 760                         > side_calc(inters.rqi(), inters.rpi(), inters.rpj(),
 761                                     inters.rqi(), inters.rqj(), inters.rqk());
 762
 763                     std::pair<operation_type, operation_type>
 764                         operations = get_info_e::operations_of_equal(side_calc);
 765
 766                     tp.operations[0].operation = operations.first;
 767                     tp.operations[1].operation = operations.second;
 768
 769                     replaced_method = method_touch;
 770                 }
 771                 else
 772                 {
 773                     side_calculator
 774                         <
 775                             typename IntersectionInfo::cs_tag,
 776                             typename IntersectionInfo::robust_point1_type,
 777                             typename IntersectionInfo::robust_point2_type,
 778                             typename IntersectionInfo::robust_point2_type,
 779                             typename IntersectionInfo::robust_point1_type,
 780                             typename IntersectionInfo::robust_point1_type,
 781                             typename IntersectionInfo::robust_point2_type,
 782                             typename IntersectionInfo::robust_point1_type,
 783                             typename IntersectionInfo::robust_point2_type
 784                         > side_calc(inters.rqi(), inters.rpi(), inters.rpj(),
 785                                     inters.rqi(), inters.rpi(), inters.rqj());
 786
 787                     std::pair<operation_type, operation_type>
 788                         operations = get_info_e::operations_of_equal(side_calc);
 789
 790                     tp.operations[0].operation = operations.first;
 791                     tp.operations[1].operation = operations.second;
 792                 }
 793
 794                 turn_transformer_ec<true> transformer(replaced_method);
 795                 transformer(tp);
 796             }
 797
 798             // equals<> or collinear<> will assign the second point,
 799             // we'd like to assign the first one
 800             base_turn_handler::assign_point(tp, tp.method, inters.i_info(), 0);
 801
 802             // NOTE: is_collinear is not set for the first endpoint of L
 803             // for which there is no preceding segment
 804             // here is_p_first_ip == true
 805             tp.operations[0].is_collinear = false;
 806
 807             AssignPolicy::apply(tp, pi, qi, inters);
 808             *out++ = tp;
 809
 810             was_first_point_handled = true;
 811         }
 812
 813         // ANALYSE AND ASSIGN LAST
 814
 815         // IP on the last point of Linear Geometry
 816         if ( BOOST_GEOMETRY_CONDITION(EnableLast)
 817           && is_p_last
 818           && ( ip_count > 1 ? (ip1.is_pj && !ip1.is_qi) : (ip0.is_pj && !ip0.is_qi) ) ) // prevents duplication
 819         {
 820             TurnInfo tp = tp_model;
 821
 822             if ( inters.i_info().count > 1 )
 823             {
 824                 //BOOST_GEOMETRY_ASSERT( result.template get<1>().dir_a == 0 && result.template get<1>().dir_b == 0 );
 825                 tp.operations[0].is_collinear = true;
 826                 tp.operations[1].operation = opposite ? operation_continue : operation_union;
 827             }
 828             else //if ( result.template get<0>().count == 1 )
 829             {
 830                 side_calculator
 831                     <
 832                         typename IntersectionInfo::cs_tag,
 833                         typename IntersectionInfo::robust_point1_type,
 834                         typename IntersectionInfo::robust_point2_type,
 835                         typename IntersectionInfo::robust_point2_type
 836                     > side_calc(inters.rqi(), inters.rpj(), inters.rpi(),
 837                                 inters.rqi(), inters.rqj(), inters.rqk());
 838
 839                 std::pair<operation_type, operation_type>
 840                     operations = get_info_e::operations_of_equal(side_calc);
 841
 842                 tp.operations[0].operation = operations.first;
 843                 tp.operations[1].operation = operations.second;
 844
 845                 turn_transformer_ec<false> transformer(method_none);
 846                 transformer(tp);
 847
 848                 tp.operations[0].is_collinear = tp.both(operation_continue);
 849             }
 850
 851             tp.method = ( ip_count > 1 ? ip1.is_qj : ip0.is_qj ) ? method_touch : method_touch_interior;
 852             tp.operations[0].operation = operation_blocked;
 853             tp.operations[0].position = position_back;
 854             tp.operations[1].position = position_middle;
 855
 856             // equals<> or collinear<> will assign the second point,
 857             // we'd like to assign the first one
 858             unsigned int ip_index = ip_count > 1 ? 1 : 0;
 859             base_turn_handler::assign_point(tp, tp.method, inters.i_info(), ip_index);
 860
 861             AssignPolicy::apply(tp, pi, qi, inters);
 862             *out++ = tp;
 863
 864             // don't ignore the first IP if the segment is opposite
 865             return !( opposite && ip_count > 1 ) || was_first_point_handled;
 866         }
 867
 868         // don't ignore anything for now
 869         return false;
 870     }
 871 };
 872
 873 }} // namespace detail::overlay
 874 #endif // DOXYGEN_NO_DETAIL
 875
 876 }} // namespace boost::geometry
 877
 878 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_GET_TURN_INFO_LA_HPP