detail/overlay/handle_colocations.hpp

0001 // Boost.Geometry (aka GGL, Generic Geometry Library)
0002
0003 // Copyright (c) 2015 Barend Gehrels, Amsterdam, the Netherlands.
0004 // Copyright (c) 2017-2023 Adam Wulkiewicz, Lodz, Poland.
0005
0006 // This file was modified by Oracle on 2017-2020.
0007 // Modifications copyright (c) 2017-2020 Oracle and/or its affiliates.
0008 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
0009
0010 // Use, modification and distribution is subject to the Boost Software License,
0011 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0012 // http://www.boost.org/LICENSE_1_0.txt)
0013
0014 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_HANDLE_COLOCATIONS_HPP
0015 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_HANDLE_COLOCATIONS_HPP
0016
0017 #include <cstddef>
0018 #include <algorithm>
0019 #include <map>
0020 #include <vector>
0021
0022 #include <boost/core/ignore_unused.hpp>
0023 #include <boost/range/begin.hpp>
0024 #include <boost/range/end.hpp>
0025 #include <boost/range/value_type.hpp>
0026
0027 #include <boost/geometry/core/assert.hpp>
0028 #include <boost/geometry/core/point_order.hpp>
0029 #include <boost/geometry/algorithms/detail/overlay/cluster_info.hpp>
0030 #include <boost/geometry/algorithms/detail/overlay/do_reverse.hpp>
0031 #include <boost/geometry/algorithms/detail/overlay/colocate_clusters.hpp>
0032 #include <boost/geometry/algorithms/detail/overlay/get_clusters.hpp>
0033 #include <boost/geometry/algorithms/detail/overlay/get_ring.hpp>
0034 #include <boost/geometry/algorithms/detail/overlay/is_self_turn.hpp>
0035 #include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp>
0036 #include <boost/geometry/algorithms/detail/overlay/sort_by_side.hpp>
0037 #include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
0038 #include <boost/geometry/algorithms/detail/overlay/segment_identifier.hpp>
0039 #include <boost/geometry/util/constexpr.hpp>
0040
0041 #if defined(BOOST_GEOMETRY_DEBUG_HANDLE_COLOCATIONS)
0042 #  include <iostream>
0043 #  include <boost/geometry/algorithms/detail/overlay/debug_turn_info.hpp>
0044 #  include <boost/geometry/io/wkt/wkt.hpp>
0045 #  define BOOST_GEOMETRY_DEBUG_IDENTIFIER
0046 #endif
0047
0048 namespace boost { namespace geometry
0049 {
0050
0051 #ifndef DOXYGEN_NO_DETAIL
0052 namespace detail { namespace overlay
0053 {
0054
0055 // Removes clusters which have only one point left, or are empty.
0056 template <typename Turns, typename Clusters>
0057 inline void remove_clusters(Turns& turns, Clusters& clusters)
0058 {
0059     auto it = clusters.begin();
0060     while (it != clusters.end())
0061     {
0062         // Hold iterator and increase. We can erase cit, this keeps the
0063         // iterator valid (cf The standard associative-container erase idiom)
0064         auto current_it = it;
0065         ++it;
0066
0067         auto const& turn_indices = current_it->second.turn_indices;
0068         if (turn_indices.size() == 1)
0069         {
0070             auto const turn_index = *turn_indices.begin();
0071             turns[turn_index].cluster_id = -1;
0072             clusters.erase(current_it);
0073         }
0074     }
0075 }
0076
0077 template <typename Turns, typename Clusters>
0078 inline void cleanup_clusters(Turns& turns, Clusters& clusters)
0079 {
0080     // Removes discarded turns from clusters
0081     for (auto& pair : clusters)
0082     {
0083         auto& cinfo = pair.second;
0084         auto& indices = cinfo.turn_indices;
0085         for (auto sit = indices.begin(); sit != indices.end(); /* no increment */)
0086         {
0087             auto current_it = sit;
0088             ++sit;
0089
0090             auto const turn_index = *current_it;
0091             if (turns[turn_index].discarded)
0092             {
0093                 indices.erase(current_it);
0094             }
0095         }
0096     }
0097
0098     remove_clusters(turns, clusters);
0099 }
0100
0101 template <typename Turn, typename IndexSet>
0102 inline void discard_colocated_turn(Turn& turn, IndexSet& indices, signed_size_type index)
0103 {
0104     turn.discarded = true;
0105     // Set cluster id to -1, but don't clear colocated flags
0106     turn.cluster_id = -1;
0107     // To remove it later from clusters
0108     indices.insert(index);
0109 }
0110
0111 template <bool Reverse>
0112 inline bool is_interior(segment_identifier const& seg_id)
0113 {
0114     return Reverse ? seg_id.ring_index == -1 : seg_id.ring_index >= 0;
0115 }
0116
0117 template <bool Reverse0, bool Reverse1>
0118 inline bool is_ie_turn(segment_identifier const& ext_seg_0,
0119                        segment_identifier const& ext_seg_1,
0120                        segment_identifier const& int_seg_0,
0121                        segment_identifier const& other_seg_1)
0122 {
0123     if (ext_seg_0.source_index == ext_seg_1.source_index)
0124     {
0125         // External turn is a self-turn, dont discard internal turn for this
0126         return false;
0127     }
0128
0129
0130     // Compares two segment identifiers from two turns (external / one internal)
0131
0132     // From first turn [0], both are from same polygon (multi_index),
0133     // one is exterior (-1), the other is interior (>= 0),
0134     // and the second turn [1] handles the same ring
0135
0136     // For difference, where the rings are processed in reversal, all interior
0137     // rings become exterior and vice versa. But also the multi property changes:
0138     // rings originally from the same multi should now be considered as from
0139     // different multi polygons.
0140     // But this is not always the case, and at this point hard to figure out
0141     // (not yet implemented, TODO)
0142
0143     bool const same_multi0 = ! Reverse0
0144                              && ext_seg_0.multi_index == int_seg_0.multi_index;
0145
0146     bool const same_multi1 = ! Reverse1
0147                              && ext_seg_1.multi_index == other_seg_1.multi_index;
0148
0149     boost::ignore_unused(same_multi1);
0150
0151     return same_multi0
0152             && same_multi1
0153             && ! is_interior<Reverse0>(ext_seg_0)
0154             && is_interior<Reverse0>(int_seg_0)
0155             && ext_seg_1.ring_index == other_seg_1.ring_index;
0156
0157     // The other way round is tested in another call
0158 }
0159
0160 template
0161 <
0162     bool Reverse0, bool Reverse1, // Reverse interpretation interior/exterior
0163     typename Turns,
0164     typename Clusters
0165 >
0166 inline void discard_interior_exterior_turns(Turns& turns, Clusters& clusters)
0167 {
0168     std::set<signed_size_type> indices_to_remove;
0169
0170     for (auto& pair : clusters)
0171     {
0172         cluster_info& cinfo = pair.second;
0173
0174         indices_to_remove.clear();
0175
0176         for (auto index : cinfo.turn_indices)
0177         {
0178             auto& turn = turns[index];
0179             segment_identifier const& seg_0 = turn.operations[0].seg_id;
0180             segment_identifier const& seg_1 = turn.operations[1].seg_id;
0181
0182             if (! (turn.both(operation_union)
0183                    || turn.combination(operation_union, operation_blocked)))
0184             {
0185                 // Not a uu/ux, so cannot be colocated with a iu turn
0186                 continue;
0187             }
0188
0189             for (auto interior_index : cinfo.turn_indices)
0190             {
0191                 if (index == interior_index)
0192                 {
0193                     continue;
0194                 }
0195
0196                 // Turn with, possibly, an interior ring involved
0197                 auto& interior_turn = turns[interior_index];
0198                 segment_identifier const& int_seg_0 = interior_turn.operations[0].seg_id;
0199                 segment_identifier const& int_seg_1 = interior_turn.operations[1].seg_id;
0200
0201                 if (is_ie_turn<Reverse0, Reverse1>(seg_0, seg_1, int_seg_0, int_seg_1))
0202                 {
0203                     discard_colocated_turn(interior_turn, indices_to_remove, interior_index);
0204                 }
0205                 if (is_ie_turn<Reverse1, Reverse0>(seg_1, seg_0, int_seg_1, int_seg_0))
0206                 {
0207                     discard_colocated_turn(interior_turn, indices_to_remove, interior_index);
0208                 }
0209             }
0210         }
0211
0212         // Erase from the indices (which cannot be done above)
0213         for (auto index : indices_to_remove)
0214         {
0215             cinfo.turn_indices.erase(index);
0216         }
0217     }
0218 }
0219
0220 template
0221 <
0222     overlay_type OverlayType,
0223     typename Turns,
0224     typename Clusters
0225 >
0226 inline void set_colocation(Turns& turns, Clusters const& clusters)
0227 {
0228     for (auto const& pair : clusters)
0229     {
0230         cluster_info const& cinfo = pair.second;
0231
0232         bool both_target = false;
0233         for (auto index : cinfo.turn_indices)
0234         {
0235             auto const& turn = turns[index];
0236             if (turn.both(operation_from_overlay<OverlayType>::value))
0237             {
0238                 both_target = true;
0239                 break;
0240             }
0241         }
0242
0243         if (both_target)
0244         {
0245             for (auto index : cinfo.turn_indices)
0246             {
0247                 auto& turn = turns[index];
0248                 turn.has_colocated_both = true;
0249             }
0250         }
0251     }
0252 }
0253
0254 template
0255 <
0256     typename Turns,
0257     typename Clusters
0258 >
0259 inline void check_colocation(bool& has_blocked,
0260         signed_size_type cluster_id, Turns const& turns, Clusters const& clusters)
0261 {
0262     typedef typename boost::range_value<Turns>::type turn_type;
0263
0264     has_blocked = false;
0265
0266     auto mit = clusters.find(cluster_id);
0267     if (mit == clusters.end())
0268     {
0269         return;
0270     }
0271
0272     cluster_info const& cinfo = mit->second;
0273
0274     for (auto index : cinfo.turn_indices)
0275     {
0276         turn_type const& turn = turns[index];
0277         if (turn.any_blocked())
0278         {
0279             has_blocked = true;
0280         }
0281     }
0282 }
0283
0284 template
0285 <
0286     typename Turns,
0287     typename Clusters
0288 >
0289 inline void assign_cluster_ids(Turns& turns, Clusters const& clusters)
0290 {
0291     for (auto& turn : turns)
0292     {
0293         turn.cluster_id = -1;
0294     }
0295     for (auto const& kv : clusters)
0296     {
0297         for (auto const& index : kv.second.turn_indices)
0298         {
0299             turns[index].cluster_id = kv.first;
0300         }
0301     }
0302 }
0303
0304 // Checks colocated turns and flags combinations of uu/other, possibly a
0305 // combination of a ring touching another geometry's interior ring which is
0306 // tangential to the exterior ring
0307
0308 // This function can be extended to replace handle_tangencies: at each
0309 // colocation incoming and outgoing vectors should be inspected
0310
0311 template
0312 <
0313     bool Reverse1, bool Reverse2,
0314     overlay_type OverlayType,
0315     typename Geometry0,
0316     typename Geometry1,
0317     typename Turns,
0318     typename Clusters,
0319     typename RobustPolicy
0320 >
0321 inline bool handle_colocations(Turns& turns, Clusters& clusters,
0322                                RobustPolicy const& robust_policy)
0323 {
0324     static const detail::overlay::operation_type target_operation
0325             = detail::overlay::operation_from_overlay<OverlayType>::value;
0326
0327     get_clusters(turns, clusters, robust_policy);
0328
0329     if (clusters.empty())
0330     {
0331         return false;
0332     }
0333
0334     assign_cluster_ids(turns, clusters);
0335
0336     // Get colocated information here, and not later, to keep information
0337     // on turns which are discarded afterwards
0338     set_colocation<OverlayType>(turns, clusters);
0339
0340     if BOOST_GEOMETRY_CONSTEXPR (target_operation == operation_intersection)
0341     {
0342         discard_interior_exterior_turns
0343             <
0344                 do_reverse<geometry::point_order<Geometry0>::value>::value != Reverse1,
0345                 do_reverse<geometry::point_order<Geometry1>::value>::value != Reverse2
0346             >(turns, clusters);
0347     }
0348
0349     // There might be clusters having only one turn, if the rest is discarded
0350     // This is cleaned up later, after gathering the properties.
0351
0352 #if defined(BOOST_GEOMETRY_DEBUG_HANDLE_COLOCATIONS)
0353     std::cout << "*** Colocations " << map.size() << std::endl;
0354     for (auto const& kv : map)
0355     {
0356         std::cout << kv.first << std::endl;
0357         for (auto const& toi : kv.second)
0358         {
0359             detail::debug::debug_print_turn(turns[toi.turn_index]);
0360             std::cout << std::endl;
0361         }
0362     }
0363 #endif
0364
0365     return true;
0366 }
0367
0368
0369 struct is_turn_index
0370 {
0371     is_turn_index(signed_size_type index)
0372         : m_index(index)
0373     {}
0374
0375     template <typename Indexed>
0376     inline bool operator()(Indexed const& indexed) const
0377     {
0378         // Indexed is a indexed_turn_operation<Operation>
0379         return indexed.turn_index == m_index;
0380     }
0381
0382     signed_size_type m_index;
0383 };
0384
0385 template
0386 <
0387     typename Sbs,
0388     typename Point,
0389     typename Turns,
0390     typename Geometry1,
0391     typename Geometry2
0392 >
0393 inline bool fill_sbs(Sbs& sbs, Point& turn_point,
0394                      cluster_info const& cinfo,
0395                      Turns const& turns,
0396                      Geometry1 const& geometry1, Geometry2 const& geometry2)
0397 {
0398     if (cinfo.turn_indices.empty())
0399     {
0400         return false;
0401     }
0402
0403     bool first = true;
0404     for (auto turn_index : cinfo.turn_indices)
0405     {
0406         auto const& turn = turns[turn_index];
0407         if (first)
0408         {
0409             turn_point = turn.point;
0410         }
0411         for (int i = 0; i < 2; i++)
0412         {
0413             sbs.add(turn, turn.operations[i], turn_index, i, geometry1, geometry2, first);
0414             first = false;
0415         }
0416     }
0417     return true;
0418 }
0419
0420 template
0421 <
0422     bool Reverse1, bool Reverse2,
0423     overlay_type OverlayType,
0424     typename Turns,
0425     typename Clusters,
0426     typename Geometry1,
0427     typename Geometry2,
0428     typename Strategy
0429 >
0430 inline void gather_cluster_properties(Clusters& clusters, Turns& turns,
0431         operation_type for_operation,
0432         Geometry1 const& geometry1, Geometry2 const& geometry2,
0433         Strategy const& strategy)
0434 {
0435     typedef typename boost::range_value<Turns>::type turn_type;
0436     typedef typename turn_type::point_type point_type;
0437     typedef typename turn_type::turn_operation_type turn_operation_type;
0438
0439     // Define sorter, sorting counter-clockwise such that polygons are on the
0440     // right side
0441     typedef sort_by_side::side_sorter
0442         <
0443             Reverse1, Reverse2, OverlayType, point_type, Strategy, std::less<int>
0444         > sbs_type;
0445
0446     for (auto& pair : clusters)
0447     {
0448         cluster_info& cinfo = pair.second;
0449
0450         sbs_type sbs(strategy);
0451         point_type turn_point; // should be all the same for all turns in cluster
0452         if (! fill_sbs(sbs, turn_point, cinfo, turns, geometry1, geometry2))
0453         {
0454             continue;
0455         }
0456
0457         sbs.apply(turn_point);
0458
0459         sbs.find_open();
0460         sbs.assign_zones(for_operation);
0461
0462         cinfo.open_count = sbs.open_count(for_operation);
0463
0464         // Determine spikes
0465         cinfo.spike_count = 0;
0466         for (std::size_t i = 0; i + 1 < sbs.m_ranked_points.size(); i++)
0467         {
0468             auto const& current = sbs.m_ranked_points[i];
0469             auto const& next = sbs.m_ranked_points[i + 1];
0470             if (current.rank == next.rank
0471                 && current.direction == detail::overlay::sort_by_side::dir_from
0472                 && next.direction == detail::overlay::sort_by_side::dir_to)
0473             {
0474                 // It leaves, from cluster point, and immediately returns.
0475                 cinfo.spike_count += 1;
0476             }
0477         }
0478
0479         bool const set_startable = OverlayType != overlay_dissolve;
0480
0481         // Unset the startable flag for all 'closed' zones. This does not
0482         // apply for self-turns, because those counts are not from both
0483         // polygons
0484         for (std::size_t i = 0; i < sbs.m_ranked_points.size(); i++)
0485         {
0486             typename sbs_type::rp const& ranked = sbs.m_ranked_points[i];
0487             turn_type& turn = turns[ranked.turn_index];
0488             turn_operation_type& op = turn.operations[ranked.operation_index];
0489
0490             if (set_startable
0491                 && for_operation == operation_union
0492                 && cinfo.open_count == 0)
0493             {
0494                 op.enriched.startable = false;
0495             }
0496
0497             if (ranked.direction != sort_by_side::dir_to)
0498             {
0499                 continue;
0500             }
0501
0502             op.enriched.count_left = ranked.count_left;
0503             op.enriched.count_right = ranked.count_right;
0504             op.enriched.rank = ranked.rank;
0505             op.enriched.zone = ranked.zone;
0506
0507             if (! set_startable)
0508             {
0509                 continue;
0510             }
0511
0512             if BOOST_GEOMETRY_CONSTEXPR (OverlayType == overlay_difference)
0513             {
0514                 if (is_self_turn<OverlayType>(turn))
0515                 {
0516                     // TODO: investigate
0517                     continue;
0518                 }
0519             }
0520
0521             if ((for_operation == operation_union
0522                     && ranked.count_left != 0)
0523              || (for_operation == operation_intersection
0524                     && ranked.count_right != 2))
0525             {
0526                 op.enriched.startable = false;
0527             }
0528         }
0529
0530     }
0531 }
0532
0533
0534 }} // namespace detail::overlay
0535 #endif //DOXYGEN_NO_DETAIL
0536
0537
0538 }} // namespace boost::geometry
0539
0540 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_HANDLE_COLOCATIONS_HPP