Chris@16: // Boost.Polygon library voronoi_diagram.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_VORONOI_DIAGRAM
Chris@16: #define BOOST_POLYGON_VORONOI_DIAGRAM
Chris@16: 
Chris@16: #include <vector>
Chris@16: #include <utility>
Chris@16: 
Chris@16: #include "detail/voronoi_ctypes.hpp"
Chris@16: #include "detail/voronoi_structures.hpp"
Chris@16: 
Chris@16: #include "voronoi_geometry_type.hpp"
Chris@16: 
Chris@16: namespace boost {
Chris@16: namespace polygon {
Chris@16: 
Chris@16: // Forward declarations.
Chris@16: template <typename T>
Chris@16: class voronoi_edge;
Chris@16: 
Chris@16: // Represents Voronoi cell.
Chris@16: // Data members:
Chris@16: //   1) index of the source within the initial input set
Chris@16: //   2) pointer to the incident edge
Chris@16: //   3) mutable color member
Chris@16: // Cell may contain point or segment site inside.
Chris@16: template <typename T>
Chris@16: class voronoi_cell {
Chris@16:  public:
Chris@16:   typedef T coordinate_type;
Chris@16:   typedef std::size_t color_type;
Chris@16:   typedef voronoi_edge<coordinate_type> voronoi_edge_type;
Chris@16:   typedef std::size_t source_index_type;
Chris@16:   typedef SourceCategory source_category_type;
Chris@16: 
Chris@16:   voronoi_cell(source_index_type source_index,
Chris@16:                source_category_type source_category) :
Chris@16:       source_index_(source_index),
Chris@16:       incident_edge_(NULL),
Chris@16:       color_(source_category) {}
Chris@16: 
Chris@16:   // Returns true if the cell contains point site, false else.
Chris@16:   bool contains_point() const {
Chris@16:     source_category_type source_category = this->source_category();
Chris@16:     return belongs(source_category, GEOMETRY_CATEGORY_POINT);
Chris@16:   }
Chris@16: 
Chris@16:   // Returns true if the cell contains segment site, false else.
Chris@16:   bool contains_segment() const {
Chris@16:     source_category_type source_category = this->source_category();
Chris@16:     return belongs(source_category, GEOMETRY_CATEGORY_SEGMENT);
Chris@16:   }
Chris@16: 
Chris@16:   source_index_type source_index() const {
Chris@16:     return source_index_;
Chris@16:   }
Chris@16: 
Chris@16:   source_category_type source_category() const {
Chris@16:     return static_cast<source_category_type>(color_ & SOURCE_CATEGORY_BITMASK);
Chris@16:   }
Chris@16: 
Chris@16:   // Degenerate cells don't have any incident edges.
Chris@16:   bool is_degenerate() const { return incident_edge_ == NULL; }
Chris@16: 
Chris@16:   voronoi_edge_type* incident_edge() { return incident_edge_; }
Chris@16:   const voronoi_edge_type* incident_edge() const { return incident_edge_; }
Chris@16:   void incident_edge(voronoi_edge_type* e) { incident_edge_ = e; }
Chris@16: 
Chris@16:   color_type color() const { return color_ >> BITS_SHIFT; }
Chris@16:   void color(color_type color) const {
Chris@16:     color_ &= BITS_MASK;
Chris@16:     color_ |= color << BITS_SHIFT;
Chris@16:   }
Chris@16: 
Chris@16:  private:
Chris@16:   // 5 color bits are reserved.
Chris@16:   enum Bits {
Chris@16:     BITS_SHIFT = 0x5,
Chris@16:     BITS_MASK = 0x1F
Chris@16:   };
Chris@16: 
Chris@16:   source_index_type source_index_;
Chris@16:   voronoi_edge_type* incident_edge_;
Chris@16:   mutable color_type color_;
Chris@16: };
Chris@16: 
Chris@16: // Represents Voronoi vertex.
Chris@16: // Data members:
Chris@16: //   1) vertex coordinates
Chris@16: //   2) pointer to the incident edge
Chris@16: //   3) mutable color member
Chris@16: template <typename T>
Chris@16: class voronoi_vertex {
Chris@16:  public:
Chris@16:   typedef T coordinate_type;
Chris@16:   typedef std::size_t color_type;
Chris@16:   typedef voronoi_edge<coordinate_type> voronoi_edge_type;
Chris@16: 
Chris@16:   voronoi_vertex(const coordinate_type& x, const coordinate_type& y) :
Chris@16:       x_(x),
Chris@16:       y_(y),
Chris@16:       incident_edge_(NULL),
Chris@16:       color_(0) {}
Chris@16: 
Chris@16:   const coordinate_type& x() const { return x_; }
Chris@16:   const coordinate_type& y() const { return y_; }
Chris@16: 
Chris@16:   bool is_degenerate() const { return incident_edge_ == NULL; }
Chris@16: 
Chris@16:   voronoi_edge_type* incident_edge() { return incident_edge_; }
Chris@16:   const voronoi_edge_type* incident_edge() const { return incident_edge_; }
Chris@16:   void incident_edge(voronoi_edge_type* e) { incident_edge_ = e; }
Chris@16: 
Chris@16:   color_type color() const { return color_ >> BITS_SHIFT; }
Chris@16:   void color(color_type color) const {
Chris@16:     color_ &= BITS_MASK;
Chris@16:     color_ |= color << BITS_SHIFT;
Chris@16:   }
Chris@16: 
Chris@16:  private:
Chris@16:   // 5 color bits are reserved.
Chris@16:   enum Bits {
Chris@16:     BITS_SHIFT = 0x5,
Chris@16:     BITS_MASK = 0x1F
Chris@16:   };
Chris@16: 
Chris@16:   coordinate_type x_;
Chris@16:   coordinate_type y_;
Chris@16:   voronoi_edge_type* incident_edge_;
Chris@16:   mutable color_type color_;
Chris@16: };
Chris@16: 
Chris@16: // Half-edge data structure. Represents Voronoi edge.
Chris@16: // Data members:
Chris@16: //   1) pointer to the corresponding cell
Chris@16: //   2) pointer to the vertex that is the starting
Chris@16: //      point of the half-edge
Chris@16: //   3) pointer to the twin edge
Chris@16: //   4) pointer to the CCW next edge
Chris@16: //   5) pointer to the CCW prev edge
Chris@16: //   6) mutable color member
Chris@16: template <typename T>
Chris@16: class voronoi_edge {
Chris@16:  public:
Chris@16:   typedef T coordinate_type;
Chris@16:   typedef voronoi_cell<coordinate_type> voronoi_cell_type;
Chris@16:   typedef voronoi_vertex<coordinate_type> voronoi_vertex_type;
Chris@16:   typedef voronoi_edge<coordinate_type> voronoi_edge_type;
Chris@16:   typedef std::size_t color_type;
Chris@16: 
Chris@16:   voronoi_edge(bool is_linear, bool is_primary) :
Chris@16:       cell_(NULL),
Chris@16:       vertex_(NULL),
Chris@16:       twin_(NULL),
Chris@16:       next_(NULL),
Chris@16:       prev_(NULL),
Chris@16:       color_(0) {
Chris@16:     if (is_linear)
Chris@16:       color_ |= BIT_IS_LINEAR;
Chris@16:     if (is_primary)
Chris@16:       color_ |= BIT_IS_PRIMARY;
Chris@16:   }
Chris@16: 
Chris@16:   voronoi_cell_type* cell() { return cell_; }
Chris@16:   const voronoi_cell_type* cell() const { return cell_; }
Chris@16:   void cell(voronoi_cell_type* c) { cell_ = c; }
Chris@16: 
Chris@16:   voronoi_vertex_type* vertex0() { return vertex_; }
Chris@16:   const voronoi_vertex_type* vertex0() const { return vertex_; }
Chris@16:   void vertex0(voronoi_vertex_type* v) { vertex_ = v; }
Chris@16: 
Chris@16:   voronoi_vertex_type* vertex1() { return twin_->vertex0(); }
Chris@16:   const voronoi_vertex_type* vertex1() const { return twin_->vertex0(); }
Chris@16: 
Chris@16:   voronoi_edge_type* twin() { return twin_; }
Chris@16:   const voronoi_edge_type* twin() const { return twin_; }
Chris@16:   void twin(voronoi_edge_type* e) { twin_ = e; }
Chris@16: 
Chris@16:   voronoi_edge_type* next() { return next_; }
Chris@16:   const voronoi_edge_type* next() const { return next_; }
Chris@16:   void next(voronoi_edge_type* e) { next_ = e; }
Chris@16: 
Chris@16:   voronoi_edge_type* prev() { return prev_; }
Chris@16:   const voronoi_edge_type* prev() const { return prev_; }
Chris@16:   void prev(voronoi_edge_type* e) { prev_ = e; }
Chris@16: 
Chris@16:   // Returns a pointer to the rotation next edge
Chris@16:   // over the starting point of the half-edge.
Chris@16:   voronoi_edge_type* rot_next() { return prev_->twin(); }
Chris@16:   const voronoi_edge_type* rot_next() const { return prev_->twin(); }
Chris@16: 
Chris@16:   // Returns a pointer to the rotation prev edge
Chris@16:   // over the starting point of the half-edge.
Chris@16:   voronoi_edge_type* rot_prev() { return twin_->next(); }
Chris@16:   const voronoi_edge_type* rot_prev() const { return twin_->next(); }
Chris@16: 
Chris@16:   // Returns true if the edge is finite (segment, parabolic arc).
Chris@16:   // Returns false if the edge is infinite (ray, line).
Chris@16:   bool is_finite() const { return vertex0() && vertex1(); }
Chris@16: 
Chris@16:   // Returns true if the edge is infinite (ray, line).
Chris@16:   // Returns false if the edge is finite (segment, parabolic arc).
Chris@16:   bool is_infinite() const { return !vertex0() || !vertex1(); }
Chris@16: 
Chris@16:   // Returns true if the edge is linear (segment, ray, line).
Chris@16:   // Returns false if the edge is curved (parabolic arc).
Chris@16:   bool is_linear() const {
Chris@16:     return (color_ & BIT_IS_LINEAR) ? true : false;
Chris@16:   }
Chris@16: 
Chris@16:   // Returns true if the edge is curved (parabolic arc).
Chris@16:   // Returns false if the edge is linear (segment, ray, line).
Chris@16:   bool is_curved() const {
Chris@16:     return (color_ & BIT_IS_LINEAR) ? false : true;
Chris@16:   }
Chris@16: 
Chris@16:   // Returns false if edge goes through the endpoint of the segment.
Chris@16:   // Returns true else.
Chris@16:   bool is_primary() const {
Chris@16:     return (color_ & BIT_IS_PRIMARY) ? true : false;
Chris@16:   }
Chris@16: 
Chris@16:   // Returns true if edge goes through the endpoint of the segment.
Chris@16:   // Returns false else.
Chris@16:   bool is_secondary() const {
Chris@16:     return (color_ & BIT_IS_PRIMARY) ? false : true;
Chris@16:   }
Chris@16: 
Chris@16:   color_type color() const { return color_ >> BITS_SHIFT; }
Chris@16:   void color(color_type color) const {
Chris@16:     color_ &= BITS_MASK;
Chris@16:     color_ |= color << BITS_SHIFT;
Chris@16:   }
Chris@16: 
Chris@16:  private:
Chris@16:   // 5 color bits are reserved.
Chris@16:   enum Bits {
Chris@16:     BIT_IS_LINEAR = 0x1,  // linear is opposite to curved
Chris@16:     BIT_IS_PRIMARY = 0x2,  // primary is opposite to secondary
Chris@16: 
Chris@16:     BITS_SHIFT = 0x5,
Chris@16:     BITS_MASK = 0x1F
Chris@16:   };
Chris@16: 
Chris@16:   voronoi_cell_type* cell_;
Chris@16:   voronoi_vertex_type* vertex_;
Chris@16:   voronoi_edge_type* twin_;
Chris@16:   voronoi_edge_type* next_;
Chris@16:   voronoi_edge_type* prev_;
Chris@16:   mutable color_type color_;
Chris@16: };
Chris@16: 
Chris@16: template <typename T>
Chris@16: struct voronoi_diagram_traits {
Chris@16:   typedef T coordinate_type;
Chris@16:   typedef voronoi_cell<coordinate_type> cell_type;
Chris@16:   typedef voronoi_vertex<coordinate_type> vertex_type;
Chris@16:   typedef voronoi_edge<coordinate_type> edge_type;
Chris@16:   typedef class {
Chris@16:    public:
Chris@16:     enum { ULPS = 128 };
Chris@16:     bool operator()(const vertex_type& v1, const vertex_type& v2) const {
Chris@16:       return (ulp_cmp(v1.x(), v2.x(), ULPS) ==
Chris@16:               detail::ulp_comparison<T>::EQUAL) &&
Chris@16:              (ulp_cmp(v1.y(), v2.y(), ULPS) ==
Chris@16:               detail::ulp_comparison<T>::EQUAL);
Chris@16:     }
Chris@16:    private:
Chris@16:     typename detail::ulp_comparison<T> ulp_cmp;
Chris@16:   } vertex_equality_predicate_type;
Chris@16: };
Chris@16: 
Chris@16: // Voronoi output data structure.
Chris@16: // CCW ordering is used on the faces perimeter and around the vertices.
Chris@16: template <typename T, typename TRAITS = voronoi_diagram_traits<T> >
Chris@16: class voronoi_diagram {
Chris@16:  public:
Chris@16:   typedef typename TRAITS::coordinate_type coordinate_type;
Chris@16:   typedef typename TRAITS::cell_type cell_type;
Chris@16:   typedef typename TRAITS::vertex_type vertex_type;
Chris@16:   typedef typename TRAITS::edge_type edge_type;
Chris@16: 
Chris@16:   typedef std::vector<cell_type> cell_container_type;
Chris@16:   typedef typename cell_container_type::const_iterator const_cell_iterator;
Chris@16: 
Chris@16:   typedef std::vector<vertex_type> vertex_container_type;
Chris@16:   typedef typename vertex_container_type::const_iterator const_vertex_iterator;
Chris@16: 
Chris@16:   typedef std::vector<edge_type> edge_container_type;
Chris@16:   typedef typename edge_container_type::const_iterator const_edge_iterator;
Chris@16: 
Chris@16:   voronoi_diagram() {}
Chris@16: 
Chris@16:   void clear() {
Chris@16:     cells_.clear();
Chris@16:     vertices_.clear();
Chris@16:     edges_.clear();
Chris@16:   }
Chris@16: 
Chris@16:   const cell_container_type& cells() const {
Chris@16:     return cells_;
Chris@16:   }
Chris@16: 
Chris@16:   const vertex_container_type& vertices() const {
Chris@16:     return vertices_;
Chris@16:   }
Chris@16: 
Chris@16:   const edge_container_type& edges() const {
Chris@16:     return edges_;
Chris@16:   }
Chris@16: 
Chris@16:   std::size_t num_cells() const {
Chris@16:     return cells_.size();
Chris@16:   }
Chris@16: 
Chris@16:   std::size_t num_edges() const {
Chris@16:     return edges_.size();
Chris@16:   }
Chris@16: 
Chris@16:   std::size_t num_vertices() const {
Chris@16:     return vertices_.size();
Chris@16:   }
Chris@16: 
Chris@16:   void _reserve(std::size_t num_sites) {
Chris@16:     cells_.reserve(num_sites);
Chris@16:     vertices_.reserve(num_sites << 1);
Chris@16:     edges_.reserve((num_sites << 2) + (num_sites << 1));
Chris@16:   }
Chris@16: 
Chris@16:   template <typename CT>
Chris@16:   void _process_single_site(const detail::site_event<CT>& site) {
Chris@16:     cells_.push_back(cell_type(site.initial_index(), site.source_category()));
Chris@16:   }
Chris@16: 
Chris@16:   // Insert a new half-edge into the output data structure.
Chris@16:   // Takes as input left and right sites that form a new bisector.
Chris@16:   // Returns a pair of pointers to a new half-edges.
Chris@16:   template <typename CT>
Chris@16:   std::pair<void*, void*> _insert_new_edge(
Chris@16:       const detail::site_event<CT>& site1,
Chris@16:       const detail::site_event<CT>& site2) {
Chris@16:     // Get sites' indexes.
Chris@16:     int site_index1 = site1.sorted_index();
Chris@16:     int site_index2 = site2.sorted_index();
Chris@16: 
Chris@16:     bool is_linear = is_linear_edge(site1, site2);
Chris@16:     bool is_primary = is_primary_edge(site1, site2);
Chris@16: 
Chris@16:     // Create a new half-edge that belongs to the first site.
Chris@16:     edges_.push_back(edge_type(is_linear, is_primary));
Chris@16:     edge_type& edge1 = edges_.back();
Chris@16: 
Chris@16:     // Create a new half-edge that belongs to the second site.
Chris@16:     edges_.push_back(edge_type(is_linear, is_primary));
Chris@16:     edge_type& edge2 = edges_.back();
Chris@16: 
Chris@16:     // Add the initial cell during the first edge insertion.
Chris@16:     if (cells_.empty()) {
Chris@16:       cells_.push_back(cell_type(
Chris@16:           site1.initial_index(), site1.source_category()));
Chris@16:     }
Chris@16: 
Chris@16:     // The second site represents a new site during site event
Chris@16:     // processing. Add a new cell to the cell records.
Chris@16:     cells_.push_back(cell_type(
Chris@16:         site2.initial_index(), site2.source_category()));
Chris@16: 
Chris@16:     // Set up pointers to cells.
Chris@16:     edge1.cell(&cells_[site_index1]);
Chris@16:     edge2.cell(&cells_[site_index2]);
Chris@16: 
Chris@16:     // Set up twin pointers.
Chris@16:     edge1.twin(&edge2);
Chris@16:     edge2.twin(&edge1);
Chris@16: 
Chris@16:     // Return a pointer to the new half-edge.
Chris@16:     return std::make_pair(&edge1, &edge2);
Chris@16:   }
Chris@16: 
Chris@16:   // Insert a new half-edge into the output data structure with the
Chris@16:   // start at the point where two previously added half-edges intersect.
Chris@16:   // Takes as input two sites that create a new bisector, circle event
Chris@16:   // that corresponds to the intersection point of the two old half-edges,
Chris@16:   // pointers to those half-edges. Half-edges' direction goes out of the
Chris@16:   // new Voronoi vertex point. Returns a pair of pointers to a new half-edges.
Chris@16:   template <typename CT1, typename CT2>
Chris@16:   std::pair<void*, void*> _insert_new_edge(
Chris@16:       const detail::site_event<CT1>& site1,
Chris@16:       const detail::site_event<CT1>& site3,
Chris@16:       const detail::circle_event<CT2>& circle,
Chris@16:       void* data12, void* data23) {
Chris@16:     edge_type* edge12 = static_cast<edge_type*>(data12);
Chris@16:     edge_type* edge23 = static_cast<edge_type*>(data23);
Chris@16: 
Chris@16:     // Add a new Voronoi vertex.
Chris@16:     vertices_.push_back(vertex_type(circle.x(), circle.y()));
Chris@16:     vertex_type& new_vertex = vertices_.back();
Chris@16: 
Chris@16:     // Update vertex pointers of the old edges.
Chris@16:     edge12->vertex0(&new_vertex);
Chris@16:     edge23->vertex0(&new_vertex);
Chris@16: 
Chris@16:     bool is_linear = is_linear_edge(site1, site3);
Chris@16:     bool is_primary = is_primary_edge(site1, site3);
Chris@16: 
Chris@16:     // Add a new half-edge.
Chris@16:     edges_.push_back(edge_type(is_linear, is_primary));
Chris@16:     edge_type& new_edge1 = edges_.back();
Chris@16:     new_edge1.cell(&cells_[site1.sorted_index()]);
Chris@16: 
Chris@16:     // Add a new half-edge.
Chris@16:     edges_.push_back(edge_type(is_linear, is_primary));
Chris@16:     edge_type& new_edge2 = edges_.back();
Chris@16:     new_edge2.cell(&cells_[site3.sorted_index()]);
Chris@16: 
Chris@16:     // Update twin pointers.
Chris@16:     new_edge1.twin(&new_edge2);
Chris@16:     new_edge2.twin(&new_edge1);
Chris@16: 
Chris@16:     // Update vertex pointer.
Chris@16:     new_edge2.vertex0(&new_vertex);
Chris@16: 
Chris@16:     // Update Voronoi prev/next pointers.
Chris@16:     edge12->prev(&new_edge1);
Chris@16:     new_edge1.next(edge12);
Chris@16:     edge12->twin()->next(edge23);
Chris@16:     edge23->prev(edge12->twin());
Chris@16:     edge23->twin()->next(&new_edge2);
Chris@16:     new_edge2.prev(edge23->twin());
Chris@16: 
Chris@16:     // Return a pointer to the new half-edge.
Chris@16:     return std::make_pair(&new_edge1, &new_edge2);
Chris@16:   }
Chris@16: 
Chris@16:   void _build() {
Chris@16:     // Remove degenerate edges.
Chris@16:     edge_iterator last_edge = edges_.begin();
Chris@16:     for (edge_iterator it = edges_.begin(); it != edges_.end(); it += 2) {
Chris@16:       const vertex_type* v1 = it->vertex0();
Chris@16:       const vertex_type* v2 = it->vertex1();
Chris@16:       if (v1 && v2 && vertex_equality_predicate_(*v1, *v2)) {
Chris@16:         remove_edge(&(*it));
Chris@16:       } else {
Chris@16:         if (it != last_edge) {
Chris@16:           edge_type* e1 = &(*last_edge = *it);
Chris@16:           edge_type* e2 = &(*(last_edge + 1) = *(it + 1));
Chris@16:           e1->twin(e2);
Chris@16:           e2->twin(e1);
Chris@16:           if (e1->prev()) {
Chris@16:             e1->prev()->next(e1);
Chris@16:             e2->next()->prev(e2);
Chris@16:           }
Chris@16:           if (e2->prev()) {
Chris@16:             e1->next()->prev(e1);
Chris@16:             e2->prev()->next(e2);
Chris@16:           }
Chris@16:         }
Chris@16:         last_edge += 2;
Chris@16:       }
Chris@16:     }
Chris@16:     edges_.erase(last_edge, edges_.end());
Chris@16: 
Chris@16:     // Set up incident edge pointers for cells and vertices.
Chris@16:     for (edge_iterator it = edges_.begin(); it != edges_.end(); ++it) {
Chris@16:       it->cell()->incident_edge(&(*it));
Chris@16:       if (it->vertex0()) {
Chris@16:         it->vertex0()->incident_edge(&(*it));
Chris@16:       }
Chris@16:     }
Chris@16: 
Chris@16:     // Remove degenerate vertices.
Chris@16:     vertex_iterator last_vertex = vertices_.begin();
Chris@16:     for (vertex_iterator it = vertices_.begin(); it != vertices_.end(); ++it) {
Chris@16:       if (it->incident_edge()) {
Chris@16:         if (it != last_vertex) {
Chris@16:           *last_vertex = *it;
Chris@16:           vertex_type* v = &(*last_vertex);
Chris@16:           edge_type* e = v->incident_edge();
Chris@16:           do {
Chris@16:             e->vertex0(v);
Chris@16:             e = e->rot_next();
Chris@16:           } while (e != v->incident_edge());
Chris@16:         }
Chris@16:         ++last_vertex;
Chris@16:       }
Chris@16:     }
Chris@16:     vertices_.erase(last_vertex, vertices_.end());
Chris@16: 
Chris@16:     // Set up next/prev pointers for infinite edges.
Chris@16:     if (vertices_.empty()) {
Chris@16:       if (!edges_.empty()) {
Chris@16:         // Update prev/next pointers for the line edges.
Chris@16:         edge_iterator edge_it = edges_.begin();
Chris@16:         edge_type* edge1 = &(*edge_it);
Chris@16:         edge1->next(edge1);
Chris@16:         edge1->prev(edge1);
Chris@16:         ++edge_it;
Chris@16:         edge1 = &(*edge_it);
Chris@16:         ++edge_it;
Chris@16: 
Chris@16:         while (edge_it != edges_.end()) {
Chris@16:           edge_type* edge2 = &(*edge_it);
Chris@16:           ++edge_it;
Chris@16: 
Chris@16:           edge1->next(edge2);
Chris@16:           edge1->prev(edge2);
Chris@16:           edge2->next(edge1);
Chris@16:           edge2->prev(edge1);
Chris@16: 
Chris@16:           edge1 = &(*edge_it);
Chris@16:           ++edge_it;
Chris@16:         }
Chris@16: 
Chris@16:         edge1->next(edge1);
Chris@16:         edge1->prev(edge1);
Chris@16:       }
Chris@16:     } else {
Chris@16:       // Update prev/next pointers for the ray edges.
Chris@16:       for (cell_iterator cell_it = cells_.begin();
Chris@16:          cell_it != cells_.end(); ++cell_it) {
Chris@16:         if (cell_it->is_degenerate())
Chris@16:           continue;
Chris@16:         // Move to the previous edge while
Chris@16:         // it is possible in the CW direction.
Chris@16:         edge_type* left_edge = cell_it->incident_edge();
Chris@16:         while (left_edge->prev() != NULL) {
Chris@16:           left_edge = left_edge->prev();
Chris@16:           // Terminate if this is not a boundary cell.
Chris@16:           if (left_edge == cell_it->incident_edge())
Chris@16:             break;
Chris@16:         }
Chris@16: 
Chris@16:         if (left_edge->prev() != NULL)
Chris@16:           continue;
Chris@16: 
Chris@16:         edge_type* right_edge = cell_it->incident_edge();
Chris@16:         while (right_edge->next() != NULL)
Chris@16:           right_edge = right_edge->next();
Chris@16:         left_edge->prev(right_edge);
Chris@16:         right_edge->next(left_edge);
Chris@16:       }
Chris@16:     }
Chris@16:   }
Chris@16: 
Chris@16:  private:
Chris@16:   typedef typename cell_container_type::iterator cell_iterator;
Chris@16:   typedef typename vertex_container_type::iterator vertex_iterator;
Chris@16:   typedef typename edge_container_type::iterator edge_iterator;
Chris@16:   typedef typename TRAITS::vertex_equality_predicate_type
Chris@16:     vertex_equality_predicate_type;
Chris@16: 
Chris@16:   template <typename SEvent>
Chris@16:   bool is_primary_edge(const SEvent& site1, const SEvent& site2) const {
Chris@16:     bool flag1 = site1.is_segment();
Chris@16:     bool flag2 = site2.is_segment();
Chris@16:     if (flag1 && !flag2) {
Chris@16:       return (site1.point0() != site2.point0()) &&
Chris@16:              (site1.point1() != site2.point0());
Chris@16:     }
Chris@16:     if (!flag1 && flag2) {
Chris@16:       return (site2.point0() != site1.point0()) &&
Chris@16:              (site2.point1() != site1.point0());
Chris@16:     }
Chris@16:     return true;
Chris@16:   }
Chris@16: 
Chris@16:   template <typename SEvent>
Chris@16:   bool is_linear_edge(const SEvent& site1, const SEvent& site2) const {
Chris@16:     if (!is_primary_edge(site1, site2)) {
Chris@16:       return true;
Chris@16:     }
Chris@16:     return !(site1.is_segment() ^ site2.is_segment());
Chris@16:   }
Chris@16: 
Chris@16:   // Remove degenerate edge.
Chris@16:   void remove_edge(edge_type* edge) {
Chris@16:     // Update the endpoints of the incident edges to the second vertex.
Chris@16:     vertex_type* vertex = edge->vertex0();
Chris@16:     edge_type* updated_edge = edge->twin()->rot_next();
Chris@16:     while (updated_edge != edge->twin()) {
Chris@16:       updated_edge->vertex0(vertex);
Chris@16:       updated_edge = updated_edge->rot_next();
Chris@16:     }
Chris@16: 
Chris@16:     edge_type* edge1 = edge;
Chris@16:     edge_type* edge2 = edge->twin();
Chris@16: 
Chris@16:     edge_type* edge1_rot_prev = edge1->rot_prev();
Chris@16:     edge_type* edge1_rot_next = edge1->rot_next();
Chris@16: 
Chris@16:     edge_type* edge2_rot_prev = edge2->rot_prev();
Chris@16:     edge_type* edge2_rot_next = edge2->rot_next();
Chris@16: 
Chris@16:     // Update prev/next pointers for the incident edges.
Chris@16:     edge1_rot_next->twin()->next(edge2_rot_prev);
Chris@16:     edge2_rot_prev->prev(edge1_rot_next->twin());
Chris@16:     edge1_rot_prev->prev(edge2_rot_next->twin());
Chris@16:     edge2_rot_next->twin()->next(edge1_rot_prev);
Chris@16:   }
Chris@16: 
Chris@16:   cell_container_type cells_;
Chris@16:   vertex_container_type vertices_;
Chris@16:   edge_container_type edges_;
Chris@16:   vertex_equality_predicate_type vertex_equality_predicate_;
Chris@16: 
Chris@16:   // Disallow copy constructor and operator=
Chris@16:   voronoi_diagram(const voronoi_diagram&);
Chris@16:   void operator=(const voronoi_diagram&);
Chris@16: };
Chris@16: }  // polygon
Chris@16: }  // boost
Chris@16: 
Chris@16: #endif  // BOOST_POLYGON_VORONOI_DIAGRAM