overlay/graph/is_target_operation.hpp

0001 // Boost.Geometry
0002
0003 // Copyright (c) 2025 Barend Gehrels, Amsterdam, the Netherlands.
0004
0005 // Use, modification and distribution is subject to the Boost Software License,
0006 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0007 // http://www.boost.org/LICENSE_1_0.txt)
0008
0009 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_GRAPH_IS_TARGET_OPERATION_HPP
0010 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_GRAPH_IS_TARGET_OPERATION_HPP
0011
0012 #include <boost/geometry/algorithms/detail/signed_size_type.hpp>
0013 #include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp>
0014 #include <boost/geometry/algorithms/detail/overlay/turn_operation_id.hpp>
0015
0016 #include <set>
0017 #include <utility>
0018
0019 namespace boost { namespace geometry
0020 {
0021
0022 #ifndef DOXYGEN_NO_DETAIL
0023 namespace detail { namespace overlay
0024 {
0025
0026 // For continue/continue cases where one of the targets
0027 // is the same as a target of the other target.
0028 // If is_target_ahead_op == true:
0029 // CC turn -------> target_op -----> target_other
0030 //         ------------------------> target_other
0031 // In this case, take the target_op
0032 template <typename Turns>
0033 std::pair<bool, bool> is_cc_target_ahead(Turns const& turns, turn_operation_id const& toi)
0034 {
0035     auto const& turn = turns[toi.turn_index];
0036     auto const& op = turn.operations[toi.operation_index];
0037     auto const& other_op = turn.operations[1 - toi.operation_index];
0038
0039     auto const target_op = op.enriched.travels_to_ip_index;
0040     auto const target_other = other_op.enriched.travels_to_ip_index;
0041
0042     auto const nop_result = std::make_pair(false, false);
0043
0044     if (target_op < 0 || target_other < 0 || target_op == target_other)
0045     {
0046         return nop_result;
0047     }
0048
0049     if (turn.is_clustered()
0050         && (turns[target_op].cluster_id == turn.cluster_id
0051             || turns[target_other].cluster_id == turn.cluster_id))
0052     {
0053         return nop_result;
0054     }
0055
0056     auto has_target = [](auto const& turn, signed_size_type target)
0057     {
0058         return turn.operations[0].enriched.travels_to_ip_index == target
0059             || turn.operations[1].enriched.travels_to_ip_index == target;
0060     };
0061
0062     bool const is_target_ahead_op = has_target(turns[target_op], target_other);
0063     bool const is_target_ahead_other = has_target(turns[target_other], target_op);
0064     if (is_target_ahead_op == is_target_ahead_other)
0065     {
0066         // It is not so that one is the target of the operation of the other,
0067         // or it is the case for both of them (this cannot be handled or
0068         // it does not occur).
0069         return nop_result;
0070     }
0071
0072 #if defined(BOOST_GEOMETRY_DEBUG_TRAVERSE_GRAPH)
0073     std::cout << "Decide for turn " << toi.turn_index << " " << toi.operation_index
0074         << " targets: " << target_op
0075         << " / " << target_other
0076         << " clusters: " << turns[target_op].cluster_id
0077         << " / " << turns[target_other].cluster_id
0078         << " via " << std::boolalpha << is_target_ahead_op << " / " << is_target_ahead_other
0079         << std::endl;
0080 #endif
0081
0082     return std::make_pair(true, is_target_ahead_op);
0083 }
0084
0085 template <typename Operation>
0086 bool is_better_collinear_for_union(Operation const& op, Operation const& other_op,
0087         turn_operation_id const& toi, turn_operation_id const& other_toi)
0088 {
0089     // Continue, prefer the one having no polygon on the left
0090     if (op.enriched.count_left > 0 && other_op.enriched.count_left == 0)
0091     {
0092         return false;
0093     }
0094     if (op.enriched.count_left == 0 && other_op.enriched.count_left > 0)
0095     {
0096         return true;
0097     }
0098
0099     // For union the cc target ahead should not be called.
0100
0101     // In some cases, one goes to a target further, while the other goes to a target closer,
0102     // and that target than goes to that same next target.
0103
0104     if (op.enriched.ahead_side != other_op.enriched.ahead_side)
0105     {
0106         // If one of them goes left (1), this one is preferred above collinear or right (-1),
0107         // whatever the distance.
0108         //                                ^
0109         //    (empty)                    /  going left
0110         //                              /
0111         // >----------------------------
0112         //                 \             .
0113         //    (polygon)     \  going right
0114         //                   v
0115         //
0116         // The left is also preferred above the other one going collinearly.
0117         // Finally, if one of them is collinear, it is preferred above the one going right.
0118
0119         return op.enriched.ahead_side > other_op.enriched.ahead_side;
0120     }
0121
0122     // If both have the same side, the preference depends on which side.
0123     // For a left turn (1), the one with the smallest distance is preferred.
0124     // For a right turn (-1), the one with the largest distance is preferred.
0125     // For collinear (0), it should not matter.
0126
0127     return
0128         op.enriched.ahead_side == 1
0129         ? op.enriched.ahead_distance_of_side_change
0130             <= other_op.enriched.ahead_distance_of_side_change
0131         : op.enriched.ahead_distance_of_side_change
0132             >= other_op.enriched.ahead_distance_of_side_change;
0133 }
0134
0135 // The same for intersection - but it needs turns for the same target ahead check.
0136 template <typename Operation, typename Turns>
0137 bool is_better_collinear_for_intersection(Operation const& op, Operation const& other_op,
0138         turn_operation_id const& toi, turn_operation_id const& other_toi, Turns const& turns)
0139 {
0140     // Continue, prefer the one having no polygon on the left
0141     if (op.enriched.count_right < 2 && other_op.enriched.count_right >= 2)
0142     {
0143         return false;
0144     }
0145     if (op.enriched.count_right >= 0 && other_op.enriched.count_right < 2)
0146     {
0147         return true;
0148     }
0149
0150     auto const target_ahead = is_cc_target_ahead(turns, toi);
0151     if (target_ahead.first)
0152     {
0153         return target_ahead.second;
0154     }
0155
0156     return op.enriched.ahead_distance_of_side_change
0157         <= other_op.enriched.ahead_distance_of_side_change;
0158 }
0159
0160 template <operation_type Operation>
0161 struct is_better_collinear_target {};
0162
0163 template <>
0164 struct is_better_collinear_target<operation_union>
0165 {
0166     template <typename Operation, typename Turns>
0167     static bool apply(Operation const& op, Operation const& other_op,
0168         turn_operation_id const& toi, turn_operation_id const& other_toi, Turns const&)
0169     {
0170         return is_better_collinear_for_union(op, other_op, toi, other_toi);
0171     }
0172 };
0173
0174 template <>
0175 struct is_better_collinear_target<operation_intersection>
0176 {
0177     template <typename Operation, typename Turns>
0178     static bool apply(Operation const& op, Operation const& other_op,
0179         turn_operation_id const& toi, turn_operation_id const& other_toi, Turns const& turns)
0180     {
0181         return is_better_collinear_for_intersection(op, other_op, toi, other_toi, turns);
0182     }
0183 };
0184
0185 template <operation_type TargetOperation, typename Turns>
0186 bool is_target_operation(Turns const& turns, turn_operation_id const& toi)
0187 {
0188     auto const& turn = turns[toi.turn_index];
0189     auto const& op = turn.operations[toi.operation_index];
0190     if (op.enriched.travels_to_ip_index < 0
0191         || op.enriched.travels_to_ip_index >= static_cast<int>(turns.size()))
0192     {
0193         return false;
0194     }
0195     if (op.operation == TargetOperation)
0196     {
0197         return true;
0198     }
0199     if (op.operation != operation_continue)
0200     {
0201         return false;
0202     }
0203
0204     turn_operation_id const other_toi{toi.turn_index, 1 - toi.operation_index};
0205     auto const& other_op = turn.operations[other_toi.operation_index];
0206     return is_better_collinear_target<TargetOperation>
0207         ::apply(op, other_op, toi, other_toi, turns);
0208 }
0209
0210 }} // namespace detail::overlay
0211 #endif // DOXYGEN_NO_DETAIL
0212
0213 }} // namespace boost::geometry
0214
0215 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_GRAPH_IS_TARGET_OPERATION_HPP