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

Subject: [Boost-commit] svn:boost r63703 - in sandbox/SOC/2010/sweepline: boost/sweepline boost/sweepline/detail libs/sweepline/test
From: sydorchuk.andriy_at_[hidden]
Date: 2010-07-06 14:12:11

Author: asydorchuk
Date: 2010-07-06 14:12:08 EDT (Tue, 06 Jul 2010)
New Revision: 63703
URL: http://svn.boost.org/trac/boost/changeset/63703

Log:
Implemented voronoi output clipping.
Added clipped output.
Updated unit tests.
Added:
   sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_sweepline.hpp   (contents, props changed)
Text files modified: 
   sandbox/SOC/2010/sweepline/boost/sweepline/detail/voronoi_formation.hpp |   689 +++++++++++++++++++++++++++++++++++++++ 
   sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_builder.hpp          |    26                                         
   sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_output.hpp           |   525 ++++++++---------------------           
   sandbox/SOC/2010/sweepline/libs/sweepline/test/event_queue_test.cpp     |     2                                         
   sandbox/SOC/2010/sweepline/libs/sweepline/test/event_types_test.cpp     |     2                                         
   sandbox/SOC/2010/sweepline/libs/sweepline/test/node_comparer_test.cpp   |     2                                         
   sandbox/SOC/2010/sweepline/libs/sweepline/test/test_type_list.hpp       |     4                                         
   sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_builder_test.cpp |   397 +++++++++++-----------                  
   8 files changed, 1051 insertions(+), 596 deletions(-)

Modified: sandbox/SOC/2010/sweepline/boost/sweepline/detail/voronoi_formation.hpp
==============================================================================
--- sandbox/SOC/2010/sweepline/boost/sweepline/detail/voronoi_formation.hpp	(original)
+++ sandbox/SOC/2010/sweepline/boost/sweepline/detail/voronoi_formation.hpp	2010-07-06 14:12:08 EDT (Tue, 06 Jul 2010)
@@ -120,7 +120,7 @@
     public:
         typedef typename Point2D::coordinate_type coordinate_type;
         typedef beach_line_node<Point2D> Key;
-        typedef beach_line_node_data<typename Point2D::Edge> Value;
+        typedef beach_line_node_data<Point2D> Value;
         typedef node_comparer<Key> NodeComparer;
         typedef typename std::map< Key, Value, NodeComparer >::iterator beach_line_iterator;
 
@@ -401,9 +401,9 @@
         void operator=(const circle_events_queue&);
     };
 
-    /////////////////////////////////////////////////////////////////////////////
-    // VORONOI BEACH LINE TYPES /////////////////////////////////////////////////
-    /////////////////////////////////////////////////////////////////////////////
+    ///////////////////////////////////////////////////////////////////////////
+    // 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
@@ -494,13 +494,16 @@
         site_event_type right_site_;
     };
 
+    template <typename Point2D>
+    struct half_edge;
+
     // Represents edge data sturcture (bisector segment), which is
     // associated with beach line node key in the binary search tree.
-    template <typename Edge>
+    template <typename Point2D>
     struct beach_line_node_data {
-        Edge *edge;
+        half_edge<Point2D> *edge;
 
-        explicit beach_line_node_data(Edge *new_edge) : edge(new_edge) {}
+        explicit beach_line_node_data(half_edge<Point2D> *new_edge) : edge(new_edge) {}
     };
 
     template <typename BeachLineNode>
@@ -576,6 +579,678 @@
             }
         }
     };
+
+    ///////////////////////////////////////////////////////////////////////////
+    // VORONOI OUTPUT /////////////////////////////////////////////////////////
+    ///////////////////////////////////////////////////////////////////////////    
+    // Voronoi record data structure. May represent voronoi cell or
+    // voronoi vertex. Contains pointer to any incident edge, point
+    // coordinates and number of incident edges.
+    template <typename Point2D>
+    struct voronoi_record {
+        half_edge<Point2D> *incident_edge;
+        Point2D voronoi_point;
+        int num_incident_edges;
+        typename std::list< voronoi_record<Point2D> >::iterator voronoi_record_it;
+
+        voronoi_record(const Point2D &point, half_edge<Point2D>* edge) :
+            incident_edge(edge),
+            voronoi_point(point),
+            num_incident_edges(0) {}
+    };
+
+    // 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) pointers to previous/next half-edges rotated
+    //              around start point;
+    //           5) pointer to twin half-edge;
+    //           6) pointer to clipped edge during clipping.
+    template <typename Point2D>
+    struct half_edge {
+        typedef voronoi_record<Point2D> voronoi_record_type;
+        typedef half_edge<Point2D> half_edge_type;
+        typedef half_edge_clipped<Point2D> half_edge_clipped_type;
+
+        voronoi_record_type *cell;
+        voronoi_record_type *start_point;
+        voronoi_record_type *end_point;
+        half_edge_type *prev;
+        half_edge_type *next;
+        half_edge_type *rot_prev;
+        half_edge_type *rot_next;
+        half_edge_type *twin;
+        half_edge_clipped_type *clipped_edge;
+
+        half_edge() :
+            cell(NULL),
+            start_point(NULL),
+            end_point(NULL),
+            prev(NULL),
+            next(NULL),
+            rot_prev(NULL),
+            rot_next(NULL),
+            twin(NULL),
+            clipped_edge(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::coordinate_type coordinate_type;
+        typedef typename detail::site_event<Point2D> site_event_type;
+        typedef typename detail::circle_event<Point2D> circle_event_type;
+
+        typedef voronoi_record<Point2D> voronoi_record_type;
+        typedef voronoi_record_clipped<Point2D> clipped_voronoi_record_type;
+        typedef half_edge<Point2D> edge_type;
+        typedef half_edge_clipped<Point2D> clipped_edge_type;
+
+        typedef std::list<voronoi_record_type> voronoi_records_type;
+        typedef std::list<edge_type> voronoi_edges_type;
+        typedef typename voronoi_records_type::iterator voronoi_iterator_type;
+        typedef typename voronoi_records_type::const_iterator voronoi_const_iterator_type;
+
+        enum kEdgeType {
+            SEGMENT = 0,
+            RAY = 1,
+            LINE = 2,
+        };
+
+        voronoi_output() {
+            num_cell_records_ = 0;
+            num_edges_ = 0;
+            num_vertex_records_ = 0;
+        }
+
+        void init(int num_sites) {
+            cell_iterators_.reserve(num_sites);
+            num_cell_records_ = 0;
+            num_edges_ = 0;
+            num_vertex_records_ = 0;
+        }
+
+        void reset() {
+            cell_iterators_.clear();
+            cell_records_.clear();
+            vertex_records_.clear();
+            edges_.clear();
+
+            num_cell_records_ = 0;
+            num_edges_ = 0;
+            num_vertex_records_ = 0;
+        }
+
+        // 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 pointer to the new half-edge. 
+        edge_type *insert_new_edge(const site_event_type &site1,
+                                   const site_event_type &site2) {
+            // Update counters.
+            num_cell_records_++;
+            num_edges_++;
+
+            // Get indices of sites.           
+            int site_index1 = site1.get_site_index();
+            int site_index2 = site2.get_site_index();
+
+            // Create new half-edge that belongs to the first site.
+            edges_.push_back(edge_type());
+            edge_type &edge1 = edges_.back();
+
+            // Create new half-edge that belongs to the second site.
+            edges_.push_back(edge_type());
+            edge_type &edge2 = edges_.back();
+
+            // Add initial cell during first edge insertion.
+            if (cell_records_.empty()) {
+                cell_iterators_.push_back(cell_records_.insert(
+                    cell_records_.end(), voronoi_record_type(site1.get_point(), &edge1)));
+                cell_records_.back().num_incident_edges++;
+                num_cell_records_++;
+                voronoi_rect_ = BRect<Point2D>(site1.get_point(), site1.get_point());
+            }
+
+            // Update bounding rectangle.
+            voronoi_rect_.update(site2.get_point());
+
+            // Second site represents new site during site event processing.
+            // Add new cell to the cell records vector.
+            cell_iterators_.push_back(cell_records_.insert(
+                cell_records_.end(), voronoi_record_type(site2.get_point(), &edge2)));
+            cell_records_.back().num_incident_edges++;
+            
+            // Update pointers to cells.
+            edge1.cell = &(*cell_iterators_[site_index1]);
+            edge2.cell = &(*cell_iterators_[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) {
+            // Update counters.
+            num_vertex_records_++;
+            num_edges_++;
+
+            // Update bounding rectangle.
+            voronoi_rect_.update(circle.get_center());
+
+            // Add new voronoi vertex with point at center of the circle.
+            vertex_records_.push_back(voronoi_record_type(circle.get_center(), edge12));
+            voronoi_record_type &new_vertex = vertex_records_.back();
+            new_vertex.num_incident_edges = 3;
+            new_vertex.voronoi_record_it = vertex_records_.end();
+            new_vertex.voronoi_record_it--;
+
+            // Update two input bisectors and their twin 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());
+            edge_type &new_edge1 = edges_.back();
+            new_edge1.cell = &(*cell_iterators_[site1.get_site_index()]);
+            new_edge1.cell->num_incident_edges++;
+            new_edge1.end_point = &new_vertex;
+
+            // Add new half-edge.
+            edges_.push_back(edge_type());
+            edge_type &new_edge2 = edges_.back();
+            new_edge2.cell = &(*cell_iterators_[site3.get_site_index()]);
+            new_edge2.cell->num_incident_edges++;
+            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 vertices incident edges pointers.
+            edge12->rot_next = &new_edge2;
+            new_edge2.rot_prev = edge12;
+            edge23->rot_next = edge12;
+            edge12->rot_prev = edge23;
+            new_edge2.rot_next = edge23;
+            edge23->rot_prev = &new_edge2;
+
+            return &new_edge1;
+        }
+
+        const voronoi_records_type &get_cell_records() const {
+            return cell_records_;
+        }
+
+        const voronoi_records_type &get_voronoi_vertices() const {
+            return vertex_records_;
+        }
+
+        const voronoi_edges_type &get_voronoi_edges() const {
+            return edges_;
+        }
+
+        int get_num_voronoi_cells() const {
+            return num_cell_records_;
+        }
+
+        int get_num_voronoi_vertices() const {
+            return num_vertex_records_;
+        }
+
+        int get_num_voronoi_edges() const {
+            return num_edges_;
+        }
+
+        const BRect<Point2D> &get_bounding_rectangle() const {
+            return voronoi_rect_;
+        }
+
+        void simplify() {
+            typename std::list<edge_type>::iterator edge_it1;
+            typename std::list<edge_type>::iterator edge_it = edges_.begin();
+
+            // Iterate over all edges and remove degeneracies.
+            while (edge_it != edges_.end()) {
+                edge_it1 = edge_it;
+                edge_it++;
+                edge_it++;
+
+                if (edge_it1->start_point && edge_it1->end_point &&
+                    edge_it1->start_point->voronoi_point ==
+                    edge_it1->end_point->voronoi_point) {
+                    // Decrease number of cell incident edges.
+                    edge_it1->cell->num_incident_edges--;
+                    edge_it1->twin->cell->num_incident_edges--;
+
+                    // To guarantee N*lon(N) time we merge vertex with
+                    // less incident edges to the one with more.
+                    if (edge_it1->start_point->num_incident_edges >=
+                        edge_it1->end_point->num_incident_edges)
+                            simplify_edge(&(*edge_it1));
+                    else
+                        simplify_edge(&(*edge_it1->twin));
+
+                    // Remove zero length edges.
+                    edges_.erase(edge_it1, edge_it);
+
+                    // Update counters.
+                    num_vertex_records_--;
+                    num_edges_--;
+                }
+            }
+
+            // Make some post processing.
+            for (voronoi_iterator_type cell_it = cell_records_.begin();
+                cell_it != cell_records_.end(); cell_it++) {
+                // Move to the previous edge while it is possible in the CW direction.
+                edge_type *cur_edge = cell_it->incident_edge;
+                while (cur_edge->prev != NULL) {
+                    cur_edge = cur_edge->prev;
+
+                    // Terminate if this is not a boundary cell.
+                    if (cur_edge == cell_it->incident_edge)
+                        break;
+                }
+
+                // Rewind incident edge pointer to the leftmost edge for the boundary cells.
+                cell_it->incident_edge = cur_edge;
+
+                // Set up prev/next half-edge pointers for ray edges.
+                if (cur_edge->prev == NULL) {
+                    edge_type *last_edge = cell_it->incident_edge;
+                    while (last_edge->next != NULL)
+                        last_edge = last_edge->next;
+                    last_edge->next = cur_edge;
+                    cur_edge->prev = last_edge;
+                }
+            }
+            
+        }
+
+        void clip(voronoi_output_clipped<Point2D> &clipped_output) const {
+            coordinate_type x_len = (voronoi_rect_.x_max - voronoi_rect_.x_min);
+            coordinate_type y_len = (voronoi_rect_.y_max - voronoi_rect_.y_min);
+            coordinate_type x_mid = (voronoi_rect_.x_max + voronoi_rect_.x_min) /
+                static_cast<coordinate_type>(2);
+            coordinate_type y_mid = (voronoi_rect_.y_max + voronoi_rect_.y_min) /
+                static_cast<coordinate_type>(2);
+
+            coordinate_type offset = x_len;
+            if (offset < y_len)
+                offset = y_len;
+            offset *= static_cast<coordinate_type>(0.55);
+            BRect<Point2D> new_brect(x_mid - offset, y_mid - offset,
+                                     x_mid + offset, y_mid + offset);
+            clip(new_brect, clipped_output);
+        }
+
+        void clip(const BRect<Point2D> &brect,
+                  voronoi_output_clipped<Point2D> &clipped_output) const {
+            if (!brect.valid())
+                return;
+            clipped_output.reset();
+            clipped_output.set_bounding_rectangle(brect);
+
+            // Iterate over all voronoi vertices.
+            for (voronoi_const_iterator_type vertex_it = vertex_records_.begin();
+                 vertex_it != vertex_records_.end(); vertex_it++) {
+                edge_type *cur_edge = vertex_it->incident_edge;
+                const Point2D &cur_vertex_point = vertex_it->voronoi_point;
+
+                // Check if bounding rectangle of clipped output contains current voronoi vertex.
+                if (brect.contains(cur_vertex_point)) {
+                    // Add current voronoi vertex to clipped output.
+                    clipped_voronoi_record_type &new_vertex =
+                        clipped_output.add_vertex(cur_vertex_point);
+                    new_vertex.num_incident_edges = vertex_it->num_incident_edges;
+                    clipped_edge_type *rot_prev_edge = NULL;
+
+                    // Process all half-edges incident to the current voronoi vertex.
+                    do {
+                        // Add new edge to the clipped output.
+                        clipped_edge_type &new_edge = clipped_output.add_edge();
+                        new_edge.start_point = &new_vertex;
+                        cur_edge->clipped_edge = &new_edge;
+ 
+                        // Ray edges with no start point don't correspond to any voronoi vertex.
+                        // That's why ray edges are processed during their twin edge processing.
+                        if (cur_edge->end_point == NULL) {
+                            // Add new twin edge.
+                            clipped_edge_type &new_twin_edge = clipped_output.add_edge();
+                            cur_edge->twin->clipped_edge = &new_twin_edge;
+                            
+                            // Add boundary vertex.
+                            std::vector<Point2D> intersections;
+                            const Point2D &site1 = cur_edge->cell->voronoi_point;
+                            const Point2D &site2 = cur_edge->twin->cell->voronoi_point;
+                            Point2D direction(site1.y() - site2.y(), site2.x() - site1.x());
+                            find_intersections(cur_vertex_point, direction, RAY, brect, intersections);
+                            clipped_voronoi_record_type &boundary_vertex = 
+                                clipped_output.add_boundary_vertex(intersections[0]);
+                            boundary_vertex.incident_edge = &new_twin_edge;
+                            boundary_vertex.num_incident_edges = 1;
+
+                            // Update new twin edge pointers.
+                            new_twin_edge.start_point = &boundary_vertex;
+                            new_twin_edge.rot_next = &new_twin_edge;
+                            new_twin_edge.rot_prev = &new_twin_edge;
+                        }
+
+                        // Update twin and end point pointers.
+                        clipped_edge_type *twin = cur_edge->twin->clipped_edge;
+                        if (twin != NULL) {
+                            new_edge.twin = twin;
+                            twin->twin = &new_edge;
+                            new_edge.end_point = twin->start_point;
+                            twin->end_point = new_edge.start_point;
+                        }
+
+                        // Update rotation prev/next pointers.
+                        if (rot_prev_edge != NULL) {
+                            new_edge.rot_prev = rot_prev_edge;
+                            rot_prev_edge->rot_next = &new_edge;
+                        }
+
+                        rot_prev_edge = &new_edge;
+                        cur_edge = cur_edge->rot_next;
+                    } while(cur_edge != vertex_it->incident_edge);
+                    
+                    // Update rotation prev/next pointers.
+                    cur_edge->clipped_edge->rot_prev = rot_prev_edge;
+                    rot_prev_edge->rot_next = cur_edge->clipped_edge;
+                    new_vertex.incident_edge = cur_edge->clipped_edge;
+                } else {
+                    do {
+                        std::vector<Point2D> intersections;
+                        Point2D direction;
+                        kEdgeType etype;
+                        if (cur_edge->end_point != NULL) {
+                            const Point2D &end_point = cur_edge->end_point->voronoi_point;
+                            direction = make_point_2d<coordinate_type> (
+                                end_point.x() - cur_vertex_point.x(),
+                                end_point.y() - cur_vertex_point.y());
+                            etype = SEGMENT;
+                        } else {
+                            const Point2D &site1 = cur_edge->cell->voronoi_point;
+                            const Point2D &site2 = cur_edge->twin->cell->voronoi_point;
+                            direction = make_point_2d<coordinate_type> (
+                                site1.y() - site2.y(), site2.x() - site1.x());
+                            etype = RAY;
+                        }
+
+                        // Find all intersections of the current
+                        // edge with bounding box of the clipped output.
+                        find_intersections(cur_vertex_point, direction, etype, brect, intersections);
+
+                        // Process edge if there are any intersections.
+                        if (!intersections.empty()) {
+                            // Add new vertex to the clipped output.
+                            clipped_voronoi_record_type &new_vertex = 
+                                clipped_output.add_boundary_vertex(intersections[0]);
+                            new_vertex.num_incident_edges = 1;
+    
+                            // Add new edge to the clipped output.
+                            clipped_edge_type &new_edge = clipped_output.add_edge();
+                            new_edge.start_point = &new_vertex;
+                            cur_edge->clipped_edge = &new_edge;
+
+                            // Process twin ray edge with no start point.
+                            if (cur_edge->end_point == NULL && intersections.size() == 2) {
+                                clipped_edge_type &new_twin_edge = clipped_output.add_edge();
+                                cur_edge->twin->clipped_edge = &new_twin_edge;
+
+                                clipped_voronoi_record_type &boundary_vertex =
+                                    clipped_output.add_boundary_vertex(intersections[1]);
+                                boundary_vertex.incident_edge = &new_twin_edge;
+                                boundary_vertex.num_incident_edges = 1;
+
+                                new_twin_edge.start_point = &boundary_vertex;
+                                new_twin_edge.rot_next = &new_twin_edge;
+                                new_twin_edge.rot_prev = &new_twin_edge;
+                            }   
+
+                            // Update twin and end point pointers.
+                            clipped_edge_type *twin = cur_edge->twin->clipped_edge;
+                            if (twin != NULL) {
+                                new_edge.twin = twin;
+                                twin->twin = &new_edge;
+                                new_edge.end_point = twin->start_point;
+                                twin->end_point = new_edge.start_point;
+                            }
+
+                            // Update rotation prev/next pointers.
+                            new_edge.rot_next = &new_edge;
+                            new_edge.rot_prev = &new_edge;
+
+                            new_vertex.incident_edge = cur_edge->clipped_edge;
+                        }
+                        cur_edge = cur_edge->rot_next;
+                    } while (cur_edge != vertex_it->incident_edge);
+                }
+            }
+
+            // Iterate over all voronoi cells.
+            for (voronoi_const_iterator_type cell_it = cell_records_.begin();
+                 cell_it != cell_records_.end(); cell_it++) {
+                // Add new cell to the clipped output.
+                clipped_voronoi_record_type &new_cell =
+                    clipped_output.add_cell(cell_it->voronoi_point);
+                edge_type *cur_edge = cell_it->incident_edge;
+                clipped_edge_type *prev = NULL;
+
+                // Update cell, next/prev pointers.
+                do {
+                    clipped_edge_type *new_edge = cur_edge->clipped_edge;
+                    if (new_edge) {
+                        if (prev) {
+                            new_edge->prev = prev;
+                            prev->next = new_edge;
+                        }
+                        new_edge->cell = &new_cell;
+                        if (new_cell.incident_edge == NULL)
+                            new_cell.incident_edge = cur_edge->clipped_edge;
+                        new_cell.num_incident_edges++;
+                        prev = new_edge;
+                        cur_edge->clipped_edge = NULL;
+                    }
+                    cur_edge = cur_edge->next;
+                } while(cur_edge != cell_it->incident_edge);
+
+                if (new_cell.incident_edge == NULL)
+                    clipped_output.pop_cell();
+                else {
+                    // Update prev/next pointers.
+                    prev->next = new_cell.incident_edge;
+                    new_cell.incident_edge->prev = prev;
+                }
+            }
+        }
+
+        // Find edge(segment, ray, line) rectangle intersetion points.
+        void find_intersections(const Point2D &origin, const Point2D &direction,
+            kEdgeType edge_type, const BRect<Point2D> &brect,
+            std::vector<Point2D> &intersections) const {
+            // Do intersection test.
+            if (!test_intersection(origin, direction, brect))
+                return;
+
+            // Intersection parameters:
+            // origin + fT[i] * direction = intersections point, i = 0 .. 1.
+            bool fT0_used = false;
+            bool fT1_used = false;
+            coordinate_type fT0 = static_cast<coordinate_type>(0);
+            coordinate_type fT1 = static_cast<coordinate_type>(0);
+
+            // Half lengths of sides of a bounding rectangle.
+            coordinate_type half = static_cast<coordinate_type>(0.5);
+            coordinate_type x_len = (brect.x_max - brect.x_min) * half;
+            coordinate_type y_len = (brect.y_max - brect.y_min) * half;
+
+            // Find intersections with lines going through sides of a bounding recntagle.
+            clip(+direction.x(), -origin.x() - x_len, fT0_used, fT1_used, fT0, fT1);
+            clip(-direction.x(), +origin.x() - x_len, fT0_used, fT1_used, fT0, fT1);
+            clip(+direction.y(), -origin.y() - y_len, fT0_used, fT1_used, fT0, fT1);
+            clip(-direction.y(), +origin.y() - y_len, fT0_used, fT1_used, fT0, fT1);
+
+            if (fT0_used && check_extent(fT0, edge_type))
+                intersections.push_back(make_point_2d(origin.x() + fT0_used * direction.x(),
+                                                      origin.y() + fT0_used * direction.y()));
+            if (fT1_used && check_extent(fT1, edge_type))
+                intersections.push_back(make_point_2d(origin.x() + fT1_used * direction.x(),
+                                                      origin.y() + fT1_used * direction.y()));
+        }
+
+    private:
+        // Simplify degenerate edge.
+        void simplify_edge(edge_type *edge) {
+            voronoi_record_type *vertex1 = edge->start_point;
+            voronoi_record_type *vertex2 = edge->end_point;
+
+            // Update number of incident edges.
+            vertex1->num_incident_edges += vertex2->num_incident_edges - 2;
+
+            // Update second vertex incident edges start and end points.
+            edge_type *updated_edge = edge->twin->rot_next;
+            while (updated_edge != edge->twin) {
+                updated_edge->start_point = vertex1;
+                updated_edge->twin->end_point = vertex1;
+                updated_edge = updated_edge->rot_next;
+            }
+
+            edge_type *edge1 = edge;
+            edge_type *edge2 = edge->twin;
+
+            edge_type *edge1_rot_prev = edge1->rot_prev;
+            edge_type *edge1_rot_next = edge1->rot_next;
+
+            edge_type *edge2_rot_prev = edge2->rot_prev;
+            edge_type *edge2_rot_next = edge2->rot_next;
+
+            // Update prev and next pointers of incident edges.
+            edge1_rot_next->twin->next = edge2_rot_prev;
+            edge2_rot_prev->prev = edge1_rot_next->twin;
+            edge1_rot_prev->prev = edge2_rot_next->twin;
+            edge2_rot_next->twin->next = edge1_rot_prev;
+
+            // Update rotation prev and next pointers of incident edges.
+            edge1_rot_prev->rot_next = edge2_rot_next;
+            edge2_rot_next->rot_prev = edge1_rot_prev;
+            edge1_rot_next->rot_prev = edge2_rot_prev;
+            edge2_rot_prev->rot_next = edge1_rot_next;
+
+            // Change incident edge pointer of a vertex if it correspongs to the
+            // degenerate edge.
+            if (vertex1->incident_edge == edge)
+                vertex1->incident_edge = edge->rot_prev;
+
+            // Remove second vertex from the vertex records list.
+            vertex_records_.erase(vertex2->voronoi_record_it);
+        }
+
+        bool check_extent(coordinate_type extent, kEdgeType etype) const {
+            switch (etype) {
+                case SEGMENT: return extent >= static_cast<coordinate_type>(0) &&
+                                     extent <= static_cast<coordinate_type>(1);
+                case RAY: return extent >= static_cast<coordinate_type>(0);
+                case LINE: return true;
+            }
+            return true;
+        }
+
+        coordinate_type magnitude(coordinate_type value) const {
+            if (value >= static_cast<coordinate_type>(0))
+                return value;
+            return -value;
+        }
+
+        // Check line rectangle intersection.
+        bool test_intersection(const Point2D &origin, const Point2D &direction,
+            const BRect<Point2D> &brect) const {
+            coordinate_type half = static_cast<coordinate_type>(0.5);
+
+            // Find rectangle center.
+            coordinate_type center_x = (brect.x_min + brect.x_max) * half;
+            coordinate_type center_y = (brect.y_min + brect.y_max) * half;
+
+            // Find rectangle half-diagonal vector.
+            coordinate_type len_x = brect.x_max - center_x;
+            coordinate_type len_y = brect.y_max - center_y;
+
+            // Find distance between origin and center of rectangle.
+            coordinate_type diff_x = origin.x() - center_x;
+            coordinate_type diff_y = origin.y() - center_y;
+            
+            // Find direction perpendicular to the current.
+            coordinate_type perp_x = direction.y();
+            coordinate_type perp_y = -direction.x();
+
+            // Compare projections of distances.
+            coordinate_type lexpr = magnitude(perp_x * diff_x + perp_y * diff_y);
+            coordinate_type rexpr = magnitude(perp_x * len_x) + magnitude(perp_y * len_y);
+
+            return lexpr <= rexpr;
+        }
+
+        bool clip(coordinate_type denom, coordinate_type numer, bool &fT0_used, bool &fT1_used,
+            coordinate_type &fT0, coordinate_type fT1) const {
+            if (denom > static_cast<coordinate_type>(0)) {
+                if (fT1_used && numer > denom * fT1)
+                    return false;
+                if (!fT0_used || numer > denom * fT0) {
+                    fT0_used = true;
+                    fT0 = numer / denom;
+                }
+                return true;
+            } else if (denom < static_cast<coordinate_type>(0)) {
+                if (fT0_used && numer > denom * fT0)
+                    return false;
+                if (!fT1_used || numer > denom * fT1) {
+                    fT1_used = true;
+                    fT1 = numer / denom;
+                }
+                return true;
+            }
+            return false;
+        }
+
+        std::vector<voronoi_iterator_type> cell_iterators_;
+        voronoi_records_type cell_records_;
+        voronoi_records_type vertex_records_;
+        std::list<edge_type> edges_;
+
+        int num_cell_records_;
+        int num_vertex_records_;
+        int num_edges_;
+
+        BRect<Point2D> voronoi_rect_;
+
+        // Disallow copy constructor and operator=
+        voronoi_output(const voronoi_output&);
+        void operator=(const voronoi_output&);
+    };
   
 } // sweepline
 } // boost

Modified: sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_builder.hpp
==============================================================================
--- sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_builder.hpp	(original)
+++ sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_builder.hpp	2010-07-06 14:12:08 EDT (Tue, 06 Jul 2010)
@@ -7,13 +7,11 @@
 
 //  See http://www.boost.org for updates, documentation, and revision history.
 
-#include <algorithm>
-
-#include "voronoi_output.hpp"
-
 #ifndef BOOST_SWEEPLINE_VORONOI_BUILDER
 #define BOOST_SWEEPLINE_VORONOI_BUILDER
 
+#include <algorithm>
+
 namespace boost {
 namespace sweepline {
 
@@ -23,7 +21,7 @@
     public:
         typedef point_2d<T> Point2D;
         typedef typename Point2D::coordinate_type coordinate_type;
-        typedef voronoi_output<Point2D> Output;
+        typedef detail::voronoi_output<Point2D> Output;
         typedef typename Output::edge_type edge_type;
 
         voronoi_builder() {
@@ -107,8 +105,16 @@
             output_.simplify();
         }
 
-        const Output &get_output() const {
-            return output_;
+        const BRect<Point2D> &get_bounding_rectangle() const {
+            return output_.get_bounding_rectangle();
+        }
+
+        void clip(voronoi_output_clipped<Point2D> &clipped_output) {
+            output_.clip(clipped_output);
+        }
+
+        void clip(const BRect<Point2D> &brect, voronoi_output_clipped<Point2D> &clipped_output) {
+            output_.clip(brect, clipped_output);
         }
 
     protected:
@@ -118,7 +124,7 @@
 
         typedef typename detail::circle_events_queue<Point2D> CircleEventsQueue;
         typedef typename detail::beach_line_node<Point2D> Key;
-        typedef typename detail::beach_line_node_data<edge_type> Value;
+        typedef typename detail::beach_line_node_data<Point2D> Value;
         typedef typename detail::node_comparer<Key> NodeComparer;
         typedef std::map< Key, Value, NodeComparer > BeachLine;
         typedef typename std::map< Key, Value, NodeComparer >::iterator beach_line_iterator;
@@ -307,9 +313,9 @@
             // Check if bisectors intersect.
             if (a >= static_cast<coordinate_type>(0))
                 return false;
-            coordinate_type b1 = (site1.x() - site2.x()) * (site1.x() + site2.x())+
+            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())+
+            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);

Modified: sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_output.hpp
==============================================================================
--- sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_output.hpp	(original)
+++ sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_output.hpp	2010-07-06 14:12:08 EDT (Tue, 06 Jul 2010)
@@ -7,25 +7,20 @@
 
 //  See http://www.boost.org for updates, documentation, and revision history.
 
-// Point in 2D space data structure. Comparators defined in this
-    // data structure actually define sweepline movement direction.
-
 #ifndef BOOST_SWEEPLINE_VORONOI_OUTPUT
 #define BOOST_SWEEPLINE_VORONOI_OUTPUT
 
-#include "detail/voronoi_formation.hpp"
+#include <list>
+#include <map>
+#include <vector>
 
 namespace boost {
 namespace sweepline {
 
-    template <typename Point2D>
-    struct half_edge;
-
     template <typename T>
     struct point_2d {
     public:
         typedef T coordinate_type;
-        typedef half_edge< point_2d<T> > Edge;
 
         point_2d() {}
 
@@ -111,135 +106,95 @@
             y_max = std::max(p1.y(), p2.y());
         }
 
+        BRect(coordinate_type x_mn, coordinate_type y_mn,
+              coordinate_type x_mx, coordinate_type y_mx) {
+             x_min = std::min(x_mn, x_mx);
+             y_min = std::min(y_mn, y_mx);
+             x_max = std::max(x_mn, x_mx);
+             y_max = std::max(y_mn, y_mx);
+        }
+
         void update(const Point2D &p) {
             x_min = std::min(x_min, p.x());
             y_min = std::min(y_min, p.y());
             x_max = std::max(x_max, p.x());
             y_max = std::max(y_max, p.y());
         }
-    };
 
-    // Cell record data structure. Represents voronoi cell.
-    // Contains site point pointer to any incident half-edge and number
-    // of incident half-edges.
-    template <typename Point2D>
-    struct cell_record {
-        half_edge<Point2D> *incident_edge;
-        Point2D site_point;
-        int num_incident_edges;
+        bool contains(const Point2D &p) const {
+            return p.x() > x_min && p.x() < x_max && p.y() > y_min && p.y() < y_max;
+        }
 
-        cell_record(const Point2D &site, half_edge<Point2D>* edge) :
-            incident_edge(edge),
-            site_point(site),
-            num_incident_edges(0) {}
+        bool valid() const {
+            return (x_min < x_max) && (y_min < y_max);
+        }
     };
 
-    // Voronoi vertex data structure. Represents voronoi vertex.
-    // Contains vertex coordinates, pointers to all incident half-edges and
-    // number of incident half-edges.
     template <typename Point2D>
-    struct vertex_record {
-        typedef typename std::list< half_edge<Point2D>* >::const_iterator 
-            vertex_incident_edges_const_it;
+    struct half_edge_clipped;
 
-        std::list< half_edge<Point2D>* > incident_edges;
-        Point2D vertex;
+    // Voronoi record data structure. May represent voronoi cell or
+    // voronoi vertex. Contains pointer to any incident edge, point
+    // coordinates and number of incident edges.
+    template <typename Point2D>
+    struct voronoi_record_clipped {
+        half_edge_clipped<Point2D> *incident_edge;
+        Point2D voronoi_point;
         int num_incident_edges;
-        typename std::list< vertex_record<Point2D> >::iterator vertex_it;
-
-        vertex_record(const Point2D &vertex) : vertex(vertex), num_incident_edges(3) {}
 
-        bool is_boundary_point() const {
-            return (num_incident_edges == 1);
-        }
-
-        vertex_incident_edges_const_it get_prev_incident_edge(
-            vertex_incident_edges_const_it it) const {
-            if (it != incident_edges.begin()) {
-                it--;
-                return it;
-            }
-            it = incident_edges.end();
-            it--;
-            return it;
-        }
-
-        vertex_incident_edges_const_it get_next_incident_edge(
-            vertex_incident_edges_const_it it) const {
-            it++;
-            if (it != incident_edges.end())
-                return it;            
-            return incident_edges.begin();
-        }
+        voronoi_record_clipped(const Point2D &point, half_edge_clipped<Point2D>* edge) :
+            incident_edge(edge),
+            voronoi_point(point),
+            num_incident_edges(0) {}
     };
 
     // 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;
-    //           5) iterator in the vertex incident edges list.
+    //           4) pointers to previous/next half-edges rotated
+    //              around start point;
+    //           5) pointer to twin half-edge.
     template <typename Point2D>
-    struct half_edge {
-        typedef cell_record<Point2D> cell_record_type;
-        typedef vertex_record<Point2D> vertex_record_type;
-        typedef half_edge<Point2D> half_edge_type;
-
-        cell_record_type *cell;
-        vertex_record_type *start_point;
-        vertex_record_type *end_point;
+    struct half_edge_clipped {
+        typedef voronoi_record_clipped<Point2D> voronoi_record_type;
+        typedef half_edge_clipped<Point2D> half_edge_type;
+
+        voronoi_record_type *cell;
+        voronoi_record_type *start_point;
+        voronoi_record_type *end_point;
         half_edge_type *prev;
         half_edge_type *next;
+        half_edge_type *rot_prev;
+        half_edge_type *rot_next;
         half_edge_type *twin;
-        typename std::list< half_edge<Point2D>* >::iterator incident_it;
 
-        half_edge() :
+        half_edge_clipped() :
             cell(NULL),
             start_point(NULL),
             end_point(NULL),
             prev(NULL),
             next(NULL),
+            rot_prev(NULL),
+            rot_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 {
+    class voronoi_output_clipped {
     public:
         typedef typename Point2D::coordinate_type coordinate_type;
-        typedef typename detail::site_event<Point2D> site_event_type;
-        typedef typename detail::circle_event<Point2D> circle_event_type;
-        typedef cell_record<Point2D> cell_record_type;
-        typedef vertex_record<Point2D> vertex_record_type;
-        typedef half_edge<Point2D> edge_type;
-        typedef std::vector<cell_record_type> cell_records_type;
-        typedef std::list<vertex_record_type> voronoi_vertices_type;
-        typedef typename std::list<edge_type *>::iterator edge_pointer_iterator_type;
-        typedef typename std::list<edge_type *>::const_iterator edge_pointer_const_iterator_type;
-        typedef typename voronoi_vertices_type::iterator voronoi_vertices_iterator_type;
-        typedef typename voronoi_vertices_type::const_iterator
-            voronoi_vertices_const_iterator_type;
-
-        enum kOrientation {
-            LEFT_ORIENTATION = 1,
-            RIGHT_ORIENTATION = -1,
-            COLINEAR = 0,
-        };
+        typedef voronoi_record_clipped<Point2D> voronoi_record_type;
+        typedef half_edge_clipped<Point2D> edge_type;
+        typedef std::list<voronoi_record_type> voronoi_records_type;
+        typedef std::list<edge_type> voronoi_edges_type;
+        typedef typename voronoi_records_type::iterator voronoi_iterator_type;
+        typedef typename voronoi_records_type::const_iterator voronoi_const_iterator_type;
 
-        voronoi_output() {
+        voronoi_output_clipped() {
             num_cell_records_ = 0;
-            num_edges_ = 0;
             num_vertex_records_ = 0;
-        }
-
-        // This preserves the validity of iterators.
-        void init(int num_sites) {
-            cell_records_.reserve(num_sites);
-            num_cell_records_ = 0;
             num_edges_ = 0;
-            num_vertex_records_ = 0;
         }
 
         void reset() {
@@ -248,136 +203,58 @@
             edges_.clear();
 
             num_cell_records_ = 0;
-            num_edges_ = 0;
             num_vertex_records_ = 0;
+            num_edges_ = 0;
         }
 
-        // 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) {
-            num_cell_records_++;
-            num_edges_++;
-
-            // 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());
-            edge_type &edge1 = edges_.back();
-
-            // Create new half-edge that belongs to the cell with the second site.
-            edges_.push_back(edge_type());
-            edge_type &edge2 = edges_.back();
+        void set_bounding_rectangle(const BRect<Point2D> &brect) {
+            brect_ = brect;
+        }
 
-            // Add initial cell during first edge insertion.
-            if (cell_records_.empty()) {
-                cell_records_.push_back(cell_record_type(site1.get_point(), &edge1));
-                num_cell_records_++;
-                voronoi_rect_ = BRect<Point2D>(site1.get_point(), site1.get_point());
-            }
+        const BRect<Point2D> &get_bounding_rectangle() {
+            return brect_;
+        }
 
-            // 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));
-            voronoi_rect_.update(site2.get_point());
-
-            // Update pointers to cells.
-            edge1.cell = &cell_records_[site_index1];
-            edge2.cell = &cell_records_[site_index2];
-
-            // Update incident edges counters.
-            cell_records_[site_index1].num_incident_edges++;
-            cell_records_[site_index2].num_incident_edges++;
-
-            // 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) {
+        voronoi_record_type &add_vertex(const Point2D &vertex_point) {
+            vertex_records_.push_back(voronoi_record_type(vertex_point, NULL));
             num_vertex_records_++;
-            num_edges_++;
-            voronoi_rect_.update(circle.get_center());
+            return vertex_records_.back();
+        }
 
-            // 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 vertex iterator.
-            voronoi_vertices_iterator_type vertices_it = vertex_records_.end();
-            vertices_it--;
-            new_vertex.vertex_it = vertices_it;
-
-            // 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;
+        voronoi_record_type &add_boundary_vertex(const Point2D &boundary_point) {
+            vertex_records_.push_back(voronoi_record_type(boundary_point, NULL));
+            return vertex_records_.back();
+        }
 
-            // Add new half-edge.
+        edge_type &add_edge() {
             edges_.push_back(edge_type());
-            edge_type &new_edge1 = edges_.back();
-            new_edge1.cell = &cell_records_[site1.get_site_index()];
-            cell_records_[site1.get_site_index()].num_incident_edges++;
-            new_edge1.end_point = &new_vertex;
+            num_edges_++;
+            return edges_.back();
+        }
 
-            // Add new half-edge.
-            edges_.push_back(edge_type());
-            edge_type &new_edge2 = edges_.back();
-            new_edge2.cell = &cell_records_[site3.get_site_index()];
-            cell_records_[site3.get_site_index()].num_incident_edges++;
-            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);
-            edge_pointer_iterator_type temp_iter =new_vertex.incident_edges.begin();
-            edge12->incident_it = temp_iter;
-            
-            new_vertex.incident_edges.push_back(edge23);
-            temp_iter++;
-            edge23->incident_it = temp_iter;
-            
-            new_vertex.incident_edges.push_back(&new_edge2);
-            temp_iter++;
-            new_edge2.incident_it = temp_iter;
+        voronoi_record_type &add_cell(const Point2D &site_point) {
+            cell_records_.push_back(voronoi_record_type(site_point, NULL));
+            num_cell_records_++;
+            return cell_records_.back();
+        }
 
-            return &new_edge1;
+        void pop_cell() {
+            cell_records_.pop_back();
+            num_cell_records_--;
         }
 
-        const cell_records_type &get_cell_records() const {
+        const voronoi_records_type &get_cell_records() const {
             return cell_records_;
         }
 
-        const voronoi_vertices_type &get_voronoi_vertices() const {
+        const voronoi_records_type &get_voronoi_vertices() const {
             return vertex_records_;
         }
 
+        const voronoi_edges_type &get_voronoi_edges() const {
+            return edges_;
+        }
+
         int get_num_voronoi_cells() const {
             return num_cell_records_;
         }
@@ -387,120 +264,87 @@
         }
 
         int get_num_voronoi_edges() const {
-            return num_edges_;
+            return num_edges_ / 2;
         }
 
-        const BRect<Point2D> &get_voronoi_bounding_rectangle() const {
-            return voronoi_rect_;
-        }
-
-        void simplify() {
-            typename std::list<edge_type>::iterator edge_it1;
-            typename std::list<edge_type>::iterator edge_it = edges_.begin();
-
-            // Iterate over all edges and remove degeneracies.
-            while (edge_it != edges_.end()) {
-                edge_it1 = edge_it;
-                edge_it++;
-                edge_it++;
-
-                if (edge_it1->start_point && edge_it1->end_point &&
-                    edge_it1->start_point->vertex == edge_it1->end_point->vertex) {
-                    // Splice incident edges of the second voronoi vertex to the first
-                    // one, if it contains less or equal number of them.
-
-                    // Decrease number of cell incident edges.
-                    edge_it1->cell->num_incident_edges--;
-                    edge_it1->twin->cell->num_incident_edges--;
-
-                    // To guarantee N*lon(N) time we merge vertex with
-                    // less incident edges to the one with more.
-                    if (edge_it1->start_point->num_incident_edges >=
-                        edge_it1->end_point->num_incident_edges)
-                            simplify_edge(*edge_it1);
-                    else
-                        simplify_edge(*edge_it1->twin);
-
-                    // Remove zero length edges.
-                    edges_.erase(edge_it1, edge_it);
-
-                    num_vertex_records_--;
-                    num_edges_--;
-                }
-            }
-        }
-
-        bool check() const {
-            // Check correct orientation of each half_edge.
+        // Check correct orientation of each half_edge.
+        bool half_edge_orientation_check() const {
             typename std::list<edge_type>::const_iterator edge_it;
             for (edge_it = edges_.begin(); edge_it != edges_.end(); edge_it++) {
-                const Point2D &site = edge_it->cell->site_point;
                 if (edge_it->start_point != NULL && edge_it->end_point != NULL) {
-                    const Point2D &start_point = edge_it->start_point->vertex;
-                    const Point2D &end_point = edge_it->end_point->vertex;
+                    const Point2D &site = edge_it->cell->voronoi_point;
+                    const Point2D &start_point = edge_it->start_point->voronoi_point;
+                    const Point2D &end_point = edge_it->end_point->voronoi_point;
                     if (check_orientation(start_point, end_point, site) != LEFT_ORIENTATION)
                         return false;
                 }
             }
+            return true;
+        }
 
-            // Check if each site belongs to convex cell.
-            typename cell_records_type::const_iterator cell_it;
+        // Check if boundary of each cell is convex.
+        bool cell_convexity_check() const {
+            voronoi_const_iterator_type cell_it;
             for (cell_it = cell_records_.begin(); cell_it != cell_records_.end(); cell_it++) {
                 const edge_type *edge = cell_it->incident_edge;
-
-                if (edge->start_point != NULL)
-                    edge = edge->prev;
-                while (edge->start_point != NULL && edge != cell_it->incident_edge)
-                    edge = edge->prev;
-                if (edge->start_point != NULL)
-                    edge = edge->next;
-
-                while (edge->end_point != NULL && edge != cell_it->incident_edge) {
+                do {
                     if (edge->next->prev != edge)
                         return false;
                     if (edge->cell != &(*cell_it))
                         return false;
-                    if (edge->start_point != NULL && edge->next->end_point != NULL) {
-                        const Point2D &vertex1 = edge->start_point->vertex;
-                        const Point2D &vertex2 = edge->end_point->vertex;
-                        const Point2D &vertex3 = edge->next->end_point->vertex;
+                    if (edge->start_point != NULL &&
+                        edge->end_point != NULL &&
+                        edge->end_point == edge->next->start_point &&
+                        edge->next->end_point != NULL) {
+                        const Point2D &vertex1 = edge->start_point->voronoi_point;
+                        const Point2D &vertex2 = edge->end_point->voronoi_point;
+                        const Point2D &vertex3 = edge->next->end_point->voronoi_point;
                         if (check_orientation(vertex1, vertex2, vertex3) != LEFT_ORIENTATION)
                             return false;
                     }
                     edge = edge->next;
-                }
+                } while(edge != cell_it->incident_edge);
             }
+            return true;
+        }
 
-            // Check voronoi vertex incident edges correct ordering.
-            voronoi_vertices_const_iterator_type vertex_it;
+        // Check CCW ordering of incident edges of voronoi vertices.
+        bool incident_edges_order_check() const {
+            voronoi_const_iterator_type vertex_it;
             for (vertex_it = vertex_records_.begin();
                  vertex_it != vertex_records_.end(); vertex_it++) {
-                edge_pointer_const_iterator_type edge_it;
-                for (edge_it = vertex_it->incident_edges.begin();
-                     edge_it != vertex_it->incident_edges.end(); edge_it++) {
-                     edge_pointer_const_iterator_type edge_it_next1 = 
-                         vertex_it->get_next_incident_edge(edge_it);
-                     edge_pointer_const_iterator_type edge_it_next2 = 
-                         vertex_it->get_next_incident_edge(edge_it_next1);
-                     const Point2D &site1 = (*edge_it)->cell->site_point;
-                     const Point2D &site2 = (*edge_it_next1)->cell->site_point;
-                     const Point2D &site3 = (*edge_it_next2)->cell->site_point;
-                     if (check_orientation(site3, site2, site1) != LEFT_ORIENTATION)
-                         return false;
-                }
+                if (vertex_it->num_incident_edges < 3)
+                    continue;
+                edge_type *edge = vertex_it->incident_edge;
+                do {
+                    edge_type *edge_next1 = edge->rot_next;
+                    edge_type *edge_next2 = edge_next1->rot_next;
+                    const Point2D &site1 = edge->cell->voronoi_point;
+                    const Point2D &site2 = edge_next1->cell->voronoi_point;
+                    const Point2D &site3 = edge_next2->cell->voronoi_point;
+
+                    if (check_orientation(site1, site2, site3) != LEFT_ORIENTATION)
+                        return false;
+
+                    edge = edge->rot_next;
+                } while (edge != vertex_it->incident_edge);
             }
+            return true;
+        }
 
-            // Check if any two half_edges intersect not at the end point.
+        // Check if any two half_edges intersect not at the end point.
+        bool half_edges_intersection_check() const {
             // Create map from edges with first point less than the second one.
-            // Key is the first point of the edges, value is vector of second points
+            // Key is the first point of the edge, value is a vector of second points
             // with the same first point.
             std::map< Point2D, std::vector<Point2D> > edge_map;
             typedef typename std::map< Point2D, std::vector<Point2D> >::const_iterator 
                 edge_map_iterator;
+            typename std::list<edge_type>::const_iterator edge_it;
             for (edge_it = edges_.begin(); edge_it != edges_.end(); edge_it++) {
                 if (edge_it->start_point != NULL && edge_it->end_point != NULL) {
-                    const Point2D &start_point = edge_it->start_point->vertex;
-                    const Point2D &end_point = edge_it->end_point->vertex;
+                    const Point2D &start_point = edge_it->start_point->voronoi_point;
+                    const Point2D &end_point = edge_it->end_point->voronoi_point;
                     if (start_point < end_point)
                         edge_map[start_point].push_back(end_point);
                 }
@@ -511,25 +355,23 @@
             // left to right checking for intersections between all pairs of edges
             // that overlap in the x dimension.
             // Complexity. Approximately N*sqrt(N). Worst case N^2.
+            typedef typename std::vector<Point2D>::size_type size_type;
             edge_map_iterator edge_map_it1, edge_map_it2, edge_map_it_bound;
             for (edge_map_it1 = edge_map.begin();
                  edge_map_it1 != edge_map.end(); edge_map_it1++) {
                 const Point2D &point1 = edge_map_it1->first;
-
-                typedef typename std::vector<Point2D>::size_type size_type;
                 for (size_type i = 0; i < edge_map_it1->second.size(); i++) {
                     const Point2D &point2 = edge_map_it1->second[i];
                     coordinate_type min_y1 = std::min(point1.y(), point2.y());
                     coordinate_type max_y1 = std::max(point1.y(), point2.y());
 
-                    // Find the first edge with greate or equal first point.
+                    // Find the first edge with greater or equal first point.
                     edge_map_it_bound = edge_map.lower_bound(point2);
 
                     edge_map_it2 = edge_map_it1;
                     edge_map_it2++;
                     for (; edge_map_it2 != edge_map_it_bound; edge_map_it2++) {
                         const Point2D &point3 = edge_map_it2->first;
-                        
                         for (size_type j = 0; j < edge_map_it2->second.size(); j++) {
                             const Point2D &point4 = edge_map_it2->second[j];
                             coordinate_type min_y2 = std::min(point3.y(), point4.y());
@@ -550,71 +392,27 @@
                     }
                 }
             }
-
             return true;
         }
 
-        void clip(coordinate_type x_min, coordinate_type y_min,
-                  coordinate_type x_max, coordinate_type y_max) {
-
-            
+        // Make a few output checks.
+        bool check() const {
+            return half_edge_orientation_check() &&
+                   cell_convexity_check() &&
+                   incident_edges_order_check() &&
+                   half_edges_intersection_check();
         }
 
     private:
-        void simplify_edge(edge_type &edge) {
-            vertex_record_type *vertex1 = edge.start_point;
-            vertex_record_type *vertex2 = edge.end_point;
-
-            // Update number of vertex incident edges.
-            vertex1->num_incident_edges += vertex2->num_incident_edges - 2;
-
-            // Update second vertex incident edges start and end points.
-            for (edge_pointer_iterator_type it = vertex2->incident_edges.begin();
-                 it != vertex2->incident_edges.end(); it++) {
-                (*it)->start_point = vertex1;
-                (*it)->twin->end_point = vertex1;
-            }
-
-            // Update prev and next pointers of incident edges that
-            // belongs to different voronoi vertices.
-            edge_pointer_iterator_type edge1_it = edge.incident_it;
-            edge_pointer_iterator_type edge2_it = edge.twin->incident_it;
-
-            edge_pointer_const_iterator_type edge1_it_prev =
-                vertex1->get_prev_incident_edge(edge1_it);
-            edge_pointer_const_iterator_type edge1_it_next =
-                vertex1->get_next_incident_edge(edge1_it);
-
-            edge_pointer_const_iterator_type edge2_it_prev =
-                vertex2->get_prev_incident_edge(edge2_it);
-            edge_pointer_const_iterator_type edge2_it_next =
-                vertex2->get_next_incident_edge(edge2_it);
-            
-            (*edge1_it_prev)->twin->next = *edge2_it_next;
-            (*edge2_it_next)->prev = (*edge1_it_prev)->twin;
-
-            (*edge1_it_next)->prev = (*edge2_it_prev)->twin;
-            (*edge2_it_prev)->twin->next = (*edge1_it_next);
-
-            // Splice incident edges of the second voronoi vertex to the first one.
-            edge2_it++;
-            for (; edge2_it != vertex2->incident_edges.end(); edge2_it++)
-                (*edge2_it)->incident_it = vertex1->incident_edges.insert(edge1_it, *edge2_it);
-
-            edge2_it = vertex2->incident_edges.begin();
-            for (; edge2_it != edge.twin->incident_it; edge2_it++)
-                (*edge2_it)->incident_it = vertex1->incident_edges.insert(edge1_it, *edge2_it);
-
-            // Remove zero length edge from list of incident edges.
-            vertex1->incident_edges.erase(edge1_it);
-
-            // Remove second vertex from the vertex records.
-            vertex_records_.erase(vertex2->vertex_it);
-        }
+        enum kOrientation {
+            LEFT_ORIENTATION = 1,
+            RIGHT_ORIENTATION = -1,
+            COLINEAR = 0,
+        };
 
         int check_orientation(const Point2D &point1,
-                                    const Point2D &point2,
-                                    const Point2D &point3) const {
+                              const Point2D &point2,
+                              const Point2D &point3) const {
             coordinate_type a = (point2.x() - point1.x()) * (point3.y() - point2.y());
             coordinate_type b = (point2.y() - point1.y()) * (point3.x() - point2.x());
             if (a > b)
@@ -624,33 +422,14 @@
             return COLINEAR;
         }
 
-        std::vector<cell_record_type> cell_records_;
-        std::list<vertex_record_type> vertex_records_;
-        std::list<edge_type> edges_;
-
+        voronoi_records_type cell_records_;
+        voronoi_records_type vertex_records_;
+        voronoi_edges_type edges_;
+        
         int num_cell_records_;
         int num_vertex_records_;
         int num_edges_;
 
-        BRect<Point2D> voronoi_rect_;
-
-        // Disallow copy constructor and operator=
-        voronoi_output(const voronoi_output&);
-        void operator=(const voronoi_output&);
-    };
-
-    template <typename Point2D>
-    class voronoi_output_clipped {
-    public:
-        typedef typename Point2D::coordinate_type coordinate_type;
-
-        voronoi_output_clipped(const Point2D &p1, const Point2D &p2) : brect_(p1, p2) {}
-
-        void clip(const voronoi_output<Point2D> &output) {
-
-        }
-
-    private:
         BRect<Point2D> brect_;
 
         // Disallow copy constructor and operator=

Added: sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_sweepline.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_sweepline.hpp	2010-07-06 14:12:08 EDT (Tue, 06 Jul 2010)
@@ -0,0 +1,19 @@
+// Boost sweepline/voronoi_sweepline.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_SWEEPLINE
+#define BOOST_SWEEPLINE_VORONOI_SWEEPLINE
+
+#include "voronoi_output.hpp"
+
+#include "detail/voronoi_formation.hpp"
+
+#include "voronoi_builder.hpp"
+
+#endif
\ 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-07-06 14:12:08 EDT (Tue, 06 Jul 2010)
@@ -10,7 +10,7 @@
 #include <cmath>
 
 #include "test_type_list.hpp"
-#include "boost/sweepline/voronoi_output.hpp"
+#include "boost/sweepline/voronoi_sweepline.hpp"
 using namespace boost::sweepline;
 
 #define BOOST_TEST_MODULE event_queue_test

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-07-06 14:12:08 EDT (Tue, 06 Jul 2010)
@@ -8,7 +8,7 @@
 //  See http://www.boost.org for updates, documentation, and revision history.
 
 #include "test_type_list.hpp"
-#include "boost/sweepline/voronoi_output.hpp"
+#include "boost/sweepline/voronoi_sweepline.hpp"
 using namespace boost::sweepline;
 using namespace boost::sweepline::detail;
 

Modified: sandbox/SOC/2010/sweepline/libs/sweepline/test/node_comparer_test.cpp
==============================================================================
--- sandbox/SOC/2010/sweepline/libs/sweepline/test/node_comparer_test.cpp	(original)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/test/node_comparer_test.cpp	2010-07-06 14:12:08 EDT (Tue, 06 Jul 2010)
@@ -8,7 +8,7 @@
 //  See http://www.boost.org for updates, documentation, and revision history.
 
 #include "test_type_list.hpp"
-#include "boost/sweepline/voronoi_output.hpp"
+#include "boost/sweepline/voronoi_sweepline.hpp"
 using namespace boost::sweepline;
 using namespace boost::sweepline::detail;
 

Modified: sandbox/SOC/2010/sweepline/libs/sweepline/test/test_type_list.hpp
==============================================================================
--- sandbox/SOC/2010/sweepline/libs/sweepline/test/test_type_list.hpp	(original)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/test/test_type_list.hpp	2010-07-06 14:12:08 EDT (Tue, 06 Jul 2010)
@@ -12,8 +12,6 @@
 
 #include <boost/mpl/list.hpp>
 
-typedef boost::mpl::list<float,
-                         double,
-                         long double> test_types;
+typedef boost::mpl::list<double, long double> test_types;
 
 #endif

Modified: sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_builder_test.cpp
==============================================================================
--- sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_builder_test.cpp	(original)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_builder_test.cpp	2010-07-06 14:12:08 EDT (Tue, 06 Jul 2010)
@@ -11,19 +11,17 @@
 #include <time.h>
 
 #include "test_type_list.hpp"
-#include "boost/sweepline/voronoi_builder.hpp"
+#include "boost/sweepline/voronoi_sweepline.hpp"
 using namespace boost::sweepline;
 
 #define BOOST_TEST_MODULE voronoi_builder_test
 #include <boost/test/test_case_template.hpp>
 
 // Sites: (0, 0), (0, 4), (2, 1).
-BOOST_AUTO_TEST_CASE_TEMPLATE(voronoi_builder_test1, T, test_types) {
-    typedef typename voronoi_output< point_2d<T> >::edge_type edge_type;
-    typedef typename voronoi_output< point_2d<T> >::edge_pointer_const_iterator_type 
-        edge_pointer_iterator_type;
-    typedef typename voronoi_output< point_2d<T> >::voronoi_vertices_const_iterator_type
-        voronoi_vertices_iterator_type;
+BOOST_AUTO_TEST_CASE_TEMPLATE(triangle_test1, T, test_types) {
+    typedef typename voronoi_output_clipped< point_2d<T> >::edge_type edge_type;
+    typedef typename voronoi_output_clipped< point_2d<T> >::voronoi_const_iterator_type
+        voronoi_const_iterator_type;
 
     voronoi_builder<T> test_beach_line;
     point_2d<T> point1 = make_point_2d<T>(0, 0);
@@ -37,60 +35,61 @@
     
     test_beach_line.init(points);
     test_beach_line.run_sweepline();
-    const voronoi_output< point_2d<T> > &test_output = test_beach_line.get_output();
+    voronoi_output_clipped< point_2d<T> > test_output;
+    test_beach_line.clip(test_output);
     BOOST_CHECK_EQUAL(test_output.check(), true);
 
+    BRect< point_2d<T> > bounding_rectangle = test_beach_line.get_bounding_rectangle();
+    BOOST_CHECK_EQUAL(bounding_rectangle.x_min == static_cast<T>(0) &&
+                      bounding_rectangle.y_min == static_cast<T>(0) &&
+                      bounding_rectangle.x_max == static_cast<T>(2) &&
+                      bounding_rectangle.y_max == static_cast<T>(4), true);
+
     BOOST_CHECK_EQUAL(static_cast<int>(test_output.get_cell_records().size()), 3);
-    BOOST_CHECK_EQUAL(static_cast<int>(test_output.get_voronoi_vertices().size()), 1);
+    BOOST_CHECK_EQUAL(static_cast<int>(test_output.get_voronoi_vertices().size()), 4);
 
-    voronoi_vertices_iterator_type it = test_output.get_voronoi_vertices().begin();
-    BOOST_CHECK_EQUAL(static_cast<int>(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);
+    voronoi_const_iterator_type it = test_output.get_voronoi_vertices().begin();
+    BOOST_CHECK_EQUAL(it->num_incident_edges, 3);
+    BOOST_CHECK_EQUAL(it->voronoi_point.x() == static_cast<T>(0.25) &&
+                      it->voronoi_point.y() == static_cast<T>(2.0), true);
 
-    edge_pointer_iterator_type edge_it = it->incident_edges.begin();
-    edge_type *edge1_1 = *edge_it;
+    edge_type *edge1_1 = it->incident_edge;
     edge_type *edge1_2 = edge1_1->twin;
-    BOOST_CHECK_EQUAL(edge1_1->cell->site_point == point3, true);
-    BOOST_CHECK_EQUAL(edge1_2->cell->site_point == point1, true);
+    BOOST_CHECK_EQUAL(edge1_1->cell->voronoi_point == point3, true);
+    BOOST_CHECK_EQUAL(edge1_2->cell->voronoi_point == point1, true);
 
-    edge_it++;
-    edge_type *edge2_1 = *edge_it;
+    edge_type *edge2_1 = edge1_1->rot_prev;
     edge_type *edge2_2 = edge2_1->twin;
-    BOOST_CHECK_EQUAL(edge2_1->cell->site_point == point1, true);
-    BOOST_CHECK_EQUAL(edge2_2->cell->site_point == point2, true);
+    BOOST_CHECK_EQUAL(edge2_1->cell->voronoi_point == point1, true);
+    BOOST_CHECK_EQUAL(edge2_2->cell->voronoi_point == point2, true);
 
-    edge_it++;
-    edge_type *edge3_1 = *edge_it;
+    edge_type *edge3_1 = edge2_1->rot_prev;
     edge_type *edge3_2 = edge3_1->twin;
-    BOOST_CHECK_EQUAL(edge3_1->cell->site_point == point2, true);
-    BOOST_CHECK_EQUAL(edge3_2->cell->site_point == point3, true);
+    BOOST_CHECK_EQUAL(edge3_1->cell->voronoi_point == point2, true);
+    BOOST_CHECK_EQUAL(edge3_2->cell->voronoi_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_CHECK_EQUAL(edge1_1->prev == edge3_2 && edge1_1->next == edge3_2, true);
+    BOOST_CHECK_EQUAL(edge2_1->prev == edge1_2 && edge2_1->next == edge1_2, true);
+    BOOST_CHECK_EQUAL(edge3_1->prev == edge2_2 && edge3_1->next == edge2_2, true);
+
+    BOOST_CHECK_EQUAL(edge1_2->next == edge2_1 && edge1_2->prev == edge2_1, true);
+    BOOST_CHECK_EQUAL(edge2_2->next == edge3_1 && edge2_2->prev == edge3_1, true);
+    BOOST_CHECK_EQUAL(edge3_2->next == edge1_1 && edge3_2->prev == edge1_1, true);
+
+    BOOST_CHECK_EQUAL(edge1_1->rot_next == edge3_1, true);
+    BOOST_CHECK_EQUAL(edge3_1->rot_next == edge2_1, true);
+    BOOST_CHECK_EQUAL(edge2_1->rot_next == edge1_1, true);
 }
 
 // Sites: (0, 1), (2, 0), (2, 4).
-BOOST_AUTO_TEST_CASE_TEMPLATE(voronoi_builder_test2, T, test_types) {
-    typedef typename voronoi_output< point_2d<T> >::edge_type edge_type;
-    typedef typename voronoi_output< point_2d<T> >::edge_pointer_const_iterator_type 
-        edge_pointer_iterator_type;
-    typedef typename voronoi_output< point_2d<T> >::voronoi_vertices_const_iterator_type
-        voronoi_vertices_iterator_type;
+BOOST_AUTO_TEST_CASE_TEMPLATE(triangle_test2, T, test_types) {
+    typedef typename voronoi_output_clipped< point_2d<T> >::edge_type edge_type;
+    typedef typename voronoi_output_clipped< point_2d<T> >::voronoi_const_iterator_type
+        voronoi_const_iterator_type;
 
     voronoi_builder<T> test_beach_line;
     point_2d<T> point1 = make_point_2d<T>(0, 1);
@@ -104,59 +103,55 @@
     
     test_beach_line.init(points);
     test_beach_line.run_sweepline();
-    const voronoi_output< point_2d<T> > &test_output = test_beach_line.get_output();
+    voronoi_output_clipped< point_2d<T> > test_output;
+    test_beach_line.clip(test_output);
     BOOST_CHECK_EQUAL(test_output.check(), true);
 
     BOOST_CHECK_EQUAL(static_cast<int>(test_output.get_cell_records().size()), 3);
-    BOOST_CHECK_EQUAL(static_cast<int>(test_output.get_voronoi_vertices().size()), 1);
+    BOOST_CHECK_EQUAL(static_cast<int>(test_output.get_voronoi_vertices().size()), 4);
 
-    voronoi_vertices_iterator_type it = test_output.get_voronoi_vertices().begin();
-    BOOST_CHECK_EQUAL(static_cast<int>(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);
+    voronoi_const_iterator_type it = test_output.get_voronoi_vertices().begin();
+    BOOST_CHECK_EQUAL(it->num_incident_edges, 3);
+    BOOST_CHECK_EQUAL(it->voronoi_point.x() == static_cast<T>(1.75) &&
+                      it->voronoi_point.y() == static_cast<T>(2.0), true);
 
-    edge_pointer_iterator_type edge_it = it->incident_edges.begin();
-    edge_type *edge1_1 = *edge_it;
+    edge_type *edge1_1 = it->incident_edge;
     edge_type *edge1_2 = edge1_1->twin;
-    BOOST_CHECK_EQUAL(edge1_1->cell->site_point == point2, true);
-    BOOST_CHECK_EQUAL(edge1_2->cell->site_point == point1, true);
+    BOOST_CHECK_EQUAL(edge1_1->cell->voronoi_point == point2, true);
+    BOOST_CHECK_EQUAL(edge1_2->cell->voronoi_point == point1, true);
 
-    edge_it++;
-    edge_type *edge2_1 = *edge_it;
+    edge_type *edge2_1 = edge1_1->rot_prev;
     edge_type *edge2_2 = edge2_1->twin;    
-    BOOST_CHECK_EQUAL(edge2_1->cell->site_point == point1, true);
-    BOOST_CHECK_EQUAL(edge2_2->cell->site_point == point3, true);
+    BOOST_CHECK_EQUAL(edge2_1->cell->voronoi_point == point1, true);
+    BOOST_CHECK_EQUAL(edge2_2->cell->voronoi_point == point3, true);
 
-    edge_it++;
-    edge_type *edge3_1 = *edge_it;
+    edge_type *edge3_1 = edge2_1->rot_prev;
     edge_type *edge3_2 = edge3_1->twin;
-    BOOST_CHECK_EQUAL(edge3_1->cell->site_point == point3, true);
-    BOOST_CHECK_EQUAL(edge3_2->cell->site_point == point2, true);
+    BOOST_CHECK_EQUAL(edge3_1->cell->voronoi_point == point3, true);
+    BOOST_CHECK_EQUAL(edge3_2->cell->voronoi_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_CHECK_EQUAL(edge1_1->prev == edge3_2 && edge1_1->next == edge3_2, true);
+    BOOST_CHECK_EQUAL(edge2_1->prev == edge1_2 && edge2_1->next == edge1_2, true);
+    BOOST_CHECK_EQUAL(edge3_1->prev == edge2_2 && edge3_1->next == edge2_2, true);
+
+    BOOST_CHECK_EQUAL(edge1_2->next == edge2_1 && edge1_2->prev == edge2_1, true);
+    BOOST_CHECK_EQUAL(edge2_2->next == edge3_1 && edge2_2->prev == edge3_1, true);
+    BOOST_CHECK_EQUAL(edge3_2->next == edge1_1 && edge3_2->prev == edge1_1, true);
+
+    BOOST_CHECK_EQUAL(edge1_1->rot_next == edge3_1, true);
+    BOOST_CHECK_EQUAL(edge3_1->rot_next == edge2_1, true);
+    BOOST_CHECK_EQUAL(edge2_1->rot_next == edge1_1, true);
 }
 
 // Sites: (0, 0), (0, 1), (1, 0), (1, 1).
-BOOST_AUTO_TEST_CASE_TEMPLATE(voronoi_builder_test3, T, test_types) {
-    typedef typename voronoi_output< point_2d<T> >::edge_type edge_type;
-    typedef typename voronoi_output< point_2d<T> >::edge_pointer_const_iterator_type 
-        edge_pointer_iterator_type;
-    typedef typename voronoi_output< point_2d<T> >::voronoi_vertices_const_iterator_type
-        voronoi_vertices_iterator_type;
+BOOST_AUTO_TEST_CASE_TEMPLATE(square_test3, T, test_types) {
+    typedef typename voronoi_output_clipped< point_2d<T> >::edge_type edge_type;
+    typedef typename voronoi_output_clipped< point_2d<T> >::voronoi_const_iterator_type
+        voronoi_const_iterator_type;
 
     voronoi_builder<T> test_beach_line;
     std::vector< point_2d<T> > points;
@@ -167,71 +162,66 @@
     
     test_beach_line.init(points);
     test_beach_line.run_sweepline();
-    const voronoi_output< point_2d<T> > &test_output = test_beach_line.get_output();
+    voronoi_output_clipped< point_2d<T> > test_output;
+    test_beach_line.clip(test_output);
     BOOST_CHECK_EQUAL(test_output.check(), true);
 
     BOOST_CHECK_EQUAL(static_cast<T>(test_output.get_cell_records().size()), 4);
-    BOOST_CHECK_EQUAL(static_cast<T>(test_output.get_voronoi_vertices().size()), 1);
+    BOOST_CHECK_EQUAL(static_cast<T>(test_output.get_voronoi_vertices().size()), 5);
     BOOST_CHECK_EQUAL(test_output.get_num_voronoi_cells(), 4);
     BOOST_CHECK_EQUAL(test_output.get_num_voronoi_vertices(), 1);
     BOOST_CHECK_EQUAL(test_output.get_num_voronoi_edges(), 4);
 
     // Check voronoi vertex.
-    voronoi_vertices_iterator_type it = test_output.get_voronoi_vertices().begin();
-    BOOST_CHECK_EQUAL(static_cast<int>(it->incident_edges.size()), 4);
-    BOOST_CHECK_EQUAL(static_cast<int>(it->incident_edges.size()), it->num_incident_edges);
-    BOOST_CHECK_EQUAL(it->vertex.x() == static_cast<T>(0.5) &&
-                      it->vertex.y() == static_cast<T>(0.5), true);
-    BOOST_CHECK_EQUAL(it == it->vertex_it, true);
+    voronoi_const_iterator_type it = test_output.get_voronoi_vertices().begin();
+    BOOST_CHECK_EQUAL(it->num_incident_edges, 4);
+    BOOST_CHECK_EQUAL(it->voronoi_point.x() == static_cast<T>(0.5) &&
+                      it->voronoi_point.y() == static_cast<T>(0.5), true);
 
     // Check voronoi edges.
-    edge_pointer_iterator_type edge_it = it->incident_edges.begin();
-    edge_type *edge1_1 = *edge_it;
+    edge_type *edge1_1 = it->incident_edge;
     edge_type *edge1_2 = edge1_1->twin;
-    BOOST_CHECK_EQUAL(edge1_1->cell->site_point == points[2], true);
-    BOOST_CHECK_EQUAL(edge1_2->cell->site_point == points[0], true);
+    BOOST_CHECK_EQUAL(edge1_1->cell->voronoi_point == points[2], true);
+    BOOST_CHECK_EQUAL(edge1_2->cell->voronoi_point == points[0], true);
 
-    edge_it++;
-    edge_type *edge2_1 = *edge_it;
+    edge_type *edge2_1 = edge1_1->rot_prev;
     edge_type *edge2_2 = edge2_1->twin;    
-    BOOST_CHECK_EQUAL(edge2_1->cell->site_point == points[0], true);
-    BOOST_CHECK_EQUAL(edge2_2->cell->site_point == points[1], true);
+    BOOST_CHECK_EQUAL(edge2_1->cell->voronoi_point == points[0], true);
+    BOOST_CHECK_EQUAL(edge2_2->cell->voronoi_point == points[1], true);
 
-    edge_it++;
-    edge_type *edge3_1 = *edge_it;
+    edge_type *edge3_1 = edge2_1->rot_prev;
     edge_type *edge3_2 = edge3_1->twin;
-    BOOST_CHECK_EQUAL(edge3_1->cell->site_point == points[1], true);
-    BOOST_CHECK_EQUAL(edge3_2->cell->site_point == points[3], true);
+    BOOST_CHECK_EQUAL(edge3_1->cell->voronoi_point == points[1], true);
+    BOOST_CHECK_EQUAL(edge3_2->cell->voronoi_point == points[3], true);
 
-    edge_it++;
-    edge_type *edge4_1 = *edge_it;
+    edge_type *edge4_1 = edge3_1->rot_prev;
     edge_type *edge4_2 = edge4_1->twin;
-    BOOST_CHECK_EQUAL(edge4_1->cell->site_point == points[3], true);
-    BOOST_CHECK_EQUAL(edge4_2->cell->site_point == points[2], true);
+    BOOST_CHECK_EQUAL(edge4_1->cell->voronoi_point == points[3], true);
+    BOOST_CHECK_EQUAL(edge4_2->cell->voronoi_point == points[2], 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(edge4_2->twin == edge4_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(edge4_1->next == NULL && edge4_2->prev == NULL, true);
-
-    BOOST_CHECK_EQUAL(edge1_1->prev == edge4_2, true);
-    BOOST_CHECK_EQUAL(edge2_1->prev == edge1_2, true);
-    BOOST_CHECK_EQUAL(edge3_1->prev == edge2_2, true);
-    BOOST_CHECK_EQUAL(edge4_1->prev == edge3_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 == edge4_1, true);
-    BOOST_CHECK_EQUAL(edge4_2->next == edge1_1, true);
+    BOOST_CHECK_EQUAL(edge1_1->prev == edge4_2 && edge1_1->next == edge4_2, true);
+    BOOST_CHECK_EQUAL(edge2_1->prev == edge1_2 && edge2_1->next == edge1_2, true);
+    BOOST_CHECK_EQUAL(edge3_1->prev == edge2_2 && edge3_1->next == edge2_2, true);
+    BOOST_CHECK_EQUAL(edge4_1->prev == edge3_2 && edge4_1->next == edge3_2, true);
+
+    BOOST_CHECK_EQUAL(edge1_2->next == edge2_1 && edge1_2->prev == edge2_1, true);
+    BOOST_CHECK_EQUAL(edge2_2->next == edge3_1 && edge2_2->prev == edge3_1, true);
+    BOOST_CHECK_EQUAL(edge3_2->next == edge4_1 && edge3_2->prev == edge4_1, true);
+    BOOST_CHECK_EQUAL(edge4_2->next == edge1_1 && edge4_2->prev == edge1_1, true);
+
+    BOOST_CHECK_EQUAL(edge1_1->rot_next == edge4_1, true);
+    BOOST_CHECK_EQUAL(edge4_1->rot_next == edge3_1, true);
+    BOOST_CHECK_EQUAL(edge3_1->rot_next == edge2_1, true);
+    BOOST_CHECK_EQUAL(edge2_1->rot_next == edge1_1, true);
 }
 
 // Sites: {(x, y) | x = 0 .. 3, y = 0 .. 3}.
-BOOST_AUTO_TEST_CASE_TEMPLATE(voronoi_builder_test4, T, test_types) {
+BOOST_AUTO_TEST_CASE_TEMPLATE(grid_test1, T, test_types) {
     voronoi_builder<T> test_beach_line;
     std::vector< point_2d<T> > points;
     for (int i = 0; i < 3; i++)
@@ -241,7 +231,8 @@
     
     test_beach_line.init(points);
     test_beach_line.run_sweepline();
-    const voronoi_output< point_2d<T> > &test_output = test_beach_line.get_output();
+    voronoi_output_clipped< point_2d<T> > test_output;
+    test_beach_line.clip(test_output);
     BOOST_CHECK_EQUAL(test_output.check(), true);
 
     BOOST_CHECK_EQUAL(test_output.get_num_voronoi_cells(), 9);
@@ -249,28 +240,8 @@
     BOOST_CHECK_EQUAL(test_output.get_num_voronoi_edges(), 12);
 }
 
-// Generate 10 random sites 1000 times.
-BOOST_AUTO_TEST_CASE_TEMPLATE(voronoi_builder_test4_1, T, test_types) {
-    srand(static_cast<unsigned int>(time(NULL)));
-    voronoi_builder<T> test_beach_line;
-    std::vector< point_2d<T> > points;
-    for (int i = 0; i < 1000; i++) {
-        points.clear();
-        for (int j = 0; j < 10; j++)
-            points.push_back(make_point_2d<T>(static_cast<T>(rand() % 100),
-                                              static_cast<T>(rand() % 100)));
-        test_beach_line.init(points);
-        test_beach_line.run_sweepline();
-        test_beach_line.reset();
-    }
-    
-    test_beach_line.init(points);
-    test_beach_line.run_sweepline();
-    BOOST_CHECK_EQUAL(test_beach_line.get_output().check(), true);
-}
-
 // Sites: {(x, y) | x = 0 .. 9, y = 0 .. 9}.
-BOOST_AUTO_TEST_CASE_TEMPLATE(voronoi_builder_test5, T, test_types) {
+BOOST_AUTO_TEST_CASE_TEMPLATE(grid_test2, T, test_types) {
     voronoi_builder<T> test_beach_line;
     std::vector< point_2d<T> > points;
     for (int i = 0; i < 10; i++)
@@ -280,7 +251,8 @@
     
     test_beach_line.init(points);
     test_beach_line.run_sweepline();
-    const voronoi_output< point_2d<T> > &test_output = test_beach_line.get_output();
+    voronoi_output_clipped< point_2d<T> > test_output;
+    test_beach_line.clip(test_output);
     BOOST_CHECK_EQUAL(test_output.check(), true);
 
     BOOST_CHECK_EQUAL(test_output.get_num_voronoi_cells(), 100);
@@ -288,28 +260,8 @@
     BOOST_CHECK_EQUAL(test_output.get_num_voronoi_edges(), 180);
 }
 
-// Generate 100 random sites 100 times.
-BOOST_AUTO_TEST_CASE_TEMPLATE(voronoi_builder_test5_1, T, test_types) {
-    srand(static_cast<unsigned int>(time(NULL)));
-    voronoi_builder<T> test_beach_line;
-    std::vector< point_2d<T> > points;
-    for (int i = 0; i < 100; i++) {
-        points.clear();
-        for (int j = 0; j < 100; j++)
-            points.push_back(make_point_2d<T>(static_cast<T>(rand() % 100),
-                                              static_cast<T>(rand() % 100)));
-        test_beach_line.init(points);
-        test_beach_line.run_sweepline();
-        test_beach_line.reset();
-    }
-    
-    test_beach_line.init(points);
-    test_beach_line.run_sweepline();
-    BOOST_CHECK_EQUAL(test_beach_line.get_output().check(), true);
-}
-
 // Sites: {(x, y) | x = 0 .. 33, y = 0 .. 33}.
-BOOST_AUTO_TEST_CASE_TEMPLATE(voronoi_builder_test6, T, test_types) {
+BOOST_AUTO_TEST_CASE_TEMPLATE(grid_test3, T, test_types) {
     voronoi_builder<T> test_beach_line;
     std::vector< point_2d<T> > points;
     for (int i = 0; i < 33; i++)
@@ -319,7 +271,8 @@
     
     test_beach_line.init(points);
     test_beach_line.run_sweepline();
-    const voronoi_output< point_2d<T> > &test_output = test_beach_line.get_output();
+    voronoi_output_clipped< point_2d<T> > test_output;
+    test_beach_line.clip(test_output);
     BOOST_CHECK_EQUAL(test_output.check(), true);
 
     BOOST_CHECK_EQUAL(test_output.get_num_voronoi_cells(), 1089);
@@ -327,28 +280,8 @@
     BOOST_CHECK_EQUAL(test_output.get_num_voronoi_edges(), 2112);
 }
 
-// Generate 1000 random sites 10 times.
-BOOST_AUTO_TEST_CASE_TEMPLATE(voronoi_builder_test6_1, T, test_types) {
-    srand(static_cast<unsigned int>(time(NULL)));
-    voronoi_builder<T> test_beach_line;
-    std::vector< point_2d<T> > points;
-    for (int i = 0; i < 10; i++) {
-        points.clear();
-        for (int j = 0; j < 1000; j++)
-            points.push_back(make_point_2d<T>(static_cast<T>(rand() % 100),
-                                              static_cast<T>(rand() % 100)));
-        test_beach_line.init(points);
-        test_beach_line.run_sweepline();
-        test_beach_line.reset();
-    }
-    
-    test_beach_line.init(points);
-    test_beach_line.run_sweepline();
-    BOOST_CHECK_EQUAL(test_beach_line.get_output().check(), true);
-}
-
 // Sites: {(x, y) | x = 0 .. 100, y = 0 .. 100}.
-BOOST_AUTO_TEST_CASE_TEMPLATE(voronoi_builder_test7, T, test_types) {
+BOOST_AUTO_TEST_CASE_TEMPLATE(grid_test4, T, test_types) {
     voronoi_builder<T> test_beach_line;
     std::vector< point_2d<T> > points;
     for (int i = 0; i < 100; i++)
@@ -358,7 +291,8 @@
     
     test_beach_line.init(points);
     test_beach_line.run_sweepline();
-    const voronoi_output< point_2d<T> > &test_output = test_beach_line.get_output();
+    voronoi_output_clipped< point_2d<T> > test_output;
+    test_beach_line.clip(test_output);
     BOOST_CHECK_EQUAL(test_output.check(), true);
 
     BOOST_CHECK_EQUAL(test_output.get_num_voronoi_cells(), 10000);
@@ -366,22 +300,8 @@
     BOOST_CHECK_EQUAL(test_output.get_num_voronoi_edges(), 19800);
 }
 
-// Generate 10000 random sites.
-BOOST_AUTO_TEST_CASE_TEMPLATE(voronoi_builder_test7_1, T, test_types) {
-    srand(static_cast<unsigned int>(time(NULL)));
-    voronoi_builder<T> test_beach_line;
-    std::vector< point_2d<T> > points;
-    for (int i = 0; i < 10000; i++)
-        points.push_back(make_point_2d<T>(static_cast<T>(rand() % 1000),
-                                          static_cast<T>(rand() % 1000)));
-    
-    test_beach_line.init(points);
-    test_beach_line.run_sweepline();
-    BOOST_CHECK_EQUAL(test_beach_line.get_output().check(), true);
-}
-
 // Sites: {(x, y) | x = 0 .. 333, y = 0 .. 333}.
-BOOST_AUTO_TEST_CASE_TEMPLATE(voronoi_builder_test8, T, test_types) {
+BOOST_AUTO_TEST_CASE_TEMPLATE(grid_test5, T, test_types) {
     voronoi_builder<T> test_beach_line;
     std::vector< point_2d<T> > points;
     for (int i = 0; i < 333; i++)
@@ -391,10 +311,87 @@
     
     test_beach_line.init(points);
     test_beach_line.run_sweepline();
-    const voronoi_output< point_2d<T> > &test_output = test_beach_line.get_output();
+    voronoi_output_clipped< point_2d<T> > test_output;
+    test_beach_line.clip(test_output);
     BOOST_CHECK_EQUAL(test_output.check(), true);
 
     BOOST_CHECK_EQUAL(test_output.get_num_voronoi_cells(), 110889);
     BOOST_CHECK_EQUAL(test_output.get_num_voronoi_vertices(), 110224);
     BOOST_CHECK_EQUAL(test_output.get_num_voronoi_edges(), 221112);
 }
+
+// Generate 10 random sites 10000 times.
+BOOST_AUTO_TEST_CASE_TEMPLATE(random_test1, T, test_types) {
+    srand(static_cast<unsigned int>(time(NULL)));
+    voronoi_builder<T> test_beach_line;
+    voronoi_output_clipped< point_2d<T> > test_output;
+    std::vector< point_2d<T> > points;
+    for (int i = 0; i < 10000; i++) {
+        points.clear();
+        for (int j = 0; j < 10; j++)
+            points.push_back(make_point_2d<T>(static_cast<T>(rand() % 10),
+                                              static_cast<T>(rand() % 10)));
+        test_beach_line.init(points);
+        test_beach_line.run_sweepline();
+        test_beach_line.clip(test_output);
+        BOOST_CHECK_EQUAL(test_output.check(), true);
+        test_beach_line.reset();
+    }
+}
+
+// Generate 100 random sites 1000 times.
+BOOST_AUTO_TEST_CASE_TEMPLATE(random_test2, T, test_types) {
+    srand(static_cast<unsigned int>(time(NULL)));
+    voronoi_builder<T> test_beach_line;
+    voronoi_output_clipped< point_2d<T> > test_output;
+    std::vector< point_2d<T> > points;
+    for (int i = 0; i < 1000; i++) {
+        points.clear();
+        for (int j = 0; j < 100; j++)
+            points.push_back(make_point_2d<T>(static_cast<T>(rand() % 100),
+                                              static_cast<T>(rand() % 100)));
+        test_beach_line.init(points);
+        test_beach_line.run_sweepline();
+        test_beach_line.clip(test_output);
+        BOOST_CHECK_EQUAL(test_output.check(), true);
+        test_beach_line.reset();
+    }
+}
+
+// Generate 1000 random sites 100 times.
+BOOST_AUTO_TEST_CASE_TEMPLATE(random_test3, T, test_types) {
+    srand(static_cast<unsigned int>(time(NULL)));
+    voronoi_builder<T> test_beach_line;
+    voronoi_output_clipped< point_2d<T> > test_output;
+    std::vector< point_2d<T> > points;
+    for (int i = 0; i < 100; i++) {
+        points.clear();
+        for (int j = 0; j < 1000; j++)
+        points.push_back(make_point_2d<T>(static_cast<T>(rand() % 100),
+                                          static_cast<T>(rand() % 100)));
+        test_beach_line.init(points);
+        test_beach_line.run_sweepline();
+        test_beach_line.clip(test_output);
+        BOOST_CHECK_EQUAL(test_output.check(), true);
+        test_beach_line.reset();
+    }
+}
+
+// Generate 10000 random sites 10 times.
+BOOST_AUTO_TEST_CASE_TEMPLATE(random_test4, T, test_types) {
+    srand(static_cast<unsigned int>(time(NULL)));
+    voronoi_builder<T> test_beach_line;
+    voronoi_output_clipped< point_2d<T> > test_output;
+    std::vector< point_2d<T> > points;
+    for (int i = 0; i < 10; i++) {
+        points.clear();
+        for (int j = 0; j < 10000; j++)
+        points.push_back(make_point_2d<T>(static_cast<T>(rand() % 1000),
+                                          static_cast<T>(rand() % 1000)));
+        test_beach_line.init(points);
+        test_beach_line.run_sweepline();
+        test_beach_line.clip(test_output);
+        BOOST_CHECK_EQUAL(test_output.check(), true);
+        test_beach_line.reset();
+    }
+}