|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r74921 - in sandbox/gtl: boost/polygon boost/polygon/detail libs/polygon/test
From: sydorchuk.andriy_at_[hidden]
Date: 2011-10-11 17:14:32
Author: asydorchuk
Date: 2011-10-11 17:14:31 EDT (Tue, 11 Oct 2011)
New Revision: 74921
URL: http://svn.boost.org/trac/boost/changeset/74921
Log:
Renamed voronoi_formation to voronoi_internal_structures.hpp
Added voronoi_internal structures test.
Added:
sandbox/gtl/boost/polygon/detail/voronoi_internal_structures.hpp
- copied, changed from r74743, /sandbox/gtl/boost/polygon/detail/voronoi_formation.hpp
sandbox/gtl/libs/polygon/test/voronoi_internal_structures_test.cpp (contents, props changed)
Removed:
sandbox/gtl/boost/polygon/detail/voronoi_formation.hpp
Text files modified:
sandbox/gtl/boost/polygon/detail/voronoi_calc_kernel.hpp | 4
sandbox/gtl/boost/polygon/detail/voronoi_internal_structures.hpp | 114 +++++++++++++--------------------------
sandbox/gtl/boost/polygon/voronoi_builder.hpp | 29 ++++++---
sandbox/gtl/libs/polygon/test/Jamfile.v2 | 5 +
sandbox/gtl/libs/polygon/test/voronoi_benchmark_test.cpp | 10 ++-
5 files changed, 69 insertions(+), 93 deletions(-)
Modified: sandbox/gtl/boost/polygon/detail/voronoi_calc_kernel.hpp
==============================================================================
--- sandbox/gtl/boost/polygon/detail/voronoi_calc_kernel.hpp (original)
+++ sandbox/gtl/boost/polygon/detail/voronoi_calc_kernel.hpp 2011-10-11 17:14:31 EDT (Tue, 11 Oct 2011)
@@ -381,8 +381,8 @@
class node_comparison_predicate {
public:
typedef Node node_type;
- typedef typename Node::coordinate_type coordinate_type;
- typedef typename Node::site_event_type site_type;
+ typedef typename Node::site_type site_type;
+ typedef typename site_type::coordinate_type coordinate_type;
typedef distance_predicate<site_type> distance_predicate_type;
// Compares nodes in the balanced binary search tree. Nodes are
Deleted: sandbox/gtl/boost/polygon/detail/voronoi_formation.hpp
==============================================================================
--- sandbox/gtl/boost/polygon/detail/voronoi_formation.hpp 2011-10-11 17:14:31 EDT (Tue, 11 Oct 2011)
+++ (empty file)
@@ -1,503 +0,0 @@
-// Boost polygon/detail/voronoi_formation.hpp header file
-
-// Copyright Andrii Sydorchuk 2010.
-// Distributed under the Boost Software License, Version 1.0.
-// (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.
-
-#ifndef BOOST_POLYGON_VORONOI_FORMATION
-#define BOOST_POLYGON_VORONOI_FORMATION
-
-#include "mpt_wrapper.hpp"
-#include "voronoi_fpt_kernel.hpp"
-
-namespace boost {
-namespace polygon {
-namespace detail {
-
- ///////////////////////////////////////////////////////////////////////////
- // VORONOI EVENT TYPES ////////////////////////////////////////////////////
- ///////////////////////////////////////////////////////////////////////////
-
- // Represents the result of the orientation test.
- enum kOrientation {
- RIGHT_ORIENTATION = -1,
- COLLINEAR = 0,
- LEFT_ORIENTATION = 1,
- };
-
- // Cartesian 2D point data structure.
- template <typename T>
- class point_2d {
- public:
- typedef T coordinate_type;
-
- point_2d() {}
-
- point_2d(coordinate_type x, coordinate_type y) {
- x_ = x;
- y_ = y;
- }
-
- bool operator==(const point_2d &that) const {
- return (this->x_ == that.x()) && (this->y_ == that.y());
- }
-
- bool operator!=(const point_2d &that) const {
- return (this->x_ != that.x()) || (this->y_ != that.y());
- }
-
- // Comparison function.
- // Defines ordering of the points on the 2D plane.
- bool operator<(const point_2d &that) const {
- if (this->x_ != that.x_)
- return this->x_ < that.x_;
- return this->y_ < that.y_;
- }
-
- bool operator<=(const point_2d &that) const {
- return !(that < (*this));
- }
-
- bool operator>(const point_2d &that) const {
- return that < (*this);
- }
-
- bool operator>=(const point_2d &that) const {
- return !((*this) < that);
- }
-
- coordinate_type x() const {
- return x_;
- }
-
- coordinate_type y() const {
- return y_;
- }
-
- void x(coordinate_type x) {
- x_ = x;
- }
-
- void y(coordinate_type y) {
- y_ = y;
- }
-
- private:
- coordinate_type x_;
- coordinate_type y_;
- };
-
- // Site event type.
- // Occurs when the sweepline sweeps over one of the initial sites:
- // 1) point site;
- // 2) startpoint of the segment site;
- // 3) endpoint of the segment site.
- // Implicit segment direction is defined: the startpoint of
- // the segment compares less than its endpoint.
- // Each input segment is divided onto two site events:
- // 1) One going from the startpoint to the endpoint
- // (is_inverse_ = false);
- // 2) Another going from the endpoint to the startpoint
- // (is_inverse_ = true).
- // In beach line data structure segment sites of the first
- // type preceed sites of the second type for the same segment.
- // Variables: point0_ - point site or segment's startpoint;
- // point1_ - segment's endpoint if site is a segment;
- // index_ - site event index among other sites;
- // is_segment_ - flag whether site is a segment;
- // is_vertical_ - flag whether site is vertical;
- // is_inverse_ - defines type of the segment site.
- // Note: for all the point sites is_vertical_ flag is true,
- // is_inverse_ flag is false.
- template <typename T>
- class site_event {
- public:
- typedef T coordinate_type;
- typedef point_2d<T> point_type;
-
- // Point site contructors.
- site_event() :
- point0_(0, 0),
- point1_(0, 0),
- is_segment_(false),
- is_vertical_(true),
- is_inverse_(false) {}
-
- site_event(coordinate_type x, coordinate_type y, int index) :
- point0_(x, y),
- point1_(x, y),
- site_index_(index),
- is_segment_(false),
- is_vertical_(true),
- is_inverse_(false) {}
-
- site_event(const point_type &point, int index) :
- point0_(point),
- point1_(point),
- site_index_(index),
- is_segment_(false),
- is_vertical_(true),
- is_inverse_(false) {}
-
- // Segment site constructors.
- site_event(coordinate_type x1, coordinate_type y1,
- coordinate_type x2, coordinate_type y2, int index):
- point0_(x1, y1),
- point1_(x2, y2),
- site_index_(index),
- is_segment_(true),
- is_inverse_(false) {
- if (point0_ > point1_)
- (std::swap)(point0_, point1_);
- is_vertical_ = (point0_.x() == point1_.x());
- }
-
- site_event(const point_type &point1,
- const point_type &point2, int index) :
- point0_(point1),
- point1_(point2),
- site_index_(index),
- is_segment_(true),
- is_inverse_(false) {
- if (point0_ > point1_)
- (std::swap)(point0_, point1_);
- is_vertical_ = (point0_.x() == point1_.x());
- }
-
- coordinate_type x(bool oriented = false) const {
- return x0(oriented);
- }
-
- coordinate_type y(bool oriented = false) const {
- return y0(oriented);
- }
-
- // Return x-coordinate of the point for the point sites.
- // Return x-coordinate of the startpoint for the segment sites.
- coordinate_type x0(bool oriented = false) const {
- if (!oriented)
- return point0_.x();
- return is_inverse_ ? point1_.x() : point0_.x();
- }
-
- // Return y-coordinate of the point for the point sites.
- // Return y-coordinate of the startpoint for the segment sites.
- coordinate_type y0(bool oriented = false) const {
- if (!oriented)
- return point0_.y();
- return is_inverse_ ? point1_.y() : point0_.y();
- }
-
- // Return x-coordinate of the endpoint of the segment sites.
- // Doesn't make sense for the point sites.
- coordinate_type x1(bool oriented = false) const {
- if (!oriented)
- return point1_.x();
- return is_inverse_ ? point0_.x() : point1_.x();
- }
-
- // Return y-coordinate of the endpoint of the segment sites.
- // Doesn't make sense for the point sites.
- coordinate_type y1(bool oriented = false) const {
- if (!oriented)
- return point1_.y();
- return is_inverse_ ? point0_.y() : point1_.y();
- }
-
- // Return point for the point sites.
- // Return startpoint for the segment sites.
- const point_type &point0(bool oriented = false) const {
- if (!oriented)
- return point0_;
- return is_inverse_ ? point1_ : point0_;
- }
-
- // Return endpoint of the segment sites.
- // Doesn't make sense for the point sites.
- const point_type &point1(bool oriented = false) const {
- if (!oriented)
- return point1_;
- return is_inverse_ ? point0_ : point1_;
- }
-
- // Return index of the site among all the other sites.
- void index(int index) {
- site_index_ = index;
- }
-
- // Change segment site orientation to the opposite one.
- void inverse() {
- is_inverse_ ^= true;
- }
-
- int index() const {
- return site_index_;
- }
-
- bool is_segment() const {
- return is_segment_;
- }
-
- bool is_vertical() const {
- return is_vertical_;
- }
-
- bool is_inverse() const {
- return is_inverse_;
- }
-
- private:
- point_type point0_;
- point_type point1_;
- int site_index_;
- bool is_segment_;
- bool is_vertical_;
- bool is_inverse_;
- };
-
- // Circle event type.
- // Occrus when the sweepline sweeps over the rightmost point of the voronoi
- // circle (with the center at the intersection point of the bisectors).
- // Circle event is made by the two consequtive nodes in the beach line data
- // structure. In case another node was inserted during algorithm execution
- // between the given two nodes circle event becomes inactive.
- // Circle events order is based on the comparison of the rightmost points
- // of the circles. The order is the same like for the point_2d class.
- // However as coordinates of the circle events might be not integers extra
- // comparison checks are required to make the comparison robust.
- // Next representation is used to store parameters of the circle:
- // each of the parameters is represented as fraction
- // numerator / denominator. Denominator is common for each of the
- // three parameters. Epsilon robust comparator class is used
- // to represent parameters of the circle events.
- // Variables: center_x_ - numerator of the center's x-coordinate.
- // center_y_ - numerator of the center's y-coordinate.
- // lower_x_ - numerator of the bottom point's x-coordinate.
- // denom_ - positive denominator for the previous three values.
- // bisector_node_ - iterator to the second bisector's node.
- // is_active_ - flag whether circle event is still active.
- // lower_y coordinate is always equal to center_y.
- template <typename T>
- class circle_event {
- public:
- typedef T coordinate_type;
-
- circle_event() : is_active_(true) {}
-
- circle_event(coordinate_type c_x,
- coordinate_type c_y,
- coordinate_type lower_x) :
- center_x_(c_x),
- center_y_(c_y),
- lower_x_(lower_x),
- is_active_(true) {}
-
- // Evaluate x-coordinate of the center of the circle.
- coordinate_type x() const {
- return center_x_;
- }
-
- void x(coordinate_type center_x) {
- center_x_ = center_x;
- }
-
- // Evaluate y-coordinate of the center of the circle.
- coordinate_type y() const {
- return center_y_;
- }
-
- void y(coordinate_type center_y) {
- center_y_ = center_y;
- }
-
- // Evaluate x-coordinate of the rightmost point of the circle.
- coordinate_type lower_x() const {
- return lower_x_;
- }
-
- coordinate_type lower_y() const {
- return center_y_;
- }
-
- void lower_x(coordinate_type lower_x) {
- lower_x_ = lower_x;
- }
-
- bool is_active() const {
- return is_active_;
- }
-
- void deactivate() {
- is_active_ = false;
- }
-
- private:
- coordinate_type center_x_;
- coordinate_type center_y_;
- coordinate_type lower_x_;
- bool is_active_;
- };
-
- ///////////////////////////////////////////////////////////////////////////
- // VORONOI CIRCLE EVENTS QUEUE ////////////////////////////////////////////
- ///////////////////////////////////////////////////////////////////////////
-
- // Event queue data structure, holds circle events.
- // During algorithm run, some of the circle events disappear(become
- // inactive). Priority queue data structure by itself doesn't support
- // iterators (there is no direct ability to modify its elements).
- // Instead list is used to store all the circle events and priority queue
- // of the iterators to the list elements is used to keep the correct circle
- // events ordering.
- template <typename T, typename Predicate>
- class ordered_queue {
- public:
- ordered_queue() {}
-
- bool empty() {
- return c_.empty();
- }
-
- const T &top() {
- return *c_.top();
- }
-
- void pop() {
- list_iterator_type it = c_.top();
- c_.pop();
- c_list_.erase(it);
- }
-
- T &push(const T &e) {
- c_list_.push_front(e);
- c_.push(c_list_.begin());
- return c_list_.front();
- }
-
- private:
- typedef typename std::list<T>::iterator list_iterator_type;
-
- struct comparison {
- Predicate cmp_;
- bool operator() (const list_iterator_type &it1,
- const list_iterator_type &it2) const {
- return cmp_(*it1, *it2);
- }
- };
-
- std::priority_queue< list_iterator_type,
- std::vector<list_iterator_type>,
- comparison > c_;
- std::list<T> c_list_;
-
- //Disallow copy constructor and operator=
- ordered_queue(const ordered_queue&);
- void operator=(const ordered_queue&);
- };
-
- ///////////////////////////////////////////////////////////////////////////
- // VORONOI BEACH LINE DATA TYPES //////////////////////////////////////////
- ///////////////////////////////////////////////////////////////////////////
-
- // Represents a bisector node made by two arcs that correspond to the left
- // and right sites. Arc is defined as a curve with points equidistant from
- // the site and from the sweepline. If the site is a point then the arc is
- // a parabola, otherwise it's a line segment. A segment site event will
- // produce different bisectors depending on its direction.
- // In the general case two sites will create two opposite bisectors. That's
- // why the order of the sites is important to define the unique bisector.
- // The one site is considered to be newer than the other in case it was
- // processed by the algorithm later.
- template <typename SEvent>
- class beach_line_node_key {
- public:
- typedef SEvent site_event_type;
- typedef typename site_event_type::coordinate_type coordinate_type;
- typedef typename site_event_type::point_type point_type;
-
- beach_line_node_key() {}
-
- // Constructs degenerate bisector, used to search an arc that is above
- // the given site. The input to the constructor is the new site point.
- explicit beach_line_node_key(const site_event_type &new_site) :
- left_site_(new_site),
- right_site_(new_site) {}
-
- // Constructs a new bisector. The input to the constructor is the two
- // sites that create the bisector. The order of sites is important.
- beach_line_node_key(const site_event_type &left_site, const site_event_type &right_site) :
- left_site_(left_site),
- right_site_(right_site) {}
-
- const site_event_type &left_site() const {
- return left_site_;
- }
-
- const site_event_type &right_site() const {
- return right_site_;
- }
-
- void left_site(const site_event_type &site) {
- left_site_ = site;
- }
-
- void right_site(const site_event_type &site) {
- right_site_ = site;
- }
-
- void inverse_left_site() {
- left_site_.inverse();
- }
-
- void inverse_right_site() {
- right_site_.inverse();
- }
-
- private:
- site_event_type left_site_;
- site_event_type right_site_;
- };
-
- // Represents edge data sturcture from the voronoi output, that is
- // associated as a value with beach line bisector as a key in the beach
- // line. Contains iterator to the circle event in the circle event
- // queue in case it's the second bisector that forms a circle event.
- template <typename CEvent>
- class beach_line_node_data {
- public:
- explicit beach_line_node_data(void *new_edge) :
- circle_event_(0),
- edge_(new_edge) {}
-
- void activate_circle_event(CEvent *circle_event) {
- circle_event_ = circle_event;
- }
-
- void deactivate_circle_event() {
- if (circle_event_) {
- circle_event_->deactivate();
- circle_event_ = 0;
- }
- }
-
- void *edge() const {
- return edge_;
- }
-
- void edge(void *new_edge) {
- edge_ = new_edge;
- }
-
- private:
- CEvent *circle_event_;
- void *edge_;
- };
-
-} // detail
-} // polygon
-} // boost
-
-#endif
Copied: sandbox/gtl/boost/polygon/detail/voronoi_internal_structures.hpp (from r74743, /sandbox/gtl/boost/polygon/detail/voronoi_formation.hpp)
==============================================================================
--- /sandbox/gtl/boost/polygon/detail/voronoi_formation.hpp (original)
+++ sandbox/gtl/boost/polygon/detail/voronoi_internal_structures.hpp 2011-10-11 17:14:31 EDT (Tue, 11 Oct 2011)
@@ -1,4 +1,4 @@
-// Boost polygon/detail/voronoi_formation.hpp header file
+// Boost.Polygon detail/voronoi_internal_structures.hpp header file
// Copyright Andrii Sydorchuk 2010.
// Distributed under the Boost Software License, Version 1.0.
@@ -7,27 +7,17 @@
// See http://www.boost.org for updates, documentation, and revision history.
-#ifndef BOOST_POLYGON_VORONOI_FORMATION
-#define BOOST_POLYGON_VORONOI_FORMATION
+#ifndef BOOST_POLYGON_VORONOI_INTERNAL_STRUCTURES
+#define BOOST_POLYGON_VORONOI_INTERNAL_STRUCTURES
-#include "mpt_wrapper.hpp"
-#include "voronoi_fpt_kernel.hpp"
+#include <list>
+#include <queue>
+#include <vector>
namespace boost {
namespace polygon {
namespace detail {
- ///////////////////////////////////////////////////////////////////////////
- // VORONOI EVENT TYPES ////////////////////////////////////////////////////
- ///////////////////////////////////////////////////////////////////////////
-
- // Represents the result of the orientation test.
- enum kOrientation {
- RIGHT_ORIENTATION = -1,
- COLLINEAR = 0,
- LEFT_ORIENTATION = 1,
- };
-
// Cartesian 2D point data structure.
template <typename T>
class point_2d {
@@ -36,10 +26,9 @@
point_2d() {}
- point_2d(coordinate_type x, coordinate_type y) {
- x_ = x;
- y_ = y;
- }
+ point_2d(coordinate_type x, coordinate_type y) :
+ x_(x),
+ y_(y) {}
bool operator==(const point_2d &that) const {
return (this->x_ == that.x()) && (this->y_ == that.y());
@@ -122,24 +111,18 @@
site_event() :
point0_(0, 0),
point1_(0, 0),
- is_segment_(false),
- is_vertical_(true),
is_inverse_(false) {}
site_event(coordinate_type x, coordinate_type y, int index) :
point0_(x, y),
point1_(x, y),
site_index_(index),
- is_segment_(false),
- is_vertical_(true),
is_inverse_(false) {}
site_event(const point_type &point, int index) :
point0_(point),
point1_(point),
site_index_(index),
- is_segment_(false),
- is_vertical_(true),
is_inverse_(false) {}
// Segment site constructors.
@@ -148,11 +131,9 @@
point0_(x1, y1),
point1_(x2, y2),
site_index_(index),
- is_segment_(true),
is_inverse_(false) {
if (point0_ > point1_)
(std::swap)(point0_, point1_);
- is_vertical_ = (point0_.x() == point1_.x());
}
site_event(const point_type &point1,
@@ -160,11 +141,9 @@
point0_(point1),
point1_(point2),
site_index_(index),
- is_segment_(true),
is_inverse_(false) {
if (point0_ > point1_)
(std::swap)(point0_, point1_);
- is_vertical_ = (point0_.x() == point1_.x());
}
coordinate_type x(bool oriented = false) const {
@@ -238,11 +217,11 @@
}
bool is_segment() const {
- return is_segment_;
+ return point0_.x() != point1_.x() || point0_.y() != point1_.y();
}
bool is_vertical() const {
- return is_vertical_;
+ return point0_.x() == point1_.x();
}
bool is_inverse() const {
@@ -253,8 +232,6 @@
point_type point0_;
point_type point1_;
int site_index_;
- bool is_segment_;
- bool is_vertical_;
bool is_inverse_;
};
@@ -341,10 +318,6 @@
bool is_active_;
};
- ///////////////////////////////////////////////////////////////////////////
- // VORONOI CIRCLE EVENTS QUEUE ////////////////////////////////////////////
- ///////////////////////////////////////////////////////////////////////////
-
// Event queue data structure, holds circle events.
// During algorithm run, some of the circle events disappear(become
// inactive). Priority queue data structure by itself doesn't support
@@ -398,10 +371,6 @@
void operator=(const ordered_queue&);
};
- ///////////////////////////////////////////////////////////////////////////
- // VORONOI BEACH LINE DATA TYPES //////////////////////////////////////////
- ///////////////////////////////////////////////////////////////////////////
-
// Represents a bisector node made by two arcs that correspond to the left
// and right sites. Arc is defined as a curve with points equidistant from
// the site and from the sweepline. If the site is a point then the arc is
@@ -411,89 +380,82 @@
// why the order of the sites is important to define the unique bisector.
// The one site is considered to be newer than the other in case it was
// processed by the algorithm later.
- template <typename SEvent>
+ template <typename Site>
class beach_line_node_key {
public:
- typedef SEvent site_event_type;
- typedef typename site_event_type::coordinate_type coordinate_type;
- typedef typename site_event_type::point_type point_type;
-
- beach_line_node_key() {}
+ typedef Site site_type;
// Constructs degenerate bisector, used to search an arc that is above
// the given site. The input to the constructor is the new site point.
- explicit beach_line_node_key(const site_event_type &new_site) :
+ explicit beach_line_node_key(const site_type &new_site) :
left_site_(new_site),
right_site_(new_site) {}
// Constructs a new bisector. The input to the constructor is the two
// sites that create the bisector. The order of sites is important.
- beach_line_node_key(const site_event_type &left_site, const site_event_type &right_site) :
+ beach_line_node_key(const site_type &left_site, const site_type &right_site) :
left_site_(left_site),
right_site_(right_site) {}
- const site_event_type &left_site() const {
+ const site_type &left_site() const {
return left_site_;
}
- const site_event_type &right_site() const {
- return right_site_;
+ site_type &left_site() {
+ return left_site_;
}
- void left_site(const site_event_type &site) {
+ void left_site(const site_type &site) {
left_site_ = site;
}
- void right_site(const site_event_type &site) {
- right_site_ = site;
+ const site_type &right_site() const {
+ return right_site_;
}
- void inverse_left_site() {
- left_site_.inverse();
+ site_type &right_site() {
+ return right_site_;
}
- void inverse_right_site() {
- right_site_.inverse();
+ void right_site(const site_type &site) {
+ right_site_ = site;
}
private:
- site_event_type left_site_;
- site_event_type right_site_;
+ site_type left_site_;
+ site_type right_site_;
};
// Represents edge data sturcture from the voronoi output, that is
// associated as a value with beach line bisector as a key in the beach
// line. Contains iterator to the circle event in the circle event
// queue in case it's the second bisector that forms a circle event.
- template <typename CEvent>
+ template <typename Edge, typename Circle>
class beach_line_node_data {
public:
- explicit beach_line_node_data(void *new_edge) :
- circle_event_(0),
+ explicit beach_line_node_data(Edge *new_edge) :
+ circle_event_(NULL),
edge_(new_edge) {}
- void activate_circle_event(CEvent *circle_event) {
- circle_event_ = circle_event;
+ Circle *circle_event() const {
+ return circle_event_;
}
- void deactivate_circle_event() {
- if (circle_event_) {
- circle_event_->deactivate();
- circle_event_ = 0;
- }
+ void circle_event(Circle *circle_event) {
+ circle_event_ = circle_event;
}
- void *edge() const {
+ Edge *edge() const {
return edge_;
}
- void edge(void *new_edge) {
+ void edge(Edge *new_edge) {
edge_ = new_edge;
}
private:
- CEvent *circle_event_;
- void *edge_;
+ Circle *circle_event_;
+ Edge *edge_;
};
} // detail
Modified: sandbox/gtl/boost/polygon/voronoi_builder.hpp
==============================================================================
--- sandbox/gtl/boost/polygon/voronoi_builder.hpp (original)
+++ sandbox/gtl/boost/polygon/voronoi_builder.hpp 2011-10-11 17:14:31 EDT (Tue, 11 Oct 2011)
@@ -26,7 +26,7 @@
#include "detail/mpt_wrapper.hpp"
#include "detail/voronoi_calc_kernel.hpp"
#include "detail/voronoi_fpt_kernel.hpp"
-#include "detail/voronoi_formation.hpp"
+#include "detail/voronoi_internal_structures.hpp"
namespace boost {
namespace polygon {
@@ -196,8 +196,9 @@
event_comparison_predicate;
typedef calc_kernel_type::circle_formation_predicate<site_event_type, circle_event_type>
circle_formation_predicate_type;
+ typedef typename output_type::voronoi_edge_type edge_type;
typedef detail::beach_line_node_key<site_event_type> key_type;
- typedef detail::beach_line_node_data<circle_event_type> value_type;
+ typedef detail::beach_line_node_data<edge_type, circle_event_type> value_type;
typedef calc_kernel_type::node_comparison_predicate<key_type> node_comparer_type;
typedef std::map< key_type, value_type, node_comparer_type > beach_line_type;
typedef typename beach_line_type::iterator beach_line_iterator;
@@ -210,7 +211,6 @@
} event_comparison_type;
typedef detail::ordered_queue<event_type, event_comparison_type>
circle_event_queue_type;
- typedef typename output_type::voronoi_edge_type edge_type;
typedef std::pair<point_type, beach_line_iterator> end_point_type;
// Create site events.
@@ -300,6 +300,13 @@
}
}
+ void deactivate_circle_event(value_type &value) {
+ if (value.circle_event()) {
+ value.circle_event()->deactivate();
+ value.circle_event(NULL);
+ }
+ }
+
// Process a single site.
void process_site_event() {
// Get the site event to process.
@@ -379,7 +386,7 @@
const site_event_type &site3 = it->first.right_site();
// Remove the candidate circle from the event queue.
- it->second.deactivate_circle_event();
+ deactivate_circle_event(it->second);
--it;
const site_event_type &site_arc1 = it->first.right_site();
const site_event_type &site1 = it->first.left_site();
@@ -427,11 +434,11 @@
site_event_type site3 = it_first->first.right_site();
// Get the half-edge corresponding to the second bisector - (B, C).
- edge_type *bisector2 = static_cast<edge_type *>(it_first->second.edge());
+ edge_type *bisector2 = it_first->second.edge();
// Get the half-edge corresponding to the first bisector - (A, B).
--it_first;
- edge_type *bisector1 = static_cast<edge_type *>(it_first->second.edge());
+ edge_type *bisector1 = it_first->second.edge();
// Get the A site.
site_event_type site1 = it_first->first.left_site();
@@ -458,7 +465,7 @@
// Check new triplets formed by the neighboring arcs
// to the left for potential circle events.
if (it_first != beach_line_.begin()) {
- it_first->second.deactivate_circle_event();
+ deactivate_circle_event(it_first->second);
--it_first;
const site_event_type &site_l1 = it_first->first.left_site();
activate_circle_event(site_l1, site1, site3, it_last);
@@ -468,7 +475,7 @@
// to the right for potential circle events.
++it_last;
if (it_last != beach_line_.end()) {
- it_last->second.deactivate_circle_event();
+ deactivate_circle_event(it_last->second);
const site_event_type &site_r1 = it_last->first.right_site();
activate_circle_event(site1, site3, site_r1, it_last);
}
@@ -485,7 +492,7 @@
// Set correct orientation for the first site of the second node.
if (site_event.is_segment()) {
- new_right_node.inverse_left_site();
+ new_right_node.left_site().inverse();
}
// Update the output.
@@ -500,7 +507,7 @@
// disappear after processing site event going through the
// endpoint of the segment site.
key_type new_node(site_event, site_event);
- new_node.inverse_right_site();
+ new_node.right_site().inverse();
beach_line_iterator temp_it = beach_line_.insert(position,
typename beach_line_type::value_type(new_node, value_type(NULL)));
@@ -528,7 +535,7 @@
// new circle event in the circle event queue.
event_type &e = circle_events_.push(
std::pair<circle_event_type, beach_line_iterator>(c_event, bisector_node));
- bisector_node->second.activate_circle_event(&e.first);
+ bisector_node->second.circle_event(&e.first);
}
}
Modified: sandbox/gtl/libs/polygon/test/Jamfile.v2
==============================================================================
--- sandbox/gtl/libs/polygon/test/Jamfile.v2 (original)
+++ sandbox/gtl/libs/polygon/test/Jamfile.v2 2011-10-11 17:14:31 EDT (Tue, 11 Oct 2011)
@@ -26,4 +26,9 @@
[ run voronoi_benchmark_test.cpp ]
;
+alias "voronoi-unit"
+ :
+ [ run voronoi_internal_structures_test.cpp ]
+ ;
+
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 2011-10-11 17:14:31 EDT (Tue, 11 Oct 2011)
@@ -1,6 +1,6 @@
// Boost.Polygon library voronoi_benchmark_test.cpp file
-// Copyright Andrii Sydorchuk 2010.
+// Copyright Andrii Sydorchuk 2010-2011.
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
@@ -103,7 +103,8 @@
}
std::sort(periods.begin(), periods.end());
// Using olympic system to evaluate average time.
- double elapsed_time = std::accumulate(periods.begin() + 2, periods.end() - 2, 0.0) / (periods.size() - 4);
+ double elapsed_time = std::accumulate(periods.begin() + 2, periods.end() - 2, 0.0);
+ elapsed_time /= (periods.size() - 4);
std::ofstream bench_file(BENCHMARK_FILE, std::ios_base::out | std::ios_base::app);
bench_file << std::setiosflags(std::ios::right | std::ios::fixed) << std::setprecision(6);
@@ -142,11 +143,12 @@
}
std::sort(periods.begin(), periods.end());
// Using olympic system to evaluate average time.
- double elapsed_time = std::accumulate(periods.begin() + 2, periods.end() - 2, 0.0) / (periods.size() - 4);
+ double elapsed_time = std::accumulate(periods.begin() + 2, periods.end() - 2, 0.0);
+ elapsed_time /= (periods.size() - 4);
std::ofstream bench_file(BENCHMARK_FILE, std::ios_base::out | std::ios_base::app);
bench_file << std::setiosflags(std::ios::right | std::ios::fixed) << std::setprecision(6);
bench_file << "Static test of " << segments.size() << " segments: " << elapsed_time << std::endl;
bench_file.close();
}
-#endif
\ No newline at end of file
+#endif
Added: sandbox/gtl/libs/polygon/test/voronoi_internal_structures_test.cpp
==============================================================================
--- (empty file)
+++ sandbox/gtl/libs/polygon/test/voronoi_internal_structures_test.cpp 2011-10-11 17:14:31 EDT (Tue, 11 Oct 2011)
@@ -0,0 +1,116 @@
+// Boost.Polygon library voronoi_internal_structures_test.cpp file
+
+// Copyright Andrii Sydorchuk 2010-2011.
+// Distributed under the Boost Software License, Version 1.0.
+// (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.
+
+#define BOOST_TEST_MODULE internal_structures_test
+
+#include <boost/test/test_case_template.hpp>
+#include "boost/polygon/detail/voronoi_internal_structures.hpp"
+using namespace boost::polygon::detail;
+
+typedef point_2d<int> point_type;
+typedef site_event<int> site_type;
+typedef circle_event<int> circle_type;
+typedef ordered_queue<int, std::greater<int> > ordered_queue_type;
+typedef beach_line_node_key<int> node_key_type;
+typedef beach_line_node_data<int> node_data_type;
+
+BOOST_AUTO_TEST_CASE(point_2d_test) {
+ 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_test1) {
+ site_type s(1, 2, 0);
+ BOOST_CHECK_EQUAL(s.x0() == s.x1() && s.x1() == 1, true);
+ BOOST_CHECK_EQUAL(s.y0() == s.y1() && s.y1() == 2, true);
+ BOOST_CHECK_EQUAL(s.index() == 0, true);
+ BOOST_CHECK_EQUAL(s.is_segment(), false);
+ BOOST_CHECK_EQUAL(s.is_vertical(), true);
+ BOOST_CHECK_EQUAL(s.is_inverse(), false);
+}
+
+BOOST_AUTO_TEST_CASE(site_event_test2) {
+ site_type s(1, 2, 3, 4, 0);
+ BOOST_CHECK_EQUAL(s.x0(true) == 1 && s.x0() == 1, true);
+ BOOST_CHECK_EQUAL(s.y0(true) == 2 && s.y0() == 2, true);
+ BOOST_CHECK_EQUAL(s.x1(true) == 3 && s.x1() == 3, true);
+ BOOST_CHECK_EQUAL(s.y1(true) == 4 && s.y1() == 4, true);
+ BOOST_CHECK_EQUAL(s.index() == 0, true);
+ BOOST_CHECK_EQUAL(s.is_segment(), true);
+ BOOST_CHECK_EQUAL(s.is_vertical(), false);
+ BOOST_CHECK_EQUAL(s.is_inverse(), false);
+ s.inverse();
+ BOOST_CHECK_EQUAL(s.x1(true) == 1 && s.x0() == 1, true);
+ BOOST_CHECK_EQUAL(s.y1(true) == 2 && s.y0() == 2, true);
+ BOOST_CHECK_EQUAL(s.x0(true) == 3 && s.x1() == 3, true);
+ BOOST_CHECK_EQUAL(s.y0(true) == 4 && s.y1() == 4, true);
+ BOOST_CHECK_EQUAL(s.is_inverse(), true);
+}
+
+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_EQUAL(c.is_active(), true);
+ c.x(3);
+ BOOST_CHECK_EQUAL(c.x(), 3);
+ c.y(4);
+ BOOST_CHECK_EQUAL(c.y(), 4);
+ c.lower_x(5);
+ BOOST_CHECK_EQUAL(c.lower_x(), 5);
+ c.deactivate();
+ BOOST_CHECK_EQUAL(c.is_active(), false);
+}
+
+BOOST_AUTO_TEST_CASE(ordered_queue_test) {
+ ordered_queue_type q;
+ BOOST_CHECK_EQUAL(q.empty(), true);
+ 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_EQUAL(q.empty(), false);
+ for (int i = 0; i < 20; ++i, q.pop())
+ BOOST_CHECK_EQUAL(q.top(), i << 1);
+ BOOST_CHECK_EQUAL(q.empty(), true);
+}
+
+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, true);
+ BOOST_CHECK_EQUAL(key.right_site() == 1, true);
+ key.right_site(3);
+ BOOST_CHECK_EQUAL(key.left_site() == 2, true);
+ BOOST_CHECK_EQUAL(key.right_site() == 3, true);
+}
+
+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);
+ BOOST_CHECK_EQUAL(&data != NULL, true);
+}
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