1 // Boost.Geometry (aka GGL, Generic Geometry Library)
3 // Copyright (c) 2011-2012 Barend Gehrels, Amsterdam, the Netherlands.
4 // Copyright (c) 2017 Adam Wulkiewicz, Lodz, Poland.
6 // This file was modified by Oracle on 2017-2020.
7 // Modifications copyright (c) 2017-2020 Oracle and/or its affiliates.
8 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
10 // Use, modification and distribution is subject to the Boost Software License,
11 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
12 // http://www.boost.org/LICENSE_1_0.txt)
14 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_HAS_SELF_INTERSECTIONS_HPP
15 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_HAS_SELF_INTERSECTIONS_HPP
19 #include <boost/range/begin.hpp>
20 #include <boost/range/end.hpp>
21 #include <boost/throw_exception.hpp>
23 #include <boost/geometry/core/point_type.hpp>
24 #include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
25 #include <boost/geometry/algorithms/detail/overlay/get_turns.hpp>
26 #include <boost/geometry/algorithms/detail/overlay/self_turn_points.hpp>
28 #include <boost/geometry/policies/disjoint_interrupt_policy.hpp>
29 #include <boost/geometry/policies/robustness/robust_point_type.hpp>
30 #include <boost/geometry/policies/robustness/segment_ratio_type.hpp>
31 #include <boost/geometry/policies/robustness/get_rescale_policy.hpp>
33 #ifdef BOOST_GEOMETRY_DEBUG_HAS_SELF_INTERSECTIONS
34 # include <boost/geometry/algorithms/detail/overlay/debug_turn_info.hpp>
35 # include <boost/geometry/io/dsv/write.hpp>
39 namespace boost { namespace geometry
43 #if ! defined(BOOST_GEOMETRY_OVERLAY_NO_THROW)
46 \brief Overlay Invalid Input Exception
48 \details The overlay_invalid_input_exception is thrown at invalid input
50 class overlay_invalid_input_exception : public geometry::exception
54 inline overlay_invalid_input_exception() {}
56 virtual char const* what() const throw()
58 return "Boost.Geometry Overlay invalid input exception";
65 #ifndef DOXYGEN_NO_DETAIL
66 namespace detail { namespace overlay
70 template <typename Geometry, typename Strategy, typename RobustPolicy>
71 inline bool has_self_intersections(Geometry const& geometry,
72 Strategy const& strategy,
73 RobustPolicy const& robust_policy,
74 bool throw_on_self_intersection = true)
76 typedef typename point_type<Geometry>::type point_type;
80 typename segment_ratio_type<point_type, RobustPolicy>::type
82 std::deque<turn_info> turns;
83 detail::disjoint::disjoint_interrupt_policy policy;
85 detail::self_get_turn_points::self_turns
88 detail::overlay::assign_null_policy
89 >(geometry, strategy, robust_policy, turns, policy, 0, false);
91 #ifdef BOOST_GEOMETRY_DEBUG_HAS_SELF_INTERSECTIONS
94 for(typename std::deque<turn_info>::const_iterator it = boost::begin(turns);
95 it != boost::end(turns); ++it)
97 turn_info const& info = *it;
98 bool const both_union_turn =
99 info.operations[0].operation == detail::overlay::operation_union
100 && info.operations[1].operation == detail::overlay::operation_union;
101 bool const both_intersection_turn =
102 info.operations[0].operation == detail::overlay::operation_intersection
103 && info.operations[1].operation == detail::overlay::operation_intersection;
105 bool const valid = (both_union_turn || both_intersection_turn)
106 && (info.method == detail::overlay::method_touch
107 || info.method == detail::overlay::method_touch_interior);
111 #ifdef BOOST_GEOMETRY_DEBUG_HAS_SELF_INTERSECTIONS
114 std::cout << "turn points: " << std::endl;
117 std::cout << method_char(info.method);
118 for (int i = 0; i < 2; i++)
120 std::cout << " " << operation_char(info.operations[i].operation);
121 std::cout << " " << info.operations[i].seg_id;
123 std::cout << " " << geometry::dsv(info.point) << std::endl;
126 #if ! defined(BOOST_GEOMETRY_OVERLAY_NO_THROW)
127 if (throw_on_self_intersection)
129 BOOST_THROW_EXCEPTION(overlay_invalid_input_exception());
139 // For backward compatibility
140 template <typename Geometry>
141 inline bool has_self_intersections(Geometry const& geometry,
142 bool throw_on_self_intersection = true)
144 typedef typename geometry::point_type<Geometry>::type point_type;
145 typedef typename geometry::rescale_policy_type<point_type>::type
148 typename strategy::intersection::services::default_strategy
150 typename cs_tag<Geometry>::type
153 rescale_policy_type robust_policy
154 = geometry::get_rescale_policy<rescale_policy_type>(geometry, strategy);
156 return has_self_intersections(geometry, strategy, robust_policy,
157 throw_on_self_intersection);
161 }} // namespace detail::overlay
162 #endif // DOXYGEN_NO_DETAIL
165 }} // namespace boost::geometry
168 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_HAS_SELF_INTERSECTIONS_HPP