Boost logo

Boost-Commit :

Subject: [Boost-commit] svn:boost r63209 - in sandbox/SOC/2010/sweepline: boost/sweepline boost/sweepline/detail libs/sweepline/test
From: sydorchuk.andriy_at_[hidden]
Date: 2010-06-21 17:49:50


Author: asydorchuk
Date: 2010-06-21 17:49:48 EDT (Mon, 21 Jun 2010)
New Revision: 63209
URL: http://svn.boost.org/trac/boost/changeset/63209

Log:
Added larger voronoi builder unit tests.
Fixed circle events queue comparison.
Changed circle events structure.
Text files modified:
   sandbox/SOC/2010/sweepline/boost/sweepline/detail/voronoi_formation.hpp | 81 +++++++++++++++++----
   sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_builder.hpp | 45 +++++------
   sandbox/SOC/2010/sweepline/libs/sweepline/test/event_queue_test.cpp | 13 ++
   sandbox/SOC/2010/sweepline/libs/sweepline/test/event_types_test.cpp | 11 ++
   sandbox/SOC/2010/sweepline/libs/sweepline/test/node_comparer_test.cpp | 2
   sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_builder_test.cpp | 152 ++++++++++++++++++++++++++++++++++++---
   6 files changed, 246 insertions(+), 58 deletions(-)

Modified: sandbox/SOC/2010/sweepline/boost/sweepline/detail/voronoi_formation.hpp
==============================================================================
--- sandbox/SOC/2010/sweepline/boost/sweepline/detail/voronoi_formation.hpp (original)
+++ sandbox/SOC/2010/sweepline/boost/sweepline/detail/voronoi_formation.hpp 2010-06-21 17:49:48 EDT (Mon, 21 Jun 2010)
@@ -196,10 +196,18 @@
 
         bool equals(const circle_event &c_event) const {
             return center_.x() == c_event.x() && center_.y() == c_event.y() &&
- sqr_radius_ == c_event.get_sqr_radius();
+ sqr_radius_ == c_event.get_sqr_radius() &&
+ sites_[0] == c_event.sites_[0] &&
+ sites_[1] == c_event.sites_[1] &&
+ sites_[2] == c_event.sites_[2];
         }
 
         bool operator==(const circle_event &c_event) const {
+ if (sites_[0] != c_event.sites_[0] ||
+ sites_[1] != c_event.sites_[1] ||
+ sites_[2] != c_event.sites_[2])
+ return false;
+
             if (center_.y() != c_event.y())
                 return false;
 
@@ -234,30 +242,58 @@
                 if (sqr_r2 <= sqr_r1)
                     return false;
                 
- if (sqr_dif_x >= sum_r_sqr)
+ if (sqr_dif_x > sum_r_sqr)
                     return false;
 
- if (value_left == value_right)
- return y1 < y2;
- else
+ if (value_left != value_right)
                     return value_left > value_right;
+
+ if (y1 != y2)
+ return y1 < y2;
+
+ if (sites_[0] != c_event.sites_[0])
+ return sites_[0] < c_event.sites_[0];
+
+ if (sites_[1] != c_event.sites_[1])
+ return sites_[1] < c_event.sites_[1];
+
+ return sites_[2] < c_event.sites_[2];
             }
             else if (x1 < x2) {
                 if (sqr_r1 <= sqr_r2)
                     return true;
 
- if (sqr_dif_x >= sum_r_sqr)
+ if (sqr_dif_x > sum_r_sqr)
                     return true;
 
- if (value_left == value_right)
- return y1 < y2;
- else
+ if (value_left != value_right)
                     return value_left < value_right;
+
+ if (y1 != y2)
+ return y1 < y2;
+
+ if (sites_[0] != c_event.sites_[0])
+ return sites_[0] < c_event.sites_[0];
+
+ if (sites_[1] != c_event.sites_[1])
+ return sites_[1] < c_event.sites_[1];
+
+ return sites_[2] < c_event.sites_[2];
             }
             else {
                 if (sqr_r1 != sqr_r2)
                     return sqr_r1 < sqr_r2;
- return y1 < y2;
+
+ if (y1 != y2)
+ return y1 < y2;
+
+ if (sites_[0] != c_event.sites_[0])
+ return sites_[0] < c_event.sites_[0];
+
+ if (sites_[1] != c_event.sites_[1])
+ return sites_[1] < c_event.sites_[1];
+
+ return sites_[2] < c_event.sites_[2];
             }
         }
 
@@ -309,13 +345,27 @@
             bisector_node_ = iterator;
         }
 
+ void set_sites(const site_event<T> site1,
+ const site_event<T> site2,
+ const site_event<T> site3) {
+ sites_[0] = site1;
+ sites_[1] = site2;
+ sites_[2] = site3;
+ }
+
         const beach_line_iterator &get_bisector() const {
             return bisector_node_;
         }
+
+ const site_event<T>* get_sites() {
+ return sites;
+ }
+
     private:
         point_2d<T> center_;
         T sqr_radius_;
         beach_line_iterator bisector_node_;
+ site_event<T> sites_[3];
     };
 
     template <typename T>
@@ -538,22 +588,21 @@
             return true;
         }
 
- circle_event_type &top() {
+ circle_event_type top() {
             remove_not_active_events();
             return circle_events_.top();
         }
 
         void pop() {
- remove_not_active_events();
             circle_events_.pop();
         }
 
- void push(const circle_event_type &circle_event) {
- circle_events_.push(circle_event);
+ void push(const circle_event_type &c_event) {
+ circle_events_.push(c_event);
         }
 
- void deactivate_event(const circle_event_type &circle_event) {
- deactivated_events_.push(circle_event);
+ void deactivate_event(const circle_event_type &c_event) {
+ deactivated_events_.push(c_event);
         }
 
     private:

Modified: sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_builder.hpp
==============================================================================
--- sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_builder.hpp (original)
+++ sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_builder.hpp 2010-06-21 17:49:48 EDT (Mon, 21 Jun 2010)
@@ -97,15 +97,17 @@
                     process_site_event(*site_events_iterator_);
                     site_events_iterator_++;
                 } else if (site_events_iterator_ == site_events_.end()) {
- process_circle_event(circle_events_.top());
+ circle_event<T> c_event = circle_events_.top();
                     circle_events_.pop();
+ process_circle_event(c_event);
                 } else {
                     if (circle_events_.top().compare(*site_events_iterator_) >= 0) {
                         process_site_event(*site_events_iterator_);
                         site_events_iterator_++;
                     } else {
- process_circle_event(circle_events_.top());
+ circle_event<T> c_event = circle_events_.top();
                         circle_events_.pop();
+ process_circle_event(c_event);
                     }
                 }
             }
@@ -208,25 +210,24 @@
                                       new_node_it);
             } else {
                 site_arc = it->first.get_left_site();
-
- // Insert new arc into the sweepline.
- beach_line_iterator new_node_it = insert_new_arc(site_arc, site_event);
-
                 const site_event_type &site2 = it->first.get_left_site();
                 const site_event_type &site3 = it->first.get_right_site();
                 it--;
- const site_event_type &site1 = it->first.get_right_site();
-
+ const site_event_type &site1 = it->first.get_left_site();
+
                 // Remove candidate circle from the event queue.
                 deactivate_circle_event(site1, site2, site3);
 
+ // Insert new arc into the sweepline.
+ beach_line_iterator new_node_it = insert_new_arc(site_arc, site_event);
+
                 // Add candidate circles to the event queue.
                 new_node_it--;
                 activate_circle_event(site1, site2, site_event, new_node_it);
                 new_node_it++;
                 new_node_it++;
                 activate_circle_event(site_event, site2, site3, new_node_it);
- }
+ }
         }
 
         // Doesn't use special comparison function as it works fine only for
@@ -258,8 +259,9 @@
             // (B, C) bisector and change (A, B) bisector to the (A, C). That's
             // why we use const_cast there and take all the responsibility that
             // map data structure keeps correct ordering.
- const_cast<Key &>(it_first->first).set_right_site(it_last->first.get_right_site());
- edge_type *edge = output_.insert_new_edge(site1, site2, site3, circle_event, bisector1.edge, bisector2.edge);
+ const_cast<Key &>(it_first->first).set_right_site(site3);
+ edge_type *edge = output_.insert_new_edge(site1, site2, site3, circle_event,
+ bisector1.edge, bisector2.edge);
             const_cast<Value &>(it_first->second).change_edge(edge);
             beach_line_.erase(it_last);
             it_last = it_first;
@@ -269,13 +271,8 @@
             if (it_first != beach_line_.begin()) {
                 it_first--;
                 const site_event_type &site_l1 = it_first->first.get_left_site();
- deactivate_circle_event(site_l1, site1, site3);
- if (it_first != beach_line_.begin()) {
- it_first--;
- const site_event_type &site_l2 = it_first->first.get_left_site();
- it_first++;
- activate_circle_event(site_l2, site_l1, site1, it_first);
- }
+ deactivate_circle_event(site_l1, site1, site2);
+ activate_circle_event(site_l1, site1, site3, it_last);
             }
 
             // Check the new triplets formed by the neighboring arcs
@@ -283,13 +280,10 @@
             it_last++;
             if (it_last != beach_line_.end()) {
                 const site_event_type &site_r1 = it_last->first.get_right_site();
- deactivate_circle_event(site1, site3, site_r1);
- it_last++;
- if (it_last != beach_line_.end()) {
- const site_event_type &site_r2 = it_last->first.get_right_site();
- activate_circle_event(site3, site_r1, site_r2, it_last);
- }
- }
+ deactivate_circle_event(site2, site3, site_r1);
+ activate_circle_event(site1, site3, site_r1, it_last);
+ }
+
         }
 
         // Insert new arc below site arc into the beach line.
@@ -330,6 +324,7 @@
                                          (c_y-site1.y())*(c_y-site1.y());
             // Create new circle event;
             c_event = make_circle_event(c_x, c_y, sqr_radius);
+ c_event.set_sites(site1, site2, site3);
             return true;
         }
 

Modified: sandbox/SOC/2010/sweepline/libs/sweepline/test/event_queue_test.cpp
==============================================================================
--- sandbox/SOC/2010/sweepline/libs/sweepline/test/event_queue_test.cpp (original)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/test/event_queue_test.cpp 2010-06-21 17:49:48 EDT (Mon, 21 Jun 2010)
@@ -8,7 +8,7 @@
 // See http://www.boost.org for updates, documentation, and revision history.
 
 #include "test_type_list.hpp"
-#include <boost/sweepline/detail/voronoi_formation.hpp>
+#include "boost/sweepline/detail/voronoi_formation.hpp"
 using namespace boost::sweepline::detail;
 
 #define BOOST_TEST_MODULE event_queue_test
@@ -41,17 +41,24 @@
 
 BOOST_AUTO_TEST_CASE_TEMPLATE(event_queue_test2, T, test_types) {
     circle_events_queue< point_2d<T> > event_q;
+ site_event<T> temp_site = make_site_event(static_cast<T>(0),
+ static_cast<T>(0),
+ 0);
 
     for (int i = 0; i < 10; i++) {
         T x = static_cast<T>(10-i);
         T y = static_cast<T>(10-i);
- event_q.push(make_circle_event(x, y, static_cast<T>(0)));
+ circle_event<T> &c = make_circle_event(x, y, static_cast<T>(0));
+ c.set_sites(temp_site, temp_site, temp_site);
+ event_q.push(c);
     }
 
     for (int i = 0; i < 5; i++) {
         T x = static_cast<T>(10-2*i-1);
         T y = static_cast<T>(10-2*i-1);
- event_q.deactivate_event(make_circle_event(x, y, static_cast<T>(0)));
+ circle_event<T> &c = make_circle_event(x, y, static_cast<T>(0));
+ c.set_sites(temp_site, temp_site, temp_site);
+ event_q.deactivate_event(c);
     }
 
     for (int i = 0; i < 5; i++) {

Modified: sandbox/SOC/2010/sweepline/libs/sweepline/test/event_types_test.cpp
==============================================================================
--- sandbox/SOC/2010/sweepline/libs/sweepline/test/event_types_test.cpp (original)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/test/event_types_test.cpp 2010-06-21 17:49:48 EDT (Mon, 21 Jun 2010)
@@ -8,7 +8,7 @@
 // See http://www.boost.org for updates, documentation, and revision history.
 
 #include "test_type_list.hpp"
-#include <boost/sweepline/detail/voronoi_formation.hpp>
+#include "boost/sweepline/detail/voronoi_formation.hpp"
 using namespace boost::sweepline::detail;
 
 #define BOOST_TEST_MODULE event_types_test
@@ -69,6 +69,10 @@
     circle_event<T> circle1 = make_circle_event<T>(static_cast<T>(1),
                                                    static_cast<T>(2),
                                                    static_cast<T>(4));
+ site_event<T> temp_site = make_site_event<T>(static_cast<T>(0),
+ static_cast<T>(0),
+ 0);
+ circle1.set_sites(temp_site, temp_site, temp_site);
     circle_event<T> circle2;
     
     BOOST_CHECK_EQUAL(circle1.x(), static_cast<T>(1));
@@ -78,18 +82,21 @@
     circle2 = make_circle_event<T>(static_cast<T>(1),
                                    static_cast<T>(2),
                                    static_cast<T>(4));
+ circle2.set_sites(temp_site, temp_site, temp_site);
     bool arr1[] = { false, false, true, true, true, false };
     EVENT_TYPES_CHECK_COMPARISON(circle1, circle2, arr1);
 
     circle2 = make_circle_event<T>(static_cast<T>(1),
                                    static_cast<T>(3),
                                    static_cast<T>(4));
+ circle2.set_sites(temp_site, temp_site, temp_site);
     bool arr2[] = { true, false, true, false, false, true };
     EVENT_TYPES_CHECK_COMPARISON(circle1, circle2, arr2);
 
     circle2 = make_circle_event<T>(static_cast<T>(1),
                                    static_cast<T>(2),
                                    static_cast<T>(5));
+ circle2.set_sites(temp_site, temp_site, temp_site);
     bool arr3[] = { true, false, true, false, false, true };
     EVENT_TYPES_CHECK_COMPARISON(circle1, circle2, arr3);
 
@@ -97,12 +104,14 @@
     circle2 = make_circle_event<T>(static_cast<T>(0),
                                    static_cast<T>(2),
                                    static_cast<T>(4));
+ circle2.set_sites(temp_site, temp_site, temp_site);
     bool arr4[] = { false, true, false, true, false, true };
     EVENT_TYPES_CHECK_COMPARISON(circle1, circle2, arr4);
 
     circle2 = make_circle_event<T>(static_cast<T>(0),
                                    static_cast<T>(0),
                                    static_cast<T>(10));
+ circle2.set_sites(temp_site, temp_site, temp_site);
     bool arr5[] = { true, false, true, false, false, true };
     EVENT_TYPES_CHECK_COMPARISON(circle1, circle2, arr5);
 }

Modified: sandbox/SOC/2010/sweepline/libs/sweepline/test/node_comparer_test.cpp
==============================================================================
--- sandbox/SOC/2010/sweepline/libs/sweepline/test/node_comparer_test.cpp (original)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/test/node_comparer_test.cpp 2010-06-21 17:49:48 EDT (Mon, 21 Jun 2010)
@@ -8,7 +8,7 @@
 // See http://www.boost.org for updates, documentation, and revision history.
 
 #include "test_type_list.hpp"
-#include <boost/sweepline/detail/voronoi_formation.hpp>
+#include "boost/sweepline/detail/voronoi_formation.hpp"
 using namespace boost::sweepline::detail;
 
 #define BOOST_TEST_MODULE node_comparer_test

Modified: sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_builder_test.cpp
==============================================================================
--- sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_builder_test.cpp (original)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_builder_test.cpp 2010-06-21 17:49:48 EDT (Mon, 21 Jun 2010)
@@ -7,13 +7,17 @@
 
 // See http://www.boost.org for updates, documentation, and revision history.
 
+#include <stdlib.h>
+#include <time.h>
+
 #include "test_type_list.hpp"
-#include <boost/sweepline/voronoi_builder.hpp>
+#include "boost/sweepline/voronoi_builder.hpp"
 using namespace boost::sweepline;
 
 #define BOOST_TEST_MODULE voronoi_builder_test
 #include <boost/test/test_case_template.hpp>
 
+// Sites: (0, 0), (0, 4), (2, 1).
 BOOST_AUTO_TEST_CASE_TEMPLATE(voronoi_builder_test1, T, test_types) {
     typedef typename voronoi_builder<T>::edge_type edge_type;
     typedef typename voronoi_builder<T>::edge_iterator edge_iterator;
@@ -76,6 +80,7 @@
 
 }
 
+// Sites: (0, 1), (2, 0), (2, 4).
 BOOST_AUTO_TEST_CASE_TEMPLATE(voronoi_builder_test2, T, test_types) {
     typedef typename voronoi_builder<T>::edge_type edge_type;
     typedef typename voronoi_builder<T>::edge_iterator edge_iterator;
@@ -137,6 +142,7 @@
     BOOST_CHECK_EQUAL(edge3_2->next == edge1_1, true);
 }
 
+// Sites: (0, 0), (0, 1), (1, 0), (1, 1).
 BOOST_AUTO_TEST_CASE_TEMPLATE(voronoi_builder_test3, T, test_types) {
     typedef typename voronoi_builder<T>::edge_type edge_type;
     typedef typename voronoi_builder<T>::edge_iterator edge_iterator;
@@ -144,19 +150,141 @@
         voronoi_vertices_iterator;
 
     voronoi_builder<T> test_beach_line;
- point_2d<T> point1 = make_point_2d<T>(0, 0);
- point_2d<T> point2 = make_point_2d<T>(0, 1);
- point_2d<T> point3 = make_point_2d<T>(1, 0);
- point_2d<T> point4 = make_point_2d<T>(1, 1);
-
     std::vector< point_2d<T> > points;
- points.push_back(point1);
- points.push_back(point2);
- points.push_back(point3);
- points.push_back(point4);
+ points.push_back(make_point_2d<T>(0, 0));
+ points.push_back(make_point_2d<T>(0, 1));
+ points.push_back(make_point_2d<T>(1, 0));
+ points.push_back(make_point_2d<T>(1, 1));
     
     test_beach_line.init(points);
     test_beach_line.run_sweepline();
     BOOST_CHECK_EQUAL(test_beach_line.get_cell_records().size(), 4);
- BOOST_CHECK_EQUAL(test_beach_line.get_voronoi_vertices().size(), 1);
-}
\ No newline at end of file
+ BOOST_CHECK_EQUAL(test_beach_line.get_voronoi_vertices().size(), 2);
+}
+
+// Sites: {(x, y) | x = 0 .. 9, y = 0 .. 9}.
+BOOST_AUTO_TEST_CASE_TEMPLATE(voronoi_builder_test4, T, test_types) {
+ typedef typename voronoi_builder<T>::edge_type edge_type;
+ typedef typename voronoi_builder<T>::edge_iterator edge_iterator;
+ typedef typename voronoi_builder<T>::voronoi_vertices_iterator
+ voronoi_vertices_iterator;
+
+ voronoi_builder<T> test_beach_line;
+ std::vector< point_2d<T> > points;
+ for (int i = 0; i < 10; i++)
+ for (int j = 0; j < 10; j++)
+ points.push_back(make_point_2d<T>(static_cast<T>(i),
+ static_cast<T>(j)));
+
+ test_beach_line.init(points);
+ test_beach_line.run_sweepline();
+}
+
+// Generate 100 random sites.
+BOOST_AUTO_TEST_CASE_TEMPLATE(voronoi_builder_test4_1, T, test_types) {
+ typedef typename voronoi_builder<T>::edge_type edge_type;
+ typedef typename voronoi_builder<T>::edge_iterator edge_iterator;
+ typedef typename voronoi_builder<T>::voronoi_vertices_iterator
+ voronoi_vertices_iterator;
+
+ srand(static_cast<unsigned int>(time(NULL)));
+ voronoi_builder<T> test_beach_line;
+ std::vector< point_2d<T> > points;
+ for (int i = 0; i < 100; i++)
+ points.push_back(make_point_2d<T>(static_cast<T>(rand() % 100),
+ static_cast<T>(rand() % 100)));
+
+ test_beach_line.init(points);
+ test_beach_line.run_sweepline();
+}
+
+// Sites: {(x, y) | x = 0 .. 33, y = 0 .. 33}.
+BOOST_AUTO_TEST_CASE_TEMPLATE(voronoi_builder_test5, T, test_types) {
+ typedef typename voronoi_builder<T>::edge_type edge_type;
+ typedef typename voronoi_builder<T>::edge_iterator edge_iterator;
+ typedef typename voronoi_builder<T>::voronoi_vertices_iterator
+ voronoi_vertices_iterator;
+
+ voronoi_builder<T> test_beach_line;
+ std::vector< point_2d<T> > points;
+ for (int i = 0; i < 33; i++)
+ for (int j = 0; j < 33; j++)
+ points.push_back(make_point_2d<T>(static_cast<T>(i),
+ static_cast<T>(j)));
+
+ test_beach_line.init(points);
+ test_beach_line.run_sweepline();
+}
+
+// Generate 1000 random sites.
+BOOST_AUTO_TEST_CASE_TEMPLATE(voronoi_builder_test5_1, T, test_types) {
+ typedef typename voronoi_builder<T>::edge_type edge_type;
+ typedef typename voronoi_builder<T>::edge_iterator edge_iterator;
+ typedef typename voronoi_builder<T>::voronoi_vertices_iterator
+ voronoi_vertices_iterator;
+
+ srand(static_cast<unsigned int>(time(NULL)));
+ voronoi_builder<T> test_beach_line;
+ std::vector< point_2d<T> > points;
+ for (int i = 0; i < 1000; i++)
+ points.push_back(make_point_2d<T>(static_cast<T>(rand() % 100),
+ static_cast<T>(rand() % 100)));
+
+ test_beach_line.init(points);
+ test_beach_line.run_sweepline();
+}
+
+// Sites: {(x, y) | x = 0 .. 100, y = 0 .. 100}.
+BOOST_AUTO_TEST_CASE_TEMPLATE(voronoi_builder_test6, T, test_types) {
+ typedef typename voronoi_builder<T>::edge_type edge_type;
+ typedef typename voronoi_builder<T>::edge_iterator edge_iterator;
+ typedef typename voronoi_builder<T>::voronoi_vertices_iterator
+ voronoi_vertices_iterator;
+
+ voronoi_builder<T> test_beach_line;
+ std::vector< point_2d<T> > points;
+ for (int i = 0; i < 100; i++)
+ for (int j = 0; j < 100; j++)
+ points.push_back(make_point_2d<T>(static_cast<T>(i),
+ static_cast<T>(j)));
+
+ test_beach_line.init(points);
+ test_beach_line.run_sweepline();
+}
+
+// Generate 10000 random sites.
+BOOST_AUTO_TEST_CASE_TEMPLATE(voronoi_builder_test6_1, T, test_types) {
+ typedef typename voronoi_builder<T>::edge_type edge_type;
+ typedef typename voronoi_builder<T>::edge_iterator edge_iterator;
+ typedef typename voronoi_builder<T>::voronoi_vertices_iterator
+ voronoi_vertices_iterator;
+
+ srand(static_cast<unsigned int>(time(NULL)));
+ voronoi_builder<T> test_beach_line;
+ std::vector< point_2d<T> > points;
+ for (int i = 0; i < 10000; i++)
+ points.push_back(make_point_2d<T>(static_cast<T>(rand() % 1000),
+ static_cast<T>(rand() % 1000)));
+
+ test_beach_line.init(points);
+ test_beach_line.run_sweepline();
+}
+
+//// Sites: {(x, y) | x = 0 .. 333, y = 0 .. 333}.
+//BOOST_AUTO_TEST_CASE_TEMPLATE(voronoi_builder_test7, T, test_types) {
+// typedef typename voronoi_builder<T>::edge_type edge_type;
+// typedef typename voronoi_builder<T>::edge_iterator edge_iterator;
+// typedef typename voronoi_builder<T>::voronoi_vertices_iterator
+// voronoi_vertices_iterator;
+//
+// srand(static_cast<unsigned int>(time(NULL)));
+// voronoi_builder<T> test_beach_line;
+// std::vector< point_2d<T> > points;
+// for (int i = 0; i < 333; i++)
+// for (int j = 0; j < 333; j++)
+// points.push_back(make_point_2d<T>(static_cast<T>(rand() % 1000),
+// static_cast<T>(rand() % 1000)));
+//
+// test_beach_line.init(points);
+// test_beach_line.run_sweepline();
+//}
\ No newline at end of file


Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk