]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // Boost.Polygon library voronoi_diagram.hpp header file |
2 | ||
3 | // Copyright Andrii Sydorchuk 2010-2012. | |
4 | // Distributed under the Boost Software License, Version 1.0. | |
5 | // (See accompanying file LICENSE_1_0.txt or copy at | |
6 | // http://www.boost.org/LICENSE_1_0.txt) | |
7 | ||
8 | // See http://www.boost.org for updates, documentation, and revision history. | |
9 | ||
10 | #ifndef BOOST_POLYGON_VORONOI_DIAGRAM | |
11 | #define BOOST_POLYGON_VORONOI_DIAGRAM | |
12 | ||
13 | #include <vector> | |
14 | #include <utility> | |
15 | ||
16 | #include "detail/voronoi_ctypes.hpp" | |
17 | #include "detail/voronoi_structures.hpp" | |
18 | ||
19 | #include "voronoi_geometry_type.hpp" | |
20 | ||
21 | namespace boost { | |
22 | namespace polygon { | |
23 | ||
24 | // Forward declarations. | |
25 | template <typename T> | |
26 | class voronoi_edge; | |
27 | ||
28 | // Represents Voronoi cell. | |
29 | // Data members: | |
30 | // 1) index of the source within the initial input set | |
31 | // 2) pointer to the incident edge | |
32 | // 3) mutable color member | |
33 | // Cell may contain point or segment site inside. | |
34 | template <typename T> | |
35 | class voronoi_cell { | |
36 | public: | |
37 | typedef T coordinate_type; | |
38 | typedef std::size_t color_type; | |
39 | typedef voronoi_edge<coordinate_type> voronoi_edge_type; | |
40 | typedef std::size_t source_index_type; | |
41 | typedef SourceCategory source_category_type; | |
42 | ||
43 | voronoi_cell(source_index_type source_index, | |
44 | source_category_type source_category) : | |
45 | source_index_(source_index), | |
46 | incident_edge_(NULL), | |
47 | color_(source_category) {} | |
48 | ||
49 | // Returns true if the cell contains point site, false else. | |
50 | bool contains_point() const { | |
51 | source_category_type source_category = this->source_category(); | |
52 | return belongs(source_category, GEOMETRY_CATEGORY_POINT); | |
53 | } | |
54 | ||
55 | // Returns true if the cell contains segment site, false else. | |
56 | bool contains_segment() const { | |
57 | source_category_type source_category = this->source_category(); | |
58 | return belongs(source_category, GEOMETRY_CATEGORY_SEGMENT); | |
59 | } | |
60 | ||
61 | source_index_type source_index() const { | |
62 | return source_index_; | |
63 | } | |
64 | ||
65 | source_category_type source_category() const { | |
66 | return static_cast<source_category_type>(color_ & SOURCE_CATEGORY_BITMASK); | |
67 | } | |
68 | ||
69 | // Degenerate cells don't have any incident edges. | |
70 | bool is_degenerate() const { return incident_edge_ == NULL; } | |
71 | ||
72 | voronoi_edge_type* incident_edge() { return incident_edge_; } | |
73 | const voronoi_edge_type* incident_edge() const { return incident_edge_; } | |
74 | void incident_edge(voronoi_edge_type* e) { incident_edge_ = e; } | |
75 | ||
76 | color_type color() const { return color_ >> BITS_SHIFT; } | |
77 | void color(color_type color) const { | |
78 | color_ &= BITS_MASK; | |
79 | color_ |= color << BITS_SHIFT; | |
80 | } | |
81 | ||
82 | private: | |
83 | // 5 color bits are reserved. | |
84 | enum Bits { | |
85 | BITS_SHIFT = 0x5, | |
86 | BITS_MASK = 0x1F | |
87 | }; | |
88 | ||
89 | source_index_type source_index_; | |
90 | voronoi_edge_type* incident_edge_; | |
91 | mutable color_type color_; | |
92 | }; | |
93 | ||
94 | // Represents Voronoi vertex. | |
95 | // Data members: | |
96 | // 1) vertex coordinates | |
97 | // 2) pointer to the incident edge | |
98 | // 3) mutable color member | |
99 | template <typename T> | |
100 | class voronoi_vertex { | |
101 | public: | |
102 | typedef T coordinate_type; | |
103 | typedef std::size_t color_type; | |
104 | typedef voronoi_edge<coordinate_type> voronoi_edge_type; | |
105 | ||
106 | voronoi_vertex(const coordinate_type& x, const coordinate_type& y) : | |
107 | x_(x), | |
108 | y_(y), | |
109 | incident_edge_(NULL), | |
110 | color_(0) {} | |
111 | ||
112 | const coordinate_type& x() const { return x_; } | |
113 | const coordinate_type& y() const { return y_; } | |
114 | ||
115 | bool is_degenerate() const { return incident_edge_ == NULL; } | |
116 | ||
117 | voronoi_edge_type* incident_edge() { return incident_edge_; } | |
118 | const voronoi_edge_type* incident_edge() const { return incident_edge_; } | |
119 | void incident_edge(voronoi_edge_type* e) { incident_edge_ = e; } | |
120 | ||
121 | color_type color() const { return color_ >> BITS_SHIFT; } | |
122 | void color(color_type color) const { | |
123 | color_ &= BITS_MASK; | |
124 | color_ |= color << BITS_SHIFT; | |
125 | } | |
126 | ||
127 | private: | |
128 | // 5 color bits are reserved. | |
129 | enum Bits { | |
130 | BITS_SHIFT = 0x5, | |
131 | BITS_MASK = 0x1F | |
132 | }; | |
133 | ||
134 | coordinate_type x_; | |
135 | coordinate_type y_; | |
136 | voronoi_edge_type* incident_edge_; | |
137 | mutable color_type color_; | |
138 | }; | |
139 | ||
140 | // Half-edge data structure. Represents Voronoi edge. | |
141 | // Data members: | |
142 | // 1) pointer to the corresponding cell | |
143 | // 2) pointer to the vertex that is the starting | |
144 | // point of the half-edge | |
145 | // 3) pointer to the twin edge | |
146 | // 4) pointer to the CCW next edge | |
147 | // 5) pointer to the CCW prev edge | |
148 | // 6) mutable color member | |
149 | template <typename T> | |
150 | class voronoi_edge { | |
151 | public: | |
152 | typedef T coordinate_type; | |
153 | typedef voronoi_cell<coordinate_type> voronoi_cell_type; | |
154 | typedef voronoi_vertex<coordinate_type> voronoi_vertex_type; | |
155 | typedef voronoi_edge<coordinate_type> voronoi_edge_type; | |
156 | typedef std::size_t color_type; | |
157 | ||
158 | voronoi_edge(bool is_linear, bool is_primary) : | |
159 | cell_(NULL), | |
160 | vertex_(NULL), | |
161 | twin_(NULL), | |
162 | next_(NULL), | |
163 | prev_(NULL), | |
164 | color_(0) { | |
165 | if (is_linear) | |
166 | color_ |= BIT_IS_LINEAR; | |
167 | if (is_primary) | |
168 | color_ |= BIT_IS_PRIMARY; | |
169 | } | |
170 | ||
171 | voronoi_cell_type* cell() { return cell_; } | |
172 | const voronoi_cell_type* cell() const { return cell_; } | |
173 | void cell(voronoi_cell_type* c) { cell_ = c; } | |
174 | ||
175 | voronoi_vertex_type* vertex0() { return vertex_; } | |
176 | const voronoi_vertex_type* vertex0() const { return vertex_; } | |
177 | void vertex0(voronoi_vertex_type* v) { vertex_ = v; } | |
178 | ||
179 | voronoi_vertex_type* vertex1() { return twin_->vertex0(); } | |
180 | const voronoi_vertex_type* vertex1() const { return twin_->vertex0(); } | |
181 | ||
182 | voronoi_edge_type* twin() { return twin_; } | |
183 | const voronoi_edge_type* twin() const { return twin_; } | |
184 | void twin(voronoi_edge_type* e) { twin_ = e; } | |
185 | ||
186 | voronoi_edge_type* next() { return next_; } | |
187 | const voronoi_edge_type* next() const { return next_; } | |
188 | void next(voronoi_edge_type* e) { next_ = e; } | |
189 | ||
190 | voronoi_edge_type* prev() { return prev_; } | |
191 | const voronoi_edge_type* prev() const { return prev_; } | |
192 | void prev(voronoi_edge_type* e) { prev_ = e; } | |
193 | ||
194 | // Returns a pointer to the rotation next edge | |
195 | // over the starting point of the half-edge. | |
196 | voronoi_edge_type* rot_next() { return prev_->twin(); } | |
197 | const voronoi_edge_type* rot_next() const { return prev_->twin(); } | |
198 | ||
199 | // Returns a pointer to the rotation prev edge | |
200 | // over the starting point of the half-edge. | |
201 | voronoi_edge_type* rot_prev() { return twin_->next(); } | |
202 | const voronoi_edge_type* rot_prev() const { return twin_->next(); } | |
203 | ||
204 | // Returns true if the edge is finite (segment, parabolic arc). | |
205 | // Returns false if the edge is infinite (ray, line). | |
206 | bool is_finite() const { return vertex0() && vertex1(); } | |
207 | ||
208 | // Returns true if the edge is infinite (ray, line). | |
209 | // Returns false if the edge is finite (segment, parabolic arc). | |
210 | bool is_infinite() const { return !vertex0() || !vertex1(); } | |
211 | ||
212 | // Returns true if the edge is linear (segment, ray, line). | |
213 | // Returns false if the edge is curved (parabolic arc). | |
214 | bool is_linear() const { | |
215 | return (color_ & BIT_IS_LINEAR) ? true : false; | |
216 | } | |
217 | ||
218 | // Returns true if the edge is curved (parabolic arc). | |
219 | // Returns false if the edge is linear (segment, ray, line). | |
220 | bool is_curved() const { | |
221 | return (color_ & BIT_IS_LINEAR) ? false : true; | |
222 | } | |
223 | ||
224 | // Returns false if edge goes through the endpoint of the segment. | |
225 | // Returns true else. | |
226 | bool is_primary() const { | |
227 | return (color_ & BIT_IS_PRIMARY) ? true : false; | |
228 | } | |
229 | ||
230 | // Returns true if edge goes through the endpoint of the segment. | |
231 | // Returns false else. | |
232 | bool is_secondary() const { | |
233 | return (color_ & BIT_IS_PRIMARY) ? false : true; | |
234 | } | |
235 | ||
236 | color_type color() const { return color_ >> BITS_SHIFT; } | |
237 | void color(color_type color) const { | |
238 | color_ &= BITS_MASK; | |
239 | color_ |= color << BITS_SHIFT; | |
240 | } | |
241 | ||
242 | private: | |
243 | // 5 color bits are reserved. | |
244 | enum Bits { | |
245 | BIT_IS_LINEAR = 0x1, // linear is opposite to curved | |
246 | BIT_IS_PRIMARY = 0x2, // primary is opposite to secondary | |
247 | ||
248 | BITS_SHIFT = 0x5, | |
249 | BITS_MASK = 0x1F | |
250 | }; | |
251 | ||
252 | voronoi_cell_type* cell_; | |
253 | voronoi_vertex_type* vertex_; | |
254 | voronoi_edge_type* twin_; | |
255 | voronoi_edge_type* next_; | |
256 | voronoi_edge_type* prev_; | |
257 | mutable color_type color_; | |
258 | }; | |
259 | ||
260 | template <typename T> | |
261 | struct voronoi_diagram_traits { | |
262 | typedef T coordinate_type; | |
263 | typedef voronoi_cell<coordinate_type> cell_type; | |
264 | typedef voronoi_vertex<coordinate_type> vertex_type; | |
265 | typedef voronoi_edge<coordinate_type> edge_type; | |
266 | typedef class { | |
267 | public: | |
268 | enum { ULPS = 128 }; | |
269 | bool operator()(const vertex_type& v1, const vertex_type& v2) const { | |
270 | return (ulp_cmp(v1.x(), v2.x(), ULPS) == | |
271 | detail::ulp_comparison<T>::EQUAL) && | |
272 | (ulp_cmp(v1.y(), v2.y(), ULPS) == | |
273 | detail::ulp_comparison<T>::EQUAL); | |
274 | } | |
275 | private: | |
276 | typename detail::ulp_comparison<T> ulp_cmp; | |
277 | } vertex_equality_predicate_type; | |
278 | }; | |
279 | ||
280 | // Voronoi output data structure. | |
281 | // CCW ordering is used on the faces perimeter and around the vertices. | |
282 | template <typename T, typename TRAITS = voronoi_diagram_traits<T> > | |
283 | class voronoi_diagram { | |
284 | public: | |
285 | typedef typename TRAITS::coordinate_type coordinate_type; | |
286 | typedef typename TRAITS::cell_type cell_type; | |
287 | typedef typename TRAITS::vertex_type vertex_type; | |
288 | typedef typename TRAITS::edge_type edge_type; | |
289 | ||
290 | typedef std::vector<cell_type> cell_container_type; | |
291 | typedef typename cell_container_type::const_iterator const_cell_iterator; | |
292 | ||
293 | typedef std::vector<vertex_type> vertex_container_type; | |
294 | typedef typename vertex_container_type::const_iterator const_vertex_iterator; | |
295 | ||
296 | typedef std::vector<edge_type> edge_container_type; | |
297 | typedef typename edge_container_type::const_iterator const_edge_iterator; | |
298 | ||
299 | voronoi_diagram() {} | |
300 | ||
301 | void clear() { | |
302 | cells_.clear(); | |
303 | vertices_.clear(); | |
304 | edges_.clear(); | |
305 | } | |
306 | ||
307 | const cell_container_type& cells() const { | |
308 | return cells_; | |
309 | } | |
310 | ||
311 | const vertex_container_type& vertices() const { | |
312 | return vertices_; | |
313 | } | |
314 | ||
315 | const edge_container_type& edges() const { | |
316 | return edges_; | |
317 | } | |
318 | ||
319 | std::size_t num_cells() const { | |
320 | return cells_.size(); | |
321 | } | |
322 | ||
323 | std::size_t num_edges() const { | |
324 | return edges_.size(); | |
325 | } | |
326 | ||
327 | std::size_t num_vertices() const { | |
328 | return vertices_.size(); | |
329 | } | |
330 | ||
331 | void _reserve(std::size_t num_sites) { | |
332 | cells_.reserve(num_sites); | |
333 | vertices_.reserve(num_sites << 1); | |
334 | edges_.reserve((num_sites << 2) + (num_sites << 1)); | |
335 | } | |
336 | ||
337 | template <typename CT> | |
338 | void _process_single_site(const detail::site_event<CT>& site) { | |
339 | cells_.push_back(cell_type(site.initial_index(), site.source_category())); | |
340 | } | |
341 | ||
342 | // Insert a new half-edge into the output data structure. | |
343 | // Takes as input left and right sites that form a new bisector. | |
344 | // Returns a pair of pointers to a new half-edges. | |
345 | template <typename CT> | |
346 | std::pair<void*, void*> _insert_new_edge( | |
347 | const detail::site_event<CT>& site1, | |
348 | const detail::site_event<CT>& site2) { | |
349 | // Get sites' indexes. | |
350 | std::size_t site_index1 = site1.sorted_index(); | |
351 | std::size_t site_index2 = site2.sorted_index(); | |
352 | ||
353 | bool is_linear = is_linear_edge(site1, site2); | |
354 | bool is_primary = is_primary_edge(site1, site2); | |
355 | ||
356 | // Create a new half-edge that belongs to the first site. | |
357 | edges_.push_back(edge_type(is_linear, is_primary)); | |
358 | edge_type& edge1 = edges_.back(); | |
359 | ||
360 | // Create a new half-edge that belongs to the second site. | |
361 | edges_.push_back(edge_type(is_linear, is_primary)); | |
362 | edge_type& edge2 = edges_.back(); | |
363 | ||
364 | // Add the initial cell during the first edge insertion. | |
365 | if (cells_.empty()) { | |
366 | cells_.push_back(cell_type( | |
367 | site1.initial_index(), site1.source_category())); | |
368 | } | |
369 | ||
370 | // The second site represents a new site during site event | |
371 | // processing. Add a new cell to the cell records. | |
372 | cells_.push_back(cell_type( | |
373 | site2.initial_index(), site2.source_category())); | |
374 | ||
375 | // Set up pointers to cells. | |
376 | edge1.cell(&cells_[site_index1]); | |
377 | edge2.cell(&cells_[site_index2]); | |
378 | ||
379 | // Set up twin pointers. | |
380 | edge1.twin(&edge2); | |
381 | edge2.twin(&edge1); | |
382 | ||
383 | // Return a pointer to the new half-edge. | |
384 | return std::make_pair(&edge1, &edge2); | |
385 | } | |
386 | ||
387 | // Insert a new half-edge into the output data structure with the | |
388 | // start at the point where two previously added half-edges intersect. | |
389 | // Takes as input two sites that create a new bisector, circle event | |
390 | // that corresponds to the intersection point of the two old half-edges, | |
391 | // pointers to those half-edges. Half-edges' direction goes out of the | |
392 | // new Voronoi vertex point. Returns a pair of pointers to a new half-edges. | |
393 | template <typename CT1, typename CT2> | |
394 | std::pair<void*, void*> _insert_new_edge( | |
395 | const detail::site_event<CT1>& site1, | |
396 | const detail::site_event<CT1>& site3, | |
397 | const detail::circle_event<CT2>& circle, | |
398 | void* data12, void* data23) { | |
399 | edge_type* edge12 = static_cast<edge_type*>(data12); | |
400 | edge_type* edge23 = static_cast<edge_type*>(data23); | |
401 | ||
402 | // Add a new Voronoi vertex. | |
403 | vertices_.push_back(vertex_type(circle.x(), circle.y())); | |
404 | vertex_type& new_vertex = vertices_.back(); | |
405 | ||
406 | // Update vertex pointers of the old edges. | |
407 | edge12->vertex0(&new_vertex); | |
408 | edge23->vertex0(&new_vertex); | |
409 | ||
410 | bool is_linear = is_linear_edge(site1, site3); | |
411 | bool is_primary = is_primary_edge(site1, site3); | |
412 | ||
413 | // Add a new half-edge. | |
414 | edges_.push_back(edge_type(is_linear, is_primary)); | |
415 | edge_type& new_edge1 = edges_.back(); | |
416 | new_edge1.cell(&cells_[site1.sorted_index()]); | |
417 | ||
418 | // Add a new half-edge. | |
419 | edges_.push_back(edge_type(is_linear, is_primary)); | |
420 | edge_type& new_edge2 = edges_.back(); | |
421 | new_edge2.cell(&cells_[site3.sorted_index()]); | |
422 | ||
423 | // Update twin pointers. | |
424 | new_edge1.twin(&new_edge2); | |
425 | new_edge2.twin(&new_edge1); | |
426 | ||
427 | // Update vertex pointer. | |
428 | new_edge2.vertex0(&new_vertex); | |
429 | ||
430 | // Update Voronoi prev/next pointers. | |
431 | edge12->prev(&new_edge1); | |
432 | new_edge1.next(edge12); | |
433 | edge12->twin()->next(edge23); | |
434 | edge23->prev(edge12->twin()); | |
435 | edge23->twin()->next(&new_edge2); | |
436 | new_edge2.prev(edge23->twin()); | |
437 | ||
438 | // Return a pointer to the new half-edge. | |
439 | return std::make_pair(&new_edge1, &new_edge2); | |
440 | } | |
441 | ||
442 | void _build() { | |
443 | // Remove degenerate edges. | |
444 | edge_iterator last_edge = edges_.begin(); | |
445 | for (edge_iterator it = edges_.begin(); it != edges_.end(); it += 2) { | |
446 | const vertex_type* v1 = it->vertex0(); | |
447 | const vertex_type* v2 = it->vertex1(); | |
448 | if (v1 && v2 && vertex_equality_predicate_(*v1, *v2)) { | |
449 | remove_edge(&(*it)); | |
450 | } else { | |
451 | if (it != last_edge) { | |
452 | edge_type* e1 = &(*last_edge = *it); | |
453 | edge_type* e2 = &(*(last_edge + 1) = *(it + 1)); | |
454 | e1->twin(e2); | |
455 | e2->twin(e1); | |
456 | if (e1->prev()) { | |
457 | e1->prev()->next(e1); | |
458 | e2->next()->prev(e2); | |
459 | } | |
460 | if (e2->prev()) { | |
461 | e1->next()->prev(e1); | |
462 | e2->prev()->next(e2); | |
463 | } | |
464 | } | |
465 | last_edge += 2; | |
466 | } | |
467 | } | |
468 | edges_.erase(last_edge, edges_.end()); | |
469 | ||
470 | // Set up incident edge pointers for cells and vertices. | |
471 | for (edge_iterator it = edges_.begin(); it != edges_.end(); ++it) { | |
472 | it->cell()->incident_edge(&(*it)); | |
473 | if (it->vertex0()) { | |
474 | it->vertex0()->incident_edge(&(*it)); | |
475 | } | |
476 | } | |
477 | ||
478 | // Remove degenerate vertices. | |
479 | vertex_iterator last_vertex = vertices_.begin(); | |
480 | for (vertex_iterator it = vertices_.begin(); it != vertices_.end(); ++it) { | |
481 | if (it->incident_edge()) { | |
482 | if (it != last_vertex) { | |
483 | *last_vertex = *it; | |
484 | vertex_type* v = &(*last_vertex); | |
485 | edge_type* e = v->incident_edge(); | |
486 | do { | |
487 | e->vertex0(v); | |
488 | e = e->rot_next(); | |
489 | } while (e != v->incident_edge()); | |
490 | } | |
491 | ++last_vertex; | |
492 | } | |
493 | } | |
494 | vertices_.erase(last_vertex, vertices_.end()); | |
495 | ||
496 | // Set up next/prev pointers for infinite edges. | |
497 | if (vertices_.empty()) { | |
498 | if (!edges_.empty()) { | |
499 | // Update prev/next pointers for the line edges. | |
500 | edge_iterator edge_it = edges_.begin(); | |
501 | edge_type* edge1 = &(*edge_it); | |
502 | edge1->next(edge1); | |
503 | edge1->prev(edge1); | |
504 | ++edge_it; | |
505 | edge1 = &(*edge_it); | |
506 | ++edge_it; | |
507 | ||
508 | while (edge_it != edges_.end()) { | |
509 | edge_type* edge2 = &(*edge_it); | |
510 | ++edge_it; | |
511 | ||
512 | edge1->next(edge2); | |
513 | edge1->prev(edge2); | |
514 | edge2->next(edge1); | |
515 | edge2->prev(edge1); | |
516 | ||
517 | edge1 = &(*edge_it); | |
518 | ++edge_it; | |
519 | } | |
520 | ||
521 | edge1->next(edge1); | |
522 | edge1->prev(edge1); | |
523 | } | |
524 | } else { | |
525 | // Update prev/next pointers for the ray edges. | |
526 | for (cell_iterator cell_it = cells_.begin(); | |
527 | cell_it != cells_.end(); ++cell_it) { | |
528 | if (cell_it->is_degenerate()) | |
529 | continue; | |
530 | // Move to the previous edge while | |
531 | // it is possible in the CW direction. | |
532 | edge_type* left_edge = cell_it->incident_edge(); | |
533 | while (left_edge->prev() != NULL) { | |
534 | left_edge = left_edge->prev(); | |
535 | // Terminate if this is not a boundary cell. | |
536 | if (left_edge == cell_it->incident_edge()) | |
537 | break; | |
538 | } | |
539 | ||
540 | if (left_edge->prev() != NULL) | |
541 | continue; | |
542 | ||
543 | edge_type* right_edge = cell_it->incident_edge(); | |
544 | while (right_edge->next() != NULL) | |
545 | right_edge = right_edge->next(); | |
546 | left_edge->prev(right_edge); | |
547 | right_edge->next(left_edge); | |
548 | } | |
549 | } | |
550 | } | |
551 | ||
552 | private: | |
553 | typedef typename cell_container_type::iterator cell_iterator; | |
554 | typedef typename vertex_container_type::iterator vertex_iterator; | |
555 | typedef typename edge_container_type::iterator edge_iterator; | |
556 | typedef typename TRAITS::vertex_equality_predicate_type | |
557 | vertex_equality_predicate_type; | |
558 | ||
559 | template <typename SEvent> | |
560 | bool is_primary_edge(const SEvent& site1, const SEvent& site2) const { | |
561 | bool flag1 = site1.is_segment(); | |
562 | bool flag2 = site2.is_segment(); | |
563 | if (flag1 && !flag2) { | |
564 | return (site1.point0() != site2.point0()) && | |
565 | (site1.point1() != site2.point0()); | |
566 | } | |
567 | if (!flag1 && flag2) { | |
568 | return (site2.point0() != site1.point0()) && | |
569 | (site2.point1() != site1.point0()); | |
570 | } | |
571 | return true; | |
572 | } | |
573 | ||
574 | template <typename SEvent> | |
575 | bool is_linear_edge(const SEvent& site1, const SEvent& site2) const { | |
576 | if (!is_primary_edge(site1, site2)) { | |
577 | return true; | |
578 | } | |
579 | return !(site1.is_segment() ^ site2.is_segment()); | |
580 | } | |
581 | ||
582 | // Remove degenerate edge. | |
583 | void remove_edge(edge_type* edge) { | |
584 | // Update the endpoints of the incident edges to the second vertex. | |
585 | vertex_type* vertex = edge->vertex0(); | |
586 | edge_type* updated_edge = edge->twin()->rot_next(); | |
587 | while (updated_edge != edge->twin()) { | |
588 | updated_edge->vertex0(vertex); | |
589 | updated_edge = updated_edge->rot_next(); | |
590 | } | |
591 | ||
592 | edge_type* edge1 = edge; | |
593 | edge_type* edge2 = edge->twin(); | |
594 | ||
595 | edge_type* edge1_rot_prev = edge1->rot_prev(); | |
596 | edge_type* edge1_rot_next = edge1->rot_next(); | |
597 | ||
598 | edge_type* edge2_rot_prev = edge2->rot_prev(); | |
599 | edge_type* edge2_rot_next = edge2->rot_next(); | |
600 | ||
601 | // Update prev/next pointers for the incident edges. | |
602 | edge1_rot_next->twin()->next(edge2_rot_prev); | |
603 | edge2_rot_prev->prev(edge1_rot_next->twin()); | |
604 | edge1_rot_prev->prev(edge2_rot_next->twin()); | |
605 | edge2_rot_next->twin()->next(edge1_rot_prev); | |
606 | } | |
607 | ||
608 | cell_container_type cells_; | |
609 | vertex_container_type vertices_; | |
610 | edge_container_type edges_; | |
611 | vertex_equality_predicate_type vertex_equality_predicate_; | |
612 | ||
613 | // Disallow copy constructor and operator= | |
614 | voronoi_diagram(const voronoi_diagram&); | |
615 | void operator=(const voronoi_diagram&); | |
616 | }; | |
617 | } // polygon | |
618 | } // boost | |
619 | ||
620 | #endif // BOOST_POLYGON_VORONOI_DIAGRAM |