]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // Boost.Geometry (aka GGL, Generic Geometry Library) |
2 | ||
3 | // Copyright (c) 2014, Oracle and/or its affiliates. | |
4 | ||
5 | // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle | |
6 | ||
7 | // Licensed under the Boost Software License version 1.0. | |
8 | // http://www.boost.org/users/license.html | |
9 | ||
10 | #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_COMPLEMENT_GRAPH_HPP | |
11 | #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_COMPLEMENT_GRAPH_HPP | |
12 | ||
13 | #include <cstddef> | |
14 | ||
15 | #include <set> | |
16 | #include <stack> | |
17 | #include <utility> | |
18 | #include <vector> | |
19 | ||
20 | #include <boost/core/addressof.hpp> | |
21 | ||
22 | #include <boost/geometry/core/assert.hpp> | |
23 | #include <boost/geometry/policies/compare.hpp> | |
24 | ||
25 | ||
26 | namespace boost { namespace geometry | |
27 | { | |
28 | ||
29 | namespace detail { namespace is_valid | |
30 | { | |
31 | ||
32 | ||
33 | template <typename TurnPoint> | |
34 | class complement_graph_vertex | |
35 | { | |
36 | public: | |
37 | complement_graph_vertex(std::size_t id) | |
38 | : m_id(id) | |
39 | , m_turn_point(NULL) | |
40 | {} | |
41 | ||
42 | complement_graph_vertex(TurnPoint const* turn_point, | |
43 | std::size_t expected_id) | |
44 | : m_id(expected_id) | |
45 | , m_turn_point(turn_point) | |
46 | {} | |
47 | ||
48 | inline std::size_t id() const { return m_id; } | |
49 | ||
50 | inline bool operator<(complement_graph_vertex const& other) const | |
51 | { | |
52 | if ( m_turn_point != NULL && other.m_turn_point != NULL ) | |
53 | { | |
54 | return geometry::less | |
55 | < | |
56 | TurnPoint | |
57 | >()(*m_turn_point, *other.m_turn_point); | |
58 | } | |
59 | if ( m_turn_point == NULL && other.m_turn_point == NULL ) | |
60 | { | |
61 | return m_id < other.m_id; | |
62 | } | |
63 | return m_turn_point == NULL; | |
64 | } | |
65 | ||
66 | private: | |
67 | // the value of m_turn_point determines the type of the vertex | |
68 | // non-NULL: vertex corresponds to an IP | |
69 | // NULL : vertex corresponds to a hole or outer space, and the id | |
70 | // is the ring id of the corresponding ring of the polygon | |
71 | std::size_t m_id; | |
72 | TurnPoint const* m_turn_point; | |
73 | }; | |
74 | ||
75 | ||
76 | ||
77 | ||
78 | template <typename TurnPoint> | |
79 | class complement_graph | |
80 | { | |
81 | private: | |
82 | typedef complement_graph_vertex<TurnPoint> vertex; | |
83 | typedef std::set<vertex> vertex_container; | |
84 | ||
85 | public: | |
86 | typedef typename vertex_container::const_iterator vertex_handle; | |
87 | ||
88 | private: | |
89 | struct vertex_handle_less | |
90 | { | |
91 | inline bool operator()(vertex_handle v1, vertex_handle v2) const | |
92 | { | |
93 | return v1->id() < v2->id(); | |
94 | } | |
95 | }; | |
96 | ||
97 | typedef std::set<vertex_handle, vertex_handle_less> neighbor_container; | |
98 | ||
99 | class has_cycles_dfs_data | |
100 | { | |
101 | public: | |
102 | has_cycles_dfs_data(std::size_t num_nodes) | |
103 | : m_visited(num_nodes, false) | |
104 | , m_parent_id(num_nodes, -1) | |
105 | {} | |
106 | ||
107 | inline signed_size_type parent_id(vertex_handle v) const | |
108 | { | |
109 | return m_parent_id[v->id()]; | |
110 | } | |
111 | ||
112 | inline void set_parent_id(vertex_handle v, signed_size_type id) | |
113 | { | |
114 | m_parent_id[v->id()] = id; | |
115 | } | |
116 | ||
117 | inline bool visited(vertex_handle v) const | |
118 | { | |
119 | return m_visited[v->id()]; | |
120 | } | |
121 | ||
122 | inline void set_visited(vertex_handle v, bool value) | |
123 | { | |
124 | m_visited[v->id()] = value; | |
125 | } | |
126 | private: | |
127 | std::vector<bool> m_visited; | |
128 | std::vector<signed_size_type> m_parent_id; | |
129 | }; | |
130 | ||
131 | ||
132 | inline bool has_cycles(vertex_handle start_vertex, | |
133 | has_cycles_dfs_data& data) const | |
134 | { | |
135 | std::stack<vertex_handle> stack; | |
136 | stack.push(start_vertex); | |
137 | ||
138 | while ( !stack.empty() ) | |
139 | { | |
140 | vertex_handle v = stack.top(); | |
141 | stack.pop(); | |
142 | ||
143 | data.set_visited(v, true); | |
144 | for (typename neighbor_container::const_iterator nit | |
145 | = m_neighbors[v->id()].begin(); | |
146 | nit != m_neighbors[v->id()].end(); ++nit) | |
147 | { | |
148 | if ( static_cast<signed_size_type>((*nit)->id()) != data.parent_id(v) ) | |
149 | { | |
150 | if ( data.visited(*nit) ) | |
151 | { | |
152 | return true; | |
153 | } | |
154 | else | |
155 | { | |
156 | data.set_parent_id(*nit, static_cast<signed_size_type>(v->id())); | |
157 | stack.push(*nit); | |
158 | } | |
159 | } | |
160 | } | |
161 | } | |
162 | return false; | |
163 | } | |
164 | ||
165 | public: | |
166 | // num_rings: total number of rings, including the exterior ring | |
167 | complement_graph(std::size_t num_rings) | |
168 | : m_num_rings(num_rings) | |
169 | , m_num_turns(0) | |
170 | , m_vertices() | |
171 | , m_neighbors(num_rings) | |
172 | {} | |
173 | ||
174 | // inserts a ring vertex in the graph and returns its handle | |
175 | // ring id's are zero-based (so the first interior ring has id 1) | |
176 | inline vertex_handle add_vertex(signed_size_type id) | |
177 | { | |
178 | return m_vertices.insert(vertex(static_cast<std::size_t>(id))).first; | |
179 | } | |
180 | ||
181 | // inserts an IP in the graph and returns its id | |
182 | inline vertex_handle add_vertex(TurnPoint const& turn_point) | |
183 | { | |
184 | std::pair<vertex_handle, bool> res | |
185 | = m_vertices.insert(vertex(boost::addressof(turn_point), | |
186 | m_num_rings + m_num_turns) | |
187 | ); | |
188 | ||
189 | if ( res.second ) | |
190 | { | |
191 | // a new element is inserted | |
192 | m_neighbors.push_back(neighbor_container()); | |
193 | ++m_num_turns; | |
194 | } | |
195 | return res.first; | |
196 | } | |
197 | ||
198 | inline void add_edge(vertex_handle v1, vertex_handle v2) | |
199 | { | |
200 | BOOST_GEOMETRY_ASSERT( v1 != m_vertices.end() ); | |
201 | BOOST_GEOMETRY_ASSERT( v2 != m_vertices.end() ); | |
202 | m_neighbors[v1->id()].insert(v2); | |
203 | m_neighbors[v2->id()].insert(v1); | |
204 | } | |
205 | ||
206 | inline bool has_cycles() const | |
207 | { | |
208 | // initialize all vertices as non-visited and with no parent set | |
209 | // this is done by the constructor of has_cycles_dfs_data | |
210 | has_cycles_dfs_data data(m_num_rings + m_num_turns); | |
211 | ||
212 | // for each non-visited vertex, start a DFS from that vertex | |
213 | for (vertex_handle it = m_vertices.begin(); | |
214 | it != m_vertices.end(); ++it) | |
215 | { | |
216 | if ( !data.visited(it) && has_cycles(it, data) ) | |
217 | { | |
218 | return true; | |
219 | } | |
220 | } | |
221 | return false; | |
222 | } | |
223 | ||
224 | template <typename OStream, typename TP> | |
225 | friend inline | |
226 | void debug_print_complement_graph(OStream&, complement_graph<TP> const&); | |
227 | ||
228 | private: | |
229 | std::size_t m_num_rings, m_num_turns; | |
230 | vertex_container m_vertices; | |
231 | std::vector<neighbor_container> m_neighbors; | |
232 | }; | |
233 | ||
234 | ||
235 | }} // namespace detail::is_valid | |
236 | ||
237 | }} // namespace boost::geometry | |
238 | ||
239 | #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_COMPLEMENT_GRAPH_HPP |