ceph/src/boost/boost/polygon/detail/voronoi_structures.hpp

   1 // Boost.Polygon library detail/voronoi_structures.hpp header 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 #ifndef BOOST_POLYGON_DETAIL_VORONOI_STRUCTURES
  11 #define BOOST_POLYGON_DETAIL_VORONOI_STRUCTURES
  12
  13 #include <list>
  14 #include <queue>
  15 #include <vector>
  16
  17 #include "boost/polygon/voronoi_geometry_type.hpp"
  18
  19 namespace boost {
  20 namespace polygon {
  21 namespace detail {
  22 // Cartesian 2D point data structure.
  23 template <typename T>
  24 class point_2d {
  25  public:
  26   typedef T coordinate_type;
  27
  28   point_2d() {}
  29
  30   point_2d(coordinate_type x, coordinate_type y) :
  31       x_(x),
  32       y_(y) {}
  33
  34   bool operator==(const point_2d& that) const {
  35     return (this->x_ == that.x()) && (this->y_ == that.y());
  36   }
  37
  38   bool operator!=(const point_2d& that) const {
  39     return (this->x_ != that.x()) || (this->y_ != that.y());
  40   }
  41
  42   coordinate_type x() const {
  43     return x_;
  44   }
  45
  46   coordinate_type y() const {
  47     return y_;
  48   }
  49
  50   point_2d& x(coordinate_type x) {
  51     x_ = x;
  52     return *this;
  53   }
  54
  55   point_2d& y(coordinate_type y) {
  56     y_ = y;
  57     return *this;
  58   }
  59
  60  private:
  61   coordinate_type x_;
  62   coordinate_type y_;
  63 };
  64
  65 // Site event type.
  66 // Occurs when the sweepline sweeps over one of the initial sites:
  67 //   1) point site
  68 //   2) start-point of the segment site
  69 //   3) endpoint of the segment site
  70 // Implicit segment direction is defined: the start-point of
  71 // the segment compares less than its endpoint.
  72 // Each input segment is divided onto two site events:
  73 //   1) One going from the start-point to the endpoint
  74 //      (is_inverse() = false)
  75 //   2) Another going from the endpoint to the start-point
  76 //      (is_inverse() = true)
  77 // In beach line data structure segment sites of the first
  78 // type precede sites of the second type for the same segment.
  79 // Members:
  80 //   point0_ - point site or segment's start-point
  81 //   point1_ - segment's endpoint if site is a segment
  82 //   sorted_index_ - the last bit encodes information if the site is inverse;
  83 //     the other bits encode site event index among the sorted site events
  84 //   initial_index_ - site index among the initial input set
  85 // Note: for all sites is_inverse_ flag is equal to false by default.
  86 template <typename T>
  87 class site_event {
  88  public:
  89   typedef T coordinate_type;
  90   typedef point_2d<T> point_type;
  91
  92   site_event() :
  93       point0_(0, 0),
  94       point1_(0, 0),
  95       sorted_index_(0),
  96       flags_(0) {}
  97
  98   site_event(coordinate_type x, coordinate_type y) :
  99       point0_(x, y),
 100       point1_(x, y),
 101       sorted_index_(0),
 102       flags_(0) {}
 103
 104   explicit site_event(const point_type& point) :
 105       point0_(point),
 106       point1_(point),
 107       sorted_index_(0),
 108       flags_(0) {}
 109
 110   site_event(coordinate_type x1, coordinate_type y1,
 111              coordinate_type x2, coordinate_type y2):
 112       point0_(x1, y1),
 113       point1_(x2, y2),
 114       sorted_index_(0),
 115       flags_(0) {}
 116
 117   site_event(const point_type& point1, const point_type& point2) :
 118       point0_(point1),
 119       point1_(point2),
 120       sorted_index_(0),
 121       flags_(0) {}
 122
 123   bool operator==(const site_event& that) const {
 124     return (this->point0_ == that.point0_) &&
 125            (this->point1_ == that.point1_);
 126   }
 127
 128   bool operator!=(const site_event& that) const {
 129     return (this->point0_ != that.point0_) ||
 130            (this->point1_ != that.point1_);
 131   }
 132
 133   coordinate_type x() const {
 134     return point0_.x();
 135   }
 136
 137   coordinate_type y() const {
 138     return point0_.y();
 139   }
 140
 141   coordinate_type x0() const {
 142     return point0_.x();
 143   }
 144
 145   coordinate_type y0() const {
 146     return point0_.y();
 147   }
 148
 149   coordinate_type x1() const {
 150     return point1_.x();
 151   }
 152
 153   coordinate_type y1() const {
 154     return point1_.y();
 155   }
 156
 157   const point_type& point0() const {
 158     return point0_;
 159   }
 160
 161   const point_type& point1() const {
 162     return point1_;
 163   }
 164
 165   std::size_t sorted_index() const {
 166     return sorted_index_;
 167   }
 168
 169   site_event& sorted_index(std::size_t index) {
 170     sorted_index_ = index;
 171     return *this;
 172   }
 173
 174   std::size_t initial_index() const {
 175     return initial_index_;
 176   }
 177
 178   site_event& initial_index(std::size_t index) {
 179     initial_index_ = index;
 180     return *this;
 181   }
 182
 183   bool is_inverse() const {
 184     return (flags_ & IS_INVERSE) ? true : false;
 185   }
 186
 187   site_event& inverse() {
 188     std::swap(point0_, point1_);
 189     flags_ ^= IS_INVERSE;
 190     return *this;
 191   }
 192
 193   SourceCategory source_category() const {
 194     return static_cast<SourceCategory>(flags_ & SOURCE_CATEGORY_BITMASK);
 195   }
 196
 197   site_event& source_category(SourceCategory source_category) {
 198     flags_ |= source_category;
 199     return *this;
 200   }
 201
 202   bool is_point() const {
 203     return (point0_.x() == point1_.x()) && (point0_.y() == point1_.y());
 204   }
 205
 206   bool is_segment() const {
 207     return (point0_.x() != point1_.x()) || (point0_.y() != point1_.y());
 208   }
 209
 210  private:
 211   enum Bits {
 212     IS_INVERSE = 0x20  // 32
 213   };
 214
 215   point_type point0_;
 216   point_type point1_;
 217   std::size_t sorted_index_;
 218   std::size_t initial_index_;
 219   std::size_t flags_;
 220 };
 221
 222 // Circle event type.
 223 // Occurs when the sweepline sweeps over the rightmost point of the Voronoi
 224 // circle (with the center at the intersection point of the bisectors).
 225 // Circle event is made of the two consecutive nodes in the beach line data
 226 // structure. In case another node was inserted during algorithm execution
 227 // between the given two nodes circle event becomes inactive.
 228 // Variables:
 229 //   center_x_ - center x-coordinate;
 230 //   center_y_ - center y-coordinate;
 231 //   lower_x_ - leftmost x-coordinate;
 232 //   is_active_ - states whether circle event is still active.
 233 // NOTE: lower_y coordinate is always equal to center_y.
 234 template <typename T>
 235 class circle_event {
 236  public:
 237   typedef T coordinate_type;
 238
 239   circle_event() : is_active_(true) {}
 240
 241   circle_event(coordinate_type c_x,
 242                coordinate_type c_y,
 243                coordinate_type lower_x) :
 244       center_x_(c_x),
 245       center_y_(c_y),
 246       lower_x_(lower_x),
 247       is_active_(true) {}
 248
 249   coordinate_type x() const {
 250     return center_x_;
 251   }
 252
 253   circle_event& x(coordinate_type center_x) {
 254     center_x_ = center_x;
 255     return *this;
 256   }
 257
 258   coordinate_type y() const {
 259     return center_y_;
 260   }
 261
 262   circle_event& y(coordinate_type center_y) {
 263     center_y_ = center_y;
 264     return *this;
 265   }
 266
 267   coordinate_type lower_x() const {
 268     return lower_x_;
 269   }
 270
 271   circle_event& lower_x(coordinate_type lower_x) {
 272     lower_x_ = lower_x;
 273     return *this;
 274   }
 275
 276   coordinate_type lower_y() const {
 277     return center_y_;
 278   }
 279
 280   bool is_active() const {
 281     return is_active_;
 282   }
 283
 284   circle_event& deactivate() {
 285     is_active_ = false;
 286     return *this;
 287   }
 288
 289  private:
 290   coordinate_type center_x_;
 291   coordinate_type center_y_;
 292   coordinate_type lower_x_;
 293   bool is_active_;
 294 };
 295
 296 // Event queue data structure, holds circle events.
 297 // During algorithm run, some of the circle events disappear (become
 298 // inactive). Priority queue data structure doesn't support
 299 // iterators (there is no direct ability to modify its elements).
 300 // Instead list is used to store all the circle events and priority queue
 301 // of the iterators to the list elements is used to keep the correct circle
 302 // events ordering.
 303 template <typename T, typename Predicate>
 304 class ordered_queue {
 305  public:
 306   ordered_queue() {}
 307
 308   bool empty() const {
 309     return c_.empty();
 310   }
 311
 312   const T &top() const {
 313     return *c_.top();
 314   }
 315
 316   void pop() {
 317     list_iterator_type it = c_.top();
 318     c_.pop();
 319     c_list_.erase(it);
 320   }
 321
 322   T &push(const T &e) {
 323     c_list_.push_front(e);
 324     c_.push(c_list_.begin());
 325     return c_list_.front();
 326   }
 327
 328   void clear() {
 329     while (!c_.empty())
 330         c_.pop();
 331     c_list_.clear();
 332   }
 333
 334  private:
 335   typedef typename std::list<T>::iterator list_iterator_type;
 336
 337   struct comparison {
 338     bool operator() (const list_iterator_type &it1,
 339                      const list_iterator_type &it2) const {
 340       return cmp_(*it1, *it2);
 341     }
 342     Predicate cmp_;
 343   };
 344
 345   std::priority_queue< list_iterator_type,
 346                        std::vector<list_iterator_type>,
 347                        comparison > c_;
 348   std::list<T> c_list_;
 349
 350   // Disallow copy constructor and operator=
 351   ordered_queue(const ordered_queue&);
 352   void operator=(const ordered_queue&);
 353 };
 354
 355 // Represents a bisector node made by two arcs that correspond to the left
 356 // and right sites. Arc is defined as a curve with points equidistant from
 357 // the site and from the sweepline. If the site is a point then arc is
 358 // a parabola, otherwise it's a line segment. A segment site event will
 359 // produce different bisectors based on its direction.
 360 // In general case two sites will create two opposite bisectors. That's
 361 // why the order of the sites is important to define the unique bisector.
 362 // The one site is considered to be newer than the other one if it was
 363 // processed by the algorithm later (has greater index).
 364 template <typename Site>
 365 class beach_line_node_key {
 366  public:
 367   typedef Site site_type;
 368
 369   // Constructs degenerate bisector, used to search an arc that is above
 370   // the given site. The input to the constructor is the new site point.
 371   explicit beach_line_node_key(const site_type &new_site) :
 372       left_site_(new_site),
 373       right_site_(new_site) {}
 374
 375   // Constructs a new bisector. The input to the constructor is the two
 376   // sites that create the bisector. The order of sites is important.
 377   beach_line_node_key(const site_type &left_site,
 378                       const site_type &right_site) :
 379       left_site_(left_site),
 380       right_site_(right_site) {}
 381
 382   const site_type &left_site() const {
 383     return left_site_;
 384   }
 385
 386   site_type &left_site() {
 387     return left_site_;
 388   }
 389
 390   beach_line_node_key& left_site(const site_type &site) {
 391     left_site_ = site;
 392     return *this;
 393   }
 394
 395   const site_type &right_site() const {
 396     return right_site_;
 397   }
 398
 399   site_type &right_site() {
 400     return right_site_;
 401   }
 402
 403   beach_line_node_key& right_site(const site_type &site) {
 404     right_site_ = site;
 405     return *this;
 406   }
 407
 408  private:
 409   site_type left_site_;
 410   site_type right_site_;
 411 };
 412
 413 // Represents edge data structure from the Voronoi output, that is
 414 // associated as a value with beach line bisector in the beach
 415 // line. Contains pointer to the circle event in the circle event
 416 // queue if the edge corresponds to the right bisector of the circle event.
 417 template <typename Edge, typename Circle>
 418 class beach_line_node_data {
 419  public:
 420   explicit beach_line_node_data(Edge* new_edge) :
 421       circle_event_(NULL),
 422       edge_(new_edge) {}
 423
 424   Circle* circle_event() const {
 425     return circle_event_;
 426   }
 427
 428   beach_line_node_data& circle_event(Circle* circle_event) {
 429     circle_event_ = circle_event;
 430     return *this;
 431   }
 432
 433   Edge* edge() const {
 434     return edge_;
 435   }
 436
 437   beach_line_node_data& edge(Edge* new_edge) {
 438     edge_ = new_edge;
 439     return *this;
 440   }
 441
 442  private:
 443   Circle* circle_event_;
 444   Edge* edge_;
 445 };
 446 }  // detail
 447 }  // polygon
 448 }  // boost
 449
 450 #endif  // BOOST_POLYGON_DETAIL_VORONOI_STRUCTURES