+++ /dev/null
-// 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
projects / ceph.git / blobdiff