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 namespace boost
23 {
24
25 template < typename Graph, typename VertexIndexMap, typename AddEdgeVisitor >
26 struct triangulation_visitor : public planar_face_traversal_visitor
27 {
28
29 typedef typename graph_traits< Graph >::vertex_descriptor vertex_t;
30 typedef typename graph_traits< Graph >::edge_descriptor edge_t;
31 typedef typename graph_traits< Graph >::vertices_size_type v_size_t;
32 typedef typename graph_traits< Graph >::degree_size_type degree_size_t;
33 typedef typename graph_traits< Graph >::edge_iterator edge_iterator_t;
34 typedef typename graph_traits< Graph >::vertex_iterator vertex_iterator_t;
35 typedef
36 typename graph_traits< Graph >::adjacency_iterator adjacency_iterator_t;
37 typedef typename std::vector< vertex_t > vertex_vector_t;
38 typedef typename std::vector< v_size_t > v_size_vector_t;
39 typedef typename std::vector< degree_size_t > degree_size_vector_t;
40 typedef iterator_property_map< typename v_size_vector_t::iterator,
41 VertexIndexMap >
42 vertex_to_v_size_map_t;
43 typedef iterator_property_map< typename degree_size_vector_t::iterator,
44 VertexIndexMap >
45 vertex_to_degree_size_map_t;
46 typedef typename vertex_vector_t::iterator face_iterator;
47
triangulation_visitorboost::triangulation_visitor48 triangulation_visitor(Graph& arg_g, VertexIndexMap arg_vm,
49 AddEdgeVisitor arg_add_edge_visitor)
50 : g(arg_g)
51 , vm(arg_vm)
52 , add_edge_visitor(arg_add_edge_visitor)
53 , timestamp(0)
54 , marked_vector(num_vertices(g), timestamp)
55 , degree_vector(num_vertices(g), 0)
56 , marked(marked_vector.begin(), vm)
57 , degree(degree_vector.begin(), vm)
58 {
59 vertex_iterator_t vi, vi_end;
60 for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
61 put(degree, *vi, out_degree(*vi, g));
62 }
63
next_vertexboost::triangulation_visitor64 template < typename Vertex > void next_vertex(Vertex v)
65 {
66 // Self-loops will appear as consecutive vertices in the list of
67 // vertices on a face. We want to skip these.
68 if (!vertices_on_face.empty()
69 && (vertices_on_face.back() == v || vertices_on_face.front() == v))
70 return;
71
72 vertices_on_face.push_back(v);
73 }
74
end_faceboost::triangulation_visitor75 void end_face()
76 {
77 ++timestamp;
78
79 if (vertices_on_face.size() <= 3)
80 {
81 // At most three vertices on this face - don't need to triangulate
82 vertices_on_face.clear();
83 return;
84 }
85
86 // Find vertex on face of minimum degree
87 degree_size_t min_degree = num_vertices(g);
88 typename vertex_vector_t::iterator min_degree_vertex_itr;
89 face_iterator fi_end = vertices_on_face.end();
90 for (face_iterator fi = vertices_on_face.begin(); fi != fi_end; ++fi)
91 {
92 degree_size_t deg = get(degree, *fi);
93 if (deg < min_degree)
94 {
95 min_degree_vertex_itr = fi;
96 min_degree = deg;
97 }
98 }
99
100 // To simplify some of the manipulations, we'll re-arrange
101 // vertices_on_face so that it still contains the same
102 // (counter-clockwise) order of the vertices on this face, but now the
103 // min_degree_vertex is the first element in vertices_on_face.
104 vertex_vector_t temp_vector;
105 std::copy(min_degree_vertex_itr, vertices_on_face.end(),
106 std::back_inserter(temp_vector));
107 std::copy(vertices_on_face.begin(), min_degree_vertex_itr,
108 std::back_inserter(temp_vector));
109 vertices_on_face.swap(temp_vector);
110
111 // Mark all of the min degree vertex's neighbors
112 adjacency_iterator_t ai, ai_end;
113 for (boost::tie(ai, ai_end)
114 = adjacent_vertices(vertices_on_face.front(), g);
115 ai != ai_end; ++ai)
116 {
117 put(marked, *ai, timestamp);
118 }
119
120 typename vertex_vector_t::iterator marked_neighbor
121 = vertices_on_face.end();
122
123 // The iterator manipulations on the next two lines are safe because
124 // vertices_on_face.size() > 3 (from the first test in this function)
125 fi_end = prior(vertices_on_face.end());
126 for (face_iterator fi
127 = boost::next(boost::next(vertices_on_face.begin()));
128 fi != fi_end; ++fi)
129 {
130 if (get(marked, *fi) == timestamp)
131 {
132 marked_neighbor = fi;
133 break;
134 }
135 }
136
137 if (marked_neighbor == vertices_on_face.end())
138 {
139 add_edge_range(vertices_on_face[0],
140 boost::next(boost::next(vertices_on_face.begin())),
141 prior(vertices_on_face.end()));
142 }
143 else
144 {
145 add_edge_range(vertices_on_face[1], boost::next(marked_neighbor),
146 vertices_on_face.end());
147
148 add_edge_range(*boost::next(marked_neighbor),
149 boost::next(boost::next(vertices_on_face.begin())),
150 marked_neighbor);
151 }
152
153 // reset for the next face
154 vertices_on_face.clear();
155 }
156
157 private:
add_edge_rangeboost::triangulation_visitor158 void add_edge_range(vertex_t anchor, face_iterator fi, face_iterator fi_end)
159 {
160 for (; fi != fi_end; ++fi)
161 {
162 vertex_t v(*fi);
163 add_edge_visitor.visit_vertex_pair(anchor, v, g);
164 put(degree, anchor, get(degree, anchor) + 1);
165 put(degree, v, get(degree, v) + 1);
166 }
167 }
168
169 Graph& g;
170 VertexIndexMap vm;
171 AddEdgeVisitor add_edge_visitor;
172 v_size_t timestamp;
173 vertex_vector_t vertices_on_face;
174 v_size_vector_t marked_vector;
175 degree_size_vector_t degree_vector;
176 vertex_to_v_size_map_t marked;
177 vertex_to_degree_size_map_t degree;
178 };
179
180 template < typename Graph, typename PlanarEmbedding, typename VertexIndexMap,
181 typename EdgeIndexMap, typename AddEdgeVisitor >
make_maximal_planar(Graph & g,PlanarEmbedding embedding,VertexIndexMap vm,EdgeIndexMap em,AddEdgeVisitor & vis)182 void make_maximal_planar(Graph& g, PlanarEmbedding embedding, VertexIndexMap vm,
183 EdgeIndexMap em, AddEdgeVisitor& vis)
184 {
185 triangulation_visitor< Graph, VertexIndexMap, AddEdgeVisitor > visitor(
186 g, vm, vis);
187 planar_face_traversal(g, embedding, visitor, em);
188 }
189
190 template < typename Graph, typename PlanarEmbedding, typename VertexIndexMap,
191 typename EdgeIndexMap >
make_maximal_planar(Graph & g,PlanarEmbedding embedding,VertexIndexMap vm,EdgeIndexMap em)192 void make_maximal_planar(
193 Graph& g, PlanarEmbedding embedding, VertexIndexMap vm, EdgeIndexMap em)
194 {
195 default_add_edge_visitor vis;
196 make_maximal_planar(g, embedding, vm, em, vis);
197 }
198
199 template < typename Graph, typename PlanarEmbedding, typename VertexIndexMap >
make_maximal_planar(Graph & g,PlanarEmbedding embedding,VertexIndexMap vm)200 void make_maximal_planar(Graph& g, PlanarEmbedding embedding, VertexIndexMap vm)
201 {
202 make_maximal_planar(g, embedding, vm, get(edge_index, g));
203 }
204
205 template < typename Graph, typename PlanarEmbedding >
make_maximal_planar(Graph & g,PlanarEmbedding embedding)206 void make_maximal_planar(Graph& g, PlanarEmbedding embedding)
207 {
208 make_maximal_planar(g, embedding, get(vertex_index, g));
209 }
210
211 } // namespace boost
212
213 #endif //__MAKE_MAXIMAL_PLANAR_HPP__
214