detail/overlay/enrich_intersection_points.hpp

0001 // Boost.Geometry (aka GGL, Generic Geometry Library)
0002
0003 // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
0004 // Copyright (c) 2017 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_ENRICH_HPP
0016 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_ENRICH_HPP
0017
0018 #include <cstddef>
0019 #include <algorithm>
0020 #include <map>
0021 #include <set>
0022 #include <vector>
0023
0024 #ifdef BOOST_GEOMETRY_DEBUG_ENRICH
0025 #  include <iostream>
0026 #  include <boost/geometry/algorithms/detail/overlay/debug_turn_info.hpp>
0027 #  include <boost/geometry/io/wkt/wkt.hpp>
0028 #  if ! defined(BOOST_GEOMETRY_DEBUG_IDENTIFIER)
0029 #    define BOOST_GEOMETRY_DEBUG_IDENTIFIER
0030   #endif
0031 #endif
0032
0033 #include <boost/range/begin.hpp>
0034 #include <boost/range/end.hpp>
0035 #include <boost/range/value_type.hpp>
0036
0037 #include <boost/geometry/algorithms/detail/ring_identifier.hpp>
0038 #include <boost/geometry/algorithms/detail/overlay/check_enrich.hpp>
0039 #include <boost/geometry/algorithms/detail/overlay/discard_duplicate_turns.hpp>
0040 #include <boost/geometry/algorithms/detail/overlay/graph/adapt_operations.hpp>
0041 #include <boost/geometry/algorithms/detail/overlay/handle_self_turns.hpp>
0042 #include <boost/geometry/algorithms/detail/overlay/is_self_turn.hpp>
0043 #include <boost/geometry/algorithms/detail/overlay/less_by_segment_ratio.hpp>
0044 #include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp>
0045 #include <boost/geometry/util/constexpr.hpp>
0046 #include <boost/geometry/views/enumerate_view.hpp>
0047
0048
0049
0050 namespace boost { namespace geometry
0051 {
0052
0053 #ifndef DOXYGEN_NO_DETAIL
0054 namespace detail { namespace overlay
0055 {
0056
0057 template <typename Turns>
0058 struct discarded_indexed_turn
0059 {
0060     discarded_indexed_turn(Turns const& turns)
0061         : m_turns(turns)
0062     {}
0063
0064     template <typename IndexedTurn>
0065     inline bool operator()(IndexedTurn const& indexed) const
0066     {
0067         return m_turns[indexed.turn_index].discarded;
0068     }
0069
0070     Turns const& m_turns;
0071 };
0072
0073 // Sorts IP-s of this ring on segment-identifier, and if on same segment,
0074 //  on distance.
0075 // Then assigns for each IP which is the next IP on this segment,
0076 // plus the vertex-index to travel to, plus the next IP
0077 // (might be on another segment)
0078 template
0079 <
0080     bool Reverse1, bool Reverse2,
0081     typename Operations,
0082     typename Turns,
0083     typename Geometry1, typename Geometry2,
0084     typename Strategy
0085 >
0086 inline void enrich_sort(Operations& operations,
0087             Turns const& turns,
0088             Geometry1 const& geometry1,
0089             Geometry2 const& geometry2,
0090             Strategy const& strategy)
0091 {
0092     std::sort(std::begin(operations),
0093               std::end(operations),
0094               less_by_segment_ratio
0095                 <
0096                     Turns,
0097                     typename boost::range_value<Operations>::type,
0098                     Geometry1, Geometry2,
0099                     Strategy,
0100                     Reverse1, Reverse2
0101                 >(turns, geometry1, geometry2, strategy));
0102 }
0103
0104 // Assign travel-to-vertex/ip index for each turn.
0105 template <typename Operations, typename Turns>
0106 inline void enrich_assign(Operations& operations, Turns& turns)
0107 {
0108     for (auto const& item : util::enumerate(operations))
0109     {
0110         auto const& index = item.index;
0111         auto const& indexed = item.value;
0112
0113         if (indexed.discarded)
0114         {
0115             continue;
0116         }
0117
0118         auto& turn = turns[indexed.turn_index];
0119         auto& op = turn.operations[indexed.operation_index];
0120
0121         std::size_t skipped_count = 0;
0122
0123         auto advance = [&](auto index)
0124         {
0125             std::size_t result = (index + 1) % operations.size();
0126             while (operations[result].discarded)
0127             {
0128                 result = (result + 1) % operations.size();
0129                 auto const& next_turn = turns[operations[result].turn_index];
0130                 if (! next_turn.is_traversable)
0131                 {
0132                     // There might be more conditions to skip.
0133                     // But it should not skip ALL discarded turns.
0134                     skipped_count++;
0135 #if defined(BOOST_GEOMETRY_DEBUG_TRAVERSE_GRAPH)
0136                     std::cout << "  -> Skip for " << operations[index].turn_index << " because of blocked "
0137                                 << " " << operations[result].turn_index
0138                                 << std::endl;
0139 #endif
0140                 }
0141             }
0142             return result;
0143         };
0144
0145         std::size_t next_index = advance(index);
0146
0147         auto next_turn = [&operations, &turns, &next_index]()
0148         {
0149             return turns[operations[next_index].turn_index];
0150         };
0151         auto next_operation = [&operations, &turns, &next_index]()
0152         {
0153             auto const& next_turn = turns[operations[next_index].turn_index];
0154             return next_turn.operations[operations[next_index].operation_index];
0155         };
0156
0157         // Cluster behaviour: next should point after cluster, unless
0158         // their seg_ids are not the same
0159         // (For dissolve, this is still to be examined - TODO)
0160         while (turn.is_clustered()
0161                 && turn.cluster_id == next_turn().cluster_id
0162                 && op.seg_id == next_operation().seg_id
0163                 && indexed.turn_index != operations[next_index].turn_index)
0164         {
0165             // In same cluster, on same segment, but not same turn
0166             next_index = advance(next_index);
0167         }
0168
0169         if (skipped_count > 0)
0170         {
0171             // Don't assign travel-info, because it is not reachable. But neither discard the turn,
0172             // the other operation might be reachable.
0173             continue;
0174         }
0175
0176         op.enriched.travels_to_ip_index
0177                 = static_cast<signed_size_type>(operations[next_index].turn_index);
0178         op.enriched.travels_to_vertex_index
0179                 = operations[next_index].subject->seg_id.segment_index;
0180     }
0181
0182 #ifdef BOOST_GEOMETRY_DEBUG_ENRICH
0183     for (auto const& indexed_op : operations)
0184     {
0185         auto const& op = turns[indexed_op.turn_index].operations[indexed_op.operation_index];
0186
0187         std::cout << indexed_op.turn_index
0188             << " cl=" << turns[indexed_op.turn_index].cluster_id
0189             << " meth=" << method_char(turns[indexed_op.turn_index].method)
0190             << " seg=" << op.seg_id
0191             << " dst=" << op.fraction // needs define
0192             << " op=" << operation_char(turns[indexed_op.turn_index].operations[0].operation)
0193             << operation_char(turns[indexed_op.turn_index].operations[1].operation)
0194             << " (" << operation_char(op.operation) << ")"
0195             << " to=" << op.enriched.travels_to_ip_index
0196             << " [vx " << op.enriched.travels_to_vertex_index << "]"
0197             << (turns[indexed_op.turn_index].discarded ? " [discarded]" : "")
0198             << (op.enriched.startable ? "" : " [not startable]")
0199             << (indexed_op.discarded ? " DISCARDED" : "")
0200             << std::endl;
0201     }
0202 #endif
0203 }
0204
0205 template <typename Operations, typename Turns>
0206 inline void enrich_adapt(Operations& operations, Turns& turns)
0207 {
0208     // Operations is a vector of indexed_turn_operation<>
0209     // If it is empty, or contains one or two items, it makes no sense
0210     if (operations.size() < 3)
0211     {
0212         return;
0213     }
0214
0215     bool next_phase = false;
0216     std::size_t previous_index = operations.size() - 1;
0217
0218     for (auto const& item : util::enumerate(operations))
0219     {
0220         auto const& index = item.index;
0221         auto const& indexed = item.value;
0222         auto& turn = turns[indexed.turn_index];
0223         auto& op = turn.operations[indexed.operation_index];
0224
0225         std::size_t const next_index = (index + 1) % operations.size();
0226         auto const& next_turn = turns[operations[next_index].turn_index];
0227         auto const& next_op = next_turn.operations[operations[next_index].operation_index];
0228
0229         if (op.seg_id.segment_index == next_op.seg_id.segment_index)
0230         {
0231             auto const& prev_turn = turns[operations[previous_index].turn_index];
0232             auto const& prev_op = prev_turn.operations[operations[previous_index].operation_index];
0233             if (op.seg_id.segment_index == prev_op.seg_id.segment_index)
0234             {
0235                 op.enriched.startable = false;
0236                 next_phase = true;
0237             }
0238         }
0239         previous_index = index;
0240     }
0241
0242     if (! next_phase)
0243     {
0244         return;
0245     }
0246
0247     // Discard turns which are both non-startable
0248     next_phase = false;
0249     for (auto& turn : turns)
0250     {
0251         if (! turn.operations[0].enriched.startable
0252             && ! turn.operations[1].enriched.startable)
0253         {
0254             turn.discarded = true;
0255             next_phase = true;
0256         }
0257     }
0258
0259     if (! next_phase)
0260     {
0261         return;
0262     }
0263
0264     // Remove discarded turns from operations to avoid having them as next turn
0265     discarded_indexed_turn<Turns> const predicate(turns);
0266     operations.erase(std::remove_if(std::begin(operations),
0267         std::end(operations), predicate), std::end(operations));
0268 }
0269
0270 struct enriched_map_default_include_policy
0271 {
0272     template <typename Operation>
0273     static inline bool include(Operation const& )
0274     {
0275         // By default include all operations
0276         return true;
0277     }
0278 };
0279
0280 // Add all (non discarded) operations on this ring
0281 // Blocked operations or uu on clusters (for intersection)
0282 // should be included, to block potential paths in clusters
0283 template <typename Turns, typename IncludePolicy>
0284 inline auto create_map(Turns const& turns, IncludePolicy const& include_policy)
0285 {
0286     using turn_type = typename boost::range_value<Turns>::type;
0287     using indexed_turn_operation = indexed_turn_operation
0288         <
0289             typename turn_type::turn_operation_type
0290         >;
0291
0292     std::map
0293     <
0294         ring_identifier,
0295         std::vector<indexed_turn_operation>
0296     > mapped_vector;
0297
0298     for (auto const& turn_item : util::enumerate(turns))
0299     {
0300         auto const& index = turn_item.index;
0301         auto const& turn = turn_item.value;
0302         for (auto const& op_item : util::enumerate(turn.operations))
0303         {
0304             auto const& op_index = op_item.index;
0305             auto const& op = op_item.value;
0306             if (include_policy.include(op.operation))
0307             {
0308                 mapped_vector[ring_id_by_seg_id(op.seg_id)].emplace_back
0309                     (
0310                          index, op_index, op, turn.operations[1 - op_index].seg_id, turn.discarded
0311                     );
0312             }
0313         }
0314     }
0315
0316     return mapped_vector;
0317 }
0318
0319 template
0320 <
0321     overlay_type OverlayType,
0322     typename Turns,
0323     typename Clusters,
0324     typename Geometry1, typename Geometry2,
0325     typename IntersectionStrategy
0326 >
0327 inline void enrich_discard_turns(Turns& turns, Clusters& clusters,
0328     Geometry1 const& geometry1, Geometry2 const& geometry2,
0329     IntersectionStrategy const& strategy)
0330 {
0331     constexpr operation_type target_operation = operation_from_overlay<OverlayType>::value;
0332
0333     constexpr operation_type opposite_operation
0334             = target_operation == operation_union
0335             ? operation_intersection
0336             : operation_union;
0337
0338     // Turns are often used by index (in clusters, next_index, etc)
0339     // and turns may therefore NOT be DELETED - they may only be flagged as discarded
0340
0341     discard_duplicate_turns(turns, geometry1, geometry2);
0342
0343     // Discard turns not part of target overlay
0344     for (auto& turn : turns)
0345     {
0346         if (turn.both(operation_none)
0347             || turn.both(opposite_operation)
0348             || turn.both(operation_blocked)
0349             || (is_self_turn<OverlayType>(turn)
0350                 && ! turn.is_clustered()
0351                 && ! turn.both(target_operation)))
0352         {
0353             // For all operations, discard xx and none/none
0354             // For intersections, remove uu to avoid the need to travel
0355             // a union (during intersection) in uu/cc clusters (e.g. #31,#32,#33)
0356
0357             // Similarly, for union, discard ii and ix
0358
0359             // For self-turns, only keep uu / ii
0360
0361             turn.discarded = true;
0362             turn.cluster_id = -1;
0363         }
0364
0365 #if defined(BOOST_GEOMETRY_CONCEPT_FIX_START_TURNS)
0366         if (turn.is_clustered() && turn.method == method_start)
0367         {
0368             // Start turns are generated, in case the previous turn is missed.
0369             // But often it is not missed, and then it should be deleted.
0370             // TODO: only if the cluster NOT ONLY contains start turns, and there are turns left...
0371             turn.discarded = true;
0372             turn.cluster_id = -1;
0373         }
0374 #endif
0375     }
0376
0377     // Discard self turns located within the other geometry (for union)
0378     // or outside it (for intersection)
0379     // For buffer or dissolve, nothing is called.
0380     discard_closed_turns
0381         <
0382             OverlayType,
0383             target_operation
0384         >::apply(turns, clusters, geometry1, geometry2,  strategy);
0385     discard_open_turns
0386         <
0387             OverlayType,
0388             target_operation
0389         >::apply(turns, clusters, geometry1, geometry2, strategy);
0390
0391     // Remove discarded turns from clusters
0392     cleanup_clusters(turns, clusters);
0393 }
0394
0395 template
0396 <
0397     bool Reverse1, bool Reverse2,
0398     overlay_type OverlayType,
0399     typename Turns,
0400     typename Geometry1, typename Geometry2,
0401     typename IntersectionStrategy
0402 >
0403 inline void enrich_turns(Turns& turns,
0404     Geometry1 const& geometry1, Geometry2 const& geometry2,
0405     IntersectionStrategy const& strategy)
0406 {
0407     constexpr operation_type target_operation = operation_from_overlay<OverlayType>::value;
0408
0409     // Create a map of vectors of indexed operation-types to be able
0410     // to sort intersection points PER RING
0411     auto mapped_vector = create_map(turns, enriched_map_default_include_policy());
0412
0413     for (auto& pair : mapped_vector)
0414     {
0415         enrich_sort<Reverse1, Reverse2>(pair.second, turns, geometry1, geometry2, strategy);
0416     }
0417
0418     for (auto& pair : mapped_vector)
0419     {
0420 #ifdef BOOST_GEOMETRY_DEBUG_ENRICH
0421     std::cout << "ENRICH-assign Ring " << pair.first << std::endl;
0422 #endif
0423         if BOOST_GEOMETRY_CONSTEXPR (OverlayType == overlay_dissolve)
0424         {
0425             enrich_adapt(pair.second, turns);
0426         }
0427
0428         enrich_assign(pair.second, turns);
0429     }
0430
0431     block_ux_uu_workaround(turns);
0432
0433 #ifdef BOOST_GEOMETRY_DEBUG_ENRICH
0434     constexpr bool do_check_graph = true;
0435 #else
0436     constexpr bool do_check_graph = false;
0437 #endif
0438
0439     if BOOST_GEOMETRY_CONSTEXPR (do_check_graph)
0440     {
0441         check_graph(turns, target_operation);
0442     }
0443 }
0444
0445 }} // namespace detail::overlay
0446 #endif //DOXYGEN_NO_DETAIL
0447
0448 /*!
0449 \brief All intersection points are enriched with successor information
0450 \ingroup overlay
0451 \tparam Turns type of intersection container
0452             (e.g. vector of "intersection/turn point"'s)
0453 \tparam Clusters type of cluster container
0454 \tparam Geometry1 \tparam_geometry
0455 \tparam Geometry2 \tparam_geometry
0456 \tparam PointInGeometryStrategy point in geometry strategy type
0457 \param turns container containing intersection points
0458 \param clusters container containing clusters
0459 \param geometry1 \param_geometry
0460 \param geometry2 \param_geometry
0461 \param strategy point in geometry strategy
0462  */
0463 template
0464 <
0465     bool Reverse1, bool Reverse2,
0466     overlay_type OverlayType,
0467     typename Turns,
0468     typename Clusters,
0469     typename Geometry1, typename Geometry2,
0470     typename IntersectionStrategy
0471 >
0472 inline void enrich_intersection_points(Turns& turns,
0473     Clusters& clusters,
0474     Geometry1 const& geometry1, Geometry2 const& geometry2,
0475     IntersectionStrategy const& strategy)
0476 {
0477     detail::overlay::enrich_discard_turns<OverlayType>(turns, clusters, geometry1, geometry2, strategy);
0478     detail::overlay::enrich_turns<Reverse1, Reverse2, OverlayType>(turns, geometry1, geometry2, strategy);
0479 }
0480
0481 }} // namespace boost::geometry
0482
0483 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_ENRICH_HPP