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.
26namespace boost {
27namespace polygon {
28
29template <typename Point, typename VB>
30typename 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
41template <typename PointIterator, typename VB>
42typename 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
57template <typename Segment, typename VB>
58typename 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
71template <typename SegmentIterator, typename VB>
72typename 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
89template <typename PointIterator, typename VD>
90typename 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
107template <typename SegmentIterator, typename VD>
108typename 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
125template <typename PointIterator, typename SegmentIterator, typename VD>
126typename 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

source code of boost/boost/polygon/voronoi.hpp