detail/overlay/backtrack_check_si.hpp

0001 // Boost.Geometry (aka GGL, Generic Geometry Library)
0002
0003 // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
0004
0005 // This file was modified by Oracle on 2017-2024.
0006 // Modifications copyright (c) 2017-2024, 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_BACKTRACK_CHECK_SI_HPP
0015 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_BACKTRACK_CHECK_SI_HPP
0016
0017 #include <cstddef>
0018 #include <string>
0019
0020 #include <boost/range/begin.hpp>
0021 #include <boost/range/end.hpp>
0022 #include <boost/range/value_type.hpp>
0023
0024 #include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
0025 #include <boost/geometry/algorithms/detail/has_self_intersections.hpp>
0026 #if defined(BOOST_GEOMETRY_DEBUG_INTERSECTION) || defined(BOOST_GEOMETRY_OVERLAY_REPORT_WKT)
0027 #  include <boost/geometry/algorithms/detail/overlay/debug_turn_info.hpp>
0028 #  include <boost/geometry/io/wkt/wkt.hpp>
0029 #endif
0030
0031 namespace boost { namespace geometry
0032 {
0033
0034 #ifndef DOXYGEN_NO_DETAIL
0035 namespace detail { namespace overlay
0036 {
0037
0038 template <typename Turns>
0039 inline void clear_visit_info(Turns& turns)
0040 {
0041     for (auto& turn : turns)
0042     {
0043         for (auto& op : turn.operations)
0044         {
0045             op.visited.clear();
0046         }
0047     }
0048 }
0049
0050 struct backtrack_state
0051 {
0052     bool m_good;
0053
0054     inline backtrack_state() : m_good(true) {}
0055     inline void reset() { m_good = true; }
0056     inline bool good() const { return m_good; }
0057 };
0058
0059
0060 enum traverse_error_type
0061 {
0062     traverse_error_none,
0063     traverse_error_no_next_ip_at_start,
0064     traverse_error_no_next_ip,
0065     traverse_error_dead_end_at_start,
0066     traverse_error_dead_end,
0067     traverse_error_visit_again,
0068     traverse_error_endless_loop
0069 };
0070
0071 inline std::string traverse_error_string(traverse_error_type error)
0072 {
0073     switch (error)
0074     {
0075         case traverse_error_none : return "";
0076         case traverse_error_no_next_ip_at_start : return "No next IP at start";
0077         case traverse_error_no_next_ip : return "No next IP";
0078         case traverse_error_dead_end_at_start : return "Dead end at start";
0079         case traverse_error_dead_end : return "Dead end";
0080         case traverse_error_visit_again : return "Visit again";
0081         case traverse_error_endless_loop : return "Endless loop";
0082         default : return "";
0083     }
0084     return "";
0085 }
0086
0087
0088 template
0089 <
0090     typename Geometry1,
0091     typename Geometry2
0092 >
0093 class backtrack_check_self_intersections
0094 {
0095     struct state : public backtrack_state
0096     {
0097         bool m_checked;
0098         inline state()
0099             : m_checked(true)
0100         {}
0101     };
0102 public :
0103     using state_type = state;
0104
0105     template
0106     <
0107         typename Operation,
0108         typename Rings, typename Ring, typename Turns,
0109         typename Strategy,
0110         typename Visitor
0111     >
0112     static inline void apply(std::size_t size_at_start,
0113                              Rings& rings,
0114                              Ring& ring,
0115                              Turns& turns,
0116                              typename boost::range_value<Turns>::type const& turn,
0117                              Operation& operation,
0118                              traverse_error_type traverse_error,
0119                              Geometry1 const& geometry1,
0120                              Geometry2 const& geometry2,
0121                              Strategy const& strategy,
0122                              state_type& state,
0123                              Visitor& visitor)
0124     {
0125         visitor.visit_traverse_reject(turns, turn, operation, traverse_error);
0126
0127         state.m_good = false;
0128
0129         // Check self-intersections and throw exception if appropriate
0130         if (! state.m_checked)
0131         {
0132             state.m_checked = true;
0133             has_self_intersections(geometry1, strategy);
0134             has_self_intersections(geometry2, strategy);
0135         }
0136
0137         // Make bad output clean
0138         rings.resize(size_at_start);
0139         geometry::traits::clear<typename boost::range_value<Rings>::type>::apply(ring);
0140
0141         // Reject this as a starting point
0142         operation.visited.set_rejected();
0143
0144         // And clear all visit info
0145         clear_visit_info(turns);
0146     }
0147 };
0148
0149 #ifdef BOOST_GEOMETRY_OVERLAY_REPORT_WKT
0150 template
0151 <
0152     typename Geometry1,
0153     typename Geometry2
0154 >
0155 class backtrack_debug
0156 {
0157 public :
0158     using state_type = backtrack_state;
0159
0160     template <typename Operation, typename Rings, typename Turns>
0161     static inline void apply(std::size_t size_at_start,
0162                 Rings& rings, typename boost::range_value<Rings>::type& ring,
0163                 Turns& turns, Operation& operation,
0164                 std::string const& reason,
0165                 Geometry1 const& geometry1,
0166                 Geometry2 const& geometry2,
0167                 state_type& state
0168                 )
0169     {
0170         std::cout << " REJECT " << reason << std::endl;
0171
0172         state.m_good = false;
0173
0174         rings.resize(size_at_start);
0175         ring.clear();
0176         operation.visited.set_rejected();
0177         clear_visit_info(turns);
0178
0179         int c = 0;
0180         for (int i = 0; i < turns.size(); i++)
0181         {
0182             for (int j = 0; j < 2; j++)
0183             {
0184                 if (turns[i].operations[j].visited.rejected())
0185                 {
0186                     c++;
0187                 }
0188             }
0189         }
0190         std::cout << "BACKTRACK (" << reason << " )"
0191             << " " << c << " of " << turns.size() << " rejected"
0192             << std::endl;
0193         std::cout
0194             << geometry::wkt(geometry1) << std::endl
0195             << geometry::wkt(geometry2) << std::endl;
0196     }
0197 };
0198 #endif // BOOST_GEOMETRY_OVERLAY_REPORT_WKT
0199
0200 }} // namespace detail::overlay
0201 #endif // DOXYGEN_NO_DETAIL
0202
0203 }} // namespace boost::geometry
0204
0205 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_BACKTRACK_CHECK_SI_HPP