overlay/graph/adapt_operations.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_ADAPT_OPERATIONS_HPP
0010 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_ADAPT_OPERATIONS_HPP
0011
0012 #include <boost/geometry/algorithms/detail/signed_size_type.hpp>
0013 #include <boost/geometry/algorithms/detail/overlay/debug_turn_info.hpp>
0014 #include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp>
0015 #include <boost/geometry/algorithms/detail/overlay/turn_operation_id.hpp>
0016
0017 namespace boost { namespace geometry
0018 {
0019
0020 #ifndef DOXYGEN_NO_DETAIL
0021 namespace detail { namespace overlay
0022 {
0023
0024 // Changes the operation of a UU turn, following a UX turn, to X (blocked)
0025 // under certain conditions, such that it is not followed
0026 // ADAPT: still necessary for just 2 cases. It should be possible to fix it in get_turn_info instead.
0027 // It happens in issue_1100_rev (union) and in ticket_10108 (sym diff)
0028 //
0029 // Situation sketch (issue_1100 reversed - the non reversed version does not need the workaround).
0030 //
0031 // +-----\   +--------+
0032 // |      \  |        |
0033 // |       \ |        |
0034 // |         + UX     |
0035 // |         |        |
0036 // |   P     |     Q  |
0037 // |         |        |
0038 // |         |        |
0039 // +---------+--------+
0040 //          UU            <- This UU turn is wrong, it should be UX
0041 //                           If it is UU, it will travel right (as designed) and polygon P will
0042 //                           not be part of the union.
0043 //
0044 template <typename Turns>
0045 void block_ux_uu_workaround(Turns& turns)
0046 {
0047     auto get_op_index = [](auto const& turn, auto&& lambda)
0048     {
0049         for (int i = 0; i < 2; i++)
0050         {
0051             if (lambda(turn.operations[i]))
0052             {
0053                 return i;
0054             }
0055         }
0056         return -1;
0057     };
0058
0059     for (std::size_t turn_index = 0; turn_index < turns.size(); turn_index++)
0060     {
0061         auto const& turn = turns[turn_index];
0062         if (turn.is_clustered()
0063             || turn.discarded
0064             || turn.is_self()
0065             || ! turn.combination(operation_blocked, operation_union))
0066         {
0067             continue;
0068         }
0069
0070         auto const blocked_index = get_op_index(turn, [](auto const& op)
0071             {
0072                 return op.operation == operation_blocked;
0073             });
0074
0075         auto const& blocked_op = turn.operations[blocked_index];
0076         auto const next_index = blocked_op.enriched.travels_to_ip_index;
0077         if (next_index < 0 || next_index >= static_cast<int>(turns.size()))
0078         {
0079             continue;
0080         }
0081
0082         auto& next_turn = turns[next_index];
0083         if (next_turn.is_self() || ! next_turn.both(operation_union))
0084         {
0085             // If it is a self-turn, they will both have the same source, and both are union.
0086             // The "other source" is then ambiguous.
0087             // It might be handled later, but only with extra conditions.
0088             continue;
0089         }
0090
0091         int const same_source_index = get_op_index(next_turn, [&](auto const& op)
0092             {
0093                 return op.seg_id.source_index == blocked_op.seg_id.source_index;
0094             });
0095
0096         if (same_source_index < 0)
0097         {
0098             continue;
0099         }
0100         int const other_index = 1 - same_source_index;
0101         auto& opposite_op = next_turn.operations[other_index];
0102         if (opposite_op.enriched.travels_to_ip_index != static_cast<signed_size_type>(turn_index))
0103         {
0104             // It is not opposite
0105             continue;
0106         }
0107
0108         opposite_op.operation = operation_blocked;
0109 #if defined(BOOST_GEOMETRY_DEBUG_TRAVERSE_GRAPH)
0110         std::cout << "BLOCK XU/UU at turns " << turn_index << "/" << next_index << std::endl;
0111 #endif
0112     }
0113 }
0114
0115 }} // namespace detail::overlay
0116 #endif // DOXYGEN_NO_DETAIL
0117
0118 }} // namespace boost::geometry
0119
0120 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_ADAPT_OPERATIONS_HPP