]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // Boost.Polygon library voronoi_basic_tutorial.cpp 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 | #include <cstdio> | |
11 | #include <vector> | |
12 | ||
13 | #include <boost/polygon/voronoi.hpp> | |
14 | using boost::polygon::voronoi_builder; | |
15 | using boost::polygon::voronoi_diagram; | |
16 | using boost::polygon::x; | |
17 | using boost::polygon::y; | |
18 | using boost::polygon::low; | |
19 | using boost::polygon::high; | |
20 | ||
21 | #include "voronoi_visual_utils.hpp" | |
22 | ||
23 | struct Point { | |
24 | int a; | |
25 | int b; | |
26 | Point(int x, int y) : a(x), b(y) {} | |
27 | }; | |
28 | ||
29 | struct Segment { | |
30 | Point p0; | |
31 | Point p1; | |
32 | Segment(int x1, int y1, int x2, int y2) : p0(x1, y1), p1(x2, y2) {} | |
33 | }; | |
34 | ||
35 | namespace boost { | |
36 | namespace polygon { | |
37 | ||
38 | template <> | |
39 | struct geometry_concept<Point> { | |
40 | typedef point_concept type; | |
41 | }; | |
42 | ||
43 | template <> | |
44 | struct point_traits<Point> { | |
45 | typedef int coordinate_type; | |
46 | ||
47 | static inline coordinate_type get( | |
48 | const Point& point, orientation_2d orient) { | |
49 | return (orient == HORIZONTAL) ? point.a : point.b; | |
50 | } | |
51 | }; | |
52 | ||
53 | template <> | |
54 | struct geometry_concept<Segment> { | |
55 | typedef segment_concept type; | |
56 | }; | |
57 | ||
58 | template <> | |
59 | struct segment_traits<Segment> { | |
60 | typedef int coordinate_type; | |
61 | typedef Point point_type; | |
62 | ||
63 | static inline point_type get(const Segment& segment, direction_1d dir) { | |
64 | return dir.to_int() ? segment.p1 : segment.p0; | |
65 | } | |
66 | }; | |
67 | } // polygon | |
68 | } // boost | |
69 | ||
70 | // Traversing Voronoi edges using edge iterator. | |
71 | int iterate_primary_edges1(const voronoi_diagram<double>& vd) { | |
72 | int result = 0; | |
73 | for (voronoi_diagram<double>::const_edge_iterator it = vd.edges().begin(); | |
74 | it != vd.edges().end(); ++it) { | |
75 | if (it->is_primary()) | |
76 | ++result; | |
77 | } | |
78 | return result; | |
79 | } | |
80 | ||
81 | // Traversing Voronoi edges using cell iterator. | |
82 | int iterate_primary_edges2(const voronoi_diagram<double> &vd) { | |
83 | int result = 0; | |
84 | for (voronoi_diagram<double>::const_cell_iterator it = vd.cells().begin(); | |
85 | it != vd.cells().end(); ++it) { | |
86 | const voronoi_diagram<double>::cell_type& cell = *it; | |
87 | const voronoi_diagram<double>::edge_type* edge = cell.incident_edge(); | |
88 | // This is convenient way to iterate edges around Voronoi cell. | |
89 | do { | |
90 | if (edge->is_primary()) | |
91 | ++result; | |
92 | edge = edge->next(); | |
93 | } while (edge != cell.incident_edge()); | |
94 | } | |
95 | return result; | |
96 | } | |
97 | ||
98 | // Traversing Voronoi edges using vertex iterator. | |
99 | // As opposite to the above two functions this one will not iterate through | |
100 | // edges without finite endpoints and will iterate only once through edges | |
101 | // with single finite endpoint. | |
102 | int iterate_primary_edges3(const voronoi_diagram<double> &vd) { | |
103 | int result = 0; | |
104 | for (voronoi_diagram<double>::const_vertex_iterator it = | |
105 | vd.vertices().begin(); it != vd.vertices().end(); ++it) { | |
106 | const voronoi_diagram<double>::vertex_type& vertex = *it; | |
107 | const voronoi_diagram<double>::edge_type* edge = vertex.incident_edge(); | |
108 | // This is convenient way to iterate edges around Voronoi vertex. | |
109 | do { | |
110 | if (edge->is_primary()) | |
111 | ++result; | |
112 | edge = edge->rot_next(); | |
113 | } while (edge != vertex.incident_edge()); | |
114 | } | |
115 | return result; | |
116 | } | |
117 | ||
118 | int main() { | |
119 | // Preparing Input Geometries. | |
120 | std::vector<Point> points; | |
121 | points.push_back(Point(0, 0)); | |
122 | points.push_back(Point(1, 6)); | |
123 | std::vector<Segment> segments; | |
124 | segments.push_back(Segment(-4, 5, 5, -1)); | |
125 | segments.push_back(Segment(3, -11, 13, -1)); | |
126 | ||
127 | // Construction of the Voronoi Diagram. | |
128 | voronoi_diagram<double> vd; | |
129 | construct_voronoi(points.begin(), points.end(), | |
130 | segments.begin(), segments.end(), | |
131 | &vd); | |
132 | ||
133 | // Traversing Voronoi Graph. | |
134 | { | |
135 | printf("Traversing Voronoi graph.\n"); | |
136 | printf("Number of visited primary edges using edge iterator: %d\n", | |
137 | iterate_primary_edges1(vd)); | |
138 | printf("Number of visited primary edges using cell iterator: %d\n", | |
139 | iterate_primary_edges2(vd)); | |
140 | printf("Number of visited primary edges using vertex iterator: %d\n", | |
141 | iterate_primary_edges3(vd)); | |
142 | printf("\n"); | |
143 | } | |
144 | ||
145 | // Using color member of the Voronoi primitives to store the average number | |
146 | // of edges around each cell (including secondary edges). | |
147 | { | |
148 | printf("Number of edges (including secondary) around the Voronoi cells:\n"); | |
149 | for (voronoi_diagram<double>::const_edge_iterator it = vd.edges().begin(); | |
150 | it != vd.edges().end(); ++it) { | |
151 | std::size_t cnt = it->cell()->color(); | |
152 | it->cell()->color(cnt + 1); | |
153 | } | |
154 | for (voronoi_diagram<double>::const_cell_iterator it = vd.cells().begin(); | |
155 | it != vd.cells().end(); ++it) { | |
156 | printf("%lu ", it->color()); | |
157 | } | |
158 | printf("\n"); | |
159 | printf("\n"); | |
160 | } | |
161 | ||
162 | // Linking Voronoi cells with input geometries. | |
163 | { | |
164 | unsigned int cell_index = 0; | |
165 | for (voronoi_diagram<double>::const_cell_iterator it = vd.cells().begin(); | |
166 | it != vd.cells().end(); ++it) { | |
167 | if (it->contains_point()) { | |
7c673cae | 168 | if (it->source_category() == |
92f5a8d4 TL |
169 | boost::polygon::SOURCE_CATEGORY_SINGLE_POINT) { |
170 | std::size_t index = it->source_index(); | |
171 | Point p = points[index]; | |
172 | printf("Cell #%u contains a point: (%d, %d).\n", | |
173 | cell_index, x(p), y(p)); | |
174 | } else if (it->source_category() == | |
175 | boost::polygon::SOURCE_CATEGORY_SEGMENT_START_POINT) { | |
176 | std::size_t index = it->source_index() - points.size(); | |
177 | Point p0 = low(segments[index]); | |
178 | printf("Cell #%u contains segment start point: (%d, %d).\n", | |
7c673cae FG |
179 | cell_index, x(p0), y(p0)); |
180 | } else if (it->source_category() == | |
181 | boost::polygon::SOURCE_CATEGORY_SEGMENT_END_POINT) { | |
92f5a8d4 TL |
182 | std::size_t index = it->source_index() - points.size(); |
183 | Point p1 = high(segments[index]); | |
184 | printf("Cell #%u contains segment end point: (%d, %d).\n", | |
185 | cell_index, x(p1), y(p1)); | |
7c673cae | 186 | } |
92f5a8d4 TL |
187 | } else { |
188 | std::size_t index = it->source_index() - points.size(); | |
189 | Point p0 = low(segments[index]); | |
190 | Point p1 = high(segments[index]); | |
191 | printf("Cell #%u contains a segment: ((%d, %d), (%d, %d)). \n", | |
192 | cell_index, x(p0), y(p0), x(p1), y(p1)); | |
7c673cae FG |
193 | } |
194 | ++cell_index; | |
195 | } | |
196 | } | |
197 | return 0; | |
198 | } |