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 2017.
7 // Modifications copyright (c) 2017 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_GET_PIECE_TURNS_HPP
15 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_GET_PIECE_TURNS_HPP
16 
17 #include <boost/range.hpp>
18 
19 #include <boost/geometry/algorithms/equals.hpp>
20 #include <boost/geometry/algorithms/expand.hpp>
21 #include <boost/geometry/algorithms/detail/disjoint/box_box.hpp>
22 #include <boost/geometry/algorithms/detail/overlay/segment_identifier.hpp>
23 #include <boost/geometry/algorithms/detail/overlay/get_turn_info.hpp>
24 #include <boost/geometry/algorithms/detail/sections/section_functions.hpp>
25 #include <boost/geometry/algorithms/detail/buffer/buffer_policies.hpp>
26 
27 
28 namespace boost { namespace geometry
29 {
30 
31 
32 #ifndef DOXYGEN_NO_DETAIL
33 namespace detail { namespace buffer
34 {
35 
36 
37 #if defined(BOOST_GEOMETRY_BUFFER_USE_SIDE_OF_INTERSECTION)
38 struct buffer_assign_turn
39 {
40     static bool const include_no_turn = false;
41     static bool const include_degenerate = false;
42     static bool const include_opposite = false;
43 
44     template
45     <
46         typename Info,
47         typename Point1,
48         typename Point2,
49         typename IntersectionInfo
50     >
applyboost::geometry::detail::buffer::buffer_assign_turn51     static inline void apply(Info& info,
52                              Point1 const& /*p1*/,
53                              Point2 const& /*p2*/,
54                              IntersectionInfo const& iinfo)
55     {
56         info.rob_pi = iinfo.rpi();
57         info.rob_pj = iinfo.rpj();
58         info.rob_qi = iinfo.rqi();
59         info.rob_qj = iinfo.rqj();
60     }
61 
62 };
63 #endif
64 
65 template
66 <
67     typename Pieces,
68     typename Rings,
69     typename Turns,
70     typename IntersectionStrategy,
71     typename RobustPolicy
72 >
73 class piece_turn_visitor
74 {
75     Pieces const& m_pieces;
76     Rings const& m_rings;
77     Turns& m_turns;
78     IntersectionStrategy const& m_intersection_strategy;
79     RobustPolicy const& m_robust_policy;
80 
81     template <typename Piece>
is_adjacent(Piece const & piece1,Piece const & piece2) const82     inline bool is_adjacent(Piece const& piece1, Piece const& piece2) const
83     {
84         if (piece1.first_seg_id.multi_index != piece2.first_seg_id.multi_index)
85         {
86             return false;
87         }
88 
89         return piece1.index == piece2.left_index
90             || piece1.index == piece2.right_index;
91     }
92 
93     template <typename Piece>
is_on_same_convex_ring(Piece const & piece1,Piece const & piece2) const94     inline bool is_on_same_convex_ring(Piece const& piece1, Piece const& piece2) const
95     {
96         if (piece1.first_seg_id.multi_index != piece2.first_seg_id.multi_index)
97         {
98             return false;
99         }
100 
101         return ! m_rings[piece1.first_seg_id.multi_index].has_concave;
102     }
103 
104     template <typename Range, typename Iterator>
move_to_next_point(Range const & range,Iterator & next) const105     inline void move_to_next_point(Range const& range, Iterator& next) const
106     {
107         ++next;
108         if (next == boost::end(range))
109         {
110             next = boost::begin(range) + 1;
111         }
112     }
113 
114     template <typename Range, typename Iterator>
next_point(Range const & range,Iterator it) const115     inline Iterator next_point(Range const& range, Iterator it) const
116     {
117         Iterator result = it;
118         move_to_next_point(range, result);
119         // TODO: we could use either piece-boundaries, or comparison with
120         // robust points, to check if the point equals the last one
121         while(geometry::equals(*it, *result))
122         {
123             move_to_next_point(range, result);
124         }
125         return result;
126     }
127 
128     template <std::size_t Dimension, typename Iterator, typename Box>
move_begin_iterator(Iterator & it_begin,Iterator it_beyond,signed_size_type & index,int dir,Box const & this_bounding_box,Box const & other_bounding_box)129     inline void move_begin_iterator(Iterator& it_begin, Iterator it_beyond,
130                                     signed_size_type& index, int dir,
131                                     Box const& this_bounding_box,
132                                     Box const& other_bounding_box)
133     {
134         for(; it_begin != it_beyond
135                 && it_begin + 1 != it_beyond
136                 && detail::section::preceding<Dimension>(dir, *(it_begin + 1),
137                                                          this_bounding_box,
138                                                          other_bounding_box,
139                                                          m_robust_policy);
140             ++it_begin, index++)
141         {}
142     }
143 
144     template <std::size_t Dimension, typename Iterator, typename Box>
move_end_iterator(Iterator it_begin,Iterator & it_beyond,int dir,Box const & this_bounding_box,Box const & other_bounding_box)145     inline void move_end_iterator(Iterator it_begin, Iterator& it_beyond,
146                                   int dir, Box const& this_bounding_box,
147                                   Box const& other_bounding_box)
148     {
149         while (it_beyond != it_begin
150             && it_beyond - 1 != it_begin
151             && it_beyond - 2 != it_begin)
152         {
153             if (detail::section::exceeding<Dimension>(dir, *(it_beyond - 2),
154                         this_bounding_box, other_bounding_box, m_robust_policy))
155             {
156                 --it_beyond;
157             }
158             else
159             {
160                 return;
161             }
162         }
163     }
164 
165     template <typename Piece, typename Section>
calculate_turns(Piece const & piece1,Piece const & piece2,Section const & section1,Section const & section2)166     inline void calculate_turns(Piece const& piece1, Piece const& piece2,
167         Section const& section1, Section const& section2)
168     {
169         typedef typename boost::range_value<Rings const>::type ring_type;
170         typedef typename boost::range_value<Turns const>::type turn_type;
171         typedef typename boost::range_iterator<ring_type const>::type iterator;
172 
173         signed_size_type const piece1_first_index = piece1.first_seg_id.segment_index;
174         signed_size_type const piece2_first_index = piece2.first_seg_id.segment_index;
175         if (piece1_first_index < 0 || piece2_first_index < 0)
176         {
177             return;
178         }
179 
180         // Get indices of part of offsetted_rings for this monotonic section:
181         signed_size_type const sec1_first_index = piece1_first_index + section1.begin_index;
182         signed_size_type const sec2_first_index = piece2_first_index + section2.begin_index;
183 
184         // index of last point in section, beyond-end is one further
185         signed_size_type const sec1_last_index = piece1_first_index + section1.end_index;
186         signed_size_type const sec2_last_index = piece2_first_index + section2.end_index;
187 
188         // get geometry and iterators over these sections
189         ring_type const& ring1 = m_rings[piece1.first_seg_id.multi_index];
190         iterator it1_first = boost::begin(ring1) + sec1_first_index;
191         iterator it1_beyond = boost::begin(ring1) + sec1_last_index + 1;
192 
193         ring_type const& ring2 = m_rings[piece2.first_seg_id.multi_index];
194         iterator it2_first = boost::begin(ring2) + sec2_first_index;
195         iterator it2_beyond = boost::begin(ring2) + sec2_last_index + 1;
196 
197         // Set begin/end of monotonic ranges, in both x/y directions
198         signed_size_type index1 = sec1_first_index;
199         move_begin_iterator<0>(it1_first, it1_beyond, index1,
200                     section1.directions[0], section1.bounding_box, section2.bounding_box);
201         move_end_iterator<0>(it1_first, it1_beyond,
202                     section1.directions[0], section1.bounding_box, section2.bounding_box);
203         move_begin_iterator<1>(it1_first, it1_beyond, index1,
204                     section1.directions[1], section1.bounding_box, section2.bounding_box);
205         move_end_iterator<1>(it1_first, it1_beyond,
206                     section1.directions[1], section1.bounding_box, section2.bounding_box);
207 
208         signed_size_type index2 = sec2_first_index;
209         move_begin_iterator<0>(it2_first, it2_beyond, index2,
210                     section2.directions[0], section2.bounding_box, section1.bounding_box);
211         move_end_iterator<0>(it2_first, it2_beyond,
212                     section2.directions[0], section2.bounding_box, section1.bounding_box);
213         move_begin_iterator<1>(it2_first, it2_beyond, index2,
214                     section2.directions[1], section2.bounding_box, section1.bounding_box);
215         move_end_iterator<1>(it2_first, it2_beyond,
216                     section2.directions[1], section2.bounding_box, section1.bounding_box);
217 
218         turn_type the_model;
219         the_model.operations[0].piece_index = piece1.index;
220         the_model.operations[0].seg_id = piece1.first_seg_id;
221         the_model.operations[0].seg_id.segment_index = index1; // override
222 
223         iterator it1 = it1_first;
224         for (iterator prev1 = it1++;
225                 it1 != it1_beyond;
226                 prev1 = it1++, the_model.operations[0].seg_id.segment_index++)
227         {
228             the_model.operations[1].piece_index = piece2.index;
229             the_model.operations[1].seg_id = piece2.first_seg_id;
230             the_model.operations[1].seg_id.segment_index = index2; // override
231 
232             iterator next1 = next_point(ring1, it1);
233 
234             iterator it2 = it2_first;
235             for (iterator prev2 = it2++;
236                     it2 != it2_beyond;
237                     prev2 = it2++, the_model.operations[1].seg_id.segment_index++)
238             {
239                 iterator next2 = next_point(ring2, it2);
240 
241                 // TODO: internally get_turn_info calculates robust points.
242                 // But they are already calculated.
243                 // We should be able to use them.
244                 // this means passing them to this visitor,
245                 // and iterating in sync with them...
246                 typedef detail::overlay::get_turn_info
247                     <
248 #if defined(BOOST_GEOMETRY_BUFFER_USE_SIDE_OF_INTERSECTION)
249                         buffer_assign_turn
250 #else
251                         detail::overlay::assign_null_policy
252 #endif
253                     > turn_policy;
254 
255                 turn_policy::apply(*prev1, *it1, *next1,
256                                     *prev2, *it2, *next2,
257                                     false, false, false, false,
258                                     the_model,
259                                     m_intersection_strategy,
260                                     m_robust_policy,
261                                     std::back_inserter(m_turns));
262             }
263         }
264     }
265 
266 public:
267 
piece_turn_visitor(Pieces const & pieces,Rings const & ring_collection,Turns & turns,IntersectionStrategy const & intersection_strategy,RobustPolicy const & robust_policy)268     piece_turn_visitor(Pieces const& pieces,
269             Rings const& ring_collection,
270             Turns& turns,
271             IntersectionStrategy const& intersection_strategy,
272             RobustPolicy const& robust_policy)
273         : m_pieces(pieces)
274         , m_rings(ring_collection)
275         , m_turns(turns)
276         , m_intersection_strategy(intersection_strategy)
277         , m_robust_policy(robust_policy)
278     {}
279 
280     template <typename Section>
apply(Section const & section1,Section const & section2,bool first=true)281     inline bool apply(Section const& section1, Section const& section2,
282                     bool first = true)
283     {
284         boost::ignore_unused_variable_warning(first);
285 
286         typedef typename boost::range_value<Pieces const>::type piece_type;
287         piece_type const& piece1 = m_pieces[section1.ring_id.source_index];
288         piece_type const& piece2 = m_pieces[section2.ring_id.source_index];
289 
290         if ( piece1.index == piece2.index
291           || is_adjacent(piece1, piece2)
292           || is_on_same_convex_ring(piece1, piece2)
293           || detail::disjoint::disjoint_box_box(section1.bounding_box,
294                                                 section2.bounding_box) )
295         {
296             return true;
297         }
298 
299         calculate_turns(piece1, piece2, section1, section2);
300 
301         return true;
302     }
303 };
304 
305 
306 }} // namespace detail::buffer
307 #endif // DOXYGEN_NO_DETAIL
308 
309 
310 }} // namespace boost::geometry
311 
312 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_GET_PIECE_TURNS_HPP
313