Subject: [Boost-commit] svn:boost r80400 - in trunk: boost/polygon boost/polygon/detail libs/polygon/example libs/polygon/test
From: sydorchuk.andriy_at_[hidden]
Date: 2012-09-04 17:26:12
Author: asydorchuk
Date: 2012-09-04 17:26:11 EDT (Tue, 04 Sep 2012)
New Revision: 80400
URL: http://svn.boost.org/trac/boost/changeset/80400
Log:
Polygon: adding voronoi_events to the public part of the library.
Added:
trunk/boost/polygon/voronoi_events.hpp (contents, props changed)
trunk/libs/polygon/test/voronoi_events_test.cpp (contents, props changed)
Text files modified:
trunk/boost/polygon/detail/voronoi_structures.hpp | 314 ----------------------------------------
trunk/boost/polygon/voronoi_builder.hpp | 22 +-
trunk/boost/polygon/voronoi_diagram.hpp | 33 ++--
trunk/libs/polygon/example/voronoi_visualizer.cpp | 4
trunk/libs/polygon/test/Jamfile.v2 | 1
trunk/libs/polygon/test/voronoi_predicates_test.cpp | 3
trunk/libs/polygon/test/voronoi_structures_test.cpp | 83 ----------
7 files changed, 32 insertions(+), 428 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-04 17:26:11 EDT (Tue, 04 Sep 2012)
@@ -17,320 +17,6 @@
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_;
-};
-
-// Represents topology type of the voronoi site.
-enum GeometryCategory {
- GEOMETRY_CATEGORY_POINT = 0x0,
- GEOMETRY_CATEGORY_SEGMENT = 0x1
-};
-
-// Represents category of the input source that forms Voronoi cell.
-enum SourceCategory {
- // Point subtypes.
- SOURCE_CATEGORY_SINGLE_POINT = 0x0,
- SOURCE_CATEGORY_SEGMENT_START_POINT = 0x1,
- SOURCE_CATEGORY_SEGMENT_END_POINT = 0x2,
-
- // Segment subtypes.
- SOURCE_CATEGORY_INITIAL_SEGMENT = 0x8,
- SOURCE_CATEGORY_REVERSE_SEGMENT = 0x9,
-
- SOURCE_CATEGORY_GEOMETRY_SHIFT = 0x3,
- SOURCE_CATEGORY_BITMASK = 0x1F
-};
-
-bool belongs(
- const SourceCategory& source_category,
- const GeometryCategory& geometry_category) {
- return (static_cast<std::size_t>(source_category) >> SOURCE_CATEGORY_GEOMETRY_SHIFT) ==
- static_cast<std::size_t>(geometry_category);
-}
-
-// 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;
- }
-
- 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-04 17:26:11 EDT (Tue, 04 Sep 2012)
@@ -18,6 +18,8 @@
#include "detail/voronoi_predicates.hpp"
#include "detail/voronoi_structures.hpp"
+#include "voronoi_events.hpp"
+
namespace boost {
namespace polygon {
// GENERAL INFO:
@@ -51,7 +53,7 @@
std::size_t insert_point(const int_type& x, const int_type& y) {
site_events_.push_back(site_event_type(x, y));
site_events_.back().initial_index(index_);
- site_events_.back().source_category(detail::SOURCE_CATEGORY_SINGLE_POINT);
+ site_events_.back().source_category(SOURCE_CATEGORY_SINGLE_POINT);
return index_++;
}
@@ -66,25 +68,21 @@
point_type p1(x1, y1);
site_events_.push_back(site_event_type(p1));
site_events_.back().initial_index(index_);
- site_events_.back().source_category(
- detail::SOURCE_CATEGORY_SEGMENT_START_POINT);
+ site_events_.back().source_category(SOURCE_CATEGORY_SEGMENT_START_POINT);
// Set up end point site.
point_type p2(x2, y2);
site_events_.push_back(site_event_type(p2));
site_events_.back().initial_index(index_);
- site_events_.back().source_category(
- detail::SOURCE_CATEGORY_SEGMENT_END_POINT);
+ site_events_.back().source_category(SOURCE_CATEGORY_SEGMENT_END_POINT);
// Set up segment site.
if (point_comparison_(p1, p2)) {
site_events_.push_back(site_event_type(p1, p2));
- site_events_.back().source_category(
- detail::SOURCE_CATEGORY_INITIAL_SEGMENT);
+ site_events_.back().source_category(SOURCE_CATEGORY_INITIAL_SEGMENT);
} else {
site_events_.push_back(site_event_type(p2, p1));
- site_events_.back().source_category(
- detail::SOURCE_CATEGORY_REVERSE_SEGMENT);
+ site_events_.back().source_category(SOURCE_CATEGORY_REVERSE_SEGMENT);
}
site_events_.back().initial_index(index_);
return index_++;
@@ -131,11 +129,11 @@
}
private:
- typedef detail::point_2d<int_type> point_type;
- typedef detail::site_event<int_type> site_event_type;
+ typedef point_2d<int_type> point_type;
+ typedef site_event<int_type> site_event_type;
typedef typename std::vector<site_event_type>::const_iterator
site_event_iterator_type;
- typedef detail::circle_event<fpt_type> circle_event_type;
+ typedef 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-04 17:26:11 EDT (Tue, 04 Sep 2012)
@@ -13,7 +13,7 @@
#include <vector>
#include "detail/voronoi_ctypes.hpp"
-#include "detail/voronoi_structures.hpp"
+#include "voronoi_events.hpp"
namespace boost {
namespace polygon {
@@ -35,7 +35,7 @@
typedef std::size_t color_type;
typedef voronoi_edge<coordinate_type> voronoi_edge_type;
typedef std::size_t source_index_type;
- typedef detail::SourceCategory source_category_type;
+ typedef SourceCategory source_category_type;
voronoi_cell(const source_index_type& source_index,
const source_category_type& source_category,
@@ -47,13 +47,13 @@
// Returns true if the cell contains point site, false else.
bool contains_point() const {
source_category_type source_category = this->source_category();
- return detail::belongs(source_category, detail::GEOMETRY_CATEGORY_POINT);
+ return belongs(source_category, GEOMETRY_CATEGORY_POINT);
}
// Returns true if the cell contains segment site, false else.
bool contains_segment() const {
source_category_type source_category = this->source_category();
- return detail::belongs(source_category, detail::GEOMETRY_CATEGORY_SEGMENT);
+ return belongs(source_category, GEOMETRY_CATEGORY_SEGMENT);
}
source_index_type source_index() const {
@@ -61,8 +61,7 @@
}
source_category_type source_category() const {
- return static_cast<source_category_type>(
- color_ & detail::SOURCE_CATEGORY_BITMASK);
+ return static_cast<source_category_type>(color_ & SOURCE_CATEGORY_BITMASK);
}
// Degenerate cells don't have any incident edges.
@@ -222,25 +221,25 @@
// Returns true if the edge is linear (segment, ray, line).
// Returns false if the edge is curved (parabolic arc).
bool is_linear() const {
- return color_ & BIT_IS_LINEAR;
+ return (color_ & BIT_IS_LINEAR) ? true : false;
}
// Returns true if the edge is curved (parabolic arc).
// Returns false if the edge is linear (segment, ray, line).
bool is_curved() const {
- return !(color_ & BIT_IS_LINEAR);
+ return (color_ & BIT_IS_LINEAR) ? false : true;
}
// Returns false if edge goes through the endpoint of the segment.
// Returns true else.
bool is_primary() const {
- return color_ & BIT_IS_PRIMARY;
+ return (color_ & BIT_IS_PRIMARY) ? true : false;
}
// Returns true if edge goes through the endpoint of the segment.
// Returns false else.
bool is_secondary() const {
- return !(color_ & BIT_IS_PRIMARY);
+ return (color_ & BIT_IS_PRIMARY) ? false : true;
}
color_type color() const { return color_ >> BITS_SHIFT; }
@@ -351,8 +350,8 @@
edges_.reserve((num_sites << 2) + (num_sites << 1));
}
-template <typename SEvent>
- void _process_single_site(const SEvent& site) {
+ template <typename CT>
+ void _process_single_site(const site_event<CT>& site) {
cells_.push_back(cell_type(
site.initial_index(), site.source_category(), NULL));
}
@@ -360,9 +359,9 @@
// Insert a new half-edge into the output data structure.
// Takes as input left and right sites that form a new bisector.
// Returns a pair of pointers to a new half-edges.
- template <typename SEvent>
+ template <typename CT>
std::pair<void*, void*> _insert_new_edge(
- const SEvent& site1, const SEvent& site2) {
+ const site_event<CT>& site1, const site_event<CT>& site2) {
// Get sites' indexes.
int site_index1 = site1.sorted_index();
int site_index2 = site2.sorted_index();
@@ -407,10 +406,10 @@
// that corresponds to the intersection point of the two old half-edges,
// pointers to those half-edges. Half-edges' direction goes out of the
// new Voronoi vertex point. Returns a pair of pointers to a new half-edges.
- template <typename SEvent, typename CEvent>
+ template <typename CT1, typename CT2>
std::pair<void*, void*> _insert_new_edge(
- const SEvent& site1, const SEvent& site3, const CEvent& circle,
- void* data12, void* data23) {
+ const site_event<CT1>& site1, const site_event<CT1>& site3,
+ const circle_event<CT2>& circle, void* data12, void* data23) {
edge_type* edge12 = static_cast<edge_type*>(data12);
edge_type* edge23 = static_cast<edge_type*>(data23);
Added: trunk/boost/polygon/voronoi_events.hpp
==============================================================================
--- (empty file)
+++ trunk/boost/polygon/voronoi_events.hpp 2012-09-04 17:26:11 EDT (Tue, 04 Sep 2012)
@@ -0,0 +1,332 @@
+// Boost.Polygon library voronoi_events.hpp header file
+
+// Copyright Andrii Sydorchuk 2010-2012.
+// 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_EVENTS
+#define BOOST_POLYGON_VORONOI_EVENTS
+
+namespace boost {
+namespace polygon {
+// Warning: only the below two enums and routine should be used by users.
+// Represents topology type of the voronoi site.
+enum GeometryCategory {
+ GEOMETRY_CATEGORY_POINT = 0x0,
+ GEOMETRY_CATEGORY_SEGMENT = 0x1
+};
+
+// Represents category of the input source that forms Voronoi cell.
+enum SourceCategory {
+ // Point subtypes.
+ SOURCE_CATEGORY_SINGLE_POINT = 0x0,
+ SOURCE_CATEGORY_SEGMENT_START_POINT = 0x1,
+ SOURCE_CATEGORY_SEGMENT_END_POINT = 0x2,
+
+ // Segment subtypes.
+ SOURCE_CATEGORY_INITIAL_SEGMENT = 0x8,
+ SOURCE_CATEGORY_REVERSE_SEGMENT = 0x9,
+
+ SOURCE_CATEGORY_GEOMETRY_SHIFT = 0x3,
+ SOURCE_CATEGORY_BITMASK = 0x1F
+};
+
+bool belongs(
+ const SourceCategory& source_category,
+ const GeometryCategory& geometry_category) {
+ return (static_cast<std::size_t>(source_category) >>
+ SOURCE_CATEGORY_GEOMETRY_SHIFT) ==
+ static_cast<std::size_t>(geometry_category);
+}
+
+// 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_;
+};
+} // polygon
+} // boost
+
+#endif // BOOST_POLYGON_VORONOI_EVENTS
Modified: trunk/libs/polygon/example/voronoi_visualizer.cpp
==============================================================================
--- trunk/libs/polygon/example/voronoi_visualizer.cpp (original)
+++ trunk/libs/polygon/example/voronoi_visualizer.cpp 2012-09-04 17:26:11 EDT (Tue, 04 Sep 2012)
@@ -349,11 +349,11 @@
point_type retrieve_point(const cell_type& cell) {
source_index_type index = cell.source_index();
source_category_type category = cell.source_category();
- if (category == detail::SOURCE_CATEGORY_SINGLE_POINT) {
+ if (category == SOURCE_CATEGORY_SINGLE_POINT) {
return point_data_[index];
}
index -= point_data_.size();
- if (category == detail::SOURCE_CATEGORY_SEGMENT_START_POINT) {
+ if (category == SOURCE_CATEGORY_SEGMENT_START_POINT) {
return low(segment_data_[index]);
} else {
return high(segment_data_[index]);
Modified: trunk/libs/polygon/test/Jamfile.v2
==============================================================================
--- trunk/libs/polygon/test/Jamfile.v2 (original)
+++ trunk/libs/polygon/test/Jamfile.v2 2012-09-04 17:26:11 EDT (Tue, 04 Sep 2012)
@@ -26,6 +26,7 @@
:
[ run voronoi_builder_test.cpp ]
[ run voronoi_ctypes_test.cpp ]
+ [ run voronoi_events_test.cpp ]
[ run voronoi_predicates_test.cpp ]
[ run voronoi_robust_fpt_test.cpp ]
[ run voronoi_structures_test.cpp ]
Added: trunk/libs/polygon/test/voronoi_events_test.cpp
==============================================================================
--- (empty file)
+++ trunk/libs/polygon/test/voronoi_events_test.cpp 2012-09-04 17:26:11 EDT (Tue, 04 Sep 2012)
@@ -0,0 +1,98 @@
+// Boost.Polygon library voronoi_events_test.cpp file
+
+// Copyright Andrii Sydorchuk 2010-2012.
+// 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 voronoi_events_test
+
+#include <boost/test/test_case_template.hpp>
+#include <boost/polygon/voronoi_events.hpp>
+using namespace boost::polygon;
+
+typedef point_2d<int> point_type;
+typedef site_event<int> site_type;
+typedef circle_event<int> circle_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(source_category_test1) {
+ BOOST_CHECK(belongs(SOURCE_CATEGORY_SINGLE_POINT, GEOMETRY_CATEGORY_POINT));
+ BOOST_CHECK(belongs(SOURCE_CATEGORY_SEGMENT_START_POINT, GEOMETRY_CATEGORY_POINT));
+ BOOST_CHECK(belongs(SOURCE_CATEGORY_SEGMENT_END_POINT, GEOMETRY_CATEGORY_POINT));
+ BOOST_CHECK(!belongs(SOURCE_CATEGORY_INITIAL_SEGMENT, GEOMETRY_CATEGORY_POINT));
+ BOOST_CHECK(!belongs(SOURCE_CATEGORY_REVERSE_SEGMENT, GEOMETRY_CATEGORY_POINT));
+
+ BOOST_CHECK(!belongs(SOURCE_CATEGORY_SINGLE_POINT, GEOMETRY_CATEGORY_SEGMENT));
+ BOOST_CHECK(!belongs(SOURCE_CATEGORY_SEGMENT_START_POINT, GEOMETRY_CATEGORY_SEGMENT));
+ BOOST_CHECK(!belongs(SOURCE_CATEGORY_SEGMENT_END_POINT, GEOMETRY_CATEGORY_SEGMENT));
+ BOOST_CHECK(belongs(SOURCE_CATEGORY_INITIAL_SEGMENT, GEOMETRY_CATEGORY_SEGMENT));
+ BOOST_CHECK(belongs(SOURCE_CATEGORY_REVERSE_SEGMENT, GEOMETRY_CATEGORY_SEGMENT));
+}
+
+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());
+}
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-04 17:26:11 EDT (Tue, 04 Sep 2012)
@@ -17,6 +17,9 @@
#include <boost/polygon/detail/voronoi_structures.hpp>
using namespace boost::polygon::detail;
+#include <boost/polygon/voronoi_events.hpp>
+using namespace boost::polygon;
+
ulp_comparison<double> ulp_cmp;
typedef voronoi_predicates< voronoi_ctype_traits<int> > VP;
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-04 17:26:11 EDT (Tue, 04 Sep 2012)
@@ -13,93 +13,10 @@
#include <boost/polygon/detail/voronoi_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, 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(source_category_test1) {
- BOOST_CHECK(belongs(SOURCE_CATEGORY_SINGLE_POINT, GEOMETRY_CATEGORY_POINT));
- BOOST_CHECK(belongs(SOURCE_CATEGORY_SEGMENT_START_POINT, GEOMETRY_CATEGORY_POINT));
- BOOST_CHECK(belongs(SOURCE_CATEGORY_SEGMENT_END_POINT, GEOMETRY_CATEGORY_POINT));
- BOOST_CHECK(!belongs(SOURCE_CATEGORY_INITIAL_SEGMENT, GEOMETRY_CATEGORY_POINT));
- BOOST_CHECK(!belongs(SOURCE_CATEGORY_REVERSE_SEGMENT, GEOMETRY_CATEGORY_POINT));
-
- BOOST_CHECK(!belongs(SOURCE_CATEGORY_SINGLE_POINT, GEOMETRY_CATEGORY_SEGMENT));
- BOOST_CHECK(!belongs(SOURCE_CATEGORY_SEGMENT_START_POINT, GEOMETRY_CATEGORY_SEGMENT));
- BOOST_CHECK(!belongs(SOURCE_CATEGORY_SEGMENT_END_POINT, GEOMETRY_CATEGORY_SEGMENT));
- BOOST_CHECK(belongs(SOURCE_CATEGORY_INITIAL_SEGMENT, GEOMETRY_CATEGORY_SEGMENT));
- BOOST_CHECK(belongs(SOURCE_CATEGORY_REVERSE_SEGMENT, GEOMETRY_CATEGORY_SEGMENT));
-}
-
-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());