view release on metacpan or  search on metacpan

src/boost/polygon/detail/voronoi_structures.hpp  view on Meta::CPAN

#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(bool oriented = false) const {
    return x0(oriented);
  }

  coordinate_type y(bool oriented = false) const {
    return y0(oriented);
  }

  coordinate_type x0(bool oriented = false) const {