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