[Boost-commit] svn:boost r78292 - in sandbox/gtl: boost/polygon libs/polygon/benchmark libs/polygon/example libs/polygon/test

Subject: [Boost-commit] svn:boost r78292 - in sandbox/gtl: boost/polygon libs/polygon/benchmark libs/polygon/example libs/polygon/test
From: sydorchuk.andriy_at_[hidden]
Date: 2012-05-01 08:43:53

Author: asydorchuk
Date: 2012-05-01 08:43:51 EDT (Tue, 01 May 2012)
New Revision: 78292
URL: http://svn.boost.org/trac/boost/changeset/78292

Log:
Updating test files indentation.
Removing dependencies on the segment_set_data.hpp (as it won't be present with the next release).
Extracting segment set clean functionality to a separate method.

Text files modified: 
   sandbox/gtl/boost/polygon/polygon.hpp                             |     2                                         
   sandbox/gtl/libs/polygon/benchmark/voronoi_benchmark_segments.cpp |    48 +                                       
   sandbox/gtl/libs/polygon/example/voronoi_basic_tutorial.cpp       |     4                                         
   sandbox/gtl/libs/polygon/example/voronoi_visualizer.cpp           |     6                                         
   sandbox/gtl/libs/polygon/test/gtl_boost_unit_test.cpp             |    22                                         
   sandbox/gtl/libs/polygon/test/voronoi_benchmark_test.cpp          |     8                                         
   sandbox/gtl/libs/polygon/test/voronoi_builder_test.cpp            |   989 +++++++++++++++++++-------------------- 
   sandbox/gtl/libs/polygon/test/voronoi_ctypes_test.cpp             |   472 +++++++++---------                      
   sandbox/gtl/libs/polygon/test/voronoi_predicates_test.cpp         |   582 +++++++++++-----------                  
   sandbox/gtl/libs/polygon/test/voronoi_robust_fpt_test.cpp         |   467 +++++++++---------                      
   sandbox/gtl/libs/polygon/test/voronoi_structures_test.cpp         |   178 +++---                                  
   sandbox/gtl/libs/polygon/test/voronoi_test_helper.hpp             |   358 +++++++------                           
   12 files changed, 1597 insertions(+), 1539 deletions(-)

Modified: sandbox/gtl/boost/polygon/polygon.hpp
==============================================================================
--- sandbox/gtl/boost/polygon/polygon.hpp	(original)
+++ sandbox/gtl/boost/polygon/polygon.hpp	2012-05-01 08:43:51 EDT (Tue, 01 May 2012)
@@ -88,8 +88,8 @@
 
 #include "polygon_set_concept.hpp"
 
+//segment
 #include "segment_data.hpp"
-#include "segment_set_data.hpp"
 #include "segment_traits.hpp"
 #include "segment_concept.hpp"
 

Modified: sandbox/gtl/libs/polygon/benchmark/voronoi_benchmark_segments.cpp
==============================================================================
--- sandbox/gtl/libs/polygon/benchmark/voronoi_benchmark_segments.cpp	(original)
+++ sandbox/gtl/libs/polygon/benchmark/voronoi_benchmark_segments.cpp	2012-05-01 08:43:51 EDT (Tue, 01 May 2012)
@@ -41,7 +41,7 @@
 #include <boost/polygon/polygon.hpp>
 typedef boost::polygon::point_data<int32> POINT_POLYGON;
 typedef boost::polygon::segment_data<int32> SEGMENT_POLYGON;
-typedef boost::polygon::segment_set_data<int32> SSD_POLYGON;
+typedef std::vector<SEGMENT_POLYGON> SSD_POLYGON;
 
 const int RANDOM_SEED = 27;
 const int NUM_TESTS = 6;
@@ -57,6 +57,38 @@
   bf << "|" << std::endl;
 }
 
+void clean_segment_set(std::vector<SEGMENT_POLYGON> &data) {
+  typedef int32 Unit;
+  typedef boost::polygon::scanline_base<Unit>::Point Point;
+  typedef boost::polygon::scanline_base<Unit>::half_edge half_edge;
+  typedef int segment_id;
+  std::vector<std::pair<half_edge, segment_id> > half_edges;
+  std::vector<std::pair<half_edge, segment_id> > half_edges_out;
+  segment_id id = 0;
+  half_edges.reserve(data.size());
+  for(std::vector<SEGMENT_POLYGON>::iterator it = data.begin(); it != data.end(); ++it) {
+    POINT_POLYGON l = it->low();
+    POINT_POLYGON h = it->high();
+    half_edges.push_back(std::make_pair(half_edge(l, h), id++));
+  }
+  half_edges_out.reserve(half_edges.size());
+  //apparently no need to pre-sort data when calling validate_scan
+  boost::polygon::line_intersection<Unit>::validate_scan(
+      half_edges_out, half_edges.begin(), half_edges.end());
+  std::vector<SEGMENT_POLYGON> result;
+  result.reserve(half_edges_out.size());
+  for(std::size_t i = 0; i < half_edges_out.size(); ++i) {
+    id = half_edges_out[i].second;
+    POINT_POLYGON l = half_edges_out[i].first.first;
+    POINT_POLYGON h = half_edges_out[i].first.second;
+    SEGMENT_POLYGON orig_seg = data[id];
+    if(orig_seg.high() < orig_seg.low())
+      std::swap(l, h);
+    result.push_back(SEGMENT_POLYGON(l, h));
+  }
+  std::swap(result, data);
+}
+
 std::vector<double> get_intersection_runtime() {
   std::vector<double> running_times;
   boost::mt19937 gen(RANDOM_SEED);
@@ -69,10 +101,10 @@
         int32 y1 = gen();
         int32 dx = (gen() & 1023) + 1;
         int32 dy = (gen() & 1023) + 1;
-        ssd.insert(SEGMENT_POLYGON(
+        ssd.push_back(SEGMENT_POLYGON(
             POINT_POLYGON(x1, y1), POINT_POLYGON(x1 + dx, y1 + dy)));
       }
-      ssd.clean();
+      clean_segment_set(ssd);
     }
     double time_per_test = timer.elapsed() / NUM_RUNS[i];
     running_times.push_back(timer.elapsed());
@@ -93,10 +125,10 @@
         int32 y1 = gen();
         int32 dx = (gen() & 1023) + 1;
         int32 dy = (gen() & 1023) + 1;
-        ssd.insert(SEGMENT_POLYGON(
+        ssd.push_back(SEGMENT_POLYGON(
             POINT_POLYGON(x1, y1), POINT_POLYGON(x1 + dx, y1 + dy)));
       }
-      ssd.clean();
+      clean_segment_set(ssd);
       boost::polygon::construct_voronoi(ssd.begin(), ssd.end(), &vd);
     }
     double time_per_test = (timer.elapsed() - running_times[i]) / NUM_RUNS[i];
@@ -117,12 +149,12 @@
         int32 y1 = gen();
         int32 dx = (gen() & 1023) + 1;
         int32 dy = (gen() & 1023) + 1;
-        ssd.insert(SEGMENT_POLYGON(POINT_POLYGON(x1, y1),
+        ssd.push_back(SEGMENT_POLYGON(POINT_POLYGON(x1, y1),
                                    POINT_POLYGON(x1 + dx, y1 + dy)));
       }
-      ssd.clean();
+      clean_segment_set(ssd);
       SDT_CGAL dt;
-      for (SSD_POLYGON::iterator_type it = ssd.begin(); it != ssd.end(); ++it) {
+      for (SSD_POLYGON::iterator it = ssd.begin(); it != ssd.end(); ++it) {
         dt.insert(Site_CGAL::construct_site_2(
           Point_CGAL(it->low().x(), it->low().y()),
           Point_CGAL(it->high().x(), it->high().y())));

Modified: sandbox/gtl/libs/polygon/example/voronoi_basic_tutorial.cpp
==============================================================================
--- sandbox/gtl/libs/polygon/example/voronoi_basic_tutorial.cpp	(original)
+++ sandbox/gtl/libs/polygon/example/voronoi_basic_tutorial.cpp	2012-05-01 08:43:51 EDT (Tue, 01 May 2012)
@@ -10,8 +10,8 @@
 #include <cstdio>
 #include <vector>
 
-#include "boost/polygon/voronoi.hpp"
-#include "boost/polygon/voronoi_utils.hpp"
+#include <boost/polygon/voronoi.hpp>
+#include <boost/polygon/voronoi_utils.hpp>
 using namespace boost::polygon;
 
 struct Point {

Modified: sandbox/gtl/libs/polygon/example/voronoi_visualizer.cpp
==============================================================================
--- sandbox/gtl/libs/polygon/example/voronoi_visualizer.cpp	(original)
+++ sandbox/gtl/libs/polygon/example/voronoi_visualizer.cpp	2012-05-01 08:43:51 EDT (Tue, 01 May 2012)
@@ -12,9 +12,9 @@
 #include <QtOpenGL/QGLWidget>
 #include <QtGui/QtGui>
 
-#include "boost/polygon/voronoi_builder.hpp"
-#include "boost/polygon/voronoi_diagram.hpp"
-#include "boost/polygon/voronoi_utils.hpp"
+#include <boost/polygon/voronoi_builder.hpp>
+#include <boost/polygon/voronoi_diagram.hpp>
+#include <boost/polygon/voronoi_utils.hpp>
 using namespace boost::polygon;
 
 class GLWidget : public QGLWidget {

Modified: sandbox/gtl/libs/polygon/test/gtl_boost_unit_test.cpp
==============================================================================
--- sandbox/gtl/libs/polygon/test/gtl_boost_unit_test.cpp	(original)
+++ sandbox/gtl/libs/polygon/test/gtl_boost_unit_test.cpp	2012-05-01 08:43:51 EDT (Tue, 01 May 2012)
@@ -13,18 +13,17 @@
 #include <stdlib.h>
 
 namespace boost { namespace polygon{
-    void addpoly(polygon_45_set_data<int>& pset,
-                 int* pts, int numpts) {
-      std::vector<point_data<int> > mppts;
-      for(unsigned int i = 0; i < numpts*2; i += 2) {
-        point_data<int>  pt(pts[i], pts[i+1]);
-        mppts.push_back(pt);
-      }
-      polygon_45_data<int> poly;
-      poly.set(mppts.begin(), mppts.end());
-      pset += poly;
+  void addpoly(polygon_45_set_data<int>& pset,
+               int* pts, int numpts) {
+    std::vector<point_data<int> > mppts;
+    for(unsigned int i = 0; i < numpts*2; i += 2) {
+      point_data<int>  pt(pts[i], pts[i+1]);
+      mppts.push_back(pt);
     }
-     
+    polygon_45_data<int> poly;
+    poly.set(mppts.begin(), mppts.end());
+    pset += poly;
+  }
 
   template <class T>
   std::ostream& operator << (std::ostream& o, const interval_data<T>& i)
@@ -3637,4 +3636,3 @@
   std::cout << "ALL TESTS COMPLETE\n";
   return 0;
 }
-

Modified: sandbox/gtl/libs/polygon/test/voronoi_benchmark_test.cpp
==============================================================================
--- sandbox/gtl/libs/polygon/test/voronoi_benchmark_test.cpp	(original)
+++ sandbox/gtl/libs/polygon/test/voronoi_benchmark_test.cpp	2012-05-01 08:43:51 EDT (Tue, 01 May 2012)
@@ -19,8 +19,8 @@
 #include <boost/test/test_case_template.hpp>
 #include <boost/timer.hpp>
 
-#include "boost/polygon/polygon.hpp"
-#include "boost/polygon/voronoi.hpp"
+#include <boost/polygon/polygon.hpp>
+#include <boost/polygon/voronoi.hpp>
 using namespace boost::polygon;
 
 typedef boost::mpl::list<int> test_types;
@@ -119,7 +119,7 @@
     typedef point_data<coordinate_type> point_type;
     typedef segment_data<coordinate_type> segment_type;
 
-    segment_set_data<coordinate_type> segments;
+    std::vector<segment_type> segments;
     {
         std::ifstream input_file(SEGMENT_INPUT_FILE);
         int num_segments;
@@ -129,7 +129,7 @@
         for (int i = 0; i < num_segments; ++i) {
             input_file >> x0 >> y0 >> x1 >> y1;
             point_type p0(x0, y0), p1(x1, y1);
-            segments.insert(segment_type(p0, p1));
+            segments.push_back(segment_type(p0, p1));
         }
         input_file.close();
     }

Modified: sandbox/gtl/libs/polygon/test/voronoi_builder_test.cpp
==============================================================================
--- sandbox/gtl/libs/polygon/test/voronoi_builder_test.cpp	(original)
+++ sandbox/gtl/libs/polygon/test/voronoi_builder_test.cpp	2012-05-01 08:43:51 EDT (Tue, 01 May 2012)
@@ -14,8 +14,8 @@
 #include <boost/random/mersenne_twister.hpp>
 #include <boost/test/test_case_template.hpp>
 
-#include "boost/polygon/polygon.hpp"
-#include "boost/polygon/voronoi.hpp"
+#include <boost/polygon/polygon.hpp>
+#include <boost/polygon/voronoi.hpp>
 using namespace boost::polygon;
 #include "voronoi_test_helper.hpp"
 
@@ -27,13 +27,13 @@
 typedef vd_type::const_vertex_iterator const_vertex_iterator;
 
 #define CHECK_EQUAL_POINTS(p1, p2) \
-        BOOST_CHECK(p1.x() == static_cast<T>(p2.x())); \
-        BOOST_CHECK(p1.y() == static_cast<T>(p2.y()))
+    BOOST_CHECK(p1.x() == static_cast<T>(p2.x())); \
+    BOOST_CHECK(p1.y() == static_cast<T>(p2.y()))
 
 #define CHECK_OUTPUT_SIZE(output, cells, vertices, edges) \
-        BOOST_CHECK(output.num_cells() == cells); \
-        BOOST_CHECK(output.num_vertices() == vertices); \
-        BOOST_CHECK(output.num_edges() == edges)
+    BOOST_CHECK(output.num_cells() == cells); \
+    BOOST_CHECK(output.num_vertices() == vertices); \
+    BOOST_CHECK(output.num_edges() == edges)
 
 #define VERIFY_OUTPUT(output) \
     BOOST_CHECK(voronoi_test_helper::verify_output(output, \
@@ -51,574 +51,571 @@
 
 // Sites: (0, 0).
 BOOST_AUTO_TEST_CASE_TEMPLATE(single_site_test, T, test_types) {
-    std::vector< point_data<T> > points;
-    points.push_back(point_data<T>(0, 0));
-    vd_type test_output;
-    construct_voronoi(points.begin(), points.end(), &test_output);
-    VERIFY_OUTPUT(test_output);
+  std::vector< point_data<T> > points;
+  points.push_back(point_data<T>(0, 0));
+  vd_type test_output;
+  construct_voronoi(points.begin(), points.end(), &test_output);
+  VERIFY_OUTPUT(test_output);
 
-    BOOST_CHECK(test_output.cells().size() == 1);
-    CHECK_OUTPUT_SIZE(test_output, 1, 0, 0);
+  BOOST_CHECK(test_output.cells().size() == 1);
+  CHECK_OUTPUT_SIZE(test_output, 1, 0, 0);
 
-    const_cell_iterator it = test_output.cells().begin();
-    BOOST_CHECK(it->incident_edge() == NULL);
+  const_cell_iterator it = test_output.cells().begin();
+  BOOST_CHECK(it->incident_edge() == NULL);
 }
 
 // Sites: (0, 0), (0, 1).
 BOOST_AUTO_TEST_CASE_TEMPLATE(collinear_sites_test1, T, test_types) {
-    std::vector< point_data<T> > points;
-    points.push_back(point_data<T>(0, 0));
-    points.push_back(point_data<T>(0, 1));
-    vd_type test_output;
-    construct_voronoi(points.begin(), points.end(), &test_output);
-    VERIFY_OUTPUT(test_output);
-    CHECK_OUTPUT_SIZE(test_output, 2, 0, 1);
-
-    const_cell_iterator cell_it = test_output.cells().begin();
-    cell_it++;
-
-    const voronoi_edge_type *edge1_1 = cell_it->incident_edge();
-    const voronoi_edge_type *edge1_2 = edge1_1->twin();
-
-    BOOST_CHECK_EQUAL(edge1_1->twin() == edge1_2, true);
-    BOOST_CHECK_EQUAL(edge1_2->twin() == edge1_1, true);
-
-    BOOST_CHECK_EQUAL(edge1_1->next() == edge1_1, true);
-    BOOST_CHECK_EQUAL(edge1_1->prev() == edge1_1, true);
-    BOOST_CHECK_EQUAL(edge1_1->rot_next() == NULL, true);
-    BOOST_CHECK_EQUAL(edge1_1->rot_prev() == NULL, true);
-
-    BOOST_CHECK_EQUAL(edge1_2->next() == edge1_2, true);
-    BOOST_CHECK_EQUAL(edge1_2->prev() == edge1_2, true);
-    BOOST_CHECK_EQUAL(edge1_2->rot_next() == NULL, true);
-    BOOST_CHECK_EQUAL(edge1_2->rot_prev() == NULL, true);
+  std::vector< point_data<T> > points;
+  points.push_back(point_data<T>(0, 0));
+  points.push_back(point_data<T>(0, 1));
+  vd_type test_output;
+  construct_voronoi(points.begin(), points.end(), &test_output);
+  VERIFY_OUTPUT(test_output);
+  CHECK_OUTPUT_SIZE(test_output, 2, 0, 1);
+
+  const_cell_iterator cell_it = test_output.cells().begin();
+  cell_it++;
+
+  const voronoi_edge_type *edge1_1 = cell_it->incident_edge();
+  const voronoi_edge_type *edge1_2 = edge1_1->twin();
+
+  BOOST_CHECK_EQUAL(edge1_1->twin() == edge1_2, true);
+  BOOST_CHECK_EQUAL(edge1_2->twin() == edge1_1, true);
+
+  BOOST_CHECK_EQUAL(edge1_1->next() == edge1_1, true);
+  BOOST_CHECK_EQUAL(edge1_1->prev() == edge1_1, true);
+  BOOST_CHECK_EQUAL(edge1_1->rot_next() == NULL, true);
+  BOOST_CHECK_EQUAL(edge1_1->rot_prev() == NULL, true);
+
+  BOOST_CHECK_EQUAL(edge1_2->next() == edge1_2, true);
+  BOOST_CHECK_EQUAL(edge1_2->prev() == edge1_2, true);
+  BOOST_CHECK_EQUAL(edge1_2->rot_next() == NULL, true);
+  BOOST_CHECK_EQUAL(edge1_2->rot_prev() == NULL, true);
 }
 
 // Sites: (0, 0), (1, 1), (2, 2).
 BOOST_AUTO_TEST_CASE_TEMPLATE(collinear_sites_test2, T, test_types) {
-    std::vector< point_data<T> > points;
-    points.push_back(point_data<T>(0, 0));
-    points.push_back(point_data<T>(1, 1));
-    points.push_back(point_data<T>(2, 2));
-    vd_type test_output;
-    construct_voronoi(points.begin(), points.end(), &test_output);
-    VERIFY_OUTPUT(test_output);
-    CHECK_OUTPUT_SIZE(test_output, 3, 0, 2);
-
-    const_cell_iterator cell_it = test_output.cells().begin();
-    const voronoi_edge_type *edge1_1 = cell_it->incident_edge();
-    const voronoi_edge_type *edge1_2 = edge1_1->twin();
-    cell_it++;
-    cell_it++;
-    const voronoi_edge_type *edge2_2 = cell_it->incident_edge();
-    const voronoi_edge_type *edge2_1 = edge2_2->twin();
-
-    BOOST_CHECK_EQUAL(edge1_1->twin() == edge1_2 && edge1_2->twin() == edge1_1, true);
-    BOOST_CHECK_EQUAL(edge2_1->twin() == edge2_2 && edge2_2->twin() == edge2_1, true);
-
-    BOOST_CHECK_EQUAL(edge1_1->next() == edge1_1 && edge1_1->prev() == edge1_1, true);
-    BOOST_CHECK_EQUAL(edge1_1->rot_next() == NULL && edge1_1->rot_prev() == NULL, true);
-    BOOST_CHECK_EQUAL(edge1_2->rot_next() == NULL && edge1_2->rot_prev() == NULL, true);
-    BOOST_CHECK_EQUAL(edge2_1->rot_next() == NULL && edge2_1->rot_prev() == NULL, true);
-    BOOST_CHECK_EQUAL(edge2_2->next() == edge2_2 && edge2_2->prev() == edge2_2, true);
-    BOOST_CHECK_EQUAL(edge2_2->rot_next() == NULL && edge2_2->rot_prev() == NULL, true);
+  std::vector< point_data<T> > points;
+  points.push_back(point_data<T>(0, 0));
+  points.push_back(point_data<T>(1, 1));
+  points.push_back(point_data<T>(2, 2));
+  vd_type test_output;
+  construct_voronoi(points.begin(), points.end(), &test_output);
+  VERIFY_OUTPUT(test_output);
+  CHECK_OUTPUT_SIZE(test_output, 3, 0, 2);
+
+  const_cell_iterator cell_it = test_output.cells().begin();
+  const voronoi_edge_type *edge1_1 = cell_it->incident_edge();
+  const voronoi_edge_type *edge1_2 = edge1_1->twin();
+  cell_it++;
+  cell_it++;
+  const voronoi_edge_type *edge2_2 = cell_it->incident_edge();
+  const voronoi_edge_type *edge2_1 = edge2_2->twin();
+
+  BOOST_CHECK_EQUAL(edge1_1->twin() == edge1_2 && edge1_2->twin() == edge1_1, true);
+  BOOST_CHECK_EQUAL(edge2_1->twin() == edge2_2 && edge2_2->twin() == edge2_1, true);
+
+  BOOST_CHECK_EQUAL(edge1_1->next() == edge1_1 && edge1_1->prev() == edge1_1, true);
+  BOOST_CHECK_EQUAL(edge1_1->rot_next() == NULL && edge1_1->rot_prev() == NULL, true);
+  BOOST_CHECK_EQUAL(edge1_2->rot_next() == NULL && edge1_2->rot_prev() == NULL, true);
+  BOOST_CHECK_EQUAL(edge2_1->rot_next() == NULL && edge2_1->rot_prev() == NULL, true);
+  BOOST_CHECK_EQUAL(edge2_2->next() == edge2_2 && edge2_2->prev() == edge2_2, true);
+  BOOST_CHECK_EQUAL(edge2_2->rot_next() == NULL && edge2_2->rot_prev() == NULL, true);
 
-    BOOST_CHECK_EQUAL(edge1_2->next() == edge2_1 && edge1_2->prev() == edge2_1, true);
-    BOOST_CHECK_EQUAL(edge2_1->next() == edge1_2 && edge2_1->prev() == edge1_2, true);
+  BOOST_CHECK_EQUAL(edge1_2->next() == edge2_1 && edge1_2->prev() == edge2_1, true);
+  BOOST_CHECK_EQUAL(edge2_1->next() == edge1_2 && edge2_1->prev() == edge1_2, true);
 }
 
 // Sites: (0, 0), (0, 4), (2, 1).
 BOOST_AUTO_TEST_CASE_TEMPLATE(triangle_test1, T, test_types) {
-    point_data<T> point1(0, 0);
-    point_data<T> point2(0, 4);
-    point_data<T> point3(2, 1);
-    std::vector< point_data<T> > points;
-    points.push_back(point1);
-    points.push_back(point2);
-    points.push_back(point3);
-    vd_type test_output;
-    construct_voronoi(points.begin(), points.end(), &test_output);
-    VERIFY_OUTPUT(test_output);
-    CHECK_OUTPUT_SIZE(test_output, 3, 1, 3);
-
-    const_vertex_iterator it = test_output.vertices().begin();
-    BOOST_CHECK_EQUAL(it->vertex().x() == static_cast<coordinate_type>(0.25) &&
-                      it->vertex().y() == static_cast<coordinate_type>(2.0), true);
-
-    const voronoi_edge_type *edge1_1 = it->incident_edge();
-    const voronoi_edge_type *edge1_2 = edge1_1->twin();
-    CHECK_EQUAL_POINTS(edge1_1->cell()->point0(), point2);
-    CHECK_EQUAL_POINTS(edge1_2->cell()->point0(), point3);
-
-    const voronoi_edge_type *edge2_1 = edge1_1->rot_prev();
-    const voronoi_edge_type *edge2_2 = edge2_1->twin();
-    CHECK_EQUAL_POINTS(edge2_1->cell()->point0(), point3);
-    CHECK_EQUAL_POINTS(edge2_2->cell()->point0(), point1);
-
-    const voronoi_edge_type *edge3_1 = edge2_1->rot_prev();
-    const voronoi_edge_type *edge3_2 = edge3_1->twin();
-    CHECK_EQUAL_POINTS(edge3_1->cell()->point0(), point1);
-    CHECK_EQUAL_POINTS(edge3_2->cell()->point0(), point2);
-
-    BOOST_CHECK_EQUAL(edge1_2->twin() == edge1_1, true);
-    BOOST_CHECK_EQUAL(edge2_2->twin() == edge2_1, true);
-    BOOST_CHECK_EQUAL(edge3_2->twin() == edge3_1, true);
-
-    BOOST_CHECK_EQUAL(edge1_1->prev() == edge3_2 && edge1_1->next() == edge3_2, true);
-    BOOST_CHECK_EQUAL(edge2_1->prev() == edge1_2 && edge2_1->next() == edge1_2, true);
-    BOOST_CHECK_EQUAL(edge3_1->prev() == edge2_2 && edge3_1->next() == edge2_2, true);
-
-    BOOST_CHECK_EQUAL(edge1_2->next() == edge2_1 && edge1_2->prev() == edge2_1, true);
-    BOOST_CHECK_EQUAL(edge2_2->next() == edge3_1 && edge2_2->prev() == edge3_1, true);
-    BOOST_CHECK_EQUAL(edge3_2->next() == edge1_1 && edge3_2->prev() == edge1_1, true);
-
-    BOOST_CHECK_EQUAL(edge1_1->rot_next() == edge3_1, true);
-    BOOST_CHECK_EQUAL(edge3_1->rot_next() == edge2_1, true);
-    BOOST_CHECK_EQUAL(edge2_1->rot_next() == edge1_1, true);
+  point_data<T> point1(0, 0);
+  point_data<T> point2(0, 4);
+  point_data<T> point3(2, 1);
+  std::vector< point_data<T> > points;
+  points.push_back(point1);
+  points.push_back(point2);
+  points.push_back(point3);
+  vd_type test_output;
+  construct_voronoi(points.begin(), points.end(), &test_output);
+  VERIFY_OUTPUT(test_output);
+  CHECK_OUTPUT_SIZE(test_output, 3, 1, 3);
+
+  const_vertex_iterator it = test_output.vertices().begin();
+  BOOST_CHECK_EQUAL(it->vertex().x() == static_cast<coordinate_type>(0.25) &&
+                    it->vertex().y() == static_cast<coordinate_type>(2.0), true);
+
+  const voronoi_edge_type *edge1_1 = it->incident_edge();
+  const voronoi_edge_type *edge1_2 = edge1_1->twin();
+  CHECK_EQUAL_POINTS(edge1_1->cell()->point0(), point2);
+  CHECK_EQUAL_POINTS(edge1_2->cell()->point0(), point3);
+
+  const voronoi_edge_type *edge2_1 = edge1_1->rot_prev();
+  const voronoi_edge_type *edge2_2 = edge2_1->twin();
+  CHECK_EQUAL_POINTS(edge2_1->cell()->point0(), point3);
+  CHECK_EQUAL_POINTS(edge2_2->cell()->point0(), point1);
+
+  const voronoi_edge_type *edge3_1 = edge2_1->rot_prev();
+  const voronoi_edge_type *edge3_2 = edge3_1->twin();
+  CHECK_EQUAL_POINTS(edge3_1->cell()->point0(), point1);
+  CHECK_EQUAL_POINTS(edge3_2->cell()->point0(), point2);
+
+  BOOST_CHECK_EQUAL(edge1_2->twin() == edge1_1, true);
+  BOOST_CHECK_EQUAL(edge2_2->twin() == edge2_1, true);
+  BOOST_CHECK_EQUAL(edge3_2->twin() == edge3_1, true);
+
+  BOOST_CHECK_EQUAL(edge1_1->prev() == edge3_2 && edge1_1->next() == edge3_2, true);
+  BOOST_CHECK_EQUAL(edge2_1->prev() == edge1_2 && edge2_1->next() == edge1_2, true);
+  BOOST_CHECK_EQUAL(edge3_1->prev() == edge2_2 && edge3_1->next() == edge2_2, true);
+
+  BOOST_CHECK_EQUAL(edge1_2->next() == edge2_1 && edge1_2->prev() == edge2_1, true);
+  BOOST_CHECK_EQUAL(edge2_2->next() == edge3_1 && edge2_2->prev() == edge3_1, true);
+  BOOST_CHECK_EQUAL(edge3_2->next() == edge1_1 && edge3_2->prev() == edge1_1, true);
+
+  BOOST_CHECK_EQUAL(edge1_1->rot_next() == edge3_1, true);
+  BOOST_CHECK_EQUAL(edge3_1->rot_next() == edge2_1, true);
+  BOOST_CHECK_EQUAL(edge2_1->rot_next() == edge1_1, true);
 }
 
 // Sites: (0, 1), (2, 0), (2, 4).
 BOOST_AUTO_TEST_CASE_TEMPLATE(triangle_test2, T, test_types) {
-    point_data<T> point1(0, 1);
-    point_data<T> point2(2, 0);
-    point_data<T> point3(2, 4);
-    std::vector< point_data<T> > points;
-    points.push_back(point1);
-    points.push_back(point2);
-    points.push_back(point3);
-    vd_type test_output;
-    construct_voronoi(points.begin(), points.end(), &test_output);
-    VERIFY_OUTPUT(test_output);
-    CHECK_OUTPUT_SIZE(test_output, 3, 1, 3);
-
-    const_vertex_iterator it = test_output.vertices().begin();
-    BOOST_CHECK_EQUAL(it->vertex().x() == static_cast<coordinate_type>(1.75) &&
-                      it->vertex().y() == static_cast<coordinate_type>(2.0), true);
-
-    const voronoi_edge_type *edge1_1 = it->incident_edge();
-    const voronoi_edge_type *edge1_2 = edge1_1->twin();
-    CHECK_EQUAL_POINTS(edge1_1->cell()->point0(), point3);
-    CHECK_EQUAL_POINTS(edge1_2->cell()->point0(), point2);
-
-    const voronoi_edge_type *edge2_1 = edge1_1->rot_prev();
-    const voronoi_edge_type *edge2_2 = edge2_1->twin();
-    CHECK_EQUAL_POINTS(edge2_1->cell()->point0(), point2);
-    CHECK_EQUAL_POINTS(edge2_2->cell()->point0(), point1);
-
-    const voronoi_edge_type *edge3_1 = edge2_1->rot_prev();
-    const voronoi_edge_type *edge3_2 = edge3_1->twin();
-    CHECK_EQUAL_POINTS(edge3_1->cell()->point0(), point1);
-    CHECK_EQUAL_POINTS(edge3_2->cell()->point0(), point3);
-
-    BOOST_CHECK_EQUAL(edge1_2->twin() == edge1_1, true);
-    BOOST_CHECK_EQUAL(edge2_2->twin() == edge2_1, true);
-    BOOST_CHECK_EQUAL(edge3_2->twin() == edge3_1, true);
-
-    BOOST_CHECK_EQUAL(edge1_1->prev() == edge3_2 && edge1_1->next() == edge3_2, true);
-    BOOST_CHECK_EQUAL(edge2_1->prev() == edge1_2 && edge2_1->next() == edge1_2, true);
-    BOOST_CHECK_EQUAL(edge3_1->prev() == edge2_2 && edge3_1->next() == edge2_2, true);
-
-    BOOST_CHECK_EQUAL(edge1_2->next() == edge2_1 && edge1_2->prev() == edge2_1, true);
-    BOOST_CHECK_EQUAL(edge2_2->next() == edge3_1 && edge2_2->prev() == edge3_1, true);
-    BOOST_CHECK_EQUAL(edge3_2->next() == edge1_1 && edge3_2->prev() == edge1_1, true);
-
-    BOOST_CHECK_EQUAL(edge1_1->rot_next() == edge3_1, true);
-    BOOST_CHECK_EQUAL(edge3_1->rot_next() == edge2_1, true);
-    BOOST_CHECK_EQUAL(edge2_1->rot_next() == edge1_1, true);
+  point_data<T> point1(0, 1);
+  point_data<T> point2(2, 0);
+  point_data<T> point3(2, 4);
+  std::vector< point_data<T> > points;
+  points.push_back(point1);
+  points.push_back(point2);
+  points.push_back(point3);
+  vd_type test_output;
+  construct_voronoi(points.begin(), points.end(), &test_output);
+  VERIFY_OUTPUT(test_output);
+  CHECK_OUTPUT_SIZE(test_output, 3, 1, 3);
+
+  const_vertex_iterator it = test_output.vertices().begin();
+  BOOST_CHECK_EQUAL(it->vertex().x() == static_cast<coordinate_type>(1.75) &&
+                    it->vertex().y() == static_cast<coordinate_type>(2.0), true);
+
+  const voronoi_edge_type *edge1_1 = it->incident_edge();
+  const voronoi_edge_type *edge1_2 = edge1_1->twin();
+  CHECK_EQUAL_POINTS(edge1_1->cell()->point0(), point3);
+  CHECK_EQUAL_POINTS(edge1_2->cell()->point0(), point2);
+
+  const voronoi_edge_type *edge2_1 = edge1_1->rot_prev();
+  const voronoi_edge_type *edge2_2 = edge2_1->twin();
+  CHECK_EQUAL_POINTS(edge2_1->cell()->point0(), point2);
+  CHECK_EQUAL_POINTS(edge2_2->cell()->point0(), point1);
+
+  const voronoi_edge_type *edge3_1 = edge2_1->rot_prev();
+  const voronoi_edge_type *edge3_2 = edge3_1->twin();
+  CHECK_EQUAL_POINTS(edge3_1->cell()->point0(), point1);
+  CHECK_EQUAL_POINTS(edge3_2->cell()->point0(), point3);
+
+  BOOST_CHECK_EQUAL(edge1_2->twin() == edge1_1, true);
+  BOOST_CHECK_EQUAL(edge2_2->twin() == edge2_1, true);
+  BOOST_CHECK_EQUAL(edge3_2->twin() == edge3_1, true);
+
+  BOOST_CHECK_EQUAL(edge1_1->prev() == edge3_2 && edge1_1->next() == edge3_2, true);
+  BOOST_CHECK_EQUAL(edge2_1->prev() == edge1_2 && edge2_1->next() == edge1_2, true);
+  BOOST_CHECK_EQUAL(edge3_1->prev() == edge2_2 && edge3_1->next() == edge2_2, true);
+
+  BOOST_CHECK_EQUAL(edge1_2->next() == edge2_1 && edge1_2->prev() == edge2_1, true);
+  BOOST_CHECK_EQUAL(edge2_2->next() == edge3_1 && edge2_2->prev() == edge3_1, true);
+  BOOST_CHECK_EQUAL(edge3_2->next() == edge1_1 && edge3_2->prev() == edge1_1, true);
+
+  BOOST_CHECK_EQUAL(edge1_1->rot_next() == edge3_1, true);
+  BOOST_CHECK_EQUAL(edge3_1->rot_next() == edge2_1, true);
+  BOOST_CHECK_EQUAL(edge2_1->rot_next() == edge1_1, true);
 }
 
 // Sites: (0, 0), (0, 1), (1, 0), (1, 1).
 BOOST_AUTO_TEST_CASE_TEMPLATE(square_test1, T, test_types) {
-    point_data<T> point1(0, 0);
-    point_data<T> point2(0, 1);
-    point_data<T> point3(1, 0);
-    point_data<T> point4(1, 1);
-    std::vector< point_data<T> > points;
-    points.push_back(point1);
-    points.push_back(point2);
-    points.push_back(point3);
-    points.push_back(point4);
-    vd_type test_output;
-    construct_voronoi(points.begin(), points.end(), &test_output);
-    VERIFY_OUTPUT(test_output);
-    CHECK_OUTPUT_SIZE(test_output, 4, 1, 4);
-
-    // Check voronoi vertex.
-    const_vertex_iterator it = test_output.vertices().begin();
-    BOOST_CHECK_EQUAL(it->vertex().x() == static_cast<coordinate_type>(0.5) &&
-                      it->vertex().y() == static_cast<coordinate_type>(0.5), true);
-
-    // Check voronoi edges.
-    const voronoi_edge_type *edge1_1 = it->incident_edge();
-    const voronoi_edge_type *edge1_2 = edge1_1->twin();
-    CHECK_EQUAL_POINTS(edge1_1->cell()->point0(), points[3]);
-    CHECK_EQUAL_POINTS(edge1_2->cell()->point0(), points[2]);
-
-    const voronoi_edge_type *edge2_1 = edge1_1->rot_prev();
-    const voronoi_edge_type *edge2_2 = edge2_1->twin();
-    CHECK_EQUAL_POINTS(edge2_1->cell()->point0(), points[2]);
-    CHECK_EQUAL_POINTS(edge2_2->cell()->point0(), points[0]);
-
-    const voronoi_edge_type *edge3_1 = edge2_1->rot_prev();
-    const voronoi_edge_type *edge3_2 = edge3_1->twin();
-    CHECK_EQUAL_POINTS(edge3_1->cell()->point0(), points[0]);
-    CHECK_EQUAL_POINTS(edge3_2->cell()->point0(), points[1]);
-
-    const voronoi_edge_type *edge4_1 = edge3_1->rot_prev();
-    const voronoi_edge_type *edge4_2 = edge4_1->twin();
-    CHECK_EQUAL_POINTS(edge4_1->cell()->point0(), points[1]);
-    CHECK_EQUAL_POINTS(edge4_2->cell()->point0(), points[3]);
-
-    BOOST_CHECK_EQUAL(edge1_2->twin() == edge1_1, true);
-    BOOST_CHECK_EQUAL(edge2_2->twin() == edge2_1, true);
-    BOOST_CHECK_EQUAL(edge3_2->twin() == edge3_1, true);
-    BOOST_CHECK_EQUAL(edge4_2->twin() == edge4_1, true);
-
-    BOOST_CHECK_EQUAL(edge1_1->prev() == edge4_2 && edge1_1->next() == edge4_2, true);
-    BOOST_CHECK_EQUAL(edge2_1->prev() == edge1_2 && edge2_1->next() == edge1_2, true);
-    BOOST_CHECK_EQUAL(edge3_1->prev() == edge2_2 && edge3_1->next() == edge2_2, true);
-    BOOST_CHECK_EQUAL(edge4_1->prev() == edge3_2 && edge4_1->next() == edge3_2, true);
-
-    BOOST_CHECK_EQUAL(edge1_2->next() == edge2_1 && edge1_2->prev() == edge2_1, true);
-    BOOST_CHECK_EQUAL(edge2_2->next() == edge3_1 && edge2_2->prev() == edge3_1, true);
-    BOOST_CHECK_EQUAL(edge3_2->next() == edge4_1 && edge3_2->prev() == edge4_1, true);
-    BOOST_CHECK_EQUAL(edge4_2->next() == edge1_1 && edge4_2->prev() == edge1_1, true);
-
-    BOOST_CHECK_EQUAL(edge1_1->rot_next() == edge4_1, true);
-    BOOST_CHECK_EQUAL(edge4_1->rot_next() == edge3_1, true);
-    BOOST_CHECK_EQUAL(edge3_1->rot_next() == edge2_1, true);
-    BOOST_CHECK_EQUAL(edge2_1->rot_next() == edge1_1, true);
+  point_data<T> point1(0, 0);
+  point_data<T> point2(0, 1);
+  point_data<T> point3(1, 0);
+  point_data<T> point4(1, 1);
+  std::vector< point_data<T> > points;
+  points.push_back(point1);
+  points.push_back(point2);
+  points.push_back(point3);
+  points.push_back(point4);
+  vd_type test_output;
+  construct_voronoi(points.begin(), points.end(), &test_output);
+  VERIFY_OUTPUT(test_output);
+  CHECK_OUTPUT_SIZE(test_output, 4, 1, 4);
+
+  // Check voronoi vertex.
+  const_vertex_iterator it = test_output.vertices().begin();
+  BOOST_CHECK_EQUAL(it->vertex().x() == static_cast<coordinate_type>(0.5) &&
+                    it->vertex().y() == static_cast<coordinate_type>(0.5), true);
+
+  // Check voronoi edges.
+  const voronoi_edge_type *edge1_1 = it->incident_edge();
+  const voronoi_edge_type *edge1_2 = edge1_1->twin();
+  CHECK_EQUAL_POINTS(edge1_1->cell()->point0(), points[3]);
+  CHECK_EQUAL_POINTS(edge1_2->cell()->point0(), points[2]);
+
+  const voronoi_edge_type *edge2_1 = edge1_1->rot_prev();
+  const voronoi_edge_type *edge2_2 = edge2_1->twin();
+  CHECK_EQUAL_POINTS(edge2_1->cell()->point0(), points[2]);
+  CHECK_EQUAL_POINTS(edge2_2->cell()->point0(), points[0]);
+
+  const voronoi_edge_type *edge3_1 = edge2_1->rot_prev();
+  const voronoi_edge_type *edge3_2 = edge3_1->twin();
+  CHECK_EQUAL_POINTS(edge3_1->cell()->point0(), points[0]);
+  CHECK_EQUAL_POINTS(edge3_2->cell()->point0(), points[1]);
+
+  const voronoi_edge_type *edge4_1 = edge3_1->rot_prev();
+  const voronoi_edge_type *edge4_2 = edge4_1->twin();
+  CHECK_EQUAL_POINTS(edge4_1->cell()->point0(), points[1]);
+  CHECK_EQUAL_POINTS(edge4_2->cell()->point0(), points[3]);
+
+  BOOST_CHECK_EQUAL(edge1_2->twin() == edge1_1, true);
+  BOOST_CHECK_EQUAL(edge2_2->twin() == edge2_1, true);
+  BOOST_CHECK_EQUAL(edge3_2->twin() == edge3_1, true);
+  BOOST_CHECK_EQUAL(edge4_2->twin() == edge4_1, true);
+
+  BOOST_CHECK_EQUAL(edge1_1->prev() == edge4_2 && edge1_1->next() == edge4_2, true);
+  BOOST_CHECK_EQUAL(edge2_1->prev() == edge1_2 && edge2_1->next() == edge1_2, true);
+  BOOST_CHECK_EQUAL(edge3_1->prev() == edge2_2 && edge3_1->next() == edge2_2, true);
+  BOOST_CHECK_EQUAL(edge4_1->prev() == edge3_2 && edge4_1->next() == edge3_2, true);
+
+  BOOST_CHECK_EQUAL(edge1_2->next() == edge2_1 && edge1_2->prev() == edge2_1, true);
+  BOOST_CHECK_EQUAL(edge2_2->next() == edge3_1 && edge2_2->prev() == edge3_1, true);
+  BOOST_CHECK_EQUAL(edge3_2->next() == edge4_1 && edge3_2->prev() == edge4_1, true);
+  BOOST_CHECK_EQUAL(edge4_2->next() == edge1_1 && edge4_2->prev() == edge1_1, true);
+
+  BOOST_CHECK_EQUAL(edge1_1->rot_next() == edge4_1, true);
+  BOOST_CHECK_EQUAL(edge4_1->rot_next() == edge3_1, true);
+  BOOST_CHECK_EQUAL(edge3_1->rot_next() == edge2_1, true);
+  BOOST_CHECK_EQUAL(edge2_1->rot_next() == edge1_1, true);
 }
 
 #ifdef NDEBUG
 BOOST_AUTO_TEST_CASE_TEMPLATE(grid_test, T, test_types) {
-    vd_type test_output_small, test_output_large;
-    std::vector< point_data<T> > point_vec_small, point_vec_large;
-    int grid_size[4] = {10, 33, 101, 163};
-    int max_value[4] = {10, 33, 101, 163};
-    int array_length = sizeof(grid_size) / sizeof(int);
-    for (int k = 0; k < array_length; k++) {
-        test_output_small.clear();
-        test_output_large.clear();
-        point_vec_small.clear();
-        point_vec_large.clear();
-        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(point_data<T>(i, j));
-                point_vec_large.push_back(point_data<T>(koef * i, koef * j));
-            }
-        construct_voronoi(point_vec_small.begin(), point_vec_small.end(), &test_output_small);
-        construct_voronoi(point_vec_large.begin(), point_vec_large.end(), &test_output_large);
-        VERIFY_OUTPUT(test_output_small);
-        VERIFY_OUTPUT(test_output_large);
-        unsigned int num_cells = grid_size[k] * grid_size[k];
-        unsigned int num_vertices = num_cells - 2 * grid_size[k] + 1;
-        unsigned int num_edges = 2 * num_cells - 2 * grid_size[k];
-        CHECK_OUTPUT_SIZE(test_output_small, num_cells, num_vertices, num_edges);
-        CHECK_OUTPUT_SIZE(test_output_large, num_cells, num_vertices, num_edges);
-    }
+  vd_type test_output_small, test_output_large;
+  std::vector< point_data<T> > point_vec_small, point_vec_large;
+  int grid_size[4] = {10, 33, 101, 163};
+  int max_value[4] = {10, 33, 101, 163};
+  int array_length = sizeof(grid_size) / sizeof(int);
+  for (int k = 0; k < array_length; k++) {
+    test_output_small.clear();
+    test_output_large.clear();
+    point_vec_small.clear();
+    point_vec_large.clear();
+    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(point_data<T>(i, j));
+        point_vec_large.push_back(point_data<T>(koef * i, koef * j));
+      }
+    construct_voronoi(point_vec_small.begin(), point_vec_small.end(), &test_output_small);
+    construct_voronoi(point_vec_large.begin(), point_vec_large.end(), &test_output_large);
+    VERIFY_OUTPUT(test_output_small);
+    VERIFY_OUTPUT(test_output_large);
+    unsigned int num_cells = grid_size[k] * grid_size[k];
+    unsigned int num_vertices = num_cells - 2 * grid_size[k] + 1;
+    unsigned int num_edges = 2 * num_cells - 2 * grid_size[k];
+    CHECK_OUTPUT_SIZE(test_output_small, num_cells, num_vertices, num_edges);
+    CHECK_OUTPUT_SIZE(test_output_large, num_cells, num_vertices, num_edges);
+  }
 }
 #endif
 
 #ifdef NDEBUG
 BOOST_AUTO_TEST_CASE_TEMPLATE(random_test, T, test_types) {
-    boost::mt19937 gen(static_cast<unsigned int>(time(NULL)));
-    vd_type test_output_small, test_output_large;
-    std::vector< point_data<T> > point_vec_small, point_vec_large;
-    int num_points[] = {5, 100, 1000, 10000, 100000};
-    int num_runs[] = {10000, 1000, 100, 10, 1};
-    int mod_koef[] = {10, 100, 100, 1000, 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++) {
-            test_output_small.clear();
-            test_output_large.clear();
-            point_vec_small.clear();
-            point_vec_large.clear();
-            for (int j = 0; j < num_points[k]; j++) {
-                T x = gen() % mod_koef[k] - mod_koef[k] / 2;
-                T y = gen() % mod_koef[k] - mod_koef[k] / 2;
-                point_vec_small.push_back(point_data<T>(x, y));
-                point_vec_large.push_back(point_data<T>(koef * x, koef * y));
-            }
-            construct_voronoi(point_vec_small.begin(), point_vec_small.end(), &test_output_small);
-            construct_voronoi(point_vec_large.begin(), point_vec_large.end(), &test_output_large);
-            VERIFY_OUTPUT(test_output_small);
-            VERIFY_OUTPUT(test_output_large);
-            BOOST_CHECK_EQUAL(test_output_small.num_cells(),
-                              test_output_large.num_cells());
-            BOOST_CHECK_EQUAL(test_output_small.num_vertices(),
-                              test_output_large.num_vertices());
-            BOOST_CHECK_EQUAL(test_output_small.num_edges(),
-                              test_output_large.num_edges());
-        }
+  boost::mt19937 gen(static_cast<unsigned int>(time(NULL)));
+  vd_type test_output_small, test_output_large;
+  std::vector< point_data<T> > point_vec_small, point_vec_large;
+  int num_points[] = {5, 100, 1000, 10000, 100000};
+  int num_runs[] = {10000, 1000, 100, 10, 1};
+  int mod_koef[] = {10, 100, 100, 1000, 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++) {
+      test_output_small.clear();
+      test_output_large.clear();
+      point_vec_small.clear();
+      point_vec_large.clear();
+      for (int j = 0; j < num_points[k]; j++) {
+        T x = gen() % mod_koef[k] - mod_koef[k] / 2;
+        T y = gen() % mod_koef[k] - mod_koef[k] / 2;
+        point_vec_small.push_back(point_data<T>(x, y));
+        point_vec_large.push_back(point_data<T>(koef * x, koef * y));
+      }
+      construct_voronoi(point_vec_small.begin(), point_vec_small.end(), &test_output_small);
+      construct_voronoi(point_vec_large.begin(), point_vec_large.end(), &test_output_large);
+      VERIFY_OUTPUT(test_output_small);
+      VERIFY_OUTPUT(test_output_large);
+      BOOST_CHECK_EQUAL(test_output_small.num_cells(), test_output_large.num_cells());
+      BOOST_CHECK_EQUAL(test_output_small.num_vertices(), test_output_large.num_vertices());
+      BOOST_CHECK_EQUAL(test_output_small.num_edges(), test_output_large.num_edges());
     }
+  }
 }
 #endif
 
 #ifdef NDEBUG
 BOOST_AUTO_TEST_CASE_TEMPLATE(enormous_random_test, T, test_types) {
-    boost::mt19937 gen(static_cast<unsigned int>(time(NULL)));
-    vd_type test_output;
-    std::vector< point_data<T> > point_vec;
-    for (int i = 0; i < 1000000; i++)
-        point_vec.push_back(point_data<T>(gen() % 10000 - 5000, gen() % 10000 - 5000));
-    construct_voronoi(point_vec.begin(), point_vec.end(), &test_output);
-    BOOST_CHECK_EQUAL(voronoi_test_helper::verify_output(test_output,
-        voronoi_test_helper::FAST_VERIFICATION), true);
+  boost::mt19937 gen(static_cast<unsigned int>(time(NULL)));
+  vd_type test_output;
+  std::vector< point_data<T> > point_vec;
+  for (int i = 0; i < 1000000; i++)
+    point_vec.push_back(point_data<T>(gen() % 10000 - 5000, gen() % 10000 - 5000));
+  construct_voronoi(point_vec.begin(), point_vec.end(), &test_output);
+  BOOST_CHECK_EQUAL(voronoi_test_helper::verify_output(test_output,
+      voronoi_test_helper::FAST_VERIFICATION), true);
 }
 #endif
 
 BOOST_AUTO_TEST_CASE_TEMPLATE(segment_sites_test1, T, test_types) {
-    vd_type test_output;
-    segment_set_data<T> segments;
-    point_data<T> point1(0, 0);
-    point_data<T> point2(1, 1);
-    segments.insert(segment_data<T>(point1, point2));
-    construct_voronoi(segments.begin(), segments.end(), &test_output);
-    CHECK_OUTPUT_SIZE(test_output, 3, 0, 2);
-    VERIFY_NO_HALF_EDGE_INTERSECTIONS(test_output);
+  vd_type test_output;
+  std::vector< segment_data<T> > segments;
+  point_data<T> point1(0, 0);
+  point_data<T> point2(1, 1);
+  segments.push_back(segment_data<T>(point1, point2));
+  construct_voronoi(segments.begin(), segments.end(), &test_output);
+  CHECK_OUTPUT_SIZE(test_output, 3, 0, 2);
+  VERIFY_NO_HALF_EDGE_INTERSECTIONS(test_output);
 }
 
 BOOST_AUTO_TEST_CASE_TEMPLATE(segment_sites_test2, T, test_types) {
-    vd_type test_output;
-    std::vector< point_data<T> > points;
-    segment_set_data<T> segments;
-    point_data<T> point1(0, 0);
-    point_data<T> point2(4, 4);
-    point_data<T> point3(3, 1);
-    point_data<T> point4(1, 3);
-    segments.insert(segment_data<T>(point1, point2));
-    points.push_back(point3);
-    points.push_back(point4);
-    construct_voronoi(points.begin(), points.end(), segments.begin(), segments.end(), &test_output);
-    CHECK_OUTPUT_SIZE(test_output, 5, 4, 8);
-    VERIFY_NO_HALF_EDGE_INTERSECTIONS(test_output);
+  vd_type test_output;
+  std::vector< point_data<T> > points;
+  std::vector< segment_data<T> > segments;
+  point_data<T> point1(0, 0);
+  point_data<T> point2(4, 4);
+  point_data<T> point3(3, 1);
+  point_data<T> point4(1, 3);
+  segments.push_back(segment_data<T>(point1, point2));
+  points.push_back(point3);
+  points.push_back(point4);
+  construct_voronoi(points.begin(), points.end(), segments.begin(), segments.end(), &test_output);
+  CHECK_OUTPUT_SIZE(test_output, 5, 4, 8);
+  VERIFY_NO_HALF_EDGE_INTERSECTIONS(test_output);
 }
 
 BOOST_AUTO_TEST_CASE_TEMPLATE(segment_sites_test3, T, test_types) {
-    vd_type test_output;
-    std::vector< point_data<T> > points;
-    segment_set_data<T> segments;
-    point_data<T> point1(4, 0);
-    point_data<T> point2(0, 4);
-    point_data<T> point3(3, 3);
-    point_data<T> point4(1, 1);
-    segments.insert(segment_data<T>(point1, point2));
-    points.push_back(point3);
-    points.push_back(point4);
-    construct_voronoi(points.begin(), points.end(), segments.begin(), segments.end(), &test_output);
-    CHECK_OUTPUT_SIZE(test_output, 5, 4, 8);
-    VERIFY_NO_HALF_EDGE_INTERSECTIONS(test_output);
+  vd_type test_output;
+  std::vector< point_data<T> > points;
+  std::vector< segment_data<T> > segments;
+  point_data<T> point1(4, 0);
+  point_data<T> point2(0, 4);
+  point_data<T> point3(3, 3);
+  point_data<T> point4(1, 1);
+  segments.push_back(segment_data<T>(point1, point2));
+  points.push_back(point3);
+  points.push_back(point4);
+  construct_voronoi(points.begin(), points.end(), segments.begin(), segments.end(), &test_output);
+  CHECK_OUTPUT_SIZE(test_output, 5, 4, 8);
+  VERIFY_NO_HALF_EDGE_INTERSECTIONS(test_output);
 }
 
 BOOST_AUTO_TEST_CASE_TEMPLATE(segment_sites_test4, T, test_types) {
-    vd_type test_output;
-    std::vector< point_data<T> > points;
-    segment_set_data<T> segments;
-    point_data<T> point1(4, 0);
-    point_data<T> point2(0, 4);
-    point_data<T> point3(3, 2);
-    point_data<T> point4(2, 3);
-    segments.insert(segment_data<T>(point1, point2));
-    points.push_back(point3);
-    points.push_back(point4);
-    construct_voronoi(points.begin(), points.end(), segments.begin(), segments.end(), &test_output);
-    CHECK_OUTPUT_SIZE(test_output, 5, 3, 7);
-    VERIFY_NO_HALF_EDGE_INTERSECTIONS(test_output);
+  vd_type test_output;
+  std::vector< point_data<T> > points;
+  std::vector< segment_data<T> > segments;
+  point_data<T> point1(4, 0);
+  point_data<T> point2(0, 4);
+  point_data<T> point3(3, 2);
+  point_data<T> point4(2, 3);
+  segments.push_back(segment_data<T>(point1, point2));
+  points.push_back(point3);
+  points.push_back(point4);
+  construct_voronoi(points.begin(), points.end(), segments.begin(), segments.end(), &test_output);
+  CHECK_OUTPUT_SIZE(test_output, 5, 3, 7);
+  VERIFY_NO_HALF_EDGE_INTERSECTIONS(test_output);
 }
 
 BOOST_AUTO_TEST_CASE_TEMPLATE(segment_site_test5, T, test_types) {
-    vd_type test_output;
-    std::vector< point_data<T> > points;
-    segment_set_data<T> segments;
-    point_data<T> point1(0, 0);
-    point_data<T> point2(0, 8);
-    point_data<T> point3(-2, -2);
-    point_data<T> point4(-2, 4);
-    point_data<T> point5(-2, 10);
-    segments.insert(segment_data<T>(point1, point2));
-    points.push_back(point3);
-    points.push_back(point4);
-    points.push_back(point5);
-    construct_voronoi(points.begin(), points.end(), segments.begin(), segments.end(), &test_output);
-    CHECK_OUTPUT_SIZE(test_output, 6, 4, 9);
-    VERIFY_NO_HALF_EDGE_INTERSECTIONS(test_output);
+  vd_type test_output;
+  std::vector< point_data<T> > points;
+  std::vector< segment_data<T> > segments;
+  point_data<T> point1(0, 0);
+  point_data<T> point2(0, 8);
+  point_data<T> point3(-2, -2);
+  point_data<T> point4(-2, 4);
+  point_data<T> point5(-2, 10);
+  segments.push_back(segment_data<T>(point1, point2));
+  points.push_back(point3);
+  points.push_back(point4);
+  points.push_back(point5);
+  construct_voronoi(points.begin(), points.end(), segments.begin(), segments.end(), &test_output);
+  CHECK_OUTPUT_SIZE(test_output, 6, 4, 9);
+  VERIFY_NO_HALF_EDGE_INTERSECTIONS(test_output);
 }
 
 BOOST_AUTO_TEST_CASE_TEMPLATE(segment_site_test6, T, test_types) {
-    vd_type test_output;
-    std::vector< point_data<T> > points;
-    segment_set_data<T> segments;
-    point_data<T> point1(-1, 1);
-    point_data<T> point2(1, 0);
-    point_data<T> point3(1, 2);
-    segments.insert(segment_data<T>(point2, point3));
-    points.push_back(point1);
-    construct_voronoi(points.begin(), points.end(), segments.begin(), segments.end(), &test_output);
-    CHECK_OUTPUT_SIZE(test_output, 4, 2, 5);
-    VERIFY_NO_HALF_EDGE_INTERSECTIONS(test_output);
+  vd_type test_output;
+  std::vector< point_data<T> > points;
+  std::vector< segment_data<T> > segments;
+  point_data<T> point1(-1, 1);
+  point_data<T> point2(1, 0);
+  point_data<T> point3(1, 2);
+  segments.push_back(segment_data<T>(point2, point3));
+  points.push_back(point1);
+  construct_voronoi(points.begin(), points.end(), segments.begin(), segments.end(), &test_output);
+  CHECK_OUTPUT_SIZE(test_output, 4, 2, 5);
+  VERIFY_NO_HALF_EDGE_INTERSECTIONS(test_output);
 }
 
 BOOST_AUTO_TEST_CASE_TEMPLATE(segment_site_test7, T, test_types) {
-    vd_type test_output;
-    segment_set_data<T> segments;
-    point_data<T> point1(0, 0);
-    point_data<T> point2(4, 0);
-    point_data<T> point3(0, 4);
-    point_data<T> point4(4, 4);
-    segments.insert(segment_data<T>(point1, point2));
-    segments.insert(segment_data<T>(point2, point3));
-    segments.insert(segment_data<T>(point3, point4));
-    construct_voronoi(segments.begin(), segments.end(), &test_output);
-    CHECK_OUTPUT_SIZE(test_output, 7, 6, 12);
-    VERIFY_NO_HALF_EDGE_INTERSECTIONS(test_output);
+  vd_type test_output;
+  std::vector< segment_data<T> > segments;
+  point_data<T> point1(0, 0);
+  point_data<T> point2(4, 0);
+  point_data<T> point3(0, 4);
+  point_data<T> point4(4, 4);
+  segments.push_back(segment_data<T>(point1, point2));
+  segments.push_back(segment_data<T>(point2, point3));
+  segments.push_back(segment_data<T>(point3, point4));
+  construct_voronoi(segments.begin(), segments.end(), &test_output);
+  CHECK_OUTPUT_SIZE(test_output, 7, 6, 12);
+  VERIFY_NO_HALF_EDGE_INTERSECTIONS(test_output);
 }
 
 BOOST_AUTO_TEST_CASE_TEMPLATE(segment_site_test8, T, test_types) {
-    vd_type test_output;
-    segment_set_data<T> segments;
-    point_data<T> point1(0, 0);
-    point_data<T> point2(4, 0);
-    point_data<T> point3(4, 4);
-    point_data<T> point4(0, 4);
-    segments.insert(segment_data<T>(point1, point2));
-    segments.insert(segment_data<T>(point2, point3));
-    segments.insert(segment_data<T>(point3, point4));
-    segments.insert(segment_data<T>(point4, point1));
-    construct_voronoi(segments.begin(), segments.end(), &test_output);
-    CHECK_OUTPUT_SIZE(test_output, 8, 5, 12);
-    VERIFY_NO_HALF_EDGE_INTERSECTIONS(test_output);
+  vd_type test_output;
+  std::vector< segment_data<T> > segments;
+  point_data<T> point1(0, 0);
+  point_data<T> point2(4, 0);
+  point_data<T> point3(4, 4);
+  point_data<T> point4(0, 4);
+  segments.push_back(segment_data<T>(point1, point2));
+  segments.push_back(segment_data<T>(point2, point3));
+  segments.push_back(segment_data<T>(point3, point4));
+  segments.push_back(segment_data<T>(point4, point1));
+  construct_voronoi(segments.begin(), segments.end(), &test_output);
+  CHECK_OUTPUT_SIZE(test_output, 8, 5, 12);
+  VERIFY_NO_HALF_EDGE_INTERSECTIONS(test_output);
 }
 
 #ifdef NDEBUG
 BOOST_AUTO_TEST_CASE_TEMPLATE(segment_grid_test, T, test_types) {
-    vd_type test_output_small, test_output_large;
-    segment_set_data<T> segments_small, segments_large;
-    int grid_size[] = {10, 33, 100};
-    int max_value[] = {100, 330, 1000};
-    int array_length = sizeof(grid_size) / sizeof(int);
-    for (int k = 0; k < array_length; k++) {
-        test_output_small.clear();
-        test_output_large.clear();
-        segments_small.clear();
-        segments_large.clear();
-        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_data<T> point1_1(10 * i, 10 * j);
-                point_data<T> point1_2(koef * 10 * i, koef * 10 * j);
-                point_data<T> point2_1(10 * i, 10 * j + 10);
-                point_data<T> point2_2(koef * 10 * i, koef * (10 * j + 10));
-                segments_small.insert(segment_data<T>(point1_1, point2_1));
-                segments_large.insert(segment_data<T>(point1_2, point2_2));
-                point_data<T> point3_1(10 * j, 10 * i);
-                point_data<T> point3_2(koef * 10 * j, koef * 10 * i);
-                point_data<T> point4_1(10 * j + 10, 10 * i);
-                point_data<T> point4_2(koef * (10 * j + 10), koef * 10 * i);
-                segments_small.insert(segment_data<T>(point3_1, point4_1));
-                segments_large.insert(segment_data<T>(point3_2, point4_2));
-            }
-        construct_voronoi(segments_small.begin(), segments_small.end(), &test_output_small);
-        construct_voronoi(segments_large.begin(), segments_large.end(), &test_output_large);
-        VERIFY_NO_HALF_EDGE_INTERSECTIONS(test_output_small);
-        VERIFY_NO_HALF_EDGE_INTERSECTIONS(test_output_large);
-        BOOST_CHECK_EQUAL(test_output_small.num_cells(), test_output_large.num_cells());
-        BOOST_CHECK_EQUAL(test_output_small.num_vertices(), test_output_large.num_vertices());
-        BOOST_CHECK_EQUAL(test_output_small.num_edges(), test_output_large.num_edges());
-    }
+  vd_type test_output_small, test_output_large;
+  std::vector< segment_data<T> > segments_small, segments_large;
+  int grid_size[] = {10, 33, 100};
+  int max_value[] = {100, 330, 1000};
+  int array_length = sizeof(grid_size) / sizeof(int);
+  for (int k = 0; k < array_length; k++) {
+    test_output_small.clear();
+    test_output_large.clear();
+    segments_small.clear();
+    segments_large.clear();
+    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_data<T> point1_1(10 * i, 10 * j);
+        point_data<T> point1_2(koef * 10 * i, koef * 10 * j);
+        point_data<T> point2_1(10 * i, 10 * j + 10);
+        point_data<T> point2_2(koef * 10 * i, koef * (10 * j + 10));
+        segments_small.push_back(segment_data<T>(point1_1, point2_1));
+        segments_large.push_back(segment_data<T>(point1_2, point2_2));
+        point_data<T> point3_1(10 * j, 10 * i);
+        point_data<T> point3_2(koef * 10 * j, koef * 10 * i);
+        point_data<T> point4_1(10 * j + 10, 10 * i);
+        point_data<T> point4_2(koef * (10 * j + 10), koef * 10 * i);
+        segments_small.push_back(segment_data<T>(point3_1, point4_1));
+        segments_large.push_back(segment_data<T>(point3_2, point4_2));
+      }
+    construct_voronoi(segments_small.begin(), segments_small.end(), &test_output_small);
+    construct_voronoi(segments_large.begin(), segments_large.end(), &test_output_large);
+    VERIFY_NO_HALF_EDGE_INTERSECTIONS(test_output_small);
+    VERIFY_NO_HALF_EDGE_INTERSECTIONS(test_output_large);
+    BOOST_CHECK_EQUAL(test_output_small.num_cells(), test_output_large.num_cells());
+    BOOST_CHECK_EQUAL(test_output_small.num_vertices(), test_output_large.num_vertices());
+    BOOST_CHECK_EQUAL(test_output_small.num_edges(), test_output_large.num_edges());
+  }
 }
 #endif
 
 #ifdef NDEBUG
 BOOST_AUTO_TEST_CASE_TEMPLATE(segment_random_test1, T, test_types) {
-    boost::mt19937 gen(static_cast<unsigned int>(time(NULL)));
-    vd_type test_output;
-    std::vector< point_data<T> > points;
-    segment_set_data<T> segments;
-    int num_runs = 1000;
-    int num_segments = 10;
-    points.push_back(point_data<T>(-100, -100));
-    points.push_back(point_data<T>(-100, 100));
-    points.push_back(point_data<T>(100, -100));
-    points.push_back(point_data<T>(100, 100));
-    for (int i = 0; i < num_runs; i++) {
-        test_output.clear();
-        segments.clear();
-        for (int j = 0; j < num_segments; j++) {
-            T x1 = 0, y1 = 0, x2 = 0, y2 = 0;
-            while (x1 == x2 && y1 == y2) {
-                x1 = (gen() % 100) - 50;
-                y1 = (gen() % 100) - 50;
-                x2 = (gen() % 100) - 50;
-                y2 = (gen() % 100) - 50;
-            }
-            point_data<T> point1(x1, y1);
-            point_data<T> point2(x2, y2);
-            segments.insert(segment_data<T>(point1, point2));
-        }
-        segments.clean();
-        construct_voronoi(points.begin(), points.end(), segments.begin(), segments.end(), &test_output);
-        VERIFY_NO_HALF_EDGE_INTERSECTIONS(test_output);
+  boost::mt19937 gen(static_cast<unsigned int>(time(NULL)));
+  vd_type test_output;
+  std::vector< point_data<T> > points;
+  std::vector< segment_data<T> > segments;
+  int num_runs = 1000;
+  int num_segments = 10;
+  points.push_back(point_data<T>(-100, -100));
+  points.push_back(point_data<T>(-100, 100));
+  points.push_back(point_data<T>(100, -100));
+  points.push_back(point_data<T>(100, 100));
+  for (int i = 0; i < num_runs; i++) {
+    test_output.clear();
+    segments.clear();
+    for (int j = 0; j < num_segments; j++) {
+      T x1 = 0, y1 = 0, x2 = 0, y2 = 0;
+      while (x1 == x2 && y1 == y2) {
+        x1 = (gen() % 100) - 50;
+        y1 = (gen() % 100) - 50;
+        x2 = (gen() % 100) - 50;
+        y2 = (gen() % 100) - 50;
+      }
+      point_data<T> point1(x1, y1);
+      point_data<T> point2(x2, y2);
+      segments.push_back(segment_data<T>(point1, point2));
     }
+    voronoi_test_helper::clean_segment_set(segments);
+    construct_voronoi(points.begin(), points.end(), segments.begin(), segments.end(), &test_output);
+    VERIFY_NO_HALF_EDGE_INTERSECTIONS(test_output);
+  }
 }
 #endif
 
 #ifdef NDEBUG
 BOOST_AUTO_TEST_CASE_TEMPLATE(segment_random_test2, T, test_types) {
-    boost::mt19937 gen(static_cast<unsigned int>(time(NULL)));
-    vd_type test_output_small, test_output_large;
-    segment_set_data<T> segments_small, segments_large;
-    int num_segments[] = {5, 25, 125, 625};
-    int num_runs[] = {1000, 100, 10, 1};
-    int mod_koef1[] = {10, 100, 200, 300};
-    int mod_koef2[] = {10, 20, 50, 100};
-    int max_value[] = {10, 60, 125, 200};
-    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++) {
-            test_output_small.clear();
-            test_output_large.clear();
-            segments_small.clear();
-            segments_large.clear();
-            for (int j = 0; j < num_segments[k]; j++) {
-                T x1 = (gen() % mod_koef1[k]) - mod_koef1[k] / 2;
-                T y1 = (gen() % mod_koef1[k]) - mod_koef1[k] / 2;
-                T dx = 0, dy = 0;
-                while (dx == 0 && dy == 0) {
-                    dx = (gen() % mod_koef2[k]) - mod_koef2[k] / 2;
-                    dy = (gen() % mod_koef2[k]) - mod_koef2[k] / 2;
-                }
-                T x2 = x1 + dx;
-                T y2 = y1 + dy;
-                point_data<T> point1_small(x1, y1);
-                point_data<T> point2_small(x2, y2);
-                segments_small.insert(segment_data<T>(point1_small, point2_small));
-            }
-            segments_small.clean();
-            for (typename segment_set_data<T>::iterator_type it = segments_small.begin();
-                 it != segments_small.end(); ++it) {
-                T x1 = it->low().x() * koef;
-                T y1 = it->low().y() * koef;
-                T x2 = it->high().x() * koef;
-                T y2 = it->high().y() * koef;
-                point_data<T> point1_large(x1, y1);
-                point_data<T> point2_large(x2, y2);
-                segments_large.insert(segment_data<T>(point1_large, point2_large));
-            }
-            construct_voronoi(segments_small.begin(), segments_small.end(), &test_output_small);
-            construct_voronoi(segments_large.begin(), segments_large.end(), &test_output_large);
-            VERIFY_NO_HALF_EDGE_INTERSECTIONS(test_output_small);
-            VERIFY_NO_HALF_EDGE_INTERSECTIONS(test_output_large);
-            BOOST_CHECK_EQUAL(test_output_small.num_cells(), test_output_large.num_cells());
-            BOOST_CHECK_EQUAL(test_output_small.num_vertices(), test_output_large.num_vertices());
-            BOOST_CHECK_EQUAL(test_output_small.num_edges(), test_output_large.num_edges());
+  boost::mt19937 gen(static_cast<unsigned int>(time(NULL)));
+  vd_type test_output_small, test_output_large;
+  std::vector< segment_data<T> > segments_small, segments_large;
+  int num_segments[] = {5, 25, 125, 625};
+  int num_runs[] = {1000, 100, 10, 1};
+  int mod_koef1[] = {10, 100, 200, 300};
+  int mod_koef2[] = {10, 20, 50, 100};
+  int max_value[] = {10, 60, 125, 200};
+  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++) {
+      test_output_small.clear();
+      test_output_large.clear();
+      segments_small.clear();
+      segments_large.clear();
+      for (int j = 0; j < num_segments[k]; j++) {
+        T x1 = (gen() % mod_koef1[k]) - mod_koef1[k] / 2;
+        T y1 = (gen() % mod_koef1[k]) - mod_koef1[k] / 2;
+        T dx = 0, dy = 0;
+        while (dx == 0 && dy == 0) {
+          dx = (gen() % mod_koef2[k]) - mod_koef2[k] / 2;
+          dy = (gen() % mod_koef2[k]) - mod_koef2[k] / 2;
         }
+        T x2 = x1 + dx;
+        T y2 = y1 + dy;
+        point_data<T> point1_small(x1, y1);
+        point_data<T> point2_small(x2, y2);
+        segments_small.push_back(segment_data<T>(point1_small, point2_small));
+      }
+      voronoi_test_helper::clean_segment_set(segments_small);
+      for (typename std::vector< segment_data<T> >::iterator it = segments_small.begin();
+           it != segments_small.end(); ++it) {
+        T x1 = it->low().x() * koef;
+        T y1 = it->low().y() * koef;
+        T x2 = it->high().x() * koef;
+        T y2 = it->high().y() * koef;
+        point_data<T> point1_large(x1, y1);
+        point_data<T> point2_large(x2, y2);
+        segments_large.push_back(segment_data<T>(point1_large, point2_large));
+      }
+      construct_voronoi(segments_small.begin(), segments_small.end(), &test_output_small);
+      construct_voronoi(segments_large.begin(), segments_large.end(), &test_output_large);
+      VERIFY_NO_HALF_EDGE_INTERSECTIONS(test_output_small);
+      VERIFY_NO_HALF_EDGE_INTERSECTIONS(test_output_large);
+      BOOST_CHECK_EQUAL(test_output_small.num_cells(), test_output_large.num_cells());
+      BOOST_CHECK_EQUAL(test_output_small.num_vertices(), test_output_large.num_vertices());
+      BOOST_CHECK_EQUAL(test_output_small.num_edges(), test_output_large.num_edges());
     }
+  }
 }
 #endif

Modified: sandbox/gtl/libs/polygon/test/voronoi_ctypes_test.cpp
==============================================================================
--- sandbox/gtl/libs/polygon/test/voronoi_ctypes_test.cpp	(original)
+++ sandbox/gtl/libs/polygon/test/voronoi_ctypes_test.cpp	2012-05-01 08:43:51 EDT (Tue, 01 May 2012)
@@ -14,305 +14,301 @@
 #include <boost/random/mersenne_twister.hpp>
 #include <boost/test/test_case_template.hpp>
 
-#include "boost/polygon/detail/voronoi_ctypes.hpp"
+#include <boost/polygon/detail/voronoi_ctypes.hpp>
 using namespace boost::polygon::detail;
 
 type_converter_fpt to_fpt;
 
 BOOST_AUTO_TEST_CASE(ulp_comparison_test1) {
-    ulp_comparison<double> ulp_cmp;
-    uint64 a = 22;
-    uint64 b = 27;
-    fpt64 da, db;
-    memcpy(&da, &a, sizeof(uint64));
-    memcpy(&db, &b, sizeof(uint64));
-    BOOST_CHECK_EQUAL(ulp_cmp(da, db, 1), ulp_cmp.LESS);
-    BOOST_CHECK_EQUAL(ulp_cmp(db, da, 1), ulp_cmp.MORE);
-    BOOST_CHECK_EQUAL(ulp_cmp(da, db, 4), ulp_cmp.LESS);
-    BOOST_CHECK_EQUAL(ulp_cmp(da, db, 5), ulp_cmp.EQUAL);
-    BOOST_CHECK_EQUAL(ulp_cmp(da, db, 6), ulp_cmp.EQUAL);
+  ulp_comparison<double> ulp_cmp;
+  uint64 a = 22;
+  uint64 b = 27;
+  fpt64 da, db;
+  memcpy(&da, &a, sizeof(uint64));
+  memcpy(&db, &b, sizeof(uint64));
+  BOOST_CHECK_EQUAL(ulp_cmp(da, db, 1), ulp_cmp.LESS);
+  BOOST_CHECK_EQUAL(ulp_cmp(db, da, 1), ulp_cmp.MORE);
+  BOOST_CHECK_EQUAL(ulp_cmp(da, db, 4), ulp_cmp.LESS);
+  BOOST_CHECK_EQUAL(ulp_cmp(da, db, 5), ulp_cmp.EQUAL);
+  BOOST_CHECK_EQUAL(ulp_cmp(da, db, 6), ulp_cmp.EQUAL);
 }
 
 BOOST_AUTO_TEST_CASE(ulp_comparison_test2) {
-    ulp_comparison<fpt64> ulp_cmp;
-    uint64 a = 0ULL;
-    uint64 b = 0x8000000000000002ULL;
-    fpt64 da, db;
-    memcpy(&da, &a, sizeof(uint64));
-    memcpy(&db, &b, sizeof(uint64));
-    BOOST_CHECK_EQUAL(ulp_cmp(da, db, 1), ulp_cmp.MORE);
-    BOOST_CHECK_EQUAL(ulp_cmp(db, da, 1), ulp_cmp.LESS);
-    BOOST_CHECK_EQUAL(ulp_cmp(da, db, 2), ulp_cmp.EQUAL);
-    BOOST_CHECK_EQUAL(ulp_cmp(da, db, 3), ulp_cmp.EQUAL);
+  ulp_comparison<fpt64> ulp_cmp;
+  uint64 a = 0ULL;
+  uint64 b = 0x8000000000000002ULL;
+  fpt64 da, db;
+  memcpy(&da, &a, sizeof(uint64));
+  memcpy(&db, &b, sizeof(uint64));
+  BOOST_CHECK_EQUAL(ulp_cmp(da, db, 1), ulp_cmp.MORE);
+  BOOST_CHECK_EQUAL(ulp_cmp(db, da, 1), ulp_cmp.LESS);
+  BOOST_CHECK_EQUAL(ulp_cmp(da, db, 2), ulp_cmp.EQUAL);
+  BOOST_CHECK_EQUAL(ulp_cmp(da, db, 3), ulp_cmp.EQUAL);
 }
 
 BOOST_AUTO_TEST_CASE(fpt_exponent_accessor_test) {
-    typedef fpt_exponent_accessor<fpt64> fpt_ea;
-    fpt64 value = 15;
-    BOOST_CHECK_EQUAL(fpt_ea::set_exponent(value, 0), 3);
-    BOOST_CHECK_EQUAL(value, 1.875);
-    value = 0.0625;
-    BOOST_CHECK_EQUAL(fpt_ea::set_exponent(value, 0), -4);
-    BOOST_CHECK_EQUAL(value, 1.0);
-    value = -1.5;
-    BOOST_CHECK_EQUAL(fpt_ea::set_exponent(value, 4), 0);
-    BOOST_CHECK_EQUAL(value, -24.0);
-    value = 0.0;
-    BOOST_CHECK_EQUAL(fpt_ea::set_exponent(value, 4), fpt_ea::kMinExponent);
-    BOOST_CHECK_EQUAL(value, 16.0);
-    value = std::pow(2.0, 2000);
-    BOOST_CHECK_EQUAL(fpt_ea::set_exponent(value, 4), fpt_ea::kMaxExponent);
-    BOOST_CHECK_EQUAL(value, 16.0);
+  typedef fpt_exponent_accessor<fpt64> fpt_ea;
+  fpt64 value = 15;
+  BOOST_CHECK_EQUAL(fpt_ea::set_exponent(value, 0), 3);
+  BOOST_CHECK_EQUAL(value, 1.875);
+  value = 0.0625;
+  BOOST_CHECK_EQUAL(fpt_ea::set_exponent(value, 0), -4);
+  BOOST_CHECK_EQUAL(value, 1.0);
+  value = -1.5;
+  BOOST_CHECK_EQUAL(fpt_ea::set_exponent(value, 4), 0);
+  BOOST_CHECK_EQUAL(value, -24.0);
+  value = 0.0;
+  BOOST_CHECK_EQUAL(fpt_ea::set_exponent(value, 4), fpt_ea::kMinExponent);
+  BOOST_CHECK_EQUAL(value, 16.0);
+  value = std::pow(2.0, 2000);
+  BOOST_CHECK_EQUAL(fpt_ea::set_exponent(value, 4), fpt_ea::kMaxExponent);
+  BOOST_CHECK_EQUAL(value, 16.0);
 }
 
 BOOST_AUTO_TEST_CASE(extended_exponent_fpt_test1) {
-    boost::mt19937_64 gen(static_cast<uint32>(time(NULL)));
-    fpt64 b = 0.0;
-    efpt64 eeb(b);
-    for (int i = 0; i < 1000; ++i) {
-        fpt64 a = to_fpt(static_cast<int64>(gen()));
-        efpt64 eea(a);
-        efpt64 neg = -eea;
-        efpt64 sum = eea + eeb;
-        efpt64 dif = eea - eeb;
-        efpt64 mul = eea * eeb;
-        BOOST_CHECK_EQUAL(to_fpt(neg), -a);
-        BOOST_CHECK_EQUAL(to_fpt(sum), a + b);
-        BOOST_CHECK_EQUAL(to_fpt(dif), a - b);
-        BOOST_CHECK_EQUAL(to_fpt(mul), a * b);
-    }
+  boost::mt19937_64 gen(static_cast<uint32>(time(NULL)));
+  fpt64 b = 0.0;
+  efpt64 eeb(b);
+  for (int i = 0; i < 1000; ++i) {
+    fpt64 a = to_fpt(static_cast<int64>(gen()));
+    efpt64 eea(a);
+    efpt64 neg = -eea;
+    efpt64 sum = eea + eeb;
+    efpt64 dif = eea - eeb;
+    efpt64 mul = eea * eeb;
+    BOOST_CHECK_EQUAL(to_fpt(neg), -a);
+    BOOST_CHECK_EQUAL(to_fpt(sum), a + b);
+    BOOST_CHECK_EQUAL(to_fpt(dif), a - b);
+    BOOST_CHECK_EQUAL(to_fpt(mul), a * b);
+  }
 }
 
 BOOST_AUTO_TEST_CASE(extended_exponent_fpt_test2) {
-    boost::mt19937_64 gen(static_cast<uint32>(time(NULL)));
-    fpt64 a = 0.0;
-    efpt64 eea(a);  
-    for (int i = 0; i < 1000; ++i) {
-        fpt64 b = to_fpt(static_cast<int64>(gen()));
-        if (b == 0.0) {
-            continue;
-        }
-        efpt64 eeb(b);
-        efpt64 neg = -eea;
-        efpt64 sum = eea + eeb;
-        efpt64 dif = eea - eeb;
-        efpt64 mul = eea * eeb;
-        efpt64 div = eea / eeb;
-        BOOST_CHECK_EQUAL(to_fpt(neg), -a);
-        BOOST_CHECK_EQUAL(to_fpt(sum), a + b);
-        BOOST_CHECK_EQUAL(to_fpt(dif), a - b);
-        BOOST_CHECK_EQUAL(to_fpt(mul), a * b);
-        BOOST_CHECK_EQUAL(to_fpt(div), a / b);
-    }
+  boost::mt19937_64 gen(static_cast<uint32>(time(NULL)));
+  fpt64 a = 0.0;
+  efpt64 eea(a);  
+  for (int i = 0; i < 1000; ++i) {
+    fpt64 b = to_fpt(static_cast<int64>(gen()));
+    if (b == 0.0)
+      continue;
+    efpt64 eeb(b);
+    efpt64 neg = -eea;
+    efpt64 sum = eea + eeb;
+    efpt64 dif = eea - eeb;
+    efpt64 mul = eea * eeb;
+    efpt64 div = eea / eeb;
+    BOOST_CHECK_EQUAL(to_fpt(neg), -a);
+    BOOST_CHECK_EQUAL(to_fpt(sum), a + b);
+    BOOST_CHECK_EQUAL(to_fpt(dif), a - b);
+    BOOST_CHECK_EQUAL(to_fpt(mul), a * b);
+    BOOST_CHECK_EQUAL(to_fpt(div), a / b);
+  }
 }
 
 BOOST_AUTO_TEST_CASE(extended_exponent_fpt_test3) {
-    boost::mt19937_64 gen(static_cast<uint32>(time(NULL)));
-    for (int i = 0; i < 1000; ++i) {
-        fpt64 a = to_fpt(static_cast<int64>(gen()));
-        fpt64 b = to_fpt(static_cast<int64>(gen()));
-        if (b == 0.0) {
-            continue;
-        }
-        efpt64 eea(a);
-        efpt64 eeb(b);
-        efpt64 neg = -eea;
-        efpt64 sum = eea + eeb;
-        efpt64 dif = eea - eeb;
-        efpt64 mul = eea * eeb;
-        efpt64 div = eea / eeb;
-        BOOST_CHECK_EQUAL(to_fpt(neg), -a);
-        BOOST_CHECK_EQUAL(to_fpt(sum), a + b);
-        BOOST_CHECK_EQUAL(to_fpt(dif), a - b);
-        BOOST_CHECK_EQUAL(to_fpt(mul), a * b);
-        BOOST_CHECK_EQUAL(to_fpt(div), a / b);
-    }
+  boost::mt19937_64 gen(static_cast<uint32>(time(NULL)));
+  for (int i = 0; i < 1000; ++i) {
+    fpt64 a = to_fpt(static_cast<int64>(gen()));
+    fpt64 b = to_fpt(static_cast<int64>(gen()));
+    if (b == 0.0)
+      continue;
+    efpt64 eea(a);
+    efpt64 eeb(b);
+    efpt64 neg = -eea;
+    efpt64 sum = eea + eeb;
+    efpt64 dif = eea - eeb;
+    efpt64 mul = eea * eeb;
+    efpt64 div = eea / eeb;
+    BOOST_CHECK_EQUAL(to_fpt(neg), -a);
+    BOOST_CHECK_EQUAL(to_fpt(sum), a + b);
+    BOOST_CHECK_EQUAL(to_fpt(dif), a - b);
+    BOOST_CHECK_EQUAL(to_fpt(mul), a * b);
+    BOOST_CHECK_EQUAL(to_fpt(div), a / b);
+  }
 }
 
 BOOST_AUTO_TEST_CASE(extended_exponent_fpt_test4) {
-    for (int exp = 0; exp < 64; ++exp)
-    for (int i = 1; i < 100; ++i) {
-        fpt64 a = i;
-        fpt64 b = to_fpt(1LL << exp);
-        efpt64 eea(a);
-        efpt64 eeb(b);
-        efpt64 neg = -eea;
-        efpt64 sum = eea + eeb;
-        efpt64 dif = eea - eeb;
-        efpt64 mul = eea * eeb;
-        efpt64 div = eea / eeb;
-        BOOST_CHECK_EQUAL(to_fpt(neg), -a);
-        BOOST_CHECK_EQUAL(to_fpt(sum), a + b);
-        BOOST_CHECK_EQUAL(to_fpt(dif), a - b);
-        BOOST_CHECK_EQUAL(to_fpt(mul), a * b);
-        BOOST_CHECK_EQUAL(to_fpt(div), a / b);
-    }
+  for (int exp = 0; exp < 64; ++exp)
+  for (int i = 1; i < 100; ++i) {
+    fpt64 a = i;
+    fpt64 b = to_fpt(1LL << exp);
+    efpt64 eea(a);
+    efpt64 eeb(b);
+    efpt64 neg = -eea;
+    efpt64 sum = eea + eeb;
+    efpt64 dif = eea - eeb;
+    efpt64 mul = eea * eeb;
+    efpt64 div = eea / eeb;
+    BOOST_CHECK_EQUAL(to_fpt(neg), -a);
+    BOOST_CHECK_EQUAL(to_fpt(sum), a + b);
+    BOOST_CHECK_EQUAL(to_fpt(dif), a - b);
+    BOOST_CHECK_EQUAL(to_fpt(mul), a * b);
+    BOOST_CHECK_EQUAL(to_fpt(div), a / b);
+  }
 }
 
 BOOST_AUTO_TEST_CASE(extended_exponent_fpt_test5) {
-    for (int i = 0; i < 100; ++i) {
-        efpt64 a(to_fpt(i * i));
-        efpt64 b = a.sqrt();
-        BOOST_CHECK_EQUAL(to_fpt(b), to_fpt(i));
-    }
+  for (int i = 0; i < 100; ++i) {
+    efpt64 a(to_fpt(i * i));
+    efpt64 b = a.sqrt();
+    BOOST_CHECK_EQUAL(to_fpt(b), to_fpt(i));
+  }
 }
 
 BOOST_AUTO_TEST_CASE(extended_exponent_fpt_test6) {
-    for (int i = -10; i <= 10; ++i) {
-        efpt64 a(to_fpt(i));
-        BOOST_CHECK_EQUAL(is_pos(a), i > 0);
-        BOOST_CHECK_EQUAL(is_neg(a), i < 0);
-        BOOST_CHECK_EQUAL(is_zero(a), !i);
-    }
+  for (int i = -10; i <= 10; ++i) {
+    efpt64 a(to_fpt(i));
+    BOOST_CHECK_EQUAL(is_pos(a), i > 0);
+    BOOST_CHECK_EQUAL(is_neg(a), i < 0);
+    BOOST_CHECK_EQUAL(is_zero(a), !i);
+  }
 }
 
 BOOST_AUTO_TEST_CASE(extended_int_test1) {
-    typedef extended_int<1> eint32;
-    eint32 e1(0), e2(32), e3(-32);
-    BOOST_CHECK_EQUAL(e1.count(), 0);
-    BOOST_CHECK_EQUAL(e1.size(), 0U);
-    BOOST_CHECK_EQUAL(e2.count(), 1);
-    BOOST_CHECK_EQUAL(e2.chunks()[0], 32U);
-    BOOST_CHECK_EQUAL(e2.size(), 1U);
-    BOOST_CHECK_EQUAL(e3.count(), -1);
-    BOOST_CHECK_EQUAL(e3.chunks()[0], 32U);
-    BOOST_CHECK_EQUAL(e3.size(), 1U);
+  typedef extended_int<1> eint32;
+  eint32 e1(0), e2(32), e3(-32);
+  BOOST_CHECK_EQUAL(e1.count(), 0);
+  BOOST_CHECK_EQUAL(e1.size(), 0U);
+  BOOST_CHECK_EQUAL(e2.count(), 1);
+  BOOST_CHECK_EQUAL(e2.chunks()[0], 32U);
+  BOOST_CHECK_EQUAL(e2.size(), 1U);
+  BOOST_CHECK_EQUAL(e3.count(), -1);
+  BOOST_CHECK_EQUAL(e3.chunks()[0], 32U);
+  BOOST_CHECK_EQUAL(e3.size(), 1U);
 }
 
 BOOST_AUTO_TEST_CASE(extended_int_test2) {
-    typedef extended_int<2> eint64;
-    int64 val64 = 0x7fffffffffffffffLL;
-    eint64 e1(0), e2(32), e3(-32), e4(val64), e5(-val64);
-    BOOST_CHECK_EQUAL(e1.count(), 0);
-    BOOST_CHECK_EQUAL(e2.count(), 1);
-    BOOST_CHECK_EQUAL(e2.chunks()[0], 32U);
-    BOOST_CHECK_EQUAL(e3.count(), -1);
-    BOOST_CHECK_EQUAL(e3.chunks()[0], 32U);
-    BOOST_CHECK_EQUAL(e4.count(), 2);
-    BOOST_CHECK_EQUAL(e4.chunks()[0], 0xffffffff);
-    BOOST_CHECK_EQUAL(e4.chunks()[1], val64 >> 32);
-    BOOST_CHECK_EQUAL(e5.count(), -2);
-    BOOST_CHECK_EQUAL(e5.chunks()[0], 0xffffffff);
-    BOOST_CHECK_EQUAL(e5.chunks()[1], val64 >> 32);
+  typedef extended_int<2> eint64;
+  int64 val64 = 0x7fffffffffffffffLL;
+  eint64 e1(0), e2(32), e3(-32), e4(val64), e5(-val64);
+  BOOST_CHECK_EQUAL(e1.count(), 0);
+  BOOST_CHECK_EQUAL(e2.count(), 1);
+  BOOST_CHECK_EQUAL(e2.chunks()[0], 32U);
+  BOOST_CHECK_EQUAL(e3.count(), -1);
+  BOOST_CHECK_EQUAL(e3.chunks()[0], 32U);
+  BOOST_CHECK_EQUAL(e4.count(), 2);
+  BOOST_CHECK_EQUAL(e4.chunks()[0], 0xffffffff);
+  BOOST_CHECK_EQUAL(e4.chunks()[1], val64 >> 32);
+  BOOST_CHECK_EQUAL(e5.count(), -2);
+  BOOST_CHECK_EQUAL(e5.chunks()[0], 0xffffffff);
+  BOOST_CHECK_EQUAL(e5.chunks()[1], val64 >> 32);
 }
 
 BOOST_AUTO_TEST_CASE(extended_int_test3) {
-    typedef extended_int<2> eint64;
-    std::vector<uint32> chunks;
-    chunks.push_back(1);
-    chunks.push_back(2);
-    eint64 e1(chunks, true), e2(chunks, false);
-    BOOST_CHECK_EQUAL(e1.count(), 2);
-    BOOST_CHECK_EQUAL(e1.chunks()[0], 2U);
-    BOOST_CHECK_EQUAL(e1.chunks()[1], 1U);
-    BOOST_CHECK_EQUAL(e2.count(), -2);
-    BOOST_CHECK_EQUAL(e2.chunks()[0], 2U);
-    BOOST_CHECK_EQUAL(e2.chunks()[1], 1U);
+  typedef extended_int<2> eint64;
+  std::vector<uint32> chunks;
+  chunks.push_back(1);
+  chunks.push_back(2);
+  eint64 e1(chunks, true), e2(chunks, false);
+  BOOST_CHECK_EQUAL(e1.count(), 2);
+  BOOST_CHECK_EQUAL(e1.chunks()[0], 2U);
+  BOOST_CHECK_EQUAL(e1.chunks()[1], 1U);
+  BOOST_CHECK_EQUAL(e2.count(), -2);
+  BOOST_CHECK_EQUAL(e2.chunks()[0], 2U);
+  BOOST_CHECK_EQUAL(e2.chunks()[1], 1U);
 }
 
 BOOST_AUTO_TEST_CASE(extended_int_test4) {
-    typedef extended_int<2> eint64;
-    std::vector<uint32> chunks;
-    chunks.push_back(1);
-    chunks.push_back(2);
-    eint64 e1(chunks, true), e2(chunks, false);
-    BOOST_CHECK_EQUAL(e1 == e2, false);
-    BOOST_CHECK_EQUAL(e1 == -e2, true);
-    BOOST_CHECK_EQUAL(e1 != e2, true);
-    BOOST_CHECK_EQUAL(e1 != -e2, false);
-    BOOST_CHECK_EQUAL(e1 < e2, false);
-    BOOST_CHECK_EQUAL(e1 < -e2, false);
-    BOOST_CHECK_EQUAL(e1 <= e2, false);
-    BOOST_CHECK_EQUAL(e1 <= -e2, true);
-    BOOST_CHECK_EQUAL(e1 > e2, true);
-    BOOST_CHECK_EQUAL(e1 > -e2, false);
-    BOOST_CHECK_EQUAL(e1 >= e2, true);
-    BOOST_CHECK_EQUAL(e1 >= -e2, true);
+  typedef extended_int<2> eint64;
+  std::vector<uint32> chunks;
+  chunks.push_back(1);
+  chunks.push_back(2);
+  eint64 e1(chunks, true), e2(chunks, false);
+  BOOST_CHECK_EQUAL(e1 == e2, false);
+  BOOST_CHECK_EQUAL(e1 == -e2, true);
+  BOOST_CHECK_EQUAL(e1 != e2, true);
+  BOOST_CHECK_EQUAL(e1 != -e2, false);
+  BOOST_CHECK_EQUAL(e1 < e2, false);
+  BOOST_CHECK_EQUAL(e1 < -e2, false);
+  BOOST_CHECK_EQUAL(e1 <= e2, false);
+  BOOST_CHECK_EQUAL(e1 <= -e2, true);
+  BOOST_CHECK_EQUAL(e1 > e2, true);
+  BOOST_CHECK_EQUAL(e1 > -e2, false);
+  BOOST_CHECK_EQUAL(e1 >= e2, true);
+  BOOST_CHECK_EQUAL(e1 >= -e2, true);
 }
 
 BOOST_AUTO_TEST_CASE(extended_int_test5) {
-    typedef extended_int<2> eint64;
-    boost::mt19937_64 gen(static_cast<uint32>(time(NULL)));
-    for (int i = 0; i < 1000; ++i) {
-        int64 i1 = static_cast<int64>(gen());
-        int64 i2 = static_cast<int64>(gen());
-        eint64 e1(i1), e2(i2);
-        BOOST_CHECK_EQUAL(e1 == e2, i1 == i2);
-        BOOST_CHECK_EQUAL(e1 != e2, i1 != i2);
-        BOOST_CHECK_EQUAL(e1 > e2, i1 > i2);
-        BOOST_CHECK_EQUAL(e1 >= e2, i1 >= i2);
-        BOOST_CHECK_EQUAL(e1 < e2, i1 < i2);
-        BOOST_CHECK_EQUAL(e1 <= e2, i1 <= i2);
-    }
+  typedef extended_int<2> eint64;
+  boost::mt19937_64 gen(static_cast<uint32>(time(NULL)));
+  for (int i = 0; i < 1000; ++i) {
+    int64 i1 = static_cast<int64>(gen());
+    int64 i2 = static_cast<int64>(gen());
+    eint64 e1(i1), e2(i2);
+    BOOST_CHECK_EQUAL(e1 == e2, i1 == i2);
+    BOOST_CHECK_EQUAL(e1 != e2, i1 != i2);
+    BOOST_CHECK_EQUAL(e1 > e2, i1 > i2);
+    BOOST_CHECK_EQUAL(e1 >= e2, i1 >= i2);
+    BOOST_CHECK_EQUAL(e1 < e2, i1 < i2);
+    BOOST_CHECK_EQUAL(e1 <= e2, i1 <= i2);
+  }
 }
 
 BOOST_AUTO_TEST_CASE(extended_int_test6) {
-    typedef extended_int<1> eint32;
-    eint32 e1(32);
-    eint32 e2 = -e1;
-    BOOST_CHECK_EQUAL(e2.count(), -1);
-    BOOST_CHECK_EQUAL(e2.size(), 1U);
-    BOOST_CHECK_EQUAL(e2.chunks()[0], 32U);
+  typedef extended_int<1> eint32;
+  eint32 e1(32);
+  eint32 e2 = -e1;
+  BOOST_CHECK_EQUAL(e2.count(), -1);
+  BOOST_CHECK_EQUAL(e2.size(), 1U);
+  BOOST_CHECK_EQUAL(e2.chunks()[0], 32U);
 }
 
 BOOST_AUTO_TEST_CASE(extended_int_test7) {
-    typedef extended_int<2> eint64;
-    boost::mt19937_64 gen(static_cast<uint32>(time(NULL)));
-    for (int i = 0; i < 1000; ++i) {
-        int64 i1 = static_cast<int64>(gen()) >> 2;
-        int64 i2 = static_cast<int64>(gen()) >> 2;
-        eint64 e1(i1), e2(i2), e3(i1 + i2), e4(i1 - i2);
-        BOOST_CHECK(e1 + e2 == e3);
-        BOOST_CHECK(e1 - e2 == e4);
-    }
+  typedef extended_int<2> eint64;
+  boost::mt19937_64 gen(static_cast<uint32>(time(NULL)));
+  for (int i = 0; i < 1000; ++i) {
+    int64 i1 = static_cast<int64>(gen()) >> 2;
+    int64 i2 = static_cast<int64>(gen()) >> 2;
+    eint64 e1(i1), e2(i2), e3(i1 + i2), e4(i1 - i2);
+    BOOST_CHECK(e1 + e2 == e3);
+    BOOST_CHECK(e1 - e2 == e4);
+  }
 }
 
 BOOST_AUTO_TEST_CASE(extended_int_test8) {
-    typedef extended_int<2> eint64;
-    boost::mt19937 gen(static_cast<uint32>(time(NULL)));
-    for (int i = 0; i < 1000; ++i) {
-        int64 i1 = static_cast<int32>(gen());
-        int64 i2 = static_cast<int32>(gen());
-        eint64 e1(i1), e2(i2), e3(i1 * i2);
-        BOOST_CHECK(e1 * e2 == e3);
-    }
+  typedef extended_int<2> eint64;
+  boost::mt19937 gen(static_cast<uint32>(time(NULL)));
+  for (int i = 0; i < 1000; ++i) {
+    int64 i1 = static_cast<int32>(gen());
+    int64 i2 = static_cast<int32>(gen());
+    eint64 e1(i1), e2(i2), e3(i1 * i2);
+    BOOST_CHECK(e1 * e2 == e3);
+  }
 }
 
 BOOST_AUTO_TEST_CASE(exnteded_int_test9) {
-    typedef extended_int<1> eint32;
-    for (int i = -10; i <= 10; ++i) {
-        for (int j = -10; j <= 10; ++j) {
-            eint32 e1(i), e2(j), e3(i+j), e4(i-j), e5(i*j);
-            BOOST_CHECK(e1 + e2 == e3);
-            BOOST_CHECK(e1 - e2 == e4);
-            BOOST_CHECK(e1 * e2 == e5);
-        }
+  typedef extended_int<1> eint32;
+  for (int i = -10; i <= 10; ++i) {
+    for (int j = -10; j <= 10; ++j) {
+      eint32 e1(i), e2(j), e3(i+j), e4(i-j), e5(i*j);
+      BOOST_CHECK(e1 + e2 == e3);
+      BOOST_CHECK(e1 - e2 == e4);
+      BOOST_CHECK(e1 * e2 == e5);
     }
+  }
 }
 
 BOOST_AUTO_TEST_CASE(extended_int_test10) {
-    typedef extended_int<2> eint64;
-    boost::mt19937_64 gen(static_cast<uint32>(time(NULL)));
-    for (int i = 0; i < 100; ++i) {
-        int64 i1 = static_cast<int64>(gen()) >> 20;
-        int64 i2 = i1 >> 32;
-        eint64 e1(i1), e2(i2);
-        BOOST_CHECK(to_fpt(e1) == static_cast<fpt64>(i1));
-        BOOST_CHECK(to_fpt(e2) == static_cast<fpt64>(i2));
-    }
+  typedef extended_int<2> eint64;
+  boost::mt19937_64 gen(static_cast<uint32>(time(NULL)));
+  for (int i = 0; i < 100; ++i) {
+    int64 i1 = static_cast<int64>(gen()) >> 20;
+    int64 i2 = i1 >> 32;
+    eint64 e1(i1), e2(i2);
+    BOOST_CHECK(to_fpt(e1) == static_cast<fpt64>(i1));
+    BOOST_CHECK(to_fpt(e2) == static_cast<fpt64>(i2));
+  }
 }
 
 BOOST_AUTO_TEST_CASE(extened_int_test11) {
-    typedef extended_int<1> eint32;
-    typedef extended_int<64> eint2048;
-    eint32 two(2), one(1);
-    eint2048 value(1);
-    for (int i = 0; i < 1024; ++i) {
-        value = value * two;
-    }
-    BOOST_CHECK_EQUAL(value.count(), 33);
-    for (size_t i = 1; i < value.size(); ++i) {
-        BOOST_CHECK_EQUAL(value.chunks()[i-1], 0U);
-    }
-    BOOST_CHECK_EQUAL(value.chunks()[32], 1U);
+  typedef extended_int<1> eint32;
+  typedef extended_int<64> eint2048;
+  eint32 two(2), one(1);
+  eint2048 value(1);
+  for (int i = 0; i < 1024; ++i)
+    value = value * two;
+  BOOST_CHECK_EQUAL(value.count(), 33);
+  for (size_t i = 1; i < value.size(); ++i)
+    BOOST_CHECK_EQUAL(value.chunks()[i-1], 0U);
+  BOOST_CHECK_EQUAL(value.chunks()[32], 1U);
 }

Modified: sandbox/gtl/libs/polygon/test/voronoi_predicates_test.cpp
==============================================================================
--- sandbox/gtl/libs/polygon/test/voronoi_predicates_test.cpp	(original)
+++ sandbox/gtl/libs/polygon/test/voronoi_predicates_test.cpp	2012-05-01 08:43:51 EDT (Tue, 01 May 2012)
@@ -12,9 +12,9 @@
 #define BOOST_TEST_MODULE voronoi_predicates_test
 #include <boost/test/test_case_template.hpp>
 
-#include "boost/polygon/detail/voronoi_ctypes.hpp"
-#include "boost/polygon/detail/voronoi_predicates.hpp"
-#include "boost/polygon/detail/voronoi_structures.hpp"
+#include <boost/polygon/detail/voronoi_ctypes.hpp>
+#include <boost/polygon/detail/voronoi_predicates.hpp>
+#include <boost/polygon/detail/voronoi_structures.hpp>
 using namespace boost::polygon::detail;
 
 ulp_comparison<double> ulp_cmp;
@@ -56,8 +56,8 @@
 
 #define CHECK_NODE_COMPARISON(node, nodes, res, sz) \
     for (int i = 0; i < sz; ++i) { \
-        BOOST_CHECK_EQUAL(node_comparison(node, nodes[i]), res[i]); \
-        BOOST_CHECK_EQUAL(node_comparison(nodes[i], node), !res[i]); \
+      BOOST_CHECK_EQUAL(node_comparison(node, nodes[i]), res[i]); \
+      BOOST_CHECK_EQUAL(node_comparison(nodes[i], node), !res[i]); \
     }
 
 #define CHECK_CIRCLE(circle, c_x, c_y, l_x) \
@@ -77,383 +77,383 @@
     CHECK_CIRCLE(c2, c_x, c_y, l_x); }
 
 BOOST_AUTO_TEST_CASE(orientation_test) {
-    int min_int = std::numeric_limits<int>::min();
-    int max_int = std::numeric_limits<int>::max();
-    point_type point1(min_int, min_int);
-    point_type point2(0, 0);
-    point_type point3(max_int, max_int);
-    point_type point4(min_int, max_int);
-    point_type point5(max_int-1, max_int);
-    CHECK_ORIENTATION(point1, point2, point3, VP::ot::COLLINEAR, VP::ot::COLLINEAR);
-    CHECK_ORIENTATION(point1, point4, point3, VP::ot::RIGHT, VP::ot::LEFT);
-    CHECK_ORIENTATION(point1, point5, point3, VP::ot::RIGHT, VP::ot::LEFT);
+  int min_int = std::numeric_limits<int>::min();
+  int max_int = std::numeric_limits<int>::max();
+  point_type point1(min_int, min_int);
+  point_type point2(0, 0);
+  point_type point3(max_int, max_int);
+  point_type point4(min_int, max_int);
+  point_type point5(max_int-1, max_int);
+  CHECK_ORIENTATION(point1, point2, point3, VP::ot::COLLINEAR, VP::ot::COLLINEAR);
+  CHECK_ORIENTATION(point1, point4, point3, VP::ot::RIGHT, VP::ot::LEFT);
+  CHECK_ORIENTATION(point1, point5, point3, VP::ot::RIGHT, VP::ot::LEFT);
 }
 
 BOOST_AUTO_TEST_CASE(event_comparison_test1) {
-    site_type site(1, 2);
-    CHECK_EVENT_COMPARISON(site, site_type(0, 2), false, true);
-    CHECK_EVENT_COMPARISON(site, site_type(1, 3), true, false);
-    CHECK_EVENT_COMPARISON(site, site_type(1, 2), false, false);
+  site_type site(1, 2);
+  CHECK_EVENT_COMPARISON(site, site_type(0, 2), false, true);
+  CHECK_EVENT_COMPARISON(site, site_type(1, 3), true, false);
+  CHECK_EVENT_COMPARISON(site, site_type(1, 2), false, false);
 }
 
 BOOST_AUTO_TEST_CASE(event_comparison_test2) {
-    site_type site(0, 0, 0, 2);
-    CHECK_EVENT_COMPARISON(site, site_type(0, 2), true, false);
-    CHECK_EVENT_COMPARISON(site, site_type(0, 0), false, true);
-    CHECK_EVENT_COMPARISON(site, site_type(0, -2, 0, -1), false, true);
-    CHECK_EVENT_COMPARISON(site, site_type(0, -2, 1, 1), true, false);
-    CHECK_EVENT_COMPARISON(site, site_type(0, 0, 1, 1), true, false);
+  site_type site(0, 0, 0, 2);
+  CHECK_EVENT_COMPARISON(site, site_type(0, 2), true, false);
+  CHECK_EVENT_COMPARISON(site, site_type(0, 0), false, true);
+  CHECK_EVENT_COMPARISON(site, site_type(0, -2, 0, -1), false, true);
+  CHECK_EVENT_COMPARISON(site, site_type(0, -2, 1, 1), true, false);
+  CHECK_EVENT_COMPARISON(site, site_type(0, 0, 1, 1), true, false);
 }
 
 BOOST_AUTO_TEST_CASE(event_comparison_test3) {
-    site_type site(0, 0, 10, 10);
-    CHECK_EVENT_COMPARISON(site, site_type(0, 0), false, true);
-    CHECK_EVENT_COMPARISON(site, site_type(0, -1), false, true);
-    CHECK_EVENT_COMPARISON(site, site_type(0, 1), false, true);
-    CHECK_EVENT_COMPARISON(site, site_type(0, 1, 0, 10), false, true);
-    CHECK_EVENT_COMPARISON(site, site_type(0, -10, 0, -1), false, true);
-    CHECK_EVENT_COMPARISON(site, site_type(0, 0, 10, 9), true, false);
-    CHECK_EVENT_COMPARISON(site, site_type(0, 0, 9, 10), false, true);
+  site_type site(0, 0, 10, 10);
+  CHECK_EVENT_COMPARISON(site, site_type(0, 0), false, true);
+  CHECK_EVENT_COMPARISON(site, site_type(0, -1), false, true);
+  CHECK_EVENT_COMPARISON(site, site_type(0, 1), false, true);
+  CHECK_EVENT_COMPARISON(site, site_type(0, 1, 0, 10), false, true);
+  CHECK_EVENT_COMPARISON(site, site_type(0, -10, 0, -1), false, true);
+  CHECK_EVENT_COMPARISON(site, site_type(0, 0, 10, 9), true, false);
+  CHECK_EVENT_COMPARISON(site, site_type(0, 0, 9, 10), false, true);
 }
 
 BOOST_AUTO_TEST_CASE(event_comparison_test4) {
-    circle_type circle(1, 2, 3);
-    CHECK_EVENT_COMPARISON(circle, circle_type(1, 2, 3), false, false);
-    CHECK_EVENT_COMPARISON(circle, circle_type(1, 3, 3), true, false);
-    CHECK_EVENT_COMPARISON(circle, circle_type(1, 2, 4), true, false);
-    CHECK_EVENT_COMPARISON(circle, circle_type(0, 2, 2), false, true);
-    CHECK_EVENT_COMPARISON(circle, circle_type(-1, 2, 3), false, false);
+  circle_type circle(1, 2, 3);
+  CHECK_EVENT_COMPARISON(circle, circle_type(1, 2, 3), false, false);
+  CHECK_EVENT_COMPARISON(circle, circle_type(1, 3, 3), true, false);
+  CHECK_EVENT_COMPARISON(circle, circle_type(1, 2, 4), true, false);
+  CHECK_EVENT_COMPARISON(circle, circle_type(0, 2, 2), false, true);
+  CHECK_EVENT_COMPARISON(circle, circle_type(-1, 2, 3), false, false);
 }
 
 BOOST_AUTO_TEST_CASE(event_comparison_test5) {
-    circle_type circle(1, 2, 3);
-    CHECK_EVENT_COMPARISON(circle, site_type(0, 100), false, true);
-    CHECK_EVENT_COMPARISON(circle, site_type(3, 0), false, true);
-    CHECK_EVENT_COMPARISON(circle, site_type(3, 2), false, false);
-    CHECK_EVENT_COMPARISON(circle, site_type(3, 3), true, false);
-    CHECK_EVENT_COMPARISON(circle, site_type(4, 2), true, false);
+  circle_type circle(1, 2, 3);
+  CHECK_EVENT_COMPARISON(circle, site_type(0, 100), false, true);
+  CHECK_EVENT_COMPARISON(circle, site_type(3, 0), false, true);
+  CHECK_EVENT_COMPARISON(circle, site_type(3, 2), false, false);
+  CHECK_EVENT_COMPARISON(circle, site_type(3, 3), true, false);
+  CHECK_EVENT_COMPARISON(circle, site_type(4, 2), true, false);
 }
 
 BOOST_AUTO_TEST_CASE(distance_predicate_test1) {
-    site_type site1(-5, 0);
-    site_type site2(-8, 9);
-    site_type site3(-2, 1);
-    CHECK_DISTANCE_PREDICATE(site1, site2, site_type(0, 5), false);
-    CHECK_DISTANCE_PREDICATE(site3, site1, site_type(0, 5), false);
-    CHECK_DISTANCE_PREDICATE(site1, site2, site_type(0, 4), false);
-    CHECK_DISTANCE_PREDICATE(site3, site1, site_type(0, 4), false);
-    CHECK_DISTANCE_PREDICATE(site1, site2, site_type(0, 6), true);
-    CHECK_DISTANCE_PREDICATE(site3, site1, site_type(0, 6), true);
+  site_type site1(-5, 0);
+  site_type site2(-8, 9);
+  site_type site3(-2, 1);
+  CHECK_DISTANCE_PREDICATE(site1, site2, site_type(0, 5), false);
+  CHECK_DISTANCE_PREDICATE(site3, site1, site_type(0, 5), false);
+  CHECK_DISTANCE_PREDICATE(site1, site2, site_type(0, 4), false);
+  CHECK_DISTANCE_PREDICATE(site3, site1, site_type(0, 4), false);
+  CHECK_DISTANCE_PREDICATE(site1, site2, site_type(0, 6), true);
+  CHECK_DISTANCE_PREDICATE(site3, site1, site_type(0, 6), true);
 }
 
 BOOST_AUTO_TEST_CASE(distance_predicate_test2) {
-    site_type site1(-4, 0, -4, 20);
-    site_type site2(-2, 10);
-    CHECK_DISTANCE_PREDICATE(site2, site1, site_type(0, 11), false);
-    CHECK_DISTANCE_PREDICATE(site2, site1, site_type(0, 9), false);
-    CHECK_DISTANCE_PREDICATE(site1, site2, site_type(0, 11), true);
-    CHECK_DISTANCE_PREDICATE(site1, site2, site_type(0, 9), true);
+  site_type site1(-4, 0, -4, 20);
+  site_type site2(-2, 10);
+  CHECK_DISTANCE_PREDICATE(site2, site1, site_type(0, 11), false);
+  CHECK_DISTANCE_PREDICATE(site2, site1, site_type(0, 9), false);
+  CHECK_DISTANCE_PREDICATE(site1, site2, site_type(0, 11), true);
+  CHECK_DISTANCE_PREDICATE(site1, site2, site_type(0, 9), true);
 }
 
 BOOST_AUTO_TEST_CASE(disntace_predicate_test3) {
-    site_type site1(-5, 5, 2, -2);
-    site1.inverse();
-    site_type site2(-2, 4);
-    CHECK_DISTANCE_PREDICATE(site1, site2, site_type(0, -1), false);
-    CHECK_DISTANCE_PREDICATE(site2, site1, site_type(0, -1), false);
-    CHECK_DISTANCE_PREDICATE(site1, site2, site_type(0, 1), false);
-    CHECK_DISTANCE_PREDICATE(site2, site1, site_type(0, 1), false);
-    CHECK_DISTANCE_PREDICATE(site1, site2, site_type(0, 4), true);
-    CHECK_DISTANCE_PREDICATE(site2, site1, site_type(0, 4), false);
-    CHECK_DISTANCE_PREDICATE(site1, site2, site_type(0, 5), true);
-    CHECK_DISTANCE_PREDICATE(site2, site1, site_type(0, 5), false);
+  site_type site1(-5, 5, 2, -2);
+  site1.inverse();
+  site_type site2(-2, 4);
+  CHECK_DISTANCE_PREDICATE(site1, site2, site_type(0, -1), false);
+  CHECK_DISTANCE_PREDICATE(site2, site1, site_type(0, -1), false);
+  CHECK_DISTANCE_PREDICATE(site1, site2, site_type(0, 1), false);
+  CHECK_DISTANCE_PREDICATE(site2, site1, site_type(0, 1), false);
+  CHECK_DISTANCE_PREDICATE(site1, site2, site_type(0, 4), true);
+  CHECK_DISTANCE_PREDICATE(site2, site1, site_type(0, 4), false);
+  CHECK_DISTANCE_PREDICATE(site1, site2, site_type(0, 5), true);
+  CHECK_DISTANCE_PREDICATE(site2, site1, site_type(0, 5), false);
 }
 
 BOOST_AUTO_TEST_CASE(distance_predicate_test4) {
-    site_type site1(-5, 5, 2, -2);
-    site_type site2(-2, -4);
-    site_type site3(-4, 1);
-    CHECK_DISTANCE_PREDICATE(site1, site2, site_type(0, 1), true);
-    CHECK_DISTANCE_PREDICATE(site2, site1, site_type(0, 1), true);
-    CHECK_DISTANCE_PREDICATE(site1, site3, site_type(0, 1), true);
-    CHECK_DISTANCE_PREDICATE(site3, site1, site_type(0, 1), true);
-    CHECK_DISTANCE_PREDICATE(site1, site2, site_type(0, -2), true);
-    CHECK_DISTANCE_PREDICATE(site2, site1, site_type(0, -2), false);
-    CHECK_DISTANCE_PREDICATE(site1, site3, site_type(0, -2), true);
-    CHECK_DISTANCE_PREDICATE(site3, site1, site_type(0, -2), false);
-    CHECK_DISTANCE_PREDICATE(site1, site2, site_type(0, -8), true);
-    CHECK_DISTANCE_PREDICATE(site2, site1, site_type(0, -8), false);
-    CHECK_DISTANCE_PREDICATE(site1, site3, site_type(0, -8), true);
-    CHECK_DISTANCE_PREDICATE(site3, site1, site_type(0, -8), false);
-    CHECK_DISTANCE_PREDICATE(site1, site2, site_type(0, -9), true);
-    CHECK_DISTANCE_PREDICATE(site2, site1, site_type(0, -9), false);
-    CHECK_DISTANCE_PREDICATE(site1, site3, site_type(0, -9), true);
-    CHECK_DISTANCE_PREDICATE(site3, site1, site_type(0, -9), false);
+  site_type site1(-5, 5, 2, -2);
+  site_type site2(-2, -4);
+  site_type site3(-4, 1);
+  CHECK_DISTANCE_PREDICATE(site1, site2, site_type(0, 1), true);
+  CHECK_DISTANCE_PREDICATE(site2, site1, site_type(0, 1), true);
+  CHECK_DISTANCE_PREDICATE(site1, site3, site_type(0, 1), true);
+  CHECK_DISTANCE_PREDICATE(site3, site1, site_type(0, 1), true);
+  CHECK_DISTANCE_PREDICATE(site1, site2, site_type(0, -2), true);
+  CHECK_DISTANCE_PREDICATE(site2, site1, site_type(0, -2), false);
+  CHECK_DISTANCE_PREDICATE(site1, site3, site_type(0, -2), true);
+  CHECK_DISTANCE_PREDICATE(site3, site1, site_type(0, -2), false);
+  CHECK_DISTANCE_PREDICATE(site1, site2, site_type(0, -8), true);
+  CHECK_DISTANCE_PREDICATE(site2, site1, site_type(0, -8), false);
+  CHECK_DISTANCE_PREDICATE(site1, site3, site_type(0, -8), true);
+  CHECK_DISTANCE_PREDICATE(site3, site1, site_type(0, -8), false);
+  CHECK_DISTANCE_PREDICATE(site1, site2, site_type(0, -9), true);
+  CHECK_DISTANCE_PREDICATE(site2, site1, site_type(0, -9), false);
+  CHECK_DISTANCE_PREDICATE(site1, site3, site_type(0, -9), true);
+  CHECK_DISTANCE_PREDICATE(site3, site1, site_type(0, -9), false);
 }
 
 BOOST_AUTO_TEST_CASE(disntace_predicate_test5) {
-    site_type site1(-5, 5, 2, -2);
-    site_type site2 = site1;
-    site2.inverse();
-    site_type site3(-2, 4);
-    site_type site4(-2, -4);
-    site_type site5(-4, 1);
-    CHECK_DISTANCE_PREDICATE(site3, site2, site_type(0, 1), false);
-    CHECK_DISTANCE_PREDICATE(site3, site2, site_type(0, 4), false);
-    CHECK_DISTANCE_PREDICATE(site3, site2, site_type(0, 5), false);
-    CHECK_DISTANCE_PREDICATE(site3, site2, site_type(0, 7), true);
-    CHECK_DISTANCE_PREDICATE(site4, site1, site_type(0, -2), false);
-    CHECK_DISTANCE_PREDICATE(site5, site1, site_type(0, -2), false);
-    CHECK_DISTANCE_PREDICATE(site4, site1, site_type(0, -8), false);
-    CHECK_DISTANCE_PREDICATE(site5, site1, site_type(0, -8), false);
-    CHECK_DISTANCE_PREDICATE(site4, site1, site_type(0, -9), false);
-    CHECK_DISTANCE_PREDICATE(site5, site1, site_type(0, -9), false);
-    CHECK_DISTANCE_PREDICATE(site4, site1, site_type(0, -18), false);
-    CHECK_DISTANCE_PREDICATE(site5, site1, site_type(0, -18), false);
-    CHECK_DISTANCE_PREDICATE(site4, site1, site_type(0, -1), true);
-    CHECK_DISTANCE_PREDICATE(site5, site1, site_type(0, -1), true);
+  site_type site1(-5, 5, 2, -2);
+  site_type site2 = site1;
+  site2.inverse();
+  site_type site3(-2, 4);
+  site_type site4(-2, -4);
+  site_type site5(-4, 1);
+  CHECK_DISTANCE_PREDICATE(site3, site2, site_type(0, 1), false);
+  CHECK_DISTANCE_PREDICATE(site3, site2, site_type(0, 4), false);
+  CHECK_DISTANCE_PREDICATE(site3, site2, site_type(0, 5), false);
+  CHECK_DISTANCE_PREDICATE(site3, site2, site_type(0, 7), true);
+  CHECK_DISTANCE_PREDICATE(site4, site1, site_type(0, -2), false);
+  CHECK_DISTANCE_PREDICATE(site5, site1, site_type(0, -2), false);
+  CHECK_DISTANCE_PREDICATE(site4, site1, site_type(0, -8), false);
+  CHECK_DISTANCE_PREDICATE(site5, site1, site_type(0, -8), false);
+  CHECK_DISTANCE_PREDICATE(site4, site1, site_type(0, -9), false);
+  CHECK_DISTANCE_PREDICATE(site5, site1, site_type(0, -9), false);
+  CHECK_DISTANCE_PREDICATE(site4, site1, site_type(0, -18), false);
+  CHECK_DISTANCE_PREDICATE(site5, site1, site_type(0, -18), false);
+  CHECK_DISTANCE_PREDICATE(site4, site1, site_type(0, -1), true);
+  CHECK_DISTANCE_PREDICATE(site5, site1, site_type(0, -1), true);
 }
 
 BOOST_AUTO_TEST_CASE(distance_predicate_test6) {
-    site_type site1(-5, 0, 2, 7);
-    site_type site2 = site1;
-    site2.inverse();
-    CHECK_DISTANCE_PREDICATE(site1, site2, site_type(2, 7), false);
-    CHECK_DISTANCE_PREDICATE(site1, site2, site_type(1, 5), false);
-    CHECK_DISTANCE_PREDICATE(site1, site2, site_type(-1, 5), true);
+  site_type site1(-5, 0, 2, 7);
+  site_type site2 = site1;
+  site2.inverse();
+  CHECK_DISTANCE_PREDICATE(site1, site2, site_type(2, 7), false);
+  CHECK_DISTANCE_PREDICATE(site1, site2, site_type(1, 5), false);
+  CHECK_DISTANCE_PREDICATE(site1, site2, site_type(-1, 5), true);
 }
 
 BOOST_AUTO_TEST_CASE(distance_predicate_test7) {
-    site_type site1(-5, 5, 2, -2);
-    site1.inverse();
-    site_type site2(-5, 5, 0, 6);
-    site_type site3(-2, 4, 0, 4);
-    site_type site4(0, 2);
-    site_type site5(0, 5);
-    site_type site6(0, 6);
-    site_type site7(0, 8);
-    CHECK_DISTANCE_PREDICATE(site1, site2, site4, false);
-    CHECK_DISTANCE_PREDICATE(site1, site2, site5, true);
-    CHECK_DISTANCE_PREDICATE(site1, site2, site6, true);
-    CHECK_DISTANCE_PREDICATE(site1, site2, site7, true);
-    CHECK_DISTANCE_PREDICATE(site1, site3, site4, false);
-    CHECK_DISTANCE_PREDICATE(site1, site3, site5, true);
-    CHECK_DISTANCE_PREDICATE(site1, site3, site6, true);
-    CHECK_DISTANCE_PREDICATE(site1, site3, site7, true);
-    site3.inverse();
-    CHECK_DISTANCE_PREDICATE(site3, site1, site4, false);
-    CHECK_DISTANCE_PREDICATE(site3, site1, site5, false);
-    CHECK_DISTANCE_PREDICATE(site3, site1, site6, false);
-    CHECK_DISTANCE_PREDICATE(site3, site1, site7, true);
+  site_type site1(-5, 5, 2, -2);
+  site1.inverse();
+  site_type site2(-5, 5, 0, 6);
+  site_type site3(-2, 4, 0, 4);
+  site_type site4(0, 2);
+  site_type site5(0, 5);
+  site_type site6(0, 6);
+  site_type site7(0, 8);
+  CHECK_DISTANCE_PREDICATE(site1, site2, site4, false);
+  CHECK_DISTANCE_PREDICATE(site1, site2, site5, true);
+  CHECK_DISTANCE_PREDICATE(site1, site2, site6, true);
+  CHECK_DISTANCE_PREDICATE(site1, site2, site7, true);
+  CHECK_DISTANCE_PREDICATE(site1, site3, site4, false);
+  CHECK_DISTANCE_PREDICATE(site1, site3, site5, true);
+  CHECK_DISTANCE_PREDICATE(site1, site3, site6, true);
+  CHECK_DISTANCE_PREDICATE(site1, site3, site7, true);
+  site3.inverse();
+  CHECK_DISTANCE_PREDICATE(site3, site1, site4, false);
+  CHECK_DISTANCE_PREDICATE(site3, site1, site5, false);
+  CHECK_DISTANCE_PREDICATE(site3, site1, site6, false);
+  CHECK_DISTANCE_PREDICATE(site3, site1, site7, true);
 }
 
 BOOST_AUTO_TEST_CASE(distatnce_predicate_test8) {
-    site_type site1(-5, 3, -2, 2);
-    site1.inverse();
-    site_type site2(-5, 5, -2, 2);
-    CHECK_DISTANCE_PREDICATE(site1, site2, site_type(-4, 2), false);
+  site_type site1(-5, 3, -2, 2);
+  site1.inverse();
+  site_type site2(-5, 5, -2, 2);
+  CHECK_DISTANCE_PREDICATE(site1, site2, site_type(-4, 2), false);
 }
 
 BOOST_AUTO_TEST_CASE(node_comparison_test1) {
-    beach_line_type beach_line;
-    site_type site1(0, 0);
-    site1.index(0);
-    site_type site2(0, 2);
-    site2.index(1);
-    site_type site3(1, 0);
-    site3.index(2);
-    beach_line[key_type(site1, site2)] = 2;
-    beach_line[key_type(site1, site3)] = 0;
-    beach_line[key_type(site3, site1)] = 1;
-    int cur_index = 0;
-    for (bieach_line_iterator it = beach_line.begin();
-         it != beach_line.end(); ++it, ++cur_index) {
-        BOOST_CHECK_EQUAL(it->second, cur_index);
-    }
+  beach_line_type beach_line;
+  site_type site1(0, 0);
+  site1.index(0);
+  site_type site2(0, 2);
+  site2.index(1);
+  site_type site3(1, 0);
+  site3.index(2);
+  beach_line[key_type(site1, site2)] = 2;
+  beach_line[key_type(site1, site3)] = 0;
+  beach_line[key_type(site3, site1)] = 1;
+  int cur_index = 0;
+  for (bieach_line_iterator it = beach_line.begin();
+       it != beach_line.end(); ++it, ++cur_index) {
+    BOOST_CHECK_EQUAL(it->second, cur_index);
+  }
 }
 
 BOOST_AUTO_TEST_CASE(node_comparison_test2) {
-    beach_line_type beach_line;
-    site_type site1(0, 1);
-    site1.index(0);
-    site_type site2(2, 0);
-    site2.index(1);
-    site_type site3(2, 4);
-    site3.index(2);
-    beach_line[key_type(site1, site2)] = 0;
-    beach_line[key_type(site2, site1)] = 1;
-    beach_line[key_type(site1, site3)] = 2;
-    beach_line[key_type(site3, site1)] = 3;
-    int cur_index = 0;
-    for (bieach_line_iterator it = beach_line.begin();
-         it != beach_line.end(); ++it, ++cur_index) {
-        BOOST_CHECK_EQUAL(it->second, cur_index);
-    }
+  beach_line_type beach_line;
+  site_type site1(0, 1);
+  site1.index(0);
+  site_type site2(2, 0);
+  site2.index(1);
+  site_type site3(2, 4);
+  site3.index(2);
+  beach_line[key_type(site1, site2)] = 0;
+  beach_line[key_type(site2, site1)] = 1;
+  beach_line[key_type(site1, site3)] = 2;
+  beach_line[key_type(site3, site1)] = 3;
+  int cur_index = 0;
+  for (bieach_line_iterator it = beach_line.begin();
+       it != beach_line.end(); ++it, ++cur_index) {
+    BOOST_CHECK_EQUAL(it->second, cur_index);
+  }
 }
 
 BOOST_AUTO_TEST_CASE(node_comparison_test3) {
-    key_type node(site_type(1, 0).index(1), site_type(0, 2).index(0));
-    key_type nodes[] = {
-        key_type(site_type(2, -10).index(2)),
-        key_type(site_type(2, -1).index(2)),
-        key_type(site_type(2, 0).index(2)),
-        key_type(site_type(2, 1).index(2)),
-        key_type(site_type(2, 2).index(2)),
-        key_type(site_type(2, 3).index(2)),
-    };
-    bool res[] = {false, false, false, false, true, true};
-    CHECK_NODE_COMPARISON(node, nodes, res, 6);
+  key_type node(site_type(1, 0).index(1), site_type(0, 2).index(0));
+  key_type nodes[] = {
+    key_type(site_type(2, -10).index(2)),
+    key_type(site_type(2, -1).index(2)),
+    key_type(site_type(2, 0).index(2)),
+    key_type(site_type(2, 1).index(2)),
+    key_type(site_type(2, 2).index(2)),
+    key_type(site_type(2, 3).index(2)),
+  };
+  bool res[] = {false, false, false, false, true, true};
+  CHECK_NODE_COMPARISON(node, nodes, res, 6);
 }
 
 BOOST_AUTO_TEST_CASE(node_comparison_test4) {
-    key_type node(site_type(0, 1).index(0), site_type(1, 0).index(1));
-    key_type nodes[] = {
-        key_type(site_type(2, -3).index(2)),
-        key_type(site_type(2, -2).index(2)),
-        key_type(site_type(2, -1).index(2)),
-        key_type(site_type(2, 0).index(2)),
-        key_type(site_type(2, 1).index(2)),
-        key_type(site_type(2, 3).index(2)),
-    };
-    bool res[] = {false, true, true, true, true, true};
-    CHECK_NODE_COMPARISON(node, nodes, res, 6);
+  key_type node(site_type(0, 1).index(0), site_type(1, 0).index(1));
+  key_type nodes[] = {
+    key_type(site_type(2, -3).index(2)),
+    key_type(site_type(2, -2).index(2)),
+    key_type(site_type(2, -1).index(2)),
+    key_type(site_type(2, 0).index(2)),
+    key_type(site_type(2, 1).index(2)),
+    key_type(site_type(2, 3).index(2)),
+  };
+  bool res[] = {false, true, true, true, true, true};
+  CHECK_NODE_COMPARISON(node, nodes, res, 6);
 }
 
 BOOST_AUTO_TEST_CASE(node_comparison_test5) {
-    key_type node(site_type(0, 0).index(0), site_type(1, 2).index(1));
-    key_type nodes[] = {
-        key_type(site_type(2, -10).index(2)),
-        key_type(site_type(2, 0).index(2)),
-        key_type(site_type(2, 1).index(2)),
-        key_type(site_type(2, 2).index(2)),
-        key_type(site_type(2, 5).index(2)),
-        key_type(site_type(2, 20).index(2)),
-    };
-    bool res[] = {false, false, true, true, true, true};
-    CHECK_NODE_COMPARISON(node, nodes, res, 6);
+  key_type node(site_type(0, 0).index(0), site_type(1, 2).index(1));
+  key_type nodes[] = {
+    key_type(site_type(2, -10).index(2)),
+    key_type(site_type(2, 0).index(2)),
+    key_type(site_type(2, 1).index(2)),
+    key_type(site_type(2, 2).index(2)),
+    key_type(site_type(2, 5).index(2)),
+    key_type(site_type(2, 20).index(2)),
+  };
+  bool res[] = {false, false, true, true, true, true};
+  CHECK_NODE_COMPARISON(node, nodes, res, 6);
 }
 
 BOOST_AUTO_TEST_CASE(node_comparison_test6) {
-    key_type node(site_type(1, 1).index(1), site_type(0, 0).index(0));
-    key_type nodes [] = {
-        key_type(site_type(2, -3).index(2)),
-        key_type(site_type(2, -2).index(2)),
-        key_type(site_type(2, 0).index(2)),
-        key_type(site_type(2, 1).index(2)),
-        key_type(site_type(2, 2).index(2)),
-        key_type(site_type(2, 3).index(2)),
-        key_type(site_type(2, 5).index(2)),
-    };
-    bool res[] = {false, false, false, false, false, false, true};
-    CHECK_NODE_COMPARISON(node, nodes, res, 7);
+  key_type node(site_type(1, 1).index(1), site_type(0, 0).index(0));
+  key_type nodes [] = {
+    key_type(site_type(2, -3).index(2)),
+    key_type(site_type(2, -2).index(2)),
+    key_type(site_type(2, 0).index(2)),
+    key_type(site_type(2, 1).index(2)),
+    key_type(site_type(2, 2).index(2)),
+    key_type(site_type(2, 3).index(2)),
+    key_type(site_type(2, 5).index(2)),
+  };
+  bool res[] = {false, false, false, false, false, false, true};
+  CHECK_NODE_COMPARISON(node, nodes, res, 7);
 }
 
 BOOST_AUTO_TEST_CASE(node_comparison_test7) {
-    key_type node(site_type(0, 0).index(0), site_type(0, 2).index(1));
-    key_type nodes[] = {
-        key_type(site_type(1, 0).index(2)),
-        key_type(site_type(1, 1).index(2)),
-        key_type(site_type(1, 2).index(2)),
-    };
-    bool res[] = {false, false, true};
-    CHECK_NODE_COMPARISON(node, nodes, res, 3);
+  key_type node(site_type(0, 0).index(0), site_type(0, 2).index(1));
+  key_type nodes[] = {
+    key_type(site_type(1, 0).index(2)),
+    key_type(site_type(1, 1).index(2)),
+    key_type(site_type(1, 2).index(2)),
+  };
+  bool res[] = {false, false, true};
+  CHECK_NODE_COMPARISON(node, nodes, res, 3);
 }
 
 BOOST_AUTO_TEST_CASE(node_comparison_test8) {
-    key_type node(site_type(0, 0).index(0), site_type(1, 1).index(2));
-    key_type nodes[] = {
-        key_type(site_type(1, 0).index(1)),
-        key_type(site_type(1, 1).index(2)),
-        key_type(site_type(1, 2).index(3)),
-        key_type(site_type(1, 1).index(2), site_type(0, 0).index(0)),
-    };
-    bool res[] = {false, true, true, true};
-    CHECK_NODE_COMPARISON(node, nodes, res, 4);
+  key_type node(site_type(0, 0).index(0), site_type(1, 1).index(2));
+  key_type nodes[] = {
+    key_type(site_type(1, 0).index(1)),
+    key_type(site_type(1, 1).index(2)),
+    key_type(site_type(1, 2).index(3)),
+    key_type(site_type(1, 1).index(2), site_type(0, 0).index(0)),
+  };
+  bool res[] = {false, true, true, true};
+  CHECK_NODE_COMPARISON(node, nodes, res, 4);
 }
 
 BOOST_AUTO_TEST_CASE(circle_formation_predicate_test1) {
-    site_type site1(0, 0);
-    site_type site2(-8, 0);
-    site_type site3(0, 6);
-    CHECK_CIRCLE_FORMATION_PREDICATE(site1, site2, site3, -4.0, 3.0, 1.0);
+  site_type site1(0, 0);
+  site_type site2(-8, 0);
+  site_type site3(0, 6);
+  CHECK_CIRCLE_FORMATION_PREDICATE(site1, site2, site3, -4.0, 3.0, 1.0);
 }
 
 BOOST_AUTO_TEST_CASE(circle_formation_predicate_test2) {
-    int min_int = std::numeric_limits<int>::min();
-    int max_int = std::numeric_limits<int>::max();
-    site_type site1(min_int, min_int);
-    site_type site2(min_int, max_int);
-    site_type site3(max_int-1, max_int-1);
-    site_type site4(max_int, max_int);
-    CHECK_CIRCLE_EXISTENCE(site1, site2, site4, true);
-    CHECK_CIRCLE_EXISTENCE(site1, site3, site4, false);
+  int min_int = std::numeric_limits<int>::min();
+  int max_int = std::numeric_limits<int>::max();
+  site_type site1(min_int, min_int);
+  site_type site2(min_int, max_int);
+  site_type site3(max_int-1, max_int-1);
+  site_type site4(max_int, max_int);
+  CHECK_CIRCLE_EXISTENCE(site1, site2, site4, true);
+  CHECK_CIRCLE_EXISTENCE(site1, site3, site4, false);
 }
 
 BOOST_AUTO_TEST_CASE(circle_formation_predicate_test3) {
-    site_type site1(-4, 0);
-    site_type site2(0, 4);
-    site_type site3(site1.point0(), site2.point0());
-    CHECK_CIRCLE_EXISTENCE(site1, site3, site2, false);
-    site_type site4(-2, 0);
-    site_type site5(0, 2);
-    CHECK_CIRCLE_EXISTENCE(site3, site4, site5, false);
-    CHECK_CIRCLE_EXISTENCE(site4, site5, site3, false);
+  site_type site1(-4, 0);
+  site_type site2(0, 4);
+  site_type site3(site1.point0(), site2.point0());
+  CHECK_CIRCLE_EXISTENCE(site1, site3, site2, false);
+  site_type site4(-2, 0);
+  site_type site5(0, 2);
+  CHECK_CIRCLE_EXISTENCE(site3, site4, site5, false);
+  CHECK_CIRCLE_EXISTENCE(site4, site5, site3, false);
 }
 
 BOOST_AUTO_TEST_CASE(circle_formation_predicate_test4) {
-    site_type site1(-4, 0, -4, 20);
-    site_type site2(-2, 10);
-    site_type site3(4, 10);
-    CHECK_CIRCLE_FORMATION_PREDICATE(site1, site2, site3, 1.0, 6.0, 6.0);
-    CHECK_CIRCLE_FORMATION_PREDICATE(site3, site2, site1, 1.0, 14.0, 6.0);
+  site_type site1(-4, 0, -4, 20);
+  site_type site2(-2, 10);
+  site_type site3(4, 10);
+  CHECK_CIRCLE_FORMATION_PREDICATE(site1, site2, site3, 1.0, 6.0, 6.0);
+  CHECK_CIRCLE_FORMATION_PREDICATE(site3, site2, site1, 1.0, 14.0, 6.0);
 }
 
 BOOST_AUTO_TEST_CASE(circle_formation_predicate_test5) {
-    site_type site1(1, 0, 7, 0);
-    site1.inverse();
-    site_type site2(-2, 4, 10, 4);
-    site_type site3(6, 2);
-    site_type site4(1, 0);
-    CHECK_CIRCLE_FORMATION_PREDICATE(site3, site1, site2, 4.0, 2.0, 6.0);
-    CHECK_CIRCLE_FORMATION_PREDICATE(site4, site2, site1, 1.0, 2.0, 3.0);
+  site_type site1(1, 0, 7, 0);
+  site1.inverse();
+  site_type site2(-2, 4, 10, 4);
+  site_type site3(6, 2);
+  site_type site4(1, 0);
+  CHECK_CIRCLE_FORMATION_PREDICATE(site3, site1, site2, 4.0, 2.0, 6.0);
+  CHECK_CIRCLE_FORMATION_PREDICATE(site4, site2, site1, 1.0, 2.0, 3.0);
 }
 
 BOOST_AUTO_TEST_CASE(circle_formation_predicate_test6) {
-    site_type site1(-1, 2, 8, -10);
-    site1.inverse();
-    site_type site2(-1, 0, 8, 12);
-    site_type site3(1, 1);
-    CHECK_CIRCLE_FORMATION_PREDICATE(site3, site2, site1, 6.0, 1.0, 11.0);
+  site_type site1(-1, 2, 8, -10);
+  site1.inverse();
+  site_type site2(-1, 0, 8, 12);
+  site_type site3(1, 1);
+  CHECK_CIRCLE_FORMATION_PREDICATE(site3, site2, site1, 6.0, 1.0, 11.0);
 }
 
 BOOST_AUTO_TEST_CASE(circle_formation_predicate_test7) {
-    site_type site1(1, 0, 6, 0);
-    site1.inverse();
-    site_type site2(-6, 4, 0, 12);
-    site_type site3(1, 0);
-    CHECK_CIRCLE_FORMATION_PREDICATE(site3, site2, site1, 1.0, 5.0, 6.0);
+  site_type site1(1, 0, 6, 0);
+  site1.inverse();
+  site_type site2(-6, 4, 0, 12);
+  site_type site3(1, 0);
+  CHECK_CIRCLE_FORMATION_PREDICATE(site3, site2, site1, 1.0, 5.0, 6.0);
 }
 
 BOOST_AUTO_TEST_CASE(circle_formation_predicate_test8) {
-    site_type site1(1, 0, 5, 0);
-    site1.inverse();
-    site_type site2(0, 12, 8, 6);
-    site_type site3(1, 0);
-    CHECK_CIRCLE_FORMATION_PREDICATE(site3, site2, site1, 1.0, 5.0, 6.0);
+  site_type site1(1, 0, 5, 0);
+  site1.inverse();
+  site_type site2(0, 12, 8, 6);
+  site_type site3(1, 0);
+  CHECK_CIRCLE_FORMATION_PREDICATE(site3, site2, site1, 1.0, 5.0, 6.0);
 }
 
 BOOST_AUTO_TEST_CASE(circle_formation_predicate_test9) {
-    site_type site1(0, 0, 4, 0);
-    site_type site2(0, 0, 0, 4);
-    site_type site3(0, 4, 4, 4);
-    site1.inverse();
-    CHECK_CIRCLE_FORMATION_PREDICATE(site1, site2, site3, 2.0, 2.0, 4.0);
+  site_type site1(0, 0, 4, 0);
+  site_type site2(0, 0, 0, 4);
+  site_type site3(0, 4, 4, 4);
+  site1.inverse();
+  CHECK_CIRCLE_FORMATION_PREDICATE(site1, site2, site3, 2.0, 2.0, 4.0);
 }
 
 BOOST_AUTO_TEST_CASE(circle_formation_predicate_test10) {
-    site_type site1(1, 0, 41, 30);
-    site_type site2(-39, 30, 1, 60);
-    site_type site3(1, 60, 41, 30);
-    site1.inverse();
-    CHECK_CIRCLE_FORMATION_PREDICATE(site1, site2, site3, 1.0, 30.0, 25.0);
+  site_type site1(1, 0, 41, 30);
+  site_type site2(-39, 30, 1, 60);
+  site_type site3(1, 60, 41, 30);
+  site1.inverse();
+  CHECK_CIRCLE_FORMATION_PREDICATE(site1, site2, site3, 1.0, 30.0, 25.0);
 }

Modified: sandbox/gtl/libs/polygon/test/voronoi_robust_fpt_test.cpp
==============================================================================
--- sandbox/gtl/libs/polygon/test/voronoi_robust_fpt_test.cpp	(original)
+++ sandbox/gtl/libs/polygon/test/voronoi_robust_fpt_test.cpp	2012-05-01 08:43:51 EDT (Tue, 01 May 2012)
@@ -15,8 +15,8 @@
 #include <boost/random/mersenne_twister.hpp>
 #include <boost/test/test_case_template.hpp>
 
-#include "boost/polygon/detail/voronoi_ctypes.hpp"
-#include "boost/polygon/detail/voronoi_robust_fpt.hpp"
+#include <boost/polygon/detail/voronoi_ctypes.hpp>
+#include <boost/polygon/detail/voronoi_robust_fpt.hpp>
 using namespace boost::polygon::detail;
 
 typedef robust_fpt<double> rfpt_type;
@@ -25,319 +25,318 @@
 type_converter_fpt to_fpt;
 
 BOOST_AUTO_TEST_CASE(robust_fpt_constructors_test1) {
-    rfpt_type a = rfpt_type();
-    BOOST_CHECK_EQUAL(a.fpv(), 0.0);
-    BOOST_CHECK_EQUAL(a.re(), 0.0);
-    BOOST_CHECK_EQUAL(a.ulp(), 0);
+  rfpt_type a = rfpt_type();
+  BOOST_CHECK_EQUAL(a.fpv(), 0.0);
+  BOOST_CHECK_EQUAL(a.re(), 0.0);
+  BOOST_CHECK_EQUAL(a.ulp(), 0);
 }
 
 BOOST_AUTO_TEST_CASE(robust_fpt_constructors_test2) {
-    rfpt_type a(10.0, 1.0);
-    BOOST_CHECK_EQUAL(a.fpv(), 10.0);
-    BOOST_CHECK_EQUAL(a.re(), 1.0);
-    BOOST_CHECK_EQUAL(a.ulp(), 1.0);
+  rfpt_type a(10.0, 1.0);
+  BOOST_CHECK_EQUAL(a.fpv(), 10.0);
+  BOOST_CHECK_EQUAL(a.re(), 1.0);
+  BOOST_CHECK_EQUAL(a.ulp(), 1.0);
 }
 
 BOOST_AUTO_TEST_CASE(robust_fpt_constructors_test3) {
-    rfpt_type a(10.0);
-    BOOST_CHECK_EQUAL(a.fpv(), 10.0);
-    BOOST_CHECK_EQUAL(a.re(), 0.0);
-    BOOST_CHECK_EQUAL(a.ulp(), 0.0);
+  rfpt_type a(10.0);
+  BOOST_CHECK_EQUAL(a.fpv(), 10.0);
+  BOOST_CHECK_EQUAL(a.re(), 0.0);
+  BOOST_CHECK_EQUAL(a.ulp(), 0.0);
 }
 
 BOOST_AUTO_TEST_CASE(robust_fpt_constructors_test4) {
-    rfpt_type a(10.0, 3.0);
-    BOOST_CHECK_EQUAL(a.fpv(), 10.0);
-    BOOST_CHECK_EQUAL(a.re(), 3.0);
-    BOOST_CHECK_EQUAL(a.ulp(), 3.0);
-
-    rfpt_type b(10.0, 2.75);
-    BOOST_CHECK_EQUAL(b.fpv(), 10.0);
-    BOOST_CHECK_EQUAL(b.re(), 2.75);
-    BOOST_CHECK_EQUAL(b.ulp(), 2.75);
+  rfpt_type a(10.0, 3.0);
+  BOOST_CHECK_EQUAL(a.fpv(), 10.0);
+  BOOST_CHECK_EQUAL(a.re(), 3.0);
+  BOOST_CHECK_EQUAL(a.ulp(), 3.0);
+
+  rfpt_type b(10.0, 2.75);
+  BOOST_CHECK_EQUAL(b.fpv(), 10.0);
+  BOOST_CHECK_EQUAL(b.re(), 2.75);
+  BOOST_CHECK_EQUAL(b.ulp(), 2.75);
 }
 
 BOOST_AUTO_TEST_CASE(robust_fpt_sum_test1) {
-    rfpt_type a(2.0, 5.0);
-    rfpt_type b(3.0, 4.0);
-    rfpt_type c = a + b;
-    BOOST_CHECK_EQUAL(c.fpv(), 5.0);
-    BOOST_CHECK_EQUAL(c.re(), 6.0);
-    BOOST_CHECK_EQUAL(c.ulp(), 6.0);
-
-    c += b;
-    BOOST_CHECK_EQUAL(c.fpv(), 8.0);
-    BOOST_CHECK_EQUAL(c.re(), 7.0);
-    BOOST_CHECK_EQUAL(c.ulp(), 7.0);
+  rfpt_type a(2.0, 5.0);
+  rfpt_type b(3.0, 4.0);
+  rfpt_type c = a + b;
+  BOOST_CHECK_EQUAL(c.fpv(), 5.0);
+  BOOST_CHECK_EQUAL(c.re(), 6.0);
+  BOOST_CHECK_EQUAL(c.ulp(), 6.0);
+
+  c += b;
+  BOOST_CHECK_EQUAL(c.fpv(), 8.0);
+  BOOST_CHECK_EQUAL(c.re(), 7.0);
+  BOOST_CHECK_EQUAL(c.ulp(), 7.0);
 }
 
 BOOST_AUTO_TEST_CASE(robust_fpt_sum_test2) {
-    rfpt_type a(3.0, 2.0);
-    rfpt_type b(-2.0, 3.0);
-    rfpt_type c = a + b;
-    BOOST_CHECK_EQUAL(c.fpv(), 1.0);
-    BOOST_CHECK_EQUAL(c.re(), 13.0);
-    BOOST_CHECK_EQUAL(c.ulp(), 13.0);
-
-    c += b;
-    BOOST_CHECK_EQUAL(c.fpv(), -1.0);
-    BOOST_CHECK_EQUAL(c.re(), 20.0);
-    BOOST_CHECK_EQUAL(c.ulp(), 20.0);
+  rfpt_type a(3.0, 2.0);
+  rfpt_type b(-2.0, 3.0);
+  rfpt_type c = a + b;
+  BOOST_CHECK_EQUAL(c.fpv(), 1.0);
+  BOOST_CHECK_EQUAL(c.re(), 13.0);
+  BOOST_CHECK_EQUAL(c.ulp(), 13.0);
+
+  c += b;
+  BOOST_CHECK_EQUAL(c.fpv(), -1.0);
+  BOOST_CHECK_EQUAL(c.re(), 20.0);
+  BOOST_CHECK_EQUAL(c.ulp(), 20.0);
 }
 
 BOOST_AUTO_TEST_CASE(robust_fpt_dif_test1) {
-    rfpt_type a(2.0, 5.0);
-    rfpt_type b(-3.0, 4.0);
-    rfpt_type c = a - b;
-    BOOST_CHECK_EQUAL(c.fpv(), 5.0);
-    BOOST_CHECK_EQUAL(c.re(), 6.0);
-    BOOST_CHECK_EQUAL(c.ulp(), 6.0);
-
-    c -= b;
-    BOOST_CHECK_EQUAL(c.fpv(), 8.0);
-    BOOST_CHECK_EQUAL(c.re(), 7.0);
-    BOOST_CHECK_EQUAL(c.ulp(), 7.0);
+  rfpt_type a(2.0, 5.0);
+  rfpt_type b(-3.0, 4.0);
+  rfpt_type c = a - b;
+  BOOST_CHECK_EQUAL(c.fpv(), 5.0);
+  BOOST_CHECK_EQUAL(c.re(), 6.0);
+  BOOST_CHECK_EQUAL(c.ulp(), 6.0);
+
+  c -= b;
+  BOOST_CHECK_EQUAL(c.fpv(), 8.0);
+  BOOST_CHECK_EQUAL(c.re(), 7.0);
+  BOOST_CHECK_EQUAL(c.ulp(), 7.0);
 }
 
 BOOST_AUTO_TEST_CASE(robust_fpt_dif_test2) {
-    rfpt_type a(3.0, 2.0);
-    rfpt_type b(2.0, 3.0);
-    rfpt_type c = a - b;
-    BOOST_CHECK_EQUAL(c.fpv(), 1.0);
-    BOOST_CHECK_EQUAL(c.re(), 13.0);
-    BOOST_CHECK_EQUAL(c.ulp(), 13.0);
-
-    c -= b;
-    BOOST_CHECK_EQUAL(c.fpv(), -1.0);
-    BOOST_CHECK_EQUAL(c.re(), 20.0);
-    BOOST_CHECK_EQUAL(c.ulp(), 20.0);
+  rfpt_type a(3.0, 2.0);
+  rfpt_type b(2.0, 3.0);
+  rfpt_type c = a - b;
+  BOOST_CHECK_EQUAL(c.fpv(), 1.0);
+  BOOST_CHECK_EQUAL(c.re(), 13.0);
+  BOOST_CHECK_EQUAL(c.ulp(), 13.0);
+
+  c -= b;
+  BOOST_CHECK_EQUAL(c.fpv(), -1.0);
+  BOOST_CHECK_EQUAL(c.re(), 20.0);
+  BOOST_CHECK_EQUAL(c.ulp(), 20.0);
 }
 
 BOOST_AUTO_TEST_CASE(robust_fpt_mult_test3) {
-    rfpt_type a(2.0, 3.0);
-    rfpt_type b(4.0, 1.0);
-    rfpt_type c = a * b;
-    BOOST_CHECK_EQUAL(c.fpv(), 8.0);
-    BOOST_CHECK_EQUAL(c.re(), 5.0);
-    BOOST_CHECK_EQUAL(c.ulp(), 5.0);
-
-    c *= b;
-    BOOST_CHECK_EQUAL(c.fpv(), 32.0);
-    BOOST_CHECK_EQUAL(c.re(), 7.0);
-    BOOST_CHECK_EQUAL(c.ulp(), 7.0);
+  rfpt_type a(2.0, 3.0);
+  rfpt_type b(4.0, 1.0);
+  rfpt_type c = a * b;
+  BOOST_CHECK_EQUAL(c.fpv(), 8.0);
+  BOOST_CHECK_EQUAL(c.re(), 5.0);
+  BOOST_CHECK_EQUAL(c.ulp(), 5.0);
+
+  c *= b;
+  BOOST_CHECK_EQUAL(c.fpv(), 32.0);
+  BOOST_CHECK_EQUAL(c.re(), 7.0);
+  BOOST_CHECK_EQUAL(c.ulp(), 7.0);
 }
 
 BOOST_AUTO_TEST_CASE(robust_fpt_div_test1) {
-    rfpt_type a(2.0, 3.0);
-    rfpt_type b(4.0, 1.0);
-    rfpt_type c = a / b;
-    BOOST_CHECK_EQUAL(c.fpv(), 0.5);
-    BOOST_CHECK_EQUAL(c.re(), 5.0);
-    BOOST_CHECK_EQUAL(c.ulp(), 5.0);
-
-    c /= b;
-    BOOST_CHECK_EQUAL(c.fpv(), 0.125);
-    BOOST_CHECK_EQUAL(c.re(), 7.0);
-    BOOST_CHECK_EQUAL(c.ulp(), 7.0);
+  rfpt_type a(2.0, 3.0);
+  rfpt_type b(4.0, 1.0);
+  rfpt_type c = a / b;
+  BOOST_CHECK_EQUAL(c.fpv(), 0.5);
+  BOOST_CHECK_EQUAL(c.re(), 5.0);
+  BOOST_CHECK_EQUAL(c.ulp(), 5.0);
+
+  c /= b;
+  BOOST_CHECK_EQUAL(c.fpv(), 0.125);
+  BOOST_CHECK_EQUAL(c.re(), 7.0);
+  BOOST_CHECK_EQUAL(c.ulp(), 7.0);
 }
 
 BOOST_AUTO_TEST_CASE(robust_dif_constructors_test) {
-    robust_dif<int> rd1;
-    BOOST_CHECK_EQUAL(rd1.pos(), 0);
-    BOOST_CHECK_EQUAL(rd1.neg(), 0);
-    BOOST_CHECK_EQUAL(rd1.dif(), 0);
-
-    robust_dif<int> rd2(1);
-    BOOST_CHECK_EQUAL(rd2.pos(), 1);
-    BOOST_CHECK_EQUAL(rd2.neg(), 0);
-    BOOST_CHECK_EQUAL(rd2.dif(), 1);
-
-    robust_dif<int> rd3(-1);
-    BOOST_CHECK_EQUAL(rd3.pos(), 0);
-    BOOST_CHECK_EQUAL(rd3.neg(), 1);
-    BOOST_CHECK_EQUAL(rd3.dif(), -1);
-
-    robust_dif<int> rd4(1, 2);
-    BOOST_CHECK_EQUAL(rd4.pos(), 1);
-    BOOST_CHECK_EQUAL(rd4.neg(), 2);
-    BOOST_CHECK_EQUAL(rd4.dif(), -1);
+  robust_dif<int> rd1;
+  BOOST_CHECK_EQUAL(rd1.pos(), 0);
+  BOOST_CHECK_EQUAL(rd1.neg(), 0);
+  BOOST_CHECK_EQUAL(rd1.dif(), 0);
+
+  robust_dif<int> rd2(1);
+  BOOST_CHECK_EQUAL(rd2.pos(), 1);
+  BOOST_CHECK_EQUAL(rd2.neg(), 0);
+  BOOST_CHECK_EQUAL(rd2.dif(), 1);
+
+  robust_dif<int> rd3(-1);
+  BOOST_CHECK_EQUAL(rd3.pos(), 0);
+  BOOST_CHECK_EQUAL(rd3.neg(), 1);
+  BOOST_CHECK_EQUAL(rd3.dif(), -1);
+
+  robust_dif<int> rd4(1, 2);
+  BOOST_CHECK_EQUAL(rd4.pos(), 1);
+  BOOST_CHECK_EQUAL(rd4.neg(), 2);
+  BOOST_CHECK_EQUAL(rd4.dif(), -1);
 }
 
 BOOST_AUTO_TEST_CASE(robust_dif_operators_test1) {
-    robust_dif<int> a(5, 2), b(1, 10);
+  robust_dif<int> a(5, 2), b(1, 10);
+  int dif_a = a.dif();
+  int dif_b = b.dif();
+  robust_dif<int> sum = a + b;
+  robust_dif<int> dif = a - b;
+  robust_dif<int> mult = a * b;
+  robust_dif<int> umin = -a;
+  BOOST_CHECK_EQUAL(sum.dif(), dif_a + dif_b);
+  BOOST_CHECK_EQUAL(dif.dif(), dif_a - dif_b);
+  BOOST_CHECK_EQUAL(mult.dif(), dif_a * dif_b);
+  BOOST_CHECK_EQUAL(umin.dif(), -dif_a);
+}
+
+BOOST_AUTO_TEST_CASE(robust_dif_operators_test2) {
+  robust_dif<int> a(5, 2);
+  for (int b = -3; b <= 3; b += 6) {
     int dif_a = a.dif();
-    int dif_b = b.dif();
+    int dif_b = b;
     robust_dif<int> sum = a + b;
     robust_dif<int> dif = a - b;
     robust_dif<int> mult = a * b;
-    robust_dif<int> umin = -a;
+    robust_dif<int> div = a / b;
     BOOST_CHECK_EQUAL(sum.dif(), dif_a + dif_b);
     BOOST_CHECK_EQUAL(dif.dif(), dif_a - dif_b);
     BOOST_CHECK_EQUAL(mult.dif(), dif_a * dif_b);
-    BOOST_CHECK_EQUAL(umin.dif(), -dif_a);
-}
-
-BOOST_AUTO_TEST_CASE(robust_dif_operators_test2) {
-    robust_dif<int> a(5, 2);
-    for (int b = -3; b <= 3; b += 6) {
-        int dif_a = a.dif();
-        int dif_b = b;
-        robust_dif<int> sum = a + b;
-        robust_dif<int> dif = a - b;
-        robust_dif<int> mult = a * b;
-        robust_dif<int> div = a / b;
-        BOOST_CHECK_EQUAL(sum.dif(), dif_a + dif_b);
-        BOOST_CHECK_EQUAL(dif.dif(), dif_a - dif_b);
-        BOOST_CHECK_EQUAL(mult.dif(), dif_a * dif_b);
-        BOOST_CHECK_EQUAL(div.dif(), dif_a / dif_b);
-    }
+    BOOST_CHECK_EQUAL(div.dif(), dif_a / dif_b);
+  }
 }
 
 BOOST_AUTO_TEST_CASE(robust_dif_operators_test3) {
-    robust_dif<int> b(5, 2);
-    for (int a = -3; a <= 3; a += 6) {
-        int dif_a = a;
-        int dif_b = b.dif();
-        robust_dif<int> sum = a + b;
-        robust_dif<int> dif = a - b;
-        robust_dif<int> mult = a * b;
-        BOOST_CHECK_EQUAL(sum.dif(), dif_a + dif_b);
-        BOOST_CHECK_EQUAL(dif.dif(), dif_a - dif_b);
-        BOOST_CHECK_EQUAL(mult.dif(), dif_a * dif_b);
-    }
+  robust_dif<int> b(5, 2);
+  for (int a = -3; a <= 3; a += 6) {
+    int dif_a = a;
+    int dif_b = b.dif();
+    robust_dif<int> sum = a + b;
+    robust_dif<int> dif = a - b;
+    robust_dif<int> mult = a * b;
+    BOOST_CHECK_EQUAL(sum.dif(), dif_a + dif_b);
+    BOOST_CHECK_EQUAL(dif.dif(), dif_a - dif_b);
+    BOOST_CHECK_EQUAL(mult.dif(), dif_a * dif_b);
+  }
 }
 
 BOOST_AUTO_TEST_CASE(robust_dif_operators_test4) {
-    std::vector< robust_dif<int> > a4(4, robust_dif<int>(5, 2));
-    std::vector< robust_dif<int> > b4(4, robust_dif<int>(1, 2));
-    std::vector< robust_dif<int> > c4 = a4;
-    c4[0] += b4[0];
-    c4[1] -= b4[1];
-    c4[2] *= b4[2];
-    BOOST_CHECK_EQUAL(c4[0].dif(), a4[0].dif() + b4[0].dif());
-    BOOST_CHECK_EQUAL(c4[1].dif(), a4[1].dif() - b4[1].dif());
-    BOOST_CHECK_EQUAL(c4[2].dif(), a4[2].dif() * b4[2].dif());
-    a4[0] += b4[0].dif();
-    a4[1] -= b4[1].dif();
-    a4[2] *= b4[2].dif();
-    a4[3] /= b4[3].dif();
-    BOOST_CHECK_EQUAL(c4[0].dif(), a4[0].dif());
-    BOOST_CHECK_EQUAL(c4[1].dif(), a4[1].dif());
-    BOOST_CHECK_EQUAL(c4[2].dif(), a4[2].dif());
-    BOOST_CHECK_EQUAL(c4[3].dif() / b4[3].dif(), a4[3].dif());
+  std::vector< robust_dif<int> > a4(4, robust_dif<int>(5, 2));
+  std::vector< robust_dif<int> > b4(4, robust_dif<int>(1, 2));
+  std::vector< robust_dif<int> > c4 = a4;
+  c4[0] += b4[0];
+  c4[1] -= b4[1];
+  c4[2] *= b4[2];
+  BOOST_CHECK_EQUAL(c4[0].dif(), a4[0].dif() + b4[0].dif());
+  BOOST_CHECK_EQUAL(c4[1].dif(), a4[1].dif() - b4[1].dif());
+  BOOST_CHECK_EQUAL(c4[2].dif(), a4[2].dif() * b4[2].dif());
+  a4[0] += b4[0].dif();
+  a4[1] -= b4[1].dif();
+  a4[2] *= b4[2].dif();
+  a4[3] /= b4[3].dif();
+  BOOST_CHECK_EQUAL(c4[0].dif(), a4[0].dif());
+  BOOST_CHECK_EQUAL(c4[1].dif(), a4[1].dif());
+  BOOST_CHECK_EQUAL(c4[2].dif(), a4[2].dif());
+  BOOST_CHECK_EQUAL(c4[3].dif() / b4[3].dif(), a4[3].dif());
 }
 
 BOOST_AUTO_TEST_CASE(robust_sqrt_expr_test1) {
-    robust_sqrt_expr<int32, fpt64, to_fpt_type> sqrt_expr;
-    int32 A[1] = {10};
-    int32 B[1] = {100};
-    BOOST_CHECK_EQUAL(sqrt_expr.eval1(A, B), 100.0);
+  robust_sqrt_expr<int32, fpt64, to_fpt_type> sqrt_expr;
+  int32 A[1] = {10};
+  int32 B[1] = {100};
+  BOOST_CHECK_EQUAL(sqrt_expr.eval1(A, B), 100.0);
 }
 
 BOOST_AUTO_TEST_CASE(robust_sqrt_expr_test2) {
-    robust_sqrt_expr<int32, fpt64, to_fpt_type> sqrt_expr;
-    int32 A[2] = {10, 30};
-    int32 B[2] = {400, 100};
-    BOOST_CHECK_EQUAL(sqrt_expr.eval2(A, B), 500.0);
+  robust_sqrt_expr<int32, fpt64, to_fpt_type> sqrt_expr;
+  int32 A[2] = {10, 30};
+  int32 B[2] = {400, 100};
+  BOOST_CHECK_EQUAL(sqrt_expr.eval2(A, B), 500.0);
 }
 
 BOOST_AUTO_TEST_CASE(robust_sqrt_expr_test3) {
-    robust_sqrt_expr<int32, fpt64, to_fpt_type> sqrt_expr;
-    int32 A[2] = {10, -30};
-    int32 B[2] = {400, 100};
-    BOOST_CHECK_EQUAL(sqrt_expr.eval2(A, B), -100.0);
+  robust_sqrt_expr<int32, fpt64, to_fpt_type> sqrt_expr;
+  int32 A[2] = {10, -30};
+  int32 B[2] = {400, 100};
+  BOOST_CHECK_EQUAL(sqrt_expr.eval2(A, B), -100.0);
 }
 
 BOOST_AUTO_TEST_CASE(robust_sqrt_expr_test4) {
-    robust_sqrt_expr<int32, fpt64, to_fpt_type> sqrt_expr;
-    int32 A[3] = {10, 30, 20};
-    int32 B[3] = {4, 1, 9};
-    BOOST_CHECK_EQUAL(sqrt_expr.eval3(A, B), 110.0);
+  robust_sqrt_expr<int32, fpt64, to_fpt_type> sqrt_expr;
+  int32 A[3] = {10, 30, 20};
+  int32 B[3] = {4, 1, 9};
+  BOOST_CHECK_EQUAL(sqrt_expr.eval3(A, B), 110.0);
 }
 
 BOOST_AUTO_TEST_CASE(robust_sqrt_expr_test5) {
-    robust_sqrt_expr<int32, fpt64, to_fpt_type> sqrt_expr;
-    int32 A[3] = {10, 30, -20};
-    int32 B[3] = {4, 1, 9};
-    BOOST_CHECK_EQUAL(sqrt_expr.eval3(A, B), -10.0);
+  robust_sqrt_expr<int32, fpt64, to_fpt_type> sqrt_expr;
+  int32 A[3] = {10, 30, -20};
+  int32 B[3] = {4, 1, 9};
+  BOOST_CHECK_EQUAL(sqrt_expr.eval3(A, B), -10.0);
 }
 
 BOOST_AUTO_TEST_CASE(robust_sqrt_expr_test6) {
-    robust_sqrt_expr<int32, fpt64, to_fpt_type> sqrt_expr;
-    int32 A[4] = {10, 30, 20, 5};
-    int32 B[4] = {4, 1, 9, 16};
-    BOOST_CHECK_EQUAL(sqrt_expr.eval4(A, B), 130.0);
+  robust_sqrt_expr<int32, fpt64, to_fpt_type> sqrt_expr;
+  int32 A[4] = {10, 30, 20, 5};
+  int32 B[4] = {4, 1, 9, 16};
+  BOOST_CHECK_EQUAL(sqrt_expr.eval4(A, B), 130.0);
 }
 
 BOOST_AUTO_TEST_CASE(robust_sqrt_expr_test7) {
-    robust_sqrt_expr<int32, fpt64, to_fpt_type> sqrt_expr;
-    int32 A[4] = {10, 30, -20, -5};
-    int32 B[4] = {4, 1, 9, 16};
-    BOOST_CHECK_EQUAL(sqrt_expr.eval4(A, B), -30.0);
+  robust_sqrt_expr<int32, fpt64, to_fpt_type> sqrt_expr;
+  int32 A[4] = {10, 30, -20, -5};
+  int32 B[4] = {4, 1, 9, 16};
+  BOOST_CHECK_EQUAL(sqrt_expr.eval4(A, B), -30.0);
 }
 
 BOOST_AUTO_TEST_CASE(robust_sqrt_expr_test8) {
-    typedef extended_int<16> eint512;
-    robust_sqrt_expr<eint512, efpt64, to_efpt_type> sqrt_expr;
-    int32 A[4] = {1000, 3000, -2000, -500};
-    int32 B[4] = {400, 100, 900, 1600};
-    eint512 AA[4], BB[4];
-    for (size_t i = 0; i < 4; ++i) {
-        AA[i] = A[i];
-        BB[i] = B[i];
-    }
-    BOOST_CHECK_EQUAL(to_fpt(sqrt_expr.eval4(AA, BB)), -30000.0);
+  typedef extended_int<16> eint512;
+  robust_sqrt_expr<eint512, efpt64, to_efpt_type> sqrt_expr;
+  int32 A[4] = {1000, 3000, -2000, -500};
+  int32 B[4] = {400, 100, 900, 1600};
+  eint512 AA[4], BB[4];
+  for (size_t i = 0; i < 4; ++i) {
+    AA[i] = A[i];
+    BB[i] = B[i];
+  }
+  BOOST_CHECK_EQUAL(to_fpt(sqrt_expr.eval4(AA, BB)), -30000.0);
 }
 
 template <typename _int, typename _fpt>
 class sqrt_expr_tester {
 public:
-    static const size_t MX_SQRTS = 4;
+  static const size_t MX_SQRTS = 4;
 
-    bool run() {
-        static boost::mt19937 gen(static_cast<uint32>(time(NULL)));
-        bool ret_val = true;
-        for (size_t i = 0; i < MX_SQRTS; ++i) {
-            a[i] = gen() & 1048575;
-            int64 temp = gen() & 1048575;
-            b[i] = temp * temp;
-        }
-        uint32 mask = (1 << MX_SQRTS);
-        for (size_t i = 0; i < mask; i++) {
-            fpt64 expected_val = 0.0;
-            for (size_t j = 0; j < MX_SQRTS; j++) {
-                if (i & (1 << j)) {
-                    A[j] = a[j];
-                    B[j] = b[j];
-                    expected_val += static_cast<fpt64>(a[j]) *
-                                    sqrt(static_cast<fpt64>(b[j]));
-                } else {
-                    A[j] = -a[j];
-                    B[j] = b[j];
-                    expected_val -= static_cast<fpt64>(a[j]) *
-                                    sqrt(static_cast<fpt64>(b[j]));
-                }
-            }
-            fpt64 received_val = to_fpt(sqrt_expr_.eval4(A, B));
-            ret_val &= ulp_cmp(expected_val, received_val, 25) ==
-                       ulp_comparison<fpt64>::EQUAL;
+  bool run() {
+    static boost::mt19937 gen(static_cast<uint32>(time(NULL)));
+    bool ret_val = true;
+    for (size_t i = 0; i < MX_SQRTS; ++i) {
+      a[i] = gen() & 1048575;
+      int64 temp = gen() & 1048575;
+      b[i] = temp * temp;
+    }
+    uint32 mask = (1 << MX_SQRTS);
+    for (size_t i = 0; i < mask; i++) {
+      fpt64 expected_val = 0.0;
+      for (size_t j = 0; j < MX_SQRTS; j++) {
+        if (i & (1 << j)) {
+          A[j] = a[j];
+          B[j] = b[j];
+          expected_val += static_cast<fpt64>(a[j]) *
+                          sqrt(static_cast<fpt64>(b[j]));
+        } else {
+          A[j] = -a[j];
+          B[j] = b[j];
+          expected_val -= static_cast<fpt64>(a[j]) *
+                          sqrt(static_cast<fpt64>(b[j]));
         }
-        return ret_val;
+      }
+      fpt64 received_val = to_fpt(sqrt_expr_.eval4(A, B));
+      ret_val &= ulp_cmp(expected_val, received_val, 25) ==
+                 ulp_comparison<fpt64>::EQUAL;
     }
+    return ret_val;
+  }
 
 private:
-    robust_sqrt_expr<_int, _fpt, to_efpt_type> sqrt_expr_;
-    ulp_comparison<fpt64> ulp_cmp;
-    _int A[MX_SQRTS];
-    _int B[MX_SQRTS];
-    int64 a[MX_SQRTS];
-    int64 b[MX_SQRTS];
+  robust_sqrt_expr<_int, _fpt, to_efpt_type> sqrt_expr_;
+  ulp_comparison<fpt64> ulp_cmp;
+  _int A[MX_SQRTS];
+  _int B[MX_SQRTS];
+  int64 a[MX_SQRTS];
+  int64 b[MX_SQRTS];
 };
 
 BOOST_AUTO_TEST_CASE(mpz_sqrt_evaluator_test) {
-    typedef extended_int<16> eint512;
-    sqrt_expr_tester<eint512, efpt64> tester;
-    for (int i = 0; i < 2000; ++i) {
-        BOOST_CHECK(tester.run());
-    }
+  typedef extended_int<16> eint512;
+  sqrt_expr_tester<eint512, efpt64> tester;
+  for (int i = 0; i < 2000; ++i)
+    BOOST_CHECK(tester.run());
 }

Modified: sandbox/gtl/libs/polygon/test/voronoi_structures_test.cpp
==============================================================================
--- sandbox/gtl/libs/polygon/test/voronoi_structures_test.cpp	(original)
+++ sandbox/gtl/libs/polygon/test/voronoi_structures_test.cpp	2012-05-01 08:43:51 EDT (Tue, 01 May 2012)
@@ -10,7 +10,7 @@
 #define BOOST_TEST_MODULE voronoi_structures_test
 
 #include <boost/test/test_case_template.hpp>
-#include "boost/polygon/detail/voronoi_structures.hpp"
+#include <boost/polygon/detail/voronoi_structures.hpp>
 using namespace boost::polygon::detail;
 
 typedef point_2d<int> point_type;
@@ -21,113 +21,113 @@
 typedef beach_line_node_data<int, int> node_data_type;
 
 BOOST_AUTO_TEST_CASE(point_2d_test1) {
-    point_type p(1, 2);
-    BOOST_CHECK_EQUAL(p.x(), 1);
-    BOOST_CHECK_EQUAL(p.y(), 2);
-    p.x(3);
-    BOOST_CHECK_EQUAL(p.x(), 3);
-    p.y(4);
-    BOOST_CHECK_EQUAL(p.y(), 4);
+  point_type p(1, 2);
+  BOOST_CHECK_EQUAL(p.x(), 1);
+  BOOST_CHECK_EQUAL(p.y(), 2);
+  p.x(3);
+  BOOST_CHECK_EQUAL(p.x(), 3);
+  p.y(4);
+  BOOST_CHECK_EQUAL(p.y(), 4);
 }
 
 BOOST_AUTO_TEST_CASE(site_event_test2) {
-    site_type s(1, 2);
-    BOOST_CHECK(s.x0() == s.x1() && s.x1() == 1);
-    BOOST_CHECK(s.y0() == s.y1() && s.y1() == 2);
-    BOOST_CHECK(s.index() == 0);
-    BOOST_CHECK(!s.is_segment());
-    BOOST_CHECK(!s.is_inverse());
-    s.index(1);
-    BOOST_CHECK(s.index() == 1);
-    BOOST_CHECK(!s.is_inverse());
+  site_type s(1, 2);
+  BOOST_CHECK(s.x0() == s.x1() && s.x1() == 1);
+  BOOST_CHECK(s.y0() == s.y1() && s.y1() == 2);
+  BOOST_CHECK(s.index() == 0);
+  BOOST_CHECK(!s.is_segment());
+  BOOST_CHECK(!s.is_inverse());
+  s.index(1);
+  BOOST_CHECK(s.index() == 1);
+  BOOST_CHECK(!s.is_inverse());
 }
 
 BOOST_AUTO_TEST_CASE(site_event_test3) {
-    site_type s(1, 2, 3, 4);
-    BOOST_CHECK(s.x0(true) == 1 && s.x0() == 1);
-    BOOST_CHECK(s.y0(true) == 2 && s.y0() == 2);
-    BOOST_CHECK(s.x1(true) == 3 && s.x1() == 3);
-    BOOST_CHECK(s.y1(true) == 4 && s.y1() == 4);
-    BOOST_CHECK(s.index() == 0);
-    BOOST_CHECK(s.is_segment());
-    BOOST_CHECK(!s.is_inverse());
-    s.inverse();
-    BOOST_CHECK(s.x1(true) == 1 && s.x0() == 1);
-    BOOST_CHECK(s.y1(true) == 2 && s.y0() == 2);
-    BOOST_CHECK(s.x0(true) == 3 && s.x1() == 3);
-    BOOST_CHECK(s.y0(true) == 4 && s.y1() == 4);
-    BOOST_CHECK(s.is_inverse());
+  site_type s(1, 2, 3, 4);
+  BOOST_CHECK(s.x0(true) == 1 && s.x0() == 1);
+  BOOST_CHECK(s.y0(true) == 2 && s.y0() == 2);
+  BOOST_CHECK(s.x1(true) == 3 && s.x1() == 3);
+  BOOST_CHECK(s.y1(true) == 4 && s.y1() == 4);
+  BOOST_CHECK(s.index() == 0);
+  BOOST_CHECK(s.is_segment());
+  BOOST_CHECK(!s.is_inverse());
+  s.inverse();
+  BOOST_CHECK(s.x1(true) == 1 && s.x0() == 1);
+  BOOST_CHECK(s.y1(true) == 2 && s.y0() == 2);
+  BOOST_CHECK(s.x0(true) == 3 && s.x1() == 3);
+  BOOST_CHECK(s.y0(true) == 4 && s.y1() == 4);
+  BOOST_CHECK(s.is_inverse());
 }
 
 BOOST_AUTO_TEST_CASE(site_event_test4) {
-    site_type s(1, 2, 3, 4);
-    s.index(27);
-    BOOST_CHECK(s.is_initial());
-    BOOST_CHECK(s.has_initial_direction());
-    BOOST_CHECK(s.index() == 27);
-    s.inverse();
-    BOOST_CHECK(!s.has_initial_direction());
-    BOOST_CHECK(s.is_initial());
-    BOOST_CHECK(s.index() == 27);
-    s.change_initial_direction();
-    BOOST_CHECK(s.has_initial_direction());
-    BOOST_CHECK(!s.is_initial());
-    BOOST_CHECK(s.index() == 27);
+  site_type s(1, 2, 3, 4);
+  s.index(27);
+  BOOST_CHECK(s.is_initial());
+  BOOST_CHECK(s.has_initial_direction());
+  BOOST_CHECK(s.index() == 27);
+  s.inverse();
+  BOOST_CHECK(!s.has_initial_direction());
+  BOOST_CHECK(s.is_initial());
+  BOOST_CHECK(s.index() == 27);
+  s.change_initial_direction();
+  BOOST_CHECK(s.has_initial_direction());
+  BOOST_CHECK(!s.is_initial());
+  BOOST_CHECK(s.index() == 27);
 }
 
 BOOST_AUTO_TEST_CASE(circle_event_test) {
-    circle_type c(0, 1, 2);
-    BOOST_CHECK_EQUAL(c.x(), 0);
-    BOOST_CHECK_EQUAL(c.y(), 1);
-    BOOST_CHECK_EQUAL(c.lower_x(), 2);
-    BOOST_CHECK_EQUAL(c.lower_y(), 1);
-    BOOST_CHECK(c.is_active());
-    c.x(3);
-    c.y(4);
-    c.lower_x(5);
-    BOOST_CHECK_EQUAL(c.x(), 3);
-    BOOST_CHECK_EQUAL(c.y(), 4);
-    BOOST_CHECK_EQUAL(c.lower_x(), 5);
-    BOOST_CHECK_EQUAL(c.lower_y(), 4);
-    c.deactivate();
-    BOOST_CHECK(!c.is_active());
+  circle_type c(0, 1, 2);
+  BOOST_CHECK_EQUAL(c.x(), 0);
+  BOOST_CHECK_EQUAL(c.y(), 1);
+  BOOST_CHECK_EQUAL(c.lower_x(), 2);
+  BOOST_CHECK_EQUAL(c.lower_y(), 1);
+  BOOST_CHECK(c.is_active());
+  c.x(3);
+  c.y(4);
+  c.lower_x(5);
+  BOOST_CHECK_EQUAL(c.x(), 3);
+  BOOST_CHECK_EQUAL(c.y(), 4);
+  BOOST_CHECK_EQUAL(c.lower_x(), 5);
+  BOOST_CHECK_EQUAL(c.lower_y(), 4);
+  c.deactivate();
+  BOOST_CHECK(!c.is_active());
 }
 
 BOOST_AUTO_TEST_CASE(ordered_queue_test) {
-    ordered_queue_type q;
-    BOOST_CHECK(q.empty());
-    std::vector<int*> vi;
-    for (int i = 0; i < 20; ++i)
-        vi.push_back(&q.push(i));
-    for (int i = 0; i < 20; ++i)
-        *vi[i] <<= 1;
-    BOOST_CHECK(!q.empty());
-    for (int i = 0; i < 20; ++i, q.pop())
-        BOOST_CHECK_EQUAL(q.top(), i << 1);
-    BOOST_CHECK(q.empty());
+  ordered_queue_type q;
+  BOOST_CHECK(q.empty());
+  std::vector<int*> vi;
+  for (int i = 0; i < 20; ++i)
+    vi.push_back(&q.push(i));
+  for (int i = 0; i < 20; ++i)
+    *vi[i] <<= 1;
+  BOOST_CHECK(!q.empty());
+  for (int i = 0; i < 20; ++i, q.pop())
+    BOOST_CHECK_EQUAL(q.top(), i << 1);
+  BOOST_CHECK(q.empty());
 }
 
 BOOST_AUTO_TEST_CASE(beach_line_node_key_test) {
-    node_key_type key(1);
-    BOOST_CHECK_EQUAL(key.left_site(), 1);
-    BOOST_CHECK_EQUAL(key.right_site(), 1);
-    key.left_site(2);
-    BOOST_CHECK_EQUAL(key.left_site(), 2);
-    BOOST_CHECK_EQUAL(key.right_site(), 1);
-    key.right_site(3);
-    BOOST_CHECK_EQUAL(key.left_site(), 2);
-    BOOST_CHECK_EQUAL(key.right_site(), 3);
+  node_key_type key(1);
+  BOOST_CHECK_EQUAL(key.left_site(), 1);
+  BOOST_CHECK_EQUAL(key.right_site(), 1);
+  key.left_site(2);
+  BOOST_CHECK_EQUAL(key.left_site(), 2);
+  BOOST_CHECK_EQUAL(key.right_site(), 1);
+  key.right_site(3);
+  BOOST_CHECK_EQUAL(key.left_site(), 2);
+  BOOST_CHECK_EQUAL(key.right_site(), 3);
 }
 
 BOOST_AUTO_TEST_CASE(beach_line_node_data_test) {
-    node_data_type node_data(NULL);
-    BOOST_CHECK_EQUAL(node_data.edge() == NULL, true);
-    BOOST_CHECK_EQUAL(node_data.circle_event() == NULL, true);
-    int data = 4;
-    node_data.circle_event(&data);
-    BOOST_CHECK_EQUAL(node_data.edge() == NULL, true);
-    BOOST_CHECK_EQUAL(node_data.circle_event() == &data, true);
-    node_data.edge(&data);
-    BOOST_CHECK_EQUAL(node_data.edge() == &data, true);
-    BOOST_CHECK_EQUAL(node_data.circle_event() == &data, true);
+  node_data_type node_data(NULL);
+  BOOST_CHECK_EQUAL(node_data.edge() == NULL, true);
+  BOOST_CHECK_EQUAL(node_data.circle_event() == NULL, true);
+  int data = 4;
+  node_data.circle_event(&data);
+  BOOST_CHECK_EQUAL(node_data.edge() == NULL, true);
+  BOOST_CHECK_EQUAL(node_data.circle_event() == &data, true);
+  node_data.edge(&data);
+  BOOST_CHECK_EQUAL(node_data.edge() == &data, true);
+  BOOST_CHECK_EQUAL(node_data.circle_event() == &data, true);
 }

Modified: sandbox/gtl/libs/polygon/test/voronoi_test_helper.hpp
==============================================================================
--- sandbox/gtl/libs/polygon/test/voronoi_test_helper.hpp	(original)
+++ sandbox/gtl/libs/polygon/test/voronoi_test_helper.hpp	2012-05-01 08:43:51 EDT (Tue, 01 May 2012)
@@ -16,219 +16,255 @@
 #include <map>
 #include <vector>
 
+#include <boost/polygon/polygon.hpp>
+using namespace boost::polygon;
+
 namespace voronoi_test_helper {
 
 enum kOrientation {
-    RIGHT = -1,
-    COLLINEAR = 0,
-    LEFT = 1
+  RIGHT = -1,
+  COLLINEAR = 0,
+  LEFT = 1
 };
 
 template <typename Point2D>
 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)
-        return COLLINEAR;
-    return (a < b) ? RIGHT : LEFT;
+  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)
+    return COLLINEAR;
+  return (a < b) ? RIGHT : LEFT;
 }
 
 template <typename Output>
 bool verify_half_edge_orientation(const Output &output) {
-    typedef typename Output::point_type point_type;
-    typename Output::const_edge_iterator edge_it;
-    for (edge_it = output.edges().begin(); 
-         edge_it != output.edges().end(); edge_it++) {
-        if (edge_it->is_finite()) {
-            const point_type &site_point = edge_it->cell()->point0();
-            const point_type &start_point = edge_it->vertex0()->vertex();
-            const point_type &end_point = edge_it->vertex1()->vertex();
-            if (get_orientation(start_point, end_point, site_point) != LEFT)
-                return false;
-        }
+  typedef typename Output::point_type point_type;
+  typename Output::const_edge_iterator edge_it;
+  for (edge_it = output.edges().begin(); 
+       edge_it != output.edges().end(); edge_it++) {
+    if (edge_it->is_finite()) {
+      const point_type &site_point = edge_it->cell()->point0();
+      const point_type &start_point = edge_it->vertex0()->vertex();
+      const point_type &end_point = edge_it->vertex1()->vertex();
+      if (get_orientation(start_point, end_point, site_point) != LEFT)
+        return false;
     }
-    return true;
+  }
+  return true;
 }
 
 template <typename Output>
 bool verify_cell_convexity(const Output &output) {
-    typedef typename Output::point_type point_type;
-    typename Output::const_cell_iterator cell_it;
-    for (cell_it = output.cells().begin();
-         cell_it != output.cells().end(); cell_it++) {
-        const typename Output::edge_type *edge = cell_it->incident_edge();
-        if (edge)
-            do {
-                if (edge->next()->prev() != edge)
-                    return false;
-                if (edge->cell() != &(*cell_it))
-                    return false;
-                if (edge->vertex0() != NULL &&
-                    edge->vertex1() != NULL &&
-                    edge->vertex1() == edge->next()->vertex0() &&
-                    edge->next()->vertex1() != NULL) {
-                        const point_type &vertex1 = edge->vertex0()->vertex();
-                        const point_type &vertex2 = edge->vertex1()->vertex();
-                        const point_type &vertex3 = edge->next()->vertex1()->vertex();
-                        if (get_orientation(vertex1, vertex2, vertex3) != LEFT)
-                            return false;
-                }
-                edge = edge->next();
-            } while(edge != cell_it->incident_edge());
-    }
-    return true;
+  typedef typename Output::point_type point_type;
+  typename Output::const_cell_iterator cell_it;
+  for (cell_it = output.cells().begin();
+       cell_it != output.cells().end(); cell_it++) {
+    const typename Output::edge_type *edge = cell_it->incident_edge();
+    if (edge)
+      do {
+        if (edge->next()->prev() != edge)
+          return false;
+        if (edge->cell() != &(*cell_it))
+          return false;
+        if (edge->vertex0() != NULL &&
+            edge->vertex1() != NULL &&
+            edge->vertex1() == edge->next()->vertex0() &&
+            edge->next()->vertex1() != NULL) {
+          const point_type &vertex1 = edge->vertex0()->vertex();
+          const point_type &vertex2 = edge->vertex1()->vertex();
+          const point_type &vertex3 = edge->next()->vertex1()->vertex();
+          if (get_orientation(vertex1, vertex2, vertex3) != LEFT)
+            return false;
+        }
+        edge = edge->next();
+      } while(edge != cell_it->incident_edge());
+  }
+  return true;
 }
 
 template <typename Output>
 bool verify_incident_edges_ccw_order(const Output &output) {
-    typedef typename Output::point_type point_type;
-    typedef typename Output::edge_type voronoi_edge_type;
-    typename Output::const_vertex_iterator vertex_it;
-    for (vertex_it = output.vertices().begin();
-         vertex_it != output.vertices().end(); vertex_it++) {
-        if (vertex_it->is_degenerate())
-          continue;
-        const voronoi_edge_type *edge = vertex_it->incident_edge();
-        do {
-            const voronoi_edge_type *edge_next1 = edge->rot_next();
-            const voronoi_edge_type *edge_next2 = edge_next1->rot_next();
-            const point_type &site1 = edge->cell()->point0();
-            const point_type &site2 = edge_next1->cell()->point0();
-            const point_type &site3 = edge_next2->cell()->point0();
-
-            if (get_orientation(site1, site2, site3) != LEFT)
-                return false;
-
-            edge = edge->rot_next();
-        } while (edge != vertex_it->incident_edge());
-    }
-    return true;
+  typedef typename Output::point_type point_type;
+  typedef typename Output::edge_type voronoi_edge_type;
+  typename Output::const_vertex_iterator vertex_it;
+  for (vertex_it = output.vertices().begin();
+     vertex_it != output.vertices().end(); vertex_it++) {
+    if (vertex_it->is_degenerate())
+      continue;
+    const voronoi_edge_type *edge = vertex_it->incident_edge();
+    do {
+      const voronoi_edge_type *edge_next1 = edge->rot_next();
+      const voronoi_edge_type *edge_next2 = edge_next1->rot_next();
+      const point_type &site1 = edge->cell()->point0();
+      const point_type &site2 = edge_next1->cell()->point0();
+      const point_type &site3 = edge_next2->cell()->point0();
+
+      if (get_orientation(site1, site2, site3) != LEFT)
+        return false;
+
+      edge = edge->rot_next();
+    } while (edge != vertex_it->incident_edge());
+  }
+  return true;
 }
 
 template <typename P>
 struct cmp {
-    bool operator()(const P& p1, const P& p2) const {
-        if (p1.x() != p2.x()) return p1.x() < p2.x();
-        return p1.y() < p2.y();
-    }
+  bool operator()(const P& p1, const P& p2) const {
+    if (p1.x() != p2.x()) 
+      return p1.x() < p2.x();
+    return p1.y() < p2.y();
+  }
 };
 
 template <typename Output>
 bool verfiy_no_line_edge_intersections(const Output &output) {
-    // Create map from edges with first point less than the second one.
-    // Key is the first point of the edge, value is a vector of second points
-    // with the same first point.
-    typedef typename Output::point_type point_type;
-    cmp<point_type> comparator;
-    std::map< point_type, std::vector<point_type>, cmp<point_type> > edge_map;
-    typename Output::const_edge_iterator edge_it;
-    for (edge_it = output.edges().begin();
-         edge_it != output.edges().end(); edge_it++) {
-        if (edge_it->is_finite()) {
-            const point_type &vertex0 = edge_it->vertex0()->vertex();
-            const point_type &vertex1 = edge_it->vertex1()->vertex();
-            if (comparator(vertex0, vertex1))
-                edge_map[vertex0].push_back(vertex1);
-        }
+  // Create map from edges with first point less than the second one.
+  // Key is the first point of the edge, value is a vector of second points
+  // with the same first point.
+  typedef typename Output::point_type point_type;
+  cmp<point_type> comparator;
+  std::map< point_type, std::vector<point_type>, cmp<point_type> > edge_map;
+  typename Output::const_edge_iterator edge_it;
+  for (edge_it = output.edges().begin();
+       edge_it != output.edges().end(); edge_it++) {
+    if (edge_it->is_finite()) {
+        const point_type &vertex0 = edge_it->vertex0()->vertex();
+        const point_type &vertex1 = edge_it->vertex1()->vertex();
+      if (comparator(vertex0, vertex1))
+        edge_map[vertex0].push_back(vertex1);
     }
-    return !intersection_check(edge_map);
+  }
+  return !intersection_check(edge_map);
 }
 
 template <typename Point2D>
 bool intersection_check(const std::map< Point2D, std::vector<Point2D>, cmp<Point2D> > &edge_map) {
-    // Iterate over map of edges and check if there are any intersections.
-    // All the edges are stored by the low x value. That's why we iterate
-    // left to right checking for intersections between all pairs of edges
-    // that overlap in the x dimension.
-    // Complexity. Approximately N*sqrt(N). Worst case N^2.
-    typedef Point2D point_type;
-    typedef typename point_type::coordinate_type coordinate_type;
-    typedef typename std::map< point_type, std::vector<point_type>, cmp<Point2D> >::const_iterator
-        edge_map_iterator;
-    typedef typename std::vector<point_type>::size_type size_type;
-    edge_map_iterator edge_map_it1, edge_map_it2, edge_map_it_bound;
-    for (edge_map_it1 = edge_map.begin();
-         edge_map_it1 != edge_map.end(); edge_map_it1++) {
-        const point_type &point1 = edge_map_it1->first;
-        for (size_type i = 0; i < edge_map_it1->second.size(); i++) {
-            const point_type &point2 = edge_map_it1->second[i];
-            coordinate_type min_y1 = std::min(point1.y(), point2.y());
-            coordinate_type max_y1 = std::max(point1.y(), point2.y());
-
-            // Find the first edge with greater or equal first point.
-            edge_map_it_bound = edge_map.lower_bound(point2);
-
-            edge_map_it2 = edge_map_it1;
-            edge_map_it2++;
-            for (; edge_map_it2 != edge_map_it_bound; edge_map_it2++) {
-                const point_type &point3 = edge_map_it2->first;
-                for (size_type j = 0; j < edge_map_it2->second.size(); j++) {
-                    const point_type &point4 = edge_map_it2->second[j];
-                    coordinate_type min_y2 = std::min(point3.y(), point4.y());
-                    coordinate_type max_y2 = std::max(point3.y(), point4.y());
-                    
-                    // In most cases it is enought to make 
-                    // simple intersection check in the y dimension.
-                    if (!(max_y1 > min_y2 && max_y2 > min_y1))
-                        continue;
-
-                    // Intersection check.
-                    if (get_orientation(point1, point2, point3) *
-                        get_orientation(point1, point2, point4) == RIGHT &&
-                        get_orientation(point3, point4, point1) *
-                        get_orientation(point3, point4, point2) == RIGHT)
-                        return true;
-                }
-            }
+  // Iterate over map of edges and check if there are any intersections.
+  // All the edges are stored by the low x value. That's why we iterate
+  // left to right checking for intersections between all pairs of edges
+  // that overlap in the x dimension.
+  // Complexity. Approximately N*sqrt(N). Worst case N^2.
+  typedef Point2D point_type;
+  typedef typename point_type::coordinate_type coordinate_type;
+  typedef typename std::map< point_type, std::vector<point_type>, cmp<Point2D> >::const_iterator
+      edge_map_iterator;
+  typedef typename std::vector<point_type>::size_type size_type;
+  edge_map_iterator edge_map_it1, edge_map_it2, edge_map_it_bound;
+  for (edge_map_it1 = edge_map.begin();
+       edge_map_it1 != edge_map.end(); edge_map_it1++) {
+    const point_type &point1 = edge_map_it1->first;
+    for (size_type i = 0; i < edge_map_it1->second.size(); i++) {
+      const point_type &point2 = edge_map_it1->second[i];
+      coordinate_type min_y1 = std::min(point1.y(), point2.y());
+      coordinate_type max_y1 = std::max(point1.y(), point2.y());
+
+      // Find the first edge with greater or equal first point.
+      edge_map_it_bound = edge_map.lower_bound(point2);
+
+      edge_map_it2 = edge_map_it1;
+      edge_map_it2++;
+      for (; edge_map_it2 != edge_map_it_bound; edge_map_it2++) {
+        const point_type &point3 = edge_map_it2->first;
+        for (size_type j = 0; j < edge_map_it2->second.size(); j++) {
+          const point_type &point4 = edge_map_it2->second[j];
+          coordinate_type min_y2 = std::min(point3.y(), point4.y());
+          coordinate_type max_y2 = std::max(point3.y(), point4.y());
+          
+          // In most cases it is enought to make 
+          // simple intersection check in the y dimension.
+          if (!(max_y1 > min_y2 && max_y2 > min_y1))
+            continue;
+
+          // Intersection check.
+          if (get_orientation(point1, point2, point3) *
+              get_orientation(point1, point2, point4) == RIGHT &&
+              get_orientation(point3, point4, point1) *
+              get_orientation(point3, point4, point2) == RIGHT)
+            return true;
         }
+      }
     }
-    return false;
+  }
+  return false;
 }
 
 enum kVerification {
-    HALF_EDGE_ORIENTATION = 1,
-    CELL_CONVEXITY = 2,
-    INCIDENT_EDGES_CCW_ORDER = 4,
-    NO_HALF_EDGE_INTERSECTIONS = 8,
-    FAST_VERIFICATION = 7,
-    COMPLETE_VERIFICATION = 15
+  HALF_EDGE_ORIENTATION = 1,
+  CELL_CONVEXITY = 2,
+  INCIDENT_EDGES_CCW_ORDER = 4,
+  NO_HALF_EDGE_INTERSECTIONS = 8,
+  FAST_VERIFICATION = 7,
+  COMPLETE_VERIFICATION = 15
 };
 
 template <typename Output>
 bool verify_output(const Output &output, kVerification mask) {
-    bool result = true;
-    if (mask & HALF_EDGE_ORIENTATION)
-        result &= verify_half_edge_orientation(output);
-    if (mask & CELL_CONVEXITY)
-        result &= verify_cell_convexity(output);
-    if (mask & INCIDENT_EDGES_CCW_ORDER)
-        result &= verify_incident_edges_ccw_order(output);
-    if (mask & NO_HALF_EDGE_INTERSECTIONS)
-        result &= verfiy_no_line_edge_intersections(output);
-    return result;
+  bool result = true;
+  if (mask & HALF_EDGE_ORIENTATION)
+    result &= verify_half_edge_orientation(output);
+  if (mask & CELL_CONVEXITY)
+    result &= verify_cell_convexity(output);
+  if (mask & INCIDENT_EDGES_CCW_ORDER)
+    result &= verify_incident_edges_ccw_order(output);
+  if (mask & NO_HALF_EDGE_INTERSECTIONS)
+    result &= verfiy_no_line_edge_intersections(output);
+  return result;
 }
 
 template <typename PointIterator>
 void save_points(PointIterator first, PointIterator last, const char *file_name) {
-    std::ofstream ofs(file_name);
-    ofs << std::distance(first, last) << std::endl;
-    for (PointIterator it = first; it != last; ++it) {
-        ofs << it->x() << " " << it->y() << std::endl;
-    }
-    ofs.close();
+  std::ofstream ofs(file_name);
+  ofs << std::distance(first, last) << std::endl;
+  for (PointIterator it = first; it != last; ++it) {
+    ofs << it->x() << " " << it->y() << std::endl;
+  }
+  ofs.close();
 }
 
 template <typename SegmentIterator>
 void save_segments(SegmentIterator first, SegmentIterator last, const char *file_name) {
-    std::ofstream ofs(file_name);
-    ofs << std::distance(first, last) << std::endl;
-    for (SegmentIterator it = first; it != last; ++it) {
-        ofs << it->low().x() << " " << it->low().y() << " ";
-        ofs << it->high().x() << " " << it->high().y() << std::endl;
-    }
-    ofs.close();
+  std::ofstream ofs(file_name);
+  ofs << std::distance(first, last) << std::endl;
+  for (SegmentIterator it = first; it != last; ++it) {
+    ofs << it->low().x() << " " << it->low().y() << " ";
+    ofs << it->high().x() << " " << it->high().y() << std::endl;
+  }
+  ofs.close();
+}
+
+template <typename T>
+void clean_segment_set(std::vector< segment_data<T> > &data) {
+  typedef T Unit;
+  typedef typename scanline_base<Unit>::Point Point;
+  typedef typename scanline_base<Unit>::half_edge half_edge;
+  typedef int segment_id;
+  std::vector<std::pair<half_edge, segment_id> > half_edges;
+  std::vector<std::pair<half_edge, segment_id> > half_edges_out;
+  segment_id id = 0;
+  half_edges.reserve(data.size());
+  for(std::vector< segment_data<T> >::iterator it = data.begin(); it != data.end(); ++it) {
+    Point l = it->low();
+    Point h = it->high();
+    half_edges.push_back(std::make_pair(half_edge(l, h), id++));
+  }
+  half_edges_out.reserve(half_edges.size());
+  //apparently no need to pre-sort data when calling validate_scan
+  line_intersection<Unit>::validate_scan(half_edges_out, half_edges.begin(), half_edges.end());
+  std::vector< segment_data<T> > result;
+  result.reserve(half_edges_out.size());
+  for(std::size_t i = 0; i < half_edges_out.size(); ++i) {
+    id = half_edges_out[i].second;
+    Point l = half_edges_out[i].first.first;
+    Point h = half_edges_out[i].first.second;
+    segment_data<T> orig_seg = data[id];
+    if(orig_seg.high() < orig_seg.low())
+      std::swap(l, h);
+    result.push_back(segment_data<T>(l, h));
+  }
+  std::swap(result, data);
 }
 
 } // voronoi_test_helper