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