1 | // Boost.Polygon library voronoi.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 |
11 | #define BOOST_POLYGON_VORONOI |
12 | |
13 | #include "isotropy.hpp" |
14 | #include "point_concept.hpp" |
15 | #include "segment_concept.hpp" |
16 | |
17 | #include "voronoi_builder.hpp" |
18 | #include "voronoi_diagram.hpp" |
19 | |
20 | // Public methods to compute Voronoi diagram of a set of points and segments. |
21 | // Coordinates of the points and of the endpoints of the segments should belong |
22 | // to the 32-bit signed integer range [-2^31, 2^31-1]. To use wider input |
23 | // coordinate range voronoi_builder configuration via coordinate type traits |
24 | // is required. |
25 | // Complexity - O(N*logN), memory usage - O(N), N - number of input objects. |
26 | namespace boost { |
27 | namespace polygon { |
28 | |
29 | template <typename Point, typename VB> |
30 | typename enable_if< |
31 | typename gtl_if< |
32 | typename is_point_concept< |
33 | typename geometry_concept<Point>::type |
34 | >::type |
35 | >::type, |
36 | std::size_t |
37 | >::type insert(const Point& point, VB* vb) { |
38 | return vb->insert_point(x(point), y(point)); |
39 | } |
40 | |
41 | template <typename PointIterator, typename VB> |
42 | typename enable_if< |
43 | typename gtl_if< |
44 | typename is_point_concept< |
45 | typename geometry_concept< |
46 | typename std::iterator_traits<PointIterator>::value_type |
47 | >::type |
48 | >::type |
49 | >::type, |
50 | void |
51 | >::type insert(const PointIterator first, const PointIterator last, VB* vb) { |
52 | for (PointIterator it = first; it != last; ++it) { |
53 | insert(*it, vb); |
54 | } |
55 | } |
56 | |
57 | template <typename Segment, typename VB> |
58 | typename enable_if< |
59 | typename gtl_if< |
60 | typename is_segment_concept< |
61 | typename geometry_concept<Segment>::type |
62 | >::type |
63 | >::type, |
64 | std::size_t |
65 | >::type insert(const Segment& segment, VB* vb) { |
66 | return vb->insert_segment( |
67 | x(low(segment)), y(low(segment)), |
68 | x(high(segment)), y(high(segment))); |
69 | } |
70 | |
71 | template <typename SegmentIterator, typename VB> |
72 | typename enable_if< |
73 | typename gtl_if< |
74 | typename is_segment_concept< |
75 | typename geometry_concept< |
76 | typename std::iterator_traits<SegmentIterator>::value_type |
77 | >::type |
78 | >::type |
79 | >::type, |
80 | void |
81 | >::type insert(const SegmentIterator first, |
82 | const SegmentIterator last, |
83 | VB* vb) { |
84 | for (SegmentIterator it = first; it != last; ++it) { |
85 | insert(*it, vb); |
86 | } |
87 | } |
88 | |
89 | template <typename PointIterator, typename VD> |
90 | typename enable_if< |
91 | typename gtl_if< |
92 | typename is_point_concept< |
93 | typename geometry_concept< |
94 | typename std::iterator_traits<PointIterator>::value_type |
95 | >::type |
96 | >::type |
97 | >::type, |
98 | void |
99 | >::type construct_voronoi(const PointIterator first, |
100 | const PointIterator last, |
101 | VD* vd) { |
102 | default_voronoi_builder builder; |
103 | insert(first, last, &builder); |
104 | builder.construct(vd); |
105 | } |
106 | |
107 | template <typename SegmentIterator, typename VD> |
108 | typename enable_if< |
109 | typename gtl_if< |
110 | typename is_segment_concept< |
111 | typename geometry_concept< |
112 | typename std::iterator_traits<SegmentIterator>::value_type |
113 | >::type |
114 | >::type |
115 | >::type, |
116 | void |
117 | >::type construct_voronoi(const SegmentIterator first, |
118 | const SegmentIterator last, |
119 | VD* vd) { |
120 | default_voronoi_builder builder; |
121 | insert(first, last, &builder); |
122 | builder.construct(vd); |
123 | } |
124 | |
125 | template <typename PointIterator, typename SegmentIterator, typename VD> |
126 | typename enable_if< |
127 | typename gtl_and< |
128 | typename gtl_if< |
129 | typename is_point_concept< |
130 | typename geometry_concept< |
131 | typename std::iterator_traits<PointIterator>::value_type |
132 | >::type |
133 | >::type |
134 | >::type, |
135 | typename gtl_if< |
136 | typename is_segment_concept< |
137 | typename geometry_concept< |
138 | typename std::iterator_traits<SegmentIterator>::value_type |
139 | >::type |
140 | >::type |
141 | >::type |
142 | >::type, |
143 | void |
144 | >::type construct_voronoi(const PointIterator p_first, |
145 | const PointIterator p_last, |
146 | const SegmentIterator s_first, |
147 | const SegmentIterator s_last, |
148 | VD* vd) { |
149 | default_voronoi_builder builder; |
150 | insert(p_first, p_last, &builder); |
151 | insert(s_first, s_last, &builder); |
152 | builder.construct(vd); |
153 | } |
154 | } // polygon |
155 | } // boost |
156 | |
157 | #endif // BOOST_POLYGON_VORONOI |
158 | |