1 // Boost.Geometry (aka GGL, Generic Geometry Library)
3 // Copyright (c) 2012-2014 Barend Gehrels, Amsterdam, the Netherlands.
5 // This file was modified by Oracle on 2016.
6 // Modifications copyright (c) 2016 Oracle and/or its affiliates.
7 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
9 // Use, modification and distribution is subject to the Boost Software License,
10 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
11 // http://www.boost.org/LICENSE_1_0.txt)
13 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_TURN_IN_PIECE_VISITOR
14 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_TURN_IN_PIECE_VISITOR
17 #include <boost/core/ignore_unused.hpp>
19 #include <boost/range.hpp>
21 #include <boost/geometry/core/assert.hpp>
23 #include <boost/geometry/arithmetic/dot_product.hpp>
24 #include <boost/geometry/algorithms/assign.hpp>
25 #include <boost/geometry/algorithms/comparable_distance.hpp>
26 #include <boost/geometry/algorithms/equals.hpp>
27 #include <boost/geometry/algorithms/expand.hpp>
28 #include <boost/geometry/algorithms/detail/disjoint/point_box.hpp>
29 #include <boost/geometry/algorithms/detail/disjoint/box_box.hpp>
30 #include <boost/geometry/algorithms/detail/overlay/segment_identifier.hpp>
31 #include <boost/geometry/algorithms/detail/overlay/get_turn_info.hpp>
32 #include <boost/geometry/policies/compare.hpp>
33 #include <boost/geometry/strategies/buffer.hpp>
34 #include <boost/geometry/algorithms/detail/buffer/buffer_policies.hpp>
36 #if defined(BOOST_GEOMETRY_BUFFER_USE_SIDE_OF_INTERSECTION)
37 #include <boost/geometry/strategies/cartesian/side_of_intersection.hpp>
41 namespace boost { namespace geometry
45 #ifndef DOXYGEN_NO_DETAIL
46 namespace detail { namespace buffer
51 template <typename Box, typename Piece>
52 static inline void apply(Box& total, Piece const& piece)
54 geometry::expand(total, piece.robust_envelope);
58 struct piece_ovelaps_box
60 template <typename Box, typename Piece>
61 static inline bool apply(Box const& box, Piece const& piece)
63 if (piece.type == strategy::buffer::buffered_flat_end
64 || piece.type == strategy::buffer::buffered_concave)
66 // Turns cannot be inside a flat end (though they can be on border)
67 // Neither we need to check if they are inside concave helper pieces
69 // Skip all pieces not used as soon as possible
73 return ! geometry::detail::disjoint::disjoint_box_box(box, piece.robust_envelope);
79 template <typename Box, typename Turn>
80 static inline void apply(Box& total, Turn const& turn)
82 geometry::expand(total, turn.robust_point);
86 struct turn_ovelaps_box
88 template <typename Box, typename Turn>
89 static inline bool apply(Box const& box, Turn const& turn)
91 return ! geometry::detail::disjoint::disjoint_point_box(turn.robust_point, box);
102 analyse_on_original_boundary,
104 #if ! defined(BOOST_GEOMETRY_BUFFER_USE_SIDE_OF_INTERSECTION)
105 , analyse_near_offsetted
109 template <typename Point>
110 inline bool in_box(Point const& previous,
111 Point const& current, Point const& point)
113 // Get its box (TODO: this can be prepared-on-demand later)
114 typedef geometry::model::box<Point> box_type;
116 geometry::assign_inverse(box);
117 geometry::expand(box, previous);
118 geometry::expand(box, current);
120 return geometry::covered_by(point, box);
123 template <typename Point, typename Turn>
124 inline analyse_result check_segment(Point const& previous,
125 Point const& current, Turn const& turn,
129 #if defined(BOOST_GEOMETRY_BUFFER_USE_SIDE_OF_INTERSECTION)
130 typedef geometry::model::referring_segment<Point const> segment_type;
131 segment_type const p(turn.rob_pi, turn.rob_pj);
132 segment_type const q(turn.rob_qi, turn.rob_qj);
133 segment_type const r(previous, current);
134 int const side = strategy::side::side_of_intersection::apply(p, q, r,
139 return analyse_on_offsetted;
141 if (side == -1 && from_monotonic)
143 return analyse_within;
145 if (side == 1 && from_monotonic)
147 return analyse_disjoint;
149 return analyse_continue;
153 typedef typename strategy::side::services::default_strategy
155 typename cs_tag<Point>::type
156 >::type side_strategy;
157 typedef typename geometry::coordinate_type<Point>::type coordinate_type;
159 coordinate_type const twice_area
160 = side_strategy::template side_value
164 >(previous, current, turn.robust_point);
168 // Collinear, only on segment if it is covered by its bbox
169 if (in_box(previous, current, turn.robust_point))
171 return analyse_on_offsetted;
174 else if (twice_area < 0)
176 // It is in the triangle right-of the segment where the
177 // segment is the hypothenusa. Check if it is close
178 // (within rounding-area)
179 if (twice_area * twice_area < geometry::comparable_distance(previous, current)
180 && in_box(previous, current, turn.robust_point))
182 return analyse_near_offsetted;
184 else if (from_monotonic)
186 return analyse_within;
189 else if (twice_area > 0 && from_monotonic)
192 return analyse_disjoint;
195 // Not monotonic, on left or right side: continue analysing
196 return analyse_continue;
201 class analyse_turn_wrt_point_piece
204 template <typename Turn, typename Piece>
205 static inline analyse_result apply(Turn const& turn, Piece const& piece)
207 typedef typename Piece::section_type section_type;
208 typedef typename Turn::robust_point_type point_type;
209 typedef typename geometry::coordinate_type<point_type>::type coordinate_type;
211 #if defined(BOOST_GEOMETRY_BUFFER_USE_SIDE_OF_INTERSECTION)
212 typedef geometry::model::referring_segment<point_type const> segment_type;
213 segment_type const p(turn.rob_pi, turn.rob_pj);
214 segment_type const q(turn.rob_qi, turn.rob_qj);
216 typedef strategy::within::winding<point_type> strategy_type;
218 typename strategy_type::state_type state;
219 strategy_type strategy;
220 boost::ignore_unused(strategy);
223 BOOST_GEOMETRY_ASSERT(! piece.sections.empty());
225 coordinate_type const point_x = geometry::get<0>(turn.robust_point);
227 for (std::size_t s = 0; s < piece.sections.size(); s++)
229 section_type const& section = piece.sections[s];
230 // If point within horizontal range of monotonic section:
231 if (! section.duplicate
232 && section.begin_index < section.end_index
233 && point_x >= geometry::get<min_corner, 0>(section.bounding_box) - 1
234 && point_x <= geometry::get<max_corner, 0>(section.bounding_box) + 1)
236 for (signed_size_type i = section.begin_index + 1; i <= section.end_index; i++)
238 point_type const& previous = piece.robust_ring[i - 1];
239 point_type const& current = piece.robust_ring[i];
241 #if defined(BOOST_GEOMETRY_BUFFER_USE_SIDE_OF_INTERSECTION)
243 // First check if it is in range - if it is not, the
244 // expensive side_of_intersection does not need to be
246 coordinate_type x1 = geometry::get<0>(previous);
247 coordinate_type x2 = geometry::get<0>(current);
254 if (point_x >= x1 - 1 && point_x <= x2 + 1)
256 segment_type const r(previous, current);
257 int const side = strategy::side::side_of_intersection::apply(p, q, r,
260 // Sections are monotonic in x-dimension
264 return analyse_disjoint;
268 // Collinear - TODO: check if really on segment
269 return analyse_on_offsetted;
273 analyse_result code = check_segment(previous, current, turn, false);
274 if (code != analyse_continue)
279 // Get the state (to determine it is within), we don't have
280 // to cover the on-segment case (covered above)
281 strategy.apply(turn.robust_point, previous, current, state);
287 #if defined(BOOST_GEOMETRY_BUFFER_USE_SIDE_OF_INTERSECTION)
288 // It is nowhere outside, and not on segment, so it is within
289 return analyse_within;
291 int const code = strategy.result(state);
294 return analyse_within;
298 return analyse_disjoint;
301 // Should normally not occur - on-segment is covered
302 return analyse_unknown;
308 class analyse_turn_wrt_piece
310 template <typename Point, typename Turn>
311 static inline analyse_result check_helper_segment(Point const& s1,
312 Point const& s2, Turn const& turn,
314 Point const& offsetted)
316 boost::ignore_unused(offsetted);
317 #if defined(BOOST_GEOMETRY_BUFFER_USE_SIDE_OF_INTERSECTION)
318 typedef geometry::model::referring_segment<Point const> segment_type;
319 segment_type const p(turn.rob_pi, turn.rob_pj);
320 segment_type const q(turn.rob_qi, turn.rob_qj);
321 segment_type const r(s1, s2);
322 int const side = strategy::side::side_of_intersection::apply(p, q, r,
328 return analyse_disjoint;
332 // If is collinear, either on segment or before/after
333 typedef geometry::model::box<Point> box_type;
336 geometry::assign_inverse(box);
337 geometry::expand(box, s1);
338 geometry::expand(box, s2);
340 if (geometry::covered_by(turn.robust_point, box))
342 // Points on helper-segments are considered as within
343 // Points on original boundary are processed differently
345 ? analyse_on_original_boundary
349 // It is collinear but not on the segment. Because these
350 // segments are convex, it is outside
351 // Unless the offsetted ring is collinear or concave w.r.t.
352 // helper-segment but that scenario is not yet supported
353 return analyse_disjoint;
357 return analyse_continue;
359 typedef typename strategy::side::services::default_strategy
361 typename cs_tag<Point>::type
362 >::type side_strategy;
364 switch(side_strategy::apply(s1, s2, turn.robust_point))
367 return analyse_disjoint; // left of segment
370 // If is collinear, either on segment or before/after
371 typedef geometry::model::box<Point> box_type;
374 geometry::assign_inverse(box);
375 geometry::expand(box, s1);
376 geometry::expand(box, s2);
378 if (geometry::covered_by(turn.robust_point, box))
380 // It is on the segment
382 && geometry::comparable_distance(turn.robust_point, offsetted) <= 1)
384 // It is close to the offsetted-boundary, take
385 // any rounding-issues into account
386 return analyse_near_offsetted;
389 // Points on helper-segments are considered as within
390 // Points on original boundary are processed differently
392 ? analyse_on_original_boundary
396 // It is collinear but not on the segment. Because these
397 // segments are convex, it is outside
398 // Unless the offsetted ring is collinear or concave w.r.t.
399 // helper-segment but that scenario is not yet supported
400 return analyse_disjoint;
406 return analyse_continue;
410 template <typename Turn, typename Piece>
411 static inline analyse_result check_helper_segments(Turn const& turn, Piece const& piece)
413 typedef typename Turn::robust_point_type point_type;
414 geometry::equal_to<point_type> comparator;
416 point_type points[4];
418 signed_size_type helper_count = static_cast<signed_size_type>(piece.robust_ring.size())
419 - piece.offsetted_count;
420 if (helper_count == 4)
422 for (int i = 0; i < 4; i++)
424 points[i] = piece.robust_ring[piece.offsetted_count + i];
427 else if (helper_count == 3)
429 // Triangular piece, assign points but assign second twice
430 for (int i = 0; i < 4; i++)
432 int index = i < 2 ? i : i - 1;
433 points[i] = piece.robust_ring[piece.offsetted_count + index];
438 // Some pieces (e.g. around points) do not have helper segments.
439 // Others should have 3 (join) or 4 (side)
440 return analyse_continue;
443 // First check point-equality
444 point_type const& point = turn.robust_point;
445 if (comparator(point, points[0]) || comparator(point, points[3]))
447 return analyse_on_offsetted;
449 if (comparator(point, points[1]) || comparator(point, points[2]))
451 return analyse_on_original_boundary;
454 // Right side of the piece
455 analyse_result result
456 = check_helper_segment(points[0], points[1], turn,
458 if (result != analyse_continue)
463 // Left side of the piece
464 result = check_helper_segment(points[2], points[3], turn,
466 if (result != analyse_continue)
471 if (! comparator(points[1], points[2]))
473 // Side of the piece at side of original geometry
474 result = check_helper_segment(points[1], points[2], turn,
476 if (result != analyse_continue)
482 // We are within the \/ or |_| shaped piece, where the top is the
484 if (! geometry::covered_by(point, piece.robust_offsetted_envelope))
486 // Not in offsetted-area. This makes a cheap check possible
487 typedef typename strategy::side::services::default_strategy
489 typename cs_tag<point_type>::type
490 >::type side_strategy;
492 switch(side_strategy::apply(points[3], points[0], point))
494 case 1 : return analyse_disjoint;
495 case -1 : return analyse_within;
496 case 0 : return analyse_disjoint;
500 return analyse_continue;
503 template <typename Turn, typename Piece, typename Compare>
504 static inline analyse_result check_monotonic(Turn const& turn, Piece const& piece, Compare const& compare)
506 typedef typename Piece::piece_robust_ring_type ring_type;
507 typedef typename ring_type::const_iterator it_type;
508 it_type end = piece.robust_ring.begin() + piece.offsetted_count;
509 it_type it = std::lower_bound(piece.robust_ring.begin(),
515 && it != piece.robust_ring.begin())
517 // iterator points to point larger than point
518 // w.r.t. specified direction, and prev points to a point smaller
519 // We now know if it is inside/outside
520 it_type prev = it - 1;
521 return check_segment(*prev, *it, turn, true);
523 return analyse_continue;
527 template <typename Turn, typename Piece>
528 static inline analyse_result apply(Turn const& turn, Piece const& piece)
530 typedef typename Turn::robust_point_type point_type;
531 analyse_result code = check_helper_segments(turn, piece);
532 if (code != analyse_continue)
537 geometry::equal_to<point_type> comparator;
539 if (piece.offsetted_count > 8)
541 // If the offset contains some points and is monotonic, we try
542 // to avoid walking all points linearly.
543 // We try it only once.
544 if (piece.is_monotonic_increasing[0])
546 code = check_monotonic(turn, piece, geometry::less<point_type, 0>());
547 if (code != analyse_continue) return code;
549 else if (piece.is_monotonic_increasing[1])
551 code = check_monotonic(turn, piece, geometry::less<point_type, 1>());
552 if (code != analyse_continue) return code;
554 else if (piece.is_monotonic_decreasing[0])
556 code = check_monotonic(turn, piece, geometry::greater<point_type, 0>());
557 if (code != analyse_continue) return code;
559 else if (piece.is_monotonic_decreasing[1])
561 code = check_monotonic(turn, piece, geometry::greater<point_type, 1>());
562 if (code != analyse_continue) return code;
566 // It is small or not monotonic, walk linearly through offset
567 // TODO: this will be combined with winding strategy
569 for (signed_size_type i = 1; i < piece.offsetted_count; i++)
571 point_type const& previous = piece.robust_ring[i - 1];
572 point_type const& current = piece.robust_ring[i];
574 // The robust ring can contain duplicates
575 // (on which any side or side-value would return 0)
576 if (! comparator(previous, current))
578 code = check_segment(previous, current, turn, false);
579 if (code != analyse_continue)
586 return analyse_unknown;
592 template <typename Turns, typename Pieces>
593 class turn_in_piece_visitor
595 Turns& m_turns; // because partition is currently operating on const input only
596 Pieces const& m_pieces; // to check for piece-type
598 template <typename Operation, typename Piece>
599 inline bool skip(Operation const& op, Piece const& piece) const
601 if (op.piece_index == piece.index)
605 Piece const& pc = m_pieces[op.piece_index];
606 if (pc.left_index == piece.index || pc.right_index == piece.index)
608 if (pc.type == strategy::buffer::buffered_flat_end)
610 // If it is a flat end, don't compare against its neighbor:
611 // it will always be located on one of the helper segments
614 if (pc.type == strategy::buffer::buffered_concave)
616 // If it is concave, the same applies: the IP will be
617 // located on one of the helper segments
625 #if defined(BOOST_GEOMETRY_BUFFER_USE_SIDE_OF_INTERSECTION)
626 // NOTE: this function returns a side value in {-1, 0, 1}
627 template <typename Turn, typename Piece>
628 static inline int turn_in_convex_piece(Turn const& turn,
631 typedef typename Turn::robust_point_type point_type;
632 typedef typename Piece::piece_robust_ring_type ring_type;
633 typedef geometry::model::referring_segment<point_type const> segment;
635 segment const p(turn.rob_pi, turn.rob_pj);
636 segment const q(turn.rob_qi, turn.rob_qj);
638 typedef typename boost::range_iterator<ring_type const>::type iterator_type;
639 iterator_type it = boost::begin(piece.robust_ring);
640 iterator_type end = boost::end(piece.robust_ring);
642 // A robust ring is always closed, and always clockwise
643 for (iterator_type previous = it++; it != end; ++previous, ++it)
645 geometry::equal_to<point_type> comparator;
646 if (comparator(*previous, *it))
648 // Points are the same
652 segment r(*previous, *it);
654 int const side = strategy::side::side_of_intersection::apply(p, q, r,
659 // IP is left of segment, so it is outside
660 return -1; // outside
664 // IP is collinear with segment. TODO: we should analyze this further
665 // For now we use the fallback point
666 if (in_box(*previous, *it, turn.robust_point))
672 return -1; // outside
683 inline turn_in_piece_visitor(Turns& turns, Pieces const& pieces)
688 template <typename Turn, typename Piece>
689 inline void apply(Turn const& turn, Piece const& piece, bool first = true)
691 boost::ignore_unused_variable_warning(first);
693 if (turn.count_within > 0)
695 // Already inside - no need to check again
699 if (piece.type == strategy::buffer::buffered_flat_end
700 || piece.type == strategy::buffer::buffered_concave)
702 // Turns cannot be located within flat-end or concave pieces
706 if (! geometry::covered_by(turn.robust_point, piece.robust_envelope))
708 // Easy check: if the turn is not in the envelope, we can safely return
712 if (skip(turn.operations[0], piece) || skip(turn.operations[1], piece))
717 // TODO: mutable_piece to make some on-demand preparations in analyse
718 Turn& mutable_turn = m_turns[turn.turn_index];
720 if (piece.type == geometry::strategy::buffer::buffered_point)
722 // Optimization for buffer around points: if distance from center
723 // is not between min/max radius, the result is clear
724 typedef typename default_comparable_distance_result
726 typename Turn::robust_point_type
727 >::type distance_type;
729 distance_type const cd
730 = geometry::comparable_distance(piece.robust_center,
733 if (cd < piece.robust_min_comparable_radius)
735 mutable_turn.count_within++;
738 if (cd > piece.robust_max_comparable_radius)
744 analyse_result analyse_code =
745 piece.type == geometry::strategy::buffer::buffered_point
746 ? analyse_turn_wrt_point_piece::apply(turn, piece)
747 : analyse_turn_wrt_piece::apply(turn, piece);
751 case analyse_disjoint :
753 case analyse_on_offsetted :
754 mutable_turn.count_on_offsetted++; // value is not used anymore
756 case analyse_on_original_boundary :
757 mutable_turn.count_on_original_boundary++;
759 case analyse_within :
760 mutable_turn.count_within++;
762 #if ! defined(BOOST_GEOMETRY_BUFFER_USE_SIDE_OF_INTERSECTION)
763 case analyse_near_offsetted :
764 mutable_turn.count_within_near_offsetted++;
771 #if defined(BOOST_GEOMETRY_BUFFER_USE_SIDE_OF_INTERSECTION)
772 // We don't know (yet)
773 int geometry_code = 0;
776 geometry_code = turn_in_convex_piece(turn, piece);
781 // TODO: this point_in_geometry is a performance-bottleneck here and
782 // will be replaced completely by extending analyse_piece functionality
783 geometry_code = detail::within::point_in_geometry(turn.robust_point, piece.robust_ring);
786 int geometry_code = detail::within::point_in_geometry(turn.robust_point, piece.robust_ring);
789 if (geometry_code == 1)
791 mutable_turn.count_within++;
797 }} // namespace detail::buffer
798 #endif // DOXYGEN_NO_DETAIL
801 }} // namespace boost::geometry
803 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_TURN_IN_PIECE_VISITOR