1 // Boost.Polygon library voronoi.hpp header file
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)
8 // See http://www.boost.org for updates, documentation, and revision history.
10 #ifndef BOOST_POLYGON_VORONOI
11 #define BOOST_POLYGON_VORONOI
13 #include "isotropy.hpp"
14 #include "point_concept.hpp"
15 #include "segment_concept.hpp"
17 #include "voronoi_builder.hpp"
18 #include "voronoi_diagram.hpp"
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
25 // Complexity - O(N*logN), memory usage - O(N), N - number of input objects.
29 template <typename Point, typename VB>
32 typename is_point_concept<
33 typename geometry_concept<Point>::type
37 >::type insert(const Point& point, VB* vb) {
38 return vb->insert_point(x(point), y(point));
41 template <typename PointIterator, typename VB>
44 typename is_point_concept<
45 typename geometry_concept<
46 typename std::iterator_traits<PointIterator>::value_type
51 >::type insert(const PointIterator first, const PointIterator last, VB* vb) {
52 for (PointIterator it = first; it != last; ++it) {
57 template <typename Segment, typename VB>
60 typename is_segment_concept<
61 typename geometry_concept<Segment>::type
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)));
71 template <typename SegmentIterator, typename VB>
74 typename is_segment_concept<
75 typename geometry_concept<
76 typename std::iterator_traits<SegmentIterator>::value_type
81 >::type insert(const SegmentIterator first,
82 const SegmentIterator last,
84 for (SegmentIterator it = first; it != last; ++it) {
89 template <typename PointIterator, typename VD>
92 typename is_point_concept<
93 typename geometry_concept<
94 typename std::iterator_traits<PointIterator>::value_type
99 >::type construct_voronoi(const PointIterator first,
100 const PointIterator last,
102 default_voronoi_builder builder;
103 insert(first, last, &builder);
104 builder.construct(vd);
107 template <typename SegmentIterator, typename VD>
110 typename is_segment_concept<
111 typename geometry_concept<
112 typename std::iterator_traits<SegmentIterator>::value_type
117 >::type construct_voronoi(const SegmentIterator first,
118 const SegmentIterator last,
120 default_voronoi_builder builder;
121 insert(first, last, &builder);
122 builder.construct(vd);
125 template <typename PointIterator, typename SegmentIterator, typename VD>
129 typename is_point_concept<
130 typename geometry_concept<
131 typename std::iterator_traits<PointIterator>::value_type
136 typename is_segment_concept<
137 typename geometry_concept<
138 typename std::iterator_traits<SegmentIterator>::value_type
144 >::type construct_voronoi(const PointIterator p_first,
145 const PointIterator p_last,
146 const SegmentIterator s_first,
147 const SegmentIterator s_last,
149 default_voronoi_builder builder;
150 insert(p_first, p_last, &builder);
151 insert(s_first, s_last, &builder);
152 builder.construct(vd);
157 #endif // BOOST_POLYGON_VORONOI