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