Subject: [Boost-commit] svn:boost r80413 - in trunk: boost/polygon boost/polygon/detail libs/polygon/test
From: sydorchuk.andriy_at_[hidden]
Date: 2012-09-05 16:18:05
Author: asydorchuk
Date: 2012-09-05 16:18:04 EDT (Wed, 05 Sep 2012)
New Revision: 80413
URL: http://svn.boost.org/trac/boost/changeset/80413
Log:
Polygon: updating public interface of the library.
Text files modified:
trunk/boost/polygon/detail/voronoi_structures.hpp | 287 ++++++++++++++++++++++++++++++++++++++++
trunk/boost/polygon/voronoi_builder.hpp | 8
trunk/boost/polygon/voronoi_diagram.hpp | 13 +
trunk/libs/polygon/test/Jamfile.v2 | 2
trunk/libs/polygon/test/voronoi_predicates_test.cpp | 2
trunk/libs/polygon/test/voronoi_structures_test.cpp | 72 ++++++++++
6 files changed, 373 insertions(+), 11 deletions(-)
Modified: trunk/boost/polygon/detail/voronoi_structures.hpp
==============================================================================
--- trunk/boost/polygon/detail/voronoi_structures.hpp (original)
+++ trunk/boost/polygon/detail/voronoi_structures.hpp 2012-09-05 16:18:04 EDT (Wed, 05 Sep 2012)
@@ -14,9 +14,296 @@
#include <queue>
#include <vector>
+#include "boost/polygon/voronoi_geometry_type.hpp"
+
namespace boost {
namespace polygon {
namespace detail {
+// 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());
+ }
+
+ coordinate_type x() const {
+ return x_;
+ }
+
+ coordinate_type y() const {
+ return y_;
+ }
+
+ point_2d& x(coordinate_type x) {
+ x_ = x;
+ return *this;
+ }
+
+ point_2d& y(coordinate_type y) {
+ y_ = y;
+ return *this;
+ }
+
+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) start-point of the segment site
+// 3) endpoint of the segment site
+// Implicit segment direction is defined: the start-point of
+// the segment compares less than its endpoint.
+// Each input segment is divided onto two site events:
+// 1) One going from the start-point to the endpoint
+// (is_inverse() = false)
+// 2) Another going from the endpoint to the start-point
+// (is_inverse() = true)
+// In beach line data structure segment sites of the first
+// type precede sites of the second type for the same segment.
+// Members:
+// point0_ - point site or segment's start-point
+// point1_ - segment's endpoint if site is a segment
+// sorted_index_ - the last bit encodes information if the site is inverse;
+// the other bits encode site event index among the sorted site events
+// initial_index_ - site index among the initial input set
+// Note: for all sites is_inverse_ flag is equal to false by default.
+template <typename T>
+class site_event {
+public:
+ typedef T coordinate_type;
+ typedef point_2d<T> point_type;
+
+ site_event() :
+ point0_(0, 0),
+ point1_(0, 0),
+ sorted_index_(0),
+ flags_(0) {}
+
+ site_event(coordinate_type x, coordinate_type y) :
+ point0_(x, y),
+ point1_(x, y),
+ sorted_index_(0),
+ flags_(0) {}
+
+ site_event(const point_type& point) :
+ point0_(point),
+ point1_(point),
+ sorted_index_(0),
+ flags_(0) {}
+
+ site_event(coordinate_type x1, coordinate_type y1,
+ coordinate_type x2, coordinate_type y2):
+ point0_(x1, y1),
+ point1_(x2, y2),
+ sorted_index_(0),
+ flags_(0) {}
+
+ site_event(const point_type& point1, const point_type& point2) :
+ point0_(point1),
+ point1_(point2),
+ sorted_index_(0),
+ flags_(0) {}
+
+ bool operator==(const site_event& that) const {
+ return (this->point0_ == that.point0_) &&
+ (this->point1_ == that.point1_);
+ }
+
+ bool operator!=(const site_event& that) const {
+ return (this->point0_ != that.point0_) ||
+ (this->point1_ != that.point1_);
+ }
+
+ coordinate_type x(bool oriented = false) const {
+ return x0(oriented);
+ }
+
+ coordinate_type y(bool oriented = false) const {
+ return y0(oriented);
+ }
+
+ coordinate_type x0(bool oriented = false) const {
+ if (!oriented)
+ return point0_.x();
+ return is_inverse() ? point1_.x() : point0_.x();
+ }
+
+ coordinate_type y0(bool oriented = false) const {
+ if (!oriented)
+ return point0_.y();
+ return is_inverse() ? point1_.y() : point0_.y();
+ }
+
+ coordinate_type x1(bool oriented = false) const {
+ if (!oriented)
+ return point1_.x();
+ return is_inverse() ? point0_.x() : point1_.x();
+ }
+
+ coordinate_type y1(bool oriented = false) const {
+ if (!oriented)
+ return point1_.y();
+ return is_inverse() ? point0_.y() : point1_.y();
+ }
+
+ const point_type& point0(bool oriented = false) const {
+ if (!oriented)
+ return point0_;
+ return is_inverse() ? point1_ : point0_;
+ }
+
+ const point_type& point1(bool oriented = false) const {
+ if (!oriented)
+ return point1_;
+ return is_inverse() ? point0_ : point1_;
+ }
+
+ std::size_t sorted_index() const {
+ return sorted_index_;
+ }
+
+ site_event& sorted_index(std::size_t index) {
+ sorted_index_ = index;
+ return *this;
+ }
+
+ std::size_t initial_index() const {
+ return initial_index_;
+ }
+
+ site_event& initial_index(std::size_t index) {
+ initial_index_ = index;
+ return *this;
+ }
+
+ bool is_inverse() const {
+ return (flags_ & IS_INVERSE) ? true : false;
+ }
+
+ site_event& inverse() {
+ flags_ ^= IS_INVERSE;
+ return *this;
+ }
+
+ SourceCategory source_category() const {
+ return static_cast<SourceCategory>(flags_ & SOURCE_CATEGORY_BITMASK);
+ }
+
+ site_event& source_category(SourceCategory source_category) {
+ flags_ |= source_category;
+ return *this;
+ }
+
+ bool is_point() const {
+ return (point0_.x() == point1_.x()) && (point0_.y() == point1_.y());
+ }
+
+ bool is_segment() const {
+ return (point0_.x() != point1_.x()) || (point0_.y() != point1_.y());
+ }
+
+private:
+ enum Bits {
+ IS_INVERSE = 0x20 // 32
+ };
+
+ point_type point0_;
+ point_type point1_;
+ std::size_t sorted_index_;
+ std::size_t initial_index_;
+ std::size_t flags_;
+};
+
+// Circle event type.
+// Occurs 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 of the two consecutive 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.
+// Variables:
+// center_x_ - center x-coordinate;
+// center_y_ - center y-coordinate;
+// lower_x_ - leftmost x-coordinate;
+// is_active_ - states whether circle event is still active.
+// NOTE: 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) {}
+
+ coordinate_type x() const {
+ return center_x_;
+ }
+
+ circle_event& x(coordinate_type center_x) {
+ center_x_ = center_x;
+ return *this;
+ }
+
+ coordinate_type y() const {
+ return center_y_;
+ }
+
+ circle_event& y(coordinate_type center_y) {
+ center_y_ = center_y;
+ return *this;
+ }
+
+ coordinate_type lower_x() const {
+ return lower_x_;
+ }
+
+ circle_event& lower_x(coordinate_type lower_x) {
+ lower_x_ = lower_x;
+ return *this;
+ }
+
+ coordinate_type lower_y() const {
+ return center_y_;
+ }
+
+ bool is_active() const {
+ return is_active_;
+ }
+
+ circle_event& deactivate() {
+ is_active_ = false;
+ return *this;
+ }
+
+private:
+ coordinate_type center_x_;
+ coordinate_type center_y_;
+ coordinate_type lower_x_;
+ bool is_active_;
+};
+
// Event queue data structure, holds circle events.
// During algorithm run, some of the circle events disappear (become
// inactive). Priority queue data structure doesn't support
Modified: trunk/boost/polygon/voronoi_builder.hpp
==============================================================================
--- trunk/boost/polygon/voronoi_builder.hpp (original)
+++ trunk/boost/polygon/voronoi_builder.hpp 2012-09-05 16:18:04 EDT (Wed, 05 Sep 2012)
@@ -18,7 +18,7 @@
#include "detail/voronoi_predicates.hpp"
#include "detail/voronoi_structures.hpp"
-#include "voronoi_events.hpp"
+#include "voronoi_geometry_type.hpp"
namespace boost {
namespace polygon {
@@ -129,11 +129,11 @@
}
private:
- typedef point_2d<int_type> point_type;
- typedef site_event<int_type> site_event_type;
+ typedef detail::point_2d<int_type> point_type;
+ typedef detail::site_event<int_type> site_event_type;
typedef typename std::vector<site_event_type>::const_iterator
site_event_iterator_type;
- typedef circle_event<fpt_type> circle_event_type;
+ typedef detail::circle_event<fpt_type> circle_event_type;
typedef typename VP::template point_comparison_predicate<point_type>
point_comparison_predicate;
typedef typename VP::
Modified: trunk/boost/polygon/voronoi_diagram.hpp
==============================================================================
--- trunk/boost/polygon/voronoi_diagram.hpp (original)
+++ trunk/boost/polygon/voronoi_diagram.hpp 2012-09-05 16:18:04 EDT (Wed, 05 Sep 2012)
@@ -13,7 +13,9 @@
#include <vector>
#include "detail/voronoi_ctypes.hpp"
-#include "voronoi_events.hpp"
+#include "detail/voronoi_structures.hpp"
+
+#include "voronoi_geometry_type.hpp"
namespace boost {
namespace polygon {
@@ -351,7 +353,7 @@
}
template <typename CT>
- void _process_single_site(const site_event<CT>& site) {
+ void _process_single_site(const detail::site_event<CT>& site) {
cells_.push_back(cell_type(
site.initial_index(), site.source_category(), NULL));
}
@@ -361,7 +363,8 @@
// Returns a pair of pointers to a new half-edges.
template <typename CT>
std::pair<void*, void*> _insert_new_edge(
- const site_event<CT>& site1, const site_event<CT>& site2) {
+ const detail::site_event<CT>& site1,
+ const detail::site_event<CT>& site2) {
// Get sites' indexes.
int site_index1 = site1.sorted_index();
int site_index2 = site2.sorted_index();
@@ -408,8 +411,8 @@
// new Voronoi vertex point. Returns a pair of pointers to a new half-edges.
template <typename CT1, typename CT2>
std::pair<void*, void*> _insert_new_edge(
- const site_event<CT1>& site1, const site_event<CT1>& site3,
- const circle_event<CT2>& circle, void* data12, void* data23) {
+ const detail::site_event<CT1>& site1, const detail::site_event<CT1>& site3,
+ const detail::circle_event<CT2>& circle, void* data12, void* data23) {
edge_type* edge12 = static_cast<edge_type*>(data12);
edge_type* edge23 = static_cast<edge_type*>(data23);
Modified: trunk/libs/polygon/test/Jamfile.v2
==============================================================================
--- trunk/libs/polygon/test/Jamfile.v2 (original)
+++ trunk/libs/polygon/test/Jamfile.v2 2012-09-05 16:18:04 EDT (Wed, 05 Sep 2012)
@@ -26,7 +26,7 @@
:
[ run voronoi_builder_test.cpp ]
[ run voronoi_ctypes_test.cpp ]
- [ run voronoi_events_test.cpp ]
+ [ run voronoi_geometry_type_test.cpp ]
[ run voronoi_predicates_test.cpp ]
[ run voronoi_robust_fpt_test.cpp ]
[ run voronoi_structures_test.cpp ]
Modified: trunk/libs/polygon/test/voronoi_predicates_test.cpp
==============================================================================
--- trunk/libs/polygon/test/voronoi_predicates_test.cpp (original)
+++ trunk/libs/polygon/test/voronoi_predicates_test.cpp 2012-09-05 16:18:04 EDT (Wed, 05 Sep 2012)
@@ -17,7 +17,7 @@
#include <boost/polygon/detail/voronoi_structures.hpp>
using namespace boost::polygon::detail;
-#include <boost/polygon/voronoi_events.hpp>
+#include <boost/polygon/voronoi_geometry_type.hpp>
using namespace boost::polygon;
ulp_comparison<double> ulp_cmp;
Modified: trunk/libs/polygon/test/voronoi_structures_test.cpp
==============================================================================
--- trunk/libs/polygon/test/voronoi_structures_test.cpp (original)
+++ trunk/libs/polygon/test/voronoi_structures_test.cpp 2012-09-05 16:18:04 EDT (Wed, 05 Sep 2012)
@@ -13,10 +13,82 @@
#include <boost/polygon/detail/voronoi_structures.hpp>
using namespace boost::polygon::detail;
+#include <boost/polygon/voronoi_geometry_type.hpp>
+using namespace boost::polygon;
+
+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, 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);
+}
+
+BOOST_AUTO_TEST_CASE(site_event_test1) {
+ site_type s(1, 2);
+ s.sorted_index(1);
+ s.initial_index(2);
+ s.source_category(SOURCE_CATEGORY_SEGMENT_START_POINT);
+ BOOST_CHECK(s.x0() == 1 && s.x1() == 1);
+ BOOST_CHECK(s.y0() == 2 && s.y1() == 2);
+ BOOST_CHECK(s.is_point());
+ BOOST_CHECK(!s.is_segment());
+ BOOST_CHECK(!s.is_inverse());
+ BOOST_CHECK(s.sorted_index() == 1);
+ BOOST_CHECK(s.initial_index() == 2);
+ BOOST_CHECK(s.source_category() == SOURCE_CATEGORY_SEGMENT_START_POINT);
+}
+
+BOOST_AUTO_TEST_CASE(site_event_test2) {
+ site_type s(1, 2, 3, 4);
+ s.sorted_index(1);
+ s.initial_index(2);
+ s.source_category(SOURCE_CATEGORY_INITIAL_SEGMENT);
+ 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.is_point());
+ BOOST_CHECK(s.is_segment());
+ BOOST_CHECK(!s.is_inverse());
+ BOOST_CHECK(s.source_category() == SOURCE_CATEGORY_INITIAL_SEGMENT);
+
+ 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_CHECK(s.source_category() == SOURCE_CATEGORY_INITIAL_SEGMENT);
+}
+
+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());
+}
+
BOOST_AUTO_TEST_CASE(ordered_queue_test) {
ordered_queue_type q;
BOOST_CHECK(q.empty());