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
|
// Boost.Polygon library voronoi.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_VORONOI
#define BOOST_POLYGON_VORONOI
#include "isotropy.hpp"
#include "point_concept.hpp"
#include "segment_concept.hpp"
#include "voronoi_builder.hpp"
#include "voronoi_diagram.hpp"
// Public methods to compute Voronoi diagram of a set of points and segments.
// Coordinates of the points and of the endpoints of the segments should belong
// to the 32-bit signed integer range [-2^31, 2^31-1]. To use wider input
// coordinate range voronoi_builder configuration via coordinate type traits
// is required.
// Complexity - O(N*logN), memory usage - O(N), N - number of input objects.
namespace boost {
namespace polygon {
template <typename Point, typename VB>
typename enable_if<
typename gtl_if<
typename is_point_concept<
typename geometry_concept<Point>::type
>::type
>::type,
std::size_t
>::type insert(const Point& point, VB* vb) {
return vb->insert_point(x(point), y(point));
}
template <typename PointIterator, typename VB>
typename enable_if<
typename gtl_if<
typename is_point_concept<
typename geometry_concept<
typename std::iterator_traits<PointIterator>::value_type
>::type
>::type
>::type,
void
>::type insert(const PointIterator first, const PointIterator last, VB* vb) {
for (PointIterator it = first; it != last; ++it) {
insert(*it, vb);
}
}
template <typename Segment, typename VB>
typename enable_if<
typename gtl_if<
typename is_segment_concept<
typename geometry_concept<Segment>::type
>::type
>::type,
std::size_t
>::type insert(const Segment& segment, VB* vb) {
return vb->insert_segment(
x(low(segment)), y(low(segment)),
x(high(segment)), y(high(segment)));
}
template <typename SegmentIterator, typename VB>
typename enable_if<
typename gtl_if<
typename is_segment_concept<
typename geometry_concept<
typename std::iterator_traits<SegmentIterator>::value_type
>::type
>::type
>::type,
void
>::type insert(const SegmentIterator first,
const SegmentIterator last,
VB* vb) {
for (SegmentIterator it = first; it != last; ++it) {
insert(*it, vb);
}
}
template <typename PointIterator, typename VD>
typename enable_if<
typename gtl_if<
typename is_point_concept<
typename geometry_concept<
typename std::iterator_traits<PointIterator>::value_type
>::type
>::type
>::type,
void
>::type construct_voronoi(const PointIterator first,
const PointIterator last,
VD* vd) {
default_voronoi_builder builder;
insert(first, last, &builder);
builder.construct(vd);
}
template <typename SegmentIterator, typename VD>
typename enable_if<
typename gtl_if<
typename is_segment_concept<
typename geometry_concept<
typename std::iterator_traits<SegmentIterator>::value_type
>::type
>::type
>::type,
void
>::type construct_voronoi(const SegmentIterator first,
const SegmentIterator last,
VD* vd) {
default_voronoi_builder builder;
insert(first, last, &builder);
builder.construct(vd);
}
template <typename PointIterator, typename SegmentIterator, typename VD>
typename enable_if<
typename gtl_and<
typename gtl_if<
typename is_point_concept<
typename geometry_concept<
typename std::iterator_traits<PointIterator>::value_type
>::type
>::type
>::type,
typename gtl_if<
typename is_segment_concept<
typename geometry_concept<
typename std::iterator_traits<SegmentIterator>::value_type
>::type
>::type
>::type
>::type,
void
>::type construct_voronoi(const PointIterator p_first,
const PointIterator p_last,
const SegmentIterator s_first,
const SegmentIterator s_last,
VD* vd) {
default_voronoi_builder builder;
insert(p_first, p_last, &builder);
insert(s_first, s_last, &builder);
builder.construct(vd);
}
} // polygon
} // boost
#endif // BOOST_POLYGON_VORONOI
|
