[Boost-commit] svn:boost r74369 - in sandbox/SOC/2010/sweepline: boost/sweepline boost/sweepline/detail libs/sweepline/example libs/sweepline/test

Subject: [Boost-commit] svn:boost r74369 - in sandbox/SOC/2010/sweepline: boost/sweepline boost/sweepline/detail libs/sweepline/example libs/sweepline/test
From: sydorchuk.andriy_at_[hidden]
Date: 2011-09-13 12:39:37

Author: asydorchuk
Date: 2011-09-13 12:39:35 EDT (Tue, 13 Sep 2011)
New Revision: 74369
URL: http://svn.boost.org/trac/boost/changeset/74369

Log:
Refactoring: 1) removed all the dependencies between voronoi_builder and voronoi_diagram classes (splitted them).
Changed benchmark test to use file streams.
Changed ercs to doubles in circle_events as they are not used anymore.
Added:
   sandbox/SOC/2010/sweepline/boost/sweepline/voronoi.hpp   (contents, props changed)
   sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_builder.hpp   (contents, props changed)
Text files modified: 
   sandbox/SOC/2010/sweepline/boost/sweepline/detail/voronoi_formation.hpp       |   112 ++----                                  
   sandbox/SOC/2010/sweepline/boost/sweepline/detail/voronoi_fpt_kernel.hpp      |    66 +--                                     
   sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_diagram.hpp                |   619 --------------------------------------- 
   sandbox/SOC/2010/sweepline/libs/sweepline/example/voronoi_visualizer.cpp      |    26                                         
   sandbox/SOC/2010/sweepline/libs/sweepline/test/benchmark_test.cpp             |     4                                         
   sandbox/SOC/2010/sweepline/libs/sweepline/test/circle_event_creation_test.cpp |     6                                         
   sandbox/SOC/2010/sweepline/libs/sweepline/test/clipping_test.cpp              |     1                                         
   sandbox/SOC/2010/sweepline/libs/sweepline/test/event_queue_test.cpp           |     2                                         
   sandbox/SOC/2010/sweepline/libs/sweepline/test/event_types_test.cpp           |     2                                         
   sandbox/SOC/2010/sweepline/libs/sweepline/test/node_comparer_test.cpp         |    18                                         
   sandbox/SOC/2010/sweepline/libs/sweepline/test/predicates_test.cpp            |     2                                         
   sandbox/SOC/2010/sweepline/libs/sweepline/test/robust_fpt_test.cpp            |     2                                         
   sandbox/SOC/2010/sweepline/libs/sweepline/test/sqrt_expr_evaluator_test.cpp   |     2                                         
   sandbox/SOC/2010/sweepline/libs/sweepline/test/sweepline_test.cpp             |    64 ++--                                    
   14 files changed, 146 insertions(+), 780 deletions(-)

Modified: sandbox/SOC/2010/sweepline/boost/sweepline/detail/voronoi_formation.hpp
==============================================================================
--- sandbox/SOC/2010/sweepline/boost/sweepline/detail/voronoi_formation.hpp	(original)
+++ sandbox/SOC/2010/sweepline/boost/sweepline/detail/voronoi_formation.hpp	2011-09-13 12:39:35 EDT (Tue, 13 Sep 2011)
@@ -15,10 +15,6 @@
 
 namespace boost {
 namespace sweepline {
-
-    template <typename T>
-    class voronoi_edge;
-
 namespace detail {
 
     ///////////////////////////////////////////////////////////////////////////
@@ -27,7 +23,7 @@
 
     // Forward declarations.
     template <typename T>
-    class beach_line_node;
+    class beach_line_node_key;
 
     template <typename T>
     class beach_line_node_data;
@@ -35,9 +31,6 @@
     template <typename T>
     struct node_comparer;
 
-    template <typename T>
-    class epsilon_robust_comparator;
-
     // Represents the result of the orientation test.
     enum kOrientation {
         RIGHT_ORIENTATION = -1,
@@ -402,8 +395,7 @@
         typedef T coordinate_type;
         typedef point_2d<T> point_type;
         typedef site_event<T> site_event_type;
-        typedef epsilon_robust_comparator<T> erc_type;
-        typedef beach_line_node<coordinate_type> Key;
+        typedef beach_line_node_key<coordinate_type> Key;
         typedef beach_line_node_data<coordinate_type> Value;
         typedef node_comparer<Key> NodeComparer;
         typedef typename std::map< Key, Value, NodeComparer >::iterator
@@ -419,17 +411,9 @@
             lower_x_(lower_x),
             is_active_(true) {}
 
-        circle_event(const erc_type &c_x,
-                     const erc_type &c_y,
-                     const erc_type &lower_x) :
-            center_x_(c_x),
-            center_y_(c_y),
-            lower_x_(lower_x),
-            is_active_(true) {}
-
         bool operator==(const circle_event &that) const {
-            return (this->lower_x_.compare(that.lower_x_, 128) == UNDEFINED &&
-                    this->center_y_.compare(that.center_y_, 128) == UNDEFINED);
+            return almost_equal(this->lower_x_, that.lower_x_, 128) &&
+                   almost_equal(this->center_y_, that.center_y_, 128);
         }
 
         bool operator!=(const circle_event &that) const {
@@ -440,14 +424,11 @@
         // Each rightmost point has next representation:
         // (lower_x / denom, center_y / denom), denom is always positive.
         bool operator<(const circle_event &that) const {
-            // Compare x-coordinates of the rightmost points. If the result
-            // is undefined we assume that x-coordinates are equal.
-            kPredicateResult pres = this->lower_x_.compare(that.lower_x_, 128);
-            if (pres != UNDEFINED)
-                return (pres == LESS);
-
-            // Compare y-coordinates of the rightmost points.
-            return this->center_y_.compare(that.center_y_, 128) == LESS;
+            if (almost_equal(this->lower_x_, that.lower_x_, 128)) {
+                if (almost_equal(this->center_y_, that.center_y_, 128)) return false;
+                return this->center_y_ < that.center_y_;
+            }
+            return this->lower_x_ < that.lower_x_;
         }
 
         bool operator<=(const circle_event &that) const {
@@ -467,20 +448,17 @@
         // If circle point is less than site point return -1.
         // If circle point is equal to site point return 0.
         // If circle point is greater than site point return 1.
-        kPredicateResult compare(const site_event_type &s_event) const {
-            // Compare x-coordinates.
-            kPredicateResult pres = lower_x_.compare(s_event.x(), 64);
-            // If the comparison result is undefined
-            // x-coordinates are considered to be equal.
-            if (pres != UNDEFINED)
-                return pres;
-            // Compare y-coordinates in case of equal x-coordinates.
-            return center_y_.compare(s_event.y(), 64);
+        kPredicateResult compare(const site_event_type &that) const {
+            if (almost_equal(this->lower_x_, that.x(), 64)) {
+                if (almost_equal(this->center_y_, that.y(), 64)) return UNDEFINED;
+                return this->center_y_ < that.y() ? LESS : MORE;
+            }
+            return this->lower_x_ < that.x() ? LESS : MORE;
         }
 
         // Evaluate x-coordinate of the center of the circle.
         coordinate_type x() const {
-            return center_x_.dif();
+            return center_x_;
         }
 
         void x(coordinate_type center_x) {
@@ -489,7 +467,7 @@
 
         // Evaluate y-coordinate of the center of the circle.
         coordinate_type y() const {
-            return center_y_.dif();
+            return center_y_;
         }
 
         void y(coordinate_type center_y) {
@@ -498,25 +476,13 @@
 
         // Evaluate x-coordinate of the rightmost point of the circle.
         coordinate_type lower_x() const {
-            return lower_x_.dif();
+            return lower_x_;
         }
 
         void lower_x(coordinate_type lower_x) {
             lower_x_ = lower_x;
         }
 
-        point_type center() const {
-            return point_type(x(), y());
-        }
-
-        const erc_type &erc_x() const {
-            return center_x_;
-        }
-
-        const erc_type &erc_y() const {
-            return center_y_;
-        }
-
         // Return iterator to the second bisector from the beach line
         // data structure that forms current circle event.
         const beach_line_iterator &bisector() const {
@@ -536,9 +502,9 @@
         }
 
     private:
-        erc_type center_x_;
-        erc_type center_y_;
-        erc_type lower_x_;
+        coordinate_type center_x_;
+        coordinate_type center_y_;
+        coordinate_type lower_x_;
         beach_line_iterator bisector_node_;
         bool is_active_;
     };
@@ -1513,7 +1479,7 @@
             t += teta / (robust_fpt<T>(8.0) * A);
             t -= A / (robust_fpt<T>(2.0) * teta);
         } else {
-            robust_fpt<T> det = ((teta * teta + denom * denom) * A * B).get_sqrt();
+            robust_fpt<T> det = ((teta * teta + denom * denom) * A * B).sqrt();
             if (segment_index == 2) {
                 t -= det / (denom * denom);
             } else {
@@ -1589,9 +1555,9 @@
             t -= robust_fpt<T>(a1) * robust_fpt<T>((segm_start1.x() + segm_start2.x()) * 0.5 - site1.x());
             t -= robust_fpt<T>(b1) * robust_fpt<T>((segm_start1.y() + segm_start2.y()) * 0.5 - site1.y());
             if (point_index == 2) {
-                t += det.get_sqrt();
+                t += det.sqrt();
             } else {
-                t -= det.get_sqrt();
+                t -= det.sqrt();
             }
             t /= a;
             epsilon_robust_comparator< robust_fpt<T> > c_x, c_y;
@@ -1600,7 +1566,7 @@
             c_y += robust_fpt<T>(0.5 * (segm_start1.y() + segm_start2.y()));
             c_y += robust_fpt<T>(b1) * t;
             epsilon_robust_comparator< robust_fpt<T> > lower_x(c_x);
-            lower_x += robust_fpt<T>(0.5) * c.fabs() / a.get_sqrt();
+            lower_x += robust_fpt<T>(0.5) * c.fabs() / a.sqrt();
             recompute_c_x = c_x.dif().ulp() > 128;
             recompute_c_y = c_y.dif().ulp() > 128;
             recompute_lower_x = lower_x.dif().ulp() > 128;
@@ -1636,9 +1602,9 @@
             b -= sqr_sum2 * robust_fpt<T>(robust_cross_product(a1, b1, -site1.y(), site1.x()), 2.0);
             t -= b;
             if (point_index == 2) {
-                t += det.get_sqrt();
+                t += det.sqrt();
             } else {
-                t -= det.get_sqrt();
+                t -= det.sqrt();
             }
             t /= (a * a);
             epsilon_robust_comparator< robust_fpt<T> > c_x(ix), c_y(iy);
@@ -1686,9 +1652,9 @@
         robust_fpt<T> b3(site3.y1(true) - site3.y0(true), 0.0);
         robust_fpt<T> c3(robust_cross_product(site3.x0(true), site3.y0(true), site3.x1(true), site3.y1(true)), 2.0);
         
-        robust_fpt<T> len1 = (a1 * a1 + b1 * b1).get_sqrt();
-        robust_fpt<T> len2 = (a2 * a2 + b2 * b2).get_sqrt();
-        robust_fpt<T> len3 = (a3 * a3 + b3 * b3).get_sqrt();
+        robust_fpt<T> len1 = (a1 * a1 + b1 * b1).sqrt();
+        robust_fpt<T> len2 = (a2 * a2 + b2 * b2).sqrt();
+        robust_fpt<T> len3 = (a3 * a3 + b3 * b3).sqrt();
         robust_fpt<T> cross_12(robust_cross_product(a1.fpv(), b1.fpv(), a2.fpv(), b2.fpv()), 2.0);
         robust_fpt<T> cross_23(robust_cross_product(a2.fpv(), b2.fpv(), a3.fpv(), b3.fpv()), 2.0);
         robust_fpt<T> cross_31(robust_cross_product(a3.fpv(), b3.fpv(), a1.fpv(), b1.fpv()), 2.0);
@@ -1746,25 +1712,25 @@
     // The one site is considered to be newer than the other in case it was
     // processed by the algorithm later.
     template <typename T>
-    class beach_line_node {
+    class beach_line_node_key {
     public:
         typedef T coordinate_type;
         typedef point_2d<T> point_type;
         typedef site_event<T> site_event_type;
 
-        beach_line_node() {}
+        beach_line_node_key() {}
 
         // 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(const site_event_type &new_site) {
+        explicit beach_line_node_key(const site_event_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(const site_event_type &left_site,
-                        const site_event_type &right_site) {
+        beach_line_node_key(const site_event_type &left_site,
+                            const site_event_type &right_site) {
             left_site_ = left_site;
             right_site_ = right_site;
         }
@@ -1864,7 +1830,7 @@
     template <typename T>
     class beach_line_node_data {
     public:
-        explicit beach_line_node_data(voronoi_edge<T> *new_edge) :
+        explicit beach_line_node_data(void *new_edge) :
             edge_(new_edge),
             contains_circle_event_(false) {}
 
@@ -1879,17 +1845,17 @@
             contains_circle_event_ = false;
         }
 
-        voronoi_edge<T> *edge() const {
+        void *edge() const {
             return edge_;
         }
 
-        void edge(voronoi_edge<T> *new_edge) {
+        void edge(void *new_edge) {
             edge_ = new_edge;
         }
 
     private:
         typename circle_events_queue<T>::circle_event_type_it circle_event_it_;
-        voronoi_edge<T> *edge_;
+        void *edge_;
         bool contains_circle_event_;
     };
 

Modified: sandbox/SOC/2010/sweepline/boost/sweepline/detail/voronoi_fpt_kernel.hpp
==============================================================================
--- sandbox/SOC/2010/sweepline/boost/sweepline/detail/voronoi_fpt_kernel.hpp	(original)
+++ sandbox/SOC/2010/sweepline/boost/sweepline/detail/voronoi_fpt_kernel.hpp	2011-09-13 12:39:35 EDT (Tue, 13 Sep 2011)
@@ -14,6 +14,9 @@
 namespace sweepline {
 namespace detail {
 
+    template <typename T>
+    class epsilon_robust_comparator;
+
     // Represents the result of the epsilon robust predicate.
     // If the result is undefined some further processing is usually required.
     enum kPredicateResult {
@@ -27,10 +30,7 @@
     // sign-magnitude integers. Values are considered to be almost equal if
     // their integer reinterpretatoins differ in not more than maxUlps units.
     template <typename T>
-    bool almost_equal(T a, T b, unsigned int ulps) {
-        if (a < b) return static_cast<unsigned int>(b - a) <= ulps;
-        return static_cast<unsigned int>(a - b) <= ulps;
-    }
+    bool almost_equal(T a, T b, unsigned int ulps);
 
     template<>
     bool almost_equal<float>(float a, float b, unsigned int maxUlps) {
@@ -90,10 +90,10 @@
         return value;
     }
 
-    template <typename _fpt>
+    template <typename FPT>
     class robust_fpt {
     public:
-	    typedef _fpt floating_point_type;
+	    typedef FPT floating_point_type;
             typedef double relative_error_type;
 
             // Rounding error is at most 1 EPS.
@@ -112,39 +112,39 @@
         relative_error_type re() const { return re_; }
         relative_error_type ulp() const { return re_; }
 
-        bool operator==(double that) const {
-            if (that == 0)
-                return this->fpv_ == that;
-            return almost_equal(this->fpv_, that, 
-                                static_cast<unsigned int>(this->ulp()));
+        template <typename T>
+        bool operator==(T that) const {
+            floating_point_type value = static_cast<floating_point_type>(that);
+            return almost_equal(this->fpv_, value, static_cast<unsigned int>(this->ulp()));
         }
 
-        bool operator!=(double that) const {
+        template <typename T>
+        bool operator!=(T that) const {
             return !(*this == that);
         }
 
-        bool operator<(double that) const {
-            if (*this == that)
-                return false;
-            return this->fpv_ < that;
+        template <typename T>
+        bool operator<(T that) const {
+            if (*this == that) return false;
+            return this->fpv_ < static_cast<floating_point_type>(that);
         }
 
-        bool operator<=(double that) const {
-            if (*this == that)
-                return true;
-            return this->fpv_ < that;
+        template <typename T>
+        bool operator<=(T that) const {
+            if (*this == that) return true;
+            return this->fpv_ < static_cast<floating_point_type>(that);
         }
 
-        bool operator>(double that) const {
-            if (*this == that)
-                return false;
-            return this->fpv_ > that;
+        template <typename T>
+        bool operator>(T that) const {
+            if (*this == that) return false;
+            return this->fpv_ > static_cast<floating_point_type>(that);
         }
 
-        bool operator>=(double that) const {
-            if (*this == that)
-                return true;
-            return this->fpv_ > that;
+        template <typename T>
+        bool operator>=(T that) const {
+            if (*this == that) return true;
+            return this->fpv_ > static_cast<floating_point_type>(that);
         }
 
             bool operator==(const robust_fpt &that) const {
@@ -260,7 +260,7 @@
             return robust_fpt(fpv, re);
         }
 
-        robust_fpt get_sqrt() const {
+        robust_fpt sqrt() const {
             return robust_fpt(std::sqrt(fpv_), re_ * 0.5 + ROUNDING_ERROR);
         }
 
@@ -408,12 +408,6 @@
             return (lhs < rhs) ? LESS : MORE;
         }
 
-        // Check whether comparison has undefined result.
-        bool compares_undefined(const epsilon_robust_comparator &rc,
-                                int ulp) const {
-            return this->compare(rc, ulp) == UNDEFINED;
-        }
-
     private:
         T positive_sum_;
         T negative_sum_;
@@ -575,4 +569,4 @@
 } // sweepline
 } // boost
 
-#endif
\ No newline at end of file
+#endif

Added: sandbox/SOC/2010/sweepline/boost/sweepline/voronoi.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2010/sweepline/boost/sweepline/voronoi.hpp	2011-09-13 12:39:35 EDT (Tue, 13 Sep 2011)
@@ -0,0 +1,59 @@
+// Boost sweepline/voronoi.hpp header file
+
+//          Copyright Andrii Sydorchuk 2010.
+// 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_SWEEPLINE_VORONOI
+#define BOOST_SWEEPLINE_VORONOI
+
+#include "boost/polygon/polygon.hpp"
+using namespace boost::polygon;
+
+#include "voronoi_builder.hpp"
+#include "voronoi_diagram.hpp"
+
+namespace boost {
+namespace sweepline {
+    
+    // Public methods to compute voronoi diagram.
+    // points - vector of input points.
+    // segments - vector of input segments.
+    // output - voronoi output data structure to hold voronoi diagram.
+    // The assumption is made that input doesn't contain segments that
+    // intersect or points lying on the segments. Also coordinates of
+    // the points and of the endpoints of the segments should be within
+    // signed integer range [-2^31, 2^31-1].
+    // Complexity - O(N*logN), memory usage - O(N), where N is the total
+    // number of points and segments.
+    template <typename T, typename PC, typename VD>
+    static inline void construct_voronoi_points(const PC &points, VD &output) {
+        voronoi_builder<T, VD> builder;
+        builder.insert_points(points.begin(), points.end());
+        builder.construct(output);
+        builder.clear();
+    }
+
+    template <typename T, typename SC, typename VD>
+    static inline void construct_voronoi_segments(const SC &segments, VD &output) {
+        voronoi_builder<T, VD> builder;
+        builder.insert_segments(segments.begin(), segments.end());
+        builder.construct(output);
+        builder.clear();
+    }
+
+    template <typename T, typename PC, typename SC, typename VD>
+    static inline void construct_voronoi(const PC &points, const SC &segments, VD &output) {
+        voronoi_builder<T, VD> builder;
+        builder.insert_sites(points.begin(), points.end(), segments.begin(), segments.end());
+        builder.construct(output);
+        builder.clear();
+    }
+
+}
+}
+
+#endif

Added: sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_builder.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_builder.hpp	2011-09-13 12:39:35 EDT (Tue, 13 Sep 2011)
@@ -0,0 +1,581 @@
+// Boost sweepline/voronoi_builder.hpp header file
+
+//          Copyright Andrii Sydorchuk 2010.
+// 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_SWEEPLINE_VORONOI_BUILDER
+#define BOOST_SWEEPLINE_VORONOI_BUILDER
+
+#include <algorithm>
+#include <cmath>
+#include <cstring>
+#include <list>
+#include <map>
+#include <queue>
+#include <vector>
+
+#pragma warning(disable:4800)
+#include <gmpxx.h>
+
+#include "boost/polygon/polygon.hpp"
+using namespace boost::polygon;
+
+#include "detail/mpt_wrapper.hpp"
+#include "detail/voronoi_fpt_kernel.hpp"
+#include "detail/voronoi_formation.hpp"
+
+namespace boost {
+namespace sweepline {
+
+    ///////////////////////////////////////////////////////////////////////////
+    // VORONOI TRAITS /////////////////////////////////////////////////////////
+    ///////////////////////////////////////////////////////////////////////////
+    
+    template <typename T>
+    struct voronoi_traits;
+
+    template <>
+    struct voronoi_traits<int> {
+        typedef double coordinate_type;
+    };
+
+    ///////////////////////////////////////////////////////////////////////////
+    // VORONOI BUILDER ////////////////////////////////////////////////////////
+    ///////////////////////////////////////////////////////////////////////////
+
+    // The sweepline algorithm implementation to compute voronoi diagram of
+    // input data sets of points and segments (Fortune's algorithm).
+    // Complexity - O(N*logN), memory usage - O(N), where N is the total
+    // number of input objects.
+    // Sweepline is a vertical line that sweeps from the left to the right
+    // along the x-axis positive direction. Each of the input objects is
+    // wrapped into the site event. Each event is characterized by its
+    // coordinates: the point site is defined by the point itself,
+    // the segment site is defined by its startpoint. At any moment we
+    // consider only the sites that lie to the left of the sweepline. Beach
+    // line is a curve formed by the parabolic arcs and line segments, that
+    // consists of the points equidistant from the sweepline and the nearest
+    // site to the left of the sweepline. The part of the generated diagram to
+    // the left of the beach line remains unchanged until the end of the
+    // algorithm. Each node in the beach line corresponds to some voronoi edge.
+    // Each node is represented by two sites. Two neighboring nodes has a
+    // common site. Circle event appears at the rightmost point of the circle
+    // tangent to the three sites that correspond to the two consecutive
+    // bisectors. At each step algorithm goes over the leftmost event
+    // and processes it appropriately. This is made until there are no events.
+    // At the end output data structure holds the voronoi diagram of the
+    // initial set of objects.
+    // Each point creates one site event. Each segment creates three site
+    // events: two for its endpoints and one for the segment itself (this is
+    // made to simplify output construction). All the site events are
+    // constructed at the algorithm initialization step. After that they
+    // are ordered using quicksort algorithm.
+    // Priority queue is used to dynamically hold circle events. At each step
+    // of the algorithm the leftmost event is retrieved by comparing the
+    // current site event and the topmost element from the circle event queue.
+    // Standard map container was chosen to hold state of the beach line. The
+    // keys of the map correspond to the bisectors and values to the
+    // corresponding edges from the output data structure. Specially defined
+    // comparison functor is used to make the beach line correctly ordered.
+    // Epsilon-based and high-precision approaches are used to guarantee
+    // efficiency and robustness of the algorithm implementation.
+    // Member data: 1) site_events_ - vector of the site events;
+    //              2) site_event_iterator_ - iterator to the next
+    //                 site event;
+    //              3) circle_events_ - priority queue of circle events,
+    //                 allows to retrieve topmost event in O(logN) time;
+    //              4) beach_line_ - contains current state of the beach line;
+    //              5) end_points_ - maps endpoints of the segment sites with
+    //                 temporary nodes from the beach line. While sweepline
+    //                 sweeps over the second endpoint of the segments
+    //                 temporary nodes are being removed;
+    //              6) output_ - contains voronoi diagram itself.
+    template <typename T, typename VD>
+    class voronoi_builder {
+    public:
+        typedef typename voronoi_traits<T>::coordinate_type coordinate_type;
+        typedef VD output_type;
+
+        voronoi_builder() {}
+
+        template <typename PointIterator>
+        void insert_points(PointIterator first_point, PointIterator last_point) {
+            // Create a site event from each input point.
+            for (PointIterator it = first_point; it != last_point; ++it) {
+                site_events_.push_back(detail::make_site_event(
+                    static_cast<coordinate_type>(it->x()),
+                    static_cast<coordinate_type>(it->y()), 0));
+            }
+        }
+
+        template <typename SegmentIterator>
+        void insert_segments(SegmentIterator first_segment, SegmentIterator last_segment) {
+            // Each segment creates three segment sites:
+            //   1) the startpoint of the segment;
+            //   2) the endpoint of the segment;
+            //   3) the segment itself.
+            for (SegmentIterator it = first_segment; it != last_segment; ++it) {
+                coordinate_type x1 = static_cast<coordinate_type>(it->low().x());
+                coordinate_type y1 = static_cast<coordinate_type>(it->low().y());
+                coordinate_type x2 = static_cast<coordinate_type>(it->high().x());
+                coordinate_type y2 = static_cast<coordinate_type>(it->high().y());
+                site_events_.push_back(detail::make_site_event(x1, y1, 0));
+                site_events_.push_back(detail::make_site_event(x2, y2, 0));
+                site_events_.push_back(detail::make_site_event(x1, y1, x2, y2, 0));
+            }
+        }
+
+        template <typename PointIterator, typename SegmentIterator>
+        void insert_sites(PointIterator first_point, PointIterator last_point,
+                          SegmentIterator first_segment, SegmentIterator last_segment) {
+            insert_points(first_point, last_point);
+            insert_segments(first_segment, last_segment);
+        }
+
+        // Run the sweepline algorithm.
+        void construct(output_type &output) {
+            // Init structures.
+            output_ = &output;
+            output_->clear();
+            output_->reserve(site_events_.size());
+            init_sites_queue();
+            init_beach_line();
+
+            // The algorithm stops when there are no events to process.
+            // The circle events with the same rightmost point as the next
+            // site event go first.
+            while (!circle_events_.empty() ||
+                   !(site_event_iterator_ == site_events_.end())) {
+                if (circle_events_.empty()) {
+                    process_site_event();
+                } else if (site_event_iterator_ == site_events_.end()) {
+                    process_circle_event();
+                } else {
+                    if (circle_events_.top().compare(*site_event_iterator_) == detail::MORE) {
+                        process_site_event();
+                    } else {
+                        process_circle_event();
+                    }
+                }
+            }
+
+            beach_line_.clear();
+
+            // Clean the output (remove zero-length edges).
+            output_->clean();
+        }
+
+        void clear() {
+            site_events_.clear();
+        }
+
+    private:
+        typedef detail::point_2d<coordinate_type> point_type;
+        typedef detail::site_event<coordinate_type> site_event_type;
+        typedef detail::circle_event<coordinate_type> circle_event_type;
+        typedef typename std::vector<site_event_type>::const_iterator
+            site_event_iterator_type;
+        typedef typename output_type::voronoi_edge_type edge_type;
+        typedef detail::circle_events_queue<coordinate_type> circle_event_queue_type;
+        typedef detail::beach_line_node_key<coordinate_type> key_type;
+        typedef detail::beach_line_node_data<coordinate_type> value_type;
+        typedef detail::node_comparer<key_type> node_comparer_type;
+        typedef std::map< key_type, value_type, node_comparer_type >
+            beach_line_type;
+        typedef typename beach_line_type::iterator beach_line_iterator;
+        typedef std::pair<point_type, beach_line_iterator> end_point_type;
+
+        // Create site events.
+        // There will be one site event for each input point and three site
+        // events for each input segment (both endpoints of a segment and the
+        // segment itself).
+        void init_sites_queue() {
+            // Sort the site events.
+            sort(site_events_.begin(), site_events_.end());
+
+            // Remove duplicates.
+            site_events_.erase(unique(
+                site_events_.begin(), site_events_.end()), site_events_.end());
+
+            // Number the sites.
+            for (size_t cur = 0; cur < site_events_.size(); ++cur)
+                site_events_[cur].index(cur);
+
+            // Init the site's iterator.
+            site_event_iterator_ = site_events_.begin();
+        }
+
+        void init_beach_line() {
+            if (site_events_.empty()) return;
+            if (site_events_.size() == 1) {
+                // Handle one input site case.
+                output_->process_single_site(site_events_[0]);
+                ++site_event_iterator_;
+            } else {
+                int skip = 0;
+
+                // Count the number of the sites to init the beach line.
+                while(site_event_iterator_ != site_events_.end() &&
+                      site_event_iterator_->x() == site_events_.begin()->x() &&
+                      site_event_iterator_->is_vertical()) {
+                    ++site_event_iterator_;
+                    ++skip;
+                }
+
+                if (skip == 1) {
+                    // Init the beach line with the two first sites.
+                    init_beach_line_default();
+                } else {
+                    // Init the beach line with the sites situated on the same
+                    // vertical line. This could be a set of point and vertical
+                    // segment sites.
+                    init_beach_line_collinear_sites();
+                }
+            }
+        }
+
+        // Init the beach line with the two first sites.
+        // The first site is always a point.
+        void init_beach_line_default() {
+            // Get the first and the second site events.
+            site_event_iterator_type it_first = site_events_.begin();
+            site_event_iterator_type it_second = site_events_.begin();
+            ++it_second;
+
+            // Update the beach line.
+            insert_new_arc(*it_first, *it_first, *it_second, beach_line_.begin());
+
+            // The second site has been already processed.
+            // Move the site's iterator.
+            ++site_event_iterator_;
+        }
+
+        // Insert bisectors for all collinear initial sites.
+        void init_beach_line_collinear_sites() {
+             site_event_iterator_type it_first = site_events_.begin();
+             site_event_iterator_type it_second = site_events_.begin();
+             ++it_second;
+             while (it_second != site_event_iterator_) {
+                 // Create a new beach line node.
+                 key_type new_node(*it_first, *it_second);
+
+                 // Update the output.
+                 edge_type *edge = output_->insert_new_edge(*it_first, *it_second);
+
+                 // Insert a new bisector into the beach line.
+                 beach_line_.insert(
+                     std::pair<key_type, value_type>(new_node, value_type(edge)));
+
+                 // Update iterators.
+                 ++it_first;
+                 ++it_second;
+             }
+        }
+
+        // Process a single site.
+        void process_site_event() {
+            // Get the site event to process.
+            site_event_type site_event = *site_event_iterator_;
+
+            // Move the site's iterator.
+            site_event_iterator_type last = site_event_iterator_ + 1;
+
+            // If a new site is an end point of some segment,
+            // remove temporary nodes from the beach line data structure.
+            if (!site_event.is_segment()) {
+                while (!end_points_.empty() &&
+                       end_points_.top().first == site_event.point0()) {
+                    beach_line_.erase(end_points_.top().second);
+                    end_points_.pop();
+                }
+            } else {
+                while (last != site_events_.end() &&
+                       last->is_segment() && last->point0() == site_event.point0())
+                    last++;
+            }
+
+            for (; site_event_iterator_ != last; ++site_event_iterator_) {
+                site_event = *site_event_iterator_;
+                // Create degenerate node.
+                key_type new_key(site_event);
+
+                // Find the node in the binary search tree with left arc
+                // lying above the new site point.
+                beach_line_iterator it = beach_line_.lower_bound(new_key);
+                int it_dist = site_event.is_segment() ? 2 : 1;
+
+                // Do further processing depending on the above node position.
+                // For any two neighbouring nodes the second site of the first node
+                // is the same as the first site of the second arc.
+                if (it == beach_line_.end()) {
+                    // The above arc corresponds to the second arc of the last node.
+                    // Move the iterator to the last node.
+                    --it;
+
+                    // Get the second site of the last node
+                    const site_event_type &site_arc = it->first.right_site();
+
+                    // Insert new nodes into the beach line. Update the output.
+                    beach_line_iterator new_node_it =
+                        insert_new_arc(site_arc, site_arc, site_event, it);
+
+                    // Add a candidate circle to the circle event queue.
+                    // There could be only one new circle event formed by
+                    // a new bisector and the one on the left.
+                    std::advance(new_node_it, -it_dist);
+                    activate_circle_event(it->first.left_site(),
+                                          it->first.right_site(),
+                                          site_event, new_node_it);
+                } else if (it == beach_line_.begin()) {
+                    // The above arc corresponds to the first site of the first node.
+                    const site_event_type &site_arc = it->first.left_site();
+
+                    // Insert new nodes into the beach line. Update the output.
+                    insert_new_arc(site_arc, site_arc, site_event, it);
+
+                    // If the site event is a segment, update its direction.
+                    if (site_event.is_segment()) {
+                        site_event.inverse();
+                    }
+
+                    // Add a candidate circle to the circle event queue.
+                    // There could be only one new circle event formed by
+                    // a new bisector and the one on the right.
+                    activate_circle_event(site_event, it->first.left_site(),
+                                          it->first.right_site(), it);
+                } else {
+                    // The above arc corresponds neither to the first,
+                    // nor to the last site in the beach line.
+                    const site_event_type &site_arc2 = it->first.left_site();
+                    const site_event_type &site3 = it->first.right_site();
+
+                    // Remove the candidate circle from the event queue.
+                    it->second.deactivate_circle_event();
+                    --it;
+                    const site_event_type &site_arc1 = it->first.right_site();
+                    const site_event_type &site1 = it->first.left_site();
+
+                    // Insert new nodes into the beach line. Update the output.
+                    beach_line_iterator new_node_it =
+                        insert_new_arc(site_arc1, site_arc2, site_event, it);
+
+                    // Add candidate circles to the circle event queue.
+                    // There could be up to two circle events formed by
+                    // a new bisector and the one on the left or right.
+                    std::advance(new_node_it, -it_dist);
+                    activate_circle_event(site1, site_arc1, site_event,
+                                          new_node_it);
+
+                    // If the site event is a segment, update its direction.
+                    if (site_event.is_segment()) {
+                        site_event.inverse();
+                    }
+                    std::advance(new_node_it, it_dist + 1);
+                    activate_circle_event(site_event, site_arc2, site3,
+                                          new_node_it);
+                }
+            }
+        }
+
+        // Process a single circle event.
+        // In general case circle event is made of the three consequtive sites
+        // that form two bisector nodes in the beach line data structure.
+        // Let circle event sites be A, B, C, two bisectors that define
+        // circle event be (A, B), (B, C). During circle event processing
+        // we remove (A, B), (B, C) and insert (A, C). As beach line comparer
+        // works correctly only if one of the nodes is a new one we remove
+        // (B, C) bisector and change (A, B) bisector to the (A, C). That's
+        // why we use const_cast there and take all the responsibility that
+        // map data structure keeps correct ordering.
+        void process_circle_event() {
+            // Get the topmost circle event.
+            const circle_event_type &circle_event = circle_events_.top();
+            beach_line_iterator it_first = circle_event.bisector();
+            beach_line_iterator it_last = it_first;
+
+            // Get the C site.
+            site_event_type site3 = it_first->first.right_site();
+
+            // Get the half-edge corresponding to the second bisector - (B, C).
+            edge_type *bisector2 = static_cast<edge_type *>(it_first->second.edge());
+
+            // Get the half-edge corresponding to the first bisector - (A, B).
+            --it_first;
+            edge_type *bisector1 = static_cast<edge_type *>(it_first->second.edge());
+
+            // Get the A site.
+            site_event_type site1 = it_first->first.left_site();
+
+            if (!site1.is_segment() && site3.is_segment() &&
+                site3.point1(true) == site1.point0()) {
+                site3.inverse();
+            }
+
+            // Change the (A, B) bisector node to the (A, C) bisector node.
+            const_cast<key_type &>(it_first->first).right_site(site3);
+
+            // Insert the new bisector into the beach line.
+            it_first->second.edge(output_->insert_new_edge(site1, site3, circle_event,
+                                                           bisector1, bisector2));
+
+            // Remove the (B, C) bisector node from the beach line.
+            beach_line_.erase(it_last);
+            it_last = it_first;
+
+            // Pop the topmost circle event from the event queue.
+            circle_events_.pop();
+
+            // Check new triplets formed by the neighboring arcs
+            // to the left for potential circle events.
+            if (it_first != beach_line_.begin()) {
+                it_first->second.deactivate_circle_event();
+                --it_first;
+                const site_event_type &site_l1 = it_first->first.left_site();
+                activate_circle_event(site_l1, site1, site3, it_last);
+            }
+
+            // Check the new triplet formed by the neighboring arcs
+            // to the right for potential circle events.
+            ++it_last;
+            if (it_last != beach_line_.end()) {
+                it_last->second.deactivate_circle_event();
+                const site_event_type &site_r1 = it_last->first.right_site();
+                activate_circle_event(site1, site3, site_r1, it_last);
+            }
+        }
+
+        // Insert new nodes into the beach line. Update the output.
+        beach_line_iterator insert_new_arc(const site_event_type &site_arc1,
+                                           const site_event_type &site_arc2,
+                                           const site_event_type &site_event,
+                                           const beach_line_iterator &position) {
+            // Create two new bisectors with opposite directions.
+            key_type new_left_node(site_arc1, site_event);
+            key_type new_right_node(site_event, site_arc2);
+
+            // Set correct orientation for the first site of the second node.
+            if (site_event.is_segment()) {
+                new_right_node.inverse_left_site();
+            }
+
+            // Update the output.
+            edge_type *edge = output_->insert_new_edge(site_arc2, site_event);
+
+            // Update the beach line with the (site_arc1, site_event) bisector.
+            beach_line_iterator it = beach_line_.insert(position,
+                typename beach_line_type::value_type(new_right_node, value_type(edge->twin())));
+
+            if (site_event.is_segment()) {
+                // Update the beach line with temporary bisector, that will
+                // disappear after processing site event going through the
+                // endpoint of the segment site.
+                key_type new_node(site_event, site_event);
+                new_node.inverse_right_site();
+                beach_line_iterator temp_it = beach_line_.insert(position,
+                    typename beach_line_type::value_type(new_node, value_type(NULL)));
+
+                // Update the data structure that holds temporary bisectors.
+                end_points_.push(std::make_pair(site_event.point1(), temp_it));
+            }
+
+            // Update the beach line with the (site_event, site_arc2) bisector.
+            beach_line_.insert(position,
+                typename beach_line_type::value_type(new_left_node, value_type(edge)));
+            return it;
+        }
+
+        // Create a circle event from the given three sites.
+        // Returns true if the circle event exists, else false.
+        // If exists circle event is saved into the c_event variable.
+        bool create_circle_event(const site_event_type &site1,
+                                 const site_event_type &site2,
+                                 const site_event_type &site3,
+                                 circle_event_type &c_event) const {
+            if (!site1.is_segment()) {
+                if (!site2.is_segment()) {
+                    if (!site3.is_segment()) {
+                        // (point, point, point) sites.
+                        return create_circle_event_ppp(site1, site2, site3, c_event);
+                    } else {
+                        // (point, point, segment) sites.
+                        return create_circle_event_pps(site1, site2, site3, 3, c_event);
+                    }
+                } else {
+                    if (!site3.is_segment()) {
+                        // (point, segment, point) sites.
+                        return create_circle_event_pps(site1, site3, site2, 2, c_event);
+                    } else {
+                        // (point, segment, segment) sites.
+                        return create_circle_event_pss(site1, site2, site3, 1, c_event);
+                    }
+                }
+            } else {
+                if (!site2.is_segment()) {
+                    if (!site3.is_segment()) {
+                        // (segment, point, point) sites.
+                        return create_circle_event_pps(site2, site3, site1, 1, c_event);
+                    } else {
+                        // (segment, point, segment) sites.
+                        return create_circle_event_pss(site2, site1, site3, 2, c_event);
+                    }
+                } else {
+                    if (!site3.is_segment()) {
+                        // (segment, segment, point) sites.
+                        return create_circle_event_pss(site3, site1, site2, 3, c_event);
+                    } else {
+                        // (segment, segment, segment) sites.
+                        return create_circle_event_sss(site1, site2, site3, c_event);
+                    }
+                }
+            }
+        }
+
+        // Add a new circle event to the event queue.
+        // bisector_node corresponds to the (site2, site3) bisector.
+        void activate_circle_event(const site_event_type &site1,
+                                   const site_event_type &site2,
+                                   const site_event_type &site3,
+                                   beach_line_iterator bisector_node) {
+            circle_event_type c_event;
+            // Check if the three input sites create a circle event.
+            if (create_circle_event(site1, site2, site3, c_event)) {
+                // Update circle event's bisector iterator to point to the
+                // second bisector that forms it in the beach line.
+                c_event.bisector(bisector_node);
+
+                // Add the new circle event to the circle events queue.
+                // Update bisector's circle event iterator to point to the
+                // new circle event in the circle event queue.
+                bisector_node->second.activate_circle_event(
+                    circle_events_.push(c_event));
+            }
+        }
+
+    private:
+        struct end_point_comparison {
+            bool operator() (const end_point_type &end1, const end_point_type &end2) const {
+                return end1.first > end2.first;
+            }
+        };
+
+        std::vector<site_event_type> site_events_;
+        site_event_iterator_type site_event_iterator_;
+        std::priority_queue< end_point_type, std::vector<end_point_type>,
+                             end_point_comparison > end_points_;
+        circle_event_queue_type circle_events_;
+        beach_line_type beach_line_;
+        output_type *output_;
+
+        //Disallow copy constructor and operator=
+        voronoi_builder(const voronoi_builder&);
+        void operator=(const voronoi_builder&);
+    };
+
+} // sweepline
+} // boost
+
+#endif

Modified: sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_diagram.hpp
==============================================================================
--- sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_diagram.hpp	(original)
+++ sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_diagram.hpp	2011-09-13 12:39:35 EDT (Tue, 13 Sep 2011)
@@ -10,25 +10,14 @@
 #ifndef BOOST_SWEEPLINE_VORONOI_DIAGRAM
 #define BOOST_SWEEPLINE_VORONOI_DIAGRAM
 
-#include <algorithm>
 #include <cmath>
-#include <cstring>
 #include <list>
-#include <map>
-#include <queue>
 #include <stack>
 #include <vector>
 
-#pragma warning(disable:4800)
-#include <gmpxx.h>
-
 #include "boost/polygon/polygon.hpp"
 using namespace boost::polygon;
 
-#include "detail/mpt_wrapper.hpp"
-#include "detail/voronoi_fpt_kernel.hpp"
-#include "detail/voronoi_formation.hpp"
-
 namespace boost {
 namespace sweepline {
 
@@ -43,9 +32,6 @@
     template <typename T>
     class voronoi_edge;
 
-    template <typename T>
-    class voronoi_output;
-
     // Bounding rectangle data structure. Contains coordinates
     // of the bottom left and the upper right points of the rectangle.
     template <typename T>
@@ -732,12 +718,10 @@
     //        to the new vector as removing elements from a vector takes O(n)
     //        time.
     template <typename T>
-    class voronoi_output {
+    class voronoi_diagram {
     public:
         typedef T coordinate_type;
         typedef point_data<coordinate_type> point_type;
-        typedef detail::site_event<coordinate_type> site_event_type;
-        typedef detail::circle_event<coordinate_type> circle_event_type;
 
         typedef voronoi_cell<coordinate_type> voronoi_cell_type;
         typedef std::vector<voronoi_cell_type> voronoi_cells_type;
@@ -760,7 +744,7 @@
         typedef typename voronoi_edges_type::const_iterator
             voronoi_edge_const_iterator_type;
 
-        voronoi_output() :
+        voronoi_diagram() :
             num_cell_records_(0),
             num_edge_records_(0),
             num_vertex_records_(0) {}
@@ -814,7 +798,8 @@
         }
 
         // Update the voronoi output in case of a single point input.
-        void process_single_site(const site_event_type &site) {
+        template <typename SEvent>
+        void process_single_site(const SEvent &site) {
             // Update bounding rectangle.
             voronoi_rect_ = BRect<coordinate_type>(site.point0());
 
@@ -828,8 +813,8 @@
         // Insert a new half-edge into the output data structure.
         // Takes as input left and right sites that form a new bisector.
         // Returns a pointer to a new half-edge.
-        voronoi_edge_type *insert_new_edge(const site_event_type &site1,
-                                           const site_event_type &site2) {
+        template <typename SEvent>
+        voronoi_edge_type *insert_new_edge(const SEvent &site1, const SEvent &site2) {
             // Get sites' indices.
             int site_index1 = site1.index();
             int site_index2 = site2.index();
@@ -885,14 +870,15 @@
         // that correponds 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 pointer to the new half-edge.
-        voronoi_edge_type *insert_new_edge(const site_event_type &site1,
-                                           const site_event_type &site3,
-                                           const circle_event_type &circle,
+        template <typename SEvent, typename CEvent>
+        voronoi_edge_type *insert_new_edge(const SEvent &site1,
+                                           const SEvent &site3,
+                                           const CEvent &circle,
                                            voronoi_edge_type *edge12,
                                            voronoi_edge_type *edge23) {
             // Add a new voronoi vertex.
             vertex_records_.push_back(voronoi_vertex_type(
-                point_type(circle.erc_x().dif(), circle.erc_y().dif()), edge12));
+                point_type(circle.x(), circle.y()), edge12));
             voronoi_vertex_type &new_vertex = vertex_records_.back();
 
             // Update vertex pointers of the old edges.
@@ -1137,589 +1123,10 @@
         BRect<coordinate_type> voronoi_rect_;
 
         // Disallow copy constructor and operator=
-        voronoi_output(const voronoi_output&);
-        void operator=(const voronoi_output&);
-    };
-
-    ///////////////////////////////////////////////////////////////////////////
-    // VORONOI TRAITS /////////////////////////////////////////////////////////
-    ///////////////////////////////////////////////////////////////////////////
-    
-    template <typename T>
-    struct voronoi_traits;
-
-    template <>
-    struct voronoi_traits<int> {
-        typedef double coordinate_type;
-    };
-
-    ///////////////////////////////////////////////////////////////////////////
-    // VORONOI BUILDER ////////////////////////////////////////////////////////
-    ///////////////////////////////////////////////////////////////////////////
-
-    // The sweepline algorithm implementation to compute voronoi diagram of
-    // input data sets of points and segments (Fortune's algorithm).
-    // Complexity - O(N*logN), memory usage - O(N), where N is the total
-    // number of input objects.
-    // Sweepline is a vertical line that sweeps from the left to the right
-    // along the x-axis positive direction. Each of the input objects is
-    // wrapped into the site event. Each event is characterized by its
-    // coordinates: the point site is defined by the point itself,
-    // the segment site is defined by its startpoint. At any moment we
-    // consider only the sites that lie to the left of the sweepline. Beach
-    // line is a curve formed by the parabolic arcs and line segments, that
-    // consists of the points equidistant from the sweepline and the nearest
-    // site to the left of the sweepline. The part of the generated diagram to
-    // the left of the beach line remains unchanged until the end of the
-    // algorithm. Each node in the beach line corresponds to some voronoi edge.
-    // Each node is represented by two sites. Two neighboring nodes has a
-    // common site. Circle event appears at the rightmost point of the circle
-    // tangent to the three sites that correspond to the two consecutive
-    // bisectors. At each step algorithm goes over the leftmost event
-    // and processes it appropriately. This is made until there are no events.
-    // At the end output data structure holds the voronoi diagram of the
-    // initial set of objects.
-    // Each point creates one site event. Each segment creates three site
-    // events: two for its endpoints and one for the segment itself (this is
-    // made to simplify output construction). All the site events are
-    // constructed at the algorithm initialization step. After that they
-    // are ordered using quicksort algorithm.
-    // Priority queue is used to dynamically hold circle events. At each step
-    // of the algorithm the leftmost event is retrieved by comparing the
-    // current site event and the topmost element from the circle event queue.
-    // Standard map container was chosen to hold state of the beach line. The
-    // keys of the map correspond to the bisectors and values to the
-    // corresponding edges from the output data structure. Specially defined
-    // comparison functor is used to make the beach line correctly ordered.
-    // Epsilon-based and high-precision approaches are used to guarantee
-    // efficiency and robustness of the algorithm implementation.
-    // Member data: 1) site_events_ - vector of the site events;
-    //              2) site_event_iterator_ - iterator to the next
-    //                 site event;
-    //              3) circle_events_ - priority queue of circle events,
-    //                 allows to retrieve topmost event in O(logN) time;
-    //              4) beach_line_ - contains current state of the beach line;
-    //              5) end_points_ - maps endpoints of the segment sites with
-    //                 temporary nodes from the beach line. While sweepline
-    //                 sweeps over the second endpoint of the segments
-    //                 temporary nodes are being removed;
-    //              6) output_ - contains voronoi diagram itself.
-    template <typename T, typename VD>
-    class voronoi_builder {
-    public:
-        typedef typename voronoi_traits<T>::coordinate_type coordinate_type;
-        typedef VD output_type;
-
-        voronoi_builder() {}
-
-        template <typename PointIterator>
-        void insert_points(PointIterator first_point, PointIterator last_point) {
-            // Create a site event from each input point.
-            for (PointIterator it = first_point; it != last_point; ++it) {
-                site_events_.push_back(detail::make_site_event(
-                    static_cast<coordinate_type>(it->x()),
-                    static_cast<coordinate_type>(it->y()), 0));
-            }
-        }
-
-        template <typename SegmentIterator>
-        void insert_segments(SegmentIterator first_segment, SegmentIterator last_segment) {
-            // Each segment creates three segment sites:
-            //   1) the startpoint of the segment;
-            //   2) the endpoint of the segment;
-            //   3) the segment itself.
-            for (SegmentIterator it = first_segment; it != last_segment; ++it) {
-                coordinate_type x1 = static_cast<coordinate_type>(it->low().x());
-                coordinate_type y1 = static_cast<coordinate_type>(it->low().y());
-                coordinate_type x2 = static_cast<coordinate_type>(it->high().x());
-                coordinate_type y2 = static_cast<coordinate_type>(it->high().y());
-                site_events_.push_back(detail::make_site_event(x1, y1, 0));
-                site_events_.push_back(detail::make_site_event(x2, y2, 0));
-                site_events_.push_back(detail::make_site_event(x1, y1, x2, y2, 0));
-            }
-        }
-
-        template <typename PointIterator, typename SegmentIterator>
-        void insert_sites(PointIterator first_point, PointIterator last_point,
-                          SegmentIterator first_segment, SegmentIterator last_segment) {
-            insert_points(first_point, last_point);
-            insert_segments(first_segment, last_segment);
-        }
-
-        // Run the sweepline algorithm.
-        void construct(output_type &output) {
-            // Init structures.
-            output_ = &output;
-            output_->clear();
-            output_->reserve(site_events_.size());
-            init_sites_queue();
-            init_beach_line();
-
-            // The algorithm stops when there are no events to process.
-            // The circle events with the same rightmost point as the next
-            // site event go first.
-            while (!circle_events_.empty() ||
-                   !(site_event_iterator_ == site_events_.end())) {
-                if (circle_events_.empty()) {
-                    process_site_event();
-                } else if (site_event_iterator_ == site_events_.end()) {
-                    process_circle_event();
-                } else {
-                    if (circle_events_.top().compare(*site_event_iterator_) == detail::MORE) {
-                        process_site_event();
-                    } else {
-                        process_circle_event();
-                    }
-                }
-            }
-
-            beach_line_.clear();
-
-            // Clean the output (remove zero-length edges).
-            output_->clean();
-        }
-
-        void clear() {
-            site_events_.clear();
-        }
-
-    private:
-        typedef detail::point_2d<coordinate_type> point_type;
-        typedef detail::site_event<coordinate_type> site_event_type;
-        typedef detail::circle_event<coordinate_type> circle_event_type;
-        typedef typename std::vector<site_event_type>::const_iterator
-            site_event_iterator_type;
-        typedef typename output_type::voronoi_edge_type edge_type;
-        typedef detail::circle_events_queue<coordinate_type> circle_event_queue_type;
-        typedef detail::beach_line_node<coordinate_type> key_type;
-        typedef detail::beach_line_node_data<coordinate_type> value_type;
-        typedef detail::node_comparer<key_type> node_comparer_type;
-        typedef std::map< key_type, value_type, node_comparer_type >
-            beach_line_type;
-        typedef typename beach_line_type::iterator beach_line_iterator;
-        typedef std::pair<point_type, beach_line_iterator> end_point_type;
-
-        // Create site events.
-        // There will be one site event for each input point and three site
-        // events for each input segment (both endpoints of a segment and the
-        // segment itself).
-        void init_sites_queue() {
-            // Sort the site events.
-            sort(site_events_.begin(), site_events_.end());
-
-            // Remove duplicates.
-            site_events_.erase(unique(
-                site_events_.begin(), site_events_.end()), site_events_.end());
-
-            // Number the sites.
-            for (size_t cur = 0; cur < site_events_.size(); ++cur)
-                site_events_[cur].index(cur);
-
-            // Init the site's iterator.
-            site_event_iterator_ = site_events_.begin();
-        }
-
-        void init_beach_line() {
-            if (site_events_.empty()) return;
-            if (site_events_.size() == 1) {
-                // Handle one input site case.
-                output_->process_single_site(site_events_[0]);
-                ++site_event_iterator_;
-            } else {
-                int skip = 0;
-
-                // Count the number of the sites to init the beach line.
-                while(site_event_iterator_ != site_events_.end() &&
-                      site_event_iterator_->x() == site_events_.begin()->x() &&
-                      site_event_iterator_->is_vertical()) {
-                    ++site_event_iterator_;
-                    ++skip;
-                }
-
-                if (skip == 1) {
-                    // Init the beach line with the two first sites.
-                    init_beach_line_default();
-                } else {
-                    // Init the beach line with the sites situated on the same
-                    // vertical line. This could be a set of point and vertical
-                    // segment sites.
-                    init_beach_line_collinear_sites();
-                }
-            }
-        }
-
-        // Init the beach line with the two first sites.
-        // The first site is always a point.
-        void init_beach_line_default() {
-            // Get the first and the second site events.
-            site_event_iterator_type it_first = site_events_.begin();
-            site_event_iterator_type it_second = site_events_.begin();
-            ++it_second;
-
-            // Update the beach line.
-            insert_new_arc(*it_first, *it_first, *it_second, beach_line_.begin());
-
-            // The second site has been already processed.
-            // Move the site's iterator.
-            ++site_event_iterator_;
-        }
-
-        // Insert bisectors for all collinear initial sites.
-        void init_beach_line_collinear_sites() {
-             site_event_iterator_type it_first = site_events_.begin();
-             site_event_iterator_type it_second = site_events_.begin();
-             ++it_second;
-             while (it_second != site_event_iterator_) {
-                 // Create a new beach line node.
-                 key_type new_node(*it_first, *it_second);
-
-                 // Update the output.
-                 edge_type *edge = output_->insert_new_edge(*it_first, *it_second);
-
-                 // Insert a new bisector into the beach line.
-                 beach_line_.insert(
-                     std::pair<key_type, value_type>(new_node, value_type(edge)));
-
-                 // Update iterators.
-                 ++it_first;
-                 ++it_second;
-             }
-        }
-
-        // Process a single site.
-        void process_site_event() {
-            // Get the site event to process.
-            site_event_type site_event = *site_event_iterator_;
-
-            // Move the site's iterator.
-            site_event_iterator_type last = site_event_iterator_ + 1;
-
-            // If a new site is an end point of some segment,
-            // remove temporary nodes from the beach line data structure.
-            if (!site_event.is_segment()) {
-                while (!end_points_.empty() &&
-                       end_points_.top().first == site_event.point0()) {
-                    beach_line_.erase(end_points_.top().second);
-                    end_points_.pop();
-                }
-            } else {
-                while (last != site_events_.end() &&
-                       last->is_segment() && last->point0() == site_event.point0())
-                    last++;
-            }
-
-            for (; site_event_iterator_ != last; ++site_event_iterator_) {
-                site_event = *site_event_iterator_;
-                // Create degenerate node.
-                key_type new_key(site_event);
-
-                // Find the node in the binary search tree with left arc
-                // lying above the new site point.
-                beach_line_iterator it = beach_line_.lower_bound(new_key);
-                int it_dist = site_event.is_segment() ? 2 : 1;
-
-                // Do further processing depending on the above node position.
-                // For any two neighbouring nodes the second site of the first node
-                // is the same as the first site of the second arc.
-                if (it == beach_line_.end()) {
-                    // The above arc corresponds to the second arc of the last node.
-                    // Move the iterator to the last node.
-                    --it;
-
-                    // Get the second site of the last node
-                    const site_event_type &site_arc = it->first.right_site();
-
-                    // Insert new nodes into the beach line. Update the output.
-                    beach_line_iterator new_node_it =
-                        insert_new_arc(site_arc, site_arc, site_event, it);
-
-                    // Add a candidate circle to the circle event queue.
-                    // There could be only one new circle event formed by
-                    // a new bisector and the one on the left.
-                    std::advance(new_node_it, -it_dist);
-                    activate_circle_event(it->first.left_site(),
-                                          it->first.right_site(),
-                                          site_event, new_node_it);
-                } else if (it == beach_line_.begin()) {
-                    // The above arc corresponds to the first site of the first node.
-                    const site_event_type &site_arc = it->first.left_site();
-
-                    // Insert new nodes into the beach line. Update the output.
-                    insert_new_arc(site_arc, site_arc, site_event, it);
-
-                    // If the site event is a segment, update its direction.
-                    if (site_event.is_segment()) {
-                        site_event.inverse();
-                    }
-
-                    // Add a candidate circle to the circle event queue.
-                    // There could be only one new circle event formed by
-                    // a new bisector and the one on the right.
-                    activate_circle_event(site_event, it->first.left_site(),
-                                          it->first.right_site(), it);
-                } else {
-                    // The above arc corresponds neither to the first,
-                    // nor to the last site in the beach line.
-                    const site_event_type &site_arc2 = it->first.left_site();
-                    const site_event_type &site3 = it->first.right_site();
-
-                    // Remove the candidate circle from the event queue.
-                    it->second.deactivate_circle_event();
-                    --it;
-                    const site_event_type &site_arc1 = it->first.right_site();
-                    const site_event_type &site1 = it->first.left_site();
-
-                    // Insert new nodes into the beach line. Update the output.
-                    beach_line_iterator new_node_it =
-                        insert_new_arc(site_arc1, site_arc2, site_event, it);
-
-                    // Add candidate circles to the circle event queue.
-                    // There could be up to two circle events formed by
-                    // a new bisector and the one on the left or right.
-                    std::advance(new_node_it, -it_dist);
-                    activate_circle_event(site1, site_arc1, site_event,
-                                          new_node_it);
-
-                    // If the site event is a segment, update its direction.
-                    if (site_event.is_segment()) {
-                        site_event.inverse();
-                    }
-                    std::advance(new_node_it, it_dist + 1);
-                    activate_circle_event(site_event, site_arc2, site3,
-                                          new_node_it);
-                }
-            }
-        }
-
-        // Process a single circle event.
-        // In general case circle event is made of the three consequtive sites
-        // that form two bisector nodes in the beach line data structure.
-        // Let circle event sites be A, B, C, two bisectors that define
-        // circle event be (A, B), (B, C). During circle event processing
-        // we remove (A, B), (B, C) and insert (A, C). As beach line comparer
-        // works correctly only if one of the nodes is a new one we remove
-        // (B, C) bisector and change (A, B) bisector to the (A, C). That's
-        // why we use const_cast there and take all the responsibility that
-        // map data structure keeps correct ordering.
-        void process_circle_event() {
-            // Get the topmost circle event.
-            const circle_event_type &circle_event = circle_events_.top();
-            beach_line_iterator it_first = circle_event.bisector();
-            beach_line_iterator it_last = it_first;
-
-            // Get the C site.
-            site_event_type site3 = it_first->first.right_site();
-
-            // Get the half-edge corresponding to the second bisector - (B, C).
-            edge_type *bisector2 = it_first->second.edge();
-
-            // Get the half-edge corresponding to the first bisector - (A, B).
-            --it_first;
-            edge_type *bisector1 = it_first->second.edge();
-
-            // Get the A site.
-            site_event_type site1 = it_first->first.left_site();
-
-            if (!site1.is_segment() && site3.is_segment() &&
-                site3.point1(true) == site1.point0()) {
-                site3.inverse();
-            }
-
-            // Change the (A, B) bisector node to the (A, C) bisector node.
-            const_cast<key_type &>(it_first->first).right_site(site3);
-
-            // Insert the new bisector into the beach line.
-            it_first->second.edge(output_->insert_new_edge(site1, site3, circle_event,
-                                                           bisector1, bisector2));
-
-            // Remove the (B, C) bisector node from the beach line.
-            beach_line_.erase(it_last);
-            it_last = it_first;
-
-            // Pop the topmost circle event from the event queue.
-            circle_events_.pop();
-
-            // Check new triplets formed by the neighboring arcs
-            // to the left for potential circle events.
-            if (it_first != beach_line_.begin()) {
-                it_first->second.deactivate_circle_event();
-                --it_first;
-                const site_event_type &site_l1 = it_first->first.left_site();
-                activate_circle_event(site_l1, site1, site3, it_last);
-            }
-
-            // Check the new triplet formed by the neighboring arcs
-            // to the right for potential circle events.
-            ++it_last;
-            if (it_last != beach_line_.end()) {
-                it_last->second.deactivate_circle_event();
-                const site_event_type &site_r1 = it_last->first.right_site();
-                activate_circle_event(site1, site3, site_r1, it_last);
-            }
-        }
-
-        // Insert new nodes into the beach line. Update the output.
-        beach_line_iterator insert_new_arc(const site_event_type &site_arc1,
-                                           const site_event_type &site_arc2,
-                                           const site_event_type &site_event,
-                                           const beach_line_iterator &position) {
-            // Create two new bisectors with opposite directions.
-            key_type new_left_node(site_arc1, site_event);
-            key_type new_right_node(site_event, site_arc2);
-
-            // Set correct orientation for the first site of the second node.
-            if (site_event.is_segment()) {
-                new_right_node.inverse_left_site();
-            }
-
-            // Update the output.
-            edge_type *edge = output_->insert_new_edge(site_arc2, site_event);
-
-            // Update the beach line with the (site_arc1, site_event) bisector.
-            beach_line_iterator it = beach_line_.insert(position,
-                typename beach_line_type::value_type(new_right_node, value_type(edge->twin())));
-
-            if (site_event.is_segment()) {
-                // Update the beach line with temporary bisector, that will
-                // disappear after processing site event going through the
-                // endpoint of the segment site.
-                key_type new_node(site_event, site_event);
-                new_node.inverse_right_site();
-                beach_line_iterator temp_it = beach_line_.insert(position,
-                    typename beach_line_type::value_type(new_node, value_type(NULL)));
-
-                // Update the data structure that holds temporary bisectors.
-                end_points_.push(std::make_pair(site_event.point1(), temp_it));
-            }
-
-            // Update the beach line with the (site_event, site_arc2) bisector.
-            beach_line_.insert(position,
-                typename beach_line_type::value_type(new_left_node, value_type(edge)));
-            return it;
-        }
-
-        // Create a circle event from the given three sites.
-        // Returns true if the circle event exists, else false.
-        // If exists circle event is saved into the c_event variable.
-        bool create_circle_event(const site_event_type &site1,
-                                 const site_event_type &site2,
-                                 const site_event_type &site3,
-                                 circle_event_type &c_event) const {
-            if (!site1.is_segment()) {
-                if (!site2.is_segment()) {
-                    if (!site3.is_segment()) {
-                        // (point, point, point) sites.
-                        return create_circle_event_ppp(site1, site2, site3, c_event);
-                    } else {
-                        // (point, point, segment) sites.
-                        return create_circle_event_pps(site1, site2, site3, 3, c_event);
-                    }
-                } else {
-                    if (!site3.is_segment()) {
-                        // (point, segment, point) sites.
-                        return create_circle_event_pps(site1, site3, site2, 2, c_event);
-                    } else {
-                        // (point, segment, segment) sites.
-                        return create_circle_event_pss(site1, site2, site3, 1, c_event);
-                    }
-                }
-            } else {
-                if (!site2.is_segment()) {
-                    if (!site3.is_segment()) {
-                        // (segment, point, point) sites.
-                        return create_circle_event_pps(site2, site3, site1, 1, c_event);
-                    } else {
-                        // (segment, point, segment) sites.
-                        return create_circle_event_pss(site2, site1, site3, 2, c_event);
-                    }
-                } else {
-                    if (!site3.is_segment()) {
-                        // (segment, segment, point) sites.
-                        return create_circle_event_pss(site3, site1, site2, 3, c_event);
-                    } else {
-                        // (segment, segment, segment) sites.
-                        return create_circle_event_sss(site1, site2, site3, c_event);
-                    }
-                }
-            }
-        }
-
-        // Add a new circle event to the event queue.
-        // bisector_node corresponds to the (site2, site3) bisector.
-        void activate_circle_event(const site_event_type &site1,
-                                   const site_event_type &site2,
-                                   const site_event_type &site3,
-                                   beach_line_iterator bisector_node) {
-            circle_event_type c_event;
-            // Check if the three input sites create a circle event.
-            if (create_circle_event(site1, site2, site3, c_event)) {
-                // Update circle event's bisector iterator to point to the
-                // second bisector that forms it in the beach line.
-                c_event.bisector(bisector_node);
-
-                // Add the new circle event to the circle events queue.
-                // Update bisector's circle event iterator to point to the
-                // new circle event in the circle event queue.
-                bisector_node->second.activate_circle_event(
-                    circle_events_.push(c_event));
-            }
-        }
-
-    private:
-        struct end_point_comparison {
-            bool operator() (const end_point_type &end1, const end_point_type &end2) const {
-                return end1.first > end2.first;
-            }
-        };
-
-        std::vector<site_event_type> site_events_;
-        site_event_iterator_type site_event_iterator_;
-        std::priority_queue< end_point_type, std::vector<end_point_type>,
-                             end_point_comparison > end_points_;
-        circle_event_queue_type circle_events_;
-        beach_line_type beach_line_;
-        output_type *output_;
-
-        //Disallow copy constructor and operator=
-        voronoi_builder(const voronoi_builder&);
-        void operator=(const voronoi_builder&);
+        voronoi_diagram(const voronoi_diagram&);
+        void operator=(const voronoi_diagram&);
     };
 
-    // Public methods to compute voronoi diagram.
-    // points - vector of input points.
-    // segments - vector of input segments.
-    // output - voronoi output data structure to hold voronoi diagram.
-    // The assumption is made that input doesn't contain segments that
-    // intersect or points lying on the segments. Also coordinates of
-    // the points and of the endpoints of the segments should be within
-    // signed integer range [-2^31, 2^31-1].
-    // Complexity - O(N*logN), memory usage - O(N), where N is the total
-    // number of points and segments.
-
-    template <typename T, typename PC, typename VD>
-    static inline void construct_voronoi_points(const PC &points, VD &output) {
-        voronoi_builder<T, VD> builder;
-        builder.insert_points(points.begin(), points.end());
-        builder.construct(output);
-        builder.clear();
-    }
-
-    template <typename T, typename SC, typename VD>
-    static inline void construct_voronoi_segments(const SC &segments, VD &output) {
-        voronoi_builder<T, VD> builder;
-        builder.insert_segments(segments.begin(), segments.end());
-        builder.construct(output);
-        builder.clear();
-    }
-
-    template <typename T, typename PC, typename SC, typename VD>
-    static inline void construct_voronoi(const PC &points, const SC &segments, VD &output) {
-        voronoi_builder<T, VD> builder;
-        builder.insert_sites(points.begin(), points.end(), segments.begin(), segments.end());
-        builder.construct(output);
-        builder.clear();
-    }
-
 } // sweepline
 } // boost
 

Modified: sandbox/SOC/2010/sweepline/libs/sweepline/example/voronoi_visualizer.cpp
==============================================================================
--- sandbox/SOC/2010/sweepline/libs/sweepline/example/voronoi_visualizer.cpp	(original)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/example/voronoi_visualizer.cpp	2011-09-13 12:39:35 EDT (Tue, 13 Sep 2011)
@@ -12,7 +12,7 @@
 #include <QtOpenGL/QGLWidget>
 #include <QtGui/QtGui>
 
-#include "boost/sweepline/voronoi_diagram.hpp"
+#include "boost/sweepline/voronoi.hpp"
 using namespace boost::sweepline;
 
 class GLWidget : public QGLWidget {
@@ -57,9 +57,9 @@
         in_stream.flush();
 
         // Build voronoi diagram.
-        construct_voronoi<int>(point_sites, segment_sites, voronoi_output_);
+        construct_voronoi<int>(point_sites, segment_sites, vd_);
         brect_ = voronoi_helper<coordinate_type>::get_view_rectangle(
-            voronoi_output_.bounding_rectangle());
+            vd_.bounding_rectangle());
 
         // Update view.
         update_view_port();
@@ -83,7 +83,7 @@
 
         // Draw voronoi sites.
         {
-            const voronoi_cells_type &cells = voronoi_output_.cell_records();
+            const voronoi_cells_type &cells = vd_.cell_records();
             voronoi_cell_const_iterator_type it;
             glColor3f(0.0f, 0.0f, 1.0f);
             glPointSize(9);
@@ -108,7 +108,7 @@
 
         // Draw voronoi vertices.
         {
-            const voronoi_vertices_type &vertices = voronoi_output_.vertex_records();
+            const voronoi_vertices_type &vertices = vd_.vertex_records();
             voronoi_vertex_const_iterator_type it;
             glColor3f(0.0f, 1.0f, 0.0f);
             glBegin(GL_POINTS);
@@ -119,7 +119,7 @@
 
         // Draw voronoi edges.
         {
-            const voronoi_edges_type &edges = voronoi_output_.edge_records();
+            const voronoi_edges_type &edges = vd_.edge_records();
             voronoi_edge_const_iterator_type it;
             glColor3f(0.0f, 1.0f, 0.0f);
             glBegin(GL_LINES);
@@ -161,17 +161,17 @@
     typedef directed_line_segment_data<int> isegment_type;
     typedef std::vector<ipoint_type> ipoint_set_type;
     typedef directed_line_segment_set_data<int> isegment_set_type;
-    typedef voronoi_output<coordinate_type>::voronoi_cells_type voronoi_cells_type;
-    typedef voronoi_output<coordinate_type>::voronoi_vertices_type voronoi_vertices_type;
-    typedef voronoi_output<coordinate_type>::voronoi_edges_type voronoi_edges_type;
-    typedef voronoi_output<coordinate_type>::voronoi_cell_const_iterator_type
+    typedef voronoi_diagram<coordinate_type>::voronoi_cells_type voronoi_cells_type;
+    typedef voronoi_diagram<coordinate_type>::voronoi_vertices_type voronoi_vertices_type;
+    typedef voronoi_diagram<coordinate_type>::voronoi_edges_type voronoi_edges_type;
+    typedef voronoi_diagram<coordinate_type>::voronoi_cell_const_iterator_type
         voronoi_cell_const_iterator_type;
-    typedef voronoi_output<coordinate_type>::voronoi_vertex_const_iterator_type
+    typedef voronoi_diagram<coordinate_type>::voronoi_vertex_const_iterator_type
         voronoi_vertex_const_iterator_type;
-    typedef voronoi_output<coordinate_type>::voronoi_edge_const_iterator_type
+    typedef voronoi_diagram<coordinate_type>::voronoi_edge_const_iterator_type
         voronoi_edge_const_iterator_type;
     BRect<coordinate_type> brect_;
-    voronoi_output<coordinate_type> voronoi_output_;
+    voronoi_diagram<coordinate_type> vd_;
     bool primary_edges_only_;
 };
 

Modified: sandbox/SOC/2010/sweepline/libs/sweepline/test/benchmark_test.cpp
==============================================================================
--- sandbox/SOC/2010/sweepline/libs/sweepline/test/benchmark_test.cpp	(original)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/test/benchmark_test.cpp	2011-09-13 12:39:35 EDT (Tue, 13 Sep 2011)
@@ -17,7 +17,7 @@
 #include <boost/test/test_case_template.hpp>
 #include <boost/timer.hpp>
 
-#include "boost/sweepline/voronoi_diagram.hpp"
+#include "boost/sweepline/voronoi.hpp"
 
 typedef boost::mpl::list<int> test_types;
 
@@ -26,7 +26,7 @@
     typedef point_data<coordinate_type> point_type;
     boost::mt19937 gen(static_cast<unsigned int>(time(NULL)));
     boost::timer timer;
-    typename boost::sweepline::voronoi_output<double> test_output;
+    typename boost::sweepline::voronoi_diagram<double> test_output;
 
     std::ofstream bench_file("benchmark.txt", std::ios_base::out | std::ios_base::app);
     bench_file << "Voronoi Segment Sweepline Benchmark Test (time in seconds):" << std::endl;

Modified: sandbox/SOC/2010/sweepline/libs/sweepline/test/circle_event_creation_test.cpp
==============================================================================
--- sandbox/SOC/2010/sweepline/libs/sweepline/test/circle_event_creation_test.cpp	(original)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/test/circle_event_creation_test.cpp	2011-09-13 12:39:35 EDT (Tue, 13 Sep 2011)
@@ -11,7 +11,7 @@
 #include <boost/mpl/list.hpp>
 #include <boost/test/test_case_template.hpp>
 
-#include "boost/sweepline/voronoi_diagram.hpp"
+#include "boost/sweepline/voronoi_builder.hpp"
 using namespace boost::sweepline;
 using namespace boost::sweepline::detail;
 
@@ -64,8 +64,8 @@
     site_event_type site1_2(static_cast<T>(0), static_cast<T>(2), 0);
     is_event = create_circle_event_pps(site1_1, site1_2, segm_site, 2, c_event);
     BOOST_CHECK_EQUAL(is_event, true);
-    BOOST_CHECK_EQUAL(c_event.center().x() == static_cast<T>(-1), true);
-    BOOST_CHECK_EQUAL(c_event.center().y() == static_cast<T>(1), true);
+    BOOST_CHECK_EQUAL(c_event.x() == static_cast<T>(-1), true);
+    BOOST_CHECK_EQUAL(c_event.y() == static_cast<T>(1), true);
     is_event = create_circle_event_pps(site1_1, site1_2, segm_site, 1, c_event);
     BOOST_CHECK_EQUAL(is_event, false);
     is_event = create_circle_event_pps(site1_1, site1_2, segm_site, 3, c_event);

Modified: sandbox/SOC/2010/sweepline/libs/sweepline/test/clipping_test.cpp
==============================================================================
--- sandbox/SOC/2010/sweepline/libs/sweepline/test/clipping_test.cpp	(original)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/test/clipping_test.cpp	2011-09-13 12:39:35 EDT (Tue, 13 Sep 2011)
@@ -13,7 +13,6 @@
 
 #include "boost/sweepline/voronoi_diagram.hpp"
 using namespace boost::sweepline;
-using namespace boost::sweepline::detail;
 
 typedef boost::mpl::list<double> test_types;
 

Modified: sandbox/SOC/2010/sweepline/libs/sweepline/test/event_queue_test.cpp
==============================================================================
--- sandbox/SOC/2010/sweepline/libs/sweepline/test/event_queue_test.cpp	(original)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/test/event_queue_test.cpp	2011-09-13 12:39:35 EDT (Tue, 13 Sep 2011)
@@ -13,7 +13,7 @@
 #include <boost/mpl/list.hpp>
 #include <boost/test/test_case_template.hpp>
 
-#include "boost/sweepline/voronoi_diagram.hpp"
+#include "boost/sweepline/voronoi_builder.hpp"
 using namespace boost::sweepline;
 using namespace boost::sweepline::detail;
 

Modified: sandbox/SOC/2010/sweepline/libs/sweepline/test/event_types_test.cpp
==============================================================================
--- sandbox/SOC/2010/sweepline/libs/sweepline/test/event_types_test.cpp	(original)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/test/event_types_test.cpp	2011-09-13 12:39:35 EDT (Tue, 13 Sep 2011)
@@ -11,7 +11,7 @@
 #include <boost/mpl/list.hpp>
 #include <boost/test/test_case_template.hpp>
 
-#include "boost/sweepline/voronoi_diagram.hpp"
+#include "boost/sweepline/voronoi_builder.hpp"
 using namespace boost::sweepline;
 using namespace boost::sweepline::detail;
 

Modified: sandbox/SOC/2010/sweepline/libs/sweepline/test/node_comparer_test.cpp
==============================================================================
--- sandbox/SOC/2010/sweepline/libs/sweepline/test/node_comparer_test.cpp	(original)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/test/node_comparer_test.cpp	2011-09-13 12:39:35 EDT (Tue, 13 Sep 2011)
@@ -11,7 +11,7 @@
 #include <boost/mpl/list.hpp>
 #include <boost/test/test_case_template.hpp>
 
-#include "boost/sweepline/voronoi_diagram.hpp"
+#include "boost/sweepline/voronoi_builder.hpp"
 using namespace boost::sweepline;
 using namespace boost::sweepline::detail;
 
@@ -19,7 +19,7 @@
 
 BOOST_AUTO_TEST_CASE_TEMPLATE(node_comparer_test_pp1, T, test_types) {
     typedef site_event<T> site_event_type;
-    typedef beach_line_node<T> bline_node;
+    typedef beach_line_node_key<T> bline_node;
     typedef typename std::map< bline_node, int,
         node_comparer<bline_node> >::const_iterator bline_it;
 
@@ -45,7 +45,7 @@
 
 BOOST_AUTO_TEST_CASE_TEMPLATE(node_comparer_test_pp2, T, test_types) {
     typedef site_event<T> site_event_type;
-    typedef beach_line_node<T> bline_node;
+    typedef beach_line_node_key<T> bline_node;
     typedef typename std::map< bline_node, int,
         node_comparer<bline_node> >::const_iterator bline_it;
 
@@ -73,7 +73,7 @@
 
 BOOST_AUTO_TEST_CASE_TEMPLATE(node_comparer_test_pp3, T, test_types) {
     typedef point_2d<T> Point2D;
-    typedef beach_line_node<T> bline_node;
+    typedef beach_line_node_key<T> bline_node;
     node_comparer<bline_node> node_comparer_test;
 
     bline_node initial_node(
@@ -106,7 +106,7 @@
 
 BOOST_AUTO_TEST_CASE_TEMPLATE(node_comparer_test_pp4, T, test_types) {
     typedef point_2d<T> Point2D;
-    typedef beach_line_node<T> bline_node;
+    typedef beach_line_node_key<T> bline_node;
     node_comparer<bline_node> node_comparer_test;
 
     bline_node initial_node(
@@ -137,7 +137,7 @@
 
 BOOST_AUTO_TEST_CASE_TEMPLATE(node_comparer_test_pp5, T, test_types) {
     typedef point_2d<T> Point2D;
-    typedef beach_line_node<T> bline_node;
+    typedef beach_line_node_key<T> bline_node;
     node_comparer<bline_node> node_comparer_test;
 
     bline_node initial_node(
@@ -170,7 +170,7 @@
 
 BOOST_AUTO_TEST_CASE_TEMPLATE(node_comparer_test_pp6, T, test_types) {
     typedef point_2d<T> Point2D;
-    typedef beach_line_node<T> bline_node;
+    typedef beach_line_node_key<T> bline_node;
     node_comparer<bline_node> node_comparer_test;
 
     bline_node initial_node(
@@ -204,7 +204,7 @@
 
 BOOST_AUTO_TEST_CASE_TEMPLATE(node_comparer_test_pp7, T, test_types) {
     typedef point_2d<T> Point2D;
-    typedef beach_line_node<T> bline_node;
+    typedef beach_line_node_key<T> bline_node;
     node_comparer<bline_node> node_comparer_test;
 
     bline_node initial_node(
@@ -226,7 +226,7 @@
 
 BOOST_AUTO_TEST_CASE_TEMPLATE(node_comparer_test_pp8, T, test_types) {
     typedef point_2d<T> Point2D;
-    typedef beach_line_node<T> bline_node;
+    typedef beach_line_node_key<T> bline_node;
     node_comparer<bline_node> node_comparer_test;
 
     bline_node initial_node(

Modified: sandbox/SOC/2010/sweepline/libs/sweepline/test/predicates_test.cpp
==============================================================================
--- sandbox/SOC/2010/sweepline/libs/sweepline/test/predicates_test.cpp	(original)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/test/predicates_test.cpp	2011-09-13 12:39:35 EDT (Tue, 13 Sep 2011)
@@ -11,7 +11,7 @@
 #include <boost/mpl/list.hpp>
 #include <boost/test/test_case_template.hpp>
 
-#include "boost/sweepline/voronoi_diagram.hpp"
+#include "boost/sweepline/voronoi_builder.hpp"
 using namespace boost::sweepline;
 using namespace boost::sweepline::detail;
 

Modified: sandbox/SOC/2010/sweepline/libs/sweepline/test/robust_fpt_test.cpp
==============================================================================
--- sandbox/SOC/2010/sweepline/libs/sweepline/test/robust_fpt_test.cpp	(original)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/test/robust_fpt_test.cpp	2011-09-13 12:39:35 EDT (Tue, 13 Sep 2011)
@@ -11,7 +11,7 @@
 #include <boost/mpl/list.hpp>
 #include <boost/test/test_case_template.hpp>
 
-#include "boost/sweepline/voronoi_diagram.hpp"
+#include "boost/sweepline/voronoi_builder.hpp"
 using namespace boost::sweepline::detail;
 
 typedef boost::mpl::list<double, mpf_class, mpt_wrapper<mpf_class, 8> > test_types;

Modified: sandbox/SOC/2010/sweepline/libs/sweepline/test/sqrt_expr_evaluator_test.cpp
==============================================================================
--- sandbox/SOC/2010/sweepline/libs/sweepline/test/sqrt_expr_evaluator_test.cpp	(original)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/test/sqrt_expr_evaluator_test.cpp	2011-09-13 12:39:35 EDT (Tue, 13 Sep 2011)
@@ -13,7 +13,7 @@
 #include <boost/random/mersenne_twister.hpp>
 #include <boost/test/test_case_template.hpp>
 
-#include "boost/sweepline/voronoi_diagram.hpp"
+#include "boost/sweepline/voronoi_builder.hpp"
 using namespace boost::sweepline::detail;
 
 template <int N>

Modified: sandbox/SOC/2010/sweepline/libs/sweepline/test/sweepline_test.cpp
==============================================================================
--- sandbox/SOC/2010/sweepline/libs/sweepline/test/sweepline_test.cpp	(original)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/test/sweepline_test.cpp	2011-09-13 12:39:35 EDT (Tue, 13 Sep 2011)
@@ -14,7 +14,7 @@
 #include <boost/random/mersenne_twister.hpp>
 #include <boost/test/test_case_template.hpp>
 
-#include "boost/sweepline/voronoi_diagram.hpp"
+#include "boost/sweepline/voronoi.hpp"
 using namespace boost::sweepline;
 using namespace boost::sweepline::detail;
 #include "output_verification.hpp"
@@ -48,12 +48,12 @@
 // Sites: (0, 0).
 BOOST_AUTO_TEST_CASE_TEMPLATE(single_site_test, T, test_types) {
     typedef double coordinate_type;
-    typedef typename voronoi_output<coordinate_type>::voronoi_cell_const_iterator_type
+    typedef typename voronoi_diagram<coordinate_type>::voronoi_cell_const_iterator_type
         voronoi_cell_const_iterator_type;
 
     std::vector< point_data<T> > points;
     points.push_back(point_data<T>(0, 0));
-    voronoi_output<coordinate_type> test_output;
+    voronoi_diagram<coordinate_type> test_output;
     construct_voronoi_points<T>(points, test_output);
     VERIFY_OUTPUT(test_output);
 
@@ -68,14 +68,14 @@
 // Sites: (0, 0), (0, 1).
 BOOST_AUTO_TEST_CASE_TEMPLATE(collinear_sites_test1, T, test_types) {
     typedef double coordinate_type;
-    typedef typename voronoi_output<coordinate_type>::voronoi_edge_type voronoi_edge_type;
-    typedef typename voronoi_output<coordinate_type>::voronoi_cell_const_iterator_type
+    typedef typename voronoi_diagram<coordinate_type>::voronoi_edge_type voronoi_edge_type;
+    typedef typename voronoi_diagram<coordinate_type>::voronoi_cell_const_iterator_type
         voronoi_cell_const_iterator_type;
 
     std::vector< point_data<T> > points;
     points.push_back(point_data<T>(0, 0));
     points.push_back(point_data<T>(0, 1));
-    voronoi_output<coordinate_type> test_output;
+    voronoi_diagram<coordinate_type> test_output;
     construct_voronoi_points<T>(points, test_output);
     VERIFY_OUTPUT(test_output);
 
@@ -107,15 +107,15 @@
 // Sites: (0, 0), (1, 1), (2, 2).
 BOOST_AUTO_TEST_CASE_TEMPLATE(collinear_sites_test2, T, test_types) {
     typedef double coordinate_type;
-    typedef typename voronoi_output<coordinate_type>::voronoi_edge_type voronoi_edge_type;
-    typedef typename voronoi_output<coordinate_type>::voronoi_cell_const_iterator_type
+    typedef typename voronoi_diagram<coordinate_type>::voronoi_edge_type voronoi_edge_type;
+    typedef typename voronoi_diagram<coordinate_type>::voronoi_cell_const_iterator_type
         voronoi_cell_const_iterator_type;
 
     std::vector< point_data<T> > points;
     points.push_back(point_data<T>(0, 0));
     points.push_back(point_data<T>(1, 1));
     points.push_back(point_data<T>(2, 2));
-    voronoi_output<coordinate_type> test_output;
+    voronoi_diagram<coordinate_type> test_output;
     construct_voronoi_points<T>(points, test_output);
     VERIFY_OUTPUT(test_output);
 
@@ -150,8 +150,8 @@
 // Sites: (0, 0), (0, 4), (2, 1).
 BOOST_AUTO_TEST_CASE_TEMPLATE(triangle_test1, T, test_types) {
     typedef double coordinate_type;
-    typedef typename voronoi_output<coordinate_type>::voronoi_edge_type voronoi_edge_type;
-    typedef typename voronoi_output<coordinate_type>::voronoi_vertex_const_iterator_type
+    typedef typename voronoi_diagram<coordinate_type>::voronoi_edge_type voronoi_edge_type;
+    typedef typename voronoi_diagram<coordinate_type>::voronoi_vertex_const_iterator_type
         voronoi_vertex_const_iterator_type;
 
     point_2d<coordinate_type> point1 = point_2d<coordinate_type>(
@@ -165,7 +165,7 @@
     points.push_back(point_data<T>(point1.x(), point1.y()));
     points.push_back(point_data<T>(point2.x(), point2.y()));
     points.push_back(point_data<T>(point3.x(), point3.y()));
-    voronoi_output<coordinate_type> test_output;
+    voronoi_diagram<coordinate_type> test_output;
     construct_voronoi_points<T>(points, test_output);
     VERIFY_OUTPUT(test_output);
 
@@ -211,8 +211,8 @@
 // Sites: (0, 1), (2, 0), (2, 4).
 BOOST_AUTO_TEST_CASE_TEMPLATE(triangle_test2, T, test_types) {
     typedef double coordinate_type;
-    typedef typename voronoi_output<coordinate_type>::voronoi_edge_type voronoi_edge_type;
-    typedef typename voronoi_output<coordinate_type>::voronoi_vertex_const_iterator_type
+    typedef typename voronoi_diagram<coordinate_type>::voronoi_edge_type voronoi_edge_type;
+    typedef typename voronoi_diagram<coordinate_type>::voronoi_vertex_const_iterator_type
         voronoi_vertex_const_iterator_type;
 
     point_2d<coordinate_type> point1 = point_2d<coordinate_type>(
@@ -226,7 +226,7 @@
     points.push_back(point_data<T>(point1.x(), point1.y()));
     points.push_back(point_data<T>(point2.x(), point2.y()));
     points.push_back(point_data<T>(point3.x(), point3.y()));
-    voronoi_output<coordinate_type> test_output;
+    voronoi_diagram<coordinate_type> test_output;
     construct_voronoi_points<T>(points, test_output);
     VERIFY_OUTPUT(test_output);
 
@@ -272,8 +272,8 @@
 // Sites: (0, 0), (0, 1), (1, 0), (1, 1).
 BOOST_AUTO_TEST_CASE_TEMPLATE(square_test1, T, test_types) {
     typedef double coordinate_type;
-    typedef typename voronoi_output<coordinate_type>::voronoi_edge_type voronoi_edge_type;
-    typedef typename voronoi_output<coordinate_type>::voronoi_vertex_const_iterator_type
+    typedef typename voronoi_diagram<coordinate_type>::voronoi_edge_type voronoi_edge_type;
+    typedef typename voronoi_diagram<coordinate_type>::voronoi_vertex_const_iterator_type
         voronoi_vertex_const_iterator_type;
 
     point_2d<coordinate_type> point1 = point_2d<coordinate_type>(
@@ -290,7 +290,7 @@
     points.push_back(point_data<T>(point2.x(), point2.y()));
     points.push_back(point_data<T>(point3.x(), point3.y()));
     points.push_back(point_data<T>(point4.x(), point4.y()));
-    voronoi_output<coordinate_type> test_output;
+    voronoi_diagram<coordinate_type> test_output;
     construct_voronoi_points<T>(points, test_output);
     VERIFY_OUTPUT(test_output);
 
@@ -346,7 +346,7 @@
 
 #ifdef NDEBUG
 BOOST_AUTO_TEST_CASE_TEMPLATE(grid_test, T, test_types) {
-    voronoi_output<double> test_output_small, test_output_large;
+    voronoi_diagram<double> test_output_small, test_output_large;
     std::vector< point_data<T> > point_vec_small, point_vec_large;
     int grid_size[4] = {10, 33, 101, 163};
     int max_value[4] = {10, 33, 101, 163};
@@ -376,7 +376,7 @@
 #ifdef NDEBUG
 BOOST_AUTO_TEST_CASE_TEMPLATE(random_test, T, test_types) {
     boost::mt19937 gen(static_cast<unsigned int>(time(NULL)));
-    voronoi_output<double> test_output_small, test_output_large;
+    voronoi_diagram<double> test_output_small, test_output_large;
     std::vector< point_data<T> > point_vec_small, point_vec_large;
     int num_points[] = {5, 100, 1000, 10000, 100000};
     int num_runs[] = {10000, 1000, 100, 10, 1};
@@ -412,7 +412,7 @@
 #ifdef NDEBUG
 BOOST_AUTO_TEST_CASE_TEMPLATE(enormous_random_test, T, test_types) {
     boost::mt19937 gen(static_cast<unsigned int>(time(NULL)));
-    voronoi_output<double> test_output;
+    voronoi_diagram<double> test_output;
     std::vector< point_data<T> > point_vec;
     for (int i = 0; i < 1000000; i++)
         point_vec.push_back(point_data<T>(gen() % 10000 - 5000, gen() % 10000 - 5000));
@@ -423,7 +423,7 @@
 
 BOOST_AUTO_TEST_CASE_TEMPLATE(segment_sites_test1, T, test_types) {
     typedef T coordinate_type;
-    voronoi_output<double> test_output;
+    voronoi_diagram<double> test_output;
     directed_line_segment_set_data<T> segments;
     point_data<T> point1(0, 0);
     point_data<T> point2(1, 1);
@@ -435,7 +435,7 @@
 
 BOOST_AUTO_TEST_CASE_TEMPLATE(segment_sites_test2, T, test_types) {
     typedef T coordinate_type;
-    voronoi_output<double> test_output;
+    voronoi_diagram<double> test_output;
     std::vector< point_data<T> > points;
     directed_line_segment_set_data<T> segments;
     point_data<T> point1(0, 0);
@@ -452,7 +452,7 @@
 
 BOOST_AUTO_TEST_CASE_TEMPLATE(segment_sites_test3, T, test_types) {
     typedef T coordinate_type;
-    voronoi_output<double> test_output;
+    voronoi_diagram<double> test_output;
     std::vector< point_data<T> > points;
     directed_line_segment_set_data<T> segments;
     point_data<T> point1(4, 0);
@@ -469,7 +469,7 @@
 
 BOOST_AUTO_TEST_CASE_TEMPLATE(segment_sites_test4, T, test_types) {
     typedef T coordinate_type;
-    voronoi_output<double> test_output;
+    voronoi_diagram<double> test_output;
     std::vector< point_data<T> > points;
     directed_line_segment_set_data<T> segments;
     point_data<T> point1(4, 0);
@@ -486,7 +486,7 @@
 
 BOOST_AUTO_TEST_CASE_TEMPLATE(segment_site_test5, T, test_types) {
     typedef T coordinate_type;
-    voronoi_output<double> test_output;
+    voronoi_diagram<double> test_output;
     std::vector< point_data<T> > points;
     directed_line_segment_set_data<T> segments;
     point_data<T> point1(0, 0);
@@ -505,7 +505,7 @@
 
 BOOST_AUTO_TEST_CASE_TEMPLATE(segment_site_test6, T, test_types) {
     typedef T coordinate_type;
-    voronoi_output<double> test_output;
+    voronoi_diagram<double> test_output;
     std::vector< point_data<T> > points;
     directed_line_segment_set_data<T> segments;
     point_data<T> point1(-1, 1);
@@ -520,7 +520,7 @@
 
 BOOST_AUTO_TEST_CASE_TEMPLATE(segment_site_test7, T, test_types) {
     typedef T coordinate_type;
-    voronoi_output<double> test_output;
+    voronoi_diagram<double> test_output;
     directed_line_segment_set_data<T> segments;
     point_data<T> point1(0, 0);
     point_data<T> point2(4, 0);
@@ -536,7 +536,7 @@
 
 BOOST_AUTO_TEST_CASE_TEMPLATE(segment_site_test8, T, test_types) {
     typedef T coordinate_type;
-    voronoi_output<double> test_output;
+    voronoi_diagram<double> test_output;
     directed_line_segment_set_data<T> segments;
     point_data<T> point1(0, 0);
     point_data<T> point2(4, 0);
@@ -553,7 +553,7 @@
 
 #ifdef NDEBUG
 BOOST_AUTO_TEST_CASE_TEMPLATE(segment_grid_test, T, test_types) {
-    voronoi_output<double> test_output_small, test_output_large;
+    voronoi_diagram<double> test_output_small, test_output_large;
     directed_line_segment_set_data<T> segments_small, segments_large;
     int grid_size[] = {10, 33, 100};
     int max_value[] = {100, 330, 1000};
@@ -592,7 +592,7 @@
 #ifdef NDEBUG
 BOOST_AUTO_TEST_CASE_TEMPLATE(segment_random_test1, T, test_types) {
     boost::mt19937 gen(static_cast<unsigned int>(time(NULL)));
-    voronoi_output<double> test_output;
+    voronoi_diagram<double> test_output;
     std::vector< point_data<T> > points;
     directed_line_segment_set_data<T> segments;
     int num_runs = 1000;
@@ -625,7 +625,7 @@
 #ifdef NDEBUG
 BOOST_AUTO_TEST_CASE_TEMPLATE(segment_random_test2, T, test_types) {
     boost::mt19937 gen(static_cast<unsigned int>(time(NULL)));
-    voronoi_output<double> test_output_small, test_output_large;
+    voronoi_diagram<double> test_output_small, test_output_large;
     directed_line_segment_set_data<T> segments_small, segments_large;
     int num_segments[] = {5, 25, 125, 625};
     int num_runs[] = {1000, 100, 10, 1};