]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 |