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