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

Subject: [Boost-commit] svn:boost r63187 - in sandbox/SOC/2010/sweepline: boost/sweepline boost/sweepline/detail libs/sweepline/test
From: sydorchuk.andriy_at_[hidden]
Date: 2010-06-21 09:47:47

Author: asydorchuk
Date: 2010-06-21 09:47:45 EDT (Mon, 21 Jun 2010)
New Revision: 63187
URL: http://svn.boost.org/trac/boost/changeset/63187

Log:
Splitted event_queue (contains only circle events now).
Made code refactoring.
Added:
   sandbox/SOC/2010/sweepline/boost/sweepline/detail/voronoi_formation.hpp
      - copied, changed from r63178, /sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_formation.hpp
   sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_builder.hpp   (contents, props changed)
   sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_builder_test.cpp   (contents, props changed)
Removed:
   sandbox/SOC/2010/sweepline/boost/sweepline/event_queue.hpp
   sandbox/SOC/2010/sweepline/boost/sweepline/event_types.hpp
   sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_formation.hpp
   sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_output.hpp
   sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_formation_test.cpp
Text files modified: 
   sandbox/SOC/2010/sweepline/boost/sweepline/detail/voronoi_formation.hpp |   923 ++++++++++++++++++++++++--------------- 
   sandbox/SOC/2010/sweepline/libs/sweepline/test/Jamfile.v2               |     2                                         
   sandbox/SOC/2010/sweepline/libs/sweepline/test/event_queue_test.cpp     |    75 --                                      
   sandbox/SOC/2010/sweepline/libs/sweepline/test/event_types_test.cpp     |     4                                         
   sandbox/SOC/2010/sweepline/libs/sweepline/test/node_comparer_test.cpp   |     4                                         
   5 files changed, 586 insertions(+), 422 deletions(-)

Copied: sandbox/SOC/2010/sweepline/boost/sweepline/detail/voronoi_formation.hpp (from r63178, /sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_formation.hpp)
==============================================================================
--- /sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_formation.hpp	(original)
+++ sandbox/SOC/2010/sweepline/boost/sweepline/detail/voronoi_formation.hpp	2010-06-21 09:47:45 EDT (Mon, 21 Jun 2010)
@@ -7,19 +7,580 @@
 
 //  See http://www.boost.org for updates, documentation, and revision history.
 
-#include <map>
-#include <vector>
-
-#include "event_queue.hpp"
-#include "event_types.hpp"
-#include "voronoi_output.hpp"
-
 #ifndef BOOST_SWEEPLINE_VORONOI_FORMATION
 #define BOOST_SWEEPLINE_VORONOI_FORMATION
 
+#include <list>
+#include <map>
+#include <queue>
+#include <vector>
+
 namespace boost {
 namespace sweepline {
+namespace detail {
+
+    ///////////////////////////////////////////////////////////////////////////
+    // VORONOI EVENT TYPES ////////////////////////////////////////////////////
+    ///////////////////////////////////////////////////////////////////////////
+
+    template <typename T>
+    struct site_event;
+    
+    template <typename T>
+    struct circle_event;
+
+    template <typename Point2D>
+    struct beach_line_node;
+
+    template <typename Point2D>
+    struct beach_line_node_data;
+
+    template <typename BeachLineNode>
+    struct node_comparer;
+
+    // Point in 2D space data structure. Comparators defined in this
+    // data structure actually define sweepline movement direction.
+    template <typename T>
+    struct point_2d {
+    public:
+        typedef T coordinate_type;
+        typedef site_event<T> site_event_type;
+        typedef circle_event<T> circle_event_type;
+
+        point_2d() {}
+
+        point_2d(T x, T y) {
+            x_ = x;
+            y_ = y;
+        }
+
+        bool operator==(const point_2d &point) const {
+            return (this->x_ == point.x()) && (this->y_ == point.y());
+        }
+
+        bool operator!=(const point_2d &point) const {
+            return (this->x_ != point.x()) || (this->y_ != point.y());
+        }
+
+        // This comparator actually defines sweepline movement direction.
+        bool operator<(const point_2d &point) const {
+            // Sweepline sweeps from left to right.
+            if (this->x_ != point.x_)
+                return this->x_ < point.x_;
+            return this->y_ < point.y_;
+        }
+
+        bool operator<=(const point_2d &point) const {
+            return !(point < (*this));
+        }
+
+        bool operator>(const point_2d &point) const {
+            return point < (*this);
+        }
+
+        bool operator>=(const point_2d &point) const {
+            return !((*this) < point);
+        }
+
+        coordinate_type x() const {
+            return this->x_;
+        }
+
+        coordinate_type y() const {
+            return this->y_;
+        }
+
+        void x(coordinate_type x) {
+            x_ = x;
+        }
+
+        void y(coordinate_type y) {
+            y_ = y;
+        }
+
+    private:
+        coordinate_type x_;
+        coordinate_type y_;
+    };
+
+    template <typename T>
+    point_2d<T> make_point_2d(T x, T y) {
+        return point_2d<T>(x,y);
+    }
+
+    // Site event type. 
+    // Occurs when sweepline sweeps over one of the initial sites.
+    // Contains index of a site below the other sorted sites.
+    template <typename T>
+    struct site_event {
+    public:
+        typedef T coordinate_type;
+
+        site_event() {}
+        
+        site_event(T x, T y, int index) : point_(x, y), site_index_(index) {}
+
+        bool operator==(const site_event &s_event) const {
+            return point_ == s_event.get_point();
+        }
+
+        bool operator!=(const site_event &s_event) const {
+            return point_ != s_event.get_point();
+        }
+
+        bool operator<(const site_event &s_event) const {
+            return point_ < s_event.get_point();
+        }
+
+        bool operator<=(const site_event &s_event) const {
+            return point_ <= s_event.get_point();
+        }
+
+        bool operator>(const site_event &s_event) const {
+            return point_ > s_event.get_point();
+        }
+
+        bool operator>=(const site_event &s_event) const {
+            return point_ >= s_event.get_point();
+        }
+
+        coordinate_type x() const {
+            return point_.x();
+        }
+
+        coordinate_type y() const {
+            return point_.y();
+        }
+
+        const point_2d<T> &get_point() const {
+            return point_;
+        }
+
+        int get_site_index() const {
+            return site_index_;
+        }
+
+    private:
+        point_2d<T> point_;
+        int site_index_;
+    };
+
+    template <typename T>
+    site_event<T> make_site_event(T x, T y, int index) {
+        return site_event<T>(x, y, index);
+    }
+
+    // Circle event type. Occurs when sweepline sweeps over the bottom point of
+    // the voronoi circle (with center at the bisectors intersection point).
+    // Circle event contains circle center and squared radius (to avoid sqrt
+    // computation). To compare bottom points of two different voronoi circles
+    // we don't compute exact radius and use special arithmetic for that. This 
+    // way voronoi diagram implementation may be used with rational arithmetic.
+    // Let circle center coordinates be (x, y), squared radius be r. 
+    // Bottom point of the voronoi circle will be defined as (x + sqrt(r), y).
+    // Contains reference to the second bisector node (ordered from left to
+    // right in the beach line) that creates given circle event.
+    template <typename T>
+    struct circle_event {
+    public:
+        typedef T coordinate_type;
+        typedef typename beach_line_node< point_2d<T> > Key;
+        typedef typename beach_line_node_data< point_2d<T> > Value;
+        typedef typename node_comparer<Key> NodeComparer;
+        typedef typename std::map< Key, Value, NodeComparer >::const_iterator beach_line_iterator;
+
+        circle_event() {}
+
+        circle_event(T c_x, T c_y, T sqr_r) :
+        center_(c_x, c_y), sqr_radius_(sqr_r) {}
+
+        bool equals(const circle_event &c_event) const {
+            return center_.x() == c_event.x() && center_.y() == c_event.y() &&
+                   sqr_radius_ == c_event.get_sqr_radius();
+        }
+
+        bool operator==(const circle_event &c_event) const {
+            if (center_.y() != c_event.y())
+                return false;
+
+            T sqr_dif_x = (center_.x() - c_event.x()) *
+                          (center_.x() - c_event.x());
+            T sum_r_sqr = sqr_radius_ + c_event.get_sqr_radius();
+            T value_left = (sum_r_sqr - sqr_dif_x) * (sum_r_sqr - sqr_dif_x);
+            T value_right = static_cast<T>(4) * sqr_radius_ *
+                            c_event.get_sqr_radius();
+
+            return value_left == value_right;
+        }
+
+        bool operator!=(const circle_event &c_event) const {
+            return !((*this) == c_event);
+        }
+
+        bool operator<(const circle_event &c_event) const {
+            T x1 = center_.x();
+            T y1 = center_.y();
+            T sqr_r1 = sqr_radius_;
+            T x2 = c_event.x();
+            T y2 = c_event.y();
+            T sqr_r2 = c_event.get_sqr_radius();
+
+            T sqr_dif_x = (x1 - x2) * (x1 - x2);
+            T sum_r_sqr = sqr_r1 + sqr_r2;
+            T value_left = (sum_r_sqr - sqr_dif_x) * (sum_r_sqr - sqr_dif_x);
+            T value_right = static_cast<T>(4) * sqr_r1 * sqr_r2;
+            
+            if (x1 > x2) {
+                if (sqr_r2 <= sqr_r1)
+                    return false;
+                
+                if (sqr_dif_x >= sum_r_sqr)
+                    return false;
+
+                if (value_left == value_right)
+                    return y1 < y2;
+                else
+                    return value_left > value_right;
+            }
+            else if (x1 < x2) {
+                if (sqr_r1 <= sqr_r2)
+                    return true;
+
+                if (sqr_dif_x >= sum_r_sqr)
+                    return true;
+
+                if (value_left == value_right)
+                    return y1 < y2;
+                else
+                    return value_left < value_right;
+            }
+            else {
+                if (sqr_r1 != sqr_r2)
+                    return sqr_r1 < sqr_r2;
+                return y1 < y2;
+            }
+        }
+
+        bool operator<=(const circle_event &c_event) const {
+            return !(c_event < (*this));
+        }
+
+        bool operator>(const circle_event &c_event) const {
+            return c_event < (*this);
+        }
+
+        bool operator>=(const circle_event &c_event) const {
+            return !((*this) < c_event);
+        }
+
+        // Compares bottom voronoi circle point with site event point.
+        // If circle point is less then site point return -1.
+        // If circle point is equal to site point return 0.
+        // If circle point is greater then site point return 1.
+        int compare(const site_event<T> &s_event) const {
+            if (s_event.x() < center_.x())
+                return 1;
+            T sqr_dif_x = (s_event.x() - center_.x()) * (s_event.x() - center_.x());
+            if (sqr_dif_x == sqr_radius_) {
+                if (center_.y() == s_event.y())
+                    return 0;
+                return (center_.y() < s_event.y()) ? -1 : 1;
+            }
+            return (sqr_dif_x < sqr_radius_) ? 1 : -1;
+        }
+
+        coordinate_type x() const {
+            return center_.x();
+        }
+
+        coordinate_type y() const {
+            return center_.y();
+        }
+
+        const point_2d<T> &get_center() const {
+            return center_;
+        }
+
+        const T &get_sqr_radius() const {
+            return sqr_radius_;
+        }
+
+        void set_bisector(beach_line_iterator iterator) {
+            bisector_node_ = iterator;
+        }
+
+        const beach_line_iterator &get_bisector() const {
+            return bisector_node_;
+        }
+    private:
+        point_2d<T> center_;
+        T sqr_radius_;
+        beach_line_iterator bisector_node_;
+    };
+
+    template <typename T>
+    circle_event<T> make_circle_event(T center_x, T center_y, T sqr_radius) {
+        return circle_event<T>(center_x, center_y, sqr_radius);
+    }
+
+    ///////////////////////////////////////////////////////////////////////////
+    // VORONOI OUTPUT TYPES ///////////////////////////////////////////////////
+    ///////////////////////////////////////////////////////////////////////////
+    
+    template <typename Point2D>
+    struct half_edge;
+
+    // Cell record data structure. Represents voronoi cell.
+    // Contains site point and pointer to any incident half-edge.
+    template <typename Point2D>
+    struct cell_record {
+        half_edge<Point2D> *incident_edge;
+        Point2D site_point;
+
+        cell_record(Point2D site, half_edge<Point2D>* edge) : incident_edge(edge), site_point(site) {}
+    };
+
+    // Voronoi vertex data structure. Represents voronoi vertex.
+    // Contains vertex coordinates and pointers to all incident half-edges.
+    template <typename Point2D>
+    struct vertex_record {
+        std::list< half_edge<Point2D>* > incident_edges;
+        Point2D vertex;
 
+        vertex_record(Point2D vertex) : vertex(vertex) {}
+    };
+
+    // Half-edge data structure. Represents voronoi edge.
+    // Contains: 1) pointer to cell records;
+    //           2) pointers to start/end vertices of half-edge;
+    //           3) pointers to previous/next half-edges(CCW);
+    //           4) pointer to twin half-edge.
+    template <typename Point2D>
+    struct half_edge {
+        typedef typename cell_record<Point2D> cell_record_type;
+        typedef typename vertex_record<Point2D> vertex_record_type;
+        typedef typename half_edge<Point2D> half_edge_type;
+
+        cell_record_type *cell_record;
+        vertex_record_type *start_point;
+        vertex_record_type *end_point;
+        half_edge_type *prev;
+        half_edge_type *next;
+        half_edge_type *twin;
+
+        half_edge(int site_index) :
+            cell_record(NULL),
+            start_point(NULL),
+            end_point(NULL),
+            prev(NULL),
+            next(NULL),
+            twin(NULL) {}
+    };
+
+    // Voronoi output data structure based on the half-edges.
+    // Contains vector of voronoi cells, doubly linked list of
+    // voronoi vertices and voronoi edges.
+    template <typename Point2D>
+    class voronoi_output {
+    public:
+        typedef typename Point2D::site_event_type site_event_type;
+        typedef typename Point2D::circle_event_type circle_event_type;
+        typedef typename cell_record<Point2D> cell_record_type;
+        typedef typename vertex_record<Point2D> vertex_record_type;
+        typedef typename half_edge<Point2D> edge_type;
+        typedef typename std::vector<cell_record_type> cell_records;
+        typedef typename std::list<vertex_record_type> voronoi_vertices;
+        typedef typename std::list<edge_type *>::const_iterator edge_iterator;
+        typedef typename voronoi_vertices::const_iterator voronoi_vertices_iterator;
+
+        voronoi_output() {}
+
+        // This preserves the validity of iterators.
+        void init(int num_sites) {
+            cell_records_.reserve(num_sites);
+        }
+
+        void reset() {
+            cell_records_.clear();
+            vertex_records_.clear();
+            edges_.clear();
+        }
+
+        // Inserts new half-edge into the output data structure during site
+        // event processing. Takes as input left and right sites of the new
+        // beach line node and returns reference to the new half-edge. 
+        // Second argument is new site. During this step we add two new
+        // twin half-edges.
+        edge_type *insert_new_edge(const site_event_type &site1,
+                                   const site_event_type &site2) {
+            // Get indexes of sites.                                           
+            int site_index1 = site1.get_site_index();
+            int site_index2 = site2.get_site_index();
+
+            // Create new half-edge that belongs to the cell with the first site.
+            edges_.push_back(edge_type(site_index1));
+            edge_type &edge1 = edges_.back();
+
+            // Create new half-edge that belongs to the cell with the second site.
+            edges_.push_back(edge_type(site_index2));
+            edge_type &edge2 = edges_.back();
+
+            // Add initial cell during first edge insertion.
+            if (cell_records_.empty())
+                cell_records_.push_back(cell_record_type(site1.get_point(), &edge1));
+
+            // Second site represents new site during site event processing.
+            // Add new cell to the cell records vector.
+            cell_records_.push_back(cell_record_type(site2.get_point(), &edge2));
+
+            // Update pointers to cells.
+            edge1.cell_record = &cell_records_[site_index1];
+            edge2.cell_record = &cell_records_[site_index2];
+
+            // Update twin pointers.
+            edge1.twin = &edge2;
+            edge2.twin = &edge1;
+
+            return &edge1;
+        }
+
+        edge_type *insert_new_edge(const site_event_type &site1,
+                                   const site_event_type &site2,
+                                   const site_event_type &site3,
+                                   const circle_event_type &circle,
+                                   edge_type *edge12,
+                                   edge_type *edge23) {
+            // Add new voronoi vertex as voronoi circle center.
+            vertex_records_.push_back(vertex_record_type(circle.get_center()));
+            vertex_record_type &new_vertex = vertex_records_.back();
+
+            // Update two input bisectors and their twins half-edges with
+            // new voronoi vertex.
+            edge12->start_point = &new_vertex;
+            edge12->twin->end_point = &new_vertex;
+            edge23->start_point = &new_vertex;
+            edge23->twin->end_point = &new_vertex;
+
+            // Add new half-edge.
+            edges_.push_back(edge_type(site1.get_site_index()));
+            edge_type &new_edge1 = edges_.back();
+            new_edge1.cell_record = &cell_records_[site1.get_site_index()];
+            new_edge1.end_point = &new_vertex;
+
+            // Add new half-edge.
+            edges_.push_back(edge_type(site3.get_site_index()));
+            edge_type &new_edge2 = edges_.back();
+            new_edge2.cell_record = &cell_records_[site3.get_site_index()];
+            new_edge2.start_point = &new_vertex;
+
+            // Update twin pointers of the new half-edges.
+            new_edge1.twin = &new_edge2;
+            new_edge2.twin = &new_edge1;
+
+            // Update voronoi prev/next pointers of all half-edges incident
+            // to the new voronoi vertex.
+            edge12->prev = &new_edge1;
+            new_edge1.next = edge12;
+            edge12->twin->next = edge23;
+            edge23->prev = edge12->twin;
+            edge23->twin->next = &new_edge2;
+            new_edge2.prev = edge23->twin;
+
+            // Update voronoi vertex incident edges pointers.
+            new_vertex.incident_edges.push_back(edge12);
+            new_vertex.incident_edges.push_back(edge23);
+            new_vertex.incident_edges.push_back(&new_edge2);
+            return &new_edge1;
+        }
+
+        const cell_records &get_cell_records() const {
+            return cell_records_;
+        }
+
+        const voronoi_vertices &get_voronoi_vertices() const {
+            return vertex_records_;
+        }
+
+    private:
+        std::vector<cell_record_type> cell_records_;
+        std::list<vertex_record_type> vertex_records_;
+        std::list<edge_type> edges_;
+
+        //Disallow copy constructor and operator=
+        voronoi_output(const voronoi_output&);
+        void operator=(const voronoi_output&);
+    };
+
+    ///////////////////////////////////////////////////////////////////////////
+    // VORONOI CIRCLE EVENTS QUEUE ////////////////////////////////////////////
+    ///////////////////////////////////////////////////////////////////////////
+    
+    // Event queue data structure, processes circle events.
+    template <typename Point2D>
+    class circle_events_queue {
+    public:
+        typedef typename Point2D::coordinate_type coordinate_type;
+        typedef typename Point2D::circle_event_type circle_event_type;
+
+        circle_events_queue() {}
+
+        void reset() {
+            while (!circle_events_.empty())
+                circle_events_.pop();
+            while (!deactivated_events_.empty())
+                deactivated_events_.pop();
+        }
+
+        bool empty() {
+            remove_not_active_events();
+            if (!circle_events_.empty())
+                return false;
+            return true;
+        }
+
+        circle_event_type &top() {
+            remove_not_active_events();
+            return circle_events_.top();
+        }
+
+        void pop() {
+            remove_not_active_events();
+            circle_events_.pop();
+        }
+
+        void push(const circle_event_type &circle_event) {
+            circle_events_.push(circle_event);
+        }
+
+        void deactivate_event(const circle_event_type &circle_event) {
+            deactivated_events_.push(circle_event);
+        }
+
+    private:
+        void remove_not_active_events() {
+            while (!circle_events_.empty() && !deactivated_events_.empty() &&
+                   circle_events_.top().equals(deactivated_events_.top())) {
+                circle_events_.pop();
+                deactivated_events_.pop();
+            }
+        }
+
+        std::priority_queue< circle_event_type,
+                             std::vector<circle_event_type>,
+                             std::greater<circle_event_type> > circle_events_;
+        std::priority_queue< circle_event_type,
+                             std::vector<circle_event_type>,
+                             std::greater<circle_event_type> > deactivated_events_;
+
+        //Disallow copy constructor and operator=
+        circle_events_queue(const circle_events_queue&);
+        void operator=(const circle_events_queue&);
+    };
+
+    /////////////////////////////////////////////////////////////////////////////
+    // VORONOI BEACH LINE TYPES /////////////////////////////////////////////////
+    /////////////////////////////////////////////////////////////////////////////
+    
     // Represents bisector made by two arcs that correspond to the left and
     // right sites. Arc is defined as curve with points equidistant from the
     // site and from the sweepline.
@@ -166,351 +727,9 @@
                 return !node2.less(node1.get_new_site());
         }
     };
-
-    // Voronoi diagram formation. Sweepline sweeps from left to right.
-    template <typename T>
-    class voronoi_formation {
-    public:
-        typedef typename point_2d<T> Point2D;
-        typedef typename Point2D::coordinate_type coordinate_type;
-        typedef typename Point2D::site_event_type site_event_type;
-        typedef typename Point2D::circle_event_type circle_event_type;
-
-        typedef typename voronoi_output<Point2D> Output;
-        typedef typename Output::edge_type edge_type;
-        typedef typename Output::edge_iterator edge_iterator;
-        typedef typename Output::cell_records cell_records;
-        typedef typename Output::voronoi_vertices voronoi_vertices;
-        typedef typename voronoi_vertices::const_iterator voronoi_vertices_iterator;
-
-        typedef typename event_queue<Point2D> EventQueue;
-        typedef typename beach_line_node<Point2D> Key;
-        typedef typename beach_line_node_data<Point2D> Value;
-        typedef typename node_comparer<Key> NodeComparer;
-        typedef typename std::map< Key, Value, NodeComparer > BeachLine;
-        typedef typename BeachLine::const_iterator beach_line_iterator;
-
-        // Functor to process events from the event queue.
-        struct event_processor {
-            event_processor() : beach_line_(NULL) {} 
-
-            void operator()(const site_event_type &site_event) {
-                beach_line_->process_site_event(site_event);
-            }
-
-            void operator()(const circle_event_type &circle_event) {
-                beach_line_->process_circle_event(circle_event);
-            }
-
-            voronoi_formation *beach_line_;
-        };
-
-        voronoi_formation() : event_processor_() {}
-
-        // Init beach line before sweepline run.
-        // In case of a few first sites situated on the same
-        // vertical line, we init beach line with all of them.
-        // In other case just use the first two sites for the initialization.
-        void init(std::vector<Point2D> &sites) {
-            output_.init(sites.size());
-
-            // Init beach_line pointer in the event_processor data sturcture.
-            // This is done here to avoid compiler warning in the constructor.
-            event_processor_.beach_line_ = this;
-            
-            // Sort all sites.
-            std::sort(sites.begin(), sites.end());
-            int skip = 0;
-
-            if (sites.size() == 1) {
-                skip = 1;
-            } else {
-                std::vector<Point2D>::const_iterator it = sites.begin();
-                while(it != sites.end() && it->x() == sites.begin()->x()) {
-                    it++;
-                    skip++;
-                }
-
-                if (skip == 1) {
-                    // Init beach line with two sites.
-                    init_beach_line(*sites.begin(), *it);
-
-                    // Skip the second point also.
-                    skip++;
-                } else {
-                    // Init beach line with sites situated on the same vertical line.
-                    init_beach_line(sites.begin(), it);
-                }
-            }
-            // Init event queue with the rest of the sites.
-            event_queue_.init(sites, skip);
-        }
-
-        void reset() {
-            event_queue_.reset();
-            beach_line_.clear();
-            output_.clear();
-        }
-
-        void run_sweepline() {
-            // Algorithm stops when there are no events in the queue.
-            while (!event_queue_.empty()) {
-                event_queue_.process_top_event(event_processor_);
-                event_queue_.pop();
-            }
-        }
-
-        // Uses special comparison function for the lower bound and insertion
-        // operations.
-        void process_site_event(const site_event_type &site_event) {
-            // Find the node in the binary search tree with left arc
-            // lying above the new site point.
-            Key new_key(site_event);
-            beach_line_iterator it = beach_line_.lower_bound(new_key);
-
-            site_event_type site_arc;
-            if (it == beach_line_.end()) {
-                it--;
-                site_arc = it->first.get_right_site();
-
-                // Insert new arc into the sweepline.
-                beach_line_iterator new_node_it = insert_new_arc(site_arc, site_event);
-                new_node_it--;
-
-                // Add candidate circle to the event queue.
-                activate_circle_event(it->first.get_left_site(),
-                                      it->first.get_right_site(),
-                                      site_event,
-                                      new_node_it);
-            } else if (it == beach_line_.begin()) {
-                site_arc = it->first.get_left_site();
-
-                // Insert new arc into the sweepline.
-                beach_line_iterator new_node_it = insert_new_arc(site_arc, site_event);
-                new_node_it++;
-
-                // Add candidate circle to the event queue.
-                activate_circle_event(site_event,
-                                      it->first.get_left_site(),
-                                      it->first.get_right_site(),
-                                      new_node_it);
-            } else {
-                site_arc = it->first.get_left_site();
-
-                // Insert new arc into the sweepline.
-                beach_line_iterator new_node_it = insert_new_arc(site_arc, site_event);
-
-                const site_event_type &site2 = it->first.get_left_site();
-                const site_event_type &site3 = it->first.get_right_site();
-                it--;
-                const site_event_type &site1 = it->first.get_right_site();
-
-                // Remove candidate circle from the event queue.
-                deactivate_circle_event(site1, site2, site3);
-
-                // Add candidate circles to the event queue.
-                new_node_it--;
-                activate_circle_event(site1, site2, site_event, new_node_it);
-                new_node_it++;
-                new_node_it++;
-                activate_circle_event(site_event, site2, site3, new_node_it);
-            }               
-        }
-
-        // Doesn't use special comparison function as it works fine only for
-        // the site events processing.
-        void process_circle_event(const circle_event_type &circle_event) {
-            // Retrieve the second bisector node that corresponds to the given
-            // circle event.
-            beach_line_iterator it_first = circle_event.get_bisector();
-            beach_line_iterator it_last = it_first;
-
-            // Get the second and the third sites that create given circle event.
-            site_event_type site2 = it_first->first.get_left_site();
-            site_event_type site3 = it_first->first.get_right_site();
-
-            // Get second bisector;
-            Value bisector2 = it_first->second;
-            
-            // Get first bisector;
-            it_first--;
-            Value bisector1 = it_first->second;
-            
-            // Get the first site that creates given circle event.
-            site_event_type site1 = it_first->first.get_left_site();
-
-            // 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 nodes 
-            // comparer doesn't work fine for the circle events. We only 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.
-            const_cast<Key &>(it_first->first).set_right_site(it_last->first.get_right_site());
-            edge_type *edge = output_.insert_new_edge(site1, site2, site3, circle_event, bisector1.edge, bisector2.edge);
-            const_cast<Value &>(it_first->second).change_edge(edge);
-            beach_line_.erase(it_last);
-            it_last = it_first;
-
-            // Check the new triplets formed by the neighboring arcs
-            // for potential circle events. Check left.
-            if (it_first != beach_line_.begin()) {
-                it_first--;
-                const site_event_type &site_l1 = it_first->first.get_left_site();
-                deactivate_circle_event(site_l1, site1, site2);
-                if (it_first != beach_line_.begin()) {
-                    it_first--;
-                    const site_event_type &site_l2 = it_first->first.get_left_site();
-                    it_first++;
-                    activate_circle_event(site_l2, site_l1, site1, it_first);
-                }
-            }
-
-            // Check the new triplets formed by the neighboring arcs
-            // for potential circle events. Check right.
-            it_last++;
-            if (it_last != beach_line_.end()) {
-                const site_event_type &site_r1 = it_last->first.get_right_site();
-                deactivate_circle_event(site2, site3, site_r1);
-                it_last++;
-                if (it_last != beach_line_.end()) {
-                    it_last++;
-                    const site_event_type &site_r2 = it_last->first.get_right_site();
-                    activate_circle_event(site3, site_r1, site_r2, it_last);
-                }
-            }            
-        }
-
-        const cell_records &get_cell_records() const {
-            return output_.get_cell_records();
-        }
-
-        const voronoi_vertices &get_voronoi_vertices() const {
-            return output_.get_voronoi_vertices();
-        }
-
-    protected:
-        void init_beach_line(typename std::vector<Point2D>::const_iterator it_begin,
-                             typename std::vector<Point2D>::const_iterator it_end) {
-             typename std::vector<Point2D>::const_iterator it_first = it_begin;
-             typename std::vector<Point2D>::const_iterator it_second = it_begin;
-             it_second++;
-             int cur_site = 0;
-             while (it_second != it_end) {
-                 site_event_type site1 = make_site_event<coordinate_type>(
-                     it_first->x(), it_first->y(), cur_site);
-                 site_event_type site2 = make_site_event<coordinate_type>(
-                     it_second->x(), it_second->y(), cur_site+1);
-
-                 // Create new beach line node.
-                 Key new_node(site1, site2);
-                 
-                 // Update output.
-                 edge_type *edge = output_.insert_new_edge(site1, site2);
-
-                 // Insert new node into the binary search tree.
-                 beach_line_.insert(std::pair<Key, Value>(new_node, Value(edge)));
-                 
-                 // Update iterators.
-                 it_first++;
-                 it_second++;
-                 cur_site++;
-             }
-        }
-
-        void init_beach_line(const Point2D &first_point,
-                             const Point2D &second_point) {
-            site_event_type site1 = make_site_event<coordinate_type>(
-                first_point.x(), first_point.y(), 0);
-            site_event_type site2 = make_site_event<coordinate_type>(
-                second_point.x(), second_point.y(), 1);
-
-            // Create two new beach line nodes.
-            Key new_left_node(site1, site2);
-            Key new_right_node(site2, site1);
-
-            // Update output.
-            edge_type *edge = output_.insert_new_edge(site1, site2);
-
-            // Insert two new nodes into the binary search tree.
-            beach_line_.insert(std::pair<Key, Value>(new_left_node, Value(edge)));
-            beach_line_.insert(std::pair<Key, Value>(new_right_node, Value(edge->twin)));
-        }
-
-        // Insert new arc below site arc into the beach line.
-        beach_line_iterator insert_new_arc(const site_event_type &site_arc,
-                                           const site_event_type &site_event) {
-            // Create two new nodes.
-            Key new_left_node(site_arc, site_event);
-            Key new_right_node(site_event, site_arc);
-            int site_index1 = site_arc.get_site_index();
-            int site_index2 = site_event.get_site_index();
-            
-            // Insert two new nodes into the binary search tree.
-            // Update output.
-            edge_type *edge = output_.insert_new_edge(site_arc, site_event);
-            beach_line_.insert(std::pair<Key, Value>(new_left_node, Value(edge)));
-            return beach_line_.insert(std::pair<Key, Value>(new_right_node, Value(edge->twin))).first;
-        }
-
-        // Create circle event from the given three points.
-        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 {
-            coordinate_type a = (site1.x() - site2.x()) * (site2.y() - site3.y()) -
-                                (site1.y() - site2.y()) * (site2.x() - site3.x());
-            // Check if bisectors intersect.
-            if (a >= static_cast<coordinate_type>(0))
-                return false;
-            coordinate_type b1 = (site1.x() - site2.x()) * (site1.x() + site2.x())+
-                                 (site1.y() - site2.y()) * (site1.y() + site2.y());
-            coordinate_type b2 = (site2.x() - site3.x()) * (site2.x() + site3.x())+
-                                 (site2.y() - site3.y()) * (site2.y() + site3.y());
-            coordinate_type c_x = (b1*(site2.y() - site3.y()) - b2*(site1.y() - site2.y())) / a *
-                                  static_cast<coordinate_type>(0.5);
-            coordinate_type c_y = (b2*(site1.x() - site2.x()) - b1*(site2.x() - site3.x())) / a *
-                                   static_cast<coordinate_type>(0.5);
-            coordinate_type sqr_radius = (c_x-site1.x())*(c_x-site1.x()) +
-                                         (c_y-site1.y())*(c_y-site1.y());
-            // Create new circle event;
-            c_event = make_circle_event(c_x, c_y, sqr_radius);
-            return true;
-        }
-
-        // Add new circle event to the event queue.
-        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;
-            if (create_circle_event(site1, site2, site3, c_event)) {
-                c_event.set_bisector(bisector_node);
-                event_queue_.push(c_event);
-            }
-        }
-
-        // Remove circle event from the event queue.
-        void deactivate_circle_event(const site_event_type &point1,
-                                     const site_event_type &point2,
-                                     const site_event_type &point3) {
-            circle_event_type c_event;
-            if (create_circle_event(point1, point2, point3, c_event))
-                event_queue_.deactivate_event(c_event);
-        }
-
-    private:
-        EventQueue event_queue_;
-        event_processor event_processor_;
-        BeachLine beach_line_;
-        Output output_;
-
-        //Disallow copy constructor and operator=
-        voronoi_formation(const voronoi_formation&);
-        void operator=(const voronoi_formation&);
-    };
-
+  
 } // sweepline
 } // boost
+} // detail
 
-#endif
\ No newline at end of file
+#endif

Deleted: sandbox/SOC/2010/sweepline/boost/sweepline/event_queue.hpp
==============================================================================
--- sandbox/SOC/2010/sweepline/boost/sweepline/event_queue.hpp	2010-06-21 09:47:45 EDT (Mon, 21 Jun 2010)
+++ (empty file)
@@ -1,141 +0,0 @@
-// Boost sweepline/event_queue.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_EVENT_QUEUE
-#define BOOST_SWEPPLINE_EVENT_QUEUE
-
-#include <queue>
-
-namespace boost {
-namespace sweepline {
-
-    // Event queue data structure, contains two types of events:
-    // site events and circle events.
-    template <typename Point2D>
-    class event_queue {
-    public:
-        typedef typename Point2D::coordinate_type coordinate_type;
-        typedef typename Point2D::site_event_type site_event_type;
-        typedef typename Point2D::circle_event_type circle_event_type;
-
-        enum kEventType {
-            SITE_EVENT = 0,
-            CIRCLE_EVENT = 1,
-            NONE = 2,
-        };
-
-        event_queue() {
-            site_events_iterator_ = site_events_.begin();
-        }
-
-        // Init event queue with sites, starting from the element with
-        // skip index. Vector of sites should be sorted.
-        void init(const std::vector<Point2D> &sites, int skip) {
-            site_events_.clear();
-            site_events_.resize(sites.size() - skip);
-            std::vector<Point2D>::const_iterator sites_it;
-            int index = 0;
-            for (sites_it = sites.begin() + skip; sites_it != sites.end(); sites_it++, index++)
-                site_events_[index] = make_site_event(sites_it->x(),
-                                                      sites_it->y(),
-                                                      index + skip);
-            init_site_events();
-        }
-
-        void reset() {
-            site_events_iterator_ = site_events_.begin();
-            while (!circle_events_.empty())
-                circle_events_.pop();
-            while (!deactivated_events_.empty())
-                deactivated_events_.pop();
-        }
-
-        bool empty() {
-            if (site_events_iterator_ != site_events_.end())
-                return false;
-            remove_not_active_events();
-            if (!circle_events_.empty())
-                return false;
-            return true;
-        }
-
-        template <typename event_handler>
-        void process_top_event(event_handler &functor) {
-            kEventType top_event_type = get_top_event_type();
-            if (top_event_type == SITE_EVENT)
-                functor(*site_events_iterator_);
-            else
-                functor(circle_events_.top());
-        }
-
-        void pop() {
-            kEventType top_event_type = get_top_event_type();
-            if (top_event_type == SITE_EVENT)
-                site_events_iterator_++;
-            else if (top_event_type == CIRCLE_EVENT)
-                circle_events_.pop();
-        }
-
-        void push(const circle_event_type &circle_event) {
-            circle_events_.push(circle_event);
-        }
-
-        void deactivate_event(const circle_event_type &circle_event) {
-            deactivated_events_.push(circle_event);
-        }
-
-    private:
-        void init_site_events() {
-            site_events_iterator_ = site_events_.begin();
-        }
-
-        void remove_not_active_events() {
-            while (!circle_events_.empty() && !deactivated_events_.empty() &&
-                   circle_events_.top().equals(deactivated_events_.top())) {
-                circle_events_.pop();
-                deactivated_events_.pop();
-            }
-        }
-
-        kEventType get_top_event_type() {
-            remove_not_active_events();
-            if (site_events_iterator_ == site_events_.end())
-                return CIRCLE_EVENT;
-            else if (circle_events_.empty())
-                return SITE_EVENT;
-            else {
-                // If two event points have the same coordinates return
-                // site event at first.
-                if (circle_events_.top().compare(*site_events_iterator_) >= 0)
-                    return SITE_EVENT;
-                else
-                    return CIRCLE_EVENT;
-            }
-            return NONE;
-        }
-
-        typename std::vector<site_event_type>::const_iterator 
-            site_events_iterator_;
-        std::vector<site_event_type> site_events_;
-        std::priority_queue< circle_event_type,
-                             std::vector<circle_event_type>,
-                             std::greater<circle_event_type> > circle_events_;
-        std::priority_queue< circle_event_type,
-                             std::vector<circle_event_type>,
-                             std::greater<circle_event_type> > deactivated_events_;
-
-        //Disallow copy constructor and operator=
-        event_queue(const event_queue&);
-        void operator=(const event_queue&);
-    };
-
-} // sweepline
-} // boost
-
-#endif
\ No newline at end of file

Deleted: sandbox/SOC/2010/sweepline/boost/sweepline/event_types.hpp
==============================================================================
--- sandbox/SOC/2010/sweepline/boost/sweepline/event_types.hpp	2010-06-21 09:47:45 EDT (Mon, 21 Jun 2010)
+++ (empty file)
@@ -1,311 +0,0 @@
-// Boost sweepline/event_types.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_EVENT_TYPES
-#define BOOST_SWEEPLINE_EVENT_TYPES
-
-namespace boost {
-namespace sweepline {
-    
-    template <typename T>
-    struct site_event;
-    
-    template <typename T>
-    struct circle_event;
-
-    template <typename T>
-    class voronoi_formation;
-
-    // Point in 2D space data structure. Comparators defined in this
-    // data structure actually define sweepline movement direction.
-    template <typename T>
-    struct point_2d {
-    public:
-        typedef T coordinate_type;
-        typedef site_event<T> site_event_type;
-        typedef circle_event<T> circle_event_type;
-
-        point_2d() {}
-
-        point_2d(T x, T y) {
-            x_ = x;
-            y_ = y;
-        }
-
-        bool operator==(const point_2d &point) const {
-            return (this->x_ == point.x()) && (this->y_ == point.y());
-        }
-
-        bool operator!=(const point_2d &point) const {
-            return (this->x_ != point.x()) || (this->y_ != point.y());
-        }
-
-        // This comparator actually defines sweepline movement direction.
-        bool operator<(const point_2d &point) const {
-            // Sweepline sweeps from left to right.
-            if (this->x_ != point.x_)
-                return this->x_ < point.x_;
-            return this->y_ < point.y_;
-        }
-
-        bool operator<=(const point_2d &point) const {
-            return !(point < (*this));
-        }
-
-        bool operator>(const point_2d &point) const {
-            return point < (*this);
-        }
-
-        bool operator>=(const point_2d &point) const {
-            return !((*this) < point);
-        }
-
-        coordinate_type x() const {
-            return this->x_;
-        }
-
-        coordinate_type y() const {
-            return this->y_;
-        }
-
-        void x(coordinate_type x) {
-            x_ = x;
-        }
-
-        void y(coordinate_type y) {
-            y_ = y;
-        }
-
-    private:
-        coordinate_type x_;
-        coordinate_type y_;
-    };
-
-    template <typename T>
-    point_2d<T> make_point_2d(T x, T y) {
-        return point_2d<T>(x,y);
-    }
-
-    // Site event type. 
-    // Occurs when sweepline sweeps over one of the initial sites.
-    // Contains index of a site below the other sorted sites.
-    template <typename T>
-    struct site_event {
-    public:
-        typedef T coordinate_type;
-
-        site_event() {}
-        
-        site_event(T x, T y, int index) : point_(x, y), site_index_(index) {}
-
-        bool operator==(const site_event &s_event) const {
-            return point_ == s_event.get_point();
-        }
-
-        bool operator!=(const site_event &s_event) const {
-            return point_ != s_event.get_point();
-        }
-
-        bool operator<(const site_event &s_event) const {
-            return point_ < s_event.get_point();
-        }
-
-        bool operator<=(const site_event &s_event) const {
-            return point_ <= s_event.get_point();
-        }
-
-        bool operator>(const site_event &s_event) const {
-            return point_ > s_event.get_point();
-        }
-
-        bool operator>=(const site_event &s_event) const {
-            return point_ >= s_event.get_point();
-        }
-
-        coordinate_type x() const {
-            return point_.x();
-        }
-
-        coordinate_type y() const {
-            return point_.y();
-        }
-
-        const point_2d<T> &get_point() const {
-            return point_;
-        }
-
-        int get_site_index() const {
-            return site_index_;
-        }
-
-    private:
-        point_2d<T> point_;
-        int site_index_;
-    };
-
-    template <typename T>
-    site_event<T> make_site_event(T x, T y, int index) {
-        return site_event<T>(x, y, index);
-    }
-
-    // Circle event type. Occurs when sweepline sweeps over the bottom point of
-    // the voronoi circle (with center at the bisectors intersection point).
-    // Circle event contains circle center and squared radius (to avoid sqrt
-    // computation). To compare bottom points of two different voronoi circles
-    // we don't compute exact radius and use special arithmetic for that. This 
-    // way voronoi diagram implementation may be used with rational arithmetic.
-    // Let circle center coordinates be (x, y), squared radius be r. 
-    // Bottom point of the voronoi circle will be defined as (x + sqrt(r), y).
-    // Contains reference to the second bisector node (ordered from left to
-    // right in the beach line) that creates given circle event.
-    template <typename T>
-    struct circle_event {
-    public:
-        typedef T coordinate_type;
-        typedef typename voronoi_formation<T>::beach_line_iterator
-            beach_line_iterator;
-
-        circle_event() {}
-
-        circle_event(T c_x, T c_y, T sqr_r) :
-        center_(c_x, c_y), sqr_radius_(sqr_r) {}
-
-        bool equals(const circle_event &c_event) const {
-            return center_.x() == c_event.x() && center_.y() == c_event.y() &&
-                   sqr_radius_ == c_event.get_sqr_radius();
-        }
-
-        bool operator==(const circle_event &c_event) const {
-            if (center_.y() != c_event.y())
-                return false;
-
-            T sqr_dif_x = (center_.x() - c_event.x()) *
-                          (center_.x() - c_event.x());
-            T sum_r_sqr = sqr_radius_ + c_event.get_sqr_radius();
-            T value_left = (sum_r_sqr - sqr_dif_x) * (sum_r_sqr - sqr_dif_x);
-            T value_right = static_cast<T>(4) * sqr_radius_ *
-                            c_event.get_sqr_radius();
-
-            return value_left == value_right;
-        }
-
-        bool operator!=(const circle_event &c_event) const {
-            return !((*this) == c_event);
-        }
-
-        bool operator<(const circle_event &c_event) const {
-            T x1 = center_.x();
-            T y1 = center_.y();
-            T sqr_r1 = sqr_radius_;
-            T x2 = c_event.x();
-            T y2 = c_event.y();
-            T sqr_r2 = c_event.get_sqr_radius();
-
-            T sqr_dif_x = (x1 - x2) * (x1 - x2);
-            T sum_r_sqr = sqr_r1 + sqr_r2;
-            T value_left = (sum_r_sqr - sqr_dif_x) * (sum_r_sqr - sqr_dif_x);
-            T value_right = static_cast<T>(4) * sqr_r1 * sqr_r2;
-            
-            if (x1 > x2) {
-                if (sqr_r2 <= sqr_r1)
-                    return false;
-                
-                if (sqr_dif_x >= sum_r_sqr)
-                    return false;
-
-                if (value_left == value_right)
-                    return y1 < y2;
-                else
-                    return value_left > value_right;
-            }
-            else if (x1 < x2) {
-                if (sqr_r1 <= sqr_r2)
-                    return true;
-
-                if (sqr_dif_x >= sum_r_sqr)
-                    return true;
-
-                if (value_left == value_right)
-                    return y1 < y2;
-                else
-                    return value_left < value_right;
-            }
-            else {
-                if (sqr_r1 != sqr_r2)
-                    return sqr_r1 < sqr_r2;
-                return y1 < y2;
-            }
-        }
-
-        bool operator<=(const circle_event &c_event) const {
-            return !(c_event < (*this));
-        }
-
-        bool operator>(const circle_event &c_event) const {
-            return c_event < (*this);
-        }
-
-        bool operator>=(const circle_event &c_event) const {
-            return !((*this) < c_event);
-        }
-
-        // Compares bottom voronoi circle point with site event point.
-        // If circle point is less then site point return -1.
-        // If circle point is equal to site point return 0.
-        // If circle point is greater then site point return 1.
-        int compare(const site_event<T> &s_event) const {
-            if (s_event.x() < center_.x())
-                return 1;
-            T sqr_dif_x = (s_event.x() - center_.x()) * (s_event.x() - center_.x());
-            if (sqr_dif_x == sqr_radius_) {
-                if (center_.y() == s_event.y())
-                    return 0;
-                return (center_.y() < s_event.y()) ? -1 : 1;
-            }
-            return (sqr_dif_x < sqr_radius_) ? 1 : -1;
-        }
-
-        coordinate_type x() const {
-            return center_.x();
-        }
-
-        coordinate_type y() const {
-            return center_.y();
-        }
-
-        const point_2d<T> &get_center() const {
-            return center_;
-        }
-
-        const T &get_sqr_radius() const {
-            return sqr_radius_;
-        }
-
-        void set_bisector(beach_line_iterator iterator) {
-            bisector_node_ = iterator;
-        }
-
-        const beach_line_iterator &get_bisector() const {
-            return bisector_node_;
-        }
-    private:
-        point_2d<T> center_;
-        T sqr_radius_;
-        beach_line_iterator bisector_node_;
-    };
-
-    template <typename T>
-    circle_event<T> make_circle_event(T center_x, T center_y, T sqr_radius) {
-        return circle_event<T>(center_x, center_y, sqr_radius);
-    }
-  
-} // sweepline
-} // boost
-
-#endif
\ No newline at end of file

Added: sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_builder.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_builder.hpp	2010-06-21 09:47:45 EDT (Mon, 21 Jun 2010)
@@ -0,0 +1,372 @@
+// 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.
+
+#include "detail/voronoi_formation.hpp"
+
+#ifndef BOOST_SWEEPLINE_VORONOI_BUILDER
+#define BOOST_SWEEPLINE_VORONOI_BUILDER
+
+namespace boost {
+namespace sweepline {
+    
+    using namespace detail;
+
+    // Voronoi diagram builder. Sweepline sweeps from left to right.
+    template <typename T>
+    class voronoi_builder {
+    public:
+        typedef typename point_2d<T> Point2D;
+        typedef typename Point2D::coordinate_type coordinate_type;
+
+        typedef typename voronoi_output<Point2D>::edge_type edge_type;
+        typedef typename voronoi_output<Point2D>::edge_iterator edge_iterator;
+        typedef typename voronoi_output<Point2D>::cell_records cell_records;
+        typedef typename voronoi_output<Point2D>::voronoi_vertices voronoi_vertices;
+        typedef typename voronoi_vertices::const_iterator voronoi_vertices_iterator;
+
+        voronoi_builder() {}
+
+        // Init beach line before sweepline run.
+        // In case of a few first sites situated on the same
+        // vertical line, we init beach line with all of them.
+        // In other case just use the first two sites for the initialization.
+        void init(std::vector<Point2D> &sites) {
+            // Sort all sites.
+            std::sort(sites.begin(), sites.end());
+
+            // Add all unique sites to the site events vector.
+            int site_event_index = 0;
+            int sz = sites.size();
+            for (int i = 0; i < sz; i++) {
+                if (!i || sites[i] != sites[i-1]) {
+                    site_events_.push_back(make_site_event(sites[i].x(), sites[i].y(),
+                                                          site_event_index));
+                    site_event_index++;
+                }
+            }
+
+            // Init output with number of site events.
+            output_.init(site_events_.size());
+
+            // Set sites iterator.
+            site_events_iterator_ = site_events_.begin();
+            
+            int skip = 0;
+            if (site_events_.size() == 1) {
+                skip = 1;
+                site_events_iterator_++;
+            } else {
+                while(site_events_iterator_ != site_events_.end() &&
+                      site_events_iterator_->x() == site_events_.begin()->x()) {
+                    site_events_iterator_++;
+                    skip++;
+                }
+
+                if (skip == 1) {
+                    // Init beach line with two sites.
+                    init_beach_line();
+
+                    // Skip the second point also.
+                    site_events_iterator_++;
+                } else {
+                    // Init beach line with sites situated on the same vertical line.
+                    init_beach_line_colinear_sites();
+                }
+            }
+        }
+
+        void reset() {
+            site_events_.clear();
+            site_events_iterator_ = site_events_.begin();
+            circle_events_.reset();
+            beach_line_.clear();
+            output_.clear();
+        }
+
+        void run_sweepline() {
+            // Algorithm stops when there are no events to process.
+            while (!circle_events_.empty() || 
+                   !(site_events_iterator_ == site_events_.end())) {
+                if (circle_events_.empty()) {
+                    process_site_event(*site_events_iterator_);
+                    site_events_iterator_++;
+                } else if (site_events_iterator_ == site_events_.end()) {
+                    process_circle_event(circle_events_.top());
+                    circle_events_.pop();
+                } else {
+                    if (circle_events_.top().compare(*site_events_iterator_) >= 0) {
+                        process_site_event(*site_events_iterator_);
+                        site_events_iterator_++;
+                    } else {
+                        process_circle_event(circle_events_.top());
+                        circle_events_.pop();
+                    }
+                }
+            }
+        }
+
+        const cell_records &get_cell_records() const {
+            return output_.get_cell_records();
+        }
+
+        const voronoi_vertices &get_voronoi_vertices() const {
+            return output_.get_voronoi_vertices();
+        }
+
+    protected:
+        typedef typename Point2D::site_event_type site_event_type;
+        typedef typename Point2D::circle_event_type circle_event_type;
+        typedef typename std::vector<site_event_type>::const_iterator site_events_iterator;
+
+        typedef typename circle_events_queue<Point2D> CircleEventsQueue;
+        typedef typename beach_line_node<Point2D> Key;
+        typedef typename beach_line_node_data<Point2D> Value;
+        typedef typename node_comparer<Key> NodeComparer;
+        typedef typename std::map< Key, Value, NodeComparer > BeachLine;
+        typedef typename BeachLine::const_iterator beach_line_iterator;
+
+        typedef typename voronoi_output<Point2D> Output;
+
+        void init_beach_line() {
+            site_events_iterator it_first = site_events_.begin();
+            site_events_iterator it_second = site_events_.begin();
+            it_second++;
+
+            // Create two new beach line nodes.
+            Key new_left_node(*it_first, *it_second);
+            Key new_right_node(*it_second, *it_first);
+
+            // Update output.
+            edge_type *edge = output_.insert_new_edge(*it_first, *it_second);
+
+            // Insert two new nodes into the binary search tree.
+            beach_line_.insert(std::pair<Key, Value>(new_left_node, Value(edge)));
+            beach_line_.insert(std::pair<Key, Value>(new_right_node, Value(edge->twin)));
+        }
+
+        void init_beach_line_colinear_sites() {
+             site_events_iterator it_first = site_events_.begin();
+             site_events_iterator it_second = site_events_.begin();
+             it_second++;
+             int cur_site = 0;
+             while (it_second != site_events_iterator_) {
+                 // Create new beach line node.
+                 Key new_node(*it_first, *it_second);
+                 
+                 // Update output.
+                 edge_type *edge = output_.insert_new_edge(*it_first, *it_second);
+
+                 // Insert new node into the binary search tree.
+                 beach_line_.insert(std::pair<Key, Value>(new_node, Value(edge)));
+                 
+                 // Update iterators.
+                 it_first++;
+                 it_second++;
+                 cur_site++;
+             }
+        }
+
+        // Uses special comparison function for the lower bound and insertion
+        // operations.
+        void process_site_event(const site_event_type &site_event) {
+            // Find the node in the binary search tree with left arc
+            // lying above the new site point.
+            Key new_key(site_event);
+            beach_line_iterator it = beach_line_.lower_bound(new_key);
+
+            site_event_type site_arc;
+            if (it == beach_line_.end()) {
+                it--;
+                site_arc = it->first.get_right_site();
+
+                // Insert new arc into the sweepline.
+                beach_line_iterator new_node_it = insert_new_arc(site_arc, site_event);
+                new_node_it--;
+
+                // Add candidate circle to the event queue.
+                activate_circle_event(it->first.get_left_site(),
+                                      it->first.get_right_site(),
+                                      site_event,
+                                      new_node_it);
+            } else if (it == beach_line_.begin()) {
+                site_arc = it->first.get_left_site();
+
+                // Insert new arc into the sweepline.
+                beach_line_iterator new_node_it = insert_new_arc(site_arc, site_event);
+                new_node_it++;
+
+                // Add candidate circle to the event queue.
+                activate_circle_event(site_event,
+                                      it->first.get_left_site(),
+                                      it->first.get_right_site(),
+                                      new_node_it);
+            } else {
+                site_arc = it->first.get_left_site();
+
+                // Insert new arc into the sweepline.
+                beach_line_iterator new_node_it = insert_new_arc(site_arc, site_event);
+
+                const site_event_type &site2 = it->first.get_left_site();
+                const site_event_type &site3 = it->first.get_right_site();
+                it--;
+                const site_event_type &site1 = it->first.get_right_site();
+
+                // Remove candidate circle from the event queue.
+                deactivate_circle_event(site1, site2, site3);
+
+                // Add candidate circles to the event queue.
+                new_node_it--;
+                activate_circle_event(site1, site2, site_event, new_node_it);
+                new_node_it++;
+                new_node_it++;
+                activate_circle_event(site_event, site2, site3, new_node_it);
+            }               
+        }
+
+        // Doesn't use special comparison function as it works fine only for
+        // the site events processing.
+        void process_circle_event(const circle_event_type &circle_event) {
+            // Retrieve the second bisector node that corresponds to the given
+            // circle event.
+            beach_line_iterator it_first = circle_event.get_bisector();
+            beach_line_iterator it_last = it_first;
+
+            // Get the second and the third sites that create given circle event.
+            site_event_type site2 = it_first->first.get_left_site();
+            site_event_type site3 = it_first->first.get_right_site();
+
+            // Get second bisector;
+            Value bisector2 = it_first->second;
+            
+            // Get first bisector;
+            it_first--;
+            Value bisector1 = it_first->second;
+            
+            // Get the first site that creates given circle event.
+            site_event_type site1 = it_first->first.get_left_site();
+
+            // 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 nodes 
+            // comparer doesn't work fine for the circle events. We only 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.
+            const_cast<Key &>(it_first->first).set_right_site(it_last->first.get_right_site());
+            edge_type *edge = output_.insert_new_edge(site1, site2, site3, circle_event, bisector1.edge, bisector2.edge);
+            const_cast<Value &>(it_first->second).change_edge(edge);
+            beach_line_.erase(it_last);
+            it_last = it_first;
+
+            // Check the new triplets formed by the neighboring arcs
+            // for potential circle events. Check left.
+            if (it_first != beach_line_.begin()) {
+                it_first--;
+                const site_event_type &site_l1 = it_first->first.get_left_site();
+                deactivate_circle_event(site_l1, site1, site3);
+                if (it_first != beach_line_.begin()) {
+                    it_first--;
+                    const site_event_type &site_l2 = it_first->first.get_left_site();
+                    it_first++;
+                    activate_circle_event(site_l2, site_l1, site1, it_first);
+                }
+            }
+
+            // Check the new triplets formed by the neighboring arcs
+            // for potential circle events. Check right.
+            it_last++;
+            if (it_last != beach_line_.end()) {
+                const site_event_type &site_r1 = it_last->first.get_right_site();
+                deactivate_circle_event(site1, site3, site_r1);
+                it_last++;
+                if (it_last != beach_line_.end()) {
+                    const site_event_type &site_r2 = it_last->first.get_right_site();
+                    activate_circle_event(site3, site_r1, site_r2, it_last);
+                }
+            }            
+        }
+
+        // Insert new arc below site arc into the beach line.
+        beach_line_iterator insert_new_arc(const site_event_type &site_arc,
+                                           const site_event_type &site_event) {
+            // Create two new nodes.
+            Key new_left_node(site_arc, site_event);
+            Key new_right_node(site_event, site_arc);
+            int site_index1 = site_arc.get_site_index();
+            int site_index2 = site_event.get_site_index();
+            
+            // Insert two new nodes into the binary search tree.
+            // Update output.
+            edge_type *edge = output_.insert_new_edge(site_arc, site_event);
+            beach_line_.insert(std::pair<Key, Value>(new_left_node, Value(edge)));
+            return beach_line_.insert(std::pair<Key, Value>(new_right_node, Value(edge->twin))).first;
+        }
+
+        // Create circle event from the given three points.
+        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 {
+            coordinate_type a = (site1.x() - site2.x()) * (site2.y() - site3.y()) -
+                                (site1.y() - site2.y()) * (site2.x() - site3.x());
+            // Check if bisectors intersect.
+            if (a >= static_cast<coordinate_type>(0))
+                return false;
+            coordinate_type b1 = (site1.x() - site2.x()) * (site1.x() + site2.x())+
+                                 (site1.y() - site2.y()) * (site1.y() + site2.y());
+            coordinate_type b2 = (site2.x() - site3.x()) * (site2.x() + site3.x())+
+                                 (site2.y() - site3.y()) * (site2.y() + site3.y());
+            coordinate_type c_x = (b1*(site2.y() - site3.y()) - b2*(site1.y() - site2.y())) / a *
+                                  static_cast<coordinate_type>(0.5);
+            coordinate_type c_y = (b2*(site1.x() - site2.x()) - b1*(site2.x() - site3.x())) / a *
+                                   static_cast<coordinate_type>(0.5);
+            coordinate_type sqr_radius = (c_x-site1.x())*(c_x-site1.x()) +
+                                         (c_y-site1.y())*(c_y-site1.y());
+            // Create new circle event;
+            c_event = make_circle_event(c_x, c_y, sqr_radius);
+            return true;
+        }
+
+        // Add new circle event to the event queue.
+        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;
+            if (create_circle_event(site1, site2, site3, c_event)) {
+                c_event.set_bisector(bisector_node);
+                circle_events_.push(c_event);
+            }
+        }
+
+        // Remove circle event from the event queue.
+        void deactivate_circle_event(const site_event_type &point1,
+                                     const site_event_type &point2,
+                                     const site_event_type &point3) {
+            circle_event_type c_event;
+            if (create_circle_event(point1, point2, point3, c_event))
+                circle_events_.deactivate_event(c_event);
+        }
+
+    private:
+        std::vector<site_event_type> site_events_;
+        site_events_iterator site_events_iterator_;
+        CircleEventsQueue circle_events_;
+        BeachLine beach_line_;
+        Output output_;
+
+        //Disallow copy constructor and operator=
+        voronoi_builder(const voronoi_builder&);
+        void operator=(const voronoi_builder&);
+    };
+
+} // sweepline
+} // boost
+
+#endif
\ No newline at end of file

Deleted: sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_formation.hpp
==============================================================================
--- sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_formation.hpp	2010-06-21 09:47:45 EDT (Mon, 21 Jun 2010)
+++ (empty file)
@@ -1,516 +0,0 @@
-// Boost sweepline/voronoi_formation.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.
-
-#include <map>
-#include <vector>
-
-#include "event_queue.hpp"
-#include "event_types.hpp"
-#include "voronoi_output.hpp"
-
-#ifndef BOOST_SWEEPLINE_VORONOI_FORMATION
-#define BOOST_SWEEPLINE_VORONOI_FORMATION
-
-namespace boost {
-namespace sweepline {
-
-    // Represents bisector made by two arcs that correspond to the left and
-    // right sites. Arc is defined as curve with points equidistant from the
-    // site and from the sweepline.
-    // Let sweepline sweep from left to right and it's current coordinate
-    // be x0, site coordinates be (x1, y1). In this case equation of the arc
-    // may be written as: (x-x0)^2 = (x-x1)^2 + (y-y1)^2, or
-    // x = ((y - y1)^2 + x1^2 - x0^2) / (2*(x1 - x0)).
-    // In general case two arcs will create two different bisectors. That's why
-    // the order of arcs is important to define unique bisector.
-    template <typename Point2D>
-    struct beach_line_node {
-    public:
-        typedef typename Point2D::coordinate_type coordinate_type;
-        typedef typename Point2D::site_event_type site_event_type;
-        typedef typename Point2D::circle_event_type circle_event_type;
-
-        beach_line_node() {}
-
-        // Constructs degenerate bisector, used to search arc that is above
-        // given site. The input to the constructor is the site event point.
-        explicit beach_line_node(const site_event_type &new_point) {
-            left_site_ = new_point;
-            right_site_ = new_point;
-        }
-
-        // Constructs new bisector. The input to the constructor is two sites
-        // that create bisector. The order of sites is important.
-        beach_line_node(const site_event_type &left_point,
-                        const site_event_type &right_point) {
-            left_site_ = left_point;
-            right_site_ = right_point;
-        }
-
-        // Returns the left site of the bisector.
-        const site_event_type &get_left_site() const {
-            return left_site_;
-        }
-
-        // Returns  the right site of the bisector.
-        const site_event_type &get_right_site() const {
-            return right_site_;
-        }
-
-        void set_left_site(const site_event_type &site) {
-            left_site_ = site;
-        }
-
-        void set_right_site(const site_event_type &site) {
-            right_site_ = site;
-        }
-
-        // Returns x coordinate of the rightmost site.
-        coordinate_type get_sweepline_coord() const {
-            return std::max(left_site_.x(), right_site_.x());
-        }
-
-        // Returns the rightmost site.
-        const site_event_type& get_new_site() const {
-            if (left_site_.x() > right_site_.x())
-                return left_site_;
-            return right_site_;
-        }
-
-        // Returns true if horizontal line going through new site intersects
-        // right arc at first, else returns false. If horizontal line goes
-        // through intersection point of the given two arcs returns false also. 
-        // Used during nodes comparison.
-        // Let x0 be sweepline coordinate, left site coordinates be (x1, y1),
-        // right site coordinates be (x2, y2). Equations of the arcs will be:
-        // x1(y) = ((y - y1)^2 + x1^2 - x0^2) / (2*(x1 - x0));
-        // x2(y) = ((y - y2)^2 + x2^2 - x0^2) / (2*(x2 - x0)).
-        // Horizontal line going throught site (x*, y*) intersects second arc
-        // at first if x2(y*) > x1(y*) or:
-        // (x2-x0)*(x1-x0)*(x1-x2) + (x2-x0)*(y*-y1)^2 < (x1-x0)*(y*-y2)^2
-        bool less(const site_event_type &new_site) const {
-            coordinate_type sweepline_coord = new_site.x();
-            coordinate_type new_node_coord = new_site.y();
-            coordinate_type a1 = left_site_.x() - sweepline_coord;
-            coordinate_type a2 = right_site_.x() - sweepline_coord;
-            coordinate_type b1 = new_node_coord - left_site_.y();
-            coordinate_type b2 = new_node_coord - right_site_.y();
-            coordinate_type c = left_site_.x() - right_site_.x();
-            return a1 * a2 * c + a2 * b1 * b1 < a1 * b2 * b2;
-        }
-
-    private:
-        site_event_type left_site_;
-        site_event_type right_site_;
-    };
-
-    // Represents edge data sturcture (bisector segment), which is
-    // associated with beach line node key in the binary search tree.
-    template <typename Point2D>
-    struct beach_line_node_data {
-        typedef typename half_edge<Point2D> Edge;
-
-        Edge *edge;
-
-        beach_line_node_data(Edge *new_edge) : edge(new_edge) {}
-
-        void change_edge(Edge *new_edge) {
-            edge = new_edge;
-        }
-    };
-
-    template <typename BeachLineNode>
-    struct node_comparer {
-    public:
-        typedef typename BeachLineNode::coordinate_type coordinate_type;
-
-        // Compares nodes in the balanced binary search tree. Nodes are
-        // compared based on the y coordinates of the arcs intersection points.
-        // Nodes with lesser y coordinate of the intersection point go first.
-        // Comparison is only called during site events processing. That's why
-        // one of the nodes will always lie on the sweepline. Comparison won't
-        // work fine for nodes situated above sweepline.
-        bool operator() (const BeachLineNode &node1,
-                         const BeachLineNode &node2) const {
-            // Get x coordinate of the righmost site from both nodes.
-            coordinate_type node1_line = node1.get_sweepline_coord();
-            coordinate_type node2_line = node2.get_sweepline_coord();
-
-            // Both nodes are situated on the same vertical line.
-            if (node1_line == node2_line) {
-                // Let A be the new site event point, and B the site that
-                // creates arc above A. In this case two new nodes are being
-                // inserted: (A,B) and (B,A). As intersection points for the
-                // first node and for the second are the same we need to
-                // compare them based on some another characteristic.
-                // That's why we assume that node (C, D) goes before node
-                // (D, C), only if D lies on the sweepline.
-                if (node1.get_left_site().get_site_index() ==
-                    node2.get_right_site().get_site_index() &&
-                    node1.get_right_site().get_site_index() ==
-                    node2.get_left_site().get_site_index())
-                    return node1.get_right_site().x() == node1_line;
-
-                // Just compare coordinates of the sites situated on the sweepline.
-                return node1.get_new_site().y() < node2.get_new_site().y();
-            }
-            else if (node1_line < node2_line)
-                return node1.less(node2.get_new_site());
-            else
-                return !node2.less(node1.get_new_site());
-        }
-    };
-
-    // Voronoi diagram formation. Sweepline sweeps from left to right.
-    template <typename T>
-    class voronoi_formation {
-    public:
-        typedef typename point_2d<T> Point2D;
-        typedef typename Point2D::coordinate_type coordinate_type;
-        typedef typename Point2D::site_event_type site_event_type;
-        typedef typename Point2D::circle_event_type circle_event_type;
-
-        typedef typename voronoi_output<Point2D> Output;
-        typedef typename Output::edge_type edge_type;
-        typedef typename Output::edge_iterator edge_iterator;
-        typedef typename Output::cell_records cell_records;
-        typedef typename Output::voronoi_vertices voronoi_vertices;
-        typedef typename voronoi_vertices::const_iterator voronoi_vertices_iterator;
-
-        typedef typename event_queue<Point2D> EventQueue;
-        typedef typename beach_line_node<Point2D> Key;
-        typedef typename beach_line_node_data<Point2D> Value;
-        typedef typename node_comparer<Key> NodeComparer;
-        typedef typename std::map< Key, Value, NodeComparer > BeachLine;
-        typedef typename BeachLine::const_iterator beach_line_iterator;
-
-        // Functor to process events from the event queue.
-        struct event_processor {
-            event_processor() : beach_line_(NULL) {} 
-
-            void operator()(const site_event_type &site_event) {
-                beach_line_->process_site_event(site_event);
-            }
-
-            void operator()(const circle_event_type &circle_event) {
-                beach_line_->process_circle_event(circle_event);
-            }
-
-            voronoi_formation *beach_line_;
-        };
-
-        voronoi_formation() : event_processor_() {}
-
-        // Init beach line before sweepline run.
-        // In case of a few first sites situated on the same
-        // vertical line, we init beach line with all of them.
-        // In other case just use the first two sites for the initialization.
-        void init(std::vector<Point2D> &sites) {
-            output_.init(sites.size());
-
-            // Init beach_line pointer in the event_processor data sturcture.
-            // This is done here to avoid compiler warning in the constructor.
-            event_processor_.beach_line_ = this;
-            
-            // Sort all sites.
-            std::sort(sites.begin(), sites.end());
-            int skip = 0;
-
-            if (sites.size() == 1) {
-                skip = 1;
-            } else {
-                std::vector<Point2D>::const_iterator it = sites.begin();
-                while(it != sites.end() && it->x() == sites.begin()->x()) {
-                    it++;
-                    skip++;
-                }
-
-                if (skip == 1) {
-                    // Init beach line with two sites.
-                    init_beach_line(*sites.begin(), *it);
-
-                    // Skip the second point also.
-                    skip++;
-                } else {
-                    // Init beach line with sites situated on the same vertical line.
-                    init_beach_line(sites.begin(), it);
-                }
-            }
-            // Init event queue with the rest of the sites.
-            event_queue_.init(sites, skip);
-        }
-
-        void reset() {
-            event_queue_.reset();
-            beach_line_.clear();
-            output_.clear();
-        }
-
-        void run_sweepline() {
-            // Algorithm stops when there are no events in the queue.
-            while (!event_queue_.empty()) {
-                event_queue_.process_top_event(event_processor_);
-                event_queue_.pop();
-            }
-        }
-
-        // Uses special comparison function for the lower bound and insertion
-        // operations.
-        void process_site_event(const site_event_type &site_event) {
-            // Find the node in the binary search tree with left arc
-            // lying above the new site point.
-            Key new_key(site_event);
-            beach_line_iterator it = beach_line_.lower_bound(new_key);
-
-            site_event_type site_arc;
-            if (it == beach_line_.end()) {
-                it--;
-                site_arc = it->first.get_right_site();
-
-                // Insert new arc into the sweepline.
-                beach_line_iterator new_node_it = insert_new_arc(site_arc, site_event);
-                new_node_it--;
-
-                // Add candidate circle to the event queue.
-                activate_circle_event(it->first.get_left_site(),
-                                      it->first.get_right_site(),
-                                      site_event,
-                                      new_node_it);
-            } else if (it == beach_line_.begin()) {
-                site_arc = it->first.get_left_site();
-
-                // Insert new arc into the sweepline.
-                beach_line_iterator new_node_it = insert_new_arc(site_arc, site_event);
-                new_node_it++;
-
-                // Add candidate circle to the event queue.
-                activate_circle_event(site_event,
-                                      it->first.get_left_site(),
-                                      it->first.get_right_site(),
-                                      new_node_it);
-            } else {
-                site_arc = it->first.get_left_site();
-
-                // Insert new arc into the sweepline.
-                beach_line_iterator new_node_it = insert_new_arc(site_arc, site_event);
-
-                const site_event_type &site2 = it->first.get_left_site();
-                const site_event_type &site3 = it->first.get_right_site();
-                it--;
-                const site_event_type &site1 = it->first.get_right_site();
-
-                // Remove candidate circle from the event queue.
-                deactivate_circle_event(site1, site2, site3);
-
-                // Add candidate circles to the event queue.
-                new_node_it--;
-                activate_circle_event(site1, site2, site_event, new_node_it);
-                new_node_it++;
-                new_node_it++;
-                activate_circle_event(site_event, site2, site3, new_node_it);
-            }               
-        }
-
-        // Doesn't use special comparison function as it works fine only for
-        // the site events processing.
-        void process_circle_event(const circle_event_type &circle_event) {
-            // Retrieve the second bisector node that corresponds to the given
-            // circle event.
-            beach_line_iterator it_first = circle_event.get_bisector();
-            beach_line_iterator it_last = it_first;
-
-            // Get the second and the third sites that create given circle event.
-            site_event_type site2 = it_first->first.get_left_site();
-            site_event_type site3 = it_first->first.get_right_site();
-
-            // Get second bisector;
-            Value bisector2 = it_first->second;
-            
-            // Get first bisector;
-            it_first--;
-            Value bisector1 = it_first->second;
-            
-            // Get the first site that creates given circle event.
-            site_event_type site1 = it_first->first.get_left_site();
-
-            // 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 nodes 
-            // comparer doesn't work fine for the circle events. We only 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.
-            const_cast<Key &>(it_first->first).set_right_site(it_last->first.get_right_site());
-            edge_type *edge = output_.insert_new_edge(site1, site2, site3, circle_event, bisector1.edge, bisector2.edge);
-            const_cast<Value &>(it_first->second).change_edge(edge);
-            beach_line_.erase(it_last);
-            it_last = it_first;
-
-            // Check the new triplets formed by the neighboring arcs
-            // for potential circle events. Check left.
-            if (it_first != beach_line_.begin()) {
-                it_first--;
-                const site_event_type &site_l1 = it_first->first.get_left_site();
-                deactivate_circle_event(site_l1, site1, site2);
-                if (it_first != beach_line_.begin()) {
-                    it_first--;
-                    const site_event_type &site_l2 = it_first->first.get_left_site();
-                    it_first++;
-                    activate_circle_event(site_l2, site_l1, site1, it_first);
-                }
-            }
-
-            // Check the new triplets formed by the neighboring arcs
-            // for potential circle events. Check right.
-            it_last++;
-            if (it_last != beach_line_.end()) {
-                const site_event_type &site_r1 = it_last->first.get_right_site();
-                deactivate_circle_event(site2, site3, site_r1);
-                it_last++;
-                if (it_last != beach_line_.end()) {
-                    it_last++;
-                    const site_event_type &site_r2 = it_last->first.get_right_site();
-                    activate_circle_event(site3, site_r1, site_r2, it_last);
-                }
-            }            
-        }
-
-        const cell_records &get_cell_records() const {
-            return output_.get_cell_records();
-        }
-
-        const voronoi_vertices &get_voronoi_vertices() const {
-            return output_.get_voronoi_vertices();
-        }
-
-    protected:
-        void init_beach_line(typename std::vector<Point2D>::const_iterator it_begin,
-                             typename std::vector<Point2D>::const_iterator it_end) {
-             typename std::vector<Point2D>::const_iterator it_first = it_begin;
-             typename std::vector<Point2D>::const_iterator it_second = it_begin;
-             it_second++;
-             int cur_site = 0;
-             while (it_second != it_end) {
-                 site_event_type site1 = make_site_event<coordinate_type>(
-                     it_first->x(), it_first->y(), cur_site);
-                 site_event_type site2 = make_site_event<coordinate_type>(
-                     it_second->x(), it_second->y(), cur_site+1);
-
-                 // Create new beach line node.
-                 Key new_node(site1, site2);
-                 
-                 // Update output.
-                 edge_type *edge = output_.insert_new_edge(site1, site2);
-
-                 // Insert new node into the binary search tree.
-                 beach_line_.insert(std::pair<Key, Value>(new_node, Value(edge)));
-                 
-                 // Update iterators.
-                 it_first++;
-                 it_second++;
-                 cur_site++;
-             }
-        }
-
-        void init_beach_line(const Point2D &first_point,
-                             const Point2D &second_point) {
-            site_event_type site1 = make_site_event<coordinate_type>(
-                first_point.x(), first_point.y(), 0);
-            site_event_type site2 = make_site_event<coordinate_type>(
-                second_point.x(), second_point.y(), 1);
-
-            // Create two new beach line nodes.
-            Key new_left_node(site1, site2);
-            Key new_right_node(site2, site1);
-
-            // Update output.
-            edge_type *edge = output_.insert_new_edge(site1, site2);
-
-            // Insert two new nodes into the binary search tree.
-            beach_line_.insert(std::pair<Key, Value>(new_left_node, Value(edge)));
-            beach_line_.insert(std::pair<Key, Value>(new_right_node, Value(edge->twin)));
-        }
-
-        // Insert new arc below site arc into the beach line.
-        beach_line_iterator insert_new_arc(const site_event_type &site_arc,
-                                           const site_event_type &site_event) {
-            // Create two new nodes.
-            Key new_left_node(site_arc, site_event);
-            Key new_right_node(site_event, site_arc);
-            int site_index1 = site_arc.get_site_index();
-            int site_index2 = site_event.get_site_index();
-            
-            // Insert two new nodes into the binary search tree.
-            // Update output.
-            edge_type *edge = output_.insert_new_edge(site_arc, site_event);
-            beach_line_.insert(std::pair<Key, Value>(new_left_node, Value(edge)));
-            return beach_line_.insert(std::pair<Key, Value>(new_right_node, Value(edge->twin))).first;
-        }
-
-        // Create circle event from the given three points.
-        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 {
-            coordinate_type a = (site1.x() - site2.x()) * (site2.y() - site3.y()) -
-                                (site1.y() - site2.y()) * (site2.x() - site3.x());
-            // Check if bisectors intersect.
-            if (a >= static_cast<coordinate_type>(0))
-                return false;
-            coordinate_type b1 = (site1.x() - site2.x()) * (site1.x() + site2.x())+
-                                 (site1.y() - site2.y()) * (site1.y() + site2.y());
-            coordinate_type b2 = (site2.x() - site3.x()) * (site2.x() + site3.x())+
-                                 (site2.y() - site3.y()) * (site2.y() + site3.y());
-            coordinate_type c_x = (b1*(site2.y() - site3.y()) - b2*(site1.y() - site2.y())) / a *
-                                  static_cast<coordinate_type>(0.5);
-            coordinate_type c_y = (b2*(site1.x() - site2.x()) - b1*(site2.x() - site3.x())) / a *
-                                   static_cast<coordinate_type>(0.5);
-            coordinate_type sqr_radius = (c_x-site1.x())*(c_x-site1.x()) +
-                                         (c_y-site1.y())*(c_y-site1.y());
-            // Create new circle event;
-            c_event = make_circle_event(c_x, c_y, sqr_radius);
-            return true;
-        }
-
-        // Add new circle event to the event queue.
-        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;
-            if (create_circle_event(site1, site2, site3, c_event)) {
-                c_event.set_bisector(bisector_node);
-                event_queue_.push(c_event);
-            }
-        }
-
-        // Remove circle event from the event queue.
-        void deactivate_circle_event(const site_event_type &point1,
-                                     const site_event_type &point2,
-                                     const site_event_type &point3) {
-            circle_event_type c_event;
-            if (create_circle_event(point1, point2, point3, c_event))
-                event_queue_.deactivate_event(c_event);
-        }
-
-    private:
-        EventQueue event_queue_;
-        event_processor event_processor_;
-        BeachLine beach_line_;
-        Output output_;
-
-        //Disallow copy constructor and operator=
-        voronoi_formation(const voronoi_formation&);
-        void operator=(const voronoi_formation&);
-    };
-
-} // sweepline
-} // boost
-
-#endif
\ No newline at end of file

Deleted: sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_output.hpp
==============================================================================
--- sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_output.hpp	2010-06-21 09:47:45 EDT (Mon, 21 Jun 2010)
+++ (empty file)
@@ -1,206 +0,0 @@
-// Boost sweepline/voronoi_output.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_OUTPUT
-#define BOOST_SWEEPLINE_VORONOI_OUTPUT
-
-#include <list>
-#include <vector>
-
-namespace boost {
-namespace sweepline {
-
-    template <typename Point2D>
-    struct half_edge;
-
-    // Cell record data structure. Represents voronoi cell.
-    // Contains site point and pointer to any incident half-edge.
-    template <typename Point2D>
-    struct cell_record {
-        half_edge<Point2D> *incident_edge;
-        Point2D site_point;
-
-        cell_record(Point2D site, half_edge<Point2D>* edge) : incident_edge(edge), site_point(site) {}
-    };
-
-    // Voronoi vertex data structure. Represents voronoi vertex.
-    // Contains vertex coordinates and pointers to all incident half-edges.
-    template <typename Point2D>
-    struct vertex_record {
-        std::list< half_edge<Point2D>* > incident_edges;
-        Point2D vertex;
-
-        vertex_record(Point2D vertex) : vertex(vertex) {}
-    };
-
-    // Half-edge data structure. Represents voronoi edge.
-    // Contains: 1) pointer to cell records;
-    //           2) pointers to start/end vertices of half-edge;
-    //           3) pointers to previous/next half-edges(CCW);
-    //           4) pointer to twin half-edge.
-    template <typename Point2D>
-    struct half_edge {
-        typedef typename cell_record<Point2D> cell_record_type;
-        typedef typename vertex_record<Point2D> vertex_record_type;
-        typedef typename half_edge<Point2D> half_edge_type;
-
-        cell_record_type *cell_record;
-        vertex_record_type *start_point;
-        vertex_record_type *end_point;
-        half_edge_type *prev;
-        half_edge_type *next;
-        half_edge_type *twin;
-
-        half_edge(int site_index) :
-            cell_record(NULL),
-            start_point(NULL),
-            end_point(NULL),
-            prev(NULL),
-            next(NULL),
-            twin(NULL) {}
-    };
-
-    // Voronoi output data structure based on the half-edges.
-    // Contains vector of voronoi cells, doubly linked list of
-    // voronoi vertices and voronoi edges.
-    template <typename Point2D>
-    class voronoi_output {
-    public:
-        typedef typename Point2D::site_event_type site_event_type;
-        typedef typename Point2D::circle_event_type circle_event_type;
-        typedef typename cell_record<Point2D> cell_record_type;
-        typedef typename vertex_record<Point2D> vertex_record_type;
-        typedef typename half_edge<Point2D> edge_type;
-        typedef typename std::vector<cell_record_type> cell_records;
-        typedef typename std::list<vertex_record_type> voronoi_vertices;
-        typedef typename std::list<edge_type *>::const_iterator edge_iterator;
-        typedef typename voronoi_vertices::const_iterator voronoi_vertices_iterator;
-
-        voronoi_output() {}
-
-        // This preserves the validity of iterators.
-        void init(int num_sites) {
-            cell_records_.reserve(num_sites);
-        }
-
-        void reset() {
-            cell_records_.clear();
-            vertex_records_.clear();
-            edges_.clear();
-        }
-
-        // Inserts new half-edge into the output data structure during site
-        // event processing. Takes as input left and right sites of the new
-        // beach line node and returns reference to the new half-edge. 
-        // Second argument is new site. During this step we add two new
-        // twin half-edges.
-        edge_type *insert_new_edge(const site_event_type &site1,
-                                   const site_event_type &site2) {
-            // Get indexes of sites.                                           
-            int site_index1 = site1.get_site_index();
-            int site_index2 = site2.get_site_index();
-
-            // Create new half-edge that belongs to the cell with the first site.
-            edges_.push_back(edge_type(site_index1));
-            edge_type &edge1 = edges_.back();
-
-            // Create new half-edge that belongs to the cell with the second site.
-            edges_.push_back(edge_type(site_index2));
-            edge_type &edge2 = edges_.back();
-
-            // Add initial cell during first edge insertion.
-            if (cell_records_.empty())
-                cell_records_.push_back(cell_record_type(site1.get_point(), &edge1));
-
-            // Second site represents new site during site event processing.
-            // Add new cell to the cell records vector.
-            cell_records_.push_back(cell_record_type(site2.get_point(), &edge2));
-
-            // Update pointers to cells.
-            edge1.cell_record = &cell_records_[site_index1];
-            edge2.cell_record = &cell_records_[site_index2];
-
-            // Update twin pointers.
-            edge1.twin = &edge2;
-            edge2.twin = &edge1;
-
-            return &edge1;
-        }
-
-        edge_type *insert_new_edge(const site_event_type &site1,
-                                   const site_event_type &site2,
-                                   const site_event_type &site3,
-                                   const circle_event_type &circle,
-                                   edge_type *edge12,
-                                   edge_type *edge23) {
-            // Add new voronoi vertex as voronoi circle center.
-            vertex_records_.push_back(vertex_record_type(circle.get_center()));
-            vertex_record_type &new_vertex = vertex_records_.back();
-
-            // Update two input bisectors and their twins half-edges with
-            // new voronoi vertex.
-            edge12->start_point = &new_vertex;
-            edge12->twin->end_point = &new_vertex;
-            edge23->start_point = &new_vertex;
-            edge23->twin->end_point = &new_vertex;
-
-            // Add new half-edge.
-            edges_.push_back(edge_type(site1.get_site_index()));
-            edge_type &new_edge1 = edges_.back();
-            new_edge1.cell_record = &cell_records_[site1.get_site_index()];
-            new_edge1.end_point = &new_vertex;
-
-            // Add new half-edge.
-            edges_.push_back(edge_type(site3.get_site_index()));
-            edge_type &new_edge2 = edges_.back();
-            new_edge2.cell_record = &cell_records_[site3.get_site_index()];
-            new_edge2.start_point = &new_vertex;
-
-            // Update twin pointers of the new half-edges.
-            new_edge1.twin = &new_edge2;
-            new_edge2.twin = &new_edge1;
-
-            // Update voronoi prev/next pointers of all half-edges incident
-            // to the new voronoi vertex.
-            edge12->prev = &new_edge1;
-            new_edge1.next = edge12;
-            edge12->twin->next = edge23;
-            edge23->prev = edge12->twin;
-            edge23->twin->next = &new_edge2;
-            new_edge2.prev = edge23->twin;
-
-            // Update voronoi vertex incident edges pointers.
-            new_vertex.incident_edges.push_back(edge12);
-            new_vertex.incident_edges.push_back(edge23);
-            new_vertex.incident_edges.push_back(&new_edge2);
-            return &new_edge1;
-        }
-
-        const cell_records &get_cell_records() const {
-            return cell_records_;
-        }
-
-        const voronoi_vertices &get_voronoi_vertices() const {
-            return vertex_records_;
-        }
-
-    private:
-        std::vector<cell_record_type> cell_records_;
-        std::list<vertex_record_type> vertex_records_;
-        std::list<edge_type> edges_;
-
-        //Disallow copy constructor and operator=
-        voronoi_output(const voronoi_output&);
-        void operator=(const voronoi_output&);
-    };
-
-} // sweepline
-} // boost
-
-#endif
\ No newline at end of file

Modified: sandbox/SOC/2010/sweepline/libs/sweepline/test/Jamfile.v2
==============================================================================
--- sandbox/SOC/2010/sweepline/libs/sweepline/test/Jamfile.v2	(original)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/test/Jamfile.v2	2010-06-21 09:47:45 EDT (Mon, 21 Jun 2010)
@@ -15,5 +15,5 @@
         [ run event_queue_test.cpp :  :  : <link>static ]
         [ run event_types_test.cpp :  :  : <link>static ]
         [ run node_comparer_test.cpp :  :  : <link>static ]
-	[ run voronoi_formation_test.cpp :  :  : <link>static ]
+	[ run voronoi_builder_test.cpp :  :  : <link>static ]
     ;
\ No newline at end of file

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	2010-06-21 09:47:45 EDT (Mon, 21 Jun 2010)
@@ -8,84 +8,31 @@
 //  See http://www.boost.org for updates, documentation, and revision history.
 
 #include "test_type_list.hpp"
-#include <boost/sweepline/voronoi_formation.hpp>
-using namespace boost::sweepline;
+#include <boost/sweepline/detail/voronoi_formation.hpp>
+using namespace boost::sweepline::detail;
 
 #define BOOST_TEST_MODULE event_queue_test
 #include <boost/test/test_case_template.hpp>
 
 #define CHECK_TOP_ELEMENT_EQUALITY(TOP, X, Y) \
-    BOOST_CHECK_EQUAL(TOP.x == static_cast<T>(X) && \
-                      TOP.y == static_cast<T>(Y), true)
-
-template <typename Point2D>
-struct event_processor {
-    typedef typename Point2D::coordinate_type coordinate_type;
-    typedef typename Point2D::site_event_type site_event_type;
-    typedef typename Point2D::circle_event_type circle_event_type;
-
-    event_processor() {}
-
-    void operator()(const site_event_type &site_event) {
-        x = site_event.x();
-        y = site_event.y();
-    }
-
-    void operator()(const circle_event_type &circle_event) {
-        x = circle_event.x() +
-            sqrt(static_cast<coordinate_type>(circle_event.get_sqr_radius()));
-        y = circle_event.y();
-    }
-        
-    coordinate_type x;
-    coordinate_type y;
-};
+    BOOST_CHECK_EQUAL(TOP.x() + sqrt(static_cast<T>(TOP.get_sqr_radius())) \
+                      == static_cast<T>(X) && \
+                      TOP.y() == static_cast<T>(Y), true)
 
 BOOST_AUTO_TEST_CASE_TEMPLATE(event_queue_test1, T, test_types) {
-    event_processor< point_2d<T> > test_processor;
-
-    event_queue< point_2d<T> > event_q;
+    circle_events_queue< point_2d<T> > event_q;
     BOOST_CHECK_EQUAL(event_q.empty(), true);
     
     event_q.reset();
 
-    std::vector< point_2d<T> > site_event_vec;
-    for (int i = 0; i <= 10; i++) {
-        T x = static_cast<T>(10-i);
-        T y = static_cast<T>(10-i);
-        site_event_vec.push_back(make_point_2d(x, y));
-    }
-    sort(site_event_vec.begin(), site_event_vec.end());
-    event_q.init(site_event_vec, 0);
-    
-    event_q.process_top_event(test_processor);
-    CHECK_TOP_ELEMENT_EQUALITY(test_processor, 0, 0);
-    event_q.pop();
-
-    event_q.process_top_event(test_processor);
-    CHECK_TOP_ELEMENT_EQUALITY(test_processor, 1, 1);
-
-    for (int i = 5; i < 10; i++) {
+    for (int i = 0; i < 10; i++) {
         T x = static_cast<T>(-i);
         T y = static_cast<T>(10-i);
         event_q.push(make_circle_event(x, y, static_cast<T>(100)));
     }
 
-    for (int i = 0; i < 5; i++) {
-        T x = static_cast<T>(-i);
-        T y = static_cast<T>(10-i-1);
-        event_q.push(make_circle_event(x, y, static_cast<T>(100)));
-    }
-    
     for (int i = 0; i < 10; i++) {
-        event_q.process_top_event(test_processor);
-        CHECK_TOP_ELEMENT_EQUALITY(test_processor, 1 + i/2, 1 + i/2);
-        event_q.pop();
-    }
-
-    for (int i = 10; i < 20; i++) {
-        event_q.process_top_event(test_processor);
-        CHECK_TOP_ELEMENT_EQUALITY(test_processor, 1 + i/2, 1 + (i-1)/2);
+        CHECK_TOP_ELEMENT_EQUALITY(event_q.top(), 1 + i, 1 + i);
         event_q.pop();
     }
 
@@ -93,8 +40,7 @@
 }
 
 BOOST_AUTO_TEST_CASE_TEMPLATE(event_queue_test2, T, test_types) {
-    event_processor< point_2d<T> > test_processor;
-    event_queue< point_2d<T> > event_q;
+    circle_events_queue< point_2d<T> > event_q;
 
     for (int i = 0; i < 10; i++) {
         T x = static_cast<T>(10-i);
@@ -109,8 +55,7 @@
     }
 
     for (int i = 0; i < 5; i++) {
-        event_q.process_top_event(test_processor);
-        CHECK_TOP_ELEMENT_EQUALITY(test_processor, 2 + 2*i, 2 + 2*i);
+        CHECK_TOP_ELEMENT_EQUALITY(event_q.top(), 2 + 2*i, 2 + 2*i);
         event_q.pop();
     }
 

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	2010-06-21 09:47:45 EDT (Mon, 21 Jun 2010)
@@ -8,8 +8,8 @@
 //  See http://www.boost.org for updates, documentation, and revision history.
 
 #include "test_type_list.hpp"
-#include <boost/sweepline/voronoi_formation.hpp>
-using namespace boost::sweepline;
+#include <boost/sweepline/detail/voronoi_formation.hpp>
+using namespace boost::sweepline::detail;
 
 #define BOOST_TEST_MODULE event_types_test
 #include <boost/test/test_case_template.hpp>

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	2010-06-21 09:47:45 EDT (Mon, 21 Jun 2010)
@@ -8,8 +8,8 @@
 //  See http://www.boost.org for updates, documentation, and revision history.
 
 #include "test_type_list.hpp"
-#include <boost/sweepline/voronoi_formation.hpp>
-using namespace boost::sweepline;
+#include <boost/sweepline/detail/voronoi_formation.hpp>
+using namespace boost::sweepline::detail;
 
 #define BOOST_TEST_MODULE node_comparer_test
 #include <boost/test/test_case_template.hpp>

Added: sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_builder_test.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_builder_test.cpp	2010-06-21 09:47:45 EDT (Mon, 21 Jun 2010)
@@ -0,0 +1,162 @@
+// Boost sweepline library voronoi_builder_test.cpp 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.
+
+#include "test_type_list.hpp"
+#include <boost/sweepline/voronoi_builder.hpp>
+using namespace boost::sweepline;
+
+#define BOOST_TEST_MODULE voronoi_builder_test
+#include <boost/test/test_case_template.hpp>
+
+BOOST_AUTO_TEST_CASE_TEMPLATE(voronoi_builder_test1, T, test_types) {
+    typedef typename voronoi_builder<T>::edge_type edge_type;
+    typedef typename voronoi_builder<T>::edge_iterator edge_iterator;
+    typedef typename voronoi_builder<T>::voronoi_vertices_iterator
+        voronoi_vertices_iterator;
+
+    voronoi_builder<T> test_beach_line;
+    point_2d<T> point1 = make_point_2d<T>(0, 0);
+    point_2d<T> point2 = make_point_2d<T>(0, 4);
+    point_2d<T> point3 = make_point_2d<T>(2, 1);
+
+    std::vector< point_2d<T> > points;
+    points.push_back(point1);
+    points.push_back(point2);
+    points.push_back(point3);
+    
+    test_beach_line.init(points);
+    test_beach_line.run_sweepline();
+    BOOST_CHECK_EQUAL(test_beach_line.get_cell_records().size(), 3);
+    BOOST_CHECK_EQUAL(test_beach_line.get_voronoi_vertices().size(), 1);
+
+    voronoi_vertices_iterator it = test_beach_line.get_voronoi_vertices().begin();
+    BOOST_CHECK_EQUAL(it->incident_edges.size(), 3);
+    BOOST_CHECK_EQUAL(it->vertex.x() == static_cast<T>(0.25) &&
+                      it->vertex.y() == static_cast<T>(2.0), true);
+
+    edge_iterator edge_it = it->incident_edges.begin();
+    edge_type *edge1_1 = *edge_it;
+    edge_type *edge1_2 = edge1_1->twin;
+    BOOST_CHECK_EQUAL(edge1_1->cell_record->site_point == point3, true);
+    BOOST_CHECK_EQUAL(edge1_2->cell_record->site_point == point1, true);
+
+    edge_it++;
+    edge_type *edge2_1 = *edge_it;
+    edge_type *edge2_2 = edge2_1->twin;
+    BOOST_CHECK_EQUAL(edge2_1->cell_record->site_point == point1, true);
+    BOOST_CHECK_EQUAL(edge2_2->cell_record->site_point == point2, true);
+
+    edge_it++;
+    edge_type *edge3_1 = *edge_it;
+    edge_type *edge3_2 = edge3_1->twin;
+    BOOST_CHECK_EQUAL(edge3_1->cell_record->site_point == point2, true);
+    BOOST_CHECK_EQUAL(edge3_2->cell_record->site_point == point3, true);
+
+    BOOST_CHECK_EQUAL(edge1_2->twin == edge1_1, true);
+    BOOST_CHECK_EQUAL(edge2_2->twin == edge2_1, true);
+    BOOST_CHECK_EQUAL(edge3_2->twin == edge3_1, true);
+
+    BOOST_CHECK_EQUAL(edge1_1->next == NULL && edge1_2->prev == NULL, true);
+    BOOST_CHECK_EQUAL(edge2_1->next == NULL && edge2_2->prev == NULL, true);
+    BOOST_CHECK_EQUAL(edge3_1->next == NULL && edge3_2->prev == NULL, true);
+
+    BOOST_CHECK_EQUAL(edge1_1->prev == edge3_2, true);
+    BOOST_CHECK_EQUAL(edge2_1->prev == edge1_2, true);
+    BOOST_CHECK_EQUAL(edge3_1->prev == edge2_2, true);
+
+    BOOST_CHECK_EQUAL(edge1_2->next == edge2_1, true);
+    BOOST_CHECK_EQUAL(edge2_2->next == edge3_1, true);
+    BOOST_CHECK_EQUAL(edge3_2->next == edge1_1, true);
+
+}
+
+BOOST_AUTO_TEST_CASE_TEMPLATE(voronoi_builder_test2, T, test_types) {
+    typedef typename voronoi_builder<T>::edge_type edge_type;
+    typedef typename voronoi_builder<T>::edge_iterator edge_iterator;
+    typedef typename voronoi_builder<T>::voronoi_vertices_iterator
+        voronoi_vertices_iterator;
+
+    voronoi_builder<T> test_beach_line;
+    point_2d<T> point1 = make_point_2d<T>(0, 1);
+    point_2d<T> point2 = make_point_2d<T>(2, 0);
+    point_2d<T> point3 = make_point_2d<T>(2, 4);
+
+    std::vector< point_2d<T> > points;
+    points.push_back(point1);
+    points.push_back(point2);
+    points.push_back(point3);
+    
+    test_beach_line.init(points);
+    test_beach_line.run_sweepline();
+    BOOST_CHECK_EQUAL(test_beach_line.get_cell_records().size(), 3);
+    BOOST_CHECK_EQUAL(test_beach_line.get_voronoi_vertices().size(), 1);
+
+    voronoi_vertices_iterator it = test_beach_line.get_voronoi_vertices().begin();
+    BOOST_CHECK_EQUAL(it->incident_edges.size(), 3);
+    BOOST_CHECK_EQUAL(it->vertex.x() == static_cast<T>(1.75) &&
+                      it->vertex.y() == static_cast<T>(2.0), true);
+
+    edge_iterator edge_it = it->incident_edges.begin();
+    edge_type *edge1_1 = *edge_it;
+    edge_type *edge1_2 = edge1_1->twin;
+    BOOST_CHECK_EQUAL(edge1_1->cell_record->site_point == point2, true);
+    BOOST_CHECK_EQUAL(edge1_2->cell_record->site_point == point1, true);
+
+    edge_it++;
+    edge_type *edge2_1 = *edge_it;
+    edge_type *edge2_2 = edge2_1->twin;    
+    BOOST_CHECK_EQUAL(edge2_1->cell_record->site_point == point1, true);
+    BOOST_CHECK_EQUAL(edge2_2->cell_record->site_point == point3, true);
+
+    edge_it++;
+    edge_type *edge3_1 = *edge_it;
+    edge_type *edge3_2 = edge3_1->twin;
+    BOOST_CHECK_EQUAL(edge3_1->cell_record->site_point == point3, true);
+    BOOST_CHECK_EQUAL(edge3_2->cell_record->site_point == point2, true);
+
+    BOOST_CHECK_EQUAL(edge1_2->twin == edge1_1, true);
+    BOOST_CHECK_EQUAL(edge2_2->twin == edge2_1, true);
+    BOOST_CHECK_EQUAL(edge3_2->twin == edge3_1, true);
+
+    BOOST_CHECK_EQUAL(edge1_1->next == NULL && edge1_2->prev == NULL, true);
+    BOOST_CHECK_EQUAL(edge2_1->next == NULL && edge2_2->prev == NULL, true);
+    BOOST_CHECK_EQUAL(edge3_1->next == NULL && edge3_2->prev == NULL, true);
+
+    BOOST_CHECK_EQUAL(edge1_1->prev == edge3_2, true);
+    BOOST_CHECK_EQUAL(edge2_1->prev == edge1_2, true);
+    BOOST_CHECK_EQUAL(edge3_1->prev == edge2_2, true);
+
+    BOOST_CHECK_EQUAL(edge1_2->next == edge2_1, true);
+    BOOST_CHECK_EQUAL(edge2_2->next == edge3_1, true);
+    BOOST_CHECK_EQUAL(edge3_2->next == edge1_1, true);
+}
+
+BOOST_AUTO_TEST_CASE_TEMPLATE(voronoi_builder_test3, T, test_types) {
+    typedef typename voronoi_builder<T>::edge_type edge_type;
+    typedef typename voronoi_builder<T>::edge_iterator edge_iterator;
+    typedef typename voronoi_builder<T>::voronoi_vertices_iterator
+        voronoi_vertices_iterator;
+
+    voronoi_builder<T> test_beach_line;
+    point_2d<T> point1 = make_point_2d<T>(0, 0);
+    point_2d<T> point2 = make_point_2d<T>(0, 1);
+    point_2d<T> point3 = make_point_2d<T>(1, 0);
+    point_2d<T> point4 = make_point_2d<T>(1, 1);
+
+    std::vector< point_2d<T> > points;
+    points.push_back(point1);
+    points.push_back(point2);
+    points.push_back(point3);
+    points.push_back(point4);
+    
+    test_beach_line.init(points);
+    test_beach_line.run_sweepline();
+    BOOST_CHECK_EQUAL(test_beach_line.get_cell_records().size(), 4);
+    BOOST_CHECK_EQUAL(test_beach_line.get_voronoi_vertices().size(), 1);
+}
\ No newline at end of file

Deleted: sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_formation_test.cpp
==============================================================================
--- sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_formation_test.cpp	2010-06-21 09:47:45 EDT (Mon, 21 Jun 2010)
+++ (empty file)
@@ -1,138 +0,0 @@
-// Boost sweepline library voronoi_formation_test.cpp 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.
-
-#include "test_type_list.hpp"
-#include <boost/sweepline/voronoi_formation.hpp>
-using namespace boost::sweepline;
-
-#define BOOST_TEST_MODULE voronoi_formation_test
-#include <boost/test/test_case_template.hpp>
-
-BOOST_AUTO_TEST_CASE_TEMPLATE(beach_line_test1, T, test_types) {
-    typedef typename voronoi_formation<T>::edge_type edge_type;
-    typedef typename voronoi_formation<T>::edge_iterator edge_iterator;
-    typedef typename voronoi_formation<T>::voronoi_vertices_iterator
-        voronoi_vertices_iterator;
-
-    voronoi_formation<T> test_beach_line;
-    point_2d<T> point1 = make_point_2d<T>(0, 0);
-    point_2d<T> point2 = make_point_2d<T>(0, 4);
-    point_2d<T> point3 = make_point_2d<T>(2, 1);
-
-    std::vector< point_2d<T> > points;
-    points.push_back(point1);
-    points.push_back(point2);
-    points.push_back(point3);
-    
-    test_beach_line.init(points);
-    test_beach_line.run_sweepline();
-    BOOST_CHECK_EQUAL(test_beach_line.get_cell_records().size(), 3);
-    BOOST_CHECK_EQUAL(test_beach_line.get_voronoi_vertices().size(), 1);
-
-    voronoi_vertices_iterator it = test_beach_line.get_voronoi_vertices().begin();
-    BOOST_CHECK_EQUAL(it->incident_edges.size(), 3);
-    BOOST_CHECK_EQUAL(it->vertex.x() == static_cast<T>(0.25) &&
-                      it->vertex.y() == static_cast<T>(2.0), true);
-
-    edge_iterator edge_it = it->incident_edges.begin();
-    edge_type *edge1_1 = *edge_it;
-    edge_type *edge1_2 = edge1_1->twin;
-    BOOST_CHECK_EQUAL(edge1_1->cell_record->site_point == point3, true);
-    BOOST_CHECK_EQUAL(edge1_2->cell_record->site_point == point1, true);
-
-    edge_it++;
-    edge_type *edge2_1 = *edge_it;
-    edge_type *edge2_2 = edge2_1->twin;
-    BOOST_CHECK_EQUAL(edge2_1->cell_record->site_point == point1, true);
-    BOOST_CHECK_EQUAL(edge2_2->cell_record->site_point == point2, true);
-
-    edge_it++;
-    edge_type *edge3_1 = *edge_it;
-    edge_type *edge3_2 = edge3_1->twin;
-    BOOST_CHECK_EQUAL(edge3_1->cell_record->site_point == point2, true);
-    BOOST_CHECK_EQUAL(edge3_2->cell_record->site_point == point3, true);
-
-    BOOST_CHECK_EQUAL(edge1_2->twin == edge1_1, true);
-    BOOST_CHECK_EQUAL(edge2_2->twin == edge2_1, true);
-    BOOST_CHECK_EQUAL(edge3_2->twin == edge3_1, true);
-
-    BOOST_CHECK_EQUAL(edge1_1->next == NULL && edge1_2->prev == NULL, true);
-    BOOST_CHECK_EQUAL(edge2_1->next == NULL && edge2_2->prev == NULL, true);
-    BOOST_CHECK_EQUAL(edge3_1->next == NULL && edge3_2->prev == NULL, true);
-
-    BOOST_CHECK_EQUAL(edge1_1->prev == edge3_2, true);
-    BOOST_CHECK_EQUAL(edge2_1->prev == edge1_2, true);
-    BOOST_CHECK_EQUAL(edge3_1->prev == edge2_2, true);
-
-    BOOST_CHECK_EQUAL(edge1_2->next == edge2_1, true);
-    BOOST_CHECK_EQUAL(edge2_2->next == edge3_1, true);
-    BOOST_CHECK_EQUAL(edge3_2->next == edge1_1, true);
-
-}
-
-BOOST_AUTO_TEST_CASE_TEMPLATE(beach_line_test2, T, test_types) {
-    typedef typename voronoi_formation<T>::edge_type edge_type;
-    typedef typename voronoi_formation<T>::edge_iterator edge_iterator;
-    typedef typename voronoi_formation<T>::voronoi_vertices_iterator
-        voronoi_vertices_iterator;
-
-    voronoi_formation<T> test_beach_line;
-    point_2d<T> point1 = make_point_2d<T>(0, 1);
-    point_2d<T> point2 = make_point_2d<T>(2, 0);
-    point_2d<T> point3 = make_point_2d<T>(2, 4);
-
-    std::vector< point_2d<T> > points;
-    points.push_back(point1);
-    points.push_back(point2);
-    points.push_back(point3);
-    
-    test_beach_line.init(points);
-    test_beach_line.run_sweepline();
-    BOOST_CHECK_EQUAL(test_beach_line.get_cell_records().size(), 3);
-    BOOST_CHECK_EQUAL(test_beach_line.get_voronoi_vertices().size(), 1);
-
-    voronoi_vertices_iterator it = test_beach_line.get_voronoi_vertices().begin();
-    BOOST_CHECK_EQUAL(it->incident_edges.size(), 3);
-    BOOST_CHECK_EQUAL(it->vertex.x() == static_cast<T>(1.75) &&
-                      it->vertex.y() == static_cast<T>(2.0), true);
-
-    edge_iterator edge_it = it->incident_edges.begin();
-    edge_type *edge1_1 = *edge_it;
-    edge_type *edge1_2 = edge1_1->twin;
-    BOOST_CHECK_EQUAL(edge1_1->cell_record->site_point == point2, true);
-    BOOST_CHECK_EQUAL(edge1_2->cell_record->site_point == point1, true);
-
-    edge_it++;
-    edge_type *edge2_1 = *edge_it;
-    edge_type *edge2_2 = edge2_1->twin;    
-    BOOST_CHECK_EQUAL(edge2_1->cell_record->site_point == point1, true);
-    BOOST_CHECK_EQUAL(edge2_2->cell_record->site_point == point3, true);
-
-    edge_it++;
-    edge_type *edge3_1 = *edge_it;
-    edge_type *edge3_2 = edge3_1->twin;
-    BOOST_CHECK_EQUAL(edge3_1->cell_record->site_point == point3, true);
-    BOOST_CHECK_EQUAL(edge3_2->cell_record->site_point == point2, true);
-
-    BOOST_CHECK_EQUAL(edge1_2->twin == edge1_1, true);
-    BOOST_CHECK_EQUAL(edge2_2->twin == edge2_1, true);
-    BOOST_CHECK_EQUAL(edge3_2->twin == edge3_1, true);
-
-    BOOST_CHECK_EQUAL(edge1_1->next == NULL && edge1_2->prev == NULL, true);
-    BOOST_CHECK_EQUAL(edge2_1->next == NULL && edge2_2->prev == NULL, true);
-    BOOST_CHECK_EQUAL(edge3_1->next == NULL && edge3_2->prev == NULL, true);
-
-    BOOST_CHECK_EQUAL(edge1_1->prev == edge3_2, true);
-    BOOST_CHECK_EQUAL(edge2_1->prev == edge1_2, true);
-    BOOST_CHECK_EQUAL(edge3_1->prev == edge2_2, true);
-
-    BOOST_CHECK_EQUAL(edge1_2->next == edge2_1, true);
-    BOOST_CHECK_EQUAL(edge2_2->next == edge3_1, true);
-    BOOST_CHECK_EQUAL(edge3_2->next == edge1_1, true);
-}
\ No newline at end of file