ceph/src/boost/libs/geometry/include/boost/geometry/algorithms/detail/overlay/backtrack_check_si.hpp

   1 // Boost.Geometry (aka GGL, Generic Geometry Library)
   2
   3 // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
   4
   5 // Use, modification and distribution is subject to the Boost Software License,
   6 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   7 // http://www.boost.org/LICENSE_1_0.txt)
   8
   9 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_BACKTRACK_CHECK_SI_HPP
  10 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_BACKTRACK_CHECK_SI_HPP
  11
  12 #include <cstddef>
  13 #include <string>
  14
  15 #include <boost/range.hpp>
  16
  17 #include <boost/geometry/core/access.hpp>
  18 #include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
  19 #include <boost/geometry/algorithms/detail/has_self_intersections.hpp>
  20 #if defined(BOOST_GEOMETRY_DEBUG_INTERSECTION) || defined(BOOST_GEOMETRY_OVERLAY_REPORT_WKT)
  21 #  include <boost/geometry/algorithms/detail/overlay/debug_turn_info.hpp>
  22 #  include <boost/geometry/io/wkt/wkt.hpp>
  23 #endif
  24
  25 namespace boost { namespace geometry
  26 {
  27
  28 #ifndef DOXYGEN_NO_DETAIL
  29 namespace detail { namespace overlay
  30 {
  31
  32 template <typename Turns>
  33 inline void clear_visit_info(Turns& turns)
  34 {
  35     typedef typename boost::range_value<Turns>::type tp_type;
  36
  37     for (typename boost::range_iterator<Turns>::type
  38         it = boost::begin(turns);
  39         it != boost::end(turns);
  40         ++it)
  41     {
  42         for (typename boost::range_iterator
  43             <
  44                 typename tp_type::container_type
  45             >::type op_it = boost::begin(it->operations);
  46             op_it != boost::end(it->operations);
  47             ++op_it)
  48         {
  49             op_it->visited.clear();
  50         }
  51     }
  52 }
  53
  54 struct backtrack_state
  55 {
  56     bool m_good;
  57
  58     inline backtrack_state() : m_good(true) {}
  59     inline void reset() { m_good = true; }
  60     inline bool good() const { return m_good; }
  61 };
  62
  63
  64 enum traverse_error_type
  65 {
  66     traverse_error_none,
  67     traverse_error_no_next_ip_at_start,
  68     traverse_error_no_next_ip,
  69     traverse_error_dead_end_at_start,
  70     traverse_error_dead_end,
  71     traverse_error_visit_again,
  72     traverse_error_endless_loop
  73 };
  74
  75 inline std::string traverse_error_string(traverse_error_type error)
  76 {
  77     switch (error)
  78     {
  79         case traverse_error_none : return "";
  80         case traverse_error_no_next_ip_at_start : return "No next IP at start";
  81         case traverse_error_no_next_ip : return "No next IP";
  82         case traverse_error_dead_end_at_start : return "Dead end at start";
  83         case traverse_error_dead_end : return "Dead end";
  84         case traverse_error_visit_again : return "Visit again";
  85         case traverse_error_endless_loop : return "Endless loop";
  86         default : return "";
  87     }
  88     return "";
  89 }
  90
  91
  92 template
  93 <
  94     typename Geometry1,
  95     typename Geometry2
  96 >
  97 class backtrack_check_self_intersections
  98 {
  99     struct state : public backtrack_state
 100     {
 101         bool m_checked;
 102         inline state()
 103             : m_checked(true)
 104         {}
 105     };
 106 public :
 107     typedef state state_type;
 108
 109     template <typename Operation, typename Rings, typename Ring, typename Turns, typename RobustPolicy, typename Visitor>
 110     static inline void apply(std::size_t size_at_start,
 111                 Rings& rings, Ring& ring,
 112                 Turns& turns,
 113                 typename boost::range_value<Turns>::type const& turn,
 114                 Operation& operation,
 115                 traverse_error_type traverse_error,
 116                 Geometry1 const& geometry1,
 117                 Geometry2 const& geometry2,
 118                 RobustPolicy const& robust_policy,
 119                 state_type& state,
 120                 Visitor& visitor
 121                 )
 122     {
 123         visitor.visit_traverse_reject(turns, turn, operation, traverse_error);
 124
 125         state.m_good = false;
 126
 127         // Check self-intersections and throw exception if appropriate
 128         if (! state.m_checked)
 129         {
 130             state.m_checked = true;
 131             has_self_intersections(geometry1, robust_policy);
 132             has_self_intersections(geometry2, robust_policy);
 133         }
 134
 135         // Make bad output clean
 136         rings.resize(size_at_start);
 137         geometry::traits::clear<typename boost::range_value<Rings>::type>::apply(ring);
 138
 139         // Reject this as a starting point
 140         operation.visited.set_rejected();
 141
 142         // And clear all visit info
 143         clear_visit_info(turns);
 144     }
 145 };
 146
 147 #ifdef BOOST_GEOMETRY_OVERLAY_REPORT_WKT
 148 template
 149 <
 150     typename Geometry1,
 151     typename Geometry2
 152 >
 153 class backtrack_debug
 154 {
 155 public :
 156     typedef backtrack_state state_type;
 157
 158     template <typename Operation, typename Rings, typename Turns>
 159     static inline void apply(std::size_t size_at_start,
 160                 Rings& rings, typename boost::range_value<Rings>::type& ring,
 161                 Turns& turns, Operation& operation,
 162                 std::string const& reason,
 163                 Geometry1 const& geometry1,
 164                 Geometry2 const& geometry2,
 165                 state_type& state
 166                 )
 167     {
 168         std::cout << " REJECT " << reason << std::endl;
 169
 170         state.m_good = false;
 171
 172         rings.resize(size_at_start);
 173         ring.clear();
 174         operation.visited.set_rejected();
 175         clear_visit_info(turns);
 176
 177         int c = 0;
 178         for (int i = 0; i < turns.size(); i++)
 179         {
 180             for (int j = 0; j < 2; j++)
 181             {
 182                 if (turns[i].operations[j].visited.rejected())
 183                 {
 184                     c++;
 185                 }
 186             }
 187         }
 188         std::cout << "BACKTRACK (" << reason << " )"
 189             << " " << c << " of " << turns.size() << " rejected"
 190             << std::endl;
 191         std::cout
 192             << geometry::wkt(geometry1) << std::endl
 193             << geometry::wkt(geometry2) << std::endl;
 194     }
 195 };
 196 #endif // BOOST_GEOMETRY_OVERLAY_REPORT_WKT
 197
 198 }} // namespace detail::overlay
 199 #endif // DOXYGEN_NO_DETAIL
 200
 201 }} // namespace boost::geometry
 202
 203 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_BACKTRACK_CHECK_SI_HPP