1 // Boost.Polygon library voronoi_test_helper.hpp file
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)
8 // See http://www.boost.org for updates, documentation, and revision history.
10 #ifndef VORONOI_TEST_HELPER
11 #define VORONOI_TEST_HELPER
21 #include <boost/polygon/polygon.hpp>
22 using namespace boost::polygon;
24 namespace voronoi_test_helper {
32 template <typename VERTEX>
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());
40 return (lhs < rhs) ? RIGHT : LEFT;
43 template <typename 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();
51 if (edge->next()->prev() != edge) {
54 if (edge->cell() != &(*cell_it)) {
57 if (edge->vertex1() != edge->next()->vertex0()) {
60 if (edge->vertex0() != NULL &&
61 edge->vertex1() != NULL &&
62 edge->next()->vertex1() != NULL) {
63 if (get_orientation(*edge->vertex0(),
65 *edge->next()->vertex1()) != LEFT) {
70 } while (edge != cell_it->incident_edge());
75 template <typename 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())
83 const voronoi_edge_type* edge = vertex_it->incident_edge();
85 const voronoi_edge_type* next_edge = edge->rot_next();
86 if (edge->vertex0() != next_edge->vertex0()) {
89 if (edge->vertex1() != NULL && next_edge->vertex1() != NULL &&
90 get_orientation(*edge->vertex1(),
92 *next_edge->vertex1()) == LEFT) {
95 edge = edge->rot_next();
96 } while (edge != vertex_it->incident_edge());
101 template <typename VERTEX>
103 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();
110 template <typename 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());
127 return !intersection_check(edge_map);
130 template <typename Point2D>
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
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());
152 // Find the first edge with greater or equal first point.
153 edge_map_it_bound = edge_map.lower_bound(point2);
155 edge_map_it2 = edge_map_it1;
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());
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))
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)
184 INCIDENT_EDGES_CCW_ORDER = 2,
185 NO_HALF_EDGE_INTERSECTIONS = 4,
186 FAST_VERIFICATION = 3,
187 COMPLETE_VERIFICATION = 7
190 template <typename Output>
191 bool verify_output(const Output &output, kVerification mask) {
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);
202 template <typename PointIterator>
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;
213 template <typename SegmentIterator>
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;
225 template <typename T>
226 void clean_segment_set(std::vector< segment_data<T> >& data) {
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;
234 half_edges.reserve(data.size());
235 for (typename std::vector< segment_data<T> >::iterator it = data.begin();
236 it != data.end(); ++it) {
238 Point h = it->high();
239 half_edges.push_back(std::make_pair(half_edge(l, h), id++));
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())
254 result.push_back(segment_data<T>(l, h));
256 std::swap(result, data);
258 } // voronoi_test_helper