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 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
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/condition.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     colocate_clusters(clusters, turns);
0101 }
0102
0103 template <typename Turn, typename IndexSet>
0104 inline void discard_colocated_turn(Turn& turn, IndexSet& indices, signed_size_type index)
0105 {
0106     turn.discarded = true;
0107     // Set cluster id to -1, but don't clear colocated flags
0108     turn.cluster_id = -1;
0109     // To remove it later from clusters
0110     indices.insert(index);
0111 }
0112
0113 template <bool Reverse>
0114 inline bool is_interior(segment_identifier const& seg_id)
0115 {
0116     return Reverse ? seg_id.ring_index == -1 : seg_id.ring_index >= 0;
0117 }
0118
0119 template <bool Reverse0, bool Reverse1>
0120 inline bool is_ie_turn(segment_identifier const& ext_seg_0,
0121                        segment_identifier const& ext_seg_1,
0122                        segment_identifier const& int_seg_0,
0123                        segment_identifier const& other_seg_1)
0124 {
0125     if (ext_seg_0.source_index == ext_seg_1.source_index)
0126     {
0127         // External turn is a self-turn, dont discard internal turn for this
0128         return false;
0129     }
0130
0131
0132     // Compares two segment identifiers from two turns (external / one internal)
0133
0134     // From first turn [0], both are from same polygon (multi_index),
0135     // one is exterior (-1), the other is interior (>= 0),
0136     // and the second turn [1] handles the same ring
0137
0138     // For difference, where the rings are processed in reversal, all interior
0139     // rings become exterior and vice versa. But also the multi property changes:
0140     // rings originally from the same multi should now be considered as from
0141     // different multi polygons.
0142     // But this is not always the case, and at this point hard to figure out
0143     // (not yet implemented, TODO)
0144
0145     bool const same_multi0 = ! Reverse0
0146                              && ext_seg_0.multi_index == int_seg_0.multi_index;
0147
0148     bool const same_multi1 = ! Reverse1
0149                              && ext_seg_1.multi_index == other_seg_1.multi_index;
0150
0151     boost::ignore_unused(same_multi1);
0152
0153     return same_multi0
0154             && same_multi1
0155             && ! is_interior<Reverse0>(ext_seg_0)
0156             && is_interior<Reverse0>(int_seg_0)
0157             && ext_seg_1.ring_index == other_seg_1.ring_index;
0158
0159     // The other way round is tested in another call
0160 }
0161
0162 template
0163 <
0164     bool Reverse0, bool Reverse1, // Reverse interpretation interior/exterior
0165     typename Turns,
0166     typename Clusters
0167 >
0168 inline void discard_interior_exterior_turns(Turns& turns, Clusters& clusters)
0169 {
0170     std::set<signed_size_type> indices_to_remove;
0171
0172     for (auto& pair : clusters)
0173     {
0174         cluster_info& cinfo = pair.second;
0175
0176         indices_to_remove.clear();
0177
0178         for (auto index : cinfo.turn_indices)
0179         {
0180             auto& turn = turns[index];
0181             segment_identifier const& seg_0 = turn.operations[0].seg_id;
0182             segment_identifier const& seg_1 = turn.operations[1].seg_id;
0183
0184             if (! (turn.both(operation_union)
0185                    || turn.combination(operation_union, operation_blocked)))
0186             {
0187                 // Not a uu/ux, so cannot be colocated with a iu turn
0188                 continue;
0189             }
0190
0191             for (auto interior_index : cinfo.turn_indices)
0192             {
0193                 if (index == interior_index)
0194                 {
0195                     continue;
0196                 }
0197
0198                 // Turn with, possibly, an interior ring involved
0199                 auto& interior_turn = turns[interior_index];
0200                 segment_identifier const& int_seg_0 = interior_turn.operations[0].seg_id;
0201                 segment_identifier const& int_seg_1 = interior_turn.operations[1].seg_id;
0202
0203                 if (is_ie_turn<Reverse0, Reverse1>(seg_0, seg_1, int_seg_0, int_seg_1))
0204                 {
0205                     discard_colocated_turn(interior_turn, indices_to_remove, interior_index);
0206                 }
0207                 if (is_ie_turn<Reverse1, Reverse0>(seg_1, seg_0, int_seg_1, int_seg_0))
0208                 {
0209                     discard_colocated_turn(interior_turn, indices_to_remove, interior_index);
0210                 }
0211             }
0212         }
0213
0214         // Erase from the indices (which cannot be done above)
0215         for (auto index : indices_to_remove)
0216         {
0217             cinfo.turn_indices.erase(index);
0218         }
0219     }
0220 }
0221
0222 template
0223 <
0224     overlay_type OverlayType,
0225     typename Turns,
0226     typename Clusters
0227 >
0228 inline void set_colocation(Turns& turns, Clusters const& clusters)
0229 {
0230     for (auto const& pair : clusters)
0231     {
0232         cluster_info const& cinfo = pair.second;
0233
0234         bool both_target = false;
0235         for (auto index : cinfo.turn_indices)
0236         {
0237             auto const& turn = turns[index];
0238             if (turn.both(operation_from_overlay<OverlayType>::value))
0239             {
0240                 both_target = true;
0241                 break;
0242             }
0243         }
0244
0245         if (both_target)
0246         {
0247             for (auto index : cinfo.turn_indices)
0248             {
0249                 auto& turn = turns[index];
0250                 turn.has_colocated_both = true;
0251             }
0252         }
0253     }
0254 }
0255
0256 template
0257 <
0258     typename Turns,
0259     typename Clusters
0260 >
0261 inline void check_colocation(bool& has_blocked,
0262         signed_size_type cluster_id, Turns const& turns, Clusters const& clusters)
0263 {
0264     typedef typename boost::range_value<Turns>::type turn_type;
0265
0266     has_blocked = false;
0267
0268     auto mit = clusters.find(cluster_id);
0269     if (mit == clusters.end())
0270     {
0271         return;
0272     }
0273
0274     cluster_info const& cinfo = mit->second;
0275
0276     for (auto index : cinfo.turn_indices)
0277     {
0278         turn_type const& turn = turns[index];
0279         if (turn.any_blocked())
0280         {
0281             has_blocked = true;
0282         }
0283     }
0284 }
0285
0286 template
0287 <
0288     typename Turns,
0289     typename Clusters
0290 >
0291 inline void assign_cluster_ids(Turns& turns, Clusters const& clusters)
0292 {
0293     for (auto& turn : turns)
0294     {
0295         turn.cluster_id = -1;
0296     }
0297     for (auto const& kv : clusters)
0298     {
0299         for (auto const& index : kv.second.turn_indices)
0300         {
0301             turns[index].cluster_id = kv.first;
0302         }
0303     }
0304 }
0305
0306 // Checks colocated turns and flags combinations of uu/other, possibly a
0307 // combination of a ring touching another geometry's interior ring which is
0308 // tangential to the exterior ring
0309
0310 // This function can be extended to replace handle_tangencies: at each
0311 // colocation incoming and outgoing vectors should be inspected
0312
0313 template
0314 <
0315     bool Reverse1, bool Reverse2,
0316     overlay_type OverlayType,
0317     typename Geometry0,
0318     typename Geometry1,
0319     typename Turns,
0320     typename Clusters,
0321     typename RobustPolicy
0322 >
0323 inline bool handle_colocations(Turns& turns, Clusters& clusters,
0324                                RobustPolicy const& robust_policy)
0325 {
0326     static const detail::overlay::operation_type target_operation
0327             = detail::overlay::operation_from_overlay<OverlayType>::value;
0328
0329     get_clusters(turns, clusters, robust_policy);
0330
0331     if (clusters.empty())
0332     {
0333         return false;
0334     }
0335
0336     assign_cluster_ids(turns, clusters);
0337
0338     // Get colocated information here, and not later, to keep information
0339     // on turns which are discarded afterwards
0340     set_colocation<OverlayType>(turns, clusters);
0341
0342     if (BOOST_GEOMETRY_CONDITION(target_operation == operation_intersection))
0343     {
0344         discard_interior_exterior_turns
0345             <
0346                 do_reverse<geometry::point_order<Geometry0>::value>::value != Reverse1,
0347                 do_reverse<geometry::point_order<Geometry1>::value>::value != Reverse2
0348             >(turns, clusters);
0349     }
0350
0351     // There might be clusters having only one turn, if the rest is discarded
0352     // This is cleaned up later, after gathering the properties.
0353
0354 #if defined(BOOST_GEOMETRY_DEBUG_HANDLE_COLOCATIONS)
0355     std::cout << "*** Colocations " << map.size() << std::endl;
0356     for (auto const& kv : map)
0357     {
0358         std::cout << kv.first << std::endl;
0359         for (auto const& toi : kv.second)
0360         {
0361             detail::debug::debug_print_turn(turns[toi.turn_index]);
0362             std::cout << std::endl;
0363         }
0364     }
0365 #endif
0366
0367     return true;
0368 }
0369
0370
0371 struct is_turn_index
0372 {
0373     is_turn_index(signed_size_type index)
0374         : m_index(index)
0375     {}
0376
0377     template <typename Indexed>
0378     inline bool operator()(Indexed const& indexed) const
0379     {
0380         // Indexed is a indexed_turn_operation<Operation>
0381         return indexed.turn_index == m_index;
0382     }
0383
0384     signed_size_type m_index;
0385 };
0386
0387 template
0388 <
0389     typename Sbs,
0390     typename Point,
0391     typename Turns,
0392     typename Geometry1,
0393     typename Geometry2
0394 >
0395 inline bool fill_sbs(Sbs& sbs, Point& turn_point,
0396                      cluster_info const& cinfo,
0397                      Turns const& turns,
0398                      Geometry1 const& geometry1, Geometry2 const& geometry2)
0399 {
0400     if (cinfo.turn_indices.empty())
0401     {
0402         return false;
0403     }
0404
0405     bool first = true;
0406     for (auto turn_index : cinfo.turn_indices)
0407     {
0408         auto const& turn = turns[turn_index];
0409         if (first)
0410         {
0411             turn_point = turn.point;
0412         }
0413         for (int i = 0; i < 2; i++)
0414         {
0415             sbs.add(turn, turn.operations[i], turn_index, i, geometry1, geometry2, first);
0416             first = false;
0417         }
0418     }
0419     return true;
0420 }
0421
0422 template
0423 <
0424     bool Reverse1, bool Reverse2,
0425     overlay_type OverlayType,
0426     typename Turns,
0427     typename Clusters,
0428     typename Geometry1,
0429     typename Geometry2,
0430     typename SideStrategy
0431 >
0432 inline void gather_cluster_properties(Clusters& clusters, Turns& turns,
0433         operation_type for_operation,
0434         Geometry1 const& geometry1, Geometry2 const& geometry2,
0435         SideStrategy const& strategy)
0436 {
0437     typedef typename boost::range_value<Turns>::type turn_type;
0438     typedef typename turn_type::point_type point_type;
0439     typedef typename turn_type::turn_operation_type turn_operation_type;
0440
0441     // Define sorter, sorting counter-clockwise such that polygons are on the
0442     // right side
0443     typedef sort_by_side::side_sorter
0444         <
0445             Reverse1, Reverse2, OverlayType, point_type, SideStrategy, std::less<int>
0446         > sbs_type;
0447
0448     for (auto& pair : clusters)
0449     {
0450         cluster_info& cinfo = pair.second;
0451
0452         sbs_type sbs(strategy);
0453         point_type turn_point; // should be all the same for all turns in cluster
0454         if (! fill_sbs(sbs, turn_point, cinfo, turns, geometry1, geometry2))
0455         {
0456             continue;
0457         }
0458
0459         sbs.apply(turn_point);
0460
0461         sbs.find_open();
0462         sbs.assign_zones(for_operation);
0463
0464         cinfo.open_count = sbs.open_count(for_operation);
0465
0466         bool const set_startable = OverlayType != overlay_dissolve;
0467
0468         // Unset the startable flag for all 'closed' zones. This does not
0469         // apply for self-turns, because those counts are not from both
0470         // polygons
0471         for (std::size_t i = 0; i < sbs.m_ranked_points.size(); i++)
0472         {
0473             typename sbs_type::rp const& ranked = sbs.m_ranked_points[i];
0474             turn_type& turn = turns[ranked.turn_index];
0475             turn_operation_type& op = turn.operations[ranked.operation_index];
0476
0477             if (set_startable
0478                     && for_operation == operation_union && cinfo.open_count == 0)
0479             {
0480                 op.enriched.startable = false;
0481             }
0482
0483             if (ranked.direction != sort_by_side::dir_to)
0484             {
0485                 continue;
0486             }
0487
0488             op.enriched.count_left = ranked.count_left;
0489             op.enriched.count_right = ranked.count_right;
0490             op.enriched.rank = ranked.rank;
0491             op.enriched.zone = ranked.zone;
0492
0493             if (! set_startable)
0494             {
0495                 continue;
0496             }
0497
0498             if (BOOST_GEOMETRY_CONDITION(OverlayType == overlay_difference)
0499                     && is_self_turn<OverlayType>(turn))
0500             {
0501                 // TODO: investigate
0502                 continue;
0503             }
0504
0505             if ((for_operation == operation_union
0506                     && ranked.count_left != 0)
0507              || (for_operation == operation_intersection
0508                     && ranked.count_right != 2))
0509             {
0510                 op.enriched.startable = false;
0511             }
0512         }
0513
0514     }
0515 }
0516
0517
0518 }} // namespace detail::overlay
0519 #endif //DOXYGEN_NO_DETAIL
0520
0521
0522 }} // namespace boost::geometry
0523
0524 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_HANDLE_COLOCATIONS_HPP