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