1 // Boost.Geometry (aka GGL, Generic Geometry Library)
3 // Copyright (c) 2015 Barend Gehrels, Amsterdam, the Netherlands.
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)
9 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_HANDLE_COLOCATIONS_HPP
10 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_HANDLE_COLOCATIONS_HPP
17 #include <boost/range.hpp>
18 #include <boost/geometry/core/point_order.hpp>
19 #include <boost/geometry/algorithms/detail/overlay/cluster_info.hpp>
20 #include <boost/geometry/algorithms/detail/overlay/do_reverse.hpp>
21 #include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp>
22 #include <boost/geometry/algorithms/detail/overlay/sort_by_side.hpp>
23 #include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
24 #include <boost/geometry/algorithms/detail/ring_identifier.hpp>
25 #include <boost/geometry/algorithms/detail/overlay/segment_identifier.hpp>
27 #if defined(BOOST_GEOMETRY_DEBUG_HANDLE_COLOCATIONS)
29 # include <boost/geometry/algorithms/detail/overlay/debug_turn_info.hpp>
30 # include <boost/geometry/io/wkt/wkt.hpp>
31 # define BOOST_GEOMETRY_DEBUG_IDENTIFIER
34 namespace boost { namespace geometry
37 #ifndef DOXYGEN_NO_DETAIL
38 namespace detail { namespace overlay
41 template <typename SegmentRatio>
42 struct segment_fraction
44 segment_identifier seg_id;
45 SegmentRatio fraction;
47 segment_fraction(segment_identifier const& id, SegmentRatio const& fr)
55 bool operator<(segment_fraction<SegmentRatio> const& other) const
57 return seg_id == other.seg_id
58 ? fraction < other.fraction
59 : seg_id < other.seg_id;
64 struct turn_operation_index
66 turn_operation_index(signed_size_type ti = -1,
67 signed_size_type oi = -1)
72 signed_size_type turn_index;
73 signed_size_type op_index; // only 0,1
77 template <typename Turns>
78 struct less_by_fraction_and_type
80 inline less_by_fraction_and_type(Turns const& turns)
85 inline bool operator()(turn_operation_index const& left,
86 turn_operation_index const& right) const
88 typedef typename boost::range_value<Turns>::type turn_type;
89 typedef typename turn_type::turn_operation_type turn_operation_type;
91 turn_type const& left_turn = m_turns[left.turn_index];
92 turn_type const& right_turn = m_turns[right.turn_index];
93 turn_operation_type const& left_op
94 = left_turn.operations[left.op_index];
96 turn_operation_type const& right_op
97 = right_turn.operations[right.op_index];
99 if (! (left_op.fraction == right_op.fraction))
101 return left_op.fraction < right_op.fraction;
104 // Order xx first - used to discard any following colocated turn
105 bool const left_both_xx = left_turn.both(operation_blocked);
106 bool const right_both_xx = right_turn.both(operation_blocked);
107 if (left_both_xx && ! right_both_xx)
111 if (! left_both_xx && right_both_xx)
116 bool const left_both_uu = left_turn.both(operation_union);
117 bool const right_both_uu = right_turn.both(operation_union);
118 if (left_both_uu && ! right_both_uu)
122 if (! left_both_uu && right_both_uu)
127 turn_operation_type const& left_other_op
128 = left_turn.operations[1 - left.op_index];
130 turn_operation_type const& right_other_op
131 = right_turn.operations[1 - right.op_index];
133 // Fraction is the same, now sort on ring id, first outer ring,
134 // then interior rings
135 return left_other_op.seg_id < right_other_op.seg_id;
139 Turns const& m_turns;
142 template <typename Operation, typename ClusterPerSegment>
143 inline signed_size_type get_cluster_id(Operation const& op, ClusterPerSegment const& cluster_per_segment)
145 typedef typename ClusterPerSegment::key_type segment_fraction_type;
147 segment_fraction_type seg_frac(op.seg_id, op.fraction);
148 typename ClusterPerSegment::const_iterator it
149 = cluster_per_segment.find(seg_frac);
151 if (it == cluster_per_segment.end())
158 template <typename Operation, typename ClusterPerSegment>
159 inline void add_cluster_id(Operation const& op,
160 ClusterPerSegment& cluster_per_segment, signed_size_type id)
162 typedef typename ClusterPerSegment::key_type segment_fraction_type;
164 segment_fraction_type seg_frac(op.seg_id, op.fraction);
166 cluster_per_segment[seg_frac] = id;
169 template <typename Turn, typename ClusterPerSegment>
170 inline signed_size_type add_turn_to_cluster(Turn const& turn,
171 ClusterPerSegment& cluster_per_segment, signed_size_type& cluster_id)
173 signed_size_type cid0 = get_cluster_id(turn.operations[0], cluster_per_segment);
174 signed_size_type cid1 = get_cluster_id(turn.operations[1], cluster_per_segment);
176 if (cid0 == -1 && cid1 == -1)
179 add_cluster_id(turn.operations[0], cluster_per_segment, cluster_id);
180 add_cluster_id(turn.operations[1], cluster_per_segment, cluster_id);
183 else if (cid0 == -1 && cid1 != -1)
185 add_cluster_id(turn.operations[0], cluster_per_segment, cid1);
188 else if (cid0 != -1 && cid1 == -1)
190 add_cluster_id(turn.operations[1], cluster_per_segment, cid0);
193 else if (cid0 == cid1)
195 // Both already added to same cluster, no action
199 // Both operations.seg_id/fraction were already part of any cluster, and
200 // these clusters are not the same. Merge of two clusters is necessary
201 std::cout << " TODO: merge " << cid0 << " and " << cid1 << std::endl;
208 typename ClusterPerSegment,
213 inline void handle_colocation_cluster(Turns& turns,
214 signed_size_type& cluster_id,
215 ClusterPerSegment& cluster_per_segment,
216 Operations const& operations,
217 Geometry1 const& /*geometry1*/, Geometry2 const& /*geometry2*/)
219 typedef typename boost::range_value<Turns>::type turn_type;
220 typedef typename turn_type::turn_operation_type turn_operation_type;
222 std::vector<turn_operation_index>::const_iterator vit = operations.begin();
224 turn_operation_index ref_toi = *vit;
225 signed_size_type ref_id = -1;
227 for (++vit; vit != operations.end(); ++vit)
229 turn_type& ref_turn = turns[ref_toi.turn_index];
230 turn_operation_type const& ref_op
231 = ref_turn.operations[ref_toi.op_index];
233 turn_operation_index const& toi = *vit;
234 turn_type& turn = turns[toi.turn_index];
235 turn_operation_type const& op = turn.operations[toi.op_index];
237 BOOST_ASSERT(ref_op.seg_id == op.seg_id);
239 if (ref_op.fraction == op.fraction)
241 turn_operation_type const& other_op = turn.operations[1 - toi.op_index];
245 ref_id = add_turn_to_cluster(ref_turn, cluster_per_segment, cluster_id);
247 BOOST_ASSERT(ref_id != -1);
249 // ref_turn (both operations) are already added to cluster,
250 // so also "op" is already added to cluster,
251 // We only need to add other_op
252 signed_size_type id = get_cluster_id(other_op, cluster_per_segment);
253 if (id != -1 && id != ref_id)
258 // Add to same cluster
259 add_cluster_id(other_op, cluster_per_segment, ref_id);
263 // In case of colocated xx turns, all other turns may NOT be
264 // followed at all. xx cannot be discarded (otherwise colocated
265 // turns are followed).
266 if (ref_turn.both(operation_blocked))
268 turn.discarded = true;
269 // We can either set or not set colocated because it is not effective on blocked turns
274 // Not on same fraction on this segment
286 typename ClusterPerSegment
288 inline void assign_cluster_to_turns(Turns& turns,
290 ClusterPerSegment const& cluster_per_segment)
292 typedef typename boost::range_value<Turns>::type turn_type;
293 typedef typename turn_type::turn_operation_type turn_operation_type;
294 typedef typename ClusterPerSegment::key_type segment_fraction_type;
296 signed_size_type turn_index = 0;
297 for (typename boost::range_iterator<Turns>::type it = turns.begin();
298 it != turns.end(); ++it, ++turn_index)
300 turn_type& turn = *it;
304 // They were processed (to create proper map) but will not be added
305 // This might leave a cluster with only 1 turn, which will be fixed
310 for (int i = 0; i < 2; i++)
312 turn_operation_type const& op = turn.operations[i];
313 segment_fraction_type seg_frac(op.seg_id, op.fraction);
314 typename ClusterPerSegment::const_iterator it = cluster_per_segment.find(seg_frac);
315 if (it != cluster_per_segment.end())
317 if (turn.cluster_id != -1
318 && turn.cluster_id != it->second)
320 std::cout << " CONFLICT " << std::endl;
322 turn.cluster_id = it->second;
323 clusters[turn.cluster_id].turn_indices.insert(turn_index);
334 inline void remove_clusters(Turns& turns, Clusters& clusters)
336 typename Clusters::iterator it = clusters.begin();
337 while (it != clusters.end())
339 // Hold iterator and increase. We can erase cit, this keeps the
340 // iterator valid (cf The standard associative-container erase idiom)
341 typename Clusters::iterator current_it = it;
344 std::set<signed_size_type> const& turn_indices
345 = current_it->second.turn_indices;
346 if (turn_indices.size() == 1)
348 signed_size_type turn_index = *turn_indices.begin();
349 turns[turn_index].cluster_id = -1;
350 clusters.erase(current_it);
355 template <typename Turn, typename IdSet>
356 inline void discard_ie_turn(Turn& turn, IdSet& ids, signed_size_type id)
358 turn.discarded = true;
359 turn.cluster_id = -1;
360 // To remove it later from clusters
364 template <bool Reverse>
365 inline bool is_interior(segment_identifier const& seg_id)
367 return Reverse ? seg_id.ring_index == -1 : seg_id.ring_index >= 0;
370 template <bool Reverse0, bool Reverse1>
371 inline bool is_ie_turn(segment_identifier const& ext_seg_0,
372 segment_identifier const& ext_seg_1,
373 segment_identifier const& int_seg_0,
374 segment_identifier const& other_seg_1)
376 // Compares two segment identifiers from two turns (external / one internal)
378 // From first turn [0], both are from same polygon (multi_index),
379 // one is exterior (-1), the other is interior (>= 0),
380 // and the second turn [1] handles the same ring
382 // For difference, where the rings are processed in reversal, all interior
383 // rings become exterior and vice versa. But also the multi property changes:
384 // rings originally from the same multi should now be considered as from
385 // different multi polygons.
386 // But this is not always the case, and at this point hard to figure out
387 // (not yet implemented, TODO)
389 bool const same_multi0 = ! Reverse0
390 && ext_seg_0.multi_index == int_seg_0.multi_index;
392 bool const same_multi1 = ! Reverse1
393 && ext_seg_1.multi_index == other_seg_1.multi_index;
397 && ! is_interior<Reverse0>(ext_seg_0)
398 && is_interior<Reverse0>(int_seg_0)
399 && ext_seg_1.ring_index == other_seg_1.ring_index;
401 // The other way round is tested in another call
406 bool Reverse0, bool Reverse1, // Reverse interpretation interior/exterior
410 inline void discard_interior_exterior_turns(Turns& turns, Clusters& clusters)
412 typedef std::set<signed_size_type>::const_iterator set_iterator;
413 typedef typename boost::range_value<Turns>::type turn_type;
415 std::set<signed_size_type> ids_to_remove;
417 for (typename Clusters::iterator cit = clusters.begin();
418 cit != clusters.end(); ++cit)
420 cluster_info& cinfo = cit->second;
421 std::set<signed_size_type>& ids = cinfo.turn_indices;
423 ids_to_remove.clear();
425 for (set_iterator it = ids.begin(); it != ids.end(); ++it)
427 turn_type& turn = turns[*it];
428 segment_identifier const& seg_0 = turn.operations[0].seg_id;
429 segment_identifier const& seg_1 = turn.operations[1].seg_id;
431 if (turn.both(operation_intersection)
432 && Reverse0 == Reverse1)
434 if ( is_interior<Reverse0>(seg_0)
435 && is_interior<Reverse1>(seg_1))
437 // ii touch with, two interior rings
438 discard_ie_turn(turn, ids_to_remove, *it);
444 if (! (turn.both(operation_union)
445 || turn.combination(operation_union, operation_blocked)))
447 // Not a uu/ux, so cannot be colocated with a iu turn
451 for (set_iterator int_it = ids.begin(); int_it != ids.end(); ++int_it)
458 // Turn with, possibly, an interior ring involved
459 turn_type& int_turn = turns[*int_it];
460 segment_identifier const& int_seg_0 = int_turn.operations[0].seg_id;
461 segment_identifier const& int_seg_1 = int_turn.operations[1].seg_id;
463 if (is_ie_turn<Reverse0, Reverse1>(seg_0, seg_1, int_seg_0, int_seg_1))
465 discard_ie_turn(int_turn, ids_to_remove, *int_it);
467 if (is_ie_turn<Reverse1, Reverse0>(seg_1, seg_0, int_seg_1, int_seg_0))
469 discard_ie_turn(int_turn, ids_to_remove, *int_it);
474 // Erase from the ids (which cannot be done above)
475 for (set_iterator sit = ids_to_remove.begin();
476 sit != ids_to_remove.end(); ++sit)
484 // Checks colocated turns and flags combinations of uu/other, possibly a
485 // combination of a ring touching another geometry's interior ring which is
486 // tangential to the exterior ring
488 // This function can be extended to replace handle_tangencies: at each
489 // colocation incoming and outgoing vectors should be inspected
493 bool Reverse1, bool Reverse2,
499 inline bool handle_colocations(Turns& turns, Clusters& clusters,
500 Geometry1 const& geometry1, Geometry2 const& geometry2)
505 std::vector<turn_operation_index>
508 // Create and fill map on segment-identifier Map is sorted on seg_id,
509 // meaning it is sorted on ring_identifier too. This means that exterior
510 // rings are handled first. If there is a colocation on the exterior ring,
511 // that information can be used for the interior ring too
515 for (typename boost::range_iterator<Turns>::type
516 it = boost::begin(turns);
517 it != boost::end(turns);
520 map[it->operations[0].seg_id].push_back(turn_operation_index(index, 0));
521 map[it->operations[1].seg_id].push_back(turn_operation_index(index, 1));
524 // Check if there are multiple turns on one or more segments,
525 // if not then nothing is to be done
526 bool colocations = 0;
527 for (typename map_type::const_iterator it = map.begin();
531 if (it->second.size() > 1u)
543 // Sort all vectors, per same segment
544 less_by_fraction_and_type<Turns> less(turns);
545 for (typename map_type::iterator it = map.begin();
546 it != map.end(); ++it)
548 std::sort(it->second.begin(), it->second.end(), less);
551 typedef typename boost::range_value<Turns>::type turn_type;
552 typedef typename turn_type::segment_ratio_type segment_ratio_type;
556 segment_fraction<segment_ratio_type>,
558 > cluster_per_segment_type;
560 cluster_per_segment_type cluster_per_segment;
561 signed_size_type cluster_id = 0;
563 for (typename map_type::const_iterator it = map.begin();
564 it != map.end(); ++it)
566 if (it->second.size() > 1u)
568 handle_colocation_cluster(turns, cluster_id, cluster_per_segment,
569 it->second, geometry1, geometry2);
573 assign_cluster_to_turns(turns, clusters, cluster_per_segment);
574 discard_interior_exterior_turns
576 do_reverse<geometry::point_order<Geometry1>::value>::value != Reverse1,
577 do_reverse<geometry::point_order<Geometry2>::value>::value != Reverse2
579 remove_clusters(turns, clusters);
581 #if defined(BOOST_GEOMETRY_DEBUG_HANDLE_COLOCATIONS)
582 std::cout << "*** Colocations " << map.size() << std::endl;
583 for (typename map_type::const_iterator it = map.begin();
584 it != map.end(); ++it)
586 std::cout << it->first << std::endl;
587 for (std::vector<turn_operation_index>::const_iterator vit
588 = it->second.begin(); vit != it->second.end(); ++vit)
590 turn_operation_index const& toi = *vit;
591 std::cout << geometry::wkt(turns[toi.turn_index].point)
593 << " discarded=" << turns[toi.turn_index].discarded
594 << " colocated=" << turns[toi.turn_index].colocated
595 << " " << operation_char(turns[toi.turn_index].operations[0].operation)
596 << " " << turns[toi.turn_index].operations[0].seg_id
597 << " " << turns[toi.turn_index].operations[0].fraction
598 << " // " << operation_char(turns[toi.turn_index].operations[1].operation)
599 << " " << turns[toi.turn_index].operations[1].seg_id
600 << " " << turns[toi.turn_index].operations[1].fraction
612 is_turn_index(signed_size_type index)
616 template <typename Indexed>
617 inline bool operator()(Indexed const& indexed) const
619 // Indexed is a indexed_turn_operation<Operation>
620 return indexed.turn_index == m_index;
629 bool Reverse1, bool Reverse2,
635 inline void gather_cluster_properties(Clusters& clusters, Turns& turns,
636 operation_type for_operation,
637 Geometry1 const& geometry1, Geometry2 const& geometry2)
639 typedef typename boost::range_value<Turns>::type turn_type;
640 typedef typename turn_type::point_type point_type;
641 typedef typename turn_type::turn_operation_type turn_operation_type;
643 // Define sorter, sorting counter-clockwise such that polygons are on the
645 typedef sort_by_side::side_sorter
647 Reverse1, Reverse2, point_type, std::less<int>
650 for (typename Clusters::iterator mit = clusters.begin();
651 mit != clusters.end(); ++mit)
653 cluster_info& cinfo = mit->second;
654 std::set<signed_size_type> const& ids = cinfo.turn_indices;
661 point_type turn_point; // should be all the same for all turns in cluster
664 for (typename std::set<signed_size_type>::const_iterator sit = ids.begin();
665 sit != ids.end(); ++sit)
667 signed_size_type turn_index = *sit;
668 turn_type const& turn = turns[turn_index];
671 turn_point = turn.point;
673 for (int i = 0; i < 2; i++)
675 turn_operation_type const& op = turn.operations[i];
676 sbs.add(op, turn_index, i, geometry1, geometry2, first);
680 sbs.apply(turn_point);
684 // Unset the startable flag for all 'closed' zones
685 for (std::size_t i = 0; i < sbs.m_ranked_points.size(); i++)
687 const typename sbs_type::rp& ranked = sbs.m_ranked_points[i];
688 turn_type& turn = turns[ranked.turn_index];
689 turn_operation_type& op = turn.operations[ranked.operation_index];
691 if (ranked.direction != sort_by_side::dir_to)
696 op.enriched.count_left = ranked.count_left;
697 op.enriched.count_right = ranked.count_right;
698 op.enriched.zone = ranked.zone;
700 if ((for_operation == operation_union
701 && ranked.count_left != 0)
702 || (for_operation == operation_intersection
703 && ranked.count_right != 2))
705 op.enriched.startable = false;
709 cinfo.open_count = sbs.open_count(turns);
714 }} // namespace detail::overlay
715 #endif //DOXYGEN_NO_DETAIL
718 }} // namespace boost::geometry
720 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_HANDLE_COLOCATIONS_HPP