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-2017.
6 // Modifications copyright (c) 2016-2017 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_BUFFERED_PIECE_COLLECTION_HPP
14 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_BUFFERED_PIECE_COLLECTION_HPP
20 #include <boost/core/ignore_unused.hpp>
21 #include <boost/range.hpp>
23 #include <boost/geometry/core/assert.hpp>
24 #include <boost/geometry/core/coordinate_type.hpp>
25 #include <boost/geometry/core/point_type.hpp>
27 #include <boost/geometry/algorithms/comparable_distance.hpp>
28 #include <boost/geometry/algorithms/covered_by.hpp>
29 #include <boost/geometry/algorithms/envelope.hpp>
30 #include <boost/geometry/algorithms/is_convex.hpp>
32 #include <boost/geometry/strategies/buffer.hpp>
34 #include <boost/geometry/geometries/ring.hpp>
36 #include <boost/geometry/algorithms/detail/buffer/buffered_ring.hpp>
37 #include <boost/geometry/algorithms/detail/buffer/buffer_policies.hpp>
38 #include <boost/geometry/algorithms/detail/overlay/cluster_info.hpp>
39 #include <boost/geometry/algorithms/detail/buffer/get_piece_turns.hpp>
40 #include <boost/geometry/algorithms/detail/buffer/turn_in_piece_visitor.hpp>
41 #include <boost/geometry/algorithms/detail/buffer/turn_in_original_visitor.hpp>
43 #include <boost/geometry/algorithms/detail/disjoint/point_box.hpp>
44 #include <boost/geometry/algorithms/detail/overlay/add_rings.hpp>
45 #include <boost/geometry/algorithms/detail/overlay/assign_parents.hpp>
46 #include <boost/geometry/algorithms/detail/overlay/enrichment_info.hpp>
47 #include <boost/geometry/algorithms/detail/overlay/enrich_intersection_points.hpp>
48 #include <boost/geometry/algorithms/detail/overlay/ring_properties.hpp>
49 #include <boost/geometry/algorithms/detail/overlay/select_rings.hpp>
50 #include <boost/geometry/algorithms/detail/overlay/traversal_info.hpp>
51 #include <boost/geometry/algorithms/detail/overlay/traverse.hpp>
52 #include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
53 #include <boost/geometry/algorithms/detail/occupation_info.hpp>
54 #include <boost/geometry/algorithms/detail/partition.hpp>
55 #include <boost/geometry/algorithms/detail/sections/sectionalize.hpp>
56 #include <boost/geometry/algorithms/detail/sections/section_box_policies.hpp>
58 #include <boost/geometry/util/range.hpp>
61 namespace boost { namespace geometry
65 #ifndef DOXYGEN_NO_DETAIL
66 namespace detail { namespace buffer
69 enum segment_relation_code
71 segment_relation_on_left,
72 segment_relation_on_right,
73 segment_relation_within,
74 segment_relation_disjoint
80 * Suppose we make a buffer (using blocked corners) of this rectangle:
88 * For the sides we get these four buffered side-pieces (marked with s)
89 * and four buffered corner pieces (marked with c)
92 * | | piece | | <- see below for details of the middle top-side-piece
95 * s | rect | s <- two side pieces left/right of rect
98 * | | piece | | <- one side-piece below, and two corner pieces
101 * The outer part of the picture above, using all pieces,
102 * form together the offsetted ring (marked with o below)
103 * The 8 pieces are part of the piece collection and use for inside-checks
104 * The inner parts form (using 1 or 2 points per piece, often co-located)
105 * form together the robust_polygons (marked with r below)
106 * The remaining piece-segments are helper-segments (marked with h)
121 template <typename Ring, typename IntersectionStrategy, typename RobustPolicy>
122 struct buffered_piece_collection
124 typedef buffered_piece_collection
126 Ring, IntersectionStrategy, RobustPolicy
129 typedef typename geometry::point_type<Ring>::type point_type;
130 typedef typename geometry::coordinate_type<Ring>::type coordinate_type;
131 typedef typename geometry::robust_point_type
135 >::type robust_point_type;
137 // Robust ring/polygon type, always clockwise
138 typedef geometry::model::ring<robust_point_type> robust_ring_type;
139 typedef geometry::model::box<robust_point_type> robust_box_type;
141 typedef typename default_comparable_distance_result
144 >::type robust_comparable_radius_type;
146 typedef typename IntersectionStrategy::side_strategy_type side_strategy_type;
148 typedef typename IntersectionStrategy::template area_strategy
151 >::type area_strategy_type;
153 typedef typename IntersectionStrategy::template area_strategy
156 >::type robust_area_strategy_type;
158 typedef typename area_strategy_type::return_type area_result_type;
159 typedef typename robust_area_strategy_type::return_type robust_area_result_type;
161 typedef typename geometry::rescale_policy_type
163 typename geometry::point_type<Ring>::type
164 >::type rescale_policy_type;
166 typedef typename geometry::segment_ratio_type
170 >::type segment_ratio_type;
172 typedef buffer_turn_info
177 > buffer_turn_info_type;
179 typedef buffer_turn_operation
183 > buffer_turn_operation_type;
185 typedef std::vector<buffer_turn_info_type> turn_vector_type;
189 std::size_t turn_index;
191 robust_point_type point;
192 segment_identifier seg_id;
193 segment_ratio_type fraction;
198 typedef robust_ring_type piece_robust_ring_type;
199 typedef geometry::section<robust_box_type, 1> section_type;
201 strategy::buffer::piece_type type;
202 signed_size_type index;
204 signed_size_type left_index; // points to previous piece of same ring
205 signed_size_type right_index; // points to next piece of same ring
207 // The next two members (1, 2) form together a complete clockwise ring
208 // for each piece (with one dupped point)
209 // The complete clockwise ring is also included as a robust ring (3)
211 // 1: half, part of offsetted_rings
212 segment_identifier first_seg_id;
213 signed_size_type last_segment_index; // no segment-identifier - it is the same as first_seg_id
214 signed_size_type offsetted_count; // part in robust_ring which is part of offsetted ring
216 #if defined(BOOST_GEOMETRY_BUFFER_USE_HELPER_POINTS)
217 // 2: half, not part of offsetted rings - part of robust ring
218 std::vector<point_type> helper_points; // 4 points for side, 3 points for join - 0 points for flat-end
225 bool is_monotonic_increasing[2]; // 0=x, 1=y
226 bool is_monotonic_decreasing[2]; // 0=x, 1=y
228 // Monotonic sections of pieces around points
229 std::vector<section_type> sections;
231 // Robust representations
233 robust_ring_type robust_ring;
235 robust_box_type robust_envelope;
236 robust_box_type robust_offsetted_envelope;
238 std::vector<robust_turn> robust_turns; // Used only in insert_rescaled_piece_turns - we might use a map instead
240 robust_point_type robust_center;
241 robust_comparable_radius_type robust_min_comparable_radius;
242 robust_comparable_radius_type robust_max_comparable_radius;
245 : type(strategy::buffer::piece_type_unknown)
249 , last_segment_index(-1)
250 , offsetted_count(-1)
251 , is_flat_start(false)
255 , robust_min_comparable_radius(0)
256 , robust_max_comparable_radius(0)
258 is_monotonic_increasing[0] = false;
259 is_monotonic_increasing[1] = false;
260 is_monotonic_decreasing[0] = false;
261 is_monotonic_decreasing[1] = false;
265 struct robust_original
267 typedef robust_ring_type original_robust_ring_type;
268 typedef geometry::sections<robust_box_type, 1> sections_type;
270 inline robust_original()
271 : m_is_interior(false)
272 , m_has_interiors(true)
275 inline robust_original(robust_ring_type const& ring,
276 bool is_interior, bool has_interiors)
278 , m_is_interior(is_interior)
279 , m_has_interiors(has_interiors)
281 geometry::envelope(m_ring, m_box);
283 // create monotonic sections in x-dimension
284 // The dimension is critical because the direction is later used
285 // in the optimization for within checks using winding strategy
286 // and this strategy is scanning in x direction.
287 typedef boost::mpl::vector_c<std::size_t, 0> dimensions;
288 geometry::sectionalize<false, dimensions>(m_ring,
289 detail::no_rescale_policy(), m_sections);
292 robust_ring_type m_ring;
293 robust_box_type m_box;
294 sections_type m_sections;
297 bool m_has_interiors;
300 typedef std::vector<piece> piece_vector_type;
302 piece_vector_type m_pieces;
303 turn_vector_type m_turns;
304 signed_size_type m_first_piece_index;
308 buffered_ring_collection<buffered_ring<Ring> > offsetted_rings; // indexed by multi_index
309 std::vector<robust_original> robust_originals; // robust representation of the original(s)
310 robust_ring_type current_robust_ring;
311 buffered_ring_collection<Ring> traversed_rings;
312 segment_identifier current_segment_id;
314 // Specificly for offsetted rings around points
315 // but also for large joins with many points
316 typedef geometry::sections<robust_box_type, 2> sections_type;
317 sections_type monotonic_sections;
319 // Define the clusters, mapping cluster_id -> turns
323 detail::overlay::cluster_info
326 cluster_type m_clusters;
328 IntersectionStrategy m_intersection_strategy;
329 side_strategy_type m_side_strategy;
330 area_strategy_type m_area_strategy;
331 robust_area_strategy_type m_robust_area_strategy;
332 RobustPolicy const& m_robust_policy;
334 struct redundant_turn
336 inline bool operator()(buffer_turn_info_type const& turn) const
338 return turn.remove_on_multi;
342 buffered_piece_collection(IntersectionStrategy const& intersection_strategy,
343 RobustPolicy const& robust_policy)
344 : m_first_piece_index(-1)
346 , m_has_deflated(false)
347 , m_intersection_strategy(intersection_strategy)
348 , m_side_strategy(intersection_strategy.get_side_strategy())
349 , m_area_strategy(intersection_strategy.template get_area_strategy<point_type>())
350 , m_robust_area_strategy(intersection_strategy.template get_area_strategy<robust_point_type>())
351 , m_robust_policy(robust_policy)
355 #if defined(BOOST_GEOMETRY_BUFFER_ENLARGED_CLUSTERS)
356 // Will (most probably) be removed later
357 template <typename OccupationMap>
358 inline void adapt_mapped_robust_point(OccupationMap const& map,
359 buffer_turn_info_type& turn, int distance) const
361 for (int x = -distance; x <= distance; x++)
363 for (int y = -distance; y <= distance; y++)
365 robust_point_type rp = turn.robust_point;
366 geometry::set<0>(rp, geometry::get<0>(rp) + x);
367 geometry::set<1>(rp, geometry::get<1>(rp) + y);
368 if (map.find(rp) != map.end())
370 turn.mapped_robust_point = rp;
378 inline void get_occupation(
379 #if defined(BOOST_GEOMETRY_BUFFER_ENLARGED_CLUSTERS)
384 typedef occupation_info<angle_info<robust_point_type, coordinate_type> >
385 buffer_occupation_info;
390 buffer_occupation_info,
391 geometry::less<robust_point_type>
392 > occupation_map_type;
394 occupation_map_type occupation_map;
396 // 1: Add all intersection points to occupation map
397 typedef typename boost::range_iterator<turn_vector_type>::type
400 for (iterator_type it = boost::begin(m_turns);
401 it != boost::end(m_turns);
404 if (it->location == location_ok)
406 #if defined(BOOST_GEOMETRY_BUFFER_ENLARGED_CLUSTERS)
407 if (distance > 0 && ! occupation_map.empty())
409 adapt_mapped_robust_point(occupation_map, *it, distance);
412 occupation_map[it->get_robust_point()].count++;
416 // Remove all points with one or more u/u points from the map
417 // (Alternatively, we could NOT do this here and change all u/u
418 // behaviour in overlay. Currently nothing is done: each polygon is
419 // just followed there. We could also always switch polygons there. For
420 // buffer behaviour, where 3 pieces might meet of which 2 (or more) form
421 // a u/u turn, this last option would have been better, probably).
422 for (iterator_type it = boost::begin(m_turns);
423 it != boost::end(m_turns);
426 if (it->both(detail::overlay::operation_union))
428 typename occupation_map_type::iterator mit =
429 occupation_map.find(it->get_robust_point());
431 if (mit != occupation_map.end())
433 occupation_map.erase(mit);
438 // 2: Remove all points from map which has only one
439 typename occupation_map_type::iterator it = occupation_map.begin();
440 while (it != occupation_map.end())
442 if (it->second.count <= 1)
444 typename occupation_map_type::iterator to_erase = it;
446 occupation_map.erase(to_erase);
454 if (occupation_map.empty())
459 // 3: Add vectors (incoming->intersection-point,
460 // intersection-point -> outgoing)
461 // for all (co-located) points still present in the map
463 for (iterator_type it = boost::begin(m_turns);
464 it != boost::end(m_turns);
467 typename occupation_map_type::iterator mit =
468 occupation_map.find(it->get_robust_point());
470 if (mit != occupation_map.end())
472 buffer_occupation_info& info = mit->second;
473 for (int i = 0; i < 2; i++)
475 add_incoming_and_outgoing_angles(it->get_robust_point(), *it,
477 i, it->operations[i].seg_id,
481 it->count_on_multi++;
485 #if defined(BOOST_GEOMETRY_BUFFER_ENLARGED_CLUSTERS)
486 // X: Check rounding issues
489 for (typename occupation_map_type::const_iterator it = occupation_map.begin();
490 it != occupation_map.end(); ++it)
492 if (it->second.has_rounding_issues(it->first))
496 get_occupation(distance + 1);
504 // Get left turns from all clusters
505 for (typename occupation_map_type::iterator it = occupation_map.begin();
506 it != occupation_map.end(); ++it)
508 it->second.get_left_turns(it->first, m_turns, m_side_strategy);
512 inline void classify_turns()
514 for (typename boost::range_iterator<turn_vector_type>::type it =
515 boost::begin(m_turns); it != boost::end(m_turns); ++it)
517 if (it->count_within > 0)
519 it->location = inside_buffer;
521 if (it->count_on_original_boundary > 0)
523 it->location = inside_buffer;
525 #if ! defined(BOOST_GEOMETRY_BUFFER_USE_SIDE_OF_INTERSECTION)
526 if (it->count_within_near_offsetted > 0)
528 // Within can have in rare cases a rounding issue. We don't discard this
529 // point, so it can be used to continue started rings in traversal. But
530 // will never start a new ring from this type of points.
531 it->operations[0].enriched.startable = false;
532 it->operations[1].enriched.startable = false;
538 struct deflate_properties
543 inline deflate_properties()
544 : has_inflated(false)
549 inline void discard_turns_for_deflate()
551 // Deflate cases should have at least 3 points PER deflated original
552 // to form a correct triangle
554 // But if there are intersections between a deflated ring and another
555 // ring, it is all accepted
557 // In deflate most turns are i/u by nature, but u/u is also possible
559 std::map<signed_size_type, deflate_properties> properties;
561 for (typename boost::range_iterator<turn_vector_type const>::type it =
562 boost::begin(m_turns); it != boost::end(m_turns); ++it)
564 const buffer_turn_info_type& turn = *it;
565 if (turn.location == location_ok)
567 const buffer_turn_operation_type& op0 = turn.operations[0];
568 const buffer_turn_operation_type& op1 = turn.operations[1];
570 if (! m_pieces[op0.seg_id.piece_index].is_deflated
571 || ! m_pieces[op1.seg_id.piece_index].is_deflated)
573 properties[op0.seg_id.multi_index].has_inflated = true;
574 properties[op1.seg_id.multi_index].has_inflated = true;
578 // It is deflated, update counts
579 for (int i = 0; i < 2; i++)
581 const buffer_turn_operation_type& op = turn.operations[i];
582 if (op.operation == detail::overlay::operation_union
583 || op.operation == detail::overlay::operation_continue)
585 properties[op.seg_id.multi_index].count++;
591 for (typename boost::range_iterator<turn_vector_type>::type it =
592 boost::begin(m_turns); it != boost::end(m_turns); ++it)
594 buffer_turn_info_type& turn = *it;
596 if (turn.location == location_ok)
598 const buffer_turn_operation_type& op0 = turn.operations[0];
599 const buffer_turn_operation_type& op1 = turn.operations[1];
600 signed_size_type const multi0 = op0.seg_id.multi_index;
601 signed_size_type const multi1 = op1.seg_id.multi_index;
603 if (multi0 == multi1)
605 const deflate_properties& prop = properties[multi0];
606 if (! prop.has_inflated && prop.count < 3)
608 // Property is not inflated
609 // Not enough points, this might be caused by <float> where
610 // detection turn-in-original failed because of numeric errors
611 turn.location = location_discard;
616 // Two different (possibly deflated) rings
622 template <typename DistanceStrategy>
623 inline void check_remaining_points(DistanceStrategy const& distance_strategy)
625 // Check if a turn is inside any of the originals
627 turn_in_original_visitor<turn_vector_type> visitor(m_turns);
632 detail::partition::include_all_policy
633 >::apply(m_turns, robust_originals, visitor,
634 turn_get_box(), turn_in_original_ovelaps_box(),
635 original_get_box(), original_ovelaps_box());
637 bool const deflate = distance_strategy.negative();
639 for (typename boost::range_iterator<turn_vector_type>::type it =
640 boost::begin(m_turns); it != boost::end(m_turns); ++it)
642 buffer_turn_info_type& turn = *it;
643 if (turn.location == location_ok)
645 if (deflate && turn.count_in_original <= 0)
647 // For deflate/negative buffers: it is not in original, discard
648 turn.location = location_discard;
650 else if (! deflate && turn.count_in_original > 0)
652 // For inflate: it is in original, discard
653 turn.location = location_discard;
660 // Either strategy was negative, or there were interior rings
661 discard_turns_for_deflate();
665 inline bool assert_indices_in_robust_rings() const
667 geometry::equal_to<robust_point_type> comparator;
668 for (typename boost::range_iterator<turn_vector_type const>::type it =
669 boost::begin(m_turns); it != boost::end(m_turns); ++it)
671 for (int i = 0; i < 2; i++)
673 robust_point_type const &p1
674 = m_pieces[it->operations[i].piece_index].robust_ring
675 [it->operations[i].index_in_robust_ring];
676 robust_point_type const &p2 = it->robust_point;
677 if (! comparator(p1, p2))
686 inline void insert_rescaled_piece_turns()
688 // Add rescaled turn points to corresponding pieces
689 // (after this, each turn occurs twice)
690 std::size_t index = 0;
691 for (typename boost::range_iterator<turn_vector_type>::type it =
692 boost::begin(m_turns); it != boost::end(m_turns); ++it, ++index)
694 geometry::recalculate(it->robust_point, it->point, m_robust_policy);
695 #if defined(BOOST_GEOMETRY_BUFFER_ENLARGED_CLUSTERS)
696 it->mapped_robust_point = it->robust_point;
700 it->turn_index = index;
701 turn.turn_index = index;
702 turn.point = it->robust_point;
703 for (int i = 0; i < 2; i++)
705 turn.operation_index = i;
706 turn.seg_id = it->operations[i].seg_id;
707 turn.fraction = it->operations[i].fraction;
709 piece& pc = m_pieces[it->operations[i].piece_index];
710 pc.robust_turns.push_back(turn);
712 // Take into account for the box (intersection points should fall inside,
713 // but in theory they can be one off because of rounding
714 geometry::expand(pc.robust_envelope, it->robust_point);
715 geometry::expand(pc.robust_offsetted_envelope, it->robust_point);
719 #if ! defined(BOOST_GEOMETRY_BUFFER_USE_SIDE_OF_INTERSECTION)
720 // Insert all rescaled turn-points into these rings, to form a
721 // reliable integer-based ring. All turns can be compared (inside) to this
722 // rings to see if they are inside.
724 for (typename boost::range_iterator<piece_vector_type>::type
725 it = boost::begin(m_pieces); it != boost::end(m_pieces); ++it)
728 signed_size_type piece_segment_index = pc.first_seg_id.segment_index;
729 if (! pc.robust_turns.empty())
731 if (pc.robust_turns.size() > 1u)
733 std::sort(pc.robust_turns.begin(), pc.robust_turns.end(), buffer_operation_less());
735 // Walk through them, in reverse to insert at right index
736 signed_size_type index_offset = static_cast<signed_size_type>(pc.robust_turns.size()) - 1;
737 for (typename boost::range_reverse_iterator<const std::vector<robust_turn> >::type
738 rit = boost::const_rbegin(pc.robust_turns);
739 rit != boost::const_rend(pc.robust_turns);
740 ++rit, --index_offset)
742 signed_size_type const index_in_vector = 1 + rit->seg_id.segment_index - piece_segment_index;
743 BOOST_GEOMETRY_ASSERT
746 && index_in_vector < pc.offsetted_count
749 pc.robust_ring.insert(boost::begin(pc.robust_ring) + index_in_vector, rit->point);
750 pc.offsetted_count++;
752 m_turns[rit->turn_index].operations[rit->operation_index].index_in_robust_ring = index_in_vector + index_offset;
757 BOOST_GEOMETRY_ASSERT(assert_indices_in_robust_rings());
761 template <std::size_t Dimension>
762 static inline void determine_monotonicity(piece& pc,
763 robust_point_type const& current,
764 robust_point_type const& next)
766 if (geometry::get<Dimension>(current) >= geometry::get<Dimension>(next))
768 pc.is_monotonic_increasing[Dimension] = false;
770 if (geometry::get<Dimension>(current) <= geometry::get<Dimension>(next))
772 pc.is_monotonic_decreasing[Dimension] = false;
776 static inline void determine_properties(piece& pc)
778 pc.is_monotonic_increasing[0] = true;
779 pc.is_monotonic_increasing[1] = true;
780 pc.is_monotonic_decreasing[0] = true;
781 pc.is_monotonic_decreasing[1] = true;
783 pc.is_convex = geometry::is_convex(pc.robust_ring);
785 if (pc.offsetted_count < 2)
790 typename robust_ring_type::const_iterator current = pc.robust_ring.begin();
791 typename robust_ring_type::const_iterator next = current + 1;
793 for (signed_size_type i = 1; i < pc.offsetted_count; i++)
795 determine_monotonicity<0>(pc, *current, *next);
796 determine_monotonicity<1>(pc, *current, *next);
802 void determine_properties()
804 for (typename piece_vector_type::iterator it = boost::begin(m_pieces);
805 it != boost::end(m_pieces);
808 determine_properties(*it);
812 inline void reverse_negative_robust_rings()
814 for (typename piece_vector_type::iterator it = boost::begin(m_pieces);
815 it != boost::end(m_pieces);
819 if (geometry::area(pc.robust_ring, m_robust_area_strategy) < 0)
822 // - in a concave piece
823 // - in a line-buffer with a negative buffer-distance
824 std::reverse(pc.robust_ring.begin(), pc.robust_ring.end());
829 inline void prepare_buffered_point_piece(piece& pc)
831 // create monotonic sections in y-dimension
832 typedef boost::mpl::vector_c<std::size_t, 1> dimensions;
833 geometry::sectionalize<false, dimensions>(pc.robust_ring,
834 detail::no_rescale_policy(), pc.sections);
836 // Determine min/max radius
837 typedef geometry::model::referring_segment<robust_point_type const>
840 typename robust_ring_type::const_iterator current = pc.robust_ring.begin();
841 typename robust_ring_type::const_iterator next = current + 1;
843 for (signed_size_type i = 1; i < pc.offsetted_count; i++)
845 robust_segment_type s(*current, *next);
846 robust_comparable_radius_type const d
847 = geometry::comparable_distance(pc.robust_center, s);
849 if (i == 1 || d < pc.robust_min_comparable_radius)
851 pc.robust_min_comparable_radius = d;
853 if (i == 1 || d > pc.robust_max_comparable_radius)
855 pc.robust_max_comparable_radius = d;
863 inline void prepare_buffered_point_pieces()
865 for (typename piece_vector_type::iterator it = boost::begin(m_pieces);
866 it != boost::end(m_pieces);
869 if (it->type == geometry::strategy::buffer::buffered_point)
871 prepare_buffered_point_piece(*it);
876 inline void get_turns()
878 for(typename boost::range_iterator<sections_type>::type it
879 = boost::begin(monotonic_sections);
880 it != boost::end(monotonic_sections);
883 enlarge_box(it->bounding_box, 1);
887 // Calculate the turns
891 buffered_ring_collection<buffered_ring<Ring> >,
893 IntersectionStrategy,
895 > visitor(m_pieces, offsetted_rings, m_turns,
896 m_intersection_strategy, m_robust_policy);
901 >::apply(monotonic_sections, visitor,
902 detail::section::get_section_box(),
903 detail::section::overlaps_section_box());
906 insert_rescaled_piece_turns();
908 reverse_negative_robust_rings();
910 determine_properties();
912 prepare_buffered_point_pieces();
915 // Check if it is inside any of the pieces
916 turn_in_piece_visitor
918 turn_vector_type, piece_vector_type
919 > visitor(m_turns, m_pieces);
924 >::apply(m_turns, m_pieces, visitor,
925 turn_get_box(), turn_ovelaps_box(),
926 piece_get_box(), piece_ovelaps_box());
931 inline void start_new_ring(bool deflate)
933 signed_size_type const n = static_cast<signed_size_type>(offsetted_rings.size());
934 current_segment_id.source_index = 0;
935 current_segment_id.multi_index = n;
936 current_segment_id.ring_index = -1;
937 current_segment_id.segment_index = 0;
939 offsetted_rings.resize(n + 1);
940 current_robust_ring.clear();
942 m_first_piece_index = static_cast<signed_size_type>(boost::size(m_pieces));
946 // Pieces contain either deflated exterior rings, or inflated
947 // interior rings which are effectively deflated too
948 m_has_deflated = true;
952 inline void abort_ring()
954 // Remove all created pieces for this ring, sections, last offsetted
955 while (! m_pieces.empty()
956 && m_pieces.back().first_seg_id.multi_index
957 == current_segment_id.multi_index)
959 m_pieces.erase(m_pieces.end() - 1);
962 while (! monotonic_sections.empty()
963 && monotonic_sections.back().ring_id.multi_index
964 == current_segment_id.multi_index)
966 monotonic_sections.erase(monotonic_sections.end() - 1);
969 offsetted_rings.erase(offsetted_rings.end() - 1);
970 current_robust_ring.clear();
972 m_first_piece_index = -1;
975 inline void update_closing_point()
977 BOOST_GEOMETRY_ASSERT(! offsetted_rings.empty());
978 buffered_ring<Ring>& added = offsetted_rings.back();
979 if (! boost::empty(added))
981 range::back(added) = range::front(added);
985 inline void update_last_point(point_type const& p,
986 buffered_ring<Ring>& ring)
988 // For the first point of a new piece, and there were already
989 // points in the offsetted ring, for some piece types the first point
990 // is a duplicate of the last point of the previous piece.
992 // TODO: disable that, that point should not be added
994 // For now, it is made equal because due to numerical instability,
995 // it can be a tiny bit off, possibly causing a self-intersection
997 BOOST_GEOMETRY_ASSERT(boost::size(m_pieces) > 0);
999 && current_segment_id.segment_index
1000 == m_pieces.back().first_seg_id.segment_index)
1006 inline void set_piece_center(point_type const& center)
1008 BOOST_GEOMETRY_ASSERT(! m_pieces.empty());
1009 geometry::recalculate(m_pieces.back().robust_center, center,
1013 inline void finish_ring(strategy::buffer::result_code code,
1014 bool is_interior = false, bool has_interiors = false)
1016 if (code == strategy::buffer::result_error_numerical)
1022 if (m_first_piece_index == -1)
1027 if (m_first_piece_index < static_cast<signed_size_type>(boost::size(m_pieces)))
1029 // If piece was added
1030 // Reassign left-of-first and right-of-last
1031 geometry::range::at(m_pieces, m_first_piece_index).left_index
1032 = static_cast<signed_size_type>(boost::size(m_pieces)) - 1;
1033 geometry::range::back(m_pieces).right_index = m_first_piece_index;
1035 m_first_piece_index = -1;
1037 update_closing_point();
1039 if (! current_robust_ring.empty())
1041 BOOST_GEOMETRY_ASSERT
1043 geometry::equals(current_robust_ring.front(),
1044 current_robust_ring.back())
1047 robust_originals.push_back(
1048 robust_original(current_robust_ring,
1049 is_interior, has_interiors));
1053 inline void set_current_ring_concave()
1055 BOOST_GEOMETRY_ASSERT(boost::size(offsetted_rings) > 0);
1056 offsetted_rings.back().has_concave = true;
1059 inline signed_size_type add_point(point_type const& p)
1061 BOOST_GEOMETRY_ASSERT(boost::size(offsetted_rings) > 0);
1063 buffered_ring<Ring>& current_ring = offsetted_rings.back();
1064 update_last_point(p, current_ring);
1066 current_segment_id.segment_index++;
1067 current_ring.push_back(p);
1068 return static_cast<signed_size_type>(current_ring.size());
1071 //-------------------------------------------------------------------------
1073 inline piece& create_piece(strategy::buffer::piece_type type,
1074 bool decrease_segment_index_by_one)
1076 if (type == strategy::buffer::buffered_concave)
1078 offsetted_rings.back().has_concave = true;
1083 pc.index = static_cast<signed_size_type>(boost::size(m_pieces));
1084 pc.is_deflated = m_deflate;
1086 current_segment_id.piece_index = pc.index;
1088 pc.first_seg_id = current_segment_id;
1090 // Assign left/right (for first/last piece per ring they will be re-assigned later)
1091 pc.left_index = pc.index - 1;
1092 pc.right_index = pc.index + 1;
1094 std::size_t const n = boost::size(offsetted_rings.back());
1095 pc.first_seg_id.segment_index = decrease_segment_index_by_one ? n - 1 : n;
1096 pc.last_segment_index = pc.first_seg_id.segment_index;
1098 m_pieces.push_back(pc);
1099 return m_pieces.back();
1102 inline void init_rescale_piece(piece& pc, std::size_t helper_points_size)
1104 if (pc.first_seg_id.segment_index < 0)
1106 // This indicates an error situation: an earlier piece was empty
1107 // It currently does not happen
1108 // std::cout << "EMPTY " << pc.type << " " << pc.index << " " << pc.first_seg_id.multi_index << std::endl;
1109 pc.offsetted_count = 0;
1113 BOOST_GEOMETRY_ASSERT(pc.first_seg_id.multi_index >= 0);
1114 BOOST_GEOMETRY_ASSERT(pc.last_segment_index >= 0);
1116 pc.offsetted_count = pc.last_segment_index - pc.first_seg_id.segment_index;
1117 BOOST_GEOMETRY_ASSERT(pc.offsetted_count >= 0);
1119 pc.robust_ring.reserve(pc.offsetted_count + helper_points_size);
1121 // Add rescaled offsetted segments
1123 buffered_ring<Ring> const& ring = offsetted_rings[pc.first_seg_id.multi_index];
1125 typedef typename boost::range_iterator<const buffered_ring<Ring> >::type it_type;
1126 for (it_type it = boost::begin(ring) + pc.first_seg_id.segment_index;
1127 it != boost::begin(ring) + pc.last_segment_index;
1130 robust_point_type point;
1131 geometry::recalculate(point, *it, m_robust_policy);
1132 pc.robust_ring.push_back(point);
1137 inline robust_point_type add_helper_point(piece& pc, const point_type& point)
1139 #if defined(BOOST_GEOMETRY_BUFFER_USE_HELPER_POINTS)
1140 pc.helper_points.push_back(point);
1143 robust_point_type rob_point;
1144 geometry::recalculate(rob_point, point, m_robust_policy);
1145 pc.robust_ring.push_back(rob_point);
1149 // TODO: this is shared with sectionalize, move to somewhere else (assign?)
1150 template <typename Box, typename Value>
1151 inline void enlarge_box(Box& box, Value value)
1153 geometry::set<0, 0>(box, geometry::get<0, 0>(box) - value);
1154 geometry::set<0, 1>(box, geometry::get<0, 1>(box) - value);
1155 geometry::set<1, 0>(box, geometry::get<1, 0>(box) + value);
1156 geometry::set<1, 1>(box, geometry::get<1, 1>(box) + value);
1159 inline void calculate_robust_envelope(piece& pc)
1161 if (pc.offsetted_count == 0)
1166 geometry::envelope(pc.robust_ring, pc.robust_envelope);
1168 geometry::assign_inverse(pc.robust_offsetted_envelope);
1169 for (signed_size_type i = 0; i < pc.offsetted_count; i++)
1171 geometry::expand(pc.robust_offsetted_envelope, pc.robust_ring[i]);
1174 // Take roundings into account, enlarge boxes with 1 integer
1175 enlarge_box(pc.robust_envelope, 1);
1176 enlarge_box(pc.robust_offsetted_envelope, 1);
1179 inline void sectionalize(piece& pc)
1182 buffered_ring<Ring> const& ring = offsetted_rings.back();
1184 typedef geometry::detail::sectionalize::sectionalize_part
1187 boost::mpl::vector_c<std::size_t, 0, 1> // x,y dimension
1190 // Create a ring-identifier. The source-index is the piece index
1191 // The multi_index is as in this collection (the ring), but not used here
1192 // The ring_index is not used
1193 ring_identifier ring_id(pc.index, pc.first_seg_id.multi_index, -1);
1195 sectionalizer::apply(monotonic_sections,
1196 boost::begin(ring) + pc.first_seg_id.segment_index,
1197 boost::begin(ring) + pc.last_segment_index,
1202 inline void finish_piece(piece& pc)
1204 init_rescale_piece(pc, 0u);
1205 calculate_robust_envelope(pc);
1209 inline void finish_piece(piece& pc,
1210 const point_type& point1,
1211 const point_type& point2,
1212 const point_type& point3)
1214 init_rescale_piece(pc, 3u);
1215 if (pc.offsetted_count == 0)
1220 add_helper_point(pc, point1);
1221 robust_point_type mid_point = add_helper_point(pc, point2);
1222 add_helper_point(pc, point3);
1223 calculate_robust_envelope(pc);
1226 current_robust_ring.push_back(mid_point);
1229 inline void finish_piece(piece& pc,
1230 const point_type& point1,
1231 const point_type& point2,
1232 const point_type& point3,
1233 const point_type& point4)
1235 init_rescale_piece(pc, 4u);
1236 add_helper_point(pc, point1);
1237 robust_point_type mid_point2 = add_helper_point(pc, point2);
1238 robust_point_type mid_point1 = add_helper_point(pc, point3);
1239 add_helper_point(pc, point4);
1241 calculate_robust_envelope(pc);
1243 // Add mid-points in other order to current helper_ring
1244 current_robust_ring.push_back(mid_point1);
1245 current_robust_ring.push_back(mid_point2);
1248 inline void add_piece(strategy::buffer::piece_type type, point_type const& p,
1249 point_type const& b1, point_type const& b2)
1251 piece& pc = create_piece(type, false);
1253 pc.last_segment_index = add_point(b2);
1254 finish_piece(pc, b2, p, b1);
1257 template <typename Range>
1258 inline void add_range_to_piece(piece& pc, Range const& range, bool add_front)
1260 BOOST_GEOMETRY_ASSERT(boost::size(range) != 0u);
1262 typename Range::const_iterator it = boost::begin(range);
1264 // If it follows a non-join (so basically the same piece-type) point b1 should be added.
1265 // There should be two intersections later and it should be discarded.
1266 // But for now we need it to calculate intersections
1272 for (++it; it != boost::end(range); ++it)
1274 pc.last_segment_index = add_point(*it);
1279 template <typename Range>
1280 inline void add_piece(strategy::buffer::piece_type type, Range const& range,
1281 bool decrease_segment_index_by_one)
1283 piece& pc = create_piece(type, decrease_segment_index_by_one);
1285 if (boost::size(range) > 0u)
1287 add_range_to_piece(pc, range, offsetted_rings.back().empty());
1292 template <typename Range>
1293 inline void add_side_piece(point_type const& p1, point_type const& p2,
1294 Range const& range, bool first)
1296 BOOST_GEOMETRY_ASSERT(boost::size(range) >= 2u);
1298 piece& pc = create_piece(strategy::buffer::buffered_segment, ! first);
1299 add_range_to_piece(pc, range, first);
1300 finish_piece(pc, range.back(), p2, p1, range.front());
1303 template <typename Range>
1304 inline void add_piece(strategy::buffer::piece_type type,
1305 point_type const& p, Range const& range)
1307 piece& pc = create_piece(type, true);
1309 if (boost::size(range) > 0u)
1311 add_range_to_piece(pc, range, offsetted_rings.back().empty());
1312 finish_piece(pc, range.back(), p, range.front());
1320 template <typename EndcapStrategy, typename Range>
1321 inline void add_endcap(EndcapStrategy const& strategy, Range const& range,
1322 point_type const& end_point)
1324 boost::ignore_unused(strategy);
1330 strategy::buffer::piece_type pt = strategy.get_piece_type();
1331 if (pt == strategy::buffer::buffered_flat_end)
1333 // It is flat, should just be added, without helper segments
1334 add_piece(pt, range, true);
1338 // Normal case, it has an "inside", helper segments should be added
1339 add_piece(pt, end_point, range);
1343 inline void mark_flat_start()
1345 if (! m_pieces.empty())
1347 piece& back = m_pieces.back();
1348 back.is_flat_start = true;
1352 inline void mark_flat_end()
1354 if (! m_pieces.empty())
1356 piece& back = m_pieces.back();
1357 back.is_flat_end = true;
1361 //-------------------------------------------------------------------------
1363 inline void enrich()
1365 enrich_intersection_points<false, false, overlay_buffer>(m_turns,
1366 m_clusters, offsetted_rings, offsetted_rings,
1367 m_robust_policy, m_side_strategy);
1370 // Discards all rings which do have not-OK intersection points only.
1371 // Those can never be traversed and should not be part of the output.
1372 inline void discard_rings()
1374 for (typename boost::range_iterator<turn_vector_type const>::type it =
1375 boost::begin(m_turns); it != boost::end(m_turns); ++it)
1377 if (it->location != location_ok)
1379 offsetted_rings[it->operations[0].seg_id.multi_index].has_discarded_intersections = true;
1380 offsetted_rings[it->operations[1].seg_id.multi_index].has_discarded_intersections = true;
1384 offsetted_rings[it->operations[0].seg_id.multi_index].has_accepted_intersections = true;
1385 offsetted_rings[it->operations[1].seg_id.multi_index].has_accepted_intersections = true;
1390 inline bool point_coveredby_original(point_type const& point)
1392 robust_point_type any_point;
1393 geometry::recalculate(any_point, point, m_robust_policy);
1395 signed_size_type count_in_original = 0;
1397 // Check of the robust point of this outputted ring is in
1398 // any of the robust original rings
1399 // This can go quadratic if the input has many rings, and there
1400 // are many untouched deflated rings around
1401 for (typename std::vector<robust_original>::const_iterator it
1402 = robust_originals.begin();
1403 it != robust_originals.end();
1406 robust_original const& original = *it;
1407 if (detail::disjoint::disjoint_point_box(any_point,
1413 int const geometry_code
1414 = detail::within::point_in_geometry(any_point,
1417 if (geometry_code == -1)
1419 // Outside, continue
1423 // Apply for possibly nested interior rings
1424 if (original.m_is_interior)
1426 count_in_original--;
1428 else if (original.m_has_interiors)
1430 count_in_original++;
1434 // Exterior ring without interior rings
1438 return count_in_original > 0;
1441 // For a deflate, all rings around inner rings which are untouched
1442 // (no intersections/turns) and which are OUTSIDE the original should
1444 inline void discard_nonintersecting_deflated_rings()
1446 for(typename buffered_ring_collection<buffered_ring<Ring> >::iterator it
1447 = boost::begin(offsetted_rings);
1448 it != boost::end(offsetted_rings);
1451 buffered_ring<Ring>& ring = *it;
1452 if (! ring.has_intersections()
1453 && boost::size(ring) > 0u
1454 && geometry::area(ring, m_area_strategy) < 0)
1456 if (! point_coveredby_original(geometry::range::front(ring)))
1458 ring.is_untouched_outside_original = true;
1464 inline void block_turns()
1466 // To fix left-turn issues like #rt_u13
1467 // But currently it causes more other issues than it fixes
1470 // std::remove_if(boost::begin(m_turns), boost::end(m_turns),
1471 // redundant_turn()),
1472 // boost::end(m_turns)
1475 for (typename boost::range_iterator<turn_vector_type>::type it =
1476 boost::begin(m_turns); it != boost::end(m_turns); ++it)
1478 buffer_turn_info_type& turn = *it;
1479 if (turn.location != location_ok)
1481 // Discard this turn (don't set it to blocked to avoid colocated
1482 // clusters being discarded afterwards
1483 turn.discarded = true;
1488 inline void traverse()
1490 typedef detail::overlay::traverse
1493 buffered_ring_collection<buffered_ring<Ring> >,
1494 buffered_ring_collection<buffered_ring<Ring > >,
1496 backtrack_for_buffer
1498 std::map<ring_identifier, overlay::ring_turn_info> turn_info_per_ring;
1500 traversed_rings.clear();
1501 buffer_overlay_visitor visitor;
1502 traverser::apply(offsetted_rings, offsetted_rings,
1503 m_intersection_strategy, m_robust_policy,
1504 m_turns, traversed_rings,
1506 m_clusters, visitor);
1509 inline void reverse()
1511 for(typename buffered_ring_collection<buffered_ring<Ring> >::iterator it = boost::begin(offsetted_rings);
1512 it != boost::end(offsetted_rings);
1515 if (! it->has_intersections())
1517 std::reverse(it->begin(), it->end());
1520 for (typename boost::range_iterator<buffered_ring_collection<Ring> >::type
1521 it = boost::begin(traversed_rings);
1522 it != boost::end(traversed_rings);
1525 std::reverse(it->begin(), it->end());
1530 template <typename GeometryOutput, typename OutputIterator>
1531 inline OutputIterator assign(OutputIterator out) const
1533 typedef detail::overlay::ring_properties<point_type, area_result_type> properties;
1535 std::map<ring_identifier, properties> selected;
1537 // Select all rings which do not have any self-intersection
1538 // Inner rings, for deflate, which do not have intersections, and
1539 // which are outside originals, are skipped
1540 // (other ones should be traversed)
1541 signed_size_type index = 0;
1542 for(typename buffered_ring_collection<buffered_ring<Ring> >::const_iterator it = boost::begin(offsetted_rings);
1543 it != boost::end(offsetted_rings);
1546 if (! it->has_intersections()
1547 && ! it->is_untouched_outside_original)
1549 properties p = properties(*it, m_area_strategy);
1552 ring_identifier id(0, index, -1);
1558 // Select all created rings
1560 for (typename boost::range_iterator<buffered_ring_collection<Ring> const>::type
1561 it = boost::begin(traversed_rings);
1562 it != boost::end(traversed_rings);
1565 properties p = properties(*it, m_area_strategy);
1568 ring_identifier id(2, index, -1);
1573 // Assign parents, checking orientation but NOT discarding double
1574 // negative rings (negative child with negative parent)
1575 detail::overlay::assign_parents(offsetted_rings, traversed_rings,
1576 selected, m_intersection_strategy, true, false);
1577 return detail::overlay::add_rings<GeometryOutput>(selected, offsetted_rings, traversed_rings, out,
1584 }} // namespace detail::buffer
1585 #endif // DOXYGEN_NO_DETAIL
1588 }} // namespace boost::geometry
1590 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_BUFFERED_PIECE_COLLECTION_HPP