1 // Boost.Geometry (aka GGL, Generic Geometry Library)
2 
3 // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
4 
5 // This file was modified by Oracle on 2017.
6 // Modifications copyright (c) 2017 Oracle and/or its affiliates.
7 
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_OVERLAY_ENRICH_HPP
15 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_ENRICH_HPP
16 
17 #include <cstddef>
18 #include <algorithm>
19 #include <map>
20 #include <set>
21 #include <vector>
22 
23 #ifdef BOOST_GEOMETRY_DEBUG_ENRICH
24 #  include <iostream>
25 #  include <boost/geometry/algorithms/detail/overlay/debug_turn_info.hpp>
26 #  include <boost/geometry/io/wkt/wkt.hpp>
27 #  if ! defined(BOOST_GEOMETRY_DEBUG_IDENTIFIER)
28 #    define BOOST_GEOMETRY_DEBUG_IDENTIFIER
29   #endif
30 #endif
31 
32 #include <boost/range.hpp>
33 
34 #include <boost/geometry/algorithms/detail/ring_identifier.hpp>
35 #include <boost/geometry/algorithms/detail/overlay/handle_colocations.hpp>
36 #include <boost/geometry/algorithms/detail/overlay/handle_self_turns.hpp>
37 #include <boost/geometry/algorithms/detail/overlay/is_self_turn.hpp>
38 #include <boost/geometry/algorithms/detail/overlay/less_by_segment_ratio.hpp>
39 #include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp>
40 #include <boost/geometry/policies/robustness/robust_type.hpp>
41 
42 #ifdef BOOST_GEOMETRY_DEBUG_ENRICH
43 #  include <boost/geometry/algorithms/detail/overlay/check_enrich.hpp>
44 #endif
45 
46 
47 namespace boost { namespace geometry
48 {
49 
50 #ifndef DOXYGEN_NO_DETAIL
51 namespace detail { namespace overlay
52 {
53 
54 
55 // Sorts IP-s of this ring on segment-identifier, and if on same segment,
56 //  on distance.
57 // Then assigns for each IP which is the next IP on this segment,
58 // plus the vertex-index to travel to, plus the next IP
59 // (might be on another segment)
60 template
61 <
62     bool Reverse1, bool Reverse2,
63     typename Operations,
64     typename Turns,
65     typename Geometry1, typename Geometry2,
66     typename RobustPolicy,
67     typename SideStrategy
68 >
enrich_sort(Operations & operations,Turns const & turns,operation_type for_operation,Geometry1 const & geometry1,Geometry2 const & geometry2,RobustPolicy const & robust_policy,SideStrategy const & strategy)69 inline void enrich_sort(Operations& operations,
70             Turns const& turns,
71             operation_type for_operation,
72             Geometry1 const& geometry1,
73             Geometry2 const& geometry2,
74             RobustPolicy const& robust_policy,
75             SideStrategy const& strategy)
76 {
77     std::sort(boost::begin(operations),
78             boost::end(operations),
79             less_by_segment_ratio
80                 <
81                     Turns,
82                     typename boost::range_value<Operations>::type,
83                     Geometry1, Geometry2,
84                     RobustPolicy,
85                     SideStrategy,
86                     Reverse1, Reverse2
87                 >(turns, for_operation, geometry1, geometry2, robust_policy, strategy));
88 }
89 
90 
91 template <typename Operations, typename Turns>
enrich_assign(Operations & operations,Turns & turns)92 inline void enrich_assign(Operations& operations, Turns& turns)
93 {
94     typedef typename boost::range_value<Turns>::type turn_type;
95     typedef typename turn_type::turn_operation_type op_type;
96     typedef typename boost::range_iterator<Operations>::type iterator_type;
97 
98 
99     if (operations.size() > 0)
100     {
101         // Assign travel-to-vertex/ip index for each turning point.
102         // Iterator "next" is circular
103 
104         geometry::ever_circling_range_iterator<Operations const> next(operations);
105         ++next;
106 
107         for (iterator_type it = boost::begin(operations);
108              it != boost::end(operations); ++it)
109         {
110             turn_type& turn = turns[it->turn_index];
111             op_type& op = turn.operations[it->operation_index];
112 
113             // Normal behaviour: next should point at next turn:
114             if (it->turn_index == next->turn_index)
115             {
116                 ++next;
117             }
118 
119             // Cluster behaviour: next should point after cluster, unless
120             // their seg_ids are not the same
121             while (turn.cluster_id != -1
122                    && it->turn_index != next->turn_index
123                    && turn.cluster_id == turns[next->turn_index].cluster_id
124                    && op.seg_id == turns[next->turn_index].operations[next->operation_index].seg_id)
125             {
126                 ++next;
127             }
128 
129             turn_type const& next_turn = turns[next->turn_index];
130             op_type const& next_op = next_turn.operations[next->operation_index];
131 
132             op.enriched.travels_to_ip_index
133                     = static_cast<signed_size_type>(next->turn_index);
134             op.enriched.travels_to_vertex_index
135                     = next->subject->seg_id.segment_index;
136 
137             if (op.seg_id.segment_index == next_op.seg_id.segment_index
138                     && op.fraction < next_op.fraction)
139             {
140                 // Next turn is located further on same segment
141                 // assign next_ip_index
142                 // (this is one not circular therefore fraction is considered)
143                 op.enriched.next_ip_index = static_cast<signed_size_type>(next->turn_index);
144             }
145         }
146     }
147 
148     // DEBUG
149 #ifdef BOOST_GEOMETRY_DEBUG_ENRICH
150     {
151         for (iterator_type it = boost::begin(operations);
152              it != boost::end(operations);
153              ++it)
154         {
155             op_type const& op = turns[it->turn_index]
156                 .operations[it->operation_index];
157 
158             std::cout << it->turn_index
159                 << " cl=" << turns[it->turn_index].cluster_id
160                 << " meth=" << method_char(turns[it->turn_index].method)
161                 << " seg=" << op.seg_id
162                 << " dst=" << op.fraction // needs define
163                 << " op=" << operation_char(turns[it->turn_index].operations[0].operation)
164                 << operation_char(turns[it->turn_index].operations[1].operation)
165                 << " (" << operation_char(op.operation) << ")"
166                 << " nxt=" << op.enriched.next_ip_index
167                 << " / " << op.enriched.travels_to_ip_index
168                 << " [vx " << op.enriched.travels_to_vertex_index << "]"
169                 << std::boolalpha << turns[it->turn_index].discarded
170                 << std::endl;
171                 ;
172         }
173     }
174 #endif
175     // END DEBUG
176 
177 }
178 
179 
180 template <typename Turns, typename MappedVector>
create_map(Turns const & turns,MappedVector & mapped_vector)181 inline void create_map(Turns const& turns, MappedVector& mapped_vector)
182 {
183     typedef typename boost::range_value<Turns>::type turn_type;
184     typedef typename turn_type::container_type container_type;
185     typedef typename MappedVector::mapped_type mapped_type;
186     typedef typename boost::range_value<mapped_type>::type indexed_type;
187 
188     std::size_t index = 0;
189     for (typename boost::range_iterator<Turns const>::type
190             it = boost::begin(turns);
191          it != boost::end(turns);
192          ++it, ++index)
193     {
194         // Add all (non discarded) operations on this ring
195         // Blocked operations or uu on clusters (for intersection)
196         // should be included, to block potential paths in clusters
197         turn_type const& turn = *it;
198         if (turn.discarded)
199         {
200             continue;
201         }
202 
203         std::size_t op_index = 0;
204         for (typename boost::range_iterator<container_type const>::type
205                 op_it = boost::begin(turn.operations);
206             op_it != boost::end(turn.operations);
207             ++op_it, ++op_index)
208         {
209             ring_identifier const ring_id
210                 (
211                     op_it->seg_id.source_index,
212                     op_it->seg_id.multi_index,
213                     op_it->seg_id.ring_index
214                 );
215             mapped_vector[ring_id].push_back
216                 (
217                     indexed_type(index, op_index, *op_it,
218                         it->operations[1 - op_index].seg_id)
219                 );
220         }
221     }
222 }
223 
224 template <typename Point1, typename Point2>
225 inline typename geometry::coordinate_type<Point1>::type
distance_measure(Point1 const & a,Point2 const & b)226         distance_measure(Point1 const& a, Point2 const& b)
227 {
228     // TODO: use comparable distance for point-point instead - but that
229     // causes currently cycling include problems
230     typedef typename geometry::coordinate_type<Point1>::type ctype;
231     ctype const dx = get<0>(a) - get<0>(b);
232     ctype const dy = get<1>(a) - get<1>(b);
233     return dx * dx + dy * dy;
234 }
235 
236 template <typename Turns>
calculate_remaining_distance(Turns & turns)237 inline void calculate_remaining_distance(Turns& turns)
238 {
239     typedef typename boost::range_value<Turns>::type turn_type;
240     typedef typename turn_type::turn_operation_type op_type;
241 
242     for (typename boost::range_iterator<Turns>::type
243             it = boost::begin(turns);
244          it != boost::end(turns);
245          ++it)
246     {
247         turn_type& turn = *it;
248         if (! turn.both(detail::overlay::operation_continue))
249         {
250            continue;
251         }
252 
253         op_type& op0 = turn.operations[0];
254         op_type& op1 = turn.operations[1];
255 
256         if (op0.remaining_distance != 0
257          || op1.remaining_distance != 0)
258         {
259             continue;
260         }
261 
262         int const to_index0 = op0.enriched.get_next_turn_index();
263         int const to_index1 = op1.enriched.get_next_turn_index();
264         if (to_index1 >= 0
265                 && to_index1 >= 0
266                 && to_index0 != to_index1)
267         {
268             op0.remaining_distance = distance_measure(turn.point, turns[to_index0].point);
269             op1.remaining_distance = distance_measure(turn.point, turns[to_index1].point);
270         }
271     }
272 }
273 
274 
275 }} // namespace detail::overlay
276 #endif //DOXYGEN_NO_DETAIL
277 
278 
279 
280 /*!
281 \brief All intersection points are enriched with successor information
282 \ingroup overlay
283 \tparam Turns type of intersection container
284             (e.g. vector of "intersection/turn point"'s)
285 \tparam Clusters type of cluster container
286 \tparam Geometry1 \tparam_geometry
287 \tparam Geometry2 \tparam_geometry
288 \tparam SideStrategy side strategy type
289 \param turns container containing intersection points
290 \param clusters container containing clusters
291 \param geometry1 \param_geometry
292 \param geometry2 \param_geometry
293 \param robust_policy policy to handle robustness issues
294 \param strategy strategy
295  */
296 template
297 <
298     bool Reverse1, bool Reverse2,
299     overlay_type OverlayType,
300     typename Turns,
301     typename Clusters,
302     typename Geometry1, typename Geometry2,
303     typename RobustPolicy,
304     typename SideStrategy
305 >
enrich_intersection_points(Turns & turns,Clusters & clusters,Geometry1 const & geometry1,Geometry2 const & geometry2,RobustPolicy const & robust_policy,SideStrategy const & strategy)306 inline void enrich_intersection_points(Turns& turns,
307     Clusters& clusters,
308     Geometry1 const& geometry1, Geometry2 const& geometry2,
309     RobustPolicy const& robust_policy,
310     SideStrategy const& strategy)
311 {
312     static const detail::overlay::operation_type target_operation
313             = detail::overlay::operation_from_overlay<OverlayType>::value;
314     static const detail::overlay::operation_type opposite_operation
315             = target_operation == detail::overlay::operation_union
316             ? detail::overlay::operation_intersection
317             : detail::overlay::operation_union;
318 
319     typedef typename boost::range_value<Turns>::type turn_type;
320     typedef typename turn_type::turn_operation_type op_type;
321     typedef detail::overlay::indexed_turn_operation
322         <
323             op_type
324         > indexed_turn_operation;
325 
326     typedef std::map
327         <
328             ring_identifier,
329             std::vector<indexed_turn_operation>
330         > mapped_vector_type;
331 
332     bool has_cc = false;
333     bool const has_colocations
334         = detail::overlay::handle_colocations<Reverse1, Reverse2, OverlayType>(turns,
335         clusters, geometry1, geometry2);
336 
337     // Discard turns not part of target overlay
338     for (typename boost::range_iterator<Turns>::type
339             it = boost::begin(turns);
340          it != boost::end(turns);
341          ++it)
342     {
343         turn_type& turn = *it;
344 
345         if (turn.both(detail::overlay::operation_none))
346         {
347             turn.discarded = true;
348             continue;
349         }
350 
351         if (turn.both(opposite_operation))
352         {
353             // For intersections, remove uu to avoid the need to travel
354             // a union (during intersection) in uu/cc clusters (e.g. #31,#32,#33)
355             // Also, for union, discard ii
356             turn.discarded = true;
357             turn.cluster_id = -1;
358             continue;
359         }
360 
361         if (detail::overlay::is_self_turn<OverlayType>(turn)
362             && turn.cluster_id < 0
363             && ! turn.both(target_operation))
364         {
365             // Only keep self-uu-turns or self-ii-turns
366            turn.discarded = true;
367            turn.cluster_id = -1;
368            continue;
369         }
370 
371         if (! turn.discarded
372             && turn.both(detail::overlay::operation_continue))
373         {
374             has_cc = true;
375         }
376     }
377 
378     detail::overlay::discard_closed_turns
379         <
380             OverlayType,
381             target_operation
382         >::apply(turns, geometry1, geometry2);
383     detail::overlay::discard_open_turns
384         <
385             OverlayType,
386             target_operation
387         >::apply(turns, geometry1, geometry2);
388 
389     // Create a map of vectors of indexed operation-types to be able
390     // to sort intersection points PER RING
391     mapped_vector_type mapped_vector;
392 
393     detail::overlay::create_map(turns, mapped_vector);
394 
395     // No const-iterator; contents of mapped copy is temporary,
396     // and changed by enrich
397     for (typename mapped_vector_type::iterator mit
398         = mapped_vector.begin();
399         mit != mapped_vector.end();
400         ++mit)
401     {
402 #ifdef BOOST_GEOMETRY_DEBUG_ENRICH
403     std::cout << "ENRICH-sort Ring "
404         << mit->first << std::endl;
405 #endif
406         detail::overlay::enrich_sort<Reverse1, Reverse2>(
407                     mit->second, turns, target_operation,
408                     geometry1, geometry2,
409                     robust_policy, strategy);
410     }
411 
412     for (typename mapped_vector_type::iterator mit
413         = mapped_vector.begin();
414         mit != mapped_vector.end();
415         ++mit)
416     {
417 #ifdef BOOST_GEOMETRY_DEBUG_ENRICH
418     std::cout << "ENRICH-assign Ring "
419         << mit->first << std::endl;
420 #endif
421         detail::overlay::enrich_assign(mit->second, turns);
422     }
423 
424     if (has_colocations)
425     {
426         // First gather cluster properties (using even clusters with
427         // discarded turns - for open turns), then clean up clusters
428         detail::overlay::gather_cluster_properties
429             <
430                 Reverse1,
431                 Reverse2,
432                 OverlayType
433             >(clusters, turns, target_operation,
434               geometry1, geometry2, strategy);
435 
436         detail::overlay::cleanup_clusters(turns, clusters);
437     }
438 
439     if (has_cc)
440     {
441         detail::overlay::calculate_remaining_distance(turns);
442     }
443 
444 #ifdef BOOST_GEOMETRY_DEBUG_ENRICH
445     //detail::overlay::check_graph(turns, for_operation);
446 #endif
447 
448 }
449 
450 }} // namespace boost::geometry
451 
452 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_ENRICH_HPP
453