1 // Boost.Geometry (aka GGL, Generic Geometry Library)
2
3 // Copyright (c) 2007-2012 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_OVERLAY_TRAVERSE_HPP
10 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_TRAVERSE_HPP
11
12 #include <cstddef>
13
14 #include <boost/range.hpp>
15
16 #include <boost/geometry/algorithms/detail/overlay/backtrack_check_si.hpp>
17 #include <boost/geometry/algorithms/detail/overlay/copy_segments.hpp>
18 #include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
19 #include <boost/geometry/algorithms/num_points.hpp>
20 #include <boost/geometry/core/access.hpp>
21 #include <boost/geometry/core/assert.hpp>
22 #include <boost/geometry/core/closure.hpp>
23 #include <boost/geometry/core/coordinate_dimension.hpp>
24 #include <boost/geometry/geometries/concepts/check.hpp>
25
26 #if defined(BOOST_GEOMETRY_DEBUG_INTERSECTION) \
27 || defined(BOOST_GEOMETRY_OVERLAY_REPORT_WKT) \
28 || defined(BOOST_GEOMETRY_DEBUG_TRAVERSE)
29 # include <string>
30 # include <boost/geometry/algorithms/detail/overlay/debug_turn_info.hpp>
31 # include <boost/geometry/io/wkt/wkt.hpp>
32 #endif
33
34 namespace boost { namespace geometry
35 {
36
37 #ifndef DOXYGEN_NO_DETAIL
38 namespace detail { namespace overlay
39 {
40
41 template <typename Turn, typename Operation>
42 #ifdef BOOST_GEOMETRY_DEBUG_TRAVERSE
debug_traverse(Turn const & turn,Operation op,std::string const & header)43 inline void debug_traverse(Turn const& turn, Operation op,
44 std::string const& header)
45 {
46 std::cout << header
47 << " at " << op.seg_id
48 << " meth: " << method_char(turn.method)
49 << " op: " << operation_char(op.operation)
50 << " vis: " << visited_char(op.visited)
51 << " of: " << operation_char(turn.operations[0].operation)
52 << operation_char(turn.operations[1].operation)
53 << " " << geometry::wkt(turn.point)
54 << std::endl;
55
56 if (boost::contains(header, "Finished"))
57 {
58 std::cout << std::endl;
59 }
60 }
61 #else
62 inline void debug_traverse(Turn const& , Operation, const char*)
63 {
64 }
65 #endif
66
67
68 template <typename Info, typename Turn>
set_visited_for_continue(Info & info,Turn const & turn)69 inline void set_visited_for_continue(Info& info, Turn const& turn)
70 {
71 // On "continue", set "visited" for ALL directions
72 if (turn.operation == detail::overlay::operation_continue)
73 {
74 for (typename boost::range_iterator
75 <
76 typename Info::container_type
77 >::type it = boost::begin(info.operations);
78 it != boost::end(info.operations);
79 ++it)
80 {
81 if (it->visited.none())
82 {
83 it->visited.set_visited();
84 }
85 }
86 }
87 }
88
89
90 template
91 <
92 bool Reverse1, bool Reverse2,
93 typename GeometryOut,
94 typename G1,
95 typename G2,
96 typename Turns,
97 typename IntersectionInfo,
98 typename RobustPolicy
99 >
assign_next_ip(G1 const & g1,G2 const & g2,Turns & turns,typename boost::range_iterator<Turns>::type & ip,GeometryOut & current_output,IntersectionInfo & info,segment_identifier & seg_id,RobustPolicy const & robust_policy)100 inline bool assign_next_ip(G1 const& g1, G2 const& g2,
101 Turns& turns,
102 typename boost::range_iterator<Turns>::type& ip,
103 GeometryOut& current_output,
104 IntersectionInfo& info,
105 segment_identifier& seg_id,
106 RobustPolicy const& robust_policy)
107 {
108 info.visited.set_visited();
109 set_visited_for_continue(*ip, info);
110
111 // If there is no next IP on this segment
112 if (info.enriched.next_ip_index < 0)
113 {
114 if (info.enriched.travels_to_vertex_index < 0
115 || info.enriched.travels_to_ip_index < 0)
116 {
117 return false;
118 }
119
120 BOOST_GEOMETRY_ASSERT(info.enriched.travels_to_vertex_index >= 0);
121 BOOST_GEOMETRY_ASSERT(info.enriched.travels_to_ip_index >= 0);
122
123 if (info.seg_id.source_index == 0)
124 {
125 geometry::copy_segments<Reverse1>(g1, info.seg_id,
126 info.enriched.travels_to_vertex_index,
127 robust_policy,
128 current_output);
129 }
130 else
131 {
132 geometry::copy_segments<Reverse2>(g2, info.seg_id,
133 info.enriched.travels_to_vertex_index,
134 robust_policy,
135 current_output);
136 }
137 seg_id = info.seg_id;
138 ip = boost::begin(turns) + info.enriched.travels_to_ip_index;
139 }
140 else
141 {
142 ip = boost::begin(turns) + info.enriched.next_ip_index;
143 seg_id = info.seg_id;
144 }
145
146 detail::overlay::append_no_dups_or_spikes(current_output, ip->point,
147 robust_policy);
148
149 return true;
150 }
151
152
select_source(operation_type operation,signed_size_type source1,signed_size_type source2)153 inline bool select_source(operation_type operation,
154 signed_size_type source1,
155 signed_size_type source2)
156 {
157 return (operation == operation_intersection && source1 != source2)
158 || (operation == operation_union && source1 == source2)
159 ;
160 }
161
162
163 template
164 <
165 typename Turn,
166 typename Iterator
167 >
select_next_ip(operation_type operation,Turn & turn,segment_identifier const & seg_id,Iterator & selected)168 inline bool select_next_ip(operation_type operation,
169 Turn& turn,
170 segment_identifier const& seg_id,
171 Iterator& selected)
172 {
173 if (turn.discarded)
174 {
175 return false;
176 }
177 bool has_tp = false;
178 selected = boost::end(turn.operations);
179 for (Iterator it = boost::begin(turn.operations);
180 it != boost::end(turn.operations);
181 ++it)
182 {
183 if (it->visited.started())
184 {
185 selected = it;
186 //std::cout << " RETURN";
187 return true;
188 }
189
190 // In some cases there are two alternatives.
191 // For "ii", take the other one (alternate)
192 // UNLESS the other one is already visited
193 // For "uu", take the same one (see above);
194 // For "cc", take either one, but if there is a starting one,
195 // take that one.
196 if ( (it->operation == operation_continue
197 && (! has_tp || it->visited.started()
198 )
199 )
200 || (it->operation == operation
201 && ! it->visited.finished()
202 && (! has_tp
203 || select_source(operation,
204 it->seg_id.source_index, seg_id.source_index)
205 )
206 )
207 )
208 {
209 selected = it;
210 debug_traverse(turn, *it, " Candidate");
211 has_tp = true;
212 }
213 }
214
215 if (has_tp)
216 {
217 debug_traverse(turn, *selected, " Accepted");
218 }
219
220
221 return has_tp;
222 }
223
224
225
226 /*!
227 \brief Traverses through intersection points / geometries
228 \ingroup overlay
229 */
230 template
231 <
232 bool Reverse1, bool Reverse2,
233 typename Geometry1,
234 typename Geometry2,
235 typename Backtrack = backtrack_check_self_intersections<Geometry1, Geometry2>
236 >
237 class traverse
238 {
239 public :
240 template <typename RobustPolicy, typename Turns, typename Rings>
apply(Geometry1 const & geometry1,Geometry2 const & geometry2,detail::overlay::operation_type operation,RobustPolicy const & robust_policy,Turns & turns,Rings & rings)241 static inline void apply(Geometry1 const& geometry1,
242 Geometry2 const& geometry2,
243 detail::overlay::operation_type operation,
244 RobustPolicy const& robust_policy,
245 Turns& turns, Rings& rings)
246 {
247 typedef typename boost::range_value<Rings>::type ring_type;
248 typedef typename boost::range_iterator<Turns>::type turn_iterator;
249 typedef typename boost::range_value<Turns>::type turn_type;
250 typedef typename boost::range_iterator
251 <
252 typename turn_type::container_type
253 >::type turn_operation_iterator_type;
254
255 std::size_t const min_num_points
256 = core_detail::closure::minimum_ring_size
257 <
258 geometry::closure<ring_type>::value
259 >::value;
260
261 std::size_t size_at_start = boost::size(rings);
262
263 typename Backtrack::state_type state;
264 do
265 {
266 state.reset();
267
268 // Iterate through all unvisited points
269 for (turn_iterator it = boost::begin(turns);
270 state.good() && it != boost::end(turns);
271 ++it)
272 {
273 // Skip discarded ones
274 if (! (it->discarded || ! it->selectable_start || it->blocked()))
275 {
276 for (turn_operation_iterator_type iit = boost::begin(it->operations);
277 state.good() && iit != boost::end(it->operations);
278 ++iit)
279 {
280 if (iit->visited.none()
281 && ! iit->visited.rejected()
282 && (iit->operation == operation
283 || iit->operation == detail::overlay::operation_continue)
284 )
285 {
286 set_visited_for_continue(*it, *iit);
287
288 ring_type current_output;
289 detail::overlay::append_no_dups_or_spikes(current_output,
290 it->point, robust_policy);
291
292 turn_iterator current = it;
293 turn_operation_iterator_type current_iit = iit;
294 segment_identifier current_seg_id;
295
296 if (! detail::overlay::assign_next_ip<Reverse1, Reverse2>(
297 geometry1, geometry2,
298 turns,
299 current, current_output,
300 *iit, current_seg_id,
301 robust_policy))
302 {
303 Backtrack::apply(
304 size_at_start,
305 rings, current_output, turns, *current_iit,
306 "No next IP",
307 geometry1, geometry2, robust_policy, state);
308 }
309
310 if (! detail::overlay::select_next_ip(
311 operation,
312 *current,
313 current_seg_id,
314 current_iit))
315 {
316 Backtrack::apply(
317 size_at_start,
318 rings, current_output, turns, *iit,
319 "Dead end at start",
320 geometry1, geometry2, robust_policy, state);
321 }
322 else
323 {
324
325 iit->visited.set_started();
326 detail::overlay::debug_traverse(*it, *iit, "-> Started");
327 detail::overlay::debug_traverse(*current, *current_iit, "Selected ");
328
329
330 typename boost::range_size<Turns>::type i = 0;
331
332 while (current_iit != iit && state.good())
333 {
334 if (current_iit->visited.visited())
335 {
336 // It visits a visited node again, without passing the start node.
337 // This makes it suspicious for endless loops
338 Backtrack::apply(
339 size_at_start,
340 rings, current_output, turns, *iit,
341 "Visit again",
342 geometry1, geometry2, robust_policy, state);
343 }
344 else
345 {
346
347
348 // We assume clockwise polygons only, non self-intersecting, closed.
349 // However, the input might be different, and checking validity
350 // is up to the library user.
351
352 // Therefore we make here some sanity checks. If the input
353 // violates the assumptions, the output polygon will not be correct
354 // but the routine will stop and output the current polygon, and
355 // will continue with the next one.
356
357 // Below three reasons to stop.
358 detail::overlay::assign_next_ip<Reverse1, Reverse2>(
359 geometry1, geometry2,
360 turns, current, current_output,
361 *current_iit, current_seg_id,
362 robust_policy);
363
364 if (! detail::overlay::select_next_ip(
365 operation,
366 *current,
367 current_seg_id,
368 current_iit))
369 {
370 // Should not occur in valid (non-self-intersecting) polygons
371 // Should not occur in self-intersecting polygons without spikes
372 // Might occur in polygons with spikes
373 Backtrack::apply(
374 size_at_start,
375 rings, current_output, turns, *iit,
376 "Dead end",
377 geometry1, geometry2, robust_policy, state);
378 }
379 else
380 {
381 detail::overlay::debug_traverse(*current, *current_iit, "Selected ");
382 }
383
384 if (i++ > 2 + 2 * turns.size())
385 {
386 // Sanity check: there may be never more loops
387 // than turn points.
388 // Turn points marked as "ii" can be visited twice.
389 Backtrack::apply(
390 size_at_start,
391 rings, current_output, turns, *iit,
392 "Endless loop",
393 geometry1, geometry2, robust_policy, state);
394 }
395 }
396 }
397
398 if (state.good())
399 {
400 iit->visited.set_finished();
401 detail::overlay::debug_traverse(*current, *iit, "->Finished");
402 if (geometry::num_points(current_output) >= min_num_points)
403 {
404 clean_closing_dups_and_spikes(current_output, robust_policy);
405 rings.push_back(current_output);
406 }
407 }
408 }
409 }
410 }
411 }
412 }
413 } while (! state.good());
414 }
415 };
416
417 }} // namespace detail::overlay
418 #endif // DOXYGEN_NO_DETAIL
419
420 }} // namespace boost::geometry
421
422 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_TRAVERSE_HPP
423