]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | //======================================================================= |
2 | // Copyright 2007 Aaron Windsor | |
3 | // | |
4 | // Distributed under the Boost Software License, Version 1.0. (See | |
5 | // accompanying file LICENSE_1_0.txt or copy at | |
6 | // http://www.boost.org/LICENSE_1_0.txt) | |
7 | //======================================================================= | |
8 | #ifndef __MAKE_MAXIMAL_PLANAR_HPP__ | |
9 | #define __MAKE_MAXIMAL_PLANAR_HPP__ | |
10 | ||
11 | #include <boost/config.hpp> | |
12 | #include <boost/tuple/tuple.hpp> //for tie | |
13 | #include <boost/graph/biconnected_components.hpp> | |
14 | #include <boost/property_map/property_map.hpp> | |
15 | #include <vector> | |
16 | #include <iterator> | |
17 | #include <algorithm> | |
18 | ||
19 | #include <boost/graph/planar_face_traversal.hpp> | |
20 | #include <boost/graph/planar_detail/add_edge_visitors.hpp> | |
21 | ||
22 | ||
23 | namespace boost | |
24 | { | |
25 | ||
26 | ||
27 | template <typename Graph, typename VertexIndexMap, typename AddEdgeVisitor> | |
28 | struct triangulation_visitor : public planar_face_traversal_visitor | |
29 | { | |
30 | ||
31 | typedef typename graph_traits<Graph>::vertex_descriptor vertex_t; | |
32 | typedef typename graph_traits<Graph>::edge_descriptor edge_t; | |
33 | typedef typename graph_traits<Graph>::vertices_size_type v_size_t; | |
34 | typedef typename graph_traits<Graph>::degree_size_type degree_size_t; | |
35 | typedef typename graph_traits<Graph>::edge_iterator edge_iterator_t; | |
36 | typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator_t; | |
37 | typedef typename graph_traits<Graph>::adjacency_iterator | |
38 | adjacency_iterator_t; | |
39 | typedef typename std::vector<vertex_t> vertex_vector_t; | |
40 | typedef typename std::vector<v_size_t> v_size_vector_t; | |
41 | typedef typename std::vector<degree_size_t> degree_size_vector_t; | |
42 | typedef iterator_property_map | |
43 | < typename v_size_vector_t::iterator, VertexIndexMap > | |
44 | vertex_to_v_size_map_t; | |
45 | typedef iterator_property_map | |
46 | < typename degree_size_vector_t::iterator, VertexIndexMap > | |
47 | vertex_to_degree_size_map_t; | |
48 | typedef typename vertex_vector_t::iterator face_iterator; | |
49 | ||
50 | ||
51 | triangulation_visitor(Graph& arg_g, | |
52 | VertexIndexMap arg_vm, | |
53 | AddEdgeVisitor arg_add_edge_visitor | |
54 | ) : | |
55 | g(arg_g), | |
56 | vm(arg_vm), | |
57 | add_edge_visitor(arg_add_edge_visitor), | |
58 | timestamp(0), | |
59 | marked_vector(num_vertices(g), timestamp), | |
60 | degree_vector(num_vertices(g), 0), | |
61 | marked(marked_vector.begin(), vm), | |
62 | degree(degree_vector.begin(), vm) | |
63 | { | |
64 | vertex_iterator_t vi, vi_end; | |
65 | for(boost::tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi) | |
66 | put(degree, *vi, out_degree(*vi, g)); | |
67 | } | |
68 | ||
69 | template <typename Vertex> | |
70 | void next_vertex(Vertex v) | |
71 | { | |
72 | // Self-loops will appear as consecutive vertices in the list of | |
73 | // vertices on a face. We want to skip these. | |
74 | if (!vertices_on_face.empty() && | |
75 | (vertices_on_face.back() == v || vertices_on_face.front() == v) | |
76 | ) | |
77 | return; | |
78 | ||
79 | vertices_on_face.push_back(v); | |
80 | } | |
81 | ||
82 | void end_face() | |
83 | { | |
84 | ++timestamp; | |
85 | ||
86 | if (vertices_on_face.size() <= 3) | |
87 | { | |
88 | // At most three vertices on this face - don't need to triangulate | |
89 | vertices_on_face.clear(); | |
90 | return; | |
91 | } | |
92 | ||
93 | // Find vertex on face of minimum degree | |
94 | degree_size_t min_degree = num_vertices(g); | |
95 | typename vertex_vector_t::iterator min_degree_vertex_itr; | |
96 | face_iterator fi_end = vertices_on_face.end(); | |
97 | for(face_iterator fi = vertices_on_face.begin(); fi != fi_end; ++fi) | |
98 | { | |
99 | degree_size_t deg = get(degree,*fi); | |
100 | if (deg < min_degree) | |
101 | { | |
102 | min_degree_vertex_itr = fi; | |
103 | min_degree = deg; | |
104 | } | |
105 | } | |
106 | ||
107 | // To simplify some of the manipulations, we'll re-arrange | |
108 | // vertices_on_face so that it still contains the same | |
109 | // (counter-clockwise) order of the vertices on this face, but now the | |
110 | // min_degree_vertex is the first element in vertices_on_face. | |
111 | vertex_vector_t temp_vector; | |
112 | std::copy(min_degree_vertex_itr, vertices_on_face.end(), | |
113 | std::back_inserter(temp_vector)); | |
114 | std::copy(vertices_on_face.begin(), min_degree_vertex_itr, | |
115 | std::back_inserter(temp_vector)); | |
116 | vertices_on_face.swap(temp_vector); | |
117 | ||
118 | // Mark all of the min degree vertex's neighbors | |
119 | adjacency_iterator_t ai, ai_end; | |
120 | for(boost::tie(ai,ai_end) = adjacent_vertices(vertices_on_face.front(),g); | |
121 | ai != ai_end; ++ai | |
122 | ) | |
123 | { | |
124 | put(marked, *ai, timestamp); | |
125 | } | |
126 | ||
127 | typename vertex_vector_t::iterator marked_neighbor | |
128 | = vertices_on_face.end(); | |
129 | ||
130 | // The iterator manipulations on the next two lines are safe because | |
131 | // vertices_on_face.size() > 3 (from the first test in this function) | |
132 | fi_end = prior(vertices_on_face.end()); | |
133 | for(face_iterator fi = boost::next(boost::next(vertices_on_face.begin())); | |
134 | fi != fi_end; ++fi | |
135 | ) | |
136 | { | |
137 | if (get(marked, *fi) == timestamp) | |
138 | { | |
139 | marked_neighbor = fi; | |
140 | break; | |
141 | } | |
142 | } | |
143 | ||
144 | if (marked_neighbor == vertices_on_face.end()) | |
145 | { | |
146 | add_edge_range( | |
147 | vertices_on_face[0], | |
148 | boost::next(boost::next(vertices_on_face.begin())), | |
149 | prior(vertices_on_face.end()) | |
150 | ); | |
151 | } | |
152 | else | |
153 | { | |
154 | add_edge_range( | |
155 | vertices_on_face[1], | |
156 | boost::next(marked_neighbor), | |
157 | vertices_on_face.end() | |
158 | ); | |
159 | ||
160 | add_edge_range( | |
161 | *boost::next(marked_neighbor), | |
162 | boost::next(boost::next(vertices_on_face.begin())), | |
163 | marked_neighbor | |
164 | ); | |
165 | } | |
166 | ||
167 | //reset for the next face | |
168 | vertices_on_face.clear(); | |
169 | ||
170 | } | |
171 | ||
172 | private: | |
173 | ||
174 | ||
175 | void add_edge_range(vertex_t anchor, | |
176 | face_iterator fi, | |
177 | face_iterator fi_end | |
178 | ) | |
179 | { | |
180 | for (; fi != fi_end; ++fi) | |
181 | { | |
182 | vertex_t v(*fi); | |
183 | add_edge_visitor.visit_vertex_pair(anchor, v, g); | |
184 | put(degree, anchor, get(degree, anchor) + 1); | |
185 | put(degree, v, get(degree, v) + 1); | |
186 | } | |
187 | } | |
188 | ||
189 | ||
190 | Graph& g; | |
191 | VertexIndexMap vm; | |
192 | AddEdgeVisitor add_edge_visitor; | |
193 | v_size_t timestamp; | |
194 | vertex_vector_t vertices_on_face; | |
195 | v_size_vector_t marked_vector; | |
196 | degree_size_vector_t degree_vector; | |
197 | vertex_to_v_size_map_t marked; | |
198 | vertex_to_degree_size_map_t degree; | |
199 | ||
200 | }; | |
201 | ||
202 | ||
203 | ||
204 | ||
205 | template <typename Graph, | |
206 | typename PlanarEmbedding, | |
207 | typename VertexIndexMap, | |
208 | typename EdgeIndexMap, | |
209 | typename AddEdgeVisitor | |
210 | > | |
211 | void make_maximal_planar(Graph& g, | |
212 | PlanarEmbedding embedding, | |
213 | VertexIndexMap vm, | |
214 | EdgeIndexMap em, | |
215 | AddEdgeVisitor& vis) | |
216 | { | |
217 | triangulation_visitor<Graph,VertexIndexMap,AddEdgeVisitor> | |
218 | visitor(g, vm, vis); | |
219 | planar_face_traversal(g, embedding, visitor, em); | |
220 | } | |
221 | ||
222 | ||
223 | ||
224 | ||
225 | template <typename Graph, | |
226 | typename PlanarEmbedding, | |
227 | typename VertexIndexMap, | |
228 | typename EdgeIndexMap | |
229 | > | |
230 | void make_maximal_planar(Graph& g, | |
231 | PlanarEmbedding embedding, | |
232 | VertexIndexMap vm, | |
233 | EdgeIndexMap em | |
234 | ) | |
235 | { | |
236 | default_add_edge_visitor vis; | |
237 | make_maximal_planar(g, embedding, vm, em, vis); | |
238 | } | |
239 | ||
240 | ||
241 | ||
242 | ||
243 | template <typename Graph, | |
244 | typename PlanarEmbedding, | |
245 | typename VertexIndexMap | |
246 | > | |
247 | void make_maximal_planar(Graph& g, | |
248 | PlanarEmbedding embedding, | |
249 | VertexIndexMap vm | |
250 | ) | |
251 | { | |
252 | make_maximal_planar(g, embedding, vm, get(edge_index,g)); | |
253 | } | |
254 | ||
255 | ||
256 | ||
257 | ||
258 | template <typename Graph, | |
259 | typename PlanarEmbedding | |
260 | > | |
261 | void make_maximal_planar(Graph& g, | |
262 | PlanarEmbedding embedding | |
263 | ) | |
264 | { | |
265 | make_maximal_planar(g, embedding, get(vertex_index,g)); | |
266 | } | |
267 | ||
268 | ||
269 | ||
270 | ||
271 | } // namespace boost | |
272 | ||
273 | ||
274 | ||
275 | #endif //__MAKE_MAXIMAL_PLANAR_HPP__ |