detail/overlay/cluster_exits.hpp

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