boost/geometry/algorithms/detail/overlay/handle_colocations.hpp

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