ceph/src/boost/libs/geometry/include/boost/geometry/algorithms/detail/has_self_intersections.hpp

   1 // Boost.Geometry (aka GGL, Generic Geometry Library)
   2
   3 // Copyright (c) 2011-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_HAS_SELF_INTERSECTIONS_HPP
  10 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_HAS_SELF_INTERSECTIONS_HPP
  11
  12 #include <deque>
  13
  14 #include <boost/range.hpp>
  15 #include <boost/geometry/core/point_type.hpp>
  16 #include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
  17 #include <boost/geometry/algorithms/detail/overlay/get_turns.hpp>
  18 #include <boost/geometry/algorithms/detail/overlay/self_turn_points.hpp>
  19
  20 #include <boost/geometry/policies/disjoint_interrupt_policy.hpp>
  21 #include <boost/geometry/policies/robustness/robust_point_type.hpp>
  22 #include <boost/geometry/policies/robustness/segment_ratio_type.hpp>
  23 #include <boost/geometry/policies/robustness/get_rescale_policy.hpp>
  24
  25 #ifdef BOOST_GEOMETRY_DEBUG_HAS_SELF_INTERSECTIONS
  26 #  include <boost/geometry/algorithms/detail/overlay/debug_turn_info.hpp>
  27 #  include <boost/geometry/io/dsv/write.hpp>
  28 #endif
  29
  30
  31 namespace boost { namespace geometry
  32 {
  33
  34
  35 #if ! defined(BOOST_GEOMETRY_OVERLAY_NO_THROW)
  36
  37 /*!
  38 \brief Overlay Invalid Input Exception
  39 \ingroup overlay
  40 \details The overlay_invalid_input_exception is thrown at invalid input
  41  */
  42 class overlay_invalid_input_exception : public geometry::exception
  43 {
  44 public:
  45
  46     inline overlay_invalid_input_exception() {}
  47
  48     virtual char const* what() const throw()
  49     {
  50         return "Boost.Geometry Overlay invalid input exception";
  51     }
  52 };
  53
  54 #endif
  55
  56
  57 #ifndef DOXYGEN_NO_DETAIL
  58 namespace detail { namespace overlay
  59 {
  60
  61
  62 template <typename Geometry, typename RobustPolicy>
  63 inline bool has_self_intersections(Geometry const& geometry,
  64         RobustPolicy const& robust_policy,
  65         bool throw_on_self_intersection = true)
  66 {
  67     typedef typename point_type<Geometry>::type point_type;
  68     typedef turn_info
  69     <
  70         point_type,
  71         typename segment_ratio_type<point_type, RobustPolicy>::type
  72     > turn_info;
  73     std::deque<turn_info> turns;
  74     detail::disjoint::disjoint_interrupt_policy policy;
  75
  76     geometry::self_turns<detail::overlay::assign_null_policy>(geometry, robust_policy, turns, policy);
  77
  78 #ifdef BOOST_GEOMETRY_DEBUG_HAS_SELF_INTERSECTIONS
  79     bool first = true;
  80 #endif
  81     for(typename std::deque<turn_info>::const_iterator it = boost::begin(turns);
  82         it != boost::end(turns); ++it)
  83     {
  84         turn_info const& info = *it;
  85         bool const both_union_turn =
  86             info.operations[0].operation == detail::overlay::operation_union
  87             && info.operations[1].operation == detail::overlay::operation_union;
  88         bool const both_intersection_turn =
  89             info.operations[0].operation == detail::overlay::operation_intersection
  90             && info.operations[1].operation == detail::overlay::operation_intersection;
  91
  92         bool const valid = (both_union_turn || both_intersection_turn)
  93             && (info.method == detail::overlay::method_touch
  94                 || info.method == detail::overlay::method_touch_interior);
  95
  96         if (! valid)
  97         {
  98 #ifdef BOOST_GEOMETRY_DEBUG_HAS_SELF_INTERSECTIONS
  99             if (first)
 100             {
 101                 std::cout << "turn points: " << std::endl;
 102                 first = false;
 103             }
 104             std::cout << method_char(info.method);
 105             for (int i = 0; i < 2; i++)
 106             {
 107                 std::cout << " " << operation_char(info.operations[i].operation);
 108                 std::cout << " " << info.operations[i].seg_id;
 109             }
 110             std::cout << " " << geometry::dsv(info.point) << std::endl;
 111 #endif
 112
 113 #if ! defined(BOOST_GEOMETRY_OVERLAY_NO_THROW)
 114             if (throw_on_self_intersection)
 115             {
 116                 throw overlay_invalid_input_exception();
 117             }
 118 #endif
 119             return true;
 120         }
 121
 122     }
 123     return false;
 124 }
 125
 126 // For backward compatibility
 127 template <typename Geometry>
 128 inline bool has_self_intersections(Geometry const& geometry,
 129                     bool throw_on_self_intersection = true)
 130 {
 131     typedef typename geometry::point_type<Geometry>::type point_type;
 132     typedef typename geometry::rescale_policy_type<point_type>::type
 133         rescale_policy_type;
 134
 135     rescale_policy_type robust_policy
 136             = geometry::get_rescale_policy<rescale_policy_type>(geometry);
 137
 138     return has_self_intersections(geometry, robust_policy,
 139                 throw_on_self_intersection);
 140 }
 141
 142
 143 }} // namespace detail::overlay
 144 #endif // DOXYGEN_NO_DETAIL
 145
 146
 147 }} // namespace boost::geometry
 148
 149
 150 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_HAS_SELF_INTERSECTIONS_HPP
 151