1 // Boost.Geometry (aka GGL, Generic Geometry Library)
2 
3 // Copyright (c) 2015 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_HANDLE_COLOCATIONS_HPP
15 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_HANDLE_COLOCATIONS_HPP
16 
17 #include <cstddef>
18 #include <algorithm>
19 #include <map>
20 #include <vector>
21 
22 #include <boost/core/ignore_unused.hpp>
23 #include <boost/range.hpp>
24 #include <boost/geometry/core/point_order.hpp>
25 #include <boost/geometry/algorithms/detail/overlay/cluster_info.hpp>
26 #include <boost/geometry/algorithms/detail/overlay/do_reverse.hpp>
27 #include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp>
28 #include <boost/geometry/algorithms/detail/overlay/sort_by_side.hpp>
29 #include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
30 #include <boost/geometry/algorithms/detail/ring_identifier.hpp>
31 #include <boost/geometry/algorithms/detail/overlay/segment_identifier.hpp>
32 
33 #if defined(BOOST_GEOMETRY_DEBUG_HANDLE_COLOCATIONS)
34 #  include <iostream>
35 #  include <boost/geometry/algorithms/detail/overlay/debug_turn_info.hpp>
36 #  include <boost/geometry/io/wkt/wkt.hpp>
37 #  define BOOST_GEOMETRY_DEBUG_IDENTIFIER
38 #endif
39 
40 namespace boost { namespace geometry
41 {
42 
43 #ifndef DOXYGEN_NO_DETAIL
44 namespace detail { namespace overlay
45 {
46 
47 template <typename SegmentRatio>
48 struct segment_fraction
49 {
50     segment_identifier seg_id;
51     SegmentRatio fraction;
52 
segment_fractionboost::geometry::detail::overlay::segment_fraction53     segment_fraction(segment_identifier const& id, SegmentRatio const& fr)
54         : seg_id(id)
55         , fraction(fr)
56     {}
57 
segment_fractionboost::geometry::detail::overlay::segment_fraction58     segment_fraction()
59     {}
60 
operator <boost::geometry::detail::overlay::segment_fraction61     bool operator<(segment_fraction<SegmentRatio> const& other) const
62     {
63         return seg_id == other.seg_id
64                 ? fraction < other.fraction
65                 : seg_id < other.seg_id;
66     }
67 
68 };
69 
70 struct turn_operation_index
71 {
turn_operation_indexboost::geometry::detail::overlay::turn_operation_index72     turn_operation_index(signed_size_type ti = -1,
73                          signed_size_type oi = -1)
74         : turn_index(ti)
75         , op_index(oi)
76     {}
77 
78     signed_size_type turn_index;
79     signed_size_type op_index; // only 0,1
80 };
81 
82 
83 template <typename Turns>
84 struct less_by_fraction_and_type
85 {
less_by_fraction_and_typeboost::geometry::detail::overlay::less_by_fraction_and_type86     inline less_by_fraction_and_type(Turns const& turns)
87         : m_turns(turns)
88     {
89     }
90 
operator ()boost::geometry::detail::overlay::less_by_fraction_and_type91     inline bool operator()(turn_operation_index const& left,
92                            turn_operation_index const& right) const
93     {
94         typedef typename boost::range_value<Turns>::type turn_type;
95         typedef typename turn_type::turn_operation_type turn_operation_type;
96 
97         turn_type const& left_turn = m_turns[left.turn_index];
98         turn_type const& right_turn = m_turns[right.turn_index];
99         turn_operation_type const& left_op
100                 = left_turn.operations[left.op_index];
101 
102         turn_operation_type const& right_op
103                 = right_turn.operations[right.op_index];
104 
105         if (! (left_op.fraction == right_op.fraction))
106         {
107             return left_op.fraction < right_op.fraction;
108         }
109 
110         // Order xx first - used to discard any following colocated turn
111         bool const left_both_xx = left_turn.both(operation_blocked);
112         bool const right_both_xx = right_turn.both(operation_blocked);
113         if (left_both_xx && ! right_both_xx)
114         {
115             return true;
116         }
117         if (! left_both_xx && right_both_xx)
118         {
119             return false;
120         }
121 
122         bool const left_both_uu = left_turn.both(operation_union);
123         bool const right_both_uu = right_turn.both(operation_union);
124         if (left_both_uu && ! right_both_uu)
125         {
126             return true;
127         }
128         if (! left_both_uu && right_both_uu)
129         {
130             return false;
131         }
132 
133         turn_operation_type const& left_other_op
134                 = left_turn.operations[1 - left.op_index];
135 
136         turn_operation_type const& right_other_op
137                 = right_turn.operations[1 - right.op_index];
138 
139         // Fraction is the same, now sort on ring id, first outer ring,
140         // then interior rings
141         return left_other_op.seg_id < right_other_op.seg_id;
142     }
143 
144 private:
145     Turns const& m_turns;
146 };
147 
148 template <typename Operation, typename ClusterPerSegment>
get_cluster_id(Operation const & op,ClusterPerSegment const & cluster_per_segment)149 inline signed_size_type get_cluster_id(Operation const& op, ClusterPerSegment const& cluster_per_segment)
150 {
151     typedef typename ClusterPerSegment::key_type segment_fraction_type;
152 
153     segment_fraction_type seg_frac(op.seg_id, op.fraction);
154     typename ClusterPerSegment::const_iterator it
155             = cluster_per_segment.find(seg_frac);
156 
157     if (it == cluster_per_segment.end())
158     {
159         return -1;
160     }
161     return it->second;
162 }
163 
164 template <typename Operation, typename ClusterPerSegment>
add_cluster_id(Operation const & op,ClusterPerSegment & cluster_per_segment,signed_size_type id)165 inline void add_cluster_id(Operation const& op,
166     ClusterPerSegment& cluster_per_segment, signed_size_type id)
167 {
168     typedef typename ClusterPerSegment::key_type segment_fraction_type;
169 
170     segment_fraction_type seg_frac(op.seg_id, op.fraction);
171 
172     cluster_per_segment[seg_frac] = id;
173 }
174 
175 template <typename Turn, typename ClusterPerSegment>
add_turn_to_cluster(Turn const & turn,ClusterPerSegment & cluster_per_segment,signed_size_type & cluster_id)176 inline signed_size_type add_turn_to_cluster(Turn const& turn,
177         ClusterPerSegment& cluster_per_segment, signed_size_type& cluster_id)
178 {
179     signed_size_type cid0 = get_cluster_id(turn.operations[0], cluster_per_segment);
180     signed_size_type cid1 = get_cluster_id(turn.operations[1], cluster_per_segment);
181 
182     if (cid0 == -1 && cid1 == -1)
183     {
184         ++cluster_id;
185         add_cluster_id(turn.operations[0], cluster_per_segment, cluster_id);
186         add_cluster_id(turn.operations[1], cluster_per_segment, cluster_id);
187         return cluster_id;
188     }
189     else if (cid0 == -1 && cid1 != -1)
190     {
191         add_cluster_id(turn.operations[0], cluster_per_segment, cid1);
192         return cid1;
193     }
194     else if (cid0 != -1 && cid1 == -1)
195     {
196         add_cluster_id(turn.operations[1], cluster_per_segment, cid0);
197         return cid0;
198     }
199     else if (cid0 == cid1)
200     {
201         // Both already added to same cluster, no action
202         return cid0;
203     }
204 
205     // Both operations.seg_id/fraction were already part of any cluster, and
206     // these clusters are not the same. Merge of two clusters is necessary
207 #if defined(BOOST_GEOMETRY_DEBUG_HANDLE_COLOCATIONS)
208     std::cout << " TODO: merge " << cid0 << " and " << cid1 << std::endl;
209 #endif
210     return cid0;
211 }
212 
213 template
214 <
215     typename Turns,
216     typename ClusterPerSegment,
217     typename Operations,
218     typename Geometry1,
219     typename Geometry2
220 >
handle_colocation_cluster(Turns & turns,signed_size_type & cluster_id,ClusterPerSegment & cluster_per_segment,Operations const & operations,Geometry1 const &,Geometry2 const &)221 inline void handle_colocation_cluster(Turns& turns,
222         signed_size_type& cluster_id,
223         ClusterPerSegment& cluster_per_segment,
224         Operations const& operations,
225         Geometry1 const& /*geometry1*/, Geometry2 const& /*geometry2*/)
226 {
227     typedef typename boost::range_value<Turns>::type turn_type;
228     typedef typename turn_type::turn_operation_type turn_operation_type;
229 
230     std::vector<turn_operation_index>::const_iterator vit = operations.begin();
231 
232     turn_operation_index ref_toi = *vit;
233     signed_size_type ref_id = -1;
234 
235     for (++vit; vit != operations.end(); ++vit)
236     {
237         turn_type& ref_turn = turns[ref_toi.turn_index];
238         turn_operation_type const& ref_op
239                 = ref_turn.operations[ref_toi.op_index];
240 
241         turn_operation_index const& toi = *vit;
242         turn_type& turn = turns[toi.turn_index];
243         turn_operation_type const& op = turn.operations[toi.op_index];
244 
245         BOOST_ASSERT(ref_op.seg_id == op.seg_id);
246 
247         if (ref_op.fraction == op.fraction)
248         {
249             turn_operation_type const& other_op = turn.operations[1 - toi.op_index];
250 
251             if (ref_id == -1)
252             {
253                 ref_id = add_turn_to_cluster(ref_turn, cluster_per_segment, cluster_id);
254             }
255             BOOST_ASSERT(ref_id != -1);
256 
257             // ref_turn (both operations) are already added to cluster,
258             // so also "op" is already added to cluster,
259             // We only need to add other_op
260             signed_size_type id = get_cluster_id(other_op, cluster_per_segment);
261             if (id != -1 && id != ref_id)
262             {
263             }
264             else if (id == -1)
265             {
266                 // Add to same cluster
267                 add_cluster_id(other_op, cluster_per_segment, ref_id);
268                 id = ref_id;
269             }
270         }
271         else
272         {
273             // Not on same fraction on this segment
274             // assign for next
275             ref_toi = toi;
276             ref_id = -1;
277         }
278     }
279 }
280 
281 template
282 <
283     typename Turns,
284     typename Clusters,
285     typename ClusterPerSegment
286 >
assign_cluster_to_turns(Turns & turns,Clusters & clusters,ClusterPerSegment const & cluster_per_segment)287 inline void assign_cluster_to_turns(Turns& turns,
288         Clusters& clusters,
289         ClusterPerSegment const& cluster_per_segment)
290 {
291     typedef typename boost::range_value<Turns>::type turn_type;
292     typedef typename turn_type::turn_operation_type turn_operation_type;
293     typedef typename ClusterPerSegment::key_type segment_fraction_type;
294 
295     signed_size_type turn_index = 0;
296     for (typename boost::range_iterator<Turns>::type it = turns.begin();
297          it != turns.end(); ++it, ++turn_index)
298     {
299         turn_type& turn = *it;
300 
301         if (turn.discarded)
302         {
303             // They were processed (to create proper map) but will not be added
304             // This might leave a cluster with only 1 turn, which will be fixed
305             // afterwards
306             continue;
307         }
308 
309         for (int i = 0; i < 2; i++)
310         {
311             turn_operation_type const& op = turn.operations[i];
312             segment_fraction_type seg_frac(op.seg_id, op.fraction);
313             typename ClusterPerSegment::const_iterator it = cluster_per_segment.find(seg_frac);
314             if (it != cluster_per_segment.end())
315             {
316 #if defined(BOOST_GEOMETRY_DEBUG_HANDLE_COLOCATIONS)
317                 if (turn.cluster_id != -1
318                         && turn.cluster_id != it->second)
319                 {
320                     std::cout << " CONFLICT " << std::endl;
321                 }
322 #endif
323                 turn.cluster_id = it->second;
324                 clusters[turn.cluster_id].turn_indices.insert(turn_index);
325             }
326         }
327     }
328 }
329 
330 template <typename Turns, typename Clusters>
remove_clusters(Turns & turns,Clusters & clusters)331 inline void remove_clusters(Turns& turns, Clusters& clusters)
332 {
333     typename Clusters::iterator it = clusters.begin();
334     while (it != clusters.end())
335     {
336         // Hold iterator and increase. We can erase cit, this keeps the
337         // iterator valid (cf The standard associative-container erase idiom)
338         typename Clusters::iterator current_it = it;
339         ++it;
340 
341         std::set<signed_size_type> const& turn_indices
342                 = current_it->second.turn_indices;
343         if (turn_indices.size() == 1)
344         {
345             signed_size_type const turn_index = *turn_indices.begin();
346             turns[turn_index].cluster_id = -1;
347             clusters.erase(current_it);
348         }
349     }
350 }
351 
352 template <typename Turns, typename Clusters>
cleanup_clusters(Turns & turns,Clusters & clusters)353 inline void cleanup_clusters(Turns& turns, Clusters& clusters)
354 {
355     // Removes discarded turns from clusters
356     for (typename Clusters::iterator mit = clusters.begin();
357          mit != clusters.end(); ++mit)
358     {
359         cluster_info& cinfo = mit->second;
360         std::set<signed_size_type>& ids = cinfo.turn_indices;
361         for (std::set<signed_size_type>::iterator sit = ids.begin();
362              sit != ids.end(); /* no increment */)
363         {
364             std::set<signed_size_type>::iterator current_it = sit;
365             ++sit;
366 
367             signed_size_type const turn_index = *current_it;
368             if (turns[turn_index].discarded)
369             {
370                 ids.erase(current_it);
371             }
372         }
373     }
374 
375     remove_clusters(turns, clusters);
376 }
377 
378 template <typename Turn, typename IdSet>
discard_ie_turn(Turn & turn,IdSet & ids,signed_size_type id)379 inline void discard_ie_turn(Turn& turn, IdSet& ids, signed_size_type id)
380 {
381     turn.discarded = true;
382     // Set cluster id to -1, but don't clear colocated flags
383     turn.cluster_id = -1;
384     // To remove it later from clusters
385     ids.insert(id);
386 }
387 
388 template <bool Reverse>
is_interior(segment_identifier const & seg_id)389 inline bool is_interior(segment_identifier const& seg_id)
390 {
391     return Reverse ? seg_id.ring_index == -1 : seg_id.ring_index >= 0;
392 }
393 
394 template <bool Reverse0, bool Reverse1>
is_ie_turn(segment_identifier const & ext_seg_0,segment_identifier const & ext_seg_1,segment_identifier const & int_seg_0,segment_identifier const & other_seg_1)395 inline bool is_ie_turn(segment_identifier const& ext_seg_0,
396                        segment_identifier const& ext_seg_1,
397                        segment_identifier const& int_seg_0,
398                        segment_identifier const& other_seg_1)
399 {
400     if (ext_seg_0.source_index == ext_seg_1.source_index)
401     {
402         // External turn is a self-turn, dont discard internal turn for this
403         return false;
404     }
405 
406 
407     // Compares two segment identifiers from two turns (external / one internal)
408 
409     // From first turn [0], both are from same polygon (multi_index),
410     // one is exterior (-1), the other is interior (>= 0),
411     // and the second turn [1] handles the same ring
412 
413     // For difference, where the rings are processed in reversal, all interior
414     // rings become exterior and vice versa. But also the multi property changes:
415     // rings originally from the same multi should now be considered as from
416     // different multi polygons.
417     // But this is not always the case, and at this point hard to figure out
418     // (not yet implemented, TODO)
419 
420     bool const same_multi0 = ! Reverse0
421                              && ext_seg_0.multi_index == int_seg_0.multi_index;
422 
423     bool const same_multi1 = ! Reverse1
424                              && ext_seg_1.multi_index == other_seg_1.multi_index;
425 
426     boost::ignore_unused(same_multi1);
427 
428     return same_multi0
429             && same_multi1
430             && ! is_interior<Reverse0>(ext_seg_0)
431             && is_interior<Reverse0>(int_seg_0)
432             && ext_seg_1.ring_index == other_seg_1.ring_index;
433 
434     // The other way round is tested in another call
435 }
436 
437 template
438 <
439     bool Reverse0, bool Reverse1, // Reverse interpretation interior/exterior
440     overlay_type OverlayType,
441     typename Turns,
442     typename Clusters
443 >
discard_interior_exterior_turns(Turns & turns,Clusters & clusters)444 inline void discard_interior_exterior_turns(Turns& turns, Clusters& clusters)
445 {
446     typedef std::set<signed_size_type>::const_iterator set_iterator;
447     typedef typename boost::range_value<Turns>::type turn_type;
448 
449     std::set<signed_size_type> ids_to_remove;
450 
451     for (typename Clusters::iterator cit = clusters.begin();
452          cit != clusters.end(); ++cit)
453     {
454         cluster_info& cinfo = cit->second;
455         std::set<signed_size_type>& ids = cinfo.turn_indices;
456 
457         ids_to_remove.clear();
458 
459         for (set_iterator it = ids.begin(); it != ids.end(); ++it)
460         {
461             turn_type& turn = turns[*it];
462             segment_identifier const& seg_0 = turn.operations[0].seg_id;
463             segment_identifier const& seg_1 = turn.operations[1].seg_id;
464 
465             if (! (turn.both(operation_union)
466                    || turn.combination(operation_union, operation_blocked)))
467             {
468                 // Not a uu/ux, so cannot be colocated with a iu turn
469                 continue;
470             }
471 
472             for (set_iterator int_it = ids.begin(); int_it != ids.end(); ++int_it)
473             {
474                 if (*it == *int_it)
475                 {
476                     continue;
477                 }
478 
479                 // Turn with, possibly, an interior ring involved
480                 turn_type& int_turn = turns[*int_it];
481                 segment_identifier const& int_seg_0 = int_turn.operations[0].seg_id;
482                 segment_identifier const& int_seg_1 = int_turn.operations[1].seg_id;
483 
484                 if (is_ie_turn<Reverse0, Reverse1>(seg_0, seg_1, int_seg_0, int_seg_1))
485                 {
486                     discard_ie_turn(int_turn, ids_to_remove, *int_it);
487                 }
488                 if (is_ie_turn<Reverse1, Reverse0>(seg_1, seg_0, int_seg_1, int_seg_0))
489                 {
490                     discard_ie_turn(int_turn, ids_to_remove, *int_it);
491                 }
492             }
493         }
494 
495         // Erase from the ids (which cannot be done above)
496         for (set_iterator sit = ids_to_remove.begin();
497              sit != ids_to_remove.end(); ++sit)
498         {
499             ids.erase(*sit);
500         }
501     }
502 }
503 
504 template
505 <
506     typename Turns,
507     typename Clusters
508 >
set_colocation(Turns & turns,Clusters const & clusters)509 inline void set_colocation(Turns& turns, Clusters const& clusters)
510 {
511     typedef std::set<signed_size_type>::const_iterator set_iterator;
512     typedef typename boost::range_value<Turns>::type turn_type;
513 
514     for (typename Clusters::const_iterator cit = clusters.begin();
515          cit != clusters.end(); ++cit)
516     {
517         cluster_info const& cinfo = cit->second;
518         std::set<signed_size_type> const& ids = cinfo.turn_indices;
519 
520         bool has_ii = false;
521         bool has_uu = false;
522         for (set_iterator it = ids.begin(); it != ids.end(); ++it)
523         {
524             turn_type const& turn = turns[*it];
525             if (turn.both(operation_intersection))
526             {
527                 has_ii = true;
528             }
529             if (turn.both(operation_union) || turn.combination(operation_union, operation_blocked))
530             {
531                 has_uu = true;
532             }
533         }
534         if (has_ii || has_uu)
535         {
536             for (set_iterator it = ids.begin(); it != ids.end(); ++it)
537             {
538                 turn_type& turn = turns[*it];
539                 if (has_ii)
540                 {
541                     turn.colocated_ii = true;
542                 }
543                 if (has_uu)
544                 {
545                     turn.colocated_uu = true;
546                 }
547             }
548         }
549     }
550 }
551 
552 // Checks colocated turns and flags combinations of uu/other, possibly a
553 // combination of a ring touching another geometry's interior ring which is
554 // tangential to the exterior ring
555 
556 // This function can be extended to replace handle_tangencies: at each
557 // colocation incoming and outgoing vectors should be inspected
558 
559 template
560 <
561     bool Reverse1, bool Reverse2,
562     overlay_type OverlayType,
563     typename Turns,
564     typename Clusters,
565     typename Geometry1,
566     typename Geometry2
567 >
handle_colocations(Turns & turns,Clusters & clusters,Geometry1 const & geometry1,Geometry2 const & geometry2)568 inline bool handle_colocations(Turns& turns, Clusters& clusters,
569         Geometry1 const& geometry1, Geometry2 const& geometry2)
570 {
571     typedef std::map
572         <
573             segment_identifier,
574             std::vector<turn_operation_index>
575         > map_type;
576 
577     // Create and fill map on segment-identifier Map is sorted on seg_id,
578     // meaning it is sorted on ring_identifier too. This means that exterior
579     // rings are handled first. If there is a colocation on the exterior ring,
580     // that information can be used for the interior ring too
581     map_type map;
582 
583     int index = 0;
584     for (typename boost::range_iterator<Turns>::type
585             it = boost::begin(turns);
586          it != boost::end(turns);
587          ++it, ++index)
588     {
589         map[it->operations[0].seg_id].push_back(turn_operation_index(index, 0));
590         map[it->operations[1].seg_id].push_back(turn_operation_index(index, 1));
591     }
592 
593     // Check if there are multiple turns on one or more segments,
594     // if not then nothing is to be done
595     bool colocations = 0;
596     for (typename map_type::const_iterator it = map.begin();
597          it != map.end();
598          ++it)
599     {
600         if (it->second.size() > 1u)
601         {
602             colocations = true;
603             break;
604         }
605     }
606 
607     if (! colocations)
608     {
609         return false;
610     }
611 
612     // Sort all vectors, per same segment
613     less_by_fraction_and_type<Turns> less(turns);
614     for (typename map_type::iterator it = map.begin();
615          it != map.end(); ++it)
616     {
617         std::sort(it->second.begin(), it->second.end(), less);
618     }
619 
620     typedef typename boost::range_value<Turns>::type turn_type;
621     typedef typename turn_type::segment_ratio_type segment_ratio_type;
622 
623     typedef std::map
624         <
625             segment_fraction<segment_ratio_type>,
626             signed_size_type
627         > cluster_per_segment_type;
628 
629     cluster_per_segment_type cluster_per_segment;
630     signed_size_type cluster_id = 0;
631 
632     for (typename map_type::const_iterator it = map.begin();
633          it != map.end(); ++it)
634     {
635         if (it->second.size() > 1u)
636         {
637             handle_colocation_cluster(turns, cluster_id, cluster_per_segment,
638                 it->second, geometry1, geometry2);
639         }
640     }
641 
642     assign_cluster_to_turns(turns, clusters, cluster_per_segment);
643     set_colocation(turns, clusters);
644     discard_interior_exterior_turns
645         <
646             do_reverse<geometry::point_order<Geometry1>::value>::value != Reverse1,
647             do_reverse<geometry::point_order<Geometry2>::value>::value != Reverse2,
648             OverlayType
649         >(turns, clusters);
650 
651 #if defined(BOOST_GEOMETRY_DEBUG_HANDLE_COLOCATIONS)
652     std::cout << "*** Colocations " << map.size() << std::endl;
653     for (typename map_type::const_iterator it = map.begin();
654          it != map.end(); ++it)
655     {
656         std::cout << it->first << std::endl;
657         for (std::vector<turn_operation_index>::const_iterator vit
658              = it->second.begin(); vit != it->second.end(); ++vit)
659         {
660             turn_operation_index const& toi = *vit;
661             std::cout << geometry::wkt(turns[toi.turn_index].point)
662                 << std::boolalpha
663                 << " discarded=" << turns[toi.turn_index].discarded
664                 << " colocated(uu)=" << turns[toi.turn_index].colocated_uu
665                 << " colocated(ii)=" << turns[toi.turn_index].colocated_ii
666                 << " " << operation_char(turns[toi.turn_index].operations[0].operation)
667                 << " "  << turns[toi.turn_index].operations[0].seg_id
668                 << " "  << turns[toi.turn_index].operations[0].fraction
669                 << " // " << operation_char(turns[toi.turn_index].operations[1].operation)
670                 << " "  << turns[toi.turn_index].operations[1].seg_id
671                 << " "  << turns[toi.turn_index].operations[1].fraction
672                 << std::endl;
673         }
674     }
675 #endif // DEBUG
676 
677     return true;
678 }
679 
680 
681 struct is_turn_index
682 {
is_turn_indexboost::geometry::detail::overlay::is_turn_index683     is_turn_index(signed_size_type index)
684         : m_index(index)
685     {}
686 
687     template <typename Indexed>
operator ()boost::geometry::detail::overlay::is_turn_index688     inline bool operator()(Indexed const& indexed) const
689     {
690         // Indexed is a indexed_turn_operation<Operation>
691         return indexed.turn_index == m_index;
692     }
693 
694     std::size_t m_index;
695 };
696 
697 
698 template
699 <
700     bool Reverse1, bool Reverse2,
701     overlay_type OverlayType,
702     typename Turns,
703     typename Clusters,
704     typename Geometry1,
705     typename Geometry2,
706     typename SideStrategy
707 >
gather_cluster_properties(Clusters & clusters,Turns & turns,operation_type for_operation,Geometry1 const & geometry1,Geometry2 const & geometry2,SideStrategy const & strategy)708 inline void gather_cluster_properties(Clusters& clusters, Turns& turns,
709         operation_type for_operation,
710         Geometry1 const& geometry1, Geometry2 const& geometry2,
711         SideStrategy const& strategy)
712 {
713     typedef typename boost::range_value<Turns>::type turn_type;
714     typedef typename turn_type::point_type point_type;
715     typedef typename turn_type::turn_operation_type turn_operation_type;
716 
717     // Define sorter, sorting counter-clockwise such that polygons are on the
718     // right side
719     typedef sort_by_side::side_sorter
720         <
721             Reverse1, Reverse2, OverlayType, point_type, SideStrategy, std::less<int>
722         > sbs_type;
723 
724     for (typename Clusters::iterator mit = clusters.begin();
725          mit != clusters.end(); ++mit)
726     {
727         cluster_info& cinfo = mit->second;
728         std::set<signed_size_type> const& ids = cinfo.turn_indices;
729         if (ids.empty())
730         {
731             continue;
732         }
733 
734         sbs_type sbs(strategy);
735         point_type turn_point; // should be all the same for all turns in cluster
736 
737         bool first = true;
738         for (std::set<signed_size_type>::const_iterator sit = ids.begin();
739              sit != ids.end(); ++sit)
740         {
741             signed_size_type turn_index = *sit;
742             turn_type const& turn = turns[turn_index];
743             if (first)
744             {
745                 turn_point = turn.point;
746             }
747             for (int i = 0; i < 2; i++)
748             {
749                 turn_operation_type const& op = turn.operations[i];
750                 sbs.add(op, turn_index, i, geometry1, geometry2, first);
751                 first = false;
752             }
753         }
754         sbs.apply(turn_point);
755 
756         sbs.find_open();
757         sbs.assign_zones(for_operation);
758 
759         cinfo.open_count = sbs.open_count(for_operation);
760 
761         // Unset the startable flag for all 'closed' zones
762         for (std::size_t i = 0; i < sbs.m_ranked_points.size(); i++)
763         {
764             const typename sbs_type::rp& ranked = sbs.m_ranked_points[i];
765             turn_type& turn = turns[ranked.turn_index];
766             turn_operation_type& op = turn.operations[ranked.operation_index];
767 
768             if (for_operation == operation_union && cinfo.open_count == 0)
769             {
770                 op.enriched.startable = false;
771             }
772 
773             if (ranked.direction != sort_by_side::dir_to)
774             {
775                 continue;
776             }
777 
778             op.enriched.count_left = ranked.count_left;
779             op.enriched.count_right = ranked.count_right;
780             op.enriched.rank = ranked.rank;
781             op.enriched.zone = ranked.zone;
782 
783             if ((for_operation == operation_union
784                     && ranked.count_left != 0)
785              || (for_operation == operation_intersection
786                     && ranked.count_right != 2))
787             {
788                 op.enriched.startable = false;
789             }
790         }
791 
792     }
793 }
794 
795 
796 }} // namespace detail::overlay
797 #endif //DOXYGEN_NO_DETAIL
798 
799 
800 }} // namespace boost::geometry
801 
802 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_HANDLE_COLOCATIONS_HPP
803