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