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
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
// Boost.Polygon library detail/voronoi_structures.hpp header file
// Copyright Andrii Sydorchuk 2010-2012.
// 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)
// See http://www.boost.org for updates, documentation, and revision history.
#ifndef BOOST_POLYGON_DETAIL_VORONOI_STRUCTURES
#define BOOST_POLYGON_DETAIL_VORONOI_STRUCTURES
#include <list>
#include <queue>
#include <vector>
#include "boost/polygon/voronoi_geometry_type.hpp"
namespace boost {
namespace polygon {
namespace detail {
// Cartesian 2D point data structure.
template <typename T>
class point_2d {
public:
typedef T coordinate_type;
point_2d() {}
point_2d(coordinate_type x, coordinate_type y) :
x_(x),
y_(y) {}
bool operator==(const point_2d& that) const {
return (this->x_ == that.x()) && (this->y_ == that.y());
}
bool operator!=(const point_2d& that) const {
return (this->x_ != that.x()) || (this->y_ != that.y());
}
coordinate_type x() const {
return x_;
}
coordinate_type y() const {
return y_;
}
point_2d& x(coordinate_type x) {
x_ = x;
return *this;
}
point_2d& y(coordinate_type y) {
y_ = y;
return *this;
}
private:
coordinate_type x_;
coordinate_type y_;
};
// Site event type.
// Occurs when the sweepline sweeps over one of the initial sites:
// 1) point site
// 2) start-point of the segment site
// 3) endpoint of the segment site
// Implicit segment direction is defined: the start-point of
// the segment compares less than its endpoint.
// Each input segment is divided onto two site events:
// 1) One going from the start-point to the endpoint
// (is_inverse() = false)
// 2) Another going from the endpoint to the start-point
// (is_inverse() = true)
// In beach line data structure segment sites of the first
// type precede sites of the second type for the same segment.
// Members:
// point0_ - point site or segment's start-point
// point1_ - segment's endpoint if site is a segment
// sorted_index_ - the last bit encodes information if the site is inverse;
// the other bits encode site event index among the sorted site events
// initial_index_ - site index among the initial input set
// Note: for all sites is_inverse_ flag is equal to false by default.
template <typename T>
class site_event {
public:
typedef T coordinate_type;
typedef point_2d<T> point_type;
site_event() :
point0_(0, 0),
point1_(0, 0),
sorted_index_(0),
flags_(0) {}
site_event(coordinate_type x, coordinate_type y) :
point0_(x, y),
point1_(x, y),
sorted_index_(0),
flags_(0) {}
explicit site_event(const point_type& point) :
point0_(point),
point1_(point),
sorted_index_(0),
flags_(0) {}
site_event(coordinate_type x1, coordinate_type y1,
coordinate_type x2, coordinate_type y2):
point0_(x1, y1),
point1_(x2, y2),
sorted_index_(0),
flags_(0) {}
site_event(const point_type& point1, const point_type& point2) :
point0_(point1),
point1_(point2),
sorted_index_(0),
flags_(0) {}
bool operator==(const site_event& that) const {
return (this->point0_ == that.point0_) &&
(this->point1_ == that.point1_);
}
bool operator!=(const site_event& that) const {
return (this->point0_ != that.point0_) ||
(this->point1_ != that.point1_);
}
coordinate_type x(bool oriented = false) const {
return x0(oriented);
}
coordinate_type y(bool oriented = false) const {
return y0(oriented);
}
coordinate_type x0(bool oriented = false) const {
if (!oriented)
return point0_.x();
return is_inverse() ? point1_.x() : point0_.x();
}
coordinate_type y0(bool oriented = false) const {
if (!oriented)
return point0_.y();
return is_inverse() ? point1_.y() : point0_.y();
}
coordinate_type x1(bool oriented = false) const {
if (!oriented)
return point1_.x();
return is_inverse() ? point0_.x() : point1_.x();
}
coordinate_type y1(bool oriented = false) const {
if (!oriented)
return point1_.y();
return is_inverse() ? point0_.y() : point1_.y();
}
const point_type& point0(bool oriented = false) const {
if (!oriented)
return point0_;
return is_inverse() ? point1_ : point0_;
}
const point_type& point1(bool oriented = false) const {
if (!oriented)
return point1_;
return is_inverse() ? point0_ : point1_;
}
std::size_t sorted_index() const {
return sorted_index_;
}
site_event& sorted_index(std::size_t index) {
sorted_index_ = index;
return *this;
}
std::size_t initial_index() const {
return initial_index_;
}
site_event& initial_index(std::size_t index) {
initial_index_ = index;
return *this;
}
bool is_inverse() const {
return (flags_ & IS_INVERSE) ? true : false;
}
site_event& inverse() {
flags_ ^= IS_INVERSE;
return *this;
}
SourceCategory source_category() const {
return static_cast<SourceCategory>(flags_ & SOURCE_CATEGORY_BITMASK);
}
site_event& source_category(SourceCategory source_category) {
flags_ |= source_category;
return *this;
}
bool is_point() const {
return (point0_.x() == point1_.x()) && (point0_.y() == point1_.y());
}
bool is_segment() const {
return (point0_.x() != point1_.x()) || (point0_.y() != point1_.y());
}
private:
enum Bits {
IS_INVERSE = 0x20 // 32
};
point_type point0_;
point_type point1_;
std::size_t sorted_index_;
std::size_t initial_index_;
std::size_t flags_;
};
// Circle event type.
// Occurs when the sweepline sweeps over the rightmost point of the Voronoi
// circle (with the center at the intersection point of the bisectors).
// Circle event is made of the two consecutive nodes in the beach line data
// structure. In case another node was inserted during algorithm execution
// between the given two nodes circle event becomes inactive.
// Variables:
// center_x_ - center x-coordinate;
// center_y_ - center y-coordinate;
// lower_x_ - leftmost x-coordinate;
// is_active_ - states whether circle event is still active.
// NOTE: lower_y coordinate is always equal to center_y.
template <typename T>
class circle_event {
public:
typedef T coordinate_type;
circle_event() : is_active_(true) {}
circle_event(coordinate_type c_x,
coordinate_type c_y,
coordinate_type lower_x) :
center_x_(c_x),
center_y_(c_y),
lower_x_(lower_x),
is_active_(true) {}
coordinate_type x() const {
return center_x_;
}
circle_event& x(coordinate_type center_x) {
center_x_ = center_x;
return *this;
}
coordinate_type y() const {
return center_y_;
}
circle_event& y(coordinate_type center_y) {
center_y_ = center_y;
return *this;
}
coordinate_type lower_x() const {
return lower_x_;
}
circle_event& lower_x(coordinate_type lower_x) {
lower_x_ = lower_x;
return *this;
}
coordinate_type lower_y() const {
return center_y_;
}
bool is_active() const {
return is_active_;
}
circle_event& deactivate() {
is_active_ = false;
return *this;
}
private:
coordinate_type center_x_;
coordinate_type center_y_;
coordinate_type lower_x_;
bool is_active_;
};
// Event queue data structure, holds circle events.
// During algorithm run, some of the circle events disappear (become
// inactive). Priority queue data structure doesn't support
// iterators (there is no direct ability to modify its elements).
// Instead list is used to store all the circle events and priority queue
// of the iterators to the list elements is used to keep the correct circle
// events ordering.
template <typename T, typename Predicate>
class ordered_queue {
public:
ordered_queue() {}
bool empty() const {
return c_.empty();
}
const T &top() const {
return *c_.top();
}
void pop() {
list_iterator_type it = c_.top();
c_.pop();
c_list_.erase(it);
}
T &push(const T &e) {
c_list_.push_front(e);
c_.push(c_list_.begin());
return c_list_.front();
}
void clear() {
while (!c_.empty())
c_.pop();
c_list_.clear();
}
private:
typedef typename std::list<T>::iterator list_iterator_type;
struct comparison {
bool operator() (const list_iterator_type &it1,
const list_iterator_type &it2) const {
return cmp_(*it1, *it2);
}
Predicate cmp_;
};
std::priority_queue< list_iterator_type,
std::vector<list_iterator_type>,
comparison > c_;
std::list<T> c_list_;
// Disallow copy constructor and operator=
ordered_queue(const ordered_queue&);
void operator=(const ordered_queue&);
};
// Represents a bisector node made by two arcs that correspond to the left
// and right sites. Arc is defined as a curve with points equidistant from
// the site and from the sweepline. If the site is a point then arc is
// a parabola, otherwise it's a line segment. A segment site event will
// produce different bisectors based on its direction.
// In general case two sites will create two opposite bisectors. That's
// why the order of the sites is important to define the unique bisector.
// The one site is considered to be newer than the other one if it was
// processed by the algorithm later (has greater index).
template <typename Site>
class beach_line_node_key {
public:
typedef Site site_type;
// Constructs degenerate bisector, used to search an arc that is above
// the given site. The input to the constructor is the new site point.
explicit beach_line_node_key(const site_type &new_site) :
left_site_(new_site),
right_site_(new_site) {}
// Constructs a new bisector. The input to the constructor is the two
// sites that create the bisector. The order of sites is important.
beach_line_node_key(const site_type &left_site,
const site_type &right_site) :
left_site_(left_site),
right_site_(right_site) {}
const site_type &left_site() const {
return left_site_;
}
site_type &left_site() {
return left_site_;
}
beach_line_node_key& left_site(const site_type &site) {
left_site_ = site;
return *this;
}
const site_type &right_site() const {
return right_site_;
}
site_type &right_site() {
return right_site_;
}
beach_line_node_key& right_site(const site_type &site) {
right_site_ = site;
return *this;
}
private:
site_type left_site_;
site_type right_site_;
};
// Represents edge data structure from the Voronoi output, that is
// associated as a value with beach line bisector in the beach
// line. Contains pointer to the circle event in the circle event
// queue if the edge corresponds to the right bisector of the circle event.
template <typename Edge, typename Circle>
class beach_line_node_data {
public:
explicit beach_line_node_data(Edge* new_edge) :
circle_event_(NULL),
edge_(new_edge) {}
Circle* circle_event() const {
return circle_event_;
}
beach_line_node_data& circle_event(Circle* circle_event) {
circle_event_ = circle_event;
return *this;
}
Edge* edge() const {
return edge_;
}
beach_line_node_data& edge(Edge* new_edge) {
edge_ = new_edge;
return *this;
}
private:
Circle* circle_event_;
Edge* edge_;
};
} // detail
} // polygon
} // boost
#endif // BOOST_POLYGON_DETAIL_VORONOI_STRUCTURES