Chris@16: // Boost.Polygon library detail/voronoi_structures.hpp header file
Chris@16: 
Chris@16: //          Copyright Andrii Sydorchuk 2010-2012.
Chris@16: // Distributed under the Boost Software License, Version 1.0.
Chris@16: //    (See accompanying file LICENSE_1_0.txt or copy at
Chris@16: //          http://www.boost.org/LICENSE_1_0.txt)
Chris@16: 
Chris@16: // See http://www.boost.org for updates, documentation, and revision history.
Chris@16: 
Chris@16: #ifndef BOOST_POLYGON_DETAIL_VORONOI_STRUCTURES
Chris@16: #define BOOST_POLYGON_DETAIL_VORONOI_STRUCTURES
Chris@16: 
Chris@16: #include <list>
Chris@16: #include <queue>
Chris@16: #include <vector>
Chris@16: 
Chris@16: #include "boost/polygon/voronoi_geometry_type.hpp"
Chris@16: 
Chris@16: namespace boost {
Chris@16: namespace polygon {
Chris@16: namespace detail {
Chris@16: // Cartesian 2D point data structure.
Chris@16: template <typename T>
Chris@16: class point_2d {
Chris@16:  public:
Chris@16:   typedef T coordinate_type;
Chris@16: 
Chris@16:   point_2d() {}
Chris@16: 
Chris@16:   point_2d(coordinate_type x, coordinate_type y) :
Chris@16:       x_(x),
Chris@16:       y_(y) {}
Chris@16: 
Chris@16:   bool operator==(const point_2d& that) const {
Chris@16:     return (this->x_ == that.x()) && (this->y_ == that.y());
Chris@16:   }
Chris@16: 
Chris@16:   bool operator!=(const point_2d& that) const {
Chris@16:     return (this->x_ != that.x()) || (this->y_ != that.y());
Chris@16:   }
Chris@16: 
Chris@16:   coordinate_type x() const {
Chris@16:     return x_;
Chris@16:   }
Chris@16: 
Chris@16:   coordinate_type y() const {
Chris@16:     return y_;
Chris@16:   }
Chris@16: 
Chris@16:   point_2d& x(coordinate_type x) {
Chris@16:     x_ = x;
Chris@16:     return *this;
Chris@16:   }
Chris@16: 
Chris@16:   point_2d& y(coordinate_type y) {
Chris@16:     y_ = y;
Chris@16:     return *this;
Chris@16:   }
Chris@16: 
Chris@16:  private:
Chris@16:   coordinate_type x_;
Chris@16:   coordinate_type y_;
Chris@16: };
Chris@16: 
Chris@16: // Site event type.
Chris@16: // Occurs when the sweepline sweeps over one of the initial sites:
Chris@16: //   1) point site
Chris@16: //   2) start-point of the segment site
Chris@16: //   3) endpoint of the segment site
Chris@16: // Implicit segment direction is defined: the start-point of
Chris@16: // the segment compares less than its endpoint.
Chris@16: // Each input segment is divided onto two site events:
Chris@16: //   1) One going from the start-point to the endpoint
Chris@16: //      (is_inverse() = false)
Chris@16: //   2) Another going from the endpoint to the start-point
Chris@16: //      (is_inverse() = true)
Chris@16: // In beach line data structure segment sites of the first
Chris@16: // type precede sites of the second type for the same segment.
Chris@16: // Members:
Chris@16: //   point0_ - point site or segment's start-point
Chris@16: //   point1_ - segment's endpoint if site is a segment
Chris@16: //   sorted_index_ - the last bit encodes information if the site is inverse;
Chris@16: //     the other bits encode site event index among the sorted site events
Chris@16: //   initial_index_ - site index among the initial input set
Chris@16: // Note: for all sites is_inverse_ flag is equal to false by default.
Chris@16: template <typename T>
Chris@16: class site_event {
Chris@16:  public:
Chris@16:   typedef T coordinate_type;
Chris@16:   typedef point_2d<T> point_type;
Chris@16: 
Chris@16:   site_event() :
Chris@16:       point0_(0, 0),
Chris@16:       point1_(0, 0),
Chris@16:       sorted_index_(0),
Chris@16:       flags_(0) {}
Chris@16: 
Chris@16:   site_event(coordinate_type x, coordinate_type y) :
Chris@16:       point0_(x, y),
Chris@16:       point1_(x, y),
Chris@16:       sorted_index_(0),
Chris@16:       flags_(0) {}
Chris@16: 
Chris@16:   explicit site_event(const point_type& point) :
Chris@16:       point0_(point),
Chris@16:       point1_(point),
Chris@16:       sorted_index_(0),
Chris@16:       flags_(0) {}
Chris@16: 
Chris@16:   site_event(coordinate_type x1, coordinate_type y1,
Chris@16:              coordinate_type x2, coordinate_type y2):
Chris@16:       point0_(x1, y1),
Chris@16:       point1_(x2, y2),
Chris@16:       sorted_index_(0),
Chris@16:       flags_(0) {}
Chris@16: 
Chris@16:   site_event(const point_type& point1, const point_type& point2) :
Chris@16:       point0_(point1),
Chris@16:       point1_(point2),
Chris@16:       sorted_index_(0),
Chris@16:       flags_(0) {}
Chris@16: 
Chris@16:   bool operator==(const site_event& that) const {
Chris@16:     return (this->point0_ == that.point0_) &&
Chris@16:            (this->point1_ == that.point1_);
Chris@16:   }
Chris@16: 
Chris@16:   bool operator!=(const site_event& that) const {
Chris@16:     return (this->point0_ != that.point0_) ||
Chris@16:            (this->point1_ != that.point1_);
Chris@16:   }
Chris@16: 
Chris@16:   coordinate_type x() const {
Chris@16:     return point0_.x();
Chris@16:   }
Chris@16: 
Chris@16:   coordinate_type y() const {
Chris@16:     return point0_.y();
Chris@16:   }
Chris@16: 
Chris@16:   coordinate_type x0() const {
Chris@16:     return point0_.x();
Chris@16:   }
Chris@16: 
Chris@16:   coordinate_type y0() const {
Chris@16:     return point0_.y();
Chris@16:   }
Chris@16: 
Chris@16:   coordinate_type x1() const {
Chris@16:     return point1_.x();
Chris@16:   }
Chris@16: 
Chris@16:   coordinate_type y1() const {
Chris@16:     return point1_.y();
Chris@16:   }
Chris@16: 
Chris@16:   const point_type& point0() const {
Chris@16:     return point0_;
Chris@16:   }
Chris@16: 
Chris@16:   const point_type& point1() const {
Chris@16:     return point1_;
Chris@16:   }
Chris@16: 
Chris@16:   std::size_t sorted_index() const {
Chris@16:     return sorted_index_;
Chris@16:   }
Chris@16: 
Chris@16:   site_event& sorted_index(std::size_t index) {
Chris@16:     sorted_index_ = index;
Chris@16:     return *this;
Chris@16:   }
Chris@16: 
Chris@16:   std::size_t initial_index() const {
Chris@16:     return initial_index_;
Chris@16:   }
Chris@16: 
Chris@16:   site_event& initial_index(std::size_t index) {
Chris@16:     initial_index_ = index;
Chris@16:     return *this;
Chris@16:   }
Chris@16: 
Chris@16:   bool is_inverse() const {
Chris@16:     return (flags_ & IS_INVERSE) ? true : false;
Chris@16:   }
Chris@16: 
Chris@16:   site_event& inverse() {
Chris@16:     std::swap(point0_, point1_);
Chris@16:     flags_ ^= IS_INVERSE;
Chris@16:     return *this;
Chris@16:   }
Chris@16: 
Chris@16:   SourceCategory source_category() const {
Chris@16:     return static_cast<SourceCategory>(flags_ & SOURCE_CATEGORY_BITMASK);
Chris@16:   }
Chris@16: 
Chris@16:   site_event& source_category(SourceCategory source_category) {
Chris@16:     flags_ |= source_category;
Chris@16:     return *this;
Chris@16:   }
Chris@16: 
Chris@16:   bool is_point() const {
Chris@16:     return (point0_.x() == point1_.x()) && (point0_.y() == point1_.y());
Chris@16:   }
Chris@16: 
Chris@16:   bool is_segment() const {
Chris@16:     return (point0_.x() != point1_.x()) || (point0_.y() != point1_.y());
Chris@16:   }
Chris@16: 
Chris@16:  private:
Chris@16:   enum Bits {
Chris@16:     IS_INVERSE = 0x20  // 32
Chris@16:   };
Chris@16: 
Chris@16:   point_type point0_;
Chris@16:   point_type point1_;
Chris@16:   std::size_t sorted_index_;
Chris@16:   std::size_t initial_index_;
Chris@16:   std::size_t flags_;
Chris@16: };
Chris@16: 
Chris@16: // Circle event type.
Chris@16: // Occurs when the sweepline sweeps over the rightmost point of the Voronoi
Chris@16: // circle (with the center at the intersection point of the bisectors).
Chris@16: // Circle event is made of the two consecutive nodes in the beach line data
Chris@16: // structure. In case another node was inserted during algorithm execution
Chris@16: // between the given two nodes circle event becomes inactive.
Chris@16: // Variables:
Chris@16: //   center_x_ - center x-coordinate;
Chris@16: //   center_y_ - center y-coordinate;
Chris@16: //   lower_x_ - leftmost x-coordinate;
Chris@16: //   is_active_ - states whether circle event is still active.
Chris@16: // NOTE: lower_y coordinate is always equal to center_y.
Chris@16: template <typename T>
Chris@16: class circle_event {
Chris@16:  public:
Chris@16:   typedef T coordinate_type;
Chris@16: 
Chris@16:   circle_event() : is_active_(true) {}
Chris@16: 
Chris@16:   circle_event(coordinate_type c_x,
Chris@16:                coordinate_type c_y,
Chris@16:                coordinate_type lower_x) :
Chris@16:       center_x_(c_x),
Chris@16:       center_y_(c_y),
Chris@16:       lower_x_(lower_x),
Chris@16:       is_active_(true) {}
Chris@16: 
Chris@16:   coordinate_type x() const {
Chris@16:     return center_x_;
Chris@16:   }
Chris@16: 
Chris@16:   circle_event& x(coordinate_type center_x) {
Chris@16:     center_x_ = center_x;
Chris@16:     return *this;
Chris@16:   }
Chris@16: 
Chris@16:   coordinate_type y() const {
Chris@16:     return center_y_;
Chris@16:   }
Chris@16: 
Chris@16:   circle_event& y(coordinate_type center_y) {
Chris@16:     center_y_ = center_y;
Chris@16:     return *this;
Chris@16:   }
Chris@16: 
Chris@16:   coordinate_type lower_x() const {
Chris@16:     return lower_x_;
Chris@16:   }
Chris@16: 
Chris@16:   circle_event& lower_x(coordinate_type lower_x) {
Chris@16:     lower_x_ = lower_x;
Chris@16:     return *this;
Chris@16:   }
Chris@16: 
Chris@16:   coordinate_type lower_y() const {
Chris@16:     return center_y_;
Chris@16:   }
Chris@16: 
Chris@16:   bool is_active() const {
Chris@16:     return is_active_;
Chris@16:   }
Chris@16: 
Chris@16:   circle_event& deactivate() {
Chris@16:     is_active_ = false;
Chris@16:     return *this;
Chris@16:   }
Chris@16: 
Chris@16:  private:
Chris@16:   coordinate_type center_x_;
Chris@16:   coordinate_type center_y_;
Chris@16:   coordinate_type lower_x_;
Chris@16:   bool is_active_;
Chris@16: };
Chris@16: 
Chris@16: // Event queue data structure, holds circle events.
Chris@16: // During algorithm run, some of the circle events disappear (become
Chris@16: // inactive). Priority queue data structure doesn't support
Chris@16: // iterators (there is no direct ability to modify its elements).
Chris@16: // Instead list is used to store all the circle events and priority queue
Chris@16: // of the iterators to the list elements is used to keep the correct circle
Chris@16: // events ordering.
Chris@16: template <typename T, typename Predicate>
Chris@16: class ordered_queue {
Chris@16:  public:
Chris@16:   ordered_queue() {}
Chris@16: 
Chris@16:   bool empty() const {
Chris@16:     return c_.empty();
Chris@16:   }
Chris@16: 
Chris@16:   const T &top() const {
Chris@16:     return *c_.top();
Chris@16:   }
Chris@16: 
Chris@16:   void pop() {
Chris@16:     list_iterator_type it = c_.top();
Chris@16:     c_.pop();
Chris@16:     c_list_.erase(it);
Chris@16:   }
Chris@16: 
Chris@16:   T &push(const T &e) {
Chris@16:     c_list_.push_front(e);
Chris@16:     c_.push(c_list_.begin());
Chris@16:     return c_list_.front();
Chris@16:   }
Chris@16: 
Chris@16:   void clear() {
Chris@16:     while (!c_.empty())
Chris@16:         c_.pop();
Chris@16:     c_list_.clear();
Chris@16:   }
Chris@16: 
Chris@16:  private:
Chris@16:   typedef typename std::list<T>::iterator list_iterator_type;
Chris@16: 
Chris@16:   struct comparison {
Chris@16:     bool operator() (const list_iterator_type &it1,
Chris@16:                      const list_iterator_type &it2) const {
Chris@16:       return cmp_(*it1, *it2);
Chris@16:     }
Chris@16:     Predicate cmp_;
Chris@16:   };
Chris@16: 
Chris@16:   std::priority_queue< list_iterator_type,
Chris@16:                        std::vector<list_iterator_type>,
Chris@16:                        comparison > c_;
Chris@16:   std::list<T> c_list_;
Chris@16: 
Chris@16:   // Disallow copy constructor and operator=
Chris@16:   ordered_queue(const ordered_queue&);
Chris@16:   void operator=(const ordered_queue&);
Chris@16: };
Chris@16: 
Chris@16: // Represents a bisector node made by two arcs that correspond to the left
Chris@16: // and right sites. Arc is defined as a curve with points equidistant from
Chris@16: // the site and from the sweepline. If the site is a point then arc is
Chris@16: // a parabola, otherwise it's a line segment. A segment site event will
Chris@16: // produce different bisectors based on its direction.
Chris@16: // In general case two sites will create two opposite bisectors. That's
Chris@16: // why the order of the sites is important to define the unique bisector.
Chris@16: // The one site is considered to be newer than the other one if it was
Chris@16: // processed by the algorithm later (has greater index).
Chris@16: template <typename Site>
Chris@16: class beach_line_node_key {
Chris@16:  public:
Chris@16:   typedef Site site_type;
Chris@16: 
Chris@16:   // Constructs degenerate bisector, used to search an arc that is above
Chris@16:   // the given site. The input to the constructor is the new site point.
Chris@16:   explicit beach_line_node_key(const site_type &new_site) :
Chris@16:       left_site_(new_site),
Chris@16:       right_site_(new_site) {}
Chris@16: 
Chris@16:   // Constructs a new bisector. The input to the constructor is the two
Chris@16:   // sites that create the bisector. The order of sites is important.
Chris@16:   beach_line_node_key(const site_type &left_site,
Chris@16:                       const site_type &right_site) :
Chris@16:       left_site_(left_site),
Chris@16:       right_site_(right_site) {}
Chris@16: 
Chris@16:   const site_type &left_site() const {
Chris@16:     return left_site_;
Chris@16:   }
Chris@16: 
Chris@16:   site_type &left_site() {
Chris@16:     return left_site_;
Chris@16:   }
Chris@16: 
Chris@16:   beach_line_node_key& left_site(const site_type &site) {
Chris@16:     left_site_ = site;
Chris@16:     return *this;
Chris@16:   }
Chris@16: 
Chris@16:   const site_type &right_site() const {
Chris@16:     return right_site_;
Chris@16:   }
Chris@16: 
Chris@16:   site_type &right_site() {
Chris@16:     return right_site_;
Chris@16:   }
Chris@16: 
Chris@16:   beach_line_node_key& right_site(const site_type &site) {
Chris@16:     right_site_ = site;
Chris@16:     return *this;
Chris@16:   }
Chris@16: 
Chris@16:  private:
Chris@16:   site_type left_site_;
Chris@16:   site_type right_site_;
Chris@16: };
Chris@16: 
Chris@16: // Represents edge data structure from the Voronoi output, that is
Chris@16: // associated as a value with beach line bisector in the beach
Chris@16: // line. Contains pointer to the circle event in the circle event
Chris@16: // queue if the edge corresponds to the right bisector of the circle event.
Chris@16: template <typename Edge, typename Circle>
Chris@16: class beach_line_node_data {
Chris@16:  public:
Chris@16:   explicit beach_line_node_data(Edge* new_edge) :
Chris@16:       circle_event_(NULL),
Chris@16:       edge_(new_edge) {}
Chris@16: 
Chris@16:   Circle* circle_event() const {
Chris@16:     return circle_event_;
Chris@16:   }
Chris@16: 
Chris@16:   beach_line_node_data& circle_event(Circle* circle_event) {
Chris@16:     circle_event_ = circle_event;
Chris@16:     return *this;
Chris@16:   }
Chris@16: 
Chris@16:   Edge* edge() const {
Chris@16:     return edge_;
Chris@16:   }
Chris@16: 
Chris@16:   beach_line_node_data& edge(Edge* new_edge) {
Chris@16:     edge_ = new_edge;
Chris@16:     return *this;
Chris@16:   }
Chris@16: 
Chris@16:  private:
Chris@16:   Circle* circle_event_;
Chris@16:   Edge* edge_;
Chris@16: };
Chris@16: }  // detail
Chris@16: }  // polygon
Chris@16: }  // boost
Chris@16: 
Chris@16: #endif  // BOOST_POLYGON_DETAIL_VORONOI_STRUCTURES