Boost logo

Boost-Commit :

Subject: [Boost-commit] svn:boost r62672 - in sandbox/SOC/2010/sweepline: boost/sweepline libs/sweepline/test
From: sydorchuk.andriy_at_[hidden]
Date: 2010-06-09 13:21:23


Author: asydorchuk
Date: 2010-06-09 13:21:22 EDT (Wed, 09 Jun 2010)
New Revision: 62672
URL: http://svn.boost.org/trac/boost/changeset/62672

Log:
Removed virtual functions from event_types implementations (changed architecture appropriately).
Added beach_line_node class (with unit tests).
Added node_comparer class (with unit tests).
Added beach_line class (voronoi math implementation).

Text files modified:
   sandbox/SOC/2010/sweepline/boost/sweepline/beach_line.hpp | 325 +++++++++++++++++++++++++++++++++++++++
   sandbox/SOC/2010/sweepline/boost/sweepline/event_queue.hpp | 62 ++++---
   sandbox/SOC/2010/sweepline/boost/sweepline/event_types.hpp | 130 +++++++++++----
   sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_builder.hpp | 22 -
   sandbox/SOC/2010/sweepline/libs/sweepline/test/Jamfile.v2 | 1
   sandbox/SOC/2010/sweepline/libs/sweepline/test/beach_line_test.cpp | 95 +++++++++++
   sandbox/SOC/2010/sweepline/libs/sweepline/test/event_queue_test.cpp | 75 +++++++-
   sandbox/SOC/2010/sweepline/libs/sweepline/test/test_type_list.hpp | 4
   sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_builder_test.cpp | 14 +
   9 files changed, 632 insertions(+), 96 deletions(-)

Modified: sandbox/SOC/2010/sweepline/boost/sweepline/beach_line.hpp
==============================================================================
--- sandbox/SOC/2010/sweepline/boost/sweepline/beach_line.hpp (original)
+++ sandbox/SOC/2010/sweepline/boost/sweepline/beach_line.hpp 2010-06-09 13:21:22 EDT (Wed, 09 Jun 2010)
@@ -8,6 +8,8 @@
 // See http://www.boost.org for updates, documentation, and revision history.
 
 #include <map>
+#include <vector>
+#include <cmath>
 
 #ifndef BOOST_SWEEPLINE_BEACH_LINE
 #define BOOST_SWEEPLINE_BEACH_LINE
@@ -15,7 +17,328 @@
 namespace boost {
 namespace sweepline {
 
- //Not implemented yet.
+ template <typename Point2D>
+ struct beach_line_node {
+ public:
+ typedef typename Point2D Point2D;
+ typedef typename Point2D::coordinate_type coordinate_type;
+ typedef typename Point2D::site_event_type site_event_type;
+ typedef typename Point2D::circle_event_type circle_event_type;
+
+ beach_line_node() {}
+
+ explicit beach_line_node(const Point2D &new_point) {
+ left_point_ = new_point;
+ right_point_ = new_point;
+ }
+
+ beach_line_node(const Point2D &left_point, const Point2D &right_point) {
+ left_point_ = left_point;
+ right_point_ = right_point;
+ }
+
+ const Point2D &get_left_point() const {
+ return left_point_;
+ }
+
+ const Point2D &get_right_point() const {
+ return right_point_;
+ }
+
+ coordinate_type get_sweepline_coord() const {
+ return std::max(left_point_.x(), right_point_.x());
+ }
+
+ const Point2D& get_new_point() const {
+ if (left_point_.x() > right_point_.x())
+ return left_point_;
+ return right_point_;
+ }
+
+ Point2D get_intersection_point(bool use_right_point, const Point2D &new_point) const {
+ const Point2D &use_point = (use_right_point) ? right_point_ : left_point_;
+ coordinate_type vertex_x = ((new_point.y() - use_point.y()) *
+ (new_point.y() - use_point.y()) /
+ (use_point.x() - new_point.x()) +
+ use_point.x() + new_point.x()) *
+ static_cast<coordinate_type>(0.5);
+ return make_point_2d(vertex_x, new_point.y());
+ }
+
+ bool less(const Point2D &new_point) const {
+ coordinate_type sweepline_coord = new_point.x();
+ coordinate_type new_node_coord = new_point.y();
+ coordinate_type a1 = left_point_.x() - sweepline_coord;
+ coordinate_type a2 = right_point_.x() - sweepline_coord;
+ coordinate_type b1 = new_node_coord - left_point_.y();
+ coordinate_type b2 = new_node_coord - right_point_.y();
+ coordinate_type c = left_point_.x() - right_point_.x();
+ return a1 * a2 * c + a2 * b1 * b1 < a1 * b2 * b2;
+ }
+
+ private:
+ Point2D left_point_;
+ Point2D right_point_;
+ };
+
+ template <typename Point2D>
+ struct beach_line_node_data {
+ public:
+ typedef typename Point2D::coordinate_type coordinate_type;
+ typedef typename Point2D::site_event_type site_event_type;
+ typedef typename Point2D::circle_event_type circle_event_type;
+
+ beach_line_node_data() {}
+ private:
+ };
+
+ template <typename BeachLineNode>
+ struct node_comparer {
+ public:
+ typedef typename BeachLineNode::coordinate_type coordinate_type;
+
+ bool operator() (const BeachLineNode &node1, const BeachLineNode &node2) const {
+ coordinate_type node1_line = node1.get_sweepline_coord();
+ coordinate_type node2_line = node2.get_sweepline_coord();
+ if (node1_line == node2_line) {
+ if (node1.get_left_point() == node2.get_right_point() &&
+ node1.get_right_point() == node2.get_left_point())
+ return node1.get_right_point().x() == node1_line;
+ return node1.get_left_point().y() <= node2.get_left_point().y();
+ }
+ else if (node1_line < node2_line)
+ return node1.less(node2.get_new_point());
+ else
+ return !node2.less(node1.get_new_point());
+ }
+ };
+
+ template <typename Key, typename Value, typename NodeComparer, typename EventQueue>
+ class beach_line {
+ public:
+ typedef typename Key::Point2D Point2D;
+ typedef typename Key::coordinate_type coordinate_type;
+ typedef typename Key::site_event_type site_event_type;
+ typedef typename Key::circle_event_type circle_event_type;
+ typedef typename std::map< Key, Value, node_comparer<Key> >::const_iterator beach_line_iterator;
+ typedef typename std::pair< beach_line_iterator, bool > beach_line_pair;
+
+ struct event_processor {
+ explicit event_processor(beach_line *b_line)
+ : beach_line_(b_line) {}
+
+ void operator()(const site_event_type &site_event) {
+ beach_line_->process_site_event(site_event);
+ }
+
+ void operator()(const circle_event_type &circle_event) {
+ beach_line_->process_circle_event(circle_event);
+ }
+
+ beach_line* beach_line_;
+ };
+
+ beach_line() {
+ event_queue_ = new EventQueue;
+ event_processor_ = new event_processor(this);
+ }
+
+ ~beach_line() {
+ if (event_queue_) {
+ delete event_queue_;
+ event_queue_ = NULL;
+ }
+ if (event_processor_) {
+ delete event_processor_;
+ event_processor_ = NULL;
+ }
+ }
+
+ void init(const std::vector<Point2D> &sites) {
+ std::sort(sites.begin(), sites.end());
+ int skip = 0;
+
+ if (sites.size() == 1) {
+ skip = 1
+ } else {
+ std::vector<Point2D>::const_iterator it = sites.begin();
+ while(it != sites.end() && it->x() == sites.begin()->x()) {
+ it++;
+ skip++;
+ }
+
+ if (num == 1) {
+ init_beach_line(*sites.begin(), *it);
+ } else {
+ init_beach_line(sites.begin(), it);
+ }
+ }
+ event_queue_->init(sites, skip);
+ }
+
+ void reset() {
+ event_queue_.reset();
+ beach_line_.clear();
+ }
+
+ void run_sweepline() {
+ while (!event_queue_->empty()) {
+ event_queue_->process_top_event(*event_processor_);
+ event_queue_->pop();
+ }
+ }
+
+ void process_site_event(const site_event_type &site_event) {
+ Key new_key(site_event.get_point());
+ beach_line_iterator it = beach_line_.lower_bound(new_key);
+
+ Point2D point_arc;
+ Point2D voronoi_vertex;
+ if (it == beach_line_.end()) {
+ it--;
+ point_arc = it->first.get_right_point();
+ voronoi_vertex = it->first.get_intersection_point(true, site_event.get_point());
+ activate_circle_event(it->first.get_left_point(),
+ it->first.get_right_point(),
+ site_event.get_point());
+ } else if (it == beach_line_.begin()) {
+ point_arc = it->first.get_left_point();
+ voronoi_vertex = it->first.get_intersection_point(false, site_event.get_point());
+ activate_circle_event(site_event.get_point(),
+ it->first.get_left_point(),
+ it->first.get_right_point());
+ } else {
+ point_arc = it->first.get_left_point();
+ voronoi_vertex = it->first.get_intersection_point(false, site_event.get_point());
+
+ const Point2D &point2 = it->first.get_left_point();
+ const Point2D &point3 = it->first.get_right_point();
+ it--;
+ const Point2D &point1 = it->first.get_right_point();
+
+ deactivate_circle_event(point1, point2, point3);
+ activate_circle_event(point1, point2, site_event.get_point());
+ activate_circle_event(site_event.get_point(), point2, point3);
+ }
+
+ Key new_left_node(point_arc, site_event.get_point());
+ Key new_right_node(site_event.get_point(), point_arc);
+ beach_line_.insert(std::pair<Key, Value>(new_left_node, Value()));
+ beach_line_.insert(std::pair<Key, Value>(new_right_node, Value()));
+ }
+
+ void process_circle_event(const circle_event_type &circle_event) {
+ Key new_key(circle_event.get_bisector_left_point(),
+ circle_event.get_bisector_right_point());
+ beach_line_iterator it_first = beach_line_.find(new_key);
+ beach_line_iterator it_last = it_first;
+
+ if (it_first == beach_line_.end())
+ return;
+
+
+ Point2D point2 = it_first->first.get_left_point();
+ Point2D point3 = it_first->first.get_right_point();
+ it_first--;
+ it_last++;
+ Point2D point1 = it_first->first.get_left_point();
+ beach_line_.erase(it_first, it_last);
+ Key new_node(point1, point3);
+ beach_line_pair it_pair =
+ beach_line_.insert(std::pair<Key, Value>(new_node, Value()));
+
+ it_first = it_pair.first;
+ it_last = it_first;
+
+ if (it_first != beach_line_.begin()) {
+ it_first--;
+ const Point2D &point_l1 = it_first->first.get_left_point();
+ deactivate_circle_event(point_l1, point1, point2);
+ if (it_first != beach_line_.begin()) {
+ it_first--;
+ const Point2D &point_l2 = it_first->first.get_left_point();
+ activate_circle_event(point_l2, point_l1, point1);
+ }
+ }
+
+ it_last++;
+ if (it_last != beach_line_.end()) {
+ const Point2D &point_r1 = it_last->first.get_right_point();
+ deactivate_circle_event(point2, point3, point_r1);
+ it_last++;
+ if (it_last != beach_line_.end()) {
+ it_last++;
+ const Point2D &point_r2 = it_last->first.get_right_point();
+ activate_circle_event(point3, point_r1, point_r2);
+ }
+ }
+ }
+
+ protected:
+ void init_beach_line(typename std::vector<Point2D>::const_iterator it_begin,
+ typename std::vector<Point2D>::const_iterator it_end) {
+ typename std::vector<Point2D>::const_iterator it_first = it_begin;
+ typename std::vector<Point2D>::const_iterator it_second = it_begin;
+ it_second++;
+ while (it_second != it_end) {
+ beach_line_node new_node(*it_first, *it_second);
+ beach_line_.insert(std::pair<Key, Value>(new_node, Value()));
+ it_first++;
+ it_second++;
+ }
+ }
+
+ void init_beach_line(const Point2D &first_point, const Point2D &second_point) {
+ beach_line_node new_left_node(firs_point, second_point);
+ beach_line_node new_second_node(second_point, first_point);
+ beach_line_.insert(std::pair<Key, Value>(new_left_node, Value()));
+ beach_line_.insert(std::pair<Key, Value>(new_right_node, Value()));
+ }
+
+ bool create_circle_event(const Point2D &point1,
+ const Point2D &point2,
+ const Point2D &point3,
+ circle_event_type &c_event) const {
+ coordinate_type a = (point1.x() - point2.x())*(point2.y() - point3.y()) -
+ (point1.y() - point2.y())*(point2.x() - point3.x());
+ if (a <= static_cast<coordinate_type>(0))
+ return false;
+ coordinate_type b1 = (point1.x() - point2.x())*(point1.x() + point2.x()) +
+ (point1.y() - point2.y())*(point1.y() + point2.y());
+ coordinate_type b2 = (point2.x() - point3.x())*(point2.x() + point3.x()) +
+ (point2.y() - point3.y())*(point2.y() + point3.y());
+ coordinate_type c_x = (b1*(point2.y() - point3.y()) - b2*(point1.y() - point2.y())) / a *
+ static_cast<coordinate_type>(0.5);
+ coordinate_type c_y = (b2*(point1.x() - point2.x()) - b1*(point2.x() - point3.x())) / a *
+ static_cast<coordinate_type>(0.5);
+ coordinate_type sqr_radius = (c_x-point1.x())*(c_x-point1.x()) + (c_y-point1.y())*(c_y-point1.y());
+ coordinate_type radius = static_cast<coordinate_type>(sqr_radius);
+ c_event = make_circle_event(c_x + radius, c_y);
+ c_event.set_bisector(point2, point3);
+ return true;
+ }
+
+ void activate_circle_event(const Point2D &point1,
+ const Point2D &point2,
+ const Point2D &point3) const {
+ circle_event_type c_event;
+ if (create_circle_event(point1, point2, point3, c_event))
+ event_queue_->push(c_event);
+ }
+
+ void deactivate_circle_event(const Point2D &point1,
+ const Point2D &point2,
+ const Point2D &point3) const {
+ circle_event_type c_event;
+ if (create_circle_event(point1, point2, point3, c_event))
+ event_queue_->deactivate_event(c_event);
+ }
+
+ private:
+ EventQueue* event_queue_;
+ event_processor* event_processor_;
+ std::map< Key, Value, NodeComparer > beach_line_;
+ };
 
 } // sweepline
 } // boost

Modified: sandbox/SOC/2010/sweepline/boost/sweepline/event_queue.hpp
==============================================================================
--- sandbox/SOC/2010/sweepline/boost/sweepline/event_queue.hpp (original)
+++ sandbox/SOC/2010/sweepline/boost/sweepline/event_queue.hpp 2010-06-09 13:21:22 EDT (Wed, 09 Jun 2010)
@@ -21,20 +21,26 @@
     class event_queue {
     public:
         typedef typename Point2D::coordinate_type coordinate_type;
- typedef typename Point2D::sweepline_event_type sweepline_event_type;
         typedef typename Point2D::site_event_type site_event_type;
         typedef typename Point2D::circle_event_type circle_event_type;
- typedef typename Point2D::sweepline_event_type::kEventType kEventType;
+
+ enum kEventType {
+ SITE_EVENT = 0,
+ CIRCLE_EVENT = 1,
+ NONE = 2,
+ };
 
         event_queue() {
             site_events_iterator_ = site_events_.begin();
         }
 
- void init(const std::vector<Point2D> &sites) {
+ void init(const std::vector<Point2D> &sites, int skip) {
             site_events_.clear();
- site_events_.resize(sites.size());
- for (int i = 0; i < sites.size(); i++)
- site_events_[i] = make_site_event(sites[i].x(), sites[i].y());
+ site_events_.resize(sites.size() - skip);
+ std::vector<Point2D>::const_iterator sites_it;
+ int index = 0;
+ for (sites_it = sites.begin() + skip; sites_it != sites.end(); sites_it++)
+ site_events_[index++] = make_site_event(sites_it->x(), sites_it->y());
             init_site_events();
         }
 
@@ -55,53 +61,57 @@
             return true;
         }
 
- const sweepline_event_type &top() {
+ template <typename event_handler>
+ void process_top_event(event_handler &functor) {
             kEventType top_event_type = get_top_event_type();
- if (top_event_type == kEventType::SITE_EVENT)
- return *site_events_iterator_;
+ if (top_event_type == SITE_EVENT)
+ functor(*site_events_iterator_);
             else
- return circle_events_.top();
+ functor(circle_events_.top());
         }
 
         void pop() {
             kEventType top_event_type = get_top_event_type();
- if (top_event_type == kEventType::SITE_EVENT)
+ if (top_event_type == SITE_EVENT)
                 site_events_iterator_++;
- else if (top_event_type == kEventType::CIRCLE_EVENT)
+ else if (top_event_type == CIRCLE_EVENT)
                 circle_events_.pop();
         }
 
- void push(circle_event_type circle_event) {
+ void push(circle_event_type &circle_event) {
             circle_events_.push(circle_event);
         }
 
+ void deactivate_event(circle_event_type &circle_event) {
+ deactivated_events_.push(circle_event);
+ }
+
     private:
         void init_site_events() {
- std::sort(site_events_.begin(), site_events_.end());
             site_events_iterator_ = site_events_.begin();
- last_event_type_ = kEventType::SITE_EVENT;
         }
 
         void remove_not_active_events() {
- while (!circle_events_.empty() &&
- !circle_events_.top().is_active())
+ while (!circle_events_.empty() && !deactivated_events_.empty() &&
+ circle_events_.top() == deactivated_events_.top()) {
                 circle_events_.pop();
+ deactivated_events_.pop();
+ }
         }
 
         kEventType get_top_event_type() {
             remove_not_active_events();
-
             if (site_events_iterator_ == site_events_.end())
- return kEventType::CIRCLE_EVENT;
+ return CIRCLE_EVENT;
             else if (circle_events_.empty())
- return kEventType::SITE_EVENT;
+ return SITE_EVENT;
             else {
- if ((*site_events_iterator_) <= circle_events_.top())
- return kEventType::SITE_EVENT;
+ if (site_events_iterator_->get_point() <= circle_events_.top().get_point())
+ return SITE_EVENT;
                 else
- return kEventType::CIRCLE_EVENT;
+ return CIRCLE_EVENT;
             }
- return kEventType::NONE;
+ return NONE;
         }
 
         typename std::vector<site_event_type>::const_iterator
@@ -110,7 +120,9 @@
         std::priority_queue< circle_event_type,
                              std::vector<circle_event_type>,
                              std::greater<circle_event_type> > circle_events_;
- kEventType last_event_type_;
+ std::priority_queue< circle_event_type,
+ std::vector<circle_event_type>,
+ std::greater<circle_event_type> > deactivated_events_;
 
         //Disallow copy constructor and operator=
         event_queue(const event_queue&);

Modified: sandbox/SOC/2010/sweepline/boost/sweepline/event_types.hpp
==============================================================================
--- sandbox/SOC/2010/sweepline/boost/sweepline/event_types.hpp (original)
+++ sandbox/SOC/2010/sweepline/boost/sweepline/event_types.hpp 2010-06-09 13:21:22 EDT (Wed, 09 Jun 2010)
@@ -14,19 +14,15 @@
 namespace sweepline {
     
     template <typename T>
- class sweepline_event;
-
- template <typename T>
- class site_event;
+ struct site_event;
     
     template <typename T>
- class circle_event;
+ struct circle_event;
 
     template <typename T>
- class point_2d {
+ struct point_2d {
     public:
         typedef T coordinate_type;
- typedef sweepline_event<T> sweepline_event_type;
         typedef site_event<T> site_event_type;
         typedef circle_event<T> circle_event_type;
 
@@ -90,33 +86,52 @@
     }
 
     template <typename T>
- class sweepline_event : public point_2d<T> {
+ struct site_event {
     public:
- enum kEventType {
- SITE_EVENT = 0,
- CIRCLE_EVENT = 1,
- NONE = 2,
- };
+ typedef T coordinate_type;
 
- sweepline_event() : point_2d() {}
+ site_event() {}
+
+ site_event(T x, T y) : point_(x, y) {}
 
- sweepline_event(T x, T y) : point_2d(x, y) {}
+ bool operator==(const site_event &s_event) const {
+ return point_ == s_event.get_point();
+ }
 
- virtual kEventType get_event_type() const {
- return NONE;
+ bool operator!=(const site_event &s_event) const {
+ return point_ != s_event.get_point();
         }
- };
 
- template <typename T>
- class site_event : public sweepline_event<T> {
- public:
- site_event() : sweepline_event() {}
-
- site_event(T x, T y) : sweepline_event(x, y) {}
+ bool operator<(const site_event &s_event) const {
+ return point_ < s_event.get_point();
+ }
+
+ bool operator<=(const site_event &s_event) const {
+ return point_ <= s_event.get_point();
+ }
 
- virtual kEventType get_event_type() const {
- return SITE_EVENT;
+ bool operator>(const site_event &s_event) const {
+ return point_ > s_event.get_point();
         }
+
+ bool operator>=(const site_event &s_event) const {
+ return point_ >= s_event.get_point();
+ }
+
+ coordinate_type x() const {
+ return point_.x();
+ }
+
+ coordinate_type y() const {
+ return point_.y();
+ }
+
+ const point_2d<T> &get_point() const {
+ return point_;
+ }
+
+ private:
+ point_2d<T> point_;
     };
 
     template <typename T>
@@ -124,27 +139,70 @@
         return site_event<T>(x,y);
     }
 
+ struct BeachLineNode;
+
     template <typename T>
- class circle_event : public site_event<T> {
+ struct circle_event {
     public:
- circle_event() : site_event() {
- active_ = true;
+ typedef T coordinate_type;
+
+ circle_event() {}
+
+ circle_event(T x, T y) : point_(x, y) {}
+
+ bool operator==(const circle_event &c_event) const {
+ return point_ == c_event.get_point();
+ }
+
+ bool operator!=(const circle_event &c_event) const {
+ return point_ != c_event.get_point();
+ }
+
+ bool operator<(const circle_event &c_event) const {
+ return point_ < c_event.get_point();
+ }
+
+ bool operator<=(const circle_event &c_event) const {
+ return point_ <= c_event.get_point();
+ }
+
+ bool operator>(const circle_event &c_event) const {
+ return point_ > c_event.get_point();
+ }
+
+ bool operator>=(const circle_event &c_event) const {
+ return point_ >= c_event.get_point();
+ }
+
+ coordinate_type x() const {
+ return point_.x();
+ }
+
+ coordinate_type y() const {
+ return point_.y();
+ }
+
+ const point_2d<T> &get_point() const {
+ return point_;
         }
 
- circle_event(T x, T y) : site_event(x, y) {
- active_ = true;
+ void set_bisector(const point_2d<T> &left_point, const point_2d<T> &right_point) {
+ bisector_left_point_ = left_point;
+ bisector_right_point_ = right_point;
         }
 
- bool is_active() {
- return active_;
+ const point_2d<T> &get_bisector_left_point() const {
+ return bisector_left_point_;
         }
 
- virtual kEventType get_event_type() const {
- return CIRCLE_EVENT;
+ const point_2d<T> &get_bisector_right_point() const {
+ return bisector_right_point_;
         }
 
     private:
- bool active_;
+ point_2d<T> point_;
+ point_2d<T> bisector_left_point_;
+ point_2d<T> bisector_right_point_;
     };
 
     template <typename T>

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-09 13:21:22 EDT (Wed, 09 Jun 2010)
@@ -15,17 +15,14 @@
 namespace boost {
 namespace sweepline {
 
- template <typename Point2D, typename EventQueue, typename BeachLine>
+template <typename Point2D, typename BeachLine>
     class voronoi_builder {
     public:
- voronoi_builder() {}
+ voronoi_builder() {
+ beach_line_ = new BeachLine;
+ }
         
         ~voronoi_builder() {
- if (event_queue_) {
- delete event_queue_;
- event_queue_ = NULL;
- }
-
             if (beach_line_) {
                 delete beach_line_;
                 beach_line_ = NULL;
@@ -33,25 +30,18 @@
         }
 
         void init(const std::vector<Point2D> &sites) {
- event_queue_->init(sites);
+ beach_line_->init(sites);
         }
 
         void reset() {
- event_queue_->reset();
             beach_line_->reset();
         }
 
         void build_voronoi_diagram() {
- while (!event_queue_->empty())
- make_one_iteration();
+ beach_line_->run_sweepline();
         }
 
     private:
- void make_one_iteration() {
- //Not implemented yet
- }
-
- EventQueue* event_queue_;
         BeachLine* beach_line_;
     };
 

Modified: sandbox/SOC/2010/sweepline/libs/sweepline/test/Jamfile.v2
==============================================================================
--- sandbox/SOC/2010/sweepline/libs/sweepline/test/Jamfile.v2 (original)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/test/Jamfile.v2 2010-06-09 13:21:22 EDT (Wed, 09 Jun 2010)
@@ -13,4 +13,5 @@
 test-suite "sweepline"
     :
         [ run event_queue_test.cpp : : : <link>static ]
+ [ run beach_line_test.cpp : : : <link>static ]
     ;
\ No newline at end of file

Modified: sandbox/SOC/2010/sweepline/libs/sweepline/test/beach_line_test.cpp
==============================================================================
--- sandbox/SOC/2010/sweepline/libs/sweepline/test/beach_line_test.cpp (original)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/test/beach_line_test.cpp 2010-06-09 13:21:22 EDT (Wed, 09 Jun 2010)
@@ -5,4 +5,97 @@
 // (See accompanying file LICENSE_1_0.txt or copy at
 // http://www.boost.org/LICENSE_1_0.txt)
 
-// See http://www.boost.org for updates, documentation, and revision history.
\ No newline at end of file
+// See http://www.boost.org for updates, documentation, and revision history.
+
+#include "test_type_list.hpp"
+#include <boost/sweepline/beach_line.hpp>
+#include <boost/sweepline/event_types.hpp>
+using namespace boost::sweepline;
+
+#define BOOST_TEST_MODULE beach_line_test
+#include <boost/test/test_case_template.hpp>
+
+BOOST_AUTO_TEST_CASE_TEMPLATE(voronoi_vertex_computation_test1, T, test_types) {
+ typedef beach_line_node< point_2d<T> > bline_node;
+ bline_node initial_node(make_point_2d<T>(static_cast<T>(0), static_cast<T>(0)),
+ make_point_2d<T>(static_cast<T>(0), static_cast<T>(2)));
+
+ point_2d<T> point1 = make_point_2d<T>(static_cast<T>(1), static_cast<T>(0));
+ point_2d<T> point2 = make_point_2d<T>(static_cast<T>(1), static_cast<T>(1));
+ point_2d<T> point3 = make_point_2d<T>(static_cast<T>(1), static_cast<T>(2));
+
+ point_2d<T> voronoi_vertex1 = initial_node.get_intersection_point(false, point1);
+ BOOST_CHECK_EQUAL(voronoi_vertex1.x() == static_cast<T>(0.5) &&
+ voronoi_vertex1.y() == static_cast<T>(0.0), true);
+
+ point_2d<T> voronoi_vertex2_1 = initial_node.get_intersection_point(false, point2);
+ point_2d<T> voronoi_vertex2_2 = initial_node.get_intersection_point(true, point2);
+ BOOST_CHECK_EQUAL(voronoi_vertex2_1.x() == static_cast<T>(0.0) &&
+ voronoi_vertex2_1.y() == static_cast<T>(1.0) &&
+ voronoi_vertex2_1.x() == voronoi_vertex2_2.x() &&
+ voronoi_vertex2_1.y() == voronoi_vertex2_2.y(), true);
+
+ point_2d<T> voronoi_vertex3 = initial_node.get_intersection_point(true, point3);
+ BOOST_CHECK_EQUAL(voronoi_vertex3.x() == static_cast<T>(0.5) &&
+ voronoi_vertex3.y() == static_cast<T>(2.0), true);
+}
+
+BOOST_AUTO_TEST_CASE_TEMPLATE(node_comparer_test1, T, test_types) {
+ typedef beach_line_node< point_2d<T> > bline_node;
+ typedef std::map< bline_node, int, node_comparer<bline_node> >::const_iterator bline_it;
+
+ std::map< bline_node, int, node_comparer<bline_node> > test_beach_line;
+
+ bline_node initial_node(make_point_2d<T>(static_cast<T>(0), static_cast<T>(0)),
+ make_point_2d<T>(static_cast<T>(0), static_cast<T>(2)));
+ test_beach_line[initial_node] = 0;
+ BOOST_CHECK_EQUAL(test_beach_line.size(), 1);
+
+ bline_node new_node1(make_point_2d<T>(static_cast<T>(1), static_cast<T>(0)));
+ bline_node new_node2(make_point_2d<T>(static_cast<T>(1), static_cast<T>(1)));
+ bline_node new_node3(make_point_2d<T>(static_cast<T>(1), static_cast<T>(2)));
+ bline_node new_node4(make_point_2d<T>(static_cast<T>(1), static_cast<T>(1.000001)));
+ bline_node new_node5(make_point_2d<T>(static_cast<T>(1), static_cast<T>(0.999999)));
+
+ bline_it it = test_beach_line.lower_bound(new_node1);
+ BOOST_CHECK_EQUAL(it == test_beach_line.begin(), true);
+
+ it = test_beach_line.lower_bound(new_node2);
+ BOOST_CHECK_EQUAL(it == test_beach_line.begin(), true);
+
+ it = test_beach_line.lower_bound(new_node3);
+ BOOST_CHECK_EQUAL(it == test_beach_line.end(), true);
+
+ it = test_beach_line.lower_bound(new_node4);
+ BOOST_CHECK_EQUAL(it == test_beach_line.end(), true);
+
+ it = test_beach_line.lower_bound(new_node5);
+ BOOST_CHECK_EQUAL(it == test_beach_line.begin(), true);
+}
+
+BOOST_AUTO_TEST_CASE_TEMPLATE(node_comparer_test2, T, test_types) {
+ typedef beach_line_node< point_2d<T> > bline_node;
+ typedef std::map< bline_node, int, node_comparer<bline_node> >::const_iterator bline_it;
+
+ std::map< bline_node, int, node_comparer<bline_node> > test_beach_line;
+
+ point_2d<T> point1 = make_point_2d<T>(static_cast<T>(0), static_cast<T>(0));
+ point_2d<T> point2 = make_point_2d<T>(static_cast<T>(0), static_cast<T>(2));
+ bline_node initial_node(point1, point2);
+ test_beach_line[initial_node] = 0;
+
+ point_2d<T> point3 = make_point_2d<T>(static_cast<T>(1), static_cast<T>(0));
+ bline_node node1(point1, point3);
+ bline_node node2(point3, point1);
+ test_beach_line.insert(std::pair< bline_node, int>(node1, 1));
+ test_beach_line.insert(std::pair< bline_node, int>(node2, 2));
+
+ bline_it it = test_beach_line.begin();
+ BOOST_CHECK_EQUAL(it->second == 1, true);
+
+ ++it;
+ BOOST_CHECK_EQUAL(it->second == 2, true);
+
+ ++it;
+ BOOST_CHECK_EQUAL(it->second == 0, true);
+}
\ No newline at end of file

Modified: sandbox/SOC/2010/sweepline/libs/sweepline/test/event_queue_test.cpp
==============================================================================
--- sandbox/SOC/2010/sweepline/libs/sweepline/test/event_queue_test.cpp (original)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/test/event_queue_test.cpp 2010-06-09 13:21:22 EDT (Wed, 09 Jun 2010)
@@ -16,11 +16,33 @@
 #include <boost/test/test_case_template.hpp>
 
 #define CHECK_TOP_ELEMENT_EQUALITY(TOP, X, Y) \
- BOOST_CHECK_EQUAL(TOP.x() == static_cast<T>(X) && \
- TOP.y() == static_cast<T>(Y), true)
+ BOOST_CHECK_EQUAL(TOP.x == static_cast<T>(X) && \
+ TOP.y == static_cast<T>(Y), true)
+
+template <typename Point2D>
+struct event_processor {
+ typedef typename Point2D::coordinate_type coordinate_type;
+ typedef typename Point2D::site_event_type site_event_type;
+ typedef typename Point2D::circle_event_type circle_event_type;
+
+ event_processor() {}
+
+ void operator()(const site_event_type &site_event) {
+ x = site_event.x();
+ y = site_event.y();
+ }
+
+ void operator()(const circle_event_type &circle_event) {
+ x = circle_event.x();
+ y = circle_event.y();
+ }
+
+ coordinate_type x;
+ coordinate_type y;
+};
 
 BOOST_AUTO_TEST_CASE_TEMPLATE(event_queue_test1, T, test_types) {
- typedef sweepline_event<T>::kEventType kEventType;
+ event_processor< point_2d<T> > test_processor;
 
     event_queue< point_2d<T> > event_q;
     BOOST_CHECK_EQUAL(event_q.empty(), true);
@@ -33,11 +55,15 @@
         T y = static_cast<T>(10-i);
         site_event_vec.push_back(make_point_2d(x, y));
     }
- event_q.init(site_event_vec);
- CHECK_TOP_ELEMENT_EQUALITY(event_q.top(), 0, 0);
-
+ sort(site_event_vec.begin(), site_event_vec.end());
+ event_q.init(site_event_vec, 0);
+
+ event_q.process_top_event(test_processor);
+ CHECK_TOP_ELEMENT_EQUALITY(test_processor, 0, 0);
     event_q.pop();
- CHECK_TOP_ELEMENT_EQUALITY(event_q.top(), 1, 1);
+
+ event_q.process_top_event(test_processor);
+ CHECK_TOP_ELEMENT_EQUALITY(test_processor, 1, 1);
 
     for (int i = 5; i < 10; i++) {
         T x = static_cast<T>(10-i);
@@ -52,18 +78,41 @@
     }
     
     for (int i = 0; i < 10; i++) {
- CHECK_TOP_ELEMENT_EQUALITY(event_q.top(), 1 + i/2, 1 + i/2);
- BOOST_CHECK_EQUAL(event_q.top().get_event_type(),
- (i&1)?(kEventType::CIRCLE_EVENT):(kEventType::SITE_EVENT));
+ event_q.process_top_event(test_processor);
+ CHECK_TOP_ELEMENT_EQUALITY(test_processor, 1 + i/2, 1 + i/2);
         event_q.pop();
     }
 
     for (int i = 10; i < 20; i++) {
- CHECK_TOP_ELEMENT_EQUALITY(event_q.top(), 1 + i/2, 1 + (i-1)/2);
- BOOST_CHECK_EQUAL(event_q.top().get_event_type(),
- (i&1)?(kEventType::SITE_EVENT):(kEventType::CIRCLE_EVENT));
+ event_q.process_top_event(test_processor);
+ CHECK_TOP_ELEMENT_EQUALITY(test_processor, 1 + i/2, 1 + (i-1)/2);
         event_q.pop();
     }
     
     BOOST_CHECK_EQUAL(event_q.empty(), true);
+}
+
+BOOST_AUTO_TEST_CASE_TEMPLATE(event_queue_test2, T, test_types) {
+ event_processor< point_2d<T> > test_processor;
+ event_queue< point_2d<T> > event_q;
+
+ 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));
+ }
+
+ 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));
+ }
+
+ for (int i = 0; i < 5; i++) {
+ event_q.process_top_event(test_processor);
+ CHECK_TOP_ELEMENT_EQUALITY(test_processor, 2 + 2*i, 2 + 2*i);
+ event_q.pop();
+ }
+
+ BOOST_CHECK_EQUAL(event_q.empty(), true);
 }
\ No newline at end of file

Modified: sandbox/SOC/2010/sweepline/libs/sweepline/test/test_type_list.hpp
==============================================================================
--- sandbox/SOC/2010/sweepline/libs/sweepline/test/test_type_list.hpp (original)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/test/test_type_list.hpp 2010-06-09 13:21:22 EDT (Wed, 09 Jun 2010)
@@ -12,9 +12,7 @@
 
 #include <boost/mpl/list.hpp>
 
-typedef boost::mpl::list<int,
- long long,
- float,
+typedef boost::mpl::list<float,
                          double,
                          long double> test_types;
 

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-09 13:21:22 EDT (Wed, 09 Jun 2010)
@@ -5,4 +5,16 @@
 // (See accompanying file LICENSE_1_0.txt or copy at
 // http://www.boost.org/LICENSE_1_0.txt)
 
-// See http://www.boost.org for updates, documentation, and revision history.
\ No newline at end of file
+// See http://www.boost.org for updates, documentation, and revision history.
+
+//#include "test_type_list.hpp"
+//#include <boost/sweepline/beach_line.hpp>
+//#include <boost/sweepline/event_queue.hpp>
+//#include <boost/sweepline/event_types.hpp>
+//#include <boost/sweepline/voronoi_builder.hpp>
+//
+//#define BOOST_TEST_MODULE voronoi_builder_test
+//#include <boost/test/test_case_template.hpp>
+//
+//BOOST_AUTO_TEST_CASE_TEMPLATE(voronoi_builder_test1, T, test_types) {
+//}
\ 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