1 // Boost.Polygon library voronoi_test_helper.hpp file
2
3 // Copyright Andrii Sydorchuk 2010-2011.
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 VORONOI_TEST_HELPER
11 #define VORONOI_TEST_HELPER
12
13 #include <boost/polygon/polygon.hpp>
14 #include <algorithm>
15 #include <iostream>
16 #include <iterator>
17 #include <fstream>
18 #include <map>
19 #include <vector>
20 #include <utility>
21
22 using namespace boost::polygon;
23
24 namespace voronoi_test_helper {
25
26 enum kOrientation {
27 RIGHT = -1,
28 COLLINEAR = 0,
29 LEFT = 1
30 };
31
32 template <typename VERTEX>
get_orientation(const VERTEX & v1,const VERTEX & v2,const VERTEX & v3)33 kOrientation get_orientation(
34 const VERTEX& v1, const VERTEX& v2, const VERTEX& v3) {
35 typename VERTEX::coordinate_type lhs = (v2.x() - v1.x()) * (v3.y() - v2.y());
36 typename VERTEX::coordinate_type rhs = (v2.y() - v1.y()) * (v3.x() - v2.x());
37 if (lhs == rhs) {
38 return COLLINEAR;
39 }
40 return (lhs < rhs) ? RIGHT : LEFT;
41 }
42
43 template <typename OUTPUT>
verify_cell_convexity(const OUTPUT & output)44 bool verify_cell_convexity(const OUTPUT& output) {
45 typename OUTPUT::const_cell_iterator cell_it;
46 for (cell_it = output.cells().begin();
47 cell_it != output.cells().end(); cell_it++) {
48 const typename OUTPUT::edge_type* edge = cell_it->incident_edge();
49 if (edge)
50 do {
51 if (edge->next()->prev() != edge) {
52 return false;
53 }
54 if (edge->cell() != &(*cell_it)) {
55 return false;
56 }
57 if (edge->vertex1() != edge->next()->vertex0()) {
58 return false;
59 }
60 if (edge->vertex0() != NULL &&
61 edge->vertex1() != NULL &&
62 edge->next()->vertex1() != NULL) {
63 if (get_orientation(*edge->vertex0(),
64 *edge->vertex1(),
65 *edge->next()->vertex1()) != LEFT) {
66 return false;
67 }
68 }
69 edge = edge->next();
70 } while (edge != cell_it->incident_edge());
71 }
72 return true;
73 }
74
75 template <typename OUTPUT>
verify_incident_edges_ccw_order(const OUTPUT & output)76 bool verify_incident_edges_ccw_order(const OUTPUT& output) {
77 typedef typename OUTPUT::edge_type voronoi_edge_type;
78 typename OUTPUT::const_vertex_iterator vertex_it;
79 for (vertex_it = output.vertices().begin();
80 vertex_it != output.vertices().end(); vertex_it++) {
81 if (vertex_it->is_degenerate())
82 continue;
83 const voronoi_edge_type* edge = vertex_it->incident_edge();
84 do {
85 const voronoi_edge_type* next_edge = edge->rot_next();
86 if (edge->vertex0() != next_edge->vertex0()) {
87 return false;
88 }
89 if (edge->vertex1() != NULL && next_edge->vertex1() != NULL &&
90 get_orientation(*edge->vertex1(),
91 *edge->vertex0(),
92 *next_edge->vertex1()) == LEFT) {
93 return false;
94 }
95 edge = edge->rot_next();
96 } while (edge != vertex_it->incident_edge());
97 }
98 return true;
99 }
100
101 template <typename VERTEX>
102 struct cmp {
operator ()voronoi_test_helper::cmp103 bool operator()(const VERTEX& v1, const VERTEX& v2) const {
104 if (v1.x() != v2.x())
105 return v1.x() < v2.x();
106 return v1.y() < v2.y();
107 }
108 };
109
110 template <typename Output>
verfiy_no_line_edge_intersections(const Output & output)111 bool verfiy_no_line_edge_intersections(const Output &output) {
112 // Create map from edges with first point less than the second one.
113 // Key is the first point of the edge, value is a vector of second points
114 // with the same first point.
115 typedef typename Output::vertex_type vertex_type;
116 cmp<vertex_type> comparator;
117 std::map< vertex_type, std::vector<vertex_type>, cmp<vertex_type> > edge_map;
118 typename Output::const_edge_iterator edge_it;
119 for (edge_it = output.edges().begin();
120 edge_it != output.edges().end(); edge_it++) {
121 if (edge_it->is_finite()) {
122 if (comparator(*edge_it->vertex0(), *edge_it->vertex1())) {
123 edge_map[*edge_it->vertex0()].push_back(*edge_it->vertex1());
124 }
125 }
126 }
127 return !intersection_check(edge_map);
128 }
129
130 template <typename Point2D>
intersection_check(const std::map<Point2D,std::vector<Point2D>,cmp<Point2D>> & edge_map)131 bool intersection_check(
132 const std::map< Point2D, std::vector<Point2D>, cmp<Point2D> > &edge_map) {
133 // Iterate over map of edges and check if there are any intersections.
134 // All the edges are stored by the low x value. That's why we iterate
135 // left to right checking for intersections between all pairs of edges
136 // that overlap in the x dimension.
137 // Complexity. Approximately N*sqrt(N). Worst case N^2.
138 typedef Point2D point_type;
139 typedef typename point_type::coordinate_type coordinate_type;
140 typedef typename std::map<point_type, std::vector<point_type>, cmp<Point2D> >::const_iterator
141 edge_map_iterator;
142 typedef typename std::vector<point_type>::size_type size_type;
143 edge_map_iterator edge_map_it1, edge_map_it2, edge_map_it_bound;
144 for (edge_map_it1 = edge_map.begin();
145 edge_map_it1 != edge_map.end(); edge_map_it1++) {
146 const point_type &point1 = edge_map_it1->first;
147 for (size_type i = 0; i < edge_map_it1->second.size(); i++) {
148 const point_type &point2 = edge_map_it1->second[i];
149 coordinate_type min_y1 = (std::min)(point1.y(), point2.y());
150 coordinate_type max_y1 = (std::max)(point1.y(), point2.y());
151
152 // Find the first edge with greater or equal first point.
153 edge_map_it_bound = edge_map.lower_bound(point2);
154
155 edge_map_it2 = edge_map_it1;
156 edge_map_it2++;
157 for (; edge_map_it2 != edge_map_it_bound; edge_map_it2++) {
158 const point_type &point3 = edge_map_it2->first;
159 for (size_type j = 0; j < edge_map_it2->second.size(); j++) {
160 const point_type &point4 = edge_map_it2->second[j];
161 coordinate_type min_y2 = (std::min)(point3.y(), point4.y());
162 coordinate_type max_y2 = (std::max)(point3.y(), point4.y());
163
164 // In most cases it is enought to make
165 // simple intersection check in the y dimension.
166 if (!(max_y1 > min_y2 && max_y2 > min_y1))
167 continue;
168
169 // Intersection check.
170 if (get_orientation(point1, point2, point3) *
171 get_orientation(point1, point2, point4) == RIGHT &&
172 get_orientation(point3, point4, point1) *
173 get_orientation(point3, point4, point2) == RIGHT)
174 return true;
175 }
176 }
177 }
178 }
179 return false;
180 }
181
182 enum kVerification {
183 CELL_CONVEXITY = 1,
184 INCIDENT_EDGES_CCW_ORDER = 2,
185 NO_HALF_EDGE_INTERSECTIONS = 4,
186 FAST_VERIFICATION = 3,
187 COMPLETE_VERIFICATION = 7
188 };
189
190 template <typename Output>
verify_output(const Output & output,kVerification mask)191 bool verify_output(const Output &output, kVerification mask) {
192 bool result = true;
193 if (mask & CELL_CONVEXITY)
194 result &= verify_cell_convexity(output);
195 if (mask & INCIDENT_EDGES_CCW_ORDER)
196 result &= verify_incident_edges_ccw_order(output);
197 if (mask & NO_HALF_EDGE_INTERSECTIONS)
198 result &= verfiy_no_line_edge_intersections(output);
199 return result;
200 }
201
202 template <typename PointIterator>
save_points(PointIterator first,PointIterator last,const char * file_name)203 void save_points(
204 PointIterator first, PointIterator last, const char* file_name) {
205 std::ofstream ofs(file_name);
206 ofs << std::distance(first, last) << std::endl;
207 for (PointIterator it = first; it != last; ++it) {
208 ofs << it->x() << " " << it->y() << std::endl;
209 }
210 ofs.close();
211 }
212
213 template <typename SegmentIterator>
save_segments(SegmentIterator first,SegmentIterator last,const char * file_name)214 void save_segments(
215 SegmentIterator first, SegmentIterator last, const char* file_name) {
216 std::ofstream ofs(file_name);
217 ofs << std::distance(first, last) << std::endl;
218 for (SegmentIterator it = first; it != last; ++it) {
219 ofs << it->low().x() << " " << it->low().y() << " ";
220 ofs << it->high().x() << " " << it->high().y() << std::endl;
221 }
222 ofs.close();
223 }
224
225 template <typename T>
clean_segment_set(std::vector<segment_data<T>> & data)226 void clean_segment_set(std::vector< segment_data<T> >& data) {
227 typedef T Unit;
228 typedef typename scanline_base<Unit>::Point Point;
229 typedef typename scanline_base<Unit>::half_edge half_edge;
230 typedef int segment_id;
231 std::vector<std::pair<half_edge, segment_id> > half_edges;
232 std::vector<std::pair<half_edge, segment_id> > half_edges_out;
233 segment_id id = 0;
234 half_edges.reserve(data.size());
235 for (typename std::vector< segment_data<T> >::iterator it = data.begin();
236 it != data.end(); ++it) {
237 Point l = it->low();
238 Point h = it->high();
239 half_edges.push_back(std::make_pair(half_edge(l, h), id++));
240 }
241 half_edges_out.reserve(half_edges.size());
242 // Apparently no need to pre-sort data when calling validate_scan.
243 line_intersection<Unit>::validate_scan(
244 half_edges_out, half_edges.begin(), half_edges.end());
245 std::vector< segment_data<T> > result;
246 result.reserve(half_edges_out.size());
247 for (std::size_t i = 0; i < half_edges_out.size(); ++i) {
248 id = half_edges_out[i].second;
249 Point l = half_edges_out[i].first.first;
250 Point h = half_edges_out[i].first.second;
251 segment_data<T> orig_seg = data[id];
252 if (orig_seg.high() < orig_seg.low())
253 std::swap(l, h);
254 result.push_back(segment_data<T>(l, h));
255 }
256 std::swap(result, data);
257 }
258 } // voronoi_test_helper
259
260 #endif
261