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/handle_colocations.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
0105 // Assign travel-to-vertex/ip index for each turn.
0106 template <typename Operations, typename Turns>
0107 inline void enrich_assign(Operations& operations, Turns& turns)
0108 {
0109     for (auto const& item : util::enumerate(operations))
0110     {
0111         auto const& index = item.index;
0112         auto const& indexed = item.value;
0113         auto& turn = turns[indexed.turn_index];
0114         auto& op = turn.operations[indexed.operation_index];
0115
0116         std::size_t next_index = index + 1 < operations.size() ? index + 1 : 0;
0117         auto advance = [&operations](auto index)
0118         {
0119             std::size_t const result = index + 1;
0120             return result >= operations.size() ? 0 : result;
0121         };
0122
0123         auto next_turn = [&operations, &turns, &next_index]()
0124         {
0125             return turns[operations[next_index].turn_index];
0126         };
0127         auto next_operation = [&operations, &turns, &next_index]()
0128         {
0129             auto const& next_turn = turns[operations[next_index].turn_index];
0130             return next_turn.operations[operations[next_index].operation_index];
0131         };
0132
0133         // Cluster behaviour: next should point after cluster, unless
0134         // their seg_ids are not the same
0135         // (For dissolve, this is still to be examined - TODO)
0136         while (turn.is_clustered()
0137                 && turn.cluster_id == next_turn().cluster_id
0138                 && op.seg_id == next_operation().seg_id
0139                 && indexed.turn_index != operations[next_index].turn_index)
0140         {
0141             // In same cluster, on same segment, but not same turn
0142             next_index = advance(next_index);
0143         }
0144
0145         op.enriched.travels_to_ip_index
0146                 = static_cast<signed_size_type>(operations[next_index].turn_index);
0147         op.enriched.travels_to_vertex_index
0148                 = operations[next_index].subject->seg_id.segment_index;
0149
0150         auto const& next_op = next_operation();
0151         if (op.seg_id.segment_index == next_op.seg_id.segment_index
0152             && op.fraction < next_op.fraction)
0153         {
0154             // Next turn is located further on same segment: assign next_ip_index
0155             op.enriched.next_ip_index = static_cast<signed_size_type>(operations[next_index].turn_index);
0156         }
0157     }
0158
0159 #ifdef BOOST_GEOMETRY_DEBUG_ENRICH
0160     for (auto const& indexed_op : operations)
0161     {
0162         auto const& op = turns[indexed_op.turn_index].operations[indexed_op.operation_index];
0163
0164         std::cout << indexed_op.turn_index
0165             << " cl=" << turns[indexed_op.turn_index].cluster_id
0166             << " meth=" << method_char(turns[indexed_op.turn_index].method)
0167             << " seg=" << op.seg_id
0168             << " dst=" << op.fraction // needs define
0169             << " op=" << operation_char(turns[indexed_op.turn_index].operations[0].operation)
0170             << operation_char(turns[indexed_op.turn_index].operations[1].operation)
0171             << " (" << operation_char(op.operation) << ")"
0172             << " nxt=" << op.enriched.next_ip_index
0173             << " / " << op.enriched.travels_to_ip_index
0174             << " [vx " << op.enriched.travels_to_vertex_index << "]"
0175             << (turns[indexed_op.turn_index].discarded ? " [discarded]" : "")
0176             << (op.enriched.startable ? "" : " [not startable]")
0177             << std::endl;
0178     }
0179 #endif
0180 }
0181
0182 template <typename Operations, typename Turns>
0183 inline void enrich_adapt(Operations& operations, Turns& turns)
0184 {
0185     // Operations is a vector of indexed_turn_operation<>
0186     // If it is empty, or contains one or two items, it makes no sense
0187     if (operations.size() < 3)
0188     {
0189         return;
0190     }
0191
0192     bool next_phase = false;
0193     std::size_t previous_index = operations.size() - 1;
0194
0195     for (auto const& item : util::enumerate(operations))
0196     {
0197         auto const& index = item.index;
0198         auto const& indexed = item.value;
0199         auto& turn = turns[indexed.turn_index];
0200         auto& op = turn.operations[indexed.operation_index];
0201
0202         std::size_t const next_index = index + 1 < operations.size() ? index + 1 : 0;
0203         auto const& next_turn = turns[operations[next_index].turn_index];
0204         auto const& next_op = next_turn.operations[operations[next_index].operation_index];
0205
0206         if (op.seg_id.segment_index == next_op.seg_id.segment_index)
0207         {
0208             auto const& prev_turn = turns[operations[previous_index].turn_index];
0209             auto const& prev_op = prev_turn.operations[operations[previous_index].operation_index];
0210             if (op.seg_id.segment_index == prev_op.seg_id.segment_index)
0211             {
0212                 op.enriched.startable = false;
0213                 next_phase = true;
0214             }
0215         }
0216         previous_index = index;
0217     }
0218
0219     if (! next_phase)
0220     {
0221         return;
0222     }
0223
0224     // Discard turns which are both non-startable
0225     next_phase = false;
0226     for (auto& turn : turns)
0227     {
0228         if (! turn.operations[0].enriched.startable
0229             && ! turn.operations[1].enriched.startable)
0230         {
0231             turn.discarded = true;
0232             next_phase = true;
0233         }
0234     }
0235
0236     if (! next_phase)
0237     {
0238         return;
0239     }
0240
0241     // Remove discarded turns from operations to avoid having them as next turn
0242     discarded_indexed_turn<Turns> const predicate(turns);
0243     operations.erase(std::remove_if(std::begin(operations),
0244         std::end(operations), predicate), std::end(operations));
0245 }
0246
0247 struct enriched_map_default_include_policy
0248 {
0249     template <typename Operation>
0250     static inline bool include(Operation const& )
0251     {
0252         // By default include all operations
0253         return true;
0254     }
0255 };
0256
0257 // Add all (non discarded) operations on this ring
0258 // Blocked operations or uu on clusters (for intersection)
0259 // should be included, to block potential paths in clusters
0260 template <typename Turns, typename IncludePolicy>
0261 inline auto create_map(Turns const& turns, IncludePolicy const& include_policy)
0262 {
0263     using turn_type = typename boost::range_value<Turns>::type;
0264     using indexed_turn_operation = detail::overlay::indexed_turn_operation
0265         <
0266             typename turn_type::turn_operation_type
0267         >;
0268
0269     std::map
0270     <
0271         ring_identifier,
0272         std::vector<indexed_turn_operation>
0273     > mapped_vector;
0274
0275     for (auto const& turn_item : util::enumerate(turns))
0276     {
0277         auto const& index = turn_item.index;
0278         auto const& turn = turn_item.value;
0279         if (turn.discarded)
0280         {
0281             continue;
0282         }
0283
0284         for (auto const& op_item : util::enumerate(turn.operations))
0285         {
0286             auto const& op_index = op_item.index;
0287             auto const& op = op_item.value;
0288             if (include_policy.include(op.operation))
0289             {
0290                 mapped_vector[ring_id_by_seg_id(op.seg_id)].emplace_back
0291                     (
0292                          index, op_index, op, turn.operations[1 - op_index].seg_id
0293                     );
0294             }
0295         }
0296     }
0297     return mapped_vector;
0298 }
0299
0300 template <typename Point1, typename Point2>
0301 inline geometry::coordinate_type_t<Point1> distance_measure(Point1 const& a, Point2 const& b)
0302 {
0303     // TODO: use comparable distance for point-point instead - but that
0304     // causes currently cycling include problems
0305     using ctype = geometry::coordinate_type_t<Point1>;
0306     ctype const dx = get<0>(a) - get<0>(b);
0307     ctype const dy = get<1>(a) - get<1>(b);
0308     return dx * dx + dy * dy;
0309 }
0310
0311 template <typename Turns>
0312 inline void calculate_remaining_distance(Turns& turns)
0313 {
0314     for (auto& turn : turns)
0315     {
0316         auto& op0 = turn.operations[0];
0317         auto& op1 = turn.operations[1];
0318
0319         static decltype(op0.remaining_distance) const zero_distance = 0;
0320
0321         if (op0.remaining_distance != zero_distance
0322             || op1.remaining_distance != zero_distance)
0323         {
0324             continue;
0325         }
0326
0327         auto const to_index0 = op0.enriched.get_next_turn_index();
0328         auto const to_index1 = op1.enriched.get_next_turn_index();
0329         if (to_index0 >= 0
0330             && to_index1 >= 0
0331             && to_index0 != to_index1)
0332         {
0333             op0.remaining_distance = distance_measure(turn.point, turns[to_index0].point);
0334             op1.remaining_distance = distance_measure(turn.point, turns[to_index1].point);
0335         }
0336     }
0337 }
0338
0339 }} // namespace detail::overlay
0340 #endif //DOXYGEN_NO_DETAIL
0341
0342
0343
0344 /*!
0345 \brief All intersection points are enriched with successor information
0346 \ingroup overlay
0347 \tparam Turns type of intersection container
0348             (e.g. vector of "intersection/turn point"'s)
0349 \tparam Clusters type of cluster container
0350 \tparam Geometry1 \tparam_geometry
0351 \tparam Geometry2 \tparam_geometry
0352 \tparam PointInGeometryStrategy point in geometry strategy type
0353 \param turns container containing intersection points
0354 \param clusters container containing clusters
0355 \param geometry1 \param_geometry
0356 \param geometry2 \param_geometry
0357 \param strategy point in geometry strategy
0358  */
0359 template
0360 <
0361     bool Reverse1, bool Reverse2,
0362     overlay_type OverlayType,
0363     typename Turns,
0364     typename Clusters,
0365     typename Geometry1, typename Geometry2,
0366     typename IntersectionStrategy
0367 >
0368 inline void enrich_intersection_points(Turns& turns,
0369     Clusters& clusters,
0370     Geometry1 const& geometry1, Geometry2 const& geometry2,
0371     IntersectionStrategy const& strategy)
0372 {
0373     constexpr detail::overlay::operation_type target_operation
0374             = detail::overlay::operation_from_overlay<OverlayType>::value;
0375     constexpr detail::overlay::operation_type opposite_operation
0376             = target_operation == detail::overlay::operation_union
0377             ? detail::overlay::operation_intersection
0378             : detail::overlay::operation_union;
0379     constexpr bool is_dissolve = OverlayType == overlay_dissolve;
0380
0381     // Turns are often used by index (in clusters, next_index, etc)
0382     // and turns may therefore NOT be DELETED - they may only be flagged as discarded
0383
0384     discard_duplicate_turns(turns, geometry1, geometry2);
0385
0386     bool has_cc = false;
0387
0388     // Discard turns not part of target overlay
0389     for (auto& turn : turns)
0390     {
0391         if (turn.both(detail::overlay::operation_none)
0392             || turn.both(opposite_operation)
0393             || turn.both(detail::overlay::operation_blocked)
0394             || (detail::overlay::is_self_turn<OverlayType>(turn)
0395                 && ! turn.is_clustered()
0396                 && ! turn.both(target_operation)))
0397         {
0398             // For all operations, discard xx and none/none
0399             // For intersections, remove uu to avoid the need to travel
0400             // a union (during intersection) in uu/cc clusters (e.g. #31,#32,#33)
0401
0402             // Similarly, for union, discard ii and ix
0403
0404             // For self-turns, only keep uu / ii
0405
0406             turn.discarded = true;
0407             turn.cluster_id = -1;
0408             continue;
0409         }
0410
0411         if (! turn.discarded
0412             && turn.both(detail::overlay::operation_continue))
0413         {
0414             has_cc = true;
0415         }
0416     }
0417
0418     if (! is_dissolve)
0419     {
0420         detail::overlay::discard_closed_turns
0421             <
0422                 OverlayType,
0423                 target_operation
0424             >::apply(turns, clusters, geometry1, geometry2,
0425                      strategy);
0426         detail::overlay::discard_open_turns
0427             <
0428                 OverlayType,
0429                 target_operation
0430             >::apply(turns, clusters, geometry1, geometry2,
0431                      strategy);
0432     }
0433
0434     if (! clusters.empty())
0435     {
0436         detail::overlay::cleanup_clusters(turns, clusters);
0437         detail::overlay::colocate_clusters(clusters, turns);
0438     }
0439
0440     // Create a map of vectors of indexed operation-types to be able
0441     // to sort intersection points PER RING
0442     auto mapped_vector = detail::overlay::create_map(turns,
0443                                 detail::overlay::enriched_map_default_include_policy());
0444
0445     for (auto& pair : mapped_vector)
0446     {
0447         detail::overlay::enrich_sort<Reverse1, Reverse2>(
0448                     pair.second, turns,
0449                     geometry1, geometry2,
0450                     strategy);
0451     }
0452
0453     // After cleaning up clusters assign the next turns
0454
0455     for (auto& pair : mapped_vector)
0456     {
0457 #ifdef BOOST_GEOMETRY_DEBUG_ENRICH
0458     std::cout << "ENRICH-assign Ring " << pair.first << std::endl;
0459 #endif
0460         if (is_dissolve)
0461         {
0462             detail::overlay::enrich_adapt(pair.second, turns);
0463         }
0464
0465         detail::overlay::enrich_assign(pair.second, turns);
0466     }
0467
0468     if (has_cc)
0469     {
0470         detail::overlay::calculate_remaining_distance(turns);
0471     }
0472
0473 #ifdef BOOST_GEOMETRY_DEBUG_ENRICH
0474     constexpr bool do_check_graph = true;
0475 #else
0476     constexpr bool do_check_graph = false;
0477 #endif
0478
0479     if BOOST_GEOMETRY_CONSTEXPR (do_check_graph)
0480     {
0481         detail::overlay::check_graph(turns, target_operation);
0482     }
0483 }
0484
0485 }} // namespace boost::geometry
0486
0487 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_ENRICH_HPP