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

Subject: [Boost-commit] svn:boost r65016 - in sandbox/SOC/2010/sweepline: boost/sweepline boost/sweepline/detail libs/sweepline/test/voronoi_segment
From: sydorchuk.andriy_at_[hidden]
Date: 2010-08-26 09:10:10

Author: asydorchuk
Date: 2010-08-26 09:10:07 EDT (Thu, 26 Aug 2010)
New Revision: 65016
URL: http://svn.boost.org/trac/boost/changeset/65016

Log:
Added inscribed circle predicates for (point, point, segment) case.
Added basic tests for voronoi of segments with one segment.
Updated (point-segment) predicate.
Updated beach line nodes comparison predicate.

Text files modified: 
   sandbox/SOC/2010/sweepline/boost/sweepline/detail/voronoi_segment_formation.hpp                 |   194 ++++++++++++++++++++++++++------------- 
   sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_segment_builder.hpp                          |   189 +++++++++++++++++++++++++++++---------  
   sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_segment/segment_event_types_test.cpp     |   126 +++++++++++++++++++------               
   sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_segment/segment_node_comparer_test.cpp   |    14 ++                                      
   sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_segment/segment_voronoi_builder_test.cpp |    86 +++++++++++++++++                       
   5 files changed, 465 insertions(+), 144 deletions(-)

Modified: sandbox/SOC/2010/sweepline/boost/sweepline/detail/voronoi_segment_formation.hpp
==============================================================================
--- sandbox/SOC/2010/sweepline/boost/sweepline/detail/voronoi_segment_formation.hpp	(original)
+++ sandbox/SOC/2010/sweepline/boost/sweepline/detail/voronoi_segment_formation.hpp	2010-08-26 09:10:07 EDT (Thu, 26 Aug 2010)
@@ -109,6 +109,42 @@
         }
     }
 
+    kOrientation orientation_test(long long dif_x1_, long long dif_y1_,
+                                  long long dif_x2_, long long dif_y2_) {
+        typedef unsigned long long ull;
+        ull dif_x1, dif_y1, dif_x2, dif_y2;
+        bool dif_x1_plus, dif_x2_plus, dif_y1_plus, dif_y2_plus;
+        INT_PREDICATE_CONVERT_65_BIT(dif_x1_, dif_x1, dif_x1_plus);
+        INT_PREDICATE_CONVERT_65_BIT(dif_y1_, dif_y1, dif_y1_plus);
+        INT_PREDICATE_CONVERT_65_BIT(dif_x2_, dif_x2, dif_x2_plus);
+        INT_PREDICATE_CONVERT_65_BIT(dif_y2_, dif_y2, dif_y2_plus);
+        
+        ull expr_l = dif_x1 * dif_y2;
+        bool expr_l_plus = (dif_x1_plus == dif_y2_plus) ? true : false;
+        ull expr_r = dif_x2 * dif_y1;
+        bool expr_r_plus = (dif_x2_plus == dif_y1_plus) ? true : false;
+
+        if (expr_l == 0)
+            expr_l_plus = true;
+        if (expr_r == 0)
+            expr_r_plus = true;
+        
+        if ((expr_l_plus == expr_r_plus) && (expr_l == expr_r))
+            return COLINEAR;
+
+        if (!expr_l_plus) {
+            if (expr_r_plus)
+                return RIGHT_ORIENTATION;
+            else
+                return (expr_l > expr_r) ? RIGHT_ORIENTATION : LEFT_ORIENTATION; 
+        } else {
+            if (!expr_r_plus)
+                return LEFT_ORIENTATION;
+            else
+                return (expr_l < expr_r) ? RIGHT_ORIENTATION : LEFT_ORIENTATION;
+        }
+    }
+
     enum kPredicateResult {
         LESS = -1,
         UNDEFINED = 0,
@@ -211,13 +247,12 @@
                                           bool reverse_order) {
         typedef long long ll;
         typedef unsigned long long ull;
-        bool is_right_oriented1 =
-            orientation_test(segment_start, segment_end, site_point) != LEFT_ORIENTATION;
-        bool is_right_oriented2 =
-            orientation_test(segment_start, segment_end, new_point) != LEFT_ORIENTATION;
-        if (is_right_oriented1 != is_right_oriented2) {
-            return (is_right_oriented1) ? LESS : MORE;
-        }
+        kOrientation orientation1 = orientation_test(segment_start, segment_end, site_point);
+        kOrientation orientation2 = orientation_test(segment_start, segment_end, new_point);
+        if (orientation1 == COLINEAR)
+            orientation1 = reverse_order ? LEFT_ORIENTATION : RIGHT_ORIENTATION;
+        if (orientation1 != orientation2)
+            return (orientation1 == RIGHT_ORIENTATION) ? LESS : MORE;
 
         ll dif_x = static_cast<ll>(new_point.x()) - static_cast<ll>(site_point.x());
         ll dif_y = static_cast<ll>(new_point.y()) - static_cast<ll>(site_point.y());
@@ -225,18 +260,16 @@
         ll b = static_cast<ll>(segment_end.y()) - static_cast<ll>(segment_start.y());
 
         if (a == 0) {
-            if (new_point.y() <= site_point.y() && !reverse_order)
+            if (new_point.y() < site_point.y() && !reverse_order)
                 return MORE;
-            else if (new_point.y() >= site_point.y() && reverse_order)
+            else if (new_point.y() > site_point.y() && reverse_order)
                 return LESS;
             return UNDEFINED;
         } else {
-            point_2d<T> point3 = make_point_2d(segment_end.x() + static_cast<T>(dif_x),
-                                               segment_end.y() + static_cast<T>(dif_y));
-            bool right_oriented =
-                orientation_test(segment_start, segment_end, point3) != LEFT_ORIENTATION;
-            if (is_right_oriented1 ^ right_oriented) {
-                if (is_right_oriented1)
+            kOrientation orientation = orientation_test(a, b, dif_x, dif_y);
+            if ((orientation == COLINEAR) ||
+                ((orientation1 == RIGHT_ORIENTATION) ^ (orientation == RIGHT_ORIENTATION))) {
+                if (orientation1 == RIGHT_ORIENTATION)
                     return reverse_order ? LESS : UNDEFINED;
                 return reverse_order ? UNDEFINED : MORE;
             }            
@@ -250,7 +283,8 @@
                                  static_cast<double>(dif_x) *
                                  static_cast<double>(dif_y);
         if (!(almost_equal(fast_left_expr, fast_right_expr, 4))) {
-            if (is_right_oriented1 ^ (fast_left_expr > fast_right_expr) ^ !reverse_order)
+            if ((orientation1 == RIGHT_ORIENTATION) ^
+                (fast_left_expr > fast_right_expr) ^ !reverse_order)
                 return reverse_order ? LESS : MORE;
             return UNDEFINED;
         }
@@ -282,7 +316,7 @@
             bool left_expr_odd = (left_expr_div % 2 == 1);
             left_expr_div >>= 1;
             if (left_expr_div != right_expr_div) {
-                comparison_result = (left_expr_div >= right_expr_div);
+                comparison_result = (left_expr_div > right_expr_div);
             } else {
                 ull temp_right = right_expr_denom - right_expr_mod;
                 if (temp_right > right_expr_mod) {
@@ -299,16 +333,16 @@
                 left_expr_div = left_expr_mod / dif_x_rob;
                 right_expr_div = right_expr_mod / a_rob;
                 if (left_expr_div != right_expr_div)
-                    comparison_result = (left_expr_div >= right_expr_div);
+                    comparison_result = (left_expr_div > right_expr_div);
                 else {
                     left_expr_mod = left_expr_mod % dif_x_rob;
                     right_expr_mod = right_expr_mod % a_rob;
-                    comparison_result = (left_expr_mod * a_rob >= right_expr_mod * dif_x_rob);
+                    comparison_result = (left_expr_mod * a_rob > right_expr_mod * dif_x_rob);
                 }
             }
         }
         
-        if (is_right_oriented1 ^ comparison_result ^ !reverse_order)
+        if ((orientation1 == RIGHT_ORIENTATION) ^ comparison_result ^ !reverse_order)
             return reverse_order ? LESS : MORE;
         return UNDEFINED;
     }
@@ -531,33 +565,57 @@
             return !((*this) == s_event);
         }
 
+        //// All the sites are sorted due to coordinates of the first point.
+        //// Point sites preceed segment sites with the same first point.
+        //// Segments with the same first point use counterclockwise comparison.
+        //bool operator<(const site_event &s_event) const {
+        //    // If first points have different x coordinates, compare them.
+        //    if (this->point0_.x() != s_event.point0_.x())
+        //        return this->point0_.x() < s_event.point0_.x();
+
+        //    // If first points have different y coordinates, compare them.
+        //    if (this->point0_.y() != s_event.point0_.y() ||
+        //        !(this->is_segment_ || s_event.is_segment_))
+        //        return this->point0_.y() < s_event.point0_.y();
+
+        //    // Point site events go before segment site events with the same first point.
+        //    if (this->is_segment_ ^ s_event.is_segment_)
+        //        return !this->is_segment;
+
+        //    // Use angle comparison for segment sites with the same first point.
+        //    return orientation_test(this->point1_, this->point0_, s_event.point1_) ==
+        //           RIGHT_ORIENTATION;
+        //}
+
         // All the sites are sorted due to coordinates of the first point.
-        // Also non vertical segments follow after sites with the same 
-        // x coordinate of the first point.
+        // Point sites preceed vertical segment sites with the same first point.
+        // Point sites and vertical segments preceed not vertical segments with
+        // the same x coordinate of the first point.
+        // Non vertical segments with the same first point are sorted counterclockwise.
         bool operator<(const site_event &s_event) const {
             // If first points have different x coordinates, compare them.
             if (this->point0_.x() != s_event.point0_.x())
                 return this->point0_.x() < s_event.point0_.x();
 
-            if (!this->is_segment_ || this->is_vertical_) {
-                // The first site is a point or a vertical segment.
-                if (!s_event.is_segment_ || s_event.is_vertical_) {
-                    // The second site is a point or a vertical segment.
-                    // Compare y coordinates.
+            if (!(this->is_segment_)) {
+                if (!s_event.is_segment_) {
                     return this->point0_.y() < s_event.point0_.y();
                 }
-                // The second site is a segment, but not vertical.
+                if (s_event.is_vertical_) {
+                    return this->point0_.y() <= s_event.point0_.y();
+                }
                 return true;
             } else {
-                // The first site is a segment, but not vertical.
                 if (!s_event.is_segment_ || s_event.is_vertical_) {
-                    // The second site is a point or a vertical segment.
+                    if (this->is_vertical_) {
+                        return this->point0_.y() < s_event.point0_.y();
+                    }
                     return false;
                 }
-                // The second site is a segment, but not vertical.
+                if (this->is_vertical_)
+                    return true;
                 if (this->point0_.y() != s_event.point0_.y())
                     return this->point0_.y() < s_event.point0_.y();
-
                 // Sort by angle.
                 return orientation_test(this->point1_, this->point0_, s_event.point1_) ==
                        RIGHT_ORIENTATION;
@@ -878,12 +936,32 @@
             right_site_ = site;
         }
 
-        // Returns the rightmost site.
-        // Works correctly for vertical segments.
-        const site_event_type& get_new_site() const {
-            if (left_site_.x() > right_site_.x())
-                return left_site_;
-            return right_site_;
+        coordinate_type get_comparison_x() const {
+            return (left_site_.get_site_index() >= right_site_.get_site_index()) ?
+                   left_site_.x() : right_site_.x();
+        }
+
+        std::pair<coordinate_type, int> get_comparison_y() const {
+            // If node is lookup node.
+            if (left_site_.get_site_index() == right_site_.get_site_index())
+                return std::make_pair(left_site_.y(), 0);
+            if (left_site_.get_site_index() > right_site_.get_site_index()) {
+                if (left_site_.x() != right_site_.x() &&
+                    left_site_.is_segment() && left_site_.is_vertical())
+                    return std::make_pair(left_site_.get_point1().y(), 1);
+                return std::make_pair(left_site_.y(), 1);
+            }
+            return std::make_pair(right_site_.y(), -1);
+        }
+
+        int get_comparison_index() const {
+            return (left_site_.get_site_index() > right_site_.get_site_index()) ?
+                   left_site_.get_site_index() : right_site_.get_site_index();
+        }
+
+        const Point2D &get_comparison_point() const {
+            return (left_site_.get_site_index() >= right_site_.get_site_index()) ?
+                   left_site_.get_point0() : right_site_.get_point0();
         }
 
         bool less(const Point2D &new_site) const {
@@ -964,41 +1042,27 @@
 
         // Compares nodes in the balanced binary search tree. Nodes are
         // compared based on the y coordinates of the arcs intersection points.
-        // Nodes with lesser y coordinate of the intersection point go first.
+        // Nodes with less y coordinate of the intersection point go first.
         // Comparison is only called during site events processing. That's why
         // one of the nodes will always lie on the sweepline. Comparison won't
         // work fine for nodes situated above sweepline.
         bool operator() (const BeachLineNode &node1,
                          const BeachLineNode &node2) const {
             // Get x coordinate of the righmost site from both nodes.
-            coordinate_type node1_line = node1.get_new_site().x();
-            coordinate_type node2_line = node2.get_new_site().x();
+            coordinate_type node1_x = node1.get_comparison_x();
+            coordinate_type node2_x = node2.get_comparison_x();
 
-            if (node1_line < node2_line) {
-                return node1.less(node2.get_new_site().get_point0());
-            } else if (node1_line > node2_line) {
-                return !node2.less(node1.get_new_site().get_point0());
+            if (node1_x < node2_x) {
+                return node1.less(node2.get_comparison_point());
+            } else if (node1_x > node2_x) {
+                return !node2.less(node1.get_comparison_point());
             } else {
-                // Both nodes are situated on the same vertical line.
-                // Let A be the new site event point, and B the site that
-                // creates arc above A. In this case two new nodes are being
-                // inserted: (A,B) and (B,A). As intersection points for the
-                // first node and for the second are the same we need to
-                // compare them based on some another characteristic.
-                // That's why we assume that node (C, D) goes before node
-                // (D, C), only if D lies on the sweepline.
-                if (node1.get_left_site().get_site_index() ==
-                    node2.get_right_site().get_site_index() &&
-                    node1.get_right_site().get_site_index() ==
-                    node2.get_left_site().get_site_index())
-                    return node1.get_right_site().x() == node1_line;
-
-                if (node1.get_right_site().get_point0().x() == node1_line &&
-                    node1.get_right_site().get_point0() == node2.get_left_site().get_point0())
-                    return true;
-
-                // Just compare coordinates of the sites situated on the sweepline.
-                return node1.get_new_site().y() < node2.get_new_site().y();
+                std::pair<coordinate_type, int> y1 = node1.get_comparison_y();
+                std::pair<coordinate_type, int> y2 = node2.get_comparison_y();
+                if (y1 != y2)
+                    return y1 < y2;
+                return (node1.get_comparison_index() > node2.get_comparison_index()) ?
+                       (y1.second > 0) : (y2.second < 0);
             }
         }
     };

Modified: sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_segment_builder.hpp
==============================================================================
--- sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_segment_builder.hpp	(original)
+++ sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_segment_builder.hpp	2010-08-26 09:10:07 EDT (Thu, 26 Aug 2010)
@@ -34,6 +34,11 @@
             init(points, empty_vec);
         }
 
+        void init(std::vector<Segment2D> &segments) {
+            std::vector<Point2D> empty_vec;
+            init(empty_vec, segments);
+        }
+
         // Init beach line before sweepline run.
         // In case of a few first sites situated on the same
         // vertical line, we init beach line with all of them.
@@ -181,7 +186,6 @@
             Key new_left_node(*it_first, *it_second);
             Key new_right_node(*it_second, *it_first);
 
-            // TODO(asydorchuk) change output insertion!!!.
             // Update output.
             edge_type *edge = output_.insert_new_edge(*it_first, *it_second);
 
@@ -303,7 +307,7 @@
             // Let circle event sites be A, B, C, two bisectors that define
             // circle event be (A, B), (B, C). During circle event processing
             // we remove (A, B), (B, C) and insert (A, C). As beach line nodes 
-            // comparer doesn't work fine for the circle events. We only remove
+            // comparer doesn't work fine for the circle events we only remove
             // (B, C) bisector and change (A, B) bisector to the (A, C). That's
             // why we use const_cast there and take all the responsibility that
             // map data structure keeps correct ordering.
@@ -354,47 +358,11 @@
             return it;
         }
 
-        // Create circle event from the given three points.
-        bool create_circle_event(const site_event_type &site1,
-                                 const site_event_type &site2,
-                                 const site_event_type &site3,
-                                 circle_event_type &c_event) const {
-            //mpz_class dif_x1, dif_x2, dif_y1, dif_y2, a;
-            //dif_x1 = static_cast<int>(site1.x() - site2.x());
-            //dif_x2 = static_cast<int>(site2.x() - site3.x());
-            //dif_y1 = static_cast<int>(site1.y() - site2.y());
-            //dif_y2 = static_cast<int>(site2.y() - site3.y());
-            //a = (dif_x1 * dif_y2 - dif_y1 * dif_x2) * 2;
-            //
-            //// Check if bisectors intersect.
-            //if (a >= 0)
-            //    return false;
-
-            //mpz_class sum_x1, sum_x2, sum_y1, sum_y2, b1, b2;
-            //sum_x1 = static_cast<int>(site1.x() + site2.x());
-            //sum_x2 = static_cast<int>(site2.x() + site3.x());
-            //sum_y1 = static_cast<int>(site1.y() + site2.y());
-            //sum_y2 = static_cast<int>(site2.y() + site3.y());
-            //b1 = dif_x1 * sum_x1 + dif_y1 * sum_y1;
-            //b2 = dif_x2 * sum_x2 + dif_y2 * sum_y2;
-
-            //mpq_class c_x(b1 * dif_y2 - b2 * dif_y1, a);
-            //c_x.canonicalize();
-            //mpq_class c_y(b2 * dif_x1 - b1 * dif_x2, a);
-            //c_y.canonicalize();
-            //mpq_class temp_x(c_x - site1.x());
-            //mpq_class temp_y(c_y - site1.y());
-            //mpq_class sqr_radius(temp_x * temp_x + temp_y * temp_y);
-
-            //// Create new circle event;
-            //c_event = detail::make_circle_event<coordinate_type>(c_x.get_d(),
-            //                                                     c_y.get_d(),
-            //                                                     sqr_radius.get_d());
-            //c_event.set_sites(site1.get_site_index(),
-            //                  site2.get_site_index(),
-            //                  site3.get_site_index());
-            //return true;
-
+        // Create circle event from three point sites.
+        bool create_circle_event_ppp(const site_event_type &site1,
+                                     const site_event_type &site2,
+                                     const site_event_type &site3,
+                                     circle_event_type &c_event) const {
             // Check if bisectors intersect.
             if (detail::orientation_test(site1.get_point0(),site2.get_point0(),
                 site3.get_point0()) != detail::RIGHT_ORIENTATION)
@@ -412,12 +380,143 @@
             // Create new circle event.
             coordinate_type c_x = (b1*(site2.y() - site3.y()) - b2*(site1.y() - site2.y())) / a;
             coordinate_type c_y = (b2*(site1.x() - site2.x()) - b1*(site2.x() - site3.x())) / a;
-            coordinate_type radius = sqrt((c_x-site1.x())*(c_x-site1.x()) +
-                                          (c_y-site1.y())*(c_y-site1.y()));
+            coordinate_type radius = sqrt((c_x-site2.x())*(c_x-site2.x()) +
+                                          (c_y-site2.y())*(c_y-site2.y()));
             c_event = detail::make_circle_event<coordinate_type>(c_x, c_y, c_x + radius);
             return true;
         }
 
+        // Create circle event from two point sites and one segment site.
+        bool create_circle_event_pps(const site_event_type &site1,
+                                     const site_event_type &site2,
+                                     const site_event_type &site3,
+                                     int segment_index,
+                                     circle_event_type &c_event) const {
+            // Check if bisectors intersect.
+            detail::kOrientation orientation1 = detail::orientation_test(
+                site3.get_point0(), site3.get_point1(), site1.get_point0());
+            detail::kOrientation orientation2 = detail::orientation_test(
+                site3.get_point0(), site3.get_point1(), site2.get_point0());
+
+            // If point sites are situated on different sides of segment return false.
+            if (static_cast<int>(orientation1) * static_cast<int>(orientation2) == -1)
+                return false;
+
+            if ((orientation1 == detail::COLINEAR) && (orientation2 == detail::COLINEAR))
+                return false;
+
+            bool right_oriented = (orientation1 == detail::RIGHT_ORIENTATION) ||
+                                  (orientation2 == detail::RIGHT_ORIENTATION);
+
+            // Additional orientation test if segment index is equal to 1 or 3.
+            if (segment_index != 2) {
+                const Point2D &test_point = ((segment_index == 1) ^ right_oriented) ?
+                                            site3.get_point1() : site3.get_point0();
+                if ((segment_index == 1 && 
+                    detail::orientation_test(test_point, site1.get_point0(), site2.get_point0()) !=
+                    detail::RIGHT_ORIENTATION) ||
+                    (segment_index == 3 &&
+                    detail::orientation_test(site1.get_point0(), site2.get_point0(), test_point) !=
+                    detail::RIGHT_ORIENTATION))
+                    return false;
+            } else {
+                if (detail::orientation_test(site1.get_point0(), site3.get_point0(),
+                    site2.get_point0()) != detail::RIGHT_ORIENTATION &&
+                    detail::orientation_test(site1.get_point0(), site3.get_point1(),
+                    site2.get_point0()) != detail::RIGHT_ORIENTATION)
+                    return false;
+            }
+
+            double line_a = site3.get_point1().y() - site3.get_point0().y();
+            double line_b = site3.get_point0().x() - site3.get_point1().x();
+            double vec_x = site2.y() - site1.y();
+            double vec_y = site1.x() - site2.x();
+            double teta = line_b * vec_y + line_a * vec_x;
+            double A = line_a * (site1.x() - site3.get_point1().x()) +
+                       line_b * (site1.y() - site3.get_point1().y());
+            double B = line_a * (site2.x() - site3.get_point1().x()) +
+                       line_b * (site2.y() - site3.get_point1().y());
+            double denom = line_b * vec_x - line_a * vec_y;
+            double det = 0.0;
+            if (orientation1 != detail::COLINEAR && orientation2 != detail::COLINEAR)
+                det = sqrt((teta * teta + denom * denom) * A * B);
+            double t;
+            
+            if (detail::orientation_test(static_cast<long long>(line_a),
+                                         static_cast<long long>(line_b),
+                                         static_cast<long long>(vec_x),
+                                         static_cast<long long>(vec_y)) == detail::COLINEAR) {
+                t = (teta * teta - 4.0 * A * B) / (4.0 * teta * (A + B));
+            } else {
+                if (segment_index == 2)
+                    det = -det;
+                t = (teta * (A + B) + 2.0 * det) / (2.0 * denom * denom);
+            }
+            double c_x = 0.5 * (site1.x() + site2.x()) + t * vec_x;
+            double c_y = 0.5 * (site1.y() + site2.y()) + t * vec_y;
+            double radius = sqrt((c_x-site2.x())*(c_x-site2.x()) +
+                                 (c_y-site2.y())*(c_y-site2.y()));
+            c_event = detail::make_circle_event<coordinate_type>(c_x, c_y, c_x + radius);
+            return true;
+        }
+
+        // Create circle event from one point site and two segment sites.
+        bool create_circle_event_pss(const site_event_type &site1,
+                                     const site_event_type &site2,
+                                     const site_event_type &site3,
+                                     int point_index,
+                                     circle_event_type &c_event) const {
+            // Check if bisectors intersect.
+            // Not implemented yet.
+            return false;
+        }
+
+        // Create circle event from three segment sites.
+        bool create_circle_event_sss(const site_event_type &site1,
+                                     const site_event_type &site2,
+                                     const site_event_type &site3,
+                                     circle_event_type &c_event) const {
+            // Check if bisectors intersecto.
+            // Not implemented yet.
+            return false;
+        }
+
+        // Create circle event from the given three points.
+        bool create_circle_event(const site_event_type &site1,
+                                 const site_event_type &site2,
+                                 const site_event_type &site3,
+                                 circle_event_type &c_event) const {
+            if (!site1.is_segment()) {
+                if (!site2.is_segment()) {
+                    if (!site3.is_segment()) {
+                        return create_circle_event_ppp(site1, site2, site3, c_event);
+                    } else {
+                        return create_circle_event_pps(site1, site2, site3, 3, c_event);
+                    }
+                } else {
+                    if (!site3.is_segment()) {
+                        return create_circle_event_pps(site1, site3, site2, 2, c_event);
+                    } else {
+                        return create_circle_event_pss(site1, site2, site3, 1, c_event);
+                    }
+                }
+            } else {
+                if (!site2.is_segment()) {
+                    if (!site3.is_segment()) {
+                        return create_circle_event_pps(site2, site3, site1, 1, c_event);
+                    } else {
+                        return create_circle_event_pss(site2, site1, site3, 2, c_event);
+                    }
+                } else {
+                    if (!site3.is_segment()) {
+                        return create_circle_event_pss(site3, site1, site2, 3, c_event);
+                    } else {
+                        return create_circle_event_sss(site1, site2, site3, c_event);
+                    }
+                }
+            }
+        }
+
         // Add new circle event to the event queue.
         void activate_circle_event(const site_event_type &site1,
                                    const site_event_type &site2,

Modified: sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_segment/segment_event_types_test.cpp
==============================================================================
--- sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_segment/segment_event_types_test.cpp	(original)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_segment/segment_event_types_test.cpp	2010-08-26 09:10:07 EDT (Thu, 26 Aug 2010)
@@ -64,6 +64,101 @@
     EVENT_TYPES_CHECK_COMPARISON(site1, site2, arr3);
 }
 
+
+BOOST_AUTO_TEST_CASE_TEMPLATE(site_event_test2, T, test_types) {
+    point_2d<T> point1 = make_point_2d<T>(static_cast<T>(0), static_cast<T>(2));
+    point_2d<T> point2 = make_point_2d<T>(static_cast<T>(0), static_cast<T>(0));
+    point_2d<T> point3 = make_point_2d<T>(static_cast<T>(0), static_cast<T>(-2));
+    point_2d<T> point4 = make_point_2d<T>(static_cast<T>(0), static_cast<T>(-1));
+    point_2d<T> point5 = make_point_2d<T>(static_cast<T>(1), static_cast<T>(1));
+    site_event<T> site1 = make_site_event<T>(point1, point2, 0);
+
+    BOOST_CHECK_EQUAL(point1 == site1.get_point1(), true);
+    BOOST_CHECK_EQUAL(point2 == site1.get_point0(), true);
+    BOOST_CHECK_EQUAL(site1.is_segment(), true);
+    BOOST_CHECK_EQUAL(site1.is_vertical(), true);
+
+    site_event<T> site2 = make_site_event<T>(point1, 0);
+    BOOST_CHECK_EQUAL(site2.is_segment(), false);
+    BOOST_CHECK_EQUAL(site2.is_vertical(), true);
+    
+    bool arr1_1[] = { true, false, true, false, false, true };
+    bool arr1_2[] = { false , true, false, true, false, true };
+    EVENT_TYPES_CHECK_COMPARISON(site1, site2, arr1_1);
+    EVENT_TYPES_CHECK_COMPARISON(site2, site1, arr1_2);
+
+    site2 = make_site_event<T>(point2, 0);
+    bool arr2_1[] = { false, true, false, true, false, true };
+    bool arr2_2[] = { true, false, true, false, false, true };
+    EVENT_TYPES_CHECK_COMPARISON(site1, site2, arr2_1);
+    EVENT_TYPES_CHECK_COMPARISON(site2, site1, arr2_2);
+
+    site2 = make_site_event<T>(point3, point4, 0);
+    bool arr3_1[] = { false, true, false, true, false, true };
+    bool arr3_2[] = { true, false, true, false, false, true };
+    EVENT_TYPES_CHECK_COMPARISON(site1, site2, arr3_1);
+    EVENT_TYPES_CHECK_COMPARISON(site2, site1, arr3_2);
+
+    site2 = make_site_event<T>(point3, point5, 0);
+    bool arr4_1[] = { true, false, true, false, false, true };
+    bool arr4_2[] = { false, true, false, true, false, true };
+    EVENT_TYPES_CHECK_COMPARISON(site1, site2, arr4_1);
+    EVENT_TYPES_CHECK_COMPARISON(site2, site1, arr4_2);
+
+    site2 = make_site_event<T>(point2, point5, 0);
+    bool arr5_1[] = { true, false, true, false, false, true };
+    bool arr5_2[] = { false, true, false, true, false, true };
+    EVENT_TYPES_CHECK_COMPARISON(site1, site2, arr5_1);
+    EVENT_TYPES_CHECK_COMPARISON(site2, site1, arr5_2);
+}
+
+BOOST_AUTO_TEST_CASE_TEMPLATE(site_event_test3, T, test_types) {
+    point_2d<T> point1 = make_point_2d<T>(static_cast<T>(10), static_cast<T>(10));
+    point_2d<T> point2 = make_point_2d<T>(static_cast<T>(0), static_cast<T>(0));
+    point_2d<T> point3 = make_point_2d<T>(static_cast<T>(0), static_cast<T>(1));
+    point_2d<T> point4 = make_point_2d<T>(static_cast<T>(0), static_cast<T>(10));
+    site_event<T> site1 = make_site_event<T>(point1, point2, 0);
+
+    BOOST_CHECK_EQUAL(point1 == site1.get_point1(), true);
+    BOOST_CHECK_EQUAL(point2 == site1.get_point0(), true);
+    BOOST_CHECK_EQUAL(site1.is_segment(), true);
+    BOOST_CHECK_EQUAL(site1.is_vertical(), false);
+
+    site_event<T> site2 = make_site_event<T>(point2, 0);
+    bool arr1_1[] = { false, true, false, true, false, true };
+    bool arr1_2[] = { true, false, true, false, false, true };
+    EVENT_TYPES_CHECK_COMPARISON(site1, site2, arr1_1);
+    EVENT_TYPES_CHECK_COMPARISON(site2, site1, arr1_2);
+
+    site2 = make_site_event<T>(static_cast<T>(0), static_cast<T>(-1), 0);
+    EVENT_TYPES_CHECK_COMPARISON(site1, site2, arr1_1);
+    EVENT_TYPES_CHECK_COMPARISON(site2, site1, arr1_2);
+
+    site2 = make_site_event<T>(static_cast<T>(0), static_cast<T>(1), 0);
+    EVENT_TYPES_CHECK_COMPARISON(site1, site2, arr1_1);
+    EVENT_TYPES_CHECK_COMPARISON(site2, site1, arr1_2);
+
+    site2 = make_site_event<T>(point3, point4, 0);
+    EVENT_TYPES_CHECK_COMPARISON(site1, site2, arr1_1);
+    EVENT_TYPES_CHECK_COMPARISON(site2, site1, arr1_2);
+
+    point3 = make_point_2d<T>(static_cast<T>(0), static_cast<T>(-10));
+    point4 = make_point_2d<T>(static_cast<T>(0), static_cast<T>(-1));
+    site2 = make_site_event<T>(point3, point4, 0);
+    EVENT_TYPES_CHECK_COMPARISON(site1, site2, arr1_1);
+    EVENT_TYPES_CHECK_COMPARISON(site2, site1, arr1_2);
+
+    point4 = make_point_2d<T>(static_cast<T>(10), static_cast<T>(9));
+    site2 = make_site_event<T>(point2, point4, 0);
+    EVENT_TYPES_CHECK_COMPARISON(site1, site2, arr1_1);
+    EVENT_TYPES_CHECK_COMPARISON(site2, site1, arr1_2);
+
+    point4 = make_point_2d<T>(static_cast<T>(9), static_cast<T>(10));
+    site2 = make_site_event<T>(point2, point4, 0);
+    EVENT_TYPES_CHECK_COMPARISON(site1, site2, arr1_2);
+    EVENT_TYPES_CHECK_COMPARISON(site2, site1, arr1_1);
+}
+
 BOOST_AUTO_TEST_CASE_TEMPLATE(circle_event_test1, T, test_types) {
     circle_event<T> circle1 = make_circle_event<T>(static_cast<T>(1),
                                                    static_cast<T>(2),
@@ -116,33 +211,4 @@
 
     site = make_site_event<T>(static_cast<T>(4), static_cast<T>(2), 0);
     BOOST_CHECK_EQUAL(circle.compare(site), -1);
-}
-
-BOOST_AUTO_TEST_CASE_TEMPLATE(segment_site_event_test1, T, test_types) {
-    point_2d<T> point1 = make_point_2d<T>(static_cast<T>(0), static_cast<T>(2));
-    point_2d<T> point2 = make_point_2d<T>(static_cast<T>(0), static_cast<T>(0));
-    site_event<T> segment = make_site_event<T>(point1, point2, 0);
-
-    BOOST_CHECK_EQUAL(point1 == segment.get_point1(), true);
-    BOOST_CHECK_EQUAL(point2 == segment.get_point0(), true);
-    BOOST_CHECK_EQUAL(segment.is_segment(), true);
-    BOOST_CHECK_EQUAL(segment.is_vertical(), true);
-
-    site_event<T> point = make_site_event<T>(point1, 0);
-    BOOST_CHECK_EQUAL(point.is_segment(), false);
-    BOOST_CHECK_EQUAL(point.is_vertical(), true);
-    
-    //bool arr1[] = {
-
-}
-
-BOOST_AUTO_TEST_CASE_TEMPLATE(segment_site_event_test2, T, test_types) {
-    point_2d<T> point1 = make_point_2d<T>(static_cast<T>(1), static_cast<T>(1));
-    point_2d<T> point2 = make_point_2d<T>(static_cast<T>(0), static_cast<T>(0));
-    site_event<T> segment = make_site_event<T>(point1, point2, 0);
-
-    BOOST_CHECK_EQUAL(point1 == segment.get_point1(), true);
-    BOOST_CHECK_EQUAL(point2 == segment.get_point0(), true);
-    BOOST_CHECK_EQUAL(segment.is_segment(), true);
-    BOOST_CHECK_EQUAL(segment.is_vertical(), false);
-}
+}
\ No newline at end of file

Modified: sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_segment/segment_node_comparer_test.cpp
==============================================================================
--- sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_segment/segment_node_comparer_test.cpp	(original)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_segment/segment_node_comparer_test.cpp	2010-08-26 09:10:07 EDT (Thu, 26 Aug 2010)
@@ -16,7 +16,6 @@
 #include <boost/test/test_case_template.hpp>
 
 BOOST_AUTO_TEST_CASE_TEMPLATE(node_comparer_test_pp1, T, test_types) {
-    typedef point_2d<T> Point2D;
     typedef site_event<T> site_event_type; 
     typedef beach_line_node<T> bline_node;
     typedef typename std::map< bline_node, int, 
@@ -43,7 +42,6 @@
 }
 
 BOOST_AUTO_TEST_CASE_TEMPLATE(node_comparer_test_pp2, T, test_types) {
-    typedef point_2d<T> Point2D;
     typedef site_event<T> site_event_type; 
     typedef beach_line_node<T> bline_node;
     typedef typename std::map< bline_node, int, 
@@ -61,8 +59,8 @@
 
     bline_node new_node1(site1, site3);
     bline_node new_node2(site3, site1);
-    test_beach_line.insert(std::pair<bline_node, int>(initial_node1, 2));
-    test_beach_line.insert(std::pair<bline_node, int>(initial_node2, 3));
+    test_beach_line.insert(std::pair<bline_node, int>(new_node1, 2));
+    test_beach_line.insert(std::pair<bline_node, int>(new_node2, 3));
 
     int cur_value = 0;
     for (bline_it it = test_beach_line.begin();
@@ -250,3 +248,11 @@
     BOOST_CHECK_EQUAL(node_comparer_test(new_node3, initial_node), false);
     BOOST_CHECK_EQUAL(node_comparer_test(new_node4, initial_node), false);
 }
+
+BOOST_AUTO_TEST_CASE_TEMPLATE(node_comparer_test_ps1, T, test_types) {
+    // TODO(asydorchuk): add more tests there.   
+}
+
+BOOST_AUTO_TEST_CASE_TEMPLATE(node_comparer_test_ss1, T, test_types) {
+    // TODO(asydorchuk): add more tests there.
+}

Modified: sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_segment/segment_voronoi_builder_test.cpp
==============================================================================
--- sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_segment/segment_voronoi_builder_test.cpp	(original)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_segment/segment_voronoi_builder_test.cpp	2010-08-26 09:10:07 EDT (Thu, 26 Aug 2010)
@@ -623,3 +623,89 @@
         test_beach_line.reset();
     }
 }
+
+BOOST_AUTO_TEST_CASE_TEMPLATE(segment_sites_test1, T, test_types) {
+    typedef T coordinate_type;
+    voronoi_builder<coordinate_type> test_voronoi_builder;
+    std::vector< typename voronoi_builder<coordinate_type>::Segment2D > segm_vec;
+    point_2d<T> point1 = make_point_2d<T>(0, 0);
+    point_2d<T> point2 = make_point_2d<T>(1, 1);
+    segm_vec.push_back(std::make_pair< point_2d<T>, point_2d<T> >(point1, point2));
+    test_voronoi_builder.init(segm_vec);
+    test_voronoi_builder.run_sweepline();
+}
+
+
+BOOST_AUTO_TEST_CASE_TEMPLATE(segment_sites_test2, T, test_types) {
+    typedef T coordinate_type;
+    voronoi_builder<coordinate_type> test_voronoi_builder;
+    std::vector< point_2d<T> > point_vec;
+    std::vector< typename voronoi_builder<coordinate_type>::Segment2D > segm_vec;
+    point_2d<T> point1 = make_point_2d<T>(0, 0);
+    point_2d<T> point2 = make_point_2d<T>(4, 4);
+    point_2d<T> point3 = make_point_2d<T>(3, 1);
+    point_2d<T> point4 = make_point_2d<T>(1, 3);
+    segm_vec.push_back(std::make_pair< point_2d<T>, point_2d<T> >(point1, point2));
+    point_vec.push_back(point3);
+    point_vec.push_back(point4);
+    test_voronoi_builder.init(point_vec, segm_vec);
+    test_voronoi_builder.run_sweepline();
+
+    // TODO(asydorchuk): Add output checks there.
+}
+
+BOOST_AUTO_TEST_CASE_TEMPLATE(segment_sites_test3, T, test_types) {
+    typedef T coordinate_type;
+    voronoi_builder<coordinate_type> test_voronoi_builder;
+    std::vector< point_2d<T> > point_vec;
+    std::vector< typename voronoi_builder<coordinate_type>::Segment2D > segm_vec;
+    point_2d<T> point1 = make_point_2d<T>(4, 0);
+    point_2d<T> point2 = make_point_2d<T>(0, 4);
+    point_2d<T> point3 = make_point_2d<T>(3, 3);
+    point_2d<T> point4 = make_point_2d<T>(1, 1);
+    segm_vec.push_back(std::make_pair< point_2d<T>, point_2d<T> >(point1, point2));
+    point_vec.push_back(point3);
+    point_vec.push_back(point4);
+    test_voronoi_builder.init(point_vec, segm_vec);
+    test_voronoi_builder.run_sweepline();
+
+    // TODO(asydorchuk): Add output checks there.
+}
+
+BOOST_AUTO_TEST_CASE_TEMPLATE(segment_sites_test4, T, test_types) {
+    typedef T coordinate_type;
+    voronoi_builder<coordinate_type> test_voronoi_builder;
+    std::vector< point_2d<T> > point_vec;
+    std::vector< typename voronoi_builder<coordinate_type>::Segment2D > segm_vec;
+    point_2d<T> point1 = make_point_2d<T>(4, 0);
+    point_2d<T> point2 = make_point_2d<T>(0, 4);
+    point_2d<T> point3 = make_point_2d<T>(3, 2);
+    point_2d<T> point4 = make_point_2d<T>(2, 3);
+    segm_vec.push_back(std::make_pair< point_2d<T>, point_2d<T> >(point1, point2));
+    point_vec.push_back(point3);
+    point_vec.push_back(point4);
+    test_voronoi_builder.init(point_vec, segm_vec);
+    test_voronoi_builder.run_sweepline();
+
+    // TODO(asydorchuk): Add output checks there.
+}
+
+BOOST_AUTO_TEST_CASE_TEMPLATE(segment_site_test5, T, test_types) {
+    typedef T coordinate_type;
+    voronoi_builder<coordinate_type> test_voronoi_builder;
+    std::vector< point_2d<T> > point_vec;
+    std::vector< typename voronoi_builder<coordinate_type>::Segment2D > segm_vec;
+    point_2d<T> point1 = make_point_2d<T>(0, 0);
+    point_2d<T> point2 = make_point_2d<T>(0, 8);
+    point_2d<T> point3 = make_point_2d<T>(-2, -2);
+    point_2d<T> point4 = make_point_2d<T>(-2, 4);
+    point_2d<T> point5 = make_point_2d<T>(-2, 10);
+    segm_vec.push_back(std::make_pair< point_2d<T>, point_2d<T> >(point1, point2));
+    point_vec.push_back(point3);
+    point_vec.push_back(point4);
+    point_vec.push_back(point5);
+    test_voronoi_builder.init(point_vec, segm_vec);
+    test_voronoi_builder.run_sweepline();
+
+    // TODO(asydorchuk): Add output checks there.
+}
\ No newline at end of file