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