ceph/src/boost/libs/polygon/test/voronoi_test_helper.hpp

   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>
  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>
  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>
  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 {
 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();
 107   }
 108 };
 109
 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());
 124       }
 125     }
 126   }
 127   return !intersection_check(edge_map);
 128 }
 129
 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
 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>
 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>
 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>
 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>
 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