detail/overlay/cluster_exits.hpp

0001 // Boost.Geometry (aka GGL, Generic Geometry Library)
0002
0003 // Copyright (c) 2020 Barend Gehrels, Amsterdam, the Netherlands.
0004 // Copyright (c) 2023 Adam Wulkiewicz, Lodz, Poland.
0005
0006 // This file was modified by Oracle on 2020-2023.
0007 // Modifications copyright (c) 2020-2023 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_CLUSTER_EXITS_HPP
0016 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_CLUSTER_EXITS_HPP
0017
0018 #include <cstddef>
0019 #include <set>
0020 #include <vector>
0021
0022 #include <boost/range/value_type.hpp>
0023
0024 #include <boost/geometry/core/assert.hpp>
0025 #include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp>
0026 #include <boost/geometry/algorithms/detail/overlay/sort_by_side.hpp>
0027 #include <boost/geometry/algorithms/detail/signed_size_type.hpp>
0028 #include <boost/geometry/util/constexpr.hpp>
0029
0030 #if defined(BOOST_GEOMETRY_DEBUG_INTERSECTION) \
0031     || defined(BOOST_GEOMETRY_OVERLAY_REPORT_WKT) \
0032     || defined(BOOST_GEOMETRY_DEBUG_TRAVERSE)
0033 #  include <string>
0034 #  include <boost/geometry/algorithms/detail/overlay/debug_turn_info.hpp>
0035 #  include <boost/geometry/io/wkt/wkt.hpp>
0036 #endif
0037
0038 namespace boost { namespace geometry
0039 {
0040
0041 #ifndef DOXYGEN_NO_DETAIL
0042 namespace detail { namespace overlay
0043 {
0044
0045 // Structure to check relatively simple cluster cases
0046 template <overlay_type OverlayType,
0047           typename Turns,
0048           typename Sbs>
0049 struct cluster_exits
0050 {
0051 private :
0052     static const operation_type target_operation = operation_from_overlay<OverlayType>::value;
0053     typedef typename boost::range_value<Turns>::type turn_type;
0054     typedef typename turn_type::turn_operation_type turn_operation_type;
0055
0056     struct linked_turn_op_info
0057     {
0058         explicit linked_turn_op_info(signed_size_type ti = -1, int oi = -1,
0059                     signed_size_type nti = -1)
0060             : turn_index(ti)
0061             , op_index(oi)
0062             , next_turn_index(nti)
0063             , rank_index(-1)
0064         {}
0065
0066         signed_size_type turn_index;
0067         int op_index;
0068         signed_size_type next_turn_index;
0069         signed_size_type rank_index;
0070     };
0071
0072     inline signed_size_type get_rank(Sbs const& sbs,
0073             linked_turn_op_info const& info) const
0074     {
0075         for (auto const& rp : sbs.m_ranked_points)
0076         {
0077             if (rp.turn_index == info.turn_index
0078                     && rp.operation_index == info.op_index
0079                     && rp.direction == sort_by_side::dir_to)
0080             {
0081                 return rp.rank;
0082             }
0083         }
0084         return -1;
0085     }
0086
0087     std::set<signed_size_type> const& m_ids;
0088     std::vector<linked_turn_op_info> possibilities;
0089     std::vector<linked_turn_op_info> blocked;
0090
0091     bool m_valid;
0092
0093     bool collect(Turns const& turns)
0094     {
0095         for (auto cluster_turn_index : m_ids)
0096         {
0097             turn_type const& cluster_turn = turns[cluster_turn_index];
0098             if (cluster_turn.discarded)
0099             {
0100                 continue;
0101             }
0102             if (cluster_turn.both(target_operation))
0103             {
0104                 // Not (yet) supported, can be cluster of u/u turns
0105                 return false;
0106             }
0107             for (int i = 0; i < 2; i++)
0108             {
0109                 turn_operation_type const& op = cluster_turn.operations[i];
0110                 turn_operation_type const& other_op = cluster_turn.operations[1 - i];
0111                 signed_size_type const ni = op.enriched.get_next_turn_index();
0112
0113                 if (op.operation == target_operation
0114                     || op.operation == operation_continue)
0115                 {
0116                     if (ni == cluster_turn_index)
0117                     {
0118                         // Not (yet) supported, traveling to itself, can be
0119                         // hole
0120                         return false;
0121                     }
0122                     possibilities.push_back(
0123                         linked_turn_op_info(cluster_turn_index, i, ni));
0124                 }
0125                 else if (op.operation == operation_blocked
0126                          && ! (ni == other_op.enriched.get_next_turn_index())
0127                          && m_ids.count(ni) == 0)
0128                 {
0129                     // Points to turn, not part of this cluster,
0130                     // and that way is blocked. But if the other operation
0131                     // points at the same turn, it is still fine.
0132                     blocked.push_back(
0133                         linked_turn_op_info(cluster_turn_index, i, ni));
0134                 }
0135             }
0136         }
0137         return true;
0138     }
0139
0140     bool check_blocked(Sbs const& sbs)
0141     {
0142         if (blocked.empty())
0143         {
0144             return true;
0145         }
0146
0147         for (auto& info : possibilities)
0148         {
0149             info.rank_index = get_rank(sbs, info);
0150         }
0151         for (auto& info : blocked)
0152         {
0153             info.rank_index = get_rank(sbs, info);
0154         }
0155
0156         for (auto const& lti : possibilities)
0157         {
0158             for (auto const& blti : blocked)
0159             {
0160                 if (blti.next_turn_index == lti.next_turn_index
0161                         && blti.rank_index == lti.rank_index)
0162                 {
0163                     return false;
0164                 }
0165             }
0166         }
0167         return true;
0168     }
0169
0170 public :
0171     cluster_exits(Turns const& turns,
0172                   std::set<signed_size_type> const& ids,
0173                   Sbs const& sbs)
0174         : m_ids(ids)
0175         , m_valid(collect(turns) && check_blocked(sbs))
0176     {
0177     }
0178
0179     inline bool apply(signed_size_type& turn_index,
0180             int& op_index,
0181             bool first_run = true) const
0182     {
0183         if (! m_valid)
0184         {
0185             return false;
0186         }
0187
0188         // Traversal can either enter the cluster in the first turn,
0189         // or it can start halfway.
0190         // If there is one (and only one) possibility pointing outside
0191         // the cluster, take that one.
0192         linked_turn_op_info target;
0193         for (auto const& lti : possibilities)
0194         {
0195             if (m_ids.count(lti.next_turn_index) == 0)
0196             {
0197                 if (target.turn_index >= 0
0198                     && target.next_turn_index != lti.next_turn_index)
0199                 {
0200                     // Points to different target
0201                     return false;
0202                 }
0203                 if BOOST_GEOMETRY_CONSTEXPR (OverlayType == overlay_buffer)
0204                 {
0205                     if (first_run && target.turn_index >= 0)
0206                     {
0207                         // Target already assigned, so there are more targets
0208                         // or more ways to the same target
0209                         return false;
0210                     }
0211                 }
0212
0213                 target = lti;
0214             }
0215         }
0216         if (target.turn_index < 0)
0217         {
0218             return false;
0219         }
0220
0221         turn_index = target.turn_index;
0222         op_index = target.op_index;
0223
0224         return true;
0225     }
0226 };
0227
0228 }} // namespace detail::overlay
0229 #endif // DOXYGEN_NO_DETAIL
0230
0231 }} // namespace boost::geometry
0232
0233 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_CLUSTER_EXITS_HPP