[Boost-commit] svn:boost r80400 - in trunk: boost/polygon boost/polygon/detail libs/polygon/example libs/polygon/test

Subject: [Boost-commit] svn:boost r80400 - in trunk: boost/polygon boost/polygon/detail libs/polygon/example libs/polygon/test
From: sydorchuk.andriy_at_[hidden]
Date: 2012-09-04 17:26:12

Author: asydorchuk
Date: 2012-09-04 17:26:11 EDT (Tue, 04 Sep 2012)
New Revision: 80400
URL: http://svn.boost.org/trac/boost/changeset/80400

Log:
Polygon: adding voronoi_events to the public part of the library.
Added:
   trunk/boost/polygon/voronoi_events.hpp   (contents, props changed)
   trunk/libs/polygon/test/voronoi_events_test.cpp   (contents, props changed)
Text files modified: 
   trunk/boost/polygon/detail/voronoi_structures.hpp   |   314 ----------------------------------------
   trunk/boost/polygon/voronoi_builder.hpp             |    22 +-                                      
   trunk/boost/polygon/voronoi_diagram.hpp             |    33 ++--                                    
   trunk/libs/polygon/example/voronoi_visualizer.cpp   |     4                                         
   trunk/libs/polygon/test/Jamfile.v2                  |     1                                         
   trunk/libs/polygon/test/voronoi_predicates_test.cpp |     3                                         
   trunk/libs/polygon/test/voronoi_structures_test.cpp |    83 ----------                              
   7 files changed, 32 insertions(+), 428 deletions(-)

Modified: trunk/boost/polygon/detail/voronoi_structures.hpp
==============================================================================
--- trunk/boost/polygon/detail/voronoi_structures.hpp	(original)
+++ trunk/boost/polygon/detail/voronoi_structures.hpp	2012-09-04 17:26:11 EDT (Tue, 04 Sep 2012)
@@ -17,320 +17,6 @@
 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_;
-};
-
-// Represents topology type of the voronoi site.
-enum GeometryCategory {
-  GEOMETRY_CATEGORY_POINT = 0x0,
-  GEOMETRY_CATEGORY_SEGMENT = 0x1
-};
-
-// Represents category of the input source that forms Voronoi cell.
-enum SourceCategory {
-  // Point subtypes.
-  SOURCE_CATEGORY_SINGLE_POINT = 0x0,
-  SOURCE_CATEGORY_SEGMENT_START_POINT = 0x1,
-  SOURCE_CATEGORY_SEGMENT_END_POINT = 0x2,
-
-  // Segment subtypes.
-  SOURCE_CATEGORY_INITIAL_SEGMENT = 0x8,
-  SOURCE_CATEGORY_REVERSE_SEGMENT = 0x9,
-
-  SOURCE_CATEGORY_GEOMETRY_SHIFT = 0x3,
-  SOURCE_CATEGORY_BITMASK = 0x1F
-};
-
-bool belongs(
-    const SourceCategory& source_category,
-    const GeometryCategory& geometry_category) {
-  return (static_cast<std::size_t>(source_category) >> SOURCE_CATEGORY_GEOMETRY_SHIFT) ==
-      static_cast<std::size_t>(geometry_category);
-}
-
-// 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) {}
-
-  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 {
-    if (!oriented)
-      return point0_.x();
-    return is_inverse() ? point1_.x() : point0_.x();
-  }
-
-  coordinate_type y0(bool oriented = false) const {
-    if (!oriented)
-      return point0_.y();
-    return is_inverse() ? point1_.y() : point0_.y();
-  }
-
-  coordinate_type x1(bool oriented = false) const {
-    if (!oriented)
-      return point1_.x();
-    return is_inverse() ? point0_.x() : point1_.x();
-  }
-
-  coordinate_type y1(bool oriented = false) const {
-    if (!oriented)
-      return point1_.y();
-    return is_inverse() ? point0_.y() : point1_.y();
-  }
-
-  const point_type& point0(bool oriented = false) const {
-    if (!oriented)
-      return point0_;
-    return is_inverse() ? point1_ : point0_;
-  }
-
-  const point_type& point1(bool oriented = false) const {
-    if (!oriented)
-      return point1_;
-    return is_inverse() ? point0_ : 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;
-  }
-
-  site_event& inverse() {
-    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

Modified: trunk/boost/polygon/voronoi_builder.hpp
==============================================================================
--- trunk/boost/polygon/voronoi_builder.hpp	(original)
+++ trunk/boost/polygon/voronoi_builder.hpp	2012-09-04 17:26:11 EDT (Tue, 04 Sep 2012)
@@ -18,6 +18,8 @@
 #include "detail/voronoi_predicates.hpp"
 #include "detail/voronoi_structures.hpp"
 
+#include "voronoi_events.hpp"
+
 namespace boost {
 namespace polygon {
 // GENERAL INFO:
@@ -51,7 +53,7 @@
   std::size_t insert_point(const int_type& x, const int_type& y) {
     site_events_.push_back(site_event_type(x, y));
     site_events_.back().initial_index(index_);
-    site_events_.back().source_category(detail::SOURCE_CATEGORY_SINGLE_POINT);
+    site_events_.back().source_category(SOURCE_CATEGORY_SINGLE_POINT);
     return index_++;
   }
 
@@ -66,25 +68,21 @@
     point_type p1(x1, y1);
     site_events_.push_back(site_event_type(p1));
     site_events_.back().initial_index(index_);
-    site_events_.back().source_category(
-        detail::SOURCE_CATEGORY_SEGMENT_START_POINT);
+    site_events_.back().source_category(SOURCE_CATEGORY_SEGMENT_START_POINT);
 
     // Set up end point site.
     point_type p2(x2, y2);
     site_events_.push_back(site_event_type(p2));
     site_events_.back().initial_index(index_);
-    site_events_.back().source_category(
-        detail::SOURCE_CATEGORY_SEGMENT_END_POINT);
+    site_events_.back().source_category(SOURCE_CATEGORY_SEGMENT_END_POINT);
 
     // Set up segment site.
     if (point_comparison_(p1, p2)) {
       site_events_.push_back(site_event_type(p1, p2));
-      site_events_.back().source_category(
-          detail::SOURCE_CATEGORY_INITIAL_SEGMENT);
+      site_events_.back().source_category(SOURCE_CATEGORY_INITIAL_SEGMENT);
     } else {
       site_events_.push_back(site_event_type(p2, p1));
-      site_events_.back().source_category(
-          detail::SOURCE_CATEGORY_REVERSE_SEGMENT);
+      site_events_.back().source_category(SOURCE_CATEGORY_REVERSE_SEGMENT);
     }
     site_events_.back().initial_index(index_);
     return index_++;
@@ -131,11 +129,11 @@
   }
 
 private:
-  typedef detail::point_2d<int_type> point_type;
-  typedef detail::site_event<int_type> site_event_type;
+  typedef point_2d<int_type> point_type;
+  typedef site_event<int_type> site_event_type;
   typedef typename std::vector<site_event_type>::const_iterator
     site_event_iterator_type;
-  typedef detail::circle_event<fpt_type> circle_event_type;
+  typedef circle_event<fpt_type> circle_event_type;
   typedef typename VP::template point_comparison_predicate<point_type>
     point_comparison_predicate;
   typedef typename VP::

Modified: trunk/boost/polygon/voronoi_diagram.hpp
==============================================================================
--- trunk/boost/polygon/voronoi_diagram.hpp	(original)
+++ trunk/boost/polygon/voronoi_diagram.hpp	2012-09-04 17:26:11 EDT (Tue, 04 Sep 2012)
@@ -13,7 +13,7 @@
 #include <vector>
 
 #include "detail/voronoi_ctypes.hpp"
-#include "detail/voronoi_structures.hpp"
+#include "voronoi_events.hpp"
 
 namespace boost {
 namespace polygon {
@@ -35,7 +35,7 @@
   typedef std::size_t color_type;
   typedef voronoi_edge<coordinate_type> voronoi_edge_type;
   typedef std::size_t source_index_type;
-  typedef detail::SourceCategory source_category_type;
+  typedef SourceCategory source_category_type;
 
   voronoi_cell(const source_index_type& source_index,
                const source_category_type& source_category,
@@ -47,13 +47,13 @@
   // Returns true if the cell contains point site, false else.
   bool contains_point() const {
     source_category_type source_category = this->source_category();
-    return detail::belongs(source_category, detail::GEOMETRY_CATEGORY_POINT);
+    return belongs(source_category, GEOMETRY_CATEGORY_POINT);
   }
 
   // Returns true if the cell contains segment site, false else.
   bool contains_segment() const {
     source_category_type source_category = this->source_category();
-    return detail::belongs(source_category, detail::GEOMETRY_CATEGORY_SEGMENT);
+    return belongs(source_category, GEOMETRY_CATEGORY_SEGMENT);
   }
 
   source_index_type source_index() const {
@@ -61,8 +61,7 @@
   }
 
   source_category_type source_category() const {
-    return static_cast<source_category_type>(
-        color_ & detail::SOURCE_CATEGORY_BITMASK);
+    return static_cast<source_category_type>(color_ & SOURCE_CATEGORY_BITMASK);
   }
 
   // Degenerate cells don't have any incident edges.
@@ -222,25 +221,25 @@
   // Returns true if the edge is linear (segment, ray, line).
   // Returns false if the edge is curved (parabolic arc).
   bool is_linear() const {
-    return color_ & BIT_IS_LINEAR;
+    return (color_ & BIT_IS_LINEAR) ? true : false;
   }
 
   // Returns true if the edge is curved (parabolic arc).
   // Returns false if the edge is linear (segment, ray, line).
   bool is_curved() const {
-    return !(color_ & BIT_IS_LINEAR);
+    return (color_ & BIT_IS_LINEAR) ? false : true;
   }
 
   // Returns false if edge goes through the endpoint of the segment.
   // Returns true else.
   bool is_primary() const {
-    return color_ & BIT_IS_PRIMARY;
+    return (color_ & BIT_IS_PRIMARY) ? true : false;
   }
 
   // Returns true if edge goes through the endpoint of the segment.
   // Returns false else.
   bool is_secondary() const {
-    return !(color_ & BIT_IS_PRIMARY);
+    return (color_ & BIT_IS_PRIMARY) ? false : true;
   }
 
   color_type color() const { return color_ >> BITS_SHIFT; }
@@ -351,8 +350,8 @@
     edges_.reserve((num_sites << 2) + (num_sites << 1));
   }
 
-template <typename SEvent>
-  void _process_single_site(const SEvent& site) {
+  template <typename CT>
+  void _process_single_site(const site_event<CT>& site) {
     cells_.push_back(cell_type(
          site.initial_index(), site.source_category(), NULL));
   }
@@ -360,9 +359,9 @@
   // Insert a new half-edge into the output data structure.
   // Takes as input left and right sites that form a new bisector.
   // Returns a pair of pointers to a new half-edges.
-  template <typename SEvent>
+  template <typename CT>
   std::pair<void*, void*> _insert_new_edge(
-      const SEvent& site1, const SEvent& site2) {
+      const site_event<CT>& site1, const site_event<CT>& site2) {
     // Get sites' indexes.
     int site_index1 = site1.sorted_index();
     int site_index2 = site2.sorted_index();
@@ -407,10 +406,10 @@
   // that corresponds to the intersection point of the two old half-edges,
   // pointers to those half-edges. Half-edges' direction goes out of the
   // new Voronoi vertex point. Returns a pair of pointers to a new half-edges.
-  template <typename SEvent, typename CEvent>
+  template <typename CT1, typename CT2>
   std::pair<void*, void*> _insert_new_edge(
-      const SEvent& site1, const SEvent& site3, const CEvent& circle,
-      void* data12, void* data23) {
+      const site_event<CT1>& site1, const site_event<CT1>& site3,
+      const circle_event<CT2>& circle, void* data12, void* data23) {
     edge_type* edge12 = static_cast<edge_type*>(data12);
     edge_type* edge23 = static_cast<edge_type*>(data23);
 

Added: trunk/boost/polygon/voronoi_events.hpp
==============================================================================
--- (empty file)
+++ trunk/boost/polygon/voronoi_events.hpp	2012-09-04 17:26:11 EDT (Tue, 04 Sep 2012)
@@ -0,0 +1,332 @@
+// Boost.Polygon library voronoi_events.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_VORONOI_EVENTS
+#define BOOST_POLYGON_VORONOI_EVENTS
+
+namespace boost {
+namespace polygon {
+// Warning: only the below two enums and routine should be used by users.
+// Represents topology type of the voronoi site.
+enum GeometryCategory {
+  GEOMETRY_CATEGORY_POINT = 0x0,
+  GEOMETRY_CATEGORY_SEGMENT = 0x1
+};
+
+// Represents category of the input source that forms Voronoi cell.
+enum SourceCategory {
+  // Point subtypes.
+  SOURCE_CATEGORY_SINGLE_POINT = 0x0,
+  SOURCE_CATEGORY_SEGMENT_START_POINT = 0x1,
+  SOURCE_CATEGORY_SEGMENT_END_POINT = 0x2,
+
+  // Segment subtypes.
+  SOURCE_CATEGORY_INITIAL_SEGMENT = 0x8,
+  SOURCE_CATEGORY_REVERSE_SEGMENT = 0x9,
+
+  SOURCE_CATEGORY_GEOMETRY_SHIFT = 0x3,
+  SOURCE_CATEGORY_BITMASK = 0x1F
+};
+
+bool belongs(
+    const SourceCategory& source_category,
+    const GeometryCategory& geometry_category) {
+  return (static_cast<std::size_t>(source_category) >>
+      SOURCE_CATEGORY_GEOMETRY_SHIFT) ==
+      static_cast<std::size_t>(geometry_category);
+}
+
+// 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) {}
+
+  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 {
+    if (!oriented)
+      return point0_.x();
+    return is_inverse() ? point1_.x() : point0_.x();
+  }
+
+  coordinate_type y0(bool oriented = false) const {
+    if (!oriented)
+      return point0_.y();
+    return is_inverse() ? point1_.y() : point0_.y();
+  }
+
+  coordinate_type x1(bool oriented = false) const {
+    if (!oriented)
+      return point1_.x();
+    return is_inverse() ? point0_.x() : point1_.x();
+  }
+
+  coordinate_type y1(bool oriented = false) const {
+    if (!oriented)
+      return point1_.y();
+    return is_inverse() ? point0_.y() : point1_.y();
+  }
+
+  const point_type& point0(bool oriented = false) const {
+    if (!oriented)
+      return point0_;
+    return is_inverse() ? point1_ : point0_;
+  }
+
+  const point_type& point1(bool oriented = false) const {
+    if (!oriented)
+      return point1_;
+    return is_inverse() ? point0_ : 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() {
+    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_;
+};
+}  // polygon
+}  // boost
+
+#endif  // BOOST_POLYGON_VORONOI_EVENTS

Modified: trunk/libs/polygon/example/voronoi_visualizer.cpp
==============================================================================
--- trunk/libs/polygon/example/voronoi_visualizer.cpp	(original)
+++ trunk/libs/polygon/example/voronoi_visualizer.cpp	2012-09-04 17:26:11 EDT (Tue, 04 Sep 2012)
@@ -349,11 +349,11 @@
   point_type retrieve_point(const cell_type& cell) {
     source_index_type index = cell.source_index();
     source_category_type category = cell.source_category();
-    if (category == detail::SOURCE_CATEGORY_SINGLE_POINT) {
+    if (category == SOURCE_CATEGORY_SINGLE_POINT) {
       return point_data_[index];
     }
     index -= point_data_.size();
-    if (category == detail::SOURCE_CATEGORY_SEGMENT_START_POINT) {
+    if (category == SOURCE_CATEGORY_SEGMENT_START_POINT) {
       return low(segment_data_[index]);
     } else {
       return high(segment_data_[index]);

Modified: trunk/libs/polygon/test/Jamfile.v2
==============================================================================
--- trunk/libs/polygon/test/Jamfile.v2	(original)
+++ trunk/libs/polygon/test/Jamfile.v2	2012-09-04 17:26:11 EDT (Tue, 04 Sep 2012)
@@ -26,6 +26,7 @@
     :
         [ run voronoi_builder_test.cpp ]
         [ run voronoi_ctypes_test.cpp ]
+        [ run voronoi_events_test.cpp ]
         [ run voronoi_predicates_test.cpp ]
         [ run voronoi_robust_fpt_test.cpp ]
         [ run voronoi_structures_test.cpp ]

Added: trunk/libs/polygon/test/voronoi_events_test.cpp
==============================================================================
--- (empty file)
+++ trunk/libs/polygon/test/voronoi_events_test.cpp	2012-09-04 17:26:11 EDT (Tue, 04 Sep 2012)
@@ -0,0 +1,98 @@
+// Boost.Polygon library voronoi_events_test.cpp 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.
+
+#define BOOST_TEST_MODULE voronoi_events_test
+
+#include <boost/test/test_case_template.hpp>
+#include <boost/polygon/voronoi_events.hpp>
+using namespace boost::polygon;
+
+typedef point_2d<int> point_type;
+typedef site_event<int> site_type;
+typedef circle_event<int> circle_type;
+
+BOOST_AUTO_TEST_CASE(point_2d_test1) {
+  point_type p(1, 2);
+  BOOST_CHECK_EQUAL(p.x(), 1);
+  BOOST_CHECK_EQUAL(p.y(), 2);
+  p.x(3);
+  BOOST_CHECK_EQUAL(p.x(), 3);
+  p.y(4);
+  BOOST_CHECK_EQUAL(p.y(), 4);
+}
+
+BOOST_AUTO_TEST_CASE(source_category_test1) {
+  BOOST_CHECK(belongs(SOURCE_CATEGORY_SINGLE_POINT, GEOMETRY_CATEGORY_POINT));
+  BOOST_CHECK(belongs(SOURCE_CATEGORY_SEGMENT_START_POINT, GEOMETRY_CATEGORY_POINT));
+  BOOST_CHECK(belongs(SOURCE_CATEGORY_SEGMENT_END_POINT, GEOMETRY_CATEGORY_POINT));
+  BOOST_CHECK(!belongs(SOURCE_CATEGORY_INITIAL_SEGMENT, GEOMETRY_CATEGORY_POINT));
+  BOOST_CHECK(!belongs(SOURCE_CATEGORY_REVERSE_SEGMENT, GEOMETRY_CATEGORY_POINT));
+
+  BOOST_CHECK(!belongs(SOURCE_CATEGORY_SINGLE_POINT, GEOMETRY_CATEGORY_SEGMENT));
+  BOOST_CHECK(!belongs(SOURCE_CATEGORY_SEGMENT_START_POINT, GEOMETRY_CATEGORY_SEGMENT));
+  BOOST_CHECK(!belongs(SOURCE_CATEGORY_SEGMENT_END_POINT, GEOMETRY_CATEGORY_SEGMENT));
+  BOOST_CHECK(belongs(SOURCE_CATEGORY_INITIAL_SEGMENT, GEOMETRY_CATEGORY_SEGMENT));
+  BOOST_CHECK(belongs(SOURCE_CATEGORY_REVERSE_SEGMENT, GEOMETRY_CATEGORY_SEGMENT));
+}
+
+BOOST_AUTO_TEST_CASE(site_event_test1) {
+  site_type s(1, 2);
+  s.sorted_index(1);
+  s.initial_index(2);
+  s.source_category(SOURCE_CATEGORY_SEGMENT_START_POINT);
+  BOOST_CHECK(s.x0() == 1 && s.x1() == 1);
+  BOOST_CHECK(s.y0() == 2 && s.y1() == 2);
+  BOOST_CHECK(s.is_point());
+  BOOST_CHECK(!s.is_segment());
+  BOOST_CHECK(!s.is_inverse());
+  BOOST_CHECK(s.sorted_index() == 1);
+  BOOST_CHECK(s.initial_index() == 2);
+  BOOST_CHECK(s.source_category() == SOURCE_CATEGORY_SEGMENT_START_POINT);
+}
+
+BOOST_AUTO_TEST_CASE(site_event_test2) {
+  site_type s(1, 2, 3, 4);
+  s.sorted_index(1);
+  s.initial_index(2);
+  s.source_category(SOURCE_CATEGORY_INITIAL_SEGMENT);
+  BOOST_CHECK(s.x0(true) == 1 && s.x0() == 1);
+  BOOST_CHECK(s.y0(true) == 2 && s.y0() == 2);
+  BOOST_CHECK(s.x1(true) == 3 && s.x1() == 3);
+  BOOST_CHECK(s.y1(true) == 4 && s.y1() == 4);
+  BOOST_CHECK(!s.is_point());
+  BOOST_CHECK(s.is_segment());
+  BOOST_CHECK(!s.is_inverse());
+  BOOST_CHECK(s.source_category() == SOURCE_CATEGORY_INITIAL_SEGMENT);
+  
+  s.inverse();
+  BOOST_CHECK(s.x1(true) == 1 && s.x0() == 1);
+  BOOST_CHECK(s.y1(true) == 2 && s.y0() == 2);
+  BOOST_CHECK(s.x0(true) == 3 && s.x1() == 3);
+  BOOST_CHECK(s.y0(true) == 4 && s.y1() == 4);
+  BOOST_CHECK(s.is_inverse());
+  BOOST_CHECK(s.source_category() == SOURCE_CATEGORY_INITIAL_SEGMENT);
+}
+
+BOOST_AUTO_TEST_CASE(circle_event_test) {
+  circle_type c(0, 1, 2);
+  BOOST_CHECK_EQUAL(c.x(), 0);
+  BOOST_CHECK_EQUAL(c.y(), 1);
+  BOOST_CHECK_EQUAL(c.lower_x(), 2);
+  BOOST_CHECK_EQUAL(c.lower_y(), 1);
+  BOOST_CHECK(c.is_active());
+  c.x(3);
+  c.y(4);
+  c.lower_x(5);
+  BOOST_CHECK_EQUAL(c.x(), 3);
+  BOOST_CHECK_EQUAL(c.y(), 4);
+  BOOST_CHECK_EQUAL(c.lower_x(), 5);
+  BOOST_CHECK_EQUAL(c.lower_y(), 4);
+  c.deactivate();
+  BOOST_CHECK(!c.is_active());
+}

Modified: trunk/libs/polygon/test/voronoi_predicates_test.cpp
==============================================================================
--- trunk/libs/polygon/test/voronoi_predicates_test.cpp	(original)
+++ trunk/libs/polygon/test/voronoi_predicates_test.cpp	2012-09-04 17:26:11 EDT (Tue, 04 Sep 2012)
@@ -17,6 +17,9 @@
 #include <boost/polygon/detail/voronoi_structures.hpp>
 using namespace boost::polygon::detail;
 
+#include <boost/polygon/voronoi_events.hpp>
+using namespace boost::polygon;
+
 ulp_comparison<double> ulp_cmp;
 
 typedef voronoi_predicates< voronoi_ctype_traits<int> > VP;

Modified: trunk/libs/polygon/test/voronoi_structures_test.cpp
==============================================================================
--- trunk/libs/polygon/test/voronoi_structures_test.cpp	(original)
+++ trunk/libs/polygon/test/voronoi_structures_test.cpp	2012-09-04 17:26:11 EDT (Tue, 04 Sep 2012)
@@ -13,93 +13,10 @@
 #include <boost/polygon/detail/voronoi_structures.hpp>
 using namespace boost::polygon::detail;
 
-typedef point_2d<int> point_type;
-typedef site_event<int> site_type;
-typedef circle_event<int> circle_type;
 typedef ordered_queue<int, std::greater<int> > ordered_queue_type;
 typedef beach_line_node_key<int> node_key_type;
 typedef beach_line_node_data<int, int> node_data_type;
 
-BOOST_AUTO_TEST_CASE(point_2d_test1) {
-  point_type p(1, 2);
-  BOOST_CHECK_EQUAL(p.x(), 1);
-  BOOST_CHECK_EQUAL(p.y(), 2);
-  p.x(3);
-  BOOST_CHECK_EQUAL(p.x(), 3);
-  p.y(4);
-  BOOST_CHECK_EQUAL(p.y(), 4);
-}
-
-BOOST_AUTO_TEST_CASE(source_category_test1) {
-  BOOST_CHECK(belongs(SOURCE_CATEGORY_SINGLE_POINT, GEOMETRY_CATEGORY_POINT));
-  BOOST_CHECK(belongs(SOURCE_CATEGORY_SEGMENT_START_POINT, GEOMETRY_CATEGORY_POINT));
-  BOOST_CHECK(belongs(SOURCE_CATEGORY_SEGMENT_END_POINT, GEOMETRY_CATEGORY_POINT));
-  BOOST_CHECK(!belongs(SOURCE_CATEGORY_INITIAL_SEGMENT, GEOMETRY_CATEGORY_POINT));
-  BOOST_CHECK(!belongs(SOURCE_CATEGORY_REVERSE_SEGMENT, GEOMETRY_CATEGORY_POINT));
-
-  BOOST_CHECK(!belongs(SOURCE_CATEGORY_SINGLE_POINT, GEOMETRY_CATEGORY_SEGMENT));
-  BOOST_CHECK(!belongs(SOURCE_CATEGORY_SEGMENT_START_POINT, GEOMETRY_CATEGORY_SEGMENT));
-  BOOST_CHECK(!belongs(SOURCE_CATEGORY_SEGMENT_END_POINT, GEOMETRY_CATEGORY_SEGMENT));
-  BOOST_CHECK(belongs(SOURCE_CATEGORY_INITIAL_SEGMENT, GEOMETRY_CATEGORY_SEGMENT));
-  BOOST_CHECK(belongs(SOURCE_CATEGORY_REVERSE_SEGMENT, GEOMETRY_CATEGORY_SEGMENT));
-}
-
-BOOST_AUTO_TEST_CASE(site_event_test1) {
-  site_type s(1, 2);
-  s.sorted_index(1);
-  s.initial_index(2);
-  s.source_category(SOURCE_CATEGORY_SEGMENT_START_POINT);
-  BOOST_CHECK(s.x0() == 1 && s.x1() == 1);
-  BOOST_CHECK(s.y0() == 2 && s.y1() == 2);
-  BOOST_CHECK(s.is_point());
-  BOOST_CHECK(!s.is_segment());
-  BOOST_CHECK(!s.is_inverse());
-  BOOST_CHECK(s.sorted_index() == 1);
-  BOOST_CHECK(s.initial_index() == 2);
-  BOOST_CHECK(s.source_category() == SOURCE_CATEGORY_SEGMENT_START_POINT);
-}
-
-BOOST_AUTO_TEST_CASE(site_event_test2) {
-  site_type s(1, 2, 3, 4);
-  s.sorted_index(1);
-  s.initial_index(2);
-  s.source_category(SOURCE_CATEGORY_INITIAL_SEGMENT);
-  BOOST_CHECK(s.x0(true) == 1 && s.x0() == 1);
-  BOOST_CHECK(s.y0(true) == 2 && s.y0() == 2);
-  BOOST_CHECK(s.x1(true) == 3 && s.x1() == 3);
-  BOOST_CHECK(s.y1(true) == 4 && s.y1() == 4);
-  BOOST_CHECK(!s.is_point());
-  BOOST_CHECK(s.is_segment());
-  BOOST_CHECK(!s.is_inverse());
-  BOOST_CHECK(s.source_category() == SOURCE_CATEGORY_INITIAL_SEGMENT);
-  
-  s.inverse();
-  BOOST_CHECK(s.x1(true) == 1 && s.x0() == 1);
-  BOOST_CHECK(s.y1(true) == 2 && s.y0() == 2);
-  BOOST_CHECK(s.x0(true) == 3 && s.x1() == 3);
-  BOOST_CHECK(s.y0(true) == 4 && s.y1() == 4);
-  BOOST_CHECK(s.is_inverse());
-  BOOST_CHECK(s.source_category() == SOURCE_CATEGORY_INITIAL_SEGMENT);
-}
-
-BOOST_AUTO_TEST_CASE(circle_event_test) {
-  circle_type c(0, 1, 2);
-  BOOST_CHECK_EQUAL(c.x(), 0);
-  BOOST_CHECK_EQUAL(c.y(), 1);
-  BOOST_CHECK_EQUAL(c.lower_x(), 2);
-  BOOST_CHECK_EQUAL(c.lower_y(), 1);
-  BOOST_CHECK(c.is_active());
-  c.x(3);
-  c.y(4);
-  c.lower_x(5);
-  BOOST_CHECK_EQUAL(c.x(), 3);
-  BOOST_CHECK_EQUAL(c.y(), 4);
-  BOOST_CHECK_EQUAL(c.lower_x(), 5);
-  BOOST_CHECK_EQUAL(c.lower_y(), 4);
-  c.deactivate();
-  BOOST_CHECK(!c.is_active());
-}
-
 BOOST_AUTO_TEST_CASE(ordered_queue_test) {
   ordered_queue_type q;
   BOOST_CHECK(q.empty());