]>
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 | ||
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 |