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

Subject: [Boost-commit] svn:boost r66711 - in sandbox/SOC/2010/sweepline: boost/sweepline boost/sweepline/detail libs/sweepline/example libs/sweepline/example/input_data libs/sweepline/example/output_data libs/sweepline/test
From: sydorchuk.andriy_at_[hidden]
Date: 2010-11-24 10:39:09

Author: asydorchuk
Date: 2010-11-24 10:39:07 EST (Wed, 24 Nov 2010)
New Revision: 66711
URL: http://svn.boost.org/trac/boost/changeset/66711

Log:
Added random segment tests.
Added a few more examples.
Updated algorithm to pass random tests.
Updated predicates.
Added:
   sandbox/SOC/2010/sweepline/libs/sweepline/example/input_data/example_046.txt   (contents, props changed)
   sandbox/SOC/2010/sweepline/libs/sweepline/example/input_data/example_047.txt   (contents, props changed)
   sandbox/SOC/2010/sweepline/libs/sweepline/example/input_data/example_048.txt   (contents, props changed)
   sandbox/SOC/2010/sweepline/libs/sweepline/example/input_data/example_049.txt   (contents, props changed)
   sandbox/SOC/2010/sweepline/libs/sweepline/example/input_data/example_050.txt   (contents, props changed)
   sandbox/SOC/2010/sweepline/libs/sweepline/example/output_data/example_046.png   (contents, props changed)
   sandbox/SOC/2010/sweepline/libs/sweepline/example/output_data/example_047.png   (contents, props changed)
   sandbox/SOC/2010/sweepline/libs/sweepline/example/output_data/example_048.png   (contents, props changed)
   sandbox/SOC/2010/sweepline/libs/sweepline/example/output_data/example_049.png   (contents, props changed)
   sandbox/SOC/2010/sweepline/libs/sweepline/example/output_data/example_050.png   (contents, props changed)
Text files modified: 
   sandbox/SOC/2010/sweepline/boost/sweepline/detail/voronoi_formation.hpp  |    67 +---                                    
   sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_builder.hpp           |    10                                         
   sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_output.hpp            |    14                                         
   sandbox/SOC/2010/sweepline/libs/sweepline/example/voronoi_visualizer.cpp |     4                                         
   sandbox/SOC/2010/sweepline/libs/sweepline/test/benchmark_test.cpp        |     2                                         
   sandbox/SOC/2010/sweepline/libs/sweepline/test/output_verification.hpp   |    65 ++++                                    
   sandbox/SOC/2010/sweepline/libs/sweepline/test/predicates_test.cpp       |    13                                         
   sandbox/SOC/2010/sweepline/libs/sweepline/test/sweepline_test.cpp        |   547 +++++++++++++++++---------------------- 
   8 files changed, 350 insertions(+), 372 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-11-24 10:39:07 EST (Wed, 24 Nov 2010)
@@ -1044,29 +1044,27 @@
                                site_event<T> right_site,
                                point_2d<T> new_point) {
         if (left_site.get_site_index() == right_site.get_site_index()) {
-            return orientation_test(left_site.get_point0(), left_site.get_point1(),
-                new_point) == LEFT_ORIENTATION;
+            return orientation_test(left_site.get_point0(), left_site.get_point1(), new_point) ==
+                   LEFT_ORIENTATION;
         }
 
-        const point_2d<T> segment1_start = left_site.get_point1();
-        const point_2d<T> segment1_end = left_site.get_point0();
-        const point_2d<T> segment2_start = right_site.get_point1();
-        const point_2d<T> segment2_end = right_site.get_point0();
+        if (left_site.get_point1() == new_point && right_site.get_point1() == new_point)
+            return false;
+
+        const point_2d<T> &segment1_start = left_site.get_point1();
+        const point_2d<T> &segment1_end = left_site.get_point0();
+        const point_2d<T> &segment2_start = right_site.get_point1();
+        const point_2d<T> &segment2_end = right_site.get_point0();
         double intersection_x1 = 0.0;
         double intersection_x2 = 0.0;
         
-        double a1 = static_cast<double>(segment1_end.x()) -
-                    static_cast<double>(segment1_start.x());
+        double a1 = segment1_end.x() - segment1_start.x();
         if (a1 == 0.0) {
             // Avoid cancellation.
-            intersection_x2 += (static_cast<double>(new_point.x()) -
-                                static_cast<double>(segment1_end.x())) * 0.5;
+            intersection_x2 += (new_point.x() - segment1_end.x()) * 0.5;
         } else {
-            double b1 = static_cast<double>(segment1_end.y()) -
-                        static_cast<double>(segment1_start.y());
-            double c1 = b1 * (static_cast<double>(new_point.x()) -
-                              static_cast<double>(segment1_start.x())) +
-                        a1 * segment1_start.y();
+            double b1 = segment1_end.y() - segment1_start.y();
+            double c1 = b1 * (new_point.x() - segment1_start.x()) + a1 * segment1_start.y();
             double mul1 = sqrt(a1 * a1 + b1 * b1);
             if (left_site.is_inverse()) {
                 if (b1 >= 0.0) {
@@ -1081,23 +1079,17 @@
                     mul1 = 1.0 / (b1 - mul1);
                 }
             }
-            avoid_cancellation(a1 * mul1 * static_cast<double>(new_point.y()),
-                                             intersection_x1, intersection_x2);
+            avoid_cancellation(a1 * mul1 * new_point.y(), intersection_x1, intersection_x2);
             avoid_cancellation(-c1 * mul1, intersection_x1, intersection_x2);
         }
 
-        double a2 = static_cast<double>(segment2_end.x()) -
-                    static_cast<double>(segment2_start.x());
+        double a2 = segment2_end.x() - segment2_start.x();
         if (a2 == 0.0) {
             // Avoid cancellation.
-            intersection_x1 += (static_cast<double>(new_point.x()) - 
-                                static_cast<double>(segment2_end.x())) * 0.5;
+            intersection_x1 += (new_point.x() - segment2_end.x()) * 0.5;
         } else {
-            double b2 = static_cast<double>(segment2_end.y()) -
-                        static_cast<double>(segment2_start.y());
-            double c2 = b2 * (static_cast<double>(new_point.x()) -
-                              static_cast<double>(segment2_start.x())) +
-                        a2 * segment2_start.y();
+            double b2 = segment2_end.y() - segment2_start.y();
+            double c2 = b2 * (new_point.x() - segment2_start.x()) + a2 * segment2_start.y();
             double mul2 = sqrt(a2 * a2 + b2 * b2);
             if (right_site.is_inverse()) {
                 if (b2 >= 0.0) {
@@ -1112,8 +1104,7 @@
                     mul2 = 1.0 / (b2 - mul2);
                 }
             }
-            avoid_cancellation(a2 * static_cast<double>(new_point.y()) * mul2,
-                                             intersection_x2, intersection_x1);
+            avoid_cancellation(a2 * new_point.y() * mul2, intersection_x2, intersection_x1);
             avoid_cancellation(-c2 * mul2, intersection_x2, intersection_x1);
         }
 
@@ -1252,20 +1243,13 @@
         const point_2d<T> &segm_start2 = site3.get_point0(true);
         const point_2d<T> &segm_end2 = site3.get_point1(true);
 
-        if (point_index != 2) {
-            if (orientation_test(segm_start1, segm_start2, site) == LEFT_ORIENTATION &&
-                orientation_test(segm_end1, segm_end2, site) == LEFT_ORIENTATION &&
-                orientation_test(segm_start1, segm_end2, site) == LEFT_ORIENTATION &&
-                orientation_test(segm_end1, segm_start2, site) == LEFT_ORIENTATION) {
+        if (point_index == 2) {
+            if (!site2.is_inverse() && site3.is_inverse())
                 return false;
-            }
-        } else {
-            if ((orientation_test(segm_end1, segm_start1, segm_start2) != RIGHT_ORIENTATION &&
-                 orientation_test(segm_end1, segm_start1, segm_end2) != RIGHT_ORIENTATION) ||
-                (orientation_test(segm_start2, segm_end2, segm_start1) != RIGHT_ORIENTATION &&
-                 orientation_test(segm_start2, segm_end2, segm_end1) != RIGHT_ORIENTATION)) {
+            if (site2.is_inverse() == site3.is_inverse() &&
+                //orientation_test(orientation) != RIGHT_ORIENTATION)
+                orientation_test(segm_end1, site1.get_point0(), segm_end2) != RIGHT_ORIENTATION)
                 return false;
-            }
         }
 
         double a1 = segm_end1.x() - segm_start1.x();
@@ -1505,8 +1489,7 @@
                     return true;
                 return less_predicate(left_site_.get_point0(), right_site_.get_point0(), new_site);
             } else {
-                return left_site_.y() + right_site_.y() <
-                       static_cast<coordinate_type>(2.0) * new_site.y();
+                return left_site_.y() + right_site_.y() < 2.0 * new_site.y();
             }
         }
 

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-11-24 10:39:07 EST (Wed, 24 Nov 2010)
@@ -302,13 +302,11 @@
             // (B, C) bisector and change (A, B) bisector to the (A, C). That's
             // why we use const_cast there and take all the responsibility that
             // map data structure keeps correct ordering.
-            const_cast<Key &>(it_first->first).set_right_site(site3);
-            if (site1.is_segment() && site1.get_point0(true) == site3.get_point0(true)) {
-                const_cast<Key &>(it_first->first).set_left_site_inverse();
-            }
-            if (site3.is_segment() && site3.get_point1(true) == site1.get_point0(true)) {
-                const_cast<Key &>(it_first->first).set_right_site_inverse();
+            if (!site1.is_segment() && site3.is_segment() &&
+                site3.get_point1(true) == site1.get_point0()) {
+                site3.set_inverse();
             }
+            const_cast<Key &>(it_first->first).set_right_site(site3);
             it_first->second.set_edge(output_.insert_new_edge(site1, site3, circle_event,
                                                               bisector1, bisector2));
             beach_line_.erase(it_last);

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-11-24 10:39:07 EST (Wed, 24 Nov 2010)
@@ -328,7 +328,7 @@
             num_incident_edges(0),
             site(new_site) {}
 
-        bool is_segment() const {
+        bool contains_segment() const {
             return site.is_segment();
         }
 
@@ -399,7 +399,7 @@
             const voronoi_cell_type *cell1 = cell;
             const voronoi_cell_type *cell2 = twin->cell;
             std::vector<Point2D> edge_points;
-            if (!(cell1->is_segment() ^ cell2->is_segment())) {
+            if (!(cell1->contains_segment() ^ cell2->contains_segment())) {
                 if (start_point != NULL && end_point != NULL) {
                     edge_points.push_back(start_point->vertex);
                     edge_points.push_back(end_point->vertex);
@@ -417,20 +417,20 @@
                         edge_points[0] = start_point->vertex;
                 }
             } else {
-                const Point2D &point1 = (cell1->is_segment()) ?
+                const Point2D &point1 = (cell1->contains_segment()) ?
                     cell2->get_point0() : cell1->get_point0();
-                const Point2D &point2 = (cell1->is_segment()) ?
+                const Point2D &point2 = (cell1->contains_segment()) ?
                     cell1->get_point0() : cell2->get_point0();
-                const Point2D &point3 = (cell1->is_segment()) ?
+                const Point2D &point3 = (cell1->contains_segment()) ?
                     cell1->get_point1() : cell2->get_point1();
                 if (start_point != NULL && end_point != NULL) {
                     edge_points.push_back(start_point->vertex);
                     edge_points.push_back(end_point->vertex);
                     Helper<T>::fill_intermediate_points(point1, point2, point3, edge_points);
                 } else {
-                    coordinate_type dir_x = (cell1->is_segment() ^ (point1 == point3)) ?
+                    coordinate_type dir_x = (cell1->contains_segment() ^ (point1 == point3)) ?
                         point3.y() - point2.y() : point2.y() - point3.y();
-                    coordinate_type dir_y = (cell1->is_segment() ^ (point1 == point3)) ?
+                    coordinate_type dir_y = (cell1->contains_segment() ^ (point1 == point3)) ?
                         point2.x() - point3.x() : point3.x() - point2.x();
                     Point2D direction(dir_x, dir_y);
                     Helper<T>::find_intersections(point1, direction, Helper<T>::LINE,

Added: sandbox/SOC/2010/sweepline/libs/sweepline/example/input_data/example_046.txt
==============================================================================
--- (empty file)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/example/input_data/example_046.txt	2010-11-24 10:39:07 EST (Wed, 24 Nov 2010)
@@ -0,0 +1,8 @@
+0
+6
+0 0 0 10
+-5 0 -1 0
+-6 2 -1 2
+-4 5 -2 5
+-8 8 -1 8
+-7 -2 -7 7
\ No newline at end of file

Added: sandbox/SOC/2010/sweepline/libs/sweepline/example/input_data/example_047.txt
==============================================================================
--- (empty file)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/example/input_data/example_047.txt	2010-11-24 10:39:07 EST (Wed, 24 Nov 2010)
@@ -0,0 +1,56 @@
+0
+54
+-12 4 -12 -4
+-12 -4 -8 -4
+-8 -4 -8 0
+-8 0 -9 0
+-9 0 -9 4
+-9 4 -12 4
+-11 1 -11 3
+-11 3 -10 3
+-10 3 -10 1
+-10 1 -11 1
+-11 -1 -9 -1
+-9 -1 -9 -3
+-9 -3 -11 -3
+-11 -3 -11 -1
+-7 4 -7 -4
+-7 -4 -3 -4
+-3 -4 -3 4
+-3 4 -7 4
+-6 3 -6 -3
+-6 -3 -4 -3
+-4 -3 -4 3
+-4 3 -6 3
+-2 4 -2 -4
+-2 -4 2 -4
+2 -4 2 4
+2 4 -2 4
+-1 3 -1 -3
+-1 -3 1 -3
+1 -3 1 3
+1 3 -1 3
+3 4 3 0
+3 0 6 0
+6 0 6 -3
+6 -3 4 -3
+4 -3 4 -2
+4 -2 3 -2
+3 -2 3 -4
+3 -4 7 -4
+7 -4 7 1
+7 1 4 1
+4 1 4 3
+4 3 6 3
+6 3 6 2
+6 2 7 2
+7 2 7 4
+7 4 3 4
+8 4 8 2
+8 2 9 2
+9 2 9 -4
+9 -4 11 -4
+11 -4 11 2
+11 2 12 2
+12 2 12 4
+12 4 8 4

Added: sandbox/SOC/2010/sweepline/libs/sweepline/example/input_data/example_048.txt
==============================================================================
--- (empty file)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/example/input_data/example_048.txt	2010-11-24 10:39:07 EST (Wed, 24 Nov 2010)
@@ -0,0 +1,5 @@
+0
+3
+-6 -1 -5 3
+-1 0 4 -1
+3 0 4 1
\ No newline at end of file

Added: sandbox/SOC/2010/sweepline/libs/sweepline/example/input_data/example_049.txt
==============================================================================
--- (empty file)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/example/input_data/example_049.txt	2010-11-24 10:39:07 EST (Wed, 24 Nov 2010)
@@ -0,0 +1,5 @@
+0
+3
+-5 -2 -4 2
+-5 3 -2 2
+-5 5 -2 2
\ No newline at end of file

Added: sandbox/SOC/2010/sweepline/libs/sweepline/example/input_data/example_050.txt
==============================================================================
--- (empty file)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/example/input_data/example_050.txt	2010-11-24 10:39:07 EST (Wed, 24 Nov 2010)
@@ -0,0 +1,5 @@
+0
+3
+-9 -8 -4 -3
+-8 -3 -4 -3
+-2 7 -1 3
\ No newline at end of file

Added: sandbox/SOC/2010/sweepline/libs/sweepline/example/output_data/example_046.png
==============================================================================
Binary file. No diff available.

Added: sandbox/SOC/2010/sweepline/libs/sweepline/example/output_data/example_047.png
==============================================================================
Binary file. No diff available.

Added: sandbox/SOC/2010/sweepline/libs/sweepline/example/output_data/example_048.png
==============================================================================
Binary file. No diff available.

Added: sandbox/SOC/2010/sweepline/libs/sweepline/example/output_data/example_049.png
==============================================================================
Binary file. No diff available.

Added: sandbox/SOC/2010/sweepline/libs/sweepline/example/output_data/example_050.png
==============================================================================
Binary file. No diff available.

Modified: sandbox/SOC/2010/sweepline/libs/sweepline/example/voronoi_visualizer.cpp
==============================================================================
--- sandbox/SOC/2010/sweepline/libs/sweepline/example/voronoi_visualizer.cpp	(original)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/example/voronoi_visualizer.cpp	2010-11-24 10:39:07 EST (Wed, 24 Nov 2010)
@@ -75,7 +75,7 @@
             glPointSize(9);
             glBegin(GL_POINTS);
             for (it = cells.begin(); it != cells.end(); it++) {
-                if (!it->is_segment())
+                if (!it->contains_segment())
                     glVertex2f(it->get_point0().x(), it->get_point0().y());
             }
             glEnd();
@@ -83,7 +83,7 @@
             glLineWidth(2.7f);
             glBegin(GL_LINES);
             for (it = cells.begin(); it != cells.end(); it++) {
-                if (it->is_segment()) {
+                if (it->contains_segment()) {
                     glVertex2f(it->get_point0().x(), it->get_point0().y());
                     glVertex2f(it->get_point1().x(), it->get_point1().y());
                 }

Modified: sandbox/SOC/2010/sweepline/libs/sweepline/test/benchmark_test.cpp
==============================================================================
--- sandbox/SOC/2010/sweepline/libs/sweepline/test/benchmark_test.cpp	(original)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/test/benchmark_test.cpp	2010-11-24 10:39:07 EST (Wed, 24 Nov 2010)
@@ -36,7 +36,7 @@
 #ifdef _DEBUG
     int max_points = 1000;
 #else
-    int max_points = 100000;
+    int max_points = 1000000;
 #endif
 
     for (int num_points = 10; num_points <= max_points; num_points *= 10) {

Modified: sandbox/SOC/2010/sweepline/libs/sweepline/test/output_verification.hpp
==============================================================================
--- sandbox/SOC/2010/sweepline/libs/sweepline/test/output_verification.hpp	(original)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/test/output_verification.hpp	2010-11-24 10:39:07 EST (Wed, 24 Nov 2010)
@@ -20,9 +20,7 @@
 };
 
 template <typename Point2D>
-kOrientation get_orientation(const Point2D &point1,
-                     const Point2D &point2,
-                     const Point2D &point3) {
+kOrientation get_orientation(const Point2D &point1, const Point2D &point2, const Point2D &point3) {
     typename Point2D::coordinate_type a = (point2.x() - point1.x()) * (point3.y() - point2.y());
     typename Point2D::coordinate_type b = (point2.y() - point1.y()) * (point3.x() - point2.x());
     if (a == b)
@@ -113,6 +111,8 @@
     typename Output::voronoi_edge_const_iterator_type edge_it;
     for (edge_it = output.edge_records.begin();
          edge_it != output.edge_records.end(); edge_it++) {
+        if (edge_it->cell->contains_segment() && edge_it->twin->cell->contains_segment())
+            continue;
         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;
@@ -155,9 +155,9 @@
 
                     // Intersection check.
                     if (get_orientation(point1, point2, point3) *
-                        get_orientation(point1, point2, point4) == -1 &&
+                        get_orientation(point1, point2, point4) == RIGHT_ORIENTATION &&
                         get_orientation(point3, point4, point1) *
-                        get_orientation(point3, point4, point2) == -1)
+                        get_orientation(point3, point4, point2) == RIGHT_ORIENTATION)
                         return false;
                 }
             }
@@ -166,6 +166,61 @@
     return true;
 }
 
+template<typename P>
+struct segm_comparison {
+    bool operator()(const std::pair<P, P>& segm1, const std::pair<P, P>& segm2) const {
+        return segm1.first.x() < segm2.first.x();
+    }
+};
+
+template<typename P>
+bool intersect(const std::pair<P, P> &segm1, const std::pair<P, P> &segm2) {
+    if ((std::max)(segm1.first.y(), segm1.second.y()) <
+        (std::min)(segm2.first.y(), segm2.second.y()) ||
+        (std::max)(segm2.first.y(), segm2.second.y()) <
+        (std::min)(segm1.first.y(), segm1.second.y()))
+        return false;
+    if (segm1.first == segm2.first)
+        return detail::orientation_test(segm1.first, segm1.second, segm2.second)
+               == detail::COLINEAR;
+    if (segm1.second == segm2.second)
+        return detail::orientation_test(segm1.first, segm1.second, segm2.first)
+               == detail::COLINEAR;
+    if ((get_orientation(segm1.first, segm1.second, segm2.first) *
+         get_orientation(segm1.first, segm1.second, segm2.second) != LEFT_ORIENTATION) &&
+        (get_orientation(segm2.first, segm2.second, segm1.first) *
+         get_orientation(segm2.first, segm2.second, segm1.second) != LEFT_ORIENTATION))
+        return true;
+    return false;
+}
+
+template<typename P>
+void remove_intersections(std::vector< std::pair<P, P> >& segm_vec) {
+    for (int i = 0; i < static_cast<int>(segm_vec.size()); i++) {
+        if (segm_vec[i].first > segm_vec[i].second) {
+            (std::swap(segm_vec[i].first, segm_vec[i].second));
+        }
+    }
+    sort(segm_vec.begin(), segm_vec.end());
+    std::vector< std::pair<P, P> > dest_vec;
+    std::vector< std::pair<P, P> >::iterator it, b_it, l_bound;
+    for (it = segm_vec.begin(); it != segm_vec.end(); it++) {
+        std::pair<P, P> bound = std::make_pair(it->second, it->second);
+        l_bound = std::upper_bound(segm_vec.begin(), segm_vec.end(), bound, segm_comparison<P>());
+        bool add = true;
+        for (b_it = it + 1; b_it != l_bound; b_it++) {
+            if (intersect(*it, *b_it)) {
+                add = false;
+                break;
+            }
+        }
+        if (add) {
+            dest_vec.push_back(*it);
+        }
+    }
+    segm_vec.swap(dest_vec);
+}
+
 enum kVerification {
     HALF_EDGE_ORIENTATION = 1,
     CELL_CONVEXITY = 2,

Modified: sandbox/SOC/2010/sweepline/libs/sweepline/test/predicates_test.cpp
==============================================================================
--- sandbox/SOC/2010/sweepline/libs/sweepline/test/predicates_test.cpp	(original)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/test/predicates_test.cpp	2010-11-24 10:39:07 EST (Wed, 24 Nov 2010)
@@ -283,3 +283,16 @@
     CHECK_LESS_PREDICATE_SS(segm_site3, segm_site1_2, new_site3, false);
     CHECK_LESS_PREDICATE_SS(segm_site3, segm_site1_2, new_site4, true);
 }
+
+BOOST_AUTO_TEST_CASE_TEMPLATE(less_predicate_segment_segment_test3, T, test_types) {
+    typedef typename detail::site_event<T> site_event_type;
+
+    point_2d<T> segm_start1 = make_point_2d<T>(static_cast<T>(-5), static_cast<T>(3));
+    point_2d<T> segm_start2 = make_point_2d<T>(static_cast<T>(-5), static_cast<T>(5));
+    point_2d<T> segm_end = make_point_2d<T>(static_cast<T>(-2), static_cast<T>(2));
+    site_event_type segm_site1(segm_start1, segm_end, 0);
+    segm_site1.set_inverse();
+    site_event_type segm_site2(segm_start2, segm_end, 1);
+    point_2d<T> point(-4, 2);
+    CHECK_LESS_PREDICATE_SS(segm_site1, segm_site2, point, false);
+}

Modified: sandbox/SOC/2010/sweepline/libs/sweepline/test/sweepline_test.cpp
==============================================================================
--- sandbox/SOC/2010/sweepline/libs/sweepline/test/sweepline_test.cpp	(original)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/test/sweepline_test.cpp	2010-11-24 10:39:07 EST (Wed, 24 Nov 2010)
@@ -19,8 +19,8 @@
 #include <boost/test/test_case_template.hpp>
 
 #define CHECK_EQUAL_POINTS(p1, p2) \
-        BOOST_CHECK_EQUAL(p1.x() == static_cast<coordinate_type>(p2.x()) && \
-                          p1.y() == static_cast<coordinate_type>(p2.y()), true)
+        BOOST_CHECK_EQUAL(p1.x() == static_cast<T>(p2.x()) && \
+                          p1.y() == static_cast<T>(p2.y()), true)
 
 #define VERIFY_VORONOI_OUTPUT(output, mask) BOOST_CHECK_EQUAL(verify_output(output, mask), true)
 
@@ -395,308 +395,112 @@
     BOOST_CHECK_EQUAL(edge2_1->rot_next == edge1_1, true);
 }
 
-// Sites: {(x, y) | x = 0 .. 3, y = 0 .. 3}.
-BOOST_AUTO_TEST_CASE_TEMPLATE(grid_test1, T, test_types) {
-    typedef T coordinate_type;
-    voronoi_builder<coordinate_type> test_beach_line;
-    std::vector< point_2d<coordinate_type> > points;
-    for (int i = 0; i < 3; i++)
-        for (int j = 0; j < 3; j++)
-            points.push_back(make_point_2d<coordinate_type>(
-                static_cast<coordinate_type>(i), static_cast<coordinate_type>(j)));
-    
-    test_beach_line.init(points);
-    test_beach_line.run_sweepline();
-    voronoi_output_clipped<coordinate_type> test_output;
-    test_beach_line.clip(test_output);
-    VERIFY_VORONOI_OUTPUT(test_output, COMPLETE_VERIFICATION);
-
-    BOOST_CHECK_EQUAL(test_output.num_cell_records, 9);
-    BOOST_CHECK_EQUAL(test_output.num_vertex_records, 4);
-    BOOST_CHECK_EQUAL(test_output.num_edge_records, 12);
-}
-
-// Sites: {(x, y) | x = 0 .. 9, y = 0 .. 9}.
-BOOST_AUTO_TEST_CASE_TEMPLATE(grid_test2, T, test_types) {
-    typedef T coordinate_type;
-    voronoi_builder<coordinate_type> test_beach_line;
-    std::vector< point_2d<coordinate_type> > points;
-    for (int i = 0; i < 10; i++)
-        for (int j = 0; j < 10; j++)
-            points.push_back(make_point_2d<coordinate_type>(
-                static_cast<coordinate_type>(i), static_cast<coordinate_type>(j)));
-    
-    test_beach_line.init(points);
-    test_beach_line.run_sweepline();
-    voronoi_output_clipped<coordinate_type> test_output;
-    test_beach_line.clip(test_output);
-    VERIFY_VORONOI_OUTPUT(test_output, COMPLETE_VERIFICATION);
-
-    BOOST_CHECK_EQUAL(test_output.num_cell_records, 100);
-    BOOST_CHECK_EQUAL(test_output.num_vertex_records, 81);
-    BOOST_CHECK_EQUAL(test_output.num_edge_records, 180);
-}
-
-// Sites: {(x, y) | x = 0 .. 33, y = 0 .. 33}.
-BOOST_AUTO_TEST_CASE_TEMPLATE(grid_test3, T, test_types) {
-    typedef T coordinate_type;
-    voronoi_builder<coordinate_type> test_beach_line;
-    std::vector< point_2d<coordinate_type> > points;
-    for (int i = 0; i < 33; i++)
-        for (int j = 0; j < 33; j++)
-            points.push_back(make_point_2d<coordinate_type>(
-                static_cast<coordinate_type>(i), static_cast<coordinate_type>(j)));
-    
-    test_beach_line.init(points);
-    test_beach_line.run_sweepline();
-    voronoi_output_clipped<coordinate_type> test_output;
-    test_beach_line.clip(test_output);
-    VERIFY_VORONOI_OUTPUT(test_output, COMPLETE_VERIFICATION);
-
-    BOOST_CHECK_EQUAL(test_output.num_cell_records, 1089);
-    BOOST_CHECK_EQUAL(test_output.num_vertex_records, 1024);
-    BOOST_CHECK_EQUAL(test_output.num_edge_records, 2112);
-}
-
-#ifndef _DEBUG
-// Sites: {(x, y) | x = 0 .. 100, y = 0 .. 100}.
-BOOST_AUTO_TEST_CASE_TEMPLATE(grid_test4, T, test_types) {
-    typedef T coordinate_type;
-    voronoi_builder<coordinate_type> test_beach_line;
-    std::vector< point_2d<coordinate_type> > points;
-    for (int i = 0; i < 100; i++)
-        for (int j = 0; j < 100; j++)
-            points.push_back(make_point_2d<coordinate_type>(
-                static_cast<coordinate_type>(i), static_cast<coordinate_type>(j)));
-    
-    test_beach_line.init(points);
-    test_beach_line.run_sweepline();
-    voronoi_output_clipped<coordinate_type> test_output;
-    test_beach_line.clip(test_output);
-    VERIFY_VORONOI_OUTPUT(test_output, COMPLETE_VERIFICATION);
-
-    BOOST_CHECK_EQUAL(test_output.num_cell_records, 10000);
-    BOOST_CHECK_EQUAL(test_output.num_vertex_records, 9801);
-    BOOST_CHECK_EQUAL(test_output.num_edge_records, 19800);
-}
-#endif
-
 #ifndef _DEBUG
-// Sites: {(x, y) | x = 0 .. 333, y = 0 .. 333}.
-BOOST_AUTO_TEST_CASE_TEMPLATE(grid_test5, T, test_types) {
-    typedef T coordinate_type;
-    voronoi_builder<coordinate_type> test_beach_line;
-    std::vector< point_2d<coordinate_type> > points;
-    for (int i = 0; i < 333; i++)
-        for (int j = 0; j < 333; j++)
-            points.push_back(make_point_2d<coordinate_type>(
-                static_cast<coordinate_type>(i), static_cast<coordinate_type>(j)));
-    
-    test_beach_line.init(points);
-    test_beach_line.run_sweepline();
-    voronoi_output_clipped<coordinate_type> test_output;
-    test_beach_line.clip(test_output);
-    VERIFY_VORONOI_OUTPUT(test_output, COMPLETE_VERIFICATION);
-
-    BOOST_CHECK_EQUAL(test_output.num_cell_records, 110889);
-    BOOST_CHECK_EQUAL(test_output.num_vertex_records, 110224);
-    BOOST_CHECK_EQUAL(test_output.num_edge_records, 221112);
-}
-#endif
-
-#ifndef _DEBUG
-// Generate 10 random sites 10000 times.
-BOOST_AUTO_TEST_CASE_TEMPLATE(random_test1, T, test_types) {
-    typedef T coordinate_type;
-    srand(static_cast<unsigned int>(time(NULL)));
-    voronoi_builder<coordinate_type> test_beach_line;
-    voronoi_output_clipped<coordinate_type> test_output;
-    std::vector< point_2d<coordinate_type> > points;
-    for (int i = 0; i < 10000; i++) {
-        points.clear();
-        for (int j = 0; j < 10; j++)
-            points.push_back(make_point_2d<coordinate_type>(
-                static_cast<coordinate_type>(rand() % 10 - 5),
-                static_cast<coordinate_type>(rand() % 10 - 5)));
-        test_beach_line.init(points);
-        test_beach_line.run_sweepline();
-        test_beach_line.clip(test_output);
-        VERIFY_VORONOI_OUTPUT(test_output, COMPLETE_VERIFICATION);
-        test_beach_line.reset();
-    }
-}
-#endif
-
-#ifndef _DEBUG
-// Generate 100 random sites 1000 times.
-BOOST_AUTO_TEST_CASE_TEMPLATE(random_test2, T, test_types) {
-    typedef T coordinate_type;
-    srand(static_cast<unsigned int>(time(NULL)));
-    voronoi_builder<coordinate_type> test_beach_line;
-    voronoi_output_clipped<coordinate_type> test_output;
-    std::vector< point_2d<coordinate_type> > points;
-    for (int i = 0; i < 1000; i++) {
-        points.clear();
-        for (int j = 0; j < 100; j++)
-            points.push_back(make_point_2d<coordinate_type>(
-                static_cast<coordinate_type>(rand() % 100 - 50),
-                static_cast<coordinate_type>(rand() % 100 - 50)));
-        test_beach_line.init(points);
-        test_beach_line.run_sweepline();
-        test_beach_line.clip(test_output);
-        VERIFY_VORONOI_OUTPUT(test_output, COMPLETE_VERIFICATION);
-        test_beach_line.reset();
-    }
-}
-#endif
-
-#ifndef _DEBUG
-// Generate 1000 random sites 100 times.
-BOOST_AUTO_TEST_CASE_TEMPLATE(random_test3, T, test_types) {
-    typedef T coordinate_type;
-    srand(static_cast<unsigned int>(time(NULL)));
-    voronoi_builder<coordinate_type> test_beach_line;
-    voronoi_output_clipped<coordinate_type> test_output;
-    std::vector< point_2d<coordinate_type> > points;
-    for (int i = 0; i < 100; i++) {
-        points.clear();
-        for (int j = 0; j < 1000; j++)
-        points.push_back(make_point_2d<coordinate_type>(
-            static_cast<coordinate_type>(rand() % 100 - 50),
-            static_cast<coordinate_type>(rand() % 100 - 50)));
-        test_beach_line.init(points);
-        test_beach_line.run_sweepline();
-        test_beach_line.clip(test_output);
-        VERIFY_VORONOI_OUTPUT(test_output, COMPLETE_VERIFICATION);
-        test_beach_line.reset();
-    }
-}
-#endif
-
-#ifndef _DEBUG
-// Generate 10000 random sites 10 times.
-BOOST_AUTO_TEST_CASE_TEMPLATE(random_test4, T, test_types) {
-    typedef T coordinate_type;
-    srand(static_cast<unsigned int>(time(NULL)));
-    voronoi_builder<coordinate_type> test_beach_line;
-    voronoi_output_clipped<coordinate_type> test_output;
-    std::vector< point_2d<coordinate_type> > points;
-    for (int i = 0; i < 10; i++) {
-        points.clear();
-        for (int j = 0; j < 10000; j++)
-        points.push_back(make_point_2d<coordinate_type>(
-            static_cast<coordinate_type>(rand() % 1000 - 500),
-            static_cast<coordinate_type>(rand() % 1000 - 500)));
-        test_beach_line.init(points);
-        test_beach_line.run_sweepline();
-        test_beach_line.clip(test_output);
-        VERIFY_VORONOI_OUTPUT(test_output, COMPLETE_VERIFICATION);
-        test_beach_line.reset();
-    }
-}
-#endif
-
-#ifndef _DEBUG
-// Generate 100000 random sites.
-BOOST_AUTO_TEST_CASE_TEMPLATE(random_test5, T, test_types) {
-    typedef T coordinate_type;
-    srand(static_cast<unsigned int>(time(NULL)));
-    voronoi_builder<coordinate_type> test_beach_line;
-    voronoi_output_clipped<coordinate_type> test_output;
-    std::vector< point_2d<coordinate_type> > points;
-    for (int i = 0; i < 1; i++) {
-        points.clear();
-        for (int j = 0; j < 100000; j++)
-        points.push_back(make_point_2d<coordinate_type>(
-            static_cast<coordinate_type>(rand() % 1000 - 500),
-            static_cast<coordinate_type>(rand() % 1000 - 500)));
-        test_beach_line.init(points);
-        test_beach_line.run_sweepline();
-        test_beach_line.clip(test_output);
-        VERIFY_VORONOI_OUTPUT(test_output, COMPLETE_VERIFICATION);
-        test_beach_line.reset();
+BOOST_AUTO_TEST_CASE_TEMPLATE(grid_test, T, test_types) {
+    voronoi_builder<T> test_builder;
+    voronoi_output_clipped<T> test_output_small, test_output_large;
+    std::vector< point_2d<T> > point_vec_small, point_vec_large;
+    int grid_size[4] = {10, 33, 100, 333};
+    int max_value[4] = {10, 33, 100, 333};
+    int array_length = sizeof(grid_size) / sizeof(int);
+    for (int k = 0; k < array_length; k++) {
+        int koef = std::numeric_limits<int>::max() / max_value[k];
+        for (int i = 0; i < grid_size[k]; i++)
+            for (int j = 0; j < grid_size[k]; j++) {
+                point_vec_small.push_back(make_point_2d<T>(i, j));
+                point_vec_large.push_back(make_point_2d<T>(koef * i, koef * j));
+            }
+        test_builder.init(point_vec_small);
+        test_builder.run_sweepline();
+        test_builder.clip(test_output_small);
+        test_builder.init(point_vec_large);
+        test_builder.run_sweepline();
+        test_builder.clip(test_output_large);
+        VERIFY_VORONOI_OUTPUT(test_output_small, COMPLETE_VERIFICATION);
+        VERIFY_VORONOI_OUTPUT(test_output_large, COMPLETE_VERIFICATION);
+        BOOST_CHECK_EQUAL(test_output_small.num_cell_records, test_output_large.num_cell_records);
+        BOOST_CHECK_EQUAL(test_output_small.num_vertex_records, test_output_large.num_vertex_records);
+        BOOST_CHECK_EQUAL(test_output_small.num_edge_records, test_output_large.num_edge_records);
+        point_vec_small.clear();
+        point_vec_large.clear();
     }
 }
 #endif
 
 #ifndef _DEBUG
-// Generate 1000000 random sites.
-BOOST_AUTO_TEST_CASE_TEMPLATE(random_test6, T, test_types) {
-    typedef T coordinate_type;
+BOOST_AUTO_TEST_CASE_TEMPLATE(random_test, T, test_types) {
     srand(static_cast<unsigned int>(time(NULL)));
-    voronoi_builder<coordinate_type> test_beach_line;
-    voronoi_output_clipped<coordinate_type> test_output;
-    std::vector< point_2d<coordinate_type> > points;
-    for (int i = 0; i < 1; i++) {
-        points.clear();
-        for (int j = 0; j < 1000000; j++)
-        points.push_back(make_point_2d<coordinate_type>(
-            static_cast<coordinate_type>(rand() % 10000 - 5000),
-            static_cast<coordinate_type>(rand() % 10000 - 5000)));
-        test_beach_line.init(points);
-        test_beach_line.run_sweepline();
-        test_beach_line.clip(test_output);
-        VERIFY_VORONOI_OUTPUT(test_output, FAST_VERIFICATION);
-        test_beach_line.reset();
+    voronoi_builder<T> test_builder;
+    voronoi_output_clipped<T> test_output_small, test_output_large;
+    std::vector< point_2d<T> > point_vec_small, point_vec_large;
+    int num_points[] = {10, 100, 1000, 10000, 100000};
+    int num_runs[] = {10000, 1000, 100, 10, 1};
+    int mod_koef[] = {10, 100, 100, 10000, 10000};
+    int max_value[] = {5, 50, 50, 5000, 5000};
+    int array_length = sizeof(num_points) / sizeof(int);
+    for (int k = 0; k < array_length; k++) {
+        int koef = std::numeric_limits<int>::max() / max_value[k];
+        for (int i = 0; i < num_runs[k]; i++) {
+            for (int j = 0; j < num_points[k]; j++) {
+                T x = rand() % mod_koef[k] - mod_koef[k] / 2;
+                T y = rand() % mod_koef[k] - mod_koef[k] / 2;
+                point_vec_small.push_back(make_point_2d<T>(x, y));
+                point_vec_large.push_back(make_point_2d<T>(koef * x, koef * y));
+            }
+            test_builder.init(point_vec_small);
+            test_builder.run_sweepline();
+            test_builder.clip(test_output_small);
+            test_builder.init(point_vec_large);
+            test_builder.run_sweepline();
+            test_builder.clip(test_output_large);
+            VERIFY_VORONOI_OUTPUT(test_output_small, COMPLETE_VERIFICATION);
+            VERIFY_VORONOI_OUTPUT(test_output_large, COMPLETE_VERIFICATION);
+            BOOST_CHECK_EQUAL(test_output_small.num_cell_records, test_output_large.num_cell_records);
+            BOOST_CHECK_EQUAL(test_output_small.num_vertex_records, test_output_large.num_vertex_records);
+            BOOST_CHECK_EQUAL(test_output_small.num_edge_records, test_output_large.num_edge_records);
+            point_vec_small.clear();
+            point_vec_large.clear();
+        }
     }
 }
 #endif
 
 #ifndef _DEBUG
-BOOST_AUTO_TEST_CASE_TEMPLATE(random_test7, T, test_types) {
-    typedef typename voronoi_output_clipped<T>::voronoi_vertex_const_iterator_type
-        voronoi_vertex_const_iterator_type;
+BOOST_AUTO_TEST_CASE_TEMPLATE(enormous_random_test, T, test_types) {
     srand(static_cast<unsigned int>(time(NULL)));
     voronoi_builder<T> test_builder;
-    voronoi_output_clipped<T> test_output_small, test_output_large;
-    std::vector< point_2d<T> > points_small, points_large;
-    int num_points = 27;
-    int md = 20;
-    int half_md = md >> 1;
-    int koef = std::numeric_limits<int>::max() / half_md;
-    for (int i = 0; i < 10000; i++) {
-        points_small.clear();
-        points_large.clear();
-        for (int j = 0; j < num_points; j++) {
-            T x_small = static_cast<T>(rand() % md - half_md);
-            T y_small = static_cast<T>(rand() % md - half_md);
-            T x_large = x_small * koef;
-            T y_large = y_small * koef;
-            points_small.push_back(make_point_2d(x_small, y_small));
-            points_large.push_back(make_point_2d(x_large, y_large));
-        }
-        test_builder.init(points_small);
-        test_builder.run_sweepline();
-        test_builder.clip(test_output_small);
-        test_builder.init(points_large);
-        test_builder.run_sweepline();
-        test_builder.clip(test_output_large);
-        VERIFY_VORONOI_OUTPUT(test_output_small, COMPLETE_VERIFICATION);
-        VERIFY_VORONOI_OUTPUT(test_output_large, COMPLETE_VERIFICATION);
-        BOOST_CHECK_EQUAL(test_output_small.num_cell_records, test_output_large.num_cell_records);
-        BOOST_CHECK_EQUAL(test_output_small.num_vertex_records, test_output_large.num_vertex_records);
-        BOOST_CHECK_EQUAL(test_output_small.num_edge_records, test_output_large.num_edge_records);
-        test_builder.reset();
-    }
+    voronoi_output_clipped<T> test_output;
+    std::vector< point_2d<T> > point_vec;
+    for (int i = 0; i < 1000000; i++)
+        point_vec.push_back(make_point_2d<T>(rand() % 10000 - 5000, rand() % 10000 - 5000));
+    test_builder.init(point_vec);
+    test_builder.run_sweepline();
+    test_builder.clip(test_output);
+    VERIFY_VORONOI_OUTPUT(test_output, FAST_VERIFICATION);
 }
 #endif
 
 BOOST_AUTO_TEST_CASE_TEMPLATE(segment_sites_test1, T, test_types) {
     typedef T coordinate_type;
-    voronoi_builder<coordinate_type> test_voronoi_builder;
+    voronoi_builder<coordinate_type> test_builder;
+    voronoi_output_clipped<coordinate_type> test_output;
     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();
-
-	// TODO(asydorchuk): Add output checks there.
+    test_builder.init(segm_vec);
+    test_builder.run_sweepline();
+    test_builder.clip(test_output);
+    BOOST_CHECK_EQUAL(test_output.num_cell_records, 3);
+    BOOST_CHECK_EQUAL(test_output.num_vertex_records, 0);
+    BOOST_CHECK_EQUAL(test_output.num_edge_records, 2);
+    VERIFY_VORONOI_OUTPUT(test_output, NO_HALF_EDGE_INTERSECTIONS);
 }
 
 BOOST_AUTO_TEST_CASE_TEMPLATE(segment_sites_test2, T, test_types) {
     typedef T coordinate_type;
-    voronoi_builder<coordinate_type> test_voronoi_builder;
+    voronoi_builder<coordinate_type> test_builder;
+    voronoi_output_clipped<coordinate_type> test_output;
     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);
@@ -706,14 +510,19 @@
     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.
+    test_builder.init(point_vec, segm_vec);
+    test_builder.run_sweepline();
+    test_builder.clip(test_output);
+    BOOST_CHECK_EQUAL(test_output.num_cell_records, 5);
+    BOOST_CHECK_EQUAL(test_output.num_vertex_records, 4);
+    BOOST_CHECK_EQUAL(test_output.num_edge_records, 8);
+    VERIFY_VORONOI_OUTPUT(test_output, NO_HALF_EDGE_INTERSECTIONS);
 }
 
 BOOST_AUTO_TEST_CASE_TEMPLATE(segment_sites_test3, T, test_types) {
     typedef T coordinate_type;
-    voronoi_builder<coordinate_type> test_voronoi_builder;
+    voronoi_builder<coordinate_type> test_builder;
+    voronoi_output_clipped<coordinate_type> test_output;
     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);
@@ -723,15 +532,19 @@
     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.
+    test_builder.init(point_vec, segm_vec);
+    test_builder.run_sweepline();
+    test_builder.clip(test_output);
+    BOOST_CHECK_EQUAL(test_output.num_cell_records, 5);
+    BOOST_CHECK_EQUAL(test_output.num_vertex_records, 4);
+    BOOST_CHECK_EQUAL(test_output.num_edge_records, 8);
+    VERIFY_VORONOI_OUTPUT(test_output, NO_HALF_EDGE_INTERSECTIONS);
 }
 
 BOOST_AUTO_TEST_CASE_TEMPLATE(segment_sites_test4, T, test_types) {
     typedef T coordinate_type;
-    voronoi_builder<coordinate_type> test_voronoi_builder;
+    voronoi_builder<coordinate_type> test_builder;
+    voronoi_output_clipped<coordinate_type> test_output;
     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);
@@ -741,15 +554,19 @@
     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.
+    test_builder.init(point_vec, segm_vec);
+    test_builder.run_sweepline();
+    test_builder.clip(test_output);
+    BOOST_CHECK_EQUAL(test_output.num_cell_records, 5);
+    BOOST_CHECK_EQUAL(test_output.num_vertex_records, 3);
+    BOOST_CHECK_EQUAL(test_output.num_edge_records, 7);
+    VERIFY_VORONOI_OUTPUT(test_output, NO_HALF_EDGE_INTERSECTIONS);
 }
 
 BOOST_AUTO_TEST_CASE_TEMPLATE(segment_site_test5, T, test_types) {
     typedef T coordinate_type;
-    voronoi_builder<coordinate_type> test_voronoi_builder;
+    voronoi_builder<coordinate_type> test_builder;
+    voronoi_output_clipped<coordinate_type> test_output;
     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);
@@ -761,15 +578,19 @@
     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.
+    test_builder.init(point_vec, segm_vec);
+    test_builder.run_sweepline();
+    test_builder.clip(test_output);
+    BOOST_CHECK_EQUAL(test_output.num_cell_records, 6);
+    BOOST_CHECK_EQUAL(test_output.num_vertex_records, 4);
+    BOOST_CHECK_EQUAL(test_output.num_edge_records, 9);
+    VERIFY_VORONOI_OUTPUT(test_output, NO_HALF_EDGE_INTERSECTIONS);
 }
 
 BOOST_AUTO_TEST_CASE_TEMPLATE(segment_site_test6, T, test_types) {
     typedef T coordinate_type;
-    voronoi_builder<coordinate_type> test_voronoi_builder;
+    voronoi_builder<coordinate_type> test_builder;
+    voronoi_output_clipped<coordinate_type> test_output;
     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>(-1, 1);
@@ -777,15 +598,19 @@
     point_2d<T> point3 = make_point_2d<T>(1, 2);
     segm_vec.push_back(std::make_pair< point_2d<T>, point_2d<T> >(point2, point3));
     point_vec.push_back(point1);
-    test_voronoi_builder.init(point_vec, segm_vec);
-    test_voronoi_builder.run_sweepline();
-
-	// TODO(asydorchuk): Add output checks there.
+    test_builder.init(point_vec, segm_vec);
+    test_builder.run_sweepline();
+    test_builder.clip(test_output);
+    BOOST_CHECK_EQUAL(test_output.num_cell_records, 4);
+    BOOST_CHECK_EQUAL(test_output.num_vertex_records, 2);
+    BOOST_CHECK_EQUAL(test_output.num_edge_records, 5);
+    VERIFY_VORONOI_OUTPUT(test_output, NO_HALF_EDGE_INTERSECTIONS);
 }
 
 BOOST_AUTO_TEST_CASE_TEMPLATE(segment_site_test7, T, test_types) {
     typedef T coordinate_type;
-    voronoi_builder<coordinate_type> test_voronoi_builder;
+    voronoi_builder<coordinate_type> test_builder;
+    voronoi_output_clipped<coordinate_type> test_output;
     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);
@@ -795,15 +620,20 @@
     segm_vec.push_back(std::make_pair(point1, point2));
     segm_vec.push_back(std::make_pair(point2, point3));
     segm_vec.push_back(std::make_pair(point3, point4));
-    test_voronoi_builder.init(segm_vec);
-    test_voronoi_builder.run_sweepline();
-
-	// TODO(asydorchuk): Add output checks there.
+    test_builder.init(segm_vec);
+    test_builder.run_sweepline();
+    test_builder.clip(test_output);
+    BOOST_CHECK_EQUAL(test_output.num_cell_records, 7);
+    BOOST_CHECK_EQUAL(test_output.num_vertex_records, 6);
+    BOOST_CHECK_EQUAL(test_output.num_edge_records, 12);
+    VERIFY_VORONOI_OUTPUT(test_output, NO_HALF_EDGE_INTERSECTIONS);
+    
 }
 
 BOOST_AUTO_TEST_CASE_TEMPLATE(segment_site_test8, T, test_types) {
     typedef T coordinate_type;
-    voronoi_builder<coordinate_type> test_voronoi_builder;
+    voronoi_builder<coordinate_type> test_builder;
+    voronoi_output_clipped<coordinate_type> test_output;
     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);
@@ -814,8 +644,107 @@
     segm_vec.push_back(std::make_pair(point2, point3));
     segm_vec.push_back(std::make_pair(point3, point4));
     segm_vec.push_back(std::make_pair(point4, point1));
-    test_voronoi_builder.init(segm_vec);
-    test_voronoi_builder.run_sweepline();
+    test_builder.init(segm_vec);
+    test_builder.run_sweepline();
+    test_builder.clip(test_output);
+    BOOST_CHECK_EQUAL(test_output.num_cell_records, 8);
+    BOOST_CHECK_EQUAL(test_output.num_vertex_records, 5);
+    BOOST_CHECK_EQUAL(test_output.num_edge_records, 12);
+    VERIFY_VORONOI_OUTPUT(test_output, NO_HALF_EDGE_INTERSECTIONS);
+}
 
-	// TODO(asydorchuk): Add output checks there.
+#ifndef _DEBUG
+BOOST_AUTO_TEST_CASE_TEMPLATE(segment_grid_test, T, test_types) {
+    voronoi_builder<T> test_builder;
+    voronoi_output_clipped<T> test_output_small, test_output_large;
+    std::vector< typename voronoi_builder<T>::Segment2D > segm_vec_small, segm_vec_large;
+    int grid_size[4] = {10, 33, 100, 333};
+    int max_value[4] = {100, 330, 1000, 3330};
+    int array_length = sizeof(grid_size) / sizeof(int);
+    for (int k = 0; k < array_length; k++) {
+        int cur_sz = grid_size[k];
+        int koef = std::numeric_limits<int>::max() / max_value[k];
+        for (int i = 0; i < cur_sz + 1; i++)
+            for (int j = 0; j < cur_sz; j++) {
+                point_2d<T> point1_1(10 * i, 10 * j);
+                point_2d<T> point1_2(koef * 10 * i, koef * 10 * j);
+                point_2d<T> point2_1(10 * i, 10 * j + 10);
+                point_2d<T> point2_2(koef * 10 * i, koef * (10 * j + 10));
+                segm_vec_small.push_back(std::make_pair(point1_1, point2_1));
+                segm_vec_large.push_back(std::make_pair(point1_2, point2_2));
+                point_2d<T> point3_1(10 * j, 10 * i);
+                point_2d<T> point3_2(koef * 10 * j, koef * 10 * i);
+                point_2d<T> point4_1(10 * j + 10, 10 * i);
+                point_2d<T> point4_2(koef * (10 * j + 10), koef * 10 * i);
+                segm_vec_small.push_back(std::make_pair(point3_1, point4_1));
+                segm_vec_large.push_back(std::make_pair(point3_2, point4_2));
+            }
+        test_builder.init(segm_vec_small);
+        test_builder.run_sweepline();
+        test_builder.clip(test_output_small);
+        test_builder.init(segm_vec_large);
+        test_builder.run_sweepline();
+        test_builder.clip(test_output_large);
+        VERIFY_VORONOI_OUTPUT(test_output_small, NO_HALF_EDGE_INTERSECTIONS);
+        VERIFY_VORONOI_OUTPUT(test_output_large, NO_HALF_EDGE_INTERSECTIONS);
+        BOOST_CHECK_EQUAL(test_output_small.num_cell_records, test_output_large.num_cell_records);
+        BOOST_CHECK_EQUAL(test_output_small.num_vertex_records, test_output_large.num_vertex_records);
+        BOOST_CHECK_EQUAL(test_output_small.num_edge_records, test_output_large.num_edge_records);
+        segm_vec_small.clear();
+        segm_vec_large.clear();
+    }
+}
+#endif
+
+#ifndef _DEBUG
+BOOST_AUTO_TEST_CASE_TEMPLATE(segment_random_test, T, test_types) {
+    srand(static_cast<unsigned int>(time(NULL)));
+    voronoi_builder<T> test_builder;
+    voronoi_output_clipped<T> test_output_small, test_output_large;
+    std::vector< typename voronoi_builder<T>::Segment2D > segm_vec;
+    int num_segments[] = {10, 100, 1000, 10000, 100000};
+    int num_runs[] = {10000, 1000, 100, 10, 1};
+    int mod_koef1[] = {10, 100, 100, 10000, 10000};
+    int mod_koef2[] = {10, 100, 100, 100, 100};
+    int max_value[] = {10, 100, 100, 5050, 5050};
+    int array_length = sizeof(num_segments) / sizeof(int);
+    for (int k = 0; k < array_length; k++) {
+        int koef = std::numeric_limits<int>::max() / max_value[k];
+        for (int i = 0; i < num_runs[k]; i++) {
+            for (int j = 0; j < num_segments[k]; j++) {
+                T x1 = (rand() % mod_koef1[k]) - mod_koef1[k] / 2;
+                T y1 = (rand() % mod_koef1[k]) - mod_koef1[k] / 2;
+                T dx = 0, dy = 0;
+                while (dx == 0 && dy == 0) {
+                    dx = (rand() % mod_koef2[k]) - mod_koef2[k] / 2;
+                    dy = (rand() % mod_koef2[k]) - mod_koef2[k] / 2;
+                }
+                T x2 = x1 + dx;
+                T y2 = y1 + dy;
+                point_2d<T> point1_small(x1, y1);
+                point_2d<T> point2_small(x2, y2);
+                segm_vec.push_back(std::make_pair(point1_small, point2_small));
+            }
+            remove_intersections(segm_vec);
+            test_builder.init(segm_vec);
+            test_builder.run_sweepline();
+            test_builder.clip(test_output_small);
+            for (size_t j = 0; j < segm_vec.size(); j++) {
+                segm_vec[j].first.x(segm_vec[j].first.x() * koef);
+                segm_vec[j].first.y(segm_vec[j].first.y() * koef);
+                segm_vec[j].second.x(segm_vec[j].second.x() * koef);
+                segm_vec[j].second.y(segm_vec[j].second.y() * koef);
+            }
+            test_builder.init(segm_vec);
+            test_builder.run_sweepline();
+            test_builder.clip(test_output_large);
+            VERIFY_VORONOI_OUTPUT(test_output_small, NO_HALF_EDGE_INTERSECTIONS);
+            VERIFY_VORONOI_OUTPUT(test_output_large, NO_HALF_EDGE_INTERSECTIONS);
+            BOOST_CHECK_EQUAL(test_output_small.num_cell_records, test_output_large.num_cell_records);
+            BOOST_CHECK_EQUAL(test_output_small.num_vertex_records, test_output_large.num_vertex_records);
+            BOOST_CHECK_EQUAL(test_output_small.num_edge_records, test_output_large.num_edge_records);
+            segm_vec.clear();
+        }
+    }
 }
+#endif