1 // Boost.Geometry (aka GGL, Generic Geometry Library)
2
3 // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
4 // Copyright (c) 2017 Adam Wulkiewicz, Lodz, Poland.
5
6 // This file was modified by Oracle on 2017, 2019.
7 // Modifications copyright (c) 2017, 2019 Oracle and/or its affiliates.
8
9 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
10
11 // Use, modification and distribution is subject to the Boost Software License,
12 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
13 // http://www.boost.org/LICENSE_1_0.txt)
14
15 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_ENRICH_HPP
16 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_ENRICH_HPP
17
18 #include <cstddef>
19 #include <algorithm>
20 #include <map>
21 #include <set>
22 #include <vector>
23
24 #ifdef BOOST_GEOMETRY_DEBUG_ENRICH
25 # include <iostream>
26 # include <boost/geometry/algorithms/detail/overlay/debug_turn_info.hpp>
27 # include <boost/geometry/io/wkt/wkt.hpp>
28 # if ! defined(BOOST_GEOMETRY_DEBUG_IDENTIFIER)
29 # define BOOST_GEOMETRY_DEBUG_IDENTIFIER
30 #endif
31 #endif
32
33 #include <boost/range.hpp>
34
35 #include <boost/geometry/algorithms/detail/ring_identifier.hpp>
36 #include <boost/geometry/algorithms/detail/overlay/handle_colocations.hpp>
37 #include <boost/geometry/algorithms/detail/overlay/handle_self_turns.hpp>
38 #include <boost/geometry/algorithms/detail/overlay/is_self_turn.hpp>
39 #include <boost/geometry/algorithms/detail/overlay/less_by_segment_ratio.hpp>
40 #include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp>
41 #include <boost/geometry/policies/robustness/robust_type.hpp>
42
43 #ifdef BOOST_GEOMETRY_DEBUG_ENRICH
44 # include <boost/geometry/algorithms/detail/overlay/check_enrich.hpp>
45 #endif
46
47
48 namespace boost { namespace geometry
49 {
50
51 #ifndef DOXYGEN_NO_DETAIL
52 namespace detail { namespace overlay
53 {
54
55 template <typename Turns>
56 struct discarded_indexed_turn
57 {
discarded_indexed_turnboost::geometry::detail::overlay::discarded_indexed_turn58 discarded_indexed_turn(Turns const& turns)
59 : m_turns(turns)
60 {}
61
62 template <typename IndexedTurn>
operator ()boost::geometry::detail::overlay::discarded_indexed_turn63 inline bool operator()(IndexedTurn const& indexed) const
64 {
65 return m_turns[indexed.turn_index].discarded;
66 }
67
68 Turns const& m_turns;
69 };
70
71 // Sorts IP-s of this ring on segment-identifier, and if on same segment,
72 // on distance.
73 // Then assigns for each IP which is the next IP on this segment,
74 // plus the vertex-index to travel to, plus the next IP
75 // (might be on another segment)
76 template
77 <
78 bool Reverse1, bool Reverse2,
79 typename Operations,
80 typename Turns,
81 typename Geometry1, typename Geometry2,
82 typename RobustPolicy,
83 typename SideStrategy
84 >
enrich_sort(Operations & operations,Turns const & turns,Geometry1 const & geometry1,Geometry2 const & geometry2,RobustPolicy const & robust_policy,SideStrategy const & strategy)85 inline void enrich_sort(Operations& operations,
86 Turns const& turns,
87 Geometry1 const& geometry1,
88 Geometry2 const& geometry2,
89 RobustPolicy const& robust_policy,
90 SideStrategy const& strategy)
91 {
92 std::sort(boost::begin(operations),
93 boost::end(operations),
94 less_by_segment_ratio
95 <
96 Turns,
97 typename boost::range_value<Operations>::type,
98 Geometry1, Geometry2,
99 RobustPolicy,
100 SideStrategy,
101 Reverse1, Reverse2
102 >(turns, geometry1, geometry2, robust_policy, strategy));
103 }
104
105
106 template <typename Operations, typename Turns>
enrich_assign(Operations & operations,Turns & turns,bool check_turns)107 inline void enrich_assign(Operations& operations, Turns& turns,
108 bool check_turns)
109 {
110 typedef typename boost::range_value<Turns>::type turn_type;
111 typedef typename turn_type::turn_operation_type op_type;
112 typedef typename boost::range_iterator<Operations>::type iterator_type;
113
114
115 if (operations.size() > 0)
116 {
117 // Assign travel-to-vertex/ip index for each turning point.
118 // Iterator "next" is circular
119
120 geometry::ever_circling_range_iterator<Operations const> next(operations);
121 ++next;
122
123 for (iterator_type it = boost::begin(operations);
124 it != boost::end(operations); ++it)
125 {
126 turn_type& turn = turns[it->turn_index];
127 op_type& op = turn.operations[it->operation_index];
128
129 if (check_turns && it->turn_index == next->turn_index)
130 {
131 // Normal behaviour: next points at next turn, increase next.
132 // For dissolve this should not be done, turn_index is often
133 // the same for two consecutive operations
134 ++next;
135 }
136
137 // Cluster behaviour: next should point after cluster, unless
138 // their seg_ids are not the same
139 // (For dissolve, this is still to be examined - TODO)
140 while (turn.is_clustered()
141 && it->turn_index != next->turn_index
142 && turn.cluster_id == turns[next->turn_index].cluster_id
143 && op.seg_id == turns[next->turn_index].operations[next->operation_index].seg_id)
144 {
145 ++next;
146 }
147
148 turn_type const& next_turn = turns[next->turn_index];
149 op_type const& next_op = next_turn.operations[next->operation_index];
150
151 op.enriched.travels_to_ip_index
152 = static_cast<signed_size_type>(next->turn_index);
153 op.enriched.travels_to_vertex_index
154 = next->subject->seg_id.segment_index;
155
156 if (op.seg_id.segment_index == next_op.seg_id.segment_index
157 && op.fraction < next_op.fraction)
158 {
159 // Next turn is located further on same segment
160 // assign next_ip_index
161 // (this is one not circular therefore fraction is considered)
162 op.enriched.next_ip_index = static_cast<signed_size_type>(next->turn_index);
163 }
164
165 if (! check_turns)
166 {
167 ++next;
168 }
169 }
170 }
171
172 // DEBUG
173 #ifdef BOOST_GEOMETRY_DEBUG_ENRICH
174 {
175 for (iterator_type it = boost::begin(operations);
176 it != boost::end(operations);
177 ++it)
178 {
179 op_type const& op = turns[it->turn_index]
180 .operations[it->operation_index];
181
182 std::cout << it->turn_index
183 << " cl=" << turns[it->turn_index].cluster_id
184 << " meth=" << method_char(turns[it->turn_index].method)
185 << " seg=" << op.seg_id
186 << " dst=" << op.fraction // needs define
187 << " op=" << operation_char(turns[it->turn_index].operations[0].operation)
188 << operation_char(turns[it->turn_index].operations[1].operation)
189 << " (" << operation_char(op.operation) << ")"
190 << " nxt=" << op.enriched.next_ip_index
191 << " / " << op.enriched.travels_to_ip_index
192 << " [vx " << op.enriched.travels_to_vertex_index << "]"
193 << std::boolalpha << turns[it->turn_index].discarded
194 << std::endl;
195 ;
196 }
197 }
198 #endif
199 // END DEBUG
200
201 }
202
203 template <typename Operations, typename Turns>
enrich_adapt(Operations & operations,Turns & turns)204 inline void enrich_adapt(Operations& operations, Turns& turns)
205 {
206 typedef typename boost::range_value<Turns>::type turn_type;
207 typedef typename turn_type::turn_operation_type op_type;
208 typedef typename boost::range_value<Operations>::type indexed_turn_type;
209
210 if (operations.size() < 3)
211 {
212 // If it is empty, or contains one or two turns, it makes no sense
213 return;
214 }
215
216 // Operations is a vector of indexed_turn_operation<>
217
218 // Last index:
219 std::size_t const x = operations.size() - 1;
220 bool next_phase = false;
221
222 for (std::size_t i = 0; i < operations.size(); i++)
223 {
224 indexed_turn_type const& indexed = operations[i];
225
226 turn_type& turn = turns[indexed.turn_index];
227 op_type& op = turn.operations[indexed.operation_index];
228
229 // Previous/next index
230 std::size_t const p = i > 0 ? i - 1 : x;
231 std::size_t const n = i < x ? i + 1 : 0;
232
233 turn_type const& next_turn = turns[operations[n].turn_index];
234 op_type const& next_op = next_turn.operations[operations[n].operation_index];
235
236 if (op.seg_id.segment_index == next_op.seg_id.segment_index)
237 {
238 turn_type const& prev_turn = turns[operations[p].turn_index];
239 op_type const& prev_op = prev_turn.operations[operations[p].operation_index];
240 if (op.seg_id.segment_index == prev_op.seg_id.segment_index)
241 {
242 op.enriched.startable = false;
243 next_phase = true;
244 }
245 }
246 }
247
248 if (! next_phase)
249 {
250 return;
251 }
252
253 // Discard turns which are both non-startable
254 next_phase = false;
255 for (typename boost::range_iterator<Turns>::type
256 it = boost::begin(turns);
257 it != boost::end(turns);
258 ++it)
259 {
260 turn_type& turn = *it;
261 if (! turn.operations[0].enriched.startable
262 && ! turn.operations[1].enriched.startable)
263 {
264 turn.discarded = true;
265 next_phase = true;
266 }
267 }
268
269 if (! next_phase)
270 {
271 return;
272 }
273
274 // Remove discarded turns from operations to avoid having them as next turn
275 discarded_indexed_turn<Turns> const predicate(turns);
276 operations.erase(std::remove_if(boost::begin(operations),
277 boost::end(operations), predicate), boost::end(operations));
278 }
279
280 template <typename Turns, typename MappedVector>
create_map(Turns const & turns,MappedVector & mapped_vector)281 inline void create_map(Turns const& turns, MappedVector& mapped_vector)
282 {
283 typedef typename boost::range_value<Turns>::type turn_type;
284 typedef typename turn_type::container_type container_type;
285 typedef typename MappedVector::mapped_type mapped_type;
286 typedef typename boost::range_value<mapped_type>::type indexed_type;
287
288 std::size_t index = 0;
289 for (typename boost::range_iterator<Turns const>::type
290 it = boost::begin(turns);
291 it != boost::end(turns);
292 ++it, ++index)
293 {
294 // Add all (non discarded) operations on this ring
295 // Blocked operations or uu on clusters (for intersection)
296 // should be included, to block potential paths in clusters
297 turn_type const& turn = *it;
298 if (turn.discarded)
299 {
300 continue;
301 }
302
303 std::size_t op_index = 0;
304 for (typename boost::range_iterator<container_type const>::type
305 op_it = boost::begin(turn.operations);
306 op_it != boost::end(turn.operations);
307 ++op_it, ++op_index)
308 {
309 ring_identifier const ring_id
310 (
311 op_it->seg_id.source_index,
312 op_it->seg_id.multi_index,
313 op_it->seg_id.ring_index
314 );
315 mapped_vector[ring_id].push_back
316 (
317 indexed_type(index, op_index, *op_it,
318 it->operations[1 - op_index].seg_id)
319 );
320 }
321 }
322 }
323
324 template <typename Point1, typename Point2>
325 inline typename geometry::coordinate_type<Point1>::type
distance_measure(Point1 const & a,Point2 const & b)326 distance_measure(Point1 const& a, Point2 const& b)
327 {
328 // TODO: use comparable distance for point-point instead - but that
329 // causes currently cycling include problems
330 typedef typename geometry::coordinate_type<Point1>::type ctype;
331 ctype const dx = get<0>(a) - get<0>(b);
332 ctype const dy = get<1>(a) - get<1>(b);
333 return dx * dx + dy * dy;
334 }
335
336 template <typename Turns>
calculate_remaining_distance(Turns & turns)337 inline void calculate_remaining_distance(Turns& turns)
338 {
339 typedef typename boost::range_value<Turns>::type turn_type;
340 typedef typename turn_type::turn_operation_type op_type;
341
342 for (typename boost::range_iterator<Turns>::type
343 it = boost::begin(turns);
344 it != boost::end(turns);
345 ++it)
346 {
347 turn_type& turn = *it;
348
349 op_type& op0 = turn.operations[0];
350 op_type& op1 = turn.operations[1];
351
352 if (op0.remaining_distance != 0
353 || op1.remaining_distance != 0)
354 {
355 continue;
356 }
357
358 signed_size_type const to_index0 = op0.enriched.get_next_turn_index();
359 signed_size_type const to_index1 = op1.enriched.get_next_turn_index();
360 if (to_index0 >= 0
361 && to_index1 >= 0
362 && to_index0 != to_index1)
363 {
364 op0.remaining_distance = distance_measure(turn.point, turns[to_index0].point);
365 op1.remaining_distance = distance_measure(turn.point, turns[to_index1].point);
366 }
367 }
368 }
369
370
371 }} // namespace detail::overlay
372 #endif //DOXYGEN_NO_DETAIL
373
374
375
376 /*!
377 \brief All intersection points are enriched with successor information
378 \ingroup overlay
379 \tparam Turns type of intersection container
380 (e.g. vector of "intersection/turn point"'s)
381 \tparam Clusters type of cluster container
382 \tparam Geometry1 \tparam_geometry
383 \tparam Geometry2 \tparam_geometry
384 \tparam PointInGeometryStrategy point in geometry strategy type
385 \param turns container containing intersection points
386 \param clusters container containing clusters
387 \param geometry1 \param_geometry
388 \param geometry2 \param_geometry
389 \param robust_policy policy to handle robustness issues
390 \param strategy point in geometry strategy
391 */
392 template
393 <
394 bool Reverse1, bool Reverse2,
395 overlay_type OverlayType,
396 typename Turns,
397 typename Clusters,
398 typename Geometry1, typename Geometry2,
399 typename RobustPolicy,
400 typename IntersectionStrategy
401 >
enrich_intersection_points(Turns & turns,Clusters & clusters,Geometry1 const & geometry1,Geometry2 const & geometry2,RobustPolicy const & robust_policy,IntersectionStrategy const & strategy)402 inline void enrich_intersection_points(Turns& turns,
403 Clusters& clusters,
404 Geometry1 const& geometry1, Geometry2 const& geometry2,
405 RobustPolicy const& robust_policy,
406 IntersectionStrategy const& strategy)
407 {
408 static const detail::overlay::operation_type target_operation
409 = detail::overlay::operation_from_overlay<OverlayType>::value;
410 static const detail::overlay::operation_type opposite_operation
411 = target_operation == detail::overlay::operation_union
412 ? detail::overlay::operation_intersection
413 : detail::overlay::operation_union;
414 static const bool is_dissolve = OverlayType == overlay_dissolve;
415
416 typedef typename boost::range_value<Turns>::type turn_type;
417 typedef typename turn_type::turn_operation_type op_type;
418 typedef detail::overlay::indexed_turn_operation
419 <
420 op_type
421 > indexed_turn_operation;
422
423 typedef std::map
424 <
425 ring_identifier,
426 std::vector<indexed_turn_operation>
427 > mapped_vector_type;
428
429 // From here on, turn indexes are used (in clusters, next_index, etc)
430 // and may only be flagged as discarded
431
432 bool has_cc = false;
433 bool const has_colocations
434 = detail::overlay::handle_colocations<Reverse1, Reverse2, OverlayType>(turns,
435 clusters, geometry1, geometry2);
436
437 // Discard turns not part of target overlay
438 for (typename boost::range_iterator<Turns>::type
439 it = boost::begin(turns);
440 it != boost::end(turns);
441 ++it)
442 {
443 turn_type& turn = *it;
444
445 if (turn.both(detail::overlay::operation_none)
446 || turn.both(opposite_operation)
447 || turn.both(detail::overlay::operation_blocked)
448 || (detail::overlay::is_self_turn<OverlayType>(turn)
449 && ! turn.is_clustered()
450 && ! turn.both(target_operation)))
451 {
452 // For all operations, discard xx and none/none
453 // For intersections, remove uu to avoid the need to travel
454 // a union (during intersection) in uu/cc clusters (e.g. #31,#32,#33)
455 // The ux is necessary to indicate impossible paths
456 // (especially if rescaling is removed)
457
458 // Similarly, for union, discard ii and ix
459
460 // For self-turns, only keep uu / ii
461
462 turn.discarded = true;
463 turn.cluster_id = -1;
464 continue;
465 }
466
467 if (! turn.discarded
468 && turn.both(detail::overlay::operation_continue))
469 {
470 has_cc = true;
471 }
472 }
473
474 if (! is_dissolve)
475 {
476 detail::overlay::discard_closed_turns
477 <
478 OverlayType,
479 target_operation
480 >::apply(turns, clusters, geometry1, geometry2,
481 strategy);
482 detail::overlay::discard_open_turns
483 <
484 OverlayType,
485 target_operation
486 >::apply(turns, clusters, geometry1, geometry2,
487 strategy);
488 }
489
490 // Create a map of vectors of indexed operation-types to be able
491 // to sort intersection points PER RING
492 mapped_vector_type mapped_vector;
493
494 detail::overlay::create_map(turns, mapped_vector);
495
496 // No const-iterator; contents of mapped copy is temporary,
497 // and changed by enrich
498 for (typename mapped_vector_type::iterator mit
499 = mapped_vector.begin();
500 mit != mapped_vector.end();
501 ++mit)
502 {
503 #ifdef BOOST_GEOMETRY_DEBUG_ENRICH
504 std::cout << "ENRICH-sort Ring "
505 << mit->first << std::endl;
506 #endif
507 detail::overlay::enrich_sort<Reverse1, Reverse2>(
508 mit->second, turns,
509 geometry1, geometry2,
510 robust_policy, strategy.get_side_strategy());
511 }
512
513 for (typename mapped_vector_type::iterator mit
514 = mapped_vector.begin();
515 mit != mapped_vector.end();
516 ++mit)
517 {
518 #ifdef BOOST_GEOMETRY_DEBUG_ENRICH
519 std::cout << "ENRICH-assign Ring "
520 << mit->first << std::endl;
521 #endif
522 if (is_dissolve)
523 {
524 detail::overlay::enrich_adapt(mit->second, turns);
525 }
526
527 detail::overlay::enrich_assign(mit->second, turns, ! is_dissolve);
528 }
529
530 if (has_colocations)
531 {
532 // First gather cluster properties (using even clusters with
533 // discarded turns - for open turns), then clean up clusters
534 detail::overlay::gather_cluster_properties
535 <
536 Reverse1,
537 Reverse2,
538 OverlayType
539 >(clusters, turns, target_operation,
540 geometry1, geometry2, strategy.get_side_strategy());
541
542 detail::overlay::cleanup_clusters(turns, clusters);
543 }
544
545 if (has_cc)
546 {
547 detail::overlay::calculate_remaining_distance(turns);
548 }
549
550 #ifdef BOOST_GEOMETRY_DEBUG_ENRICH
551 //detail::overlay::check_graph(turns, for_operation);
552 #endif
553
554 }
555
556 }} // namespace boost::geometry
557
558 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_ENRICH_HPP
559