Back to home page

EIC code displayed by LXR

 
 

    


File indexing completed on 2025-07-05 08:33:00

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-2021.
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_ENRICH_HPP
0015 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_ENRICH_HPP
0016 
0017 #include <cstddef>
0018 #include <algorithm>
0019 #include <map>
0020 #include <set>
0021 #include <vector>
0022 
0023 #ifdef BOOST_GEOMETRY_DEBUG_ENRICH
0024 #  include <iostream>
0025 #  include <boost/geometry/algorithms/detail/overlay/debug_turn_info.hpp>
0026 #  include <boost/geometry/io/wkt/wkt.hpp>
0027 #  if ! defined(BOOST_GEOMETRY_DEBUG_IDENTIFIER)
0028 #    define BOOST_GEOMETRY_DEBUG_IDENTIFIER
0029   #endif
0030 #endif
0031 
0032 #include <boost/range/begin.hpp>
0033 #include <boost/range/end.hpp>
0034 #include <boost/range/value_type.hpp>
0035 
0036 #include <boost/geometry/algorithms/detail/ring_identifier.hpp>
0037 #include <boost/geometry/algorithms/detail/overlay/discard_duplicate_turns.hpp>
0038 #include <boost/geometry/algorithms/detail/overlay/handle_colocations.hpp>
0039 #include <boost/geometry/algorithms/detail/overlay/handle_self_turns.hpp>
0040 #include <boost/geometry/algorithms/detail/overlay/is_self_turn.hpp>
0041 #include <boost/geometry/algorithms/detail/overlay/less_by_segment_ratio.hpp>
0042 #include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp>
0043 #include <boost/geometry/policies/robustness/robust_type.hpp>
0044 #include <boost/geometry/util/constexpr.hpp>
0045 #include <boost/geometry/util/for_each_with_index.hpp>
0046 
0047 #ifdef BOOST_GEOMETRY_DEBUG_ENRICH
0048 #  include <boost/geometry/algorithms/detail/overlay/check_enrich.hpp>
0049 #endif
0050 
0051 
0052 namespace boost { namespace geometry
0053 {
0054 
0055 #ifndef DOXYGEN_NO_DETAIL
0056 namespace detail { namespace overlay
0057 {
0058 
0059 template <typename Turns>
0060 struct discarded_indexed_turn
0061 {
0062     discarded_indexed_turn(Turns const& turns)
0063         : m_turns(turns)
0064     {}
0065 
0066     template <typename IndexedTurn>
0067     inline bool operator()(IndexedTurn const& indexed) const
0068     {
0069         return m_turns[indexed.turn_index].discarded;
0070     }
0071 
0072     Turns const& m_turns;
0073 };
0074 
0075 // Sorts IP-s of this ring on segment-identifier, and if on same segment,
0076 //  on distance.
0077 // Then assigns for each IP which is the next IP on this segment,
0078 // plus the vertex-index to travel to, plus the next IP
0079 // (might be on another segment)
0080 template
0081 <
0082     bool Reverse1, bool Reverse2,
0083     typename Operations,
0084     typename Turns,
0085     typename Geometry1, typename Geometry2,
0086     typename RobustPolicy,
0087     typename Strategy
0088 >
0089 inline void enrich_sort(Operations& operations,
0090             Turns const& turns,
0091             Geometry1 const& geometry1,
0092             Geometry2 const& geometry2,
0093             RobustPolicy const& robust_policy,
0094             Strategy const& strategy)
0095 {
0096     std::sort(std::begin(operations),
0097               std::end(operations),
0098               less_by_segment_ratio
0099                 <
0100                     Turns,
0101                     typename boost::range_value<Operations>::type,
0102                     Geometry1, Geometry2,
0103                     RobustPolicy,
0104                     Strategy,
0105                     Reverse1, Reverse2
0106                 >(turns, geometry1, geometry2, robust_policy, strategy));
0107 }
0108 
0109 
0110 // Assign travel-to-vertex/ip index for each turn.
0111 template <typename Operations, typename Turns>
0112 inline void enrich_assign(Operations& operations, Turns& turns,
0113                           bool check_consecutive_turns)
0114 {
0115     for_each_with_index(operations, [&](std::size_t index, auto const& indexed)
0116     {
0117         auto& turn = turns[indexed.turn_index];
0118         auto& op = turn.operations[indexed.operation_index];
0119 
0120         std::size_t next_index = index + 1 < operations.size() ? index + 1 : 0;
0121         auto advance = [&operations](auto index)
0122         {
0123             std::size_t const result = index + 1;
0124             return result >= operations.size() ? 0 : result;
0125         };
0126 
0127         auto next_turn = [&operations, &turns, &next_index]()
0128         {
0129             return turns[operations[next_index].turn_index];
0130         };
0131         auto next_operation = [&operations, &turns, &next_index]()
0132         {
0133             auto const& next_turn = turns[operations[next_index].turn_index];
0134             return next_turn.operations[operations[next_index].operation_index];
0135         };
0136 
0137         if (check_consecutive_turns
0138             && indexed.turn_index == operations[next_index].turn_index
0139             && op.seg_id == next_operation().seg_id)
0140         {
0141             // If the two operations on the same turn are ordered consecutively,
0142             // and they are on the same segment, then the turn where to travel to should
0143             // be considered one further. Therefore next is increased.
0144             //
0145             // It often happens in buffer, in these configurations:
0146             // +---->--+
0147             // |       |
0148             // |   +->-*---->
0149             // |   |   |
0150             // ^   +-<-+
0151             // If the next index is not corrected, the small rectangle
0152             // will be kept in the output.
0153 
0154             // This is a normal situation and occurs, for example, in every concave bend.
0155             // In general it should always travel from turn to next turn.
0156             // Only in some circumstances traveling to the same turn is necessary, for example
0157             // if there is only one turn in the outer ring.
0158             //
0159             // (For dissolve this is not done, turn_index is often
0160             // the same for two consecutive operations - but the conditions are changed
0161             // and this should be verified again)
0162             next_index = advance(next_index);
0163         }
0164 
0165         // Cluster behaviour: next should point after cluster, unless
0166         // their seg_ids are not the same
0167         // (For dissolve, this is still to be examined - TODO)
0168         while (turn.is_clustered()
0169                 && turn.cluster_id == next_turn().cluster_id
0170                 && op.seg_id == next_operation().seg_id
0171                 && indexed.turn_index != operations[next_index].turn_index)
0172         {
0173             next_index = advance(next_index);
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         auto const& next_op = next_operation();
0182         if (op.seg_id.segment_index == next_op.seg_id.segment_index
0183             && op.fraction < next_op.fraction)
0184         {
0185             // Next turn is located further on same segment: assign next_ip_index
0186             op.enriched.next_ip_index = static_cast<signed_size_type>(operations[next_index].turn_index);
0187         }
0188     });
0189 
0190 #ifdef BOOST_GEOMETRY_DEBUG_ENRICH
0191     for (auto const& indexed_op : operations)
0192     {
0193         auto const& op = turns[indexed_op.turn_index].operations[indexed_op.operation_index];
0194 
0195         std::cout << indexed_op.turn_index
0196             << " cl=" << turns[indexed_op.turn_index].cluster_id
0197             << " meth=" << method_char(turns[indexed_op.turn_index].method)
0198             << " seg=" << op.seg_id
0199             << " dst=" << op.fraction // needs define
0200             << " op=" << operation_char(turns[indexed_op.turn_index].operations[0].operation)
0201             << operation_char(turns[indexed_op.turn_index].operations[1].operation)
0202             << " (" << operation_char(op.operation) << ")"
0203             << " nxt=" << op.enriched.next_ip_index
0204             << " / " << op.enriched.travels_to_ip_index
0205             << " [vx " << op.enriched.travels_to_vertex_index << "]"
0206             << (turns[indexed_op.turn_index].discarded ? " [discarded]" : "")
0207             << (op.enriched.startable ? "" : " [not startable]")
0208             << std::endl;
0209     }
0210 #endif
0211 }
0212 
0213 template <typename Operations, typename Turns>
0214 inline void enrich_adapt(Operations& operations, Turns& turns)
0215 {
0216     // Operations is a vector of indexed_turn_operation<>
0217     // If it is empty, or contains one or two items, it makes no sense
0218     if (operations.size() < 3)
0219     {
0220         return;
0221     }
0222 
0223     bool next_phase = false;
0224     std::size_t previous_index = operations.size() - 1;
0225 
0226     for_each_with_index(operations, [&](std::size_t index, auto const& indexed)
0227     {
0228         auto& turn = turns[indexed.turn_index];
0229         auto& op = turn.operations[indexed.operation_index];
0230 
0231         std::size_t const next_index = index + 1 < operations.size() ? index + 1 : 0;
0232         auto const& next_turn = turns[operations[next_index].turn_index];
0233         auto const& next_op = next_turn.operations[operations[next_index].operation_index];
0234 
0235         if (op.seg_id.segment_index == next_op.seg_id.segment_index)
0236         {
0237             auto const& prev_turn = turns[operations[previous_index].turn_index];
0238             auto const& prev_op = prev_turn.operations[operations[previous_index].operation_index];
0239             if (op.seg_id.segment_index == prev_op.seg_id.segment_index)
0240             {
0241                 op.enriched.startable = false;
0242                 next_phase = true;
0243             }
0244         }
0245         previous_index = index;
0246     });
0247 
0248     if (! next_phase)
0249     {
0250         return;
0251     }
0252 
0253     // Discard turns which are both non-startable
0254     next_phase = false;
0255     for (auto& turn : turns)
0256     {
0257         if (! turn.operations[0].enriched.startable
0258             && ! turn.operations[1].enriched.startable)
0259         {
0260             turn.discarded = true;
0261             next_phase = true;
0262         }
0263     }
0264 
0265     if (! next_phase)
0266     {
0267         return;
0268     }
0269 
0270     // Remove discarded turns from operations to avoid having them as next turn
0271     discarded_indexed_turn<Turns> const predicate(turns);
0272     operations.erase(std::remove_if(std::begin(operations),
0273         std::end(operations), predicate), std::end(operations));
0274 }
0275 
0276 struct enriched_map_default_include_policy
0277 {
0278     template <typename Operation>
0279     static inline bool include(Operation const& )
0280     {
0281         // By default include all operations
0282         return true;
0283     }
0284 };
0285 
0286 // Add all (non discarded) operations on this ring
0287 // Blocked operations or uu on clusters (for intersection)
0288 // should be included, to block potential paths in clusters
0289 template <typename Turns, typename MappedVector, typename IncludePolicy>
0290 inline void create_map(Turns const& turns, MappedVector& mapped_vector,
0291                        IncludePolicy const& include_policy)
0292 {
0293     for_each_with_index(turns, [&](std::size_t index, auto const& turn)
0294     {
0295         if (! turn.discarded)
0296         {
0297             for_each_with_index(turn.operations, [&](std::size_t op_index, auto const& op)
0298             {
0299                 if (include_policy.include(op.operation))
0300                 {
0301                     ring_identifier const ring_id
0302                         (
0303                             op.seg_id.source_index,
0304                             op.seg_id.multi_index,
0305                             op.seg_id.ring_index
0306                         );
0307                     mapped_vector[ring_id].emplace_back
0308                         (
0309                             index, op_index, op, turn.operations[1 - op_index].seg_id
0310                         );
0311                 }
0312             });
0313         }
0314     });
0315 }
0316 
0317 template <typename Point1, typename Point2>
0318 inline typename geometry::coordinate_type<Point1>::type
0319         distance_measure(Point1 const& a, Point2 const& b)
0320 {
0321     // TODO: use comparable distance for point-point instead - but that
0322     // causes currently cycling include problems
0323     using ctype = typename geometry::coordinate_type<Point1>::type;
0324     ctype const dx = get<0>(a) - get<0>(b);
0325     ctype const dy = get<1>(a) - get<1>(b);
0326     return dx * dx + dy * dy;
0327 }
0328 
0329 template <typename Turns>
0330 inline void calculate_remaining_distance(Turns& turns)
0331 {
0332     for (auto& turn : turns)
0333     {
0334         auto& op0 = turn.operations[0];
0335         auto& op1 = turn.operations[1];
0336 
0337         static decltype(op0.remaining_distance) const zero_distance = 0;
0338 
0339         if (op0.remaining_distance != zero_distance
0340             || op1.remaining_distance != zero_distance)
0341         {
0342             continue;
0343         }
0344 
0345         auto const to_index0 = op0.enriched.get_next_turn_index();
0346         auto const to_index1 = op1.enriched.get_next_turn_index();
0347         if (to_index0 >= 0
0348             && to_index1 >= 0
0349             && to_index0 != to_index1)
0350         {
0351             op0.remaining_distance = distance_measure(turn.point, turns[to_index0].point);
0352             op1.remaining_distance = distance_measure(turn.point, turns[to_index1].point);
0353         }
0354     }
0355 }
0356 
0357 
0358 }} // namespace detail::overlay
0359 #endif //DOXYGEN_NO_DETAIL
0360 
0361 
0362 
0363 /*!
0364 \brief All intersection points are enriched with successor information
0365 \ingroup overlay
0366 \tparam Turns type of intersection container
0367             (e.g. vector of "intersection/turn point"'s)
0368 \tparam Clusters type of cluster container
0369 \tparam Geometry1 \tparam_geometry
0370 \tparam Geometry2 \tparam_geometry
0371 \tparam PointInGeometryStrategy point in geometry strategy type
0372 \param turns container containing intersection points
0373 \param clusters container containing clusters
0374 \param geometry1 \param_geometry
0375 \param geometry2 \param_geometry
0376 \param robust_policy policy to handle robustness issues
0377 \param strategy point in geometry strategy
0378  */
0379 template
0380 <
0381     bool Reverse1, bool Reverse2,
0382     overlay_type OverlayType,
0383     typename Turns,
0384     typename Clusters,
0385     typename Geometry1, typename Geometry2,
0386     typename RobustPolicy,
0387     typename IntersectionStrategy
0388 >
0389 inline void enrich_intersection_points(Turns& turns,
0390     Clusters& clusters,
0391     Geometry1 const& geometry1, Geometry2 const& geometry2,
0392     RobustPolicy const& robust_policy,
0393     IntersectionStrategy const& strategy)
0394 {
0395     constexpr detail::overlay::operation_type target_operation
0396             = detail::overlay::operation_from_overlay<OverlayType>::value;
0397     constexpr detail::overlay::operation_type opposite_operation
0398             = target_operation == detail::overlay::operation_union
0399             ? detail::overlay::operation_intersection
0400             : detail::overlay::operation_union;
0401     constexpr bool is_dissolve = OverlayType == overlay_dissolve;
0402     constexpr bool is_buffer = OverlayType == overlay_buffer;
0403 
0404     using turn_type = typename boost::range_value<Turns>::type;
0405     using indexed_turn_operation = detail::overlay::indexed_turn_operation
0406         <
0407             typename turn_type::turn_operation_type
0408         > ;
0409 
0410     using mapped_vector_type = std::map
0411         <
0412             ring_identifier,
0413             std::vector<indexed_turn_operation>
0414         >;
0415 
0416     // Turns are often used by index (in clusters, next_index, etc)
0417     // and turns may therefore NOT be DELETED - they may only be flagged as discarded
0418 
0419     bool has_cc = false;
0420     bool has_colocations = false;
0421 
0422     if BOOST_GEOMETRY_CONSTEXPR (! is_buffer)
0423     {
0424         // Handle colocations, gathering clusters and (below) their properties.
0425         has_colocations = detail::overlay::handle_colocations
0426                     <
0427                         Reverse1, Reverse2, OverlayType, Geometry1, Geometry2
0428                     >(turns, clusters, robust_policy);
0429         // Gather cluster properties (using even clusters with
0430         // discarded turns - for open turns)
0431         detail::overlay::gather_cluster_properties
0432             <
0433                 Reverse1,
0434                 Reverse2,
0435                 OverlayType
0436             >(clusters, turns, target_operation,
0437             geometry1, geometry2, strategy);
0438     }
0439     else
0440     {
0441         // For buffer, this was already done before calling enrich_intersection_points.
0442         has_colocations = ! clusters.empty();
0443     }
0444 
0445     discard_duplicate_start_turns(turns, geometry1, geometry2);
0446 
0447     // Discard turns not part of target overlay
0448     for (auto& turn : turns)
0449     {
0450         if (turn.both(detail::overlay::operation_none)
0451             || turn.both(opposite_operation)
0452             || turn.both(detail::overlay::operation_blocked)
0453             || (detail::overlay::is_self_turn<OverlayType>(turn)
0454                 && ! turn.is_clustered()
0455                 && ! turn.both(target_operation)))
0456         {
0457             // For all operations, discard xx and none/none
0458             // For intersections, remove uu to avoid the need to travel
0459             // a union (during intersection) in uu/cc clusters (e.g. #31,#32,#33)
0460             // The ux is necessary to indicate impossible paths
0461             // (especially if rescaling is removed)
0462 
0463             // Similarly, for union, discard ii and ix
0464 
0465             // For self-turns, only keep uu / ii
0466 
0467             turn.discarded = true;
0468             turn.cluster_id = -1;
0469             continue;
0470         }
0471 
0472         if (! turn.discarded
0473             && turn.both(detail::overlay::operation_continue))
0474         {
0475             has_cc = true;
0476         }
0477     }
0478 
0479     if (! is_dissolve)
0480     {
0481         detail::overlay::discard_closed_turns
0482             <
0483                 OverlayType,
0484                 target_operation
0485             >::apply(turns, clusters, geometry1, geometry2,
0486                      strategy);
0487         detail::overlay::discard_open_turns
0488             <
0489                 OverlayType,
0490                 target_operation
0491             >::apply(turns, clusters, geometry1, geometry2,
0492                      strategy);
0493     }
0494 
0495     // Create a map of vectors of indexed operation-types to be able
0496     // to sort intersection points PER RING
0497     mapped_vector_type mapped_vector;
0498 
0499     detail::overlay::create_map(turns, mapped_vector,
0500                                 detail::overlay::enriched_map_default_include_policy());
0501 
0502     for (auto& pair : mapped_vector)
0503     {
0504         detail::overlay::enrich_sort<Reverse1, Reverse2>(
0505                     pair.second, turns,
0506                     geometry1, geometry2,
0507                     robust_policy, strategy);
0508     }
0509 
0510     if (has_colocations)
0511     {
0512         detail::overlay::cleanup_clusters(turns, clusters);
0513         detail::overlay::colocate_clusters(clusters, turns);
0514     }
0515 
0516     // After cleaning up clusters assign the next turns
0517 
0518     for (auto& pair : mapped_vector)
0519     {
0520 #ifdef BOOST_GEOMETRY_DEBUG_ENRICH
0521     std::cout << "ENRICH-assign Ring " << pair.first << std::endl;
0522 #endif
0523         if (is_dissolve)
0524         {
0525             detail::overlay::enrich_adapt(pair.second, turns);
0526         }
0527 
0528         detail::overlay::enrich_assign(pair.second, turns, ! is_dissolve);
0529     }
0530 
0531     if (has_cc)
0532     {
0533         detail::overlay::calculate_remaining_distance(turns);
0534     }
0535 
0536 #ifdef BOOST_GEOMETRY_DEBUG_ENRICH
0537     //detail::overlay::check_graph(turns, for_operation);
0538 #endif
0539 
0540 }
0541 
0542 }} // namespace boost::geometry
0543 
0544 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_ENRICH_HPP