boost/geometry/algorithms/detail/buffer/turn_in_piece_visitor.hpp

   1 // Boost.Geometry (aka GGL, Generic Geometry Library)
   2
   3 // Copyright (c) 2012-2014 Barend Gehrels, Amsterdam, the Netherlands.
   4 // Copyright (c) 2017 Adam Wulkiewicz, Lodz, Poland.
   5
   6 // This file was modified by Oracle on 2016, 2018.
   7 // Modifications copyright (c) 2016-2018 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 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_TURN_IN_PIECE_VISITOR
  15 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_TURN_IN_PIECE_VISITOR
  16
  17
  18 #include <boost/core/ignore_unused.hpp>
  19
  20 #include <boost/range.hpp>
  21
  22 #include <boost/geometry/core/assert.hpp>
  23 #include <boost/geometry/core/config.hpp>
  24
  25 #include <boost/geometry/arithmetic/dot_product.hpp>
  26 #include <boost/geometry/algorithms/assign.hpp>
  27 #include <boost/geometry/algorithms/comparable_distance.hpp>
  28 #include <boost/geometry/algorithms/equals.hpp>
  29 #include <boost/geometry/algorithms/expand.hpp>
  30 #include <boost/geometry/algorithms/detail/disjoint/point_box.hpp>
  31 #include <boost/geometry/algorithms/detail/disjoint/box_box.hpp>
  32 #include <boost/geometry/algorithms/detail/overlay/segment_identifier.hpp>
  33 #include <boost/geometry/algorithms/detail/overlay/get_turn_info.hpp>
  34 #include <boost/geometry/policies/compare.hpp>
  35 #include <boost/geometry/strategies/buffer.hpp>
  36 #include <boost/geometry/algorithms/detail/buffer/buffer_policies.hpp>
  37
  38 #include <boost/geometry/strategies/cartesian/side_of_intersection.hpp>
  39
  40
  41 namespace boost { namespace geometry
  42 {
  43
  44
  45 #ifndef DOXYGEN_NO_DETAIL
  46 namespace detail { namespace buffer
  47 {
  48
  49 struct piece_get_box
  50 {
  51     template <typename Box, typename Piece>
  52     static inline void apply(Box& total, Piece const& piece)
  53     {
  54         geometry::expand(total, piece.robust_envelope);
  55     }
  56 };
  57
  58 template <typename DisjointBoxBoxStrategy>
  59 struct piece_ovelaps_box
  60 {
  61     template <typename Box, typename Piece>
  62     static inline bool apply(Box const& box, Piece const& piece)
  63     {
  64         if (piece.type == strategy::buffer::buffered_flat_end
  65             || piece.type == strategy::buffer::buffered_concave)
  66         {
  67             // Turns cannot be inside a flat end (though they can be on border)
  68             // Neither we need to check if they are inside concave helper pieces
  69
  70             // Skip all pieces not used as soon as possible
  71             return false;
  72         }
  73
  74         return ! geometry::detail::disjoint::disjoint_box_box(box, piece.robust_envelope,
  75                                                               DisjointBoxBoxStrategy());
  76     }
  77 };
  78
  79 struct turn_get_box
  80 {
  81     template <typename Box, typename Turn>
  82     static inline void apply(Box& total, Turn const& turn)
  83     {
  84         geometry::expand(total, turn.robust_point);
  85     }
  86 };
  87
  88 template <typename DisjointPointBoxStrategy>
  89 struct turn_ovelaps_box
  90 {
  91     template <typename Box, typename Turn>
  92     static inline bool apply(Box const& box, Turn const& turn)
  93     {
  94         return ! geometry::detail::disjoint::disjoint_point_box(turn.robust_point, box,
  95                                                                 DisjointPointBoxStrategy());
  96     }
  97 };
  98
  99
 100 enum analyse_result
 101 {
 102     analyse_unknown,
 103     analyse_continue,
 104     analyse_disjoint,
 105     analyse_within,
 106     analyse_on_original_boundary,
 107     analyse_on_offsetted,
 108     analyse_near_offsetted
 109 };
 110
 111 template <typename Point>
 112 inline bool in_box(Point const& previous,
 113         Point const& current, Point const& point)
 114 {
 115     // Get its box (TODO: this can be prepared-on-demand later)
 116     typedef geometry::model::box<Point> box_type;
 117     box_type box;
 118     geometry::assign_inverse(box);
 119     geometry::expand(box, previous);
 120     geometry::expand(box, current);
 121
 122     return geometry::covered_by(point, box);
 123 }
 124
 125 template <typename NumericType>
 126 inline bool is_one_sided(NumericType const& left, NumericType const& right)
 127 {
 128     static NumericType const zero = 0;
 129     return geometry::math::equals(left, zero)
 130         || geometry::math::equals(right, zero);
 131 }
 132
 133 template <typename Point, typename DistanceStrategy>
 134 inline bool has_zero_distance_at(Point const& point,
 135                                  DistanceStrategy const& distance_strategy)
 136 {
 137     return is_one_sided(distance_strategy.apply(point, point,
 138             strategy::buffer::buffer_side_left),
 139         distance_strategy.apply(point, point,
 140             strategy::buffer::buffer_side_right));
 141 }
 142
 143 // meta-programming-structure defining if to use side-of-intersection
 144 // (only for cartesian / only necessary with rescaling)
 145 template <typename Tag>
 146 struct use_side_of_intersection {};
 147
 148 #if defined(BOOST_GEOMETRY_USE_RESCALING)
 149 // With rescaling, let Cartesian use side-of-intersection
 150 template <>
 151 struct use_side_of_intersection<cartesian_tag> { static bool const value = true; };
 152 #else
 153 template <>
 154 struct use_side_of_intersection<cartesian_tag> { static bool const value = false; };
 155 #endif
 156
 157 template <>
 158 struct use_side_of_intersection<spherical_tag> { static bool const value = false; };
 159
 160 template <>
 161 struct use_side_of_intersection<geographic_tag> { static bool const value = false; };
 162
 163
 164 template <bool UseSideOfIntersection>
 165 struct check_segment {};
 166
 167 // Implementation using side-of-intersection
 168 template <>
 169 struct check_segment<true>
 170 {
 171     template <typename Point, typename Turn, typename SideStrategy>
 172     static inline analyse_result apply(Point const& previous,
 173             Point const& current, Turn const& turn,
 174             bool from_monotonic,
 175             SideStrategy const& )
 176     {
 177         typedef geometry::model::referring_segment<Point const> segment_type;
 178         segment_type const p(turn.rob_pi, turn.rob_pj);
 179         segment_type const q(turn.rob_qi, turn.rob_qj);
 180         segment_type const r(previous, current);
 181         int const side = strategy::side::side_of_intersection::apply(p, q, r,
 182                     turn.robust_point);
 183
 184         if (side == 0)
 185         {
 186             return analyse_on_offsetted;
 187         }
 188         if (side == -1 && from_monotonic)
 189         {
 190             return analyse_within;
 191         }
 192         if (side == 1 && from_monotonic)
 193         {
 194             return analyse_disjoint;
 195         }
 196         return analyse_continue;
 197     }
 198 };
 199
 200 template <>
 201 struct check_segment<false>
 202 {
 203     template <typename Point, typename Turn, typename SideStrategy>
 204     static inline analyse_result apply(Point const& previous,
 205             Point const& current, Turn const& turn,
 206             bool from_monotonic,
 207             SideStrategy const& side_strategy)
 208     {
 209         int const side = side_strategy.apply(previous, current, turn.robust_point);
 210
 211         if (side == 0)
 212         {
 213             // Collinear, only on segment if it is covered by its bbox
 214             if (in_box(previous, current, turn.robust_point))
 215             {
 216                 return analyse_on_offsetted;
 217             }
 218         }
 219         else if (side == -1)
 220         {
 221             // It is in the triangle right-of the segment where the
 222             // segment is the hypothenusa. Check if it is close
 223             // (within rounding-area)
 224             if (in_box(previous, current, turn.robust_point))
 225             {
 226                 return analyse_near_offsetted;
 227             }
 228             else if (from_monotonic)
 229             {
 230                 return analyse_within;
 231             }
 232         }
 233         else if (from_monotonic)
 234         {
 235             // Left of segment
 236             return analyse_disjoint;
 237         }
 238
 239         // Not monotonic, on left or right side: continue analysing
 240         return analyse_continue;
 241     }
 242 };
 243
 244 template <bool UseSideOfIntersection>
 245 class analyse_turn_wrt_point_piece {};
 246
 247 template <>
 248 class analyse_turn_wrt_point_piece<true>
 249 {
 250 public :
 251     template <typename Turn, typename Piece, typename PointInGeometryStrategy, typename SideStrategy>
 252     static inline analyse_result apply(Turn const& turn, Piece const& piece,
 253                                        PointInGeometryStrategy const& ,
 254                                        SideStrategy const& )
 255     {
 256         typedef typename Piece::section_type section_type;
 257         typedef typename Turn::robust_point_type point_type;
 258         typedef typename geometry::coordinate_type<point_type>::type coordinate_type;
 259
 260         typedef geometry::model::referring_segment<point_type const> segment_type;
 261         segment_type const p(turn.rob_pi, turn.rob_pj);
 262         segment_type const q(turn.rob_qi, turn.rob_qj);
 263
 264         BOOST_GEOMETRY_ASSERT(! piece.sections.empty());
 265
 266         coordinate_type const point_x = geometry::get<0>(turn.robust_point);
 267
 268         for (std::size_t s = 0; s < piece.sections.size(); s++)
 269         {
 270             section_type const& section = piece.sections[s];
 271             // If point within horizontal range of monotonic section:
 272             if (! section.duplicate
 273                 && section.begin_index < section.end_index
 274                 && point_x >= geometry::get<min_corner, 0>(section.bounding_box) - 1
 275                 && point_x <= geometry::get<max_corner, 0>(section.bounding_box) + 1)
 276             {
 277                 for (signed_size_type i = section.begin_index + 1; i <= section.end_index; i++)
 278                 {
 279                     point_type const& previous = piece.robust_ring[i - 1];
 280                     point_type const& current = piece.robust_ring[i];
 281
 282
 283                     // First check if it is in range - if it is not, the
 284                     // expensive side_of_intersection does not need to be
 285                     // applied
 286                     coordinate_type x1 = geometry::get<0>(previous);
 287                     coordinate_type x2 = geometry::get<0>(current);
 288
 289                     if (x1 > x2)
 290                     {
 291                         std::swap(x1, x2);
 292                     }
 293
 294                     if (point_x >= x1 - 1 && point_x <= x2 + 1)
 295                     {
 296                         segment_type const r(previous, current);
 297                         int const side = strategy::side::side_of_intersection::apply(p, q, r,
 298                                     turn.robust_point);
 299
 300                         // Sections are monotonic in x-dimension
 301                         if (side == 1)
 302                         {
 303                             // Left on segment
 304                             return analyse_disjoint;
 305                         }
 306                         else if (side == 0)
 307                         {
 308                             // Collinear - TODO: check if really on segment
 309                             return analyse_on_offsetted;
 310                         }
 311                     }
 312                 }
 313             }
 314         }
 315
 316         // It is nowhere outside, and not on segment, so it is within
 317         return analyse_within;
 318     }
 319
 320 };
 321
 322 template <>
 323 class analyse_turn_wrt_point_piece<false>
 324 {
 325 public :
 326     template <typename Turn, typename Piece, typename PointInGeometryStrategy, typename SideStrategy>
 327     static inline analyse_result apply(Turn const& turn, Piece const& piece,
 328                                        PointInGeometryStrategy const& point_in_geometry_strategy,
 329                                        SideStrategy const& side_strategy)
 330     {
 331         typedef typename Piece::section_type section_type;
 332         typedef typename Turn::robust_point_type point_type;
 333         typedef typename geometry::coordinate_type<point_type>::type coordinate_type;
 334
 335         typename PointInGeometryStrategy::state_type state;
 336
 337         BOOST_GEOMETRY_ASSERT(! piece.sections.empty());
 338
 339         coordinate_type const point_x = geometry::get<0>(turn.robust_point);
 340
 341         for (std::size_t s = 0; s < piece.sections.size(); s++)
 342         {
 343             section_type const& section = piece.sections[s];
 344             // If point within horizontal range of monotonic section:
 345             if (! section.duplicate
 346                 && section.begin_index < section.end_index
 347                 && point_x >= geometry::get<min_corner, 0>(section.bounding_box) - 1
 348                 && point_x <= geometry::get<max_corner, 0>(section.bounding_box) + 1)
 349             {
 350                 for (signed_size_type i = section.begin_index + 1; i <= section.end_index; i++)
 351                 {
 352                     point_type const& previous = piece.robust_ring[i - 1];
 353                     point_type const& current = piece.robust_ring[i];
 354
 355                     analyse_result code = check_segment<false>::apply(previous, current, turn, false, side_strategy);
 356                     if (code != analyse_continue)
 357                     {
 358                         return code;
 359                     }
 360
 361                     // Get the state (to determine it is within), we don't have
 362                     // to cover the on-segment case (covered above)
 363                     point_in_geometry_strategy.apply(turn.robust_point, previous, current, state);
 364                 }
 365             }
 366         }
 367
 368         int const code = point_in_geometry_strategy.result(state);
 369         if (code == 1)
 370         {
 371             return analyse_within;
 372         }
 373         else if (code == -1)
 374         {
 375             return analyse_disjoint;
 376         }
 377
 378         // Should normally not occur - on-segment is covered
 379         return analyse_unknown;
 380     }
 381
 382 };
 383
 384 template <bool UseSideOfIntersection>
 385 struct check_helper_segment {};
 386
 387 template <>
 388 struct check_helper_segment<true>
 389 {
 390     template <typename Point, typename Turn,  typename SideStrategy>
 391     static inline analyse_result apply(Point const& s1,
 392                 Point const& s2, Turn const& turn,
 393                 bool is_original,
 394                 analyse_result result_for_original,
 395                 Point const& offsetted,
 396                 SideStrategy const& )
 397     {
 398         boost::ignore_unused(offsetted, is_original);
 399
 400         typedef geometry::model::referring_segment<Point const> segment_type;
 401         segment_type const p(turn.rob_pi, turn.rob_pj);
 402         segment_type const q(turn.rob_qi, turn.rob_qj);
 403         segment_type const r(s1, s2);
 404         int const side = strategy::side::side_of_intersection::apply(p, q, r,
 405                     turn.robust_point);
 406
 407         if (side == 1)
 408         {
 409             // left of segment
 410             return analyse_disjoint;
 411         }
 412         else if (side == 0)
 413         {
 414             // If is collinear, either on segment or before/after
 415             typedef geometry::model::box<Point> box_type;
 416
 417             box_type box;
 418             geometry::assign_inverse(box);
 419             geometry::expand(box, s1);
 420             geometry::expand(box, s2);
 421
 422             if (geometry::covered_by(turn.robust_point, box))
 423             {
 424                 return result_for_original;
 425             }
 426
 427             // It is collinear but not on the segment. Because these
 428             // segments are convex, it is outside
 429             // Unless the offsetted ring is collinear or concave w.r.t.
 430             // helper-segment but that scenario is not yet supported
 431             return analyse_disjoint;
 432         }
 433
 434         // right of segment
 435         return analyse_continue;
 436     }
 437
 438 };
 439
 440 template <>
 441 struct check_helper_segment<false>
 442 {
 443     template <typename Point, typename Turn, typename SideStrategy>
 444     static inline analyse_result apply(Point const& s1,
 445                 Point const& s2, Turn const& turn,
 446                 bool is_original,
 447                 analyse_result result_for_original,
 448                 Point const& offsetted,
 449                 SideStrategy const& side_strategy)
 450     {
 451         switch(side_strategy.apply(s1, s2, turn.robust_point))
 452         {
 453             case 1 :
 454                 return analyse_disjoint; // left of segment
 455             case 0 :
 456                 {
 457                     // If is collinear, either on segment or before/after
 458                     typedef geometry::model::box<Point> box_type;
 459
 460                     box_type box;
 461                     geometry::assign_inverse(box);
 462                     geometry::expand(box, s1);
 463                     geometry::expand(box, s2);
 464
 465                     if (geometry::covered_by(turn.robust_point, box))
 466                     {
 467                         // It is on the segment
 468                         if (! is_original
 469                             && geometry::comparable_distance(turn.robust_point, offsetted) <= 1)
 470                         {
 471                             // It is within, and close to the offsetted-boundary,
 472                             // take any rounding-issues into account
 473                             return analyse_near_offsetted;
 474                         }
 475
 476                         // Points on helper-segments are considered as within
 477                         // Points on original boundary are processed differently
 478                         return result_for_original;
 479                     }
 480
 481                     // It is collinear but not on the segment. Because these
 482                     // segments are convex, it is outside
 483                     // Unless the offsetted ring is collinear or concave w.r.t.
 484                     // helper-segment but that scenario is not yet supported
 485                     return analyse_disjoint;
 486                 }
 487                 break;
 488         }
 489
 490         // right of segment
 491         return analyse_continue;
 492     }
 493 };
 494
 495 template <bool UseSideOfIntersection>
 496 class analyse_turn_wrt_piece
 497 {
 498     template
 499     <
 500         typename Turn,
 501         typename Piece,
 502         typename DistanceStrategy,
 503         typename SideStrategy
 504     >
 505     static inline analyse_result
 506     check_helper_segments(Turn const& turn, Piece const& piece,
 507                           DistanceStrategy const& distance_strategy,
 508                           SideStrategy const& side_strategy)
 509     {
 510         typedef typename Turn::robust_point_type point_type;
 511         geometry::equal_to<point_type> comparator;
 512
 513         point_type points[4];
 514
 515         signed_size_type helper_count = static_cast<signed_size_type>(piece.robust_ring.size())
 516                                             - piece.offsetted_count;
 517         if (helper_count == 4)
 518         {
 519             for (int i = 0; i < 4; i++)
 520             {
 521                 points[i] = piece.robust_ring[piece.offsetted_count + i];
 522             }
 523
 524             //      3--offsetted outline--0
 525             //      |                     |
 526             // left |                     | right
 527             //      |                     |
 528             //      2===>==original===>===1
 529
 530         }
 531         else if (helper_count == 3)
 532         {
 533             // Triangular piece, assign points but assign second twice
 534             for (int i = 0; i < 4; i++)
 535             {
 536                 int index = i < 2 ? i : i - 1;
 537                 points[i] = piece.robust_ring[piece.offsetted_count + index];
 538             }
 539         }
 540         else
 541         {
 542             // Some pieces (e.g. around points) do not have helper segments.
 543             // Others should have 3 (join) or 4 (side)
 544             return analyse_continue;
 545         }
 546
 547         // If a turn is located on the original, it is considered as within,
 548         // unless it is at a flat start or end, or the buffer (at that point)
 549         // is one-sided (zero-distance)
 550         bool const one_sided = has_zero_distance_at(turn.point, distance_strategy);
 551
 552         analyse_result const result_for_original
 553                 = one_sided || piece.is_flat_end || piece.is_flat_start
 554                 ? analyse_on_original_boundary
 555                 : analyse_within;
 556
 557         // First check point-equality
 558         point_type const& point = turn.robust_point;
 559         if (comparator(point, points[0]) || comparator(point, points[3]))
 560         {
 561             return analyse_on_offsetted;
 562         }
 563         if (comparator(point, points[1]))
 564         {
 565             // On original, with right corner of piece
 566             return result_for_original;
 567         }
 568         if (comparator(point, points[2]))
 569         {
 570             // On original, with left corner of piece
 571             return result_for_original;
 572         }
 573
 574         // Right side of the piece (never an original)
 575         analyse_result result
 576             = check_helper_segment<UseSideOfIntersection>::apply(points[0], points[1], turn,
 577                     false, analyse_within, points[0], side_strategy);
 578         if (result != analyse_continue)
 579         {
 580             return result;
 581         }
 582
 583         // Left side of the piece (never an original)
 584         result = check_helper_segment<UseSideOfIntersection>::apply(points[2], points[3], turn,
 585                     false, analyse_within, points[3], side_strategy);
 586         if (result != analyse_continue)
 587         {
 588             return result;
 589         }
 590
 591         // Side of the piece at side of original geometry
 592         // (here flat start/end will result in within)
 593         if (! comparator(points[1], points[2]))
 594         {
 595             result = check_helper_segment<UseSideOfIntersection>::apply(points[1],
 596                     points[2], turn, true,
 597                     one_sided ? analyse_on_original_boundary : analyse_within,
 598                     point, side_strategy);
 599             if (result != analyse_continue)
 600             {
 601                 return result;
 602             }
 603         }
 604
 605         // We are within the \/ or |_| shaped piece, where the top is the
 606         // offsetted ring.
 607         if (! geometry::covered_by(point, piece.robust_offsetted_envelope))
 608         {
 609             // Not in offsetted-area. This makes a cheap check possible
 610             switch(side_strategy.apply(points[3], points[0], point))
 611             {
 612                 case 1 : return analyse_disjoint;
 613                 case -1 : return analyse_within;
 614                 case 0 : return analyse_disjoint;
 615             }
 616         }
 617
 618         return analyse_continue;
 619     }
 620
 621     template <typename Turn, typename Piece, typename Compare,  typename SideStrategy>
 622     static inline analyse_result check_monotonic(Turn const& turn, Piece const& piece, Compare const& compare, SideStrategy const& side_strategy)
 623     {
 624         typedef typename Piece::piece_robust_ring_type ring_type;
 625         typedef typename ring_type::const_iterator it_type;
 626         it_type end = piece.robust_ring.begin() + piece.offsetted_count;
 627         it_type it = std::lower_bound(piece.robust_ring.begin(),
 628                     end,
 629                     turn.robust_point,
 630                     compare);
 631
 632         if (it != end
 633             && it != piece.robust_ring.begin())
 634         {
 635             // iterator points to point larger than point
 636             // w.r.t. specified direction, and prev points to a point smaller
 637             // We now know if it is inside/outside
 638             it_type prev = it - 1;
 639             return check_segment<UseSideOfIntersection>::apply(*prev, *it, turn, true, side_strategy);
 640         }
 641         return analyse_continue;
 642     }
 643
 644 public :
 645     template
 646     <
 647         typename Turn,
 648         typename Piece,
 649         typename DistanceStrategy,
 650         typename SideStrategy
 651     >
 652     static inline analyse_result apply(Turn const& turn, Piece const& piece,
 653                                        DistanceStrategy const& distance_strategy,
 654                                        SideStrategy const& side_strategy)
 655     {
 656         typedef typename Turn::robust_point_type point_type;
 657         analyse_result code = check_helper_segments(turn, piece, distance_strategy, side_strategy);
 658         if (code != analyse_continue)
 659         {
 660             return code;
 661         }
 662
 663         geometry::equal_to<point_type> comparator;
 664
 665         if (piece.offsetted_count > 8)
 666         {
 667             // If the offset contains some points and is monotonic, we try
 668             // to avoid walking all points linearly.
 669             // We try it only once.
 670             if (piece.is_monotonic_increasing[0])
 671             {
 672                 code = check_monotonic(turn, piece, geometry::less<point_type, 0>(), side_strategy);
 673                 if (code != analyse_continue) return code;
 674             }
 675             else if (piece.is_monotonic_increasing[1])
 676             {
 677                 code = check_monotonic(turn, piece, geometry::less<point_type, 1>(), side_strategy);
 678                 if (code != analyse_continue) return code;
 679             }
 680             else if (piece.is_monotonic_decreasing[0])
 681             {
 682                 code = check_monotonic(turn, piece, geometry::greater<point_type, 0>(), side_strategy);
 683                 if (code != analyse_continue) return code;
 684             }
 685             else if (piece.is_monotonic_decreasing[1])
 686             {
 687                 code = check_monotonic(turn, piece, geometry::greater<point_type, 1>(), side_strategy);
 688                 if (code != analyse_continue) return code;
 689             }
 690         }
 691
 692         // It is small or not monotonic, walk linearly through offset
 693         // TODO: this will be combined with winding strategy
 694
 695         for (signed_size_type i = 1; i < piece.offsetted_count; i++)
 696         {
 697             point_type const& previous = piece.robust_ring[i - 1];
 698             point_type const& current = piece.robust_ring[i];
 699
 700             // The robust ring can contain duplicates
 701             // (on which any side or side-value would return 0)
 702             if (! comparator(previous, current))
 703             {
 704                 code = check_segment<UseSideOfIntersection>::apply(previous, current, turn, false, side_strategy);
 705                 if (code != analyse_continue)
 706                 {
 707                     return code;
 708                 }
 709             }
 710         }
 711
 712         return analyse_unknown;
 713     }
 714
 715 };
 716
 717 // Helper Structure, of which the apply method returns a side value in {-1, 0, 1}
 718 template <bool UseSideOfIntersection>
 719 struct turn_in_piece {};
 720
 721 template <>
 722 struct turn_in_piece<true>
 723 {
 724
 725 private :
 726     template <typename Turn, typename Piece>
 727     static inline int in_convex_piece(Turn const& turn, Piece const& piece)
 728     {
 729         typedef typename Turn::robust_point_type point_type;
 730         typedef typename Piece::piece_robust_ring_type ring_type;
 731         typedef geometry::model::referring_segment<point_type const> segment;
 732
 733         segment const p(turn.rob_pi, turn.rob_pj);
 734         segment const q(turn.rob_qi, turn.rob_qj);
 735
 736         typedef typename boost::range_iterator<ring_type const>::type iterator_type;
 737         iterator_type it = boost::begin(piece.robust_ring);
 738         iterator_type end = boost::end(piece.robust_ring);
 739
 740         // A robust ring is always closed, and always clockwise
 741         for (iterator_type previous = it++; it != end; ++previous, ++it)
 742         {
 743             geometry::equal_to<point_type> comparator;
 744             if (comparator(*previous, *it))
 745             {
 746                 // Points are the same
 747                 continue;
 748             }
 749
 750             segment r(*previous, *it);
 751
 752             int const side = strategy::side::side_of_intersection::apply(p, q, r,
 753                         turn.robust_point);
 754
 755             if (side == 1)
 756             {
 757                 // IP is left of segment, so it is outside
 758                 return -1; // outside
 759             }
 760             else if (side == 0)
 761             {
 762                 // IP is collinear with segment. TODO: we should analyze this further
 763                 // For now we use the fallback point
 764                 if (in_box(*previous, *it, turn.robust_point))
 765                 {
 766                     return 0;
 767                 }
 768                 else
 769                 {
 770                     return -1; // outside
 771                 }
 772             }
 773         }
 774         return 1; // inside
 775     }
 776
 777 public :
 778
 779     template <typename Turn, typename Piece, typename Strategy>
 780     static inline int apply(Turn const& turn, Piece const& piece,
 781             Strategy const& strategy)
 782     {
 783         if (piece.is_convex)
 784         {
 785             return in_convex_piece(turn, piece);
 786         }
 787         else
 788         {
 789             // side-of-intersection only supported for convex pieces
 790             // Call point_in_geometry, a performance-bottleneck
 791             // TODO: might be replaced by extending analysing piece
 792             return detail::within::point_in_geometry(turn.robust_point,
 793                 piece.robust_ring, strategy);
 794         }
 795     }
 796 };
 797
 798 template <>
 799 struct turn_in_piece<false>
 800 {
 801 public :
 802
 803     template <typename Turn, typename Piece, typename Strategy>
 804     static inline int apply(Turn const& turn, Piece const& piece,
 805             Strategy const& strategy)
 806     {
 807         return detail::within::point_in_geometry(turn.robust_point,
 808             piece.robust_ring, strategy);
 809     }
 810 };
 811
 812 template
 813 <
 814     typename CsTag,
 815     typename Turns,
 816     typename Pieces,
 817     typename DistanceStrategy,
 818     typename PointInGeometryStrategy,
 819     typename SideStrategy
 820
 821 >
 822 class turn_in_piece_visitor
 823 {
 824     Turns& m_turns; // because partition is currently operating on const input only
 825     Pieces const& m_pieces; // to check for piece-type
 826     DistanceStrategy const& m_distance_strategy; // to check if point is on original
 827     PointInGeometryStrategy const& m_point_in_geometry_strategy;
 828     SideStrategy const& m_side_strategy;
 829
 830     template <typename Operation, typename Piece>
 831     inline bool skip(Operation const& op, Piece const& piece) const
 832     {
 833         if (op.piece_index == piece.index)
 834         {
 835             return true;
 836         }
 837         Piece const& pc = m_pieces[op.piece_index];
 838         if (pc.left_index == piece.index || pc.right_index == piece.index)
 839         {
 840             if (pc.type == strategy::buffer::buffered_flat_end)
 841             {
 842                 // If it is a flat end, don't compare against its neighbor:
 843                 // it will always be located on one of the helper segments
 844                 return true;
 845             }
 846             if (pc.type == strategy::buffer::buffered_concave)
 847             {
 848                 // If it is concave, the same applies: the IP will be
 849                 // located on one of the helper segments
 850                 return true;
 851             }
 852         }
 853
 854         return false;
 855     }
 856
 857
 858 public:
 859
 860     inline turn_in_piece_visitor(Turns& turns, Pieces const& pieces,
 861                                  DistanceStrategy const& distance_strategy,
 862                                  PointInGeometryStrategy const& strategy,
 863                                  SideStrategy const& side_strategy)
 864         : m_turns(turns)
 865         , m_pieces(pieces)
 866         , m_distance_strategy(distance_strategy)
 867         , m_point_in_geometry_strategy(strategy)
 868         , m_side_strategy(side_strategy)
 869     {}
 870
 871     template <typename Turn, typename Piece>
 872     inline bool apply(Turn const& turn, Piece const& piece, bool first = true)
 873     {
 874         boost::ignore_unused(first);
 875
 876         if (turn.count_within > 0)
 877         {
 878             // Already inside - no need to check again
 879             return true;
 880         }
 881
 882         if (piece.type == strategy::buffer::buffered_flat_end
 883             || piece.type == strategy::buffer::buffered_concave)
 884         {
 885             // Turns cannot be located within flat-end or concave pieces
 886             return true;
 887         }
 888
 889         if (! geometry::covered_by(turn.robust_point, piece.robust_envelope))
 890         {
 891             // Easy check: if the turn is not in the envelope, we can safely return
 892             return true;
 893         }
 894
 895         if (skip(turn.operations[0], piece) || skip(turn.operations[1], piece))
 896         {
 897             return true;
 898         }
 899
 900         // TODO: mutable_piece to make some on-demand preparations in analyse
 901         Turn& mutable_turn = m_turns[turn.turn_index];
 902
 903         if (piece.type == geometry::strategy::buffer::buffered_point)
 904         {
 905             // Optimization for buffer around points: if distance from center
 906             // is not between min/max radius, the result is clear
 907             typedef typename default_comparable_distance_result
 908                 <
 909                     typename Turn::robust_point_type
 910                 >::type distance_type;
 911
 912             distance_type const cd
 913                 = geometry::comparable_distance(piece.robust_center,
 914                         turn.robust_point);
 915
 916             if (cd < piece.robust_min_comparable_radius)
 917             {
 918                 mutable_turn.count_within++;
 919                 return true;
 920             }
 921             if (cd > piece.robust_max_comparable_radius)
 922             {
 923                 return true;
 924             }
 925         }
 926
 927         static const bool use_soi = use_side_of_intersection<CsTag>::value;
 928         boost::ignore_unused(use_soi);
 929
 930         analyse_result const analyse_code =
 931             piece.type == geometry::strategy::buffer::buffered_point
 932                 ? analyse_turn_wrt_point_piece<use_soi>::apply(turn, piece, m_point_in_geometry_strategy, m_side_strategy)
 933                 : analyse_turn_wrt_piece<use_soi>::apply(turn, piece, m_distance_strategy, m_side_strategy);
 934
 935         switch(analyse_code)
 936         {
 937             case analyse_disjoint :
 938                 return true;
 939             case analyse_on_offsetted :
 940                 mutable_turn.count_on_offsetted++; // value is not used anymore
 941                 return true;
 942             case analyse_on_original_boundary :
 943                 mutable_turn.count_on_original_boundary++;
 944                 return true;
 945             case analyse_within :
 946                 mutable_turn.count_within++;
 947                 return true;
 948             case analyse_near_offsetted :
 949                 mutable_turn.count_within_near_offsetted++;
 950                 return true;
 951             default :
 952                 break;
 953         }
 954
 955         int const geometry_code = turn_in_piece<use_soi>::apply(turn, piece,
 956                 m_point_in_geometry_strategy);
 957
 958         if (geometry_code == 1)
 959         {
 960             mutable_turn.count_within++;
 961         }
 962
 963         return true;
 964     }
 965 };
 966
 967
 968 }} // namespace detail::buffer
 969 #endif // DOXYGEN_NO_DETAIL
 970
 971
 972 }} // namespace boost::geometry
 973
 974 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_TURN_IN_PIECE_VISITOR