1 // Boost.Geometry (aka GGL, Generic Geometry Library)
3 // Copyright (c) 2012-2014 Barend Gehrels, Amsterdam, the Netherlands.
4 // Copyright (c) 2017 Adam Wulkiewicz, Lodz, Poland.
6 // This file was modified by Oracle on 2017, 2018.
7 // Modifications copyright (c) 2017-2018 Oracle and/or its affiliates.
8 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
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)
14 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_GET_PIECE_TURNS_HPP
15 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_GET_PIECE_TURNS_HPP
17 #include <boost/core/ignore_unused.hpp>
18 #include <boost/range.hpp>
20 #include <boost/geometry/core/assert.hpp>
21 #include <boost/geometry/algorithms/equals.hpp>
22 #include <boost/geometry/algorithms/detail/disjoint/box_box.hpp>
23 #include <boost/geometry/algorithms/detail/overlay/segment_identifier.hpp>
24 #include <boost/geometry/algorithms/detail/overlay/get_turn_info.hpp>
25 #include <boost/geometry/algorithms/detail/sections/section_functions.hpp>
26 #include <boost/geometry/algorithms/detail/buffer/buffer_policies.hpp>
29 namespace boost { namespace geometry
33 #ifndef DOXYGEN_NO_DETAIL
34 namespace detail { namespace buffer
37 // Implements a unique_sub_range for a buffered piece,
38 // the range can return subsequent points
39 // known as "i", "j" and "k" (and further), indexed as 0,1,2,3
40 template <typename Ring>
41 struct unique_sub_range_from_piece
43 typedef typename boost::range_iterator<Ring const>::type iterator_type;
44 typedef typename geometry::point_type<Ring const>::type point_type;
46 unique_sub_range_from_piece(Ring const& ring,
47 iterator_type iterator_at_i, iterator_type iterator_at_j)
49 , m_iterator_at_i(iterator_at_i)
50 , m_iterator_at_j(iterator_at_j)
51 , m_point_retrieved(false)
54 static inline bool is_first_segment() { return false; }
55 static inline bool is_last_segment() { return false; }
57 static inline std::size_t size() { return 3u; }
59 inline point_type const& at(std::size_t index) const
61 BOOST_GEOMETRY_ASSERT(index < size());
64 case 0 : return *m_iterator_at_i;
65 case 1 : return *m_iterator_at_j;
66 case 2 : return get_point_k();
67 default : return *m_iterator_at_i;
73 inline point_type const& get_point_k() const
75 if (! m_point_retrieved)
77 m_iterator_at_k = advance_one(m_iterator_at_j);
78 m_point_retrieved = true;
80 return *m_iterator_at_k;
83 inline void circular_advance_one(iterator_type& next) const
86 if (next == boost::end(m_ring))
88 next = boost::begin(m_ring) + 1;
92 inline iterator_type advance_one(iterator_type it) const
94 iterator_type result = it;
95 circular_advance_one(result);
97 // TODO: we could also use piece-boundaries
98 // to check if the point equals the last one
99 while (geometry::equals(*it, *result))
101 circular_advance_one(result);
107 iterator_type m_iterator_at_i;
108 iterator_type m_iterator_at_j;
109 mutable iterator_type m_iterator_at_k;
110 mutable bool m_point_retrieved;
118 typename IntersectionStrategy,
119 typename RobustPolicy
121 class piece_turn_visitor
123 Pieces const& m_pieces;
124 Rings const& m_rings;
126 IntersectionStrategy const& m_intersection_strategy;
127 RobustPolicy const& m_robust_policy;
129 template <typename Piece>
130 inline bool is_adjacent(Piece const& piece1, Piece const& piece2) const
132 if (piece1.first_seg_id.multi_index != piece2.first_seg_id.multi_index)
137 return piece1.index == piece2.left_index
138 || piece1.index == piece2.right_index;
141 template <typename Piece>
142 inline bool is_on_same_convex_ring(Piece const& piece1, Piece const& piece2) const
144 if (piece1.first_seg_id.multi_index != piece2.first_seg_id.multi_index)
149 return ! m_rings[piece1.first_seg_id.multi_index].has_concave;
153 template <std::size_t Dimension, typename Iterator, typename Box>
154 inline void move_begin_iterator(Iterator& it_begin, Iterator it_beyond,
155 signed_size_type& index, int dir,
156 Box const& this_bounding_box,
157 Box const& other_bounding_box)
159 for(; it_begin != it_beyond
160 && it_begin + 1 != it_beyond
161 && detail::section::preceding<Dimension>(dir, *(it_begin + 1),
169 template <std::size_t Dimension, typename Iterator, typename Box>
170 inline void move_end_iterator(Iterator it_begin, Iterator& it_beyond,
171 int dir, Box const& this_bounding_box,
172 Box const& other_bounding_box)
174 while (it_beyond != it_begin
175 && it_beyond - 1 != it_begin
176 && it_beyond - 2 != it_begin)
178 if (detail::section::exceeding<Dimension>(dir, *(it_beyond - 2),
179 this_bounding_box, other_bounding_box, m_robust_policy))
190 template <typename Piece, typename Section>
191 inline void calculate_turns(Piece const& piece1, Piece const& piece2,
192 Section const& section1, Section const& section2)
194 typedef typename boost::range_value<Rings const>::type ring_type;
195 typedef typename boost::range_value<Turns const>::type turn_type;
196 typedef typename boost::range_iterator<ring_type const>::type iterator;
198 signed_size_type const piece1_first_index = piece1.first_seg_id.segment_index;
199 signed_size_type const piece2_first_index = piece2.first_seg_id.segment_index;
200 if (piece1_first_index < 0 || piece2_first_index < 0)
205 // Get indices of part of offsetted_rings for this monotonic section:
206 signed_size_type const sec1_first_index = piece1_first_index + section1.begin_index;
207 signed_size_type const sec2_first_index = piece2_first_index + section2.begin_index;
209 // index of last point in section, beyond-end is one further
210 signed_size_type const sec1_last_index = piece1_first_index + section1.end_index;
211 signed_size_type const sec2_last_index = piece2_first_index + section2.end_index;
213 // get geometry and iterators over these sections
214 ring_type const& ring1 = m_rings[piece1.first_seg_id.multi_index];
215 iterator it1_first = boost::begin(ring1) + sec1_first_index;
216 iterator it1_beyond = boost::begin(ring1) + sec1_last_index + 1;
218 ring_type const& ring2 = m_rings[piece2.first_seg_id.multi_index];
219 iterator it2_first = boost::begin(ring2) + sec2_first_index;
220 iterator it2_beyond = boost::begin(ring2) + sec2_last_index + 1;
222 // Set begin/end of monotonic ranges, in both x/y directions
223 signed_size_type index1 = sec1_first_index;
224 move_begin_iterator<0>(it1_first, it1_beyond, index1,
225 section1.directions[0], section1.bounding_box, section2.bounding_box);
226 move_end_iterator<0>(it1_first, it1_beyond,
227 section1.directions[0], section1.bounding_box, section2.bounding_box);
228 move_begin_iterator<1>(it1_first, it1_beyond, index1,
229 section1.directions[1], section1.bounding_box, section2.bounding_box);
230 move_end_iterator<1>(it1_first, it1_beyond,
231 section1.directions[1], section1.bounding_box, section2.bounding_box);
233 signed_size_type index2 = sec2_first_index;
234 move_begin_iterator<0>(it2_first, it2_beyond, index2,
235 section2.directions[0], section2.bounding_box, section1.bounding_box);
236 move_end_iterator<0>(it2_first, it2_beyond,
237 section2.directions[0], section2.bounding_box, section1.bounding_box);
238 move_begin_iterator<1>(it2_first, it2_beyond, index2,
239 section2.directions[1], section2.bounding_box, section1.bounding_box);
240 move_end_iterator<1>(it2_first, it2_beyond,
241 section2.directions[1], section2.bounding_box, section1.bounding_box);
244 the_model.operations[0].piece_index = piece1.index;
245 the_model.operations[0].seg_id = piece1.first_seg_id;
246 the_model.operations[0].seg_id.segment_index = index1; // override
248 iterator it1 = it1_first;
249 for (iterator prev1 = it1++;
251 prev1 = it1++, the_model.operations[0].seg_id.segment_index++)
253 the_model.operations[1].piece_index = piece2.index;
254 the_model.operations[1].seg_id = piece2.first_seg_id;
255 the_model.operations[1].seg_id.segment_index = index2; // override
256 geometry::recalculate(the_model.rob_pi, *prev1, m_robust_policy);
257 geometry::recalculate(the_model.rob_pj, *it1, m_robust_policy);
259 unique_sub_range_from_piece<ring_type> unique_sub_range1(ring1, prev1, it1);
261 iterator it2 = it2_first;
262 for (iterator prev2 = it2++;
264 prev2 = it2++, the_model.operations[1].seg_id.segment_index++)
266 unique_sub_range_from_piece<ring_type> unique_sub_range2(ring2, prev2, it2);
267 geometry::recalculate(the_model.rob_qi, *prev2, m_robust_policy);
268 geometry::recalculate(the_model.rob_qj, *it2, m_robust_policy);
270 // TODO: internally get_turn_info calculates robust points.
271 // But they are already calculated.
272 // We should be able to use them.
273 // this means passing them to this visitor,
274 // and iterating in sync with them...
275 typedef detail::overlay::get_turn_info
277 detail::overlay::assign_null_policy
280 turn_policy::apply(unique_sub_range1, unique_sub_range2,
282 m_intersection_strategy,
284 std::back_inserter(m_turns));
291 piece_turn_visitor(Pieces const& pieces,
292 Rings const& ring_collection,
294 IntersectionStrategy const& intersection_strategy,
295 RobustPolicy const& robust_policy)
297 , m_rings(ring_collection)
299 , m_intersection_strategy(intersection_strategy)
300 , m_robust_policy(robust_policy)
303 template <typename Section>
304 inline bool apply(Section const& section1, Section const& section2,
307 boost::ignore_unused(first);
309 typedef typename boost::range_value<Pieces const>::type piece_type;
310 piece_type const& piece1 = m_pieces[section1.ring_id.source_index];
311 piece_type const& piece2 = m_pieces[section2.ring_id.source_index];
313 if ( piece1.index == piece2.index
314 || is_adjacent(piece1, piece2)
315 || is_on_same_convex_ring(piece1, piece2)
316 || detail::disjoint::disjoint_box_box(section1.bounding_box,
317 section2.bounding_box,
318 m_intersection_strategy.get_disjoint_box_box_strategy()) )
323 calculate_turns(piece1, piece2, section1, section2);
330 }} // namespace detail::buffer
331 #endif // DOXYGEN_NO_DETAIL
334 }} // namespace boost::geometry
336 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_GET_PIECE_TURNS_HPP