|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r74267 - in sandbox/SOC/2010/sweepline: boost/sweepline boost/sweepline/detail libs/sweepline/test
From: sydorchuk.andriy_at_[hidden]
Date: 2011-09-06 11:04:09
Author: asydorchuk
Date: 2011-09-06 11:04:03 EDT (Tue, 06 Sep 2011)
New Revision: 74267
URL: http://svn.boost.org/trac/boost/changeset/74267
Log:
Changed voronoi diagram output data structures to operate with Boost.Polygon point_data type.
Text files modified:
sandbox/SOC/2010/sweepline/boost/sweepline/detail/voronoi_formation.hpp | 2
sandbox/SOC/2010/sweepline/boost/sweepline/detail/voronoi_fpt_kernel.hpp | 15 ++++---
sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_diagram.hpp | 78 ++++++++++++++++++++--------------------
sandbox/SOC/2010/sweepline/libs/sweepline/test/clipping_test.cpp | 70 +++++++++++++++++-----------------
4 files changed, 84 insertions(+), 81 deletions(-)
Modified: sandbox/SOC/2010/sweepline/boost/sweepline/detail/voronoi_formation.hpp
==============================================================================
--- sandbox/SOC/2010/sweepline/boost/sweepline/detail/voronoi_formation.hpp (original)
+++ sandbox/SOC/2010/sweepline/boost/sweepline/detail/voronoi_formation.hpp 2011-09-06 11:04:03 EDT (Tue, 06 Sep 2011)
@@ -2085,7 +2085,7 @@
site_event_iterator_ = site_events_.begin();
// Init the output data structure.
- output_.init(site_events_.size());
+ output_.reserve(site_events_.size());
}
void clear() {
Modified: sandbox/SOC/2010/sweepline/boost/sweepline/detail/voronoi_fpt_kernel.hpp
==============================================================================
--- sandbox/SOC/2010/sweepline/boost/sweepline/detail/voronoi_fpt_kernel.hpp (original)
+++ sandbox/SOC/2010/sweepline/boost/sweepline/detail/voronoi_fpt_kernel.hpp 2011-09-06 11:04:03 EDT (Tue, 06 Sep 2011)
@@ -27,10 +27,13 @@
// sign-magnitude integers. Values are considered to be almost equal if
// their integer reinterpretatoins differ in not more than maxUlps units.
template <typename T>
- static bool almost_equal(T a, T b, unsigned int ulps);
+ static bool almost_equal(T a, T b, unsigned int ulps) {
+ if (a < b) return static_cast<unsigned int>(b - a) <= ulps;
+ return static_cast<unsigned int>(a - b) <= ulps;
+ }
template<>
- bool almost_equal<float>(float a, float b, unsigned int maxUlps) {
+ static bool almost_equal<float>(float a, float b, unsigned int maxUlps) {
unsigned int ll_a, ll_b;
// Reinterpret double bits as 32-bit signed integer.
@@ -48,7 +51,7 @@
}
template<>
- bool almost_equal<double>(double a, double b, unsigned int maxUlps) {
+ static bool almost_equal<double>(double a, double b, unsigned int maxUlps) {
unsigned long long ll_a, ll_b;
// Reinterpret double bits as 64-bit signed integer.
@@ -73,17 +76,17 @@
}
template <typename T>
- double get_d(const T& value) {
+ static double get_d(const T& value) {
return value.get_d();
}
template <>
- double get_d(const float& value) {
+ static double get_d(const float& value) {
return value;
}
template <>
- double get_d(const double& value) {
+ static double get_d(const double& value) {
return value;
}
Modified: sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_diagram.hpp
==============================================================================
--- sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_diagram.hpp (original)
+++ sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_diagram.hpp 2011-09-06 11:04:03 EDT (Tue, 06 Sep 2011)
@@ -52,15 +52,22 @@
class BRect {
public:
typedef T coordinate_type;
- typedef detail::point_2d<coordinate_type> point_type;
+ typedef point_data<coordinate_type> point_type;
BRect() {}
- BRect(const point_type &p1, const point_type &p2) {
- x_min_ = (std::min)(p1.x(), p2.x());
- y_min_ = (std::min)(p1.y(), p2.y());
- x_max_ = (std::max)(p1.x(), p2.x());
- y_max_ = (std::max)(p1.y(), p2.y());
+ template <typename P>
+ BRect(const P &p) {
+ x_min_ = x_max_ = static_cast<coordinate_type>(p.x());
+ y_min_ = y_max_ = static_cast<coordinate_type>(p.y());
+ }
+
+ template <typename P>
+ BRect(const P &p1, const P &p2) {
+ x_min_ = (std::min)(static_cast<coordinate_type>(p1.x()), static_cast<coordinate_type>(p2.x()));
+ y_min_ = (std::min)(static_cast<coordinate_type>(p1.y()), static_cast<coordinate_type>(p2.y()));
+ x_max_ = (std::max)(static_cast<coordinate_type>(p1.x()), static_cast<coordinate_type>(p2.x()));
+ y_max_ = (std::max)(static_cast<coordinate_type>(p1.y()), static_cast<coordinate_type>(p2.y()));
}
BRect(coordinate_type x_mn, coordinate_type y_mn,
@@ -72,22 +79,23 @@
}
// Extend the rectangle with a new point.
- void update(const point_type &p) {
- x_min_ = (std::min)(x_min_, p.x());
- y_min_ = (std::min)(y_min_, p.y());
- x_max_ = (std::max)(x_max_, p.x());
- y_max_ = (std::max)(y_max_, p.y());
+ template <typename P>
+ void update(const P &p) {
+ x_min_ = (std::min)(x_min_, static_cast<coordinate_type>(p.x()));
+ y_min_ = (std::min)(y_min_, static_cast<coordinate_type>(p.y()));
+ x_max_ = (std::max)(x_max_, static_cast<coordinate_type>(p.x()));
+ y_max_ = (std::max)(y_max_, static_cast<coordinate_type>(p.y()));
}
// Check whether a point is situated inside the bounding rectangle.
bool contains(const point_type &p) const {
- return p.x() > x_min_ && p.x() < x_max_ &&
- p.y() > y_min_ && p.y() < y_max_;
+ return p.x() >= x_min_ && p.x() <= x_max_ &&
+ p.y() >= y_min_ && p.y() <= y_max_;
}
// Check whether the bounding rectangle has a non-zero area.
- bool is_valid() const {
- return (x_min_ < x_max_) && (y_min_ < y_max_);
+ bool verify() const {
+ return (x_min_ <= x_max_) && (y_min_ <= y_max_);
}
// Return the x-coordinate of the bottom left point of the rectangle.
@@ -130,8 +138,7 @@
class voronoi_helper {
public:
typedef T coordinate_type;
- typedef point_data<coordinate_type> out_point_type;
- typedef detail::point_2d<coordinate_type> point_type;
+ typedef point_data<coordinate_type> point_type;
typedef directed_line_segment_data<coordinate_type> segment_type;
typedef directed_line_segment_set_data<coordinate_type> segment_set_type;
typedef BRect<coordinate_type> brect_type;
@@ -170,7 +177,7 @@
// Max_error is the maximum distance (relative to the minor of two
// rectangle sides) allowed between the parabola and line segments
// that interpolate it.
- static std::vector<out_point_type> get_point_interpolation(
+ static std::vector<point_type> get_point_interpolation(
const voronoi_edge<coordinate_type> *edge,
const BRect<coordinate_type> &brect,
double max_error) {
@@ -250,14 +257,7 @@
edge_points[0] = edge->vertex0()->vertex();
}
}
- std::vector<out_point_type> ret_val;
- for (typename std::vector<point_type>::const_iterator it = edge_points.begin();
- it != edge_points.end(); ++it) {
- coordinate_type x = it->x();
- coordinate_type y = it->y();
- ret_val.push_back(out_point_type(x, y));
- }
- return ret_val;
+ return edge_points;
}
// Interpolate voronoi edge with a set of segments to satisfy maximal
@@ -266,7 +266,7 @@
const voronoi_edge<coordinate_type> *edge,
const BRect<coordinate_type> &brect,
double max_error) {
- std::vector<out_point_type> point_interpolation =
+ std::vector<point_type> point_interpolation =
get_point_interpolcation(edge, brect, max_error);
segment_set_type ret_val;
for (size_t i = 1; i < point_interpolation.size(); ++i)
@@ -534,14 +534,14 @@
class voronoi_cell {
public:
typedef T coordinate_type;
- typedef detail::point_2d<coordinate_type> point_type;
- typedef detail::site_event<coordinate_type> site_event_type;
+ typedef point_data<coordinate_type> point_type;
typedef voronoi_edge<coordinate_type> voronoi_edge_type;
- voronoi_cell(const point_type &p1, const point_type &p2,
+ template <typename P>
+ voronoi_cell(const P &p1, const P &p2,
bool contains_segment, voronoi_edge_type *edge) :
- point0_(p1),
- point1_(p2),
+ point0_(static_cast<coordinate_type>(p1.x()), static_cast<coordinate_type>(p1.y())),
+ point1_(static_cast<coordinate_type>(p2.x()), static_cast<coordinate_type>(p2.y())),
contains_segment_(contains_segment),
incident_edge_(edge),
num_incident_edges_(0) {}
@@ -583,11 +583,12 @@
class voronoi_vertex {
public:
typedef T coordinate_type;
- typedef detail::point_2d<T> point_type;
+ typedef point_data<T> point_type;
typedef voronoi_edge<coordinate_type> voronoi_edge_type;
- voronoi_vertex(const point_type &vertex, voronoi_edge_type *edge) :
- vertex_(vertex),
+ template <typename P>
+ voronoi_vertex(const P &vertex, voronoi_edge_type *edge) :
+ vertex_(static_cast<coordinate_type>(vertex.x()), static_cast<coordinate_type>(vertex.y())),
incident_edge_(edge),
num_incident_edges_(3) {}
@@ -734,7 +735,7 @@
class voronoi_output {
public:
typedef T coordinate_type;
- typedef detail::point_2d<coordinate_type> point_type;
+ typedef point_data<coordinate_type> point_type;
typedef voronoi_cell<coordinate_type> voronoi_cell_type;
typedef std::vector<voronoi_cell_type> voronoi_cells_type;
@@ -806,7 +807,7 @@
friend class detail::voronoi_builder<int>;
- void init(int num_sites) {
+ void reserve(int num_sites) {
// Resize cell vector to avoid reallocations.
cell_records_.reserve(num_sites);
@@ -819,8 +820,7 @@
// Update the voronoi output in case of a single point input.
void process_single_site(const site_event_type &site) {
// Update bounding rectangle.
- voronoi_rect_ = BRect<coordinate_type>(site.point0(),
- site.point0());
+ voronoi_rect_ = BRect<coordinate_type>(site.point0());
// Update cell records.
cell_records_.push_back(voronoi_cell_type(site.point0(),
Modified: sandbox/SOC/2010/sweepline/libs/sweepline/test/clipping_test.cpp
==============================================================================
--- sandbox/SOC/2010/sweepline/libs/sweepline/test/clipping_test.cpp (original)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/test/clipping_test.cpp 2011-09-06 11:04:03 EDT (Tue, 06 Sep 2011)
@@ -21,16 +21,16 @@
BOOST_AUTO_TEST_CASE_TEMPLATE(segment_clipping_test1, T, test_types) {
BRect<T> test_rect(static_cast<T>(0.0), static_cast<T>(-1.0),
static_cast<T>(4.0), static_cast<T>(2.0));
- point_2d<T> test_origin(static_cast<T>(-1), static_cast<T>(3));
- point_2d<T> test_direction1_1(static_cast<T>(8), static_cast<T>(-8));
- point_2d<T> test_direction1_2(static_cast<T>(2), static_cast<T>(-2));
- point_2d<T> test_direction1_3(static_cast<T>(0.5), static_cast<T>(-0.5));
- point_2d<T> test_direction2(static_cast<T>(2), static_cast<T>(-4));
- point_2d<T> test_direction3(static_cast<T>(2), static_cast<T>(-1));
- point_2d<T> test_direction4(static_cast<T>(1), static_cast<T>(-4));
- point_2d<T> test_direction5(static_cast<T>(5), static_cast<T>(-1));
+ point_data<T> test_origin(static_cast<T>(-1), static_cast<T>(3));
+ point_data<T> test_direction1_1(static_cast<T>(8), static_cast<T>(-8));
+ point_data<T> test_direction1_2(static_cast<T>(2), static_cast<T>(-2));
+ point_data<T> test_direction1_3(static_cast<T>(0.5), static_cast<T>(-0.5));
+ point_data<T> test_direction2(static_cast<T>(2), static_cast<T>(-4));
+ point_data<T> test_direction3(static_cast<T>(2), static_cast<T>(-1));
+ point_data<T> test_direction4(static_cast<T>(1), static_cast<T>(-4));
+ point_data<T> test_direction5(static_cast<T>(5), static_cast<T>(-1));
- std::vector< point_2d<T> > intersections;
+ std::vector< point_data<T> > intersections;
voronoi_helper<T>::find_intersections(test_origin, test_direction1_1,
voronoi_helper<T>::SEGMENT,
test_rect, intersections);
@@ -86,13 +86,13 @@
BOOST_AUTO_TEST_CASE_TEMPLATE(segment_clipping_test2, T, test_types) {
BRect<T> test_rect(static_cast<T>(0.0), static_cast<T>(-1.0),
static_cast<T>(4.0), static_cast<T>(3.0));
- std::vector< point_2d<T> > intersections;
- point_2d<T> test_origin(2, 1);
+ std::vector< point_data<T> > intersections;
+ point_data<T> test_origin(2, 1);
for (int i = -50; i <= 50; i++)
for (int j = -50; j <= 50; j++) {
intersections.clear();
- point_2d<T> test_direction(static_cast<T>(i), static_cast<T>(j));
+ point_data<T> test_direction(static_cast<T>(i), static_cast<T>(j));
voronoi_helper<T>::find_intersections(test_origin, test_direction,
voronoi_helper<T>::SEGMENT, test_rect, intersections);
if (abs(i) >= 2 || abs(j) >= 2)
@@ -105,15 +105,15 @@
BOOST_AUTO_TEST_CASE_TEMPLATE(segment_clipping_test3, T, test_types) {
BRect<T> test_rect(static_cast<T>(0.0), static_cast<T>(-1.0),
static_cast<T>(4.0), static_cast<T>(3.0));
- std::vector< point_2d<T> > intersections;
- point_2d<T> test_origin(2, 1);
+ std::vector< point_data<T> > intersections;
+ point_data<T> test_origin(2, 1);
for (int i = -50; i <= 50; i++)
for (int j = -50; j <= 50; j++) {
intersections.clear();
T x = static_cast<T>(i) / static_cast<T>(26);
T y = static_cast<T>(j) / static_cast<T>(26);
- point_2d<T> test_direction(x, y);
+ point_data<T> test_direction(x, y);
voronoi_helper<T>::find_intersections(test_origin, test_direction,
voronoi_helper<T>::SEGMENT, test_rect, intersections);
BOOST_CHECK_EQUAL(static_cast<int>(intersections.size()), 0);
@@ -124,14 +124,14 @@
BOOST_AUTO_TEST_CASE_TEMPLATE(ray_clipping_test1, T, test_types) {
BRect<T> test_rect(static_cast<T>(0.0), static_cast<T>(-1.0),
static_cast<T>(4.0), static_cast<T>(2.0));
- point_2d<T> test_origin(static_cast<T>(-1), static_cast<T>(3));
- point_2d<T> test_direction1(static_cast<T>(2), static_cast<T>(-2));
- point_2d<T> test_direction2(static_cast<T>(2), static_cast<T>(-4));
- point_2d<T> test_direction3(static_cast<T>(2), static_cast<T>(-1));
- point_2d<T> test_direction4(static_cast<T>(1), static_cast<T>(-4));
- point_2d<T> test_direction5(static_cast<T>(5), static_cast<T>(-1));
+ point_data<T> test_origin(static_cast<T>(-1), static_cast<T>(3));
+ point_data<T> test_direction1(static_cast<T>(2), static_cast<T>(-2));
+ point_data<T> test_direction2(static_cast<T>(2), static_cast<T>(-4));
+ point_data<T> test_direction3(static_cast<T>(2), static_cast<T>(-1));
+ point_data<T> test_direction4(static_cast<T>(1), static_cast<T>(-4));
+ point_data<T> test_direction5(static_cast<T>(5), static_cast<T>(-1));
- std::vector< point_2d<T> > intersections;
+ std::vector< point_data<T> > intersections;
voronoi_helper<T>::find_intersections(test_origin, test_direction1,
voronoi_helper<T>::RAY, test_rect, intersections);
BOOST_CHECK_EQUAL(static_cast<int>(intersections.size()), 2);
@@ -176,15 +176,15 @@
BOOST_AUTO_TEST_CASE_TEMPLATE(ray_clipping_test2, T, test_types) {
BRect<T> test_rect(static_cast<T>(0.0), static_cast<T>(-1.0),
static_cast<T>(4.0), static_cast<T>(3.0));
- std::vector< point_2d<T> > intersections;
- point_2d<T> test_origin(2, 1);
+ std::vector< point_data<T> > intersections;
+ point_data<T> test_origin(2, 1);
for (int i = -50; i <= 50; i++)
for (int j = -50; j <= 50; j++) {
intersections.clear();
T x = static_cast<T>(i) / static_cast<T>(26);
T y = static_cast<T>(j) / static_cast<T>(26);
- point_2d<T> test_direction(x, y);
+ point_data<T> test_direction(x, y);
voronoi_helper<T>::find_intersections(test_origin, test_direction,
voronoi_helper<T>::RAY, test_rect, intersections);
if (i && j)
@@ -196,14 +196,14 @@
BOOST_AUTO_TEST_CASE_TEMPLATE(line_clipping_test1, T, test_types) {
BRect<T> test_rect(static_cast<T>(0.0), static_cast<T>(-1.0),
static_cast<T>(4.0), static_cast<T>(2.0));
- point_2d<T> test_origin(static_cast<T>(-1), static_cast<T>(3));
- point_2d<T> test_direction1(static_cast<T>(-1), static_cast<T>(1));
- point_2d<T> test_direction2(static_cast<T>(-1), static_cast<T>(2));
- point_2d<T> test_direction3(static_cast<T>(-2), static_cast<T>(1));
- point_2d<T> test_direction4(static_cast<T>(-1), static_cast<T>(4));
- point_2d<T> test_direction5(static_cast<T>(-5), static_cast<T>(1));
+ point_data<T> test_origin(static_cast<T>(-1), static_cast<T>(3));
+ point_data<T> test_direction1(static_cast<T>(-1), static_cast<T>(1));
+ point_data<T> test_direction2(static_cast<T>(-1), static_cast<T>(2));
+ point_data<T> test_direction3(static_cast<T>(-2), static_cast<T>(1));
+ point_data<T> test_direction4(static_cast<T>(-1), static_cast<T>(4));
+ point_data<T> test_direction5(static_cast<T>(-5), static_cast<T>(1));
- std::vector< point_2d<T> > intersections;
+ std::vector< point_data<T> > intersections;
voronoi_helper<T>::find_intersections(test_origin, test_direction1,
voronoi_helper<T>::LINE, test_rect, intersections);
BOOST_CHECK_EQUAL(static_cast<int>(intersections.size()), 2);
@@ -248,15 +248,15 @@
BOOST_AUTO_TEST_CASE_TEMPLATE(line_clipping_test2, T, test_types) {
BRect<T> test_rect(static_cast<T>(0.0), static_cast<T>(-1.0),
static_cast<T>(4.0), static_cast<T>(3.0));
- std::vector< point_2d<T> > intersections;
- point_2d<T> test_origin(2, 1);
+ std::vector< point_data<T> > intersections;
+ point_data<T> test_origin(2, 1);
for (int i = -50; i <= 50; i++)
for (int j = -50; j <= 50; j++) {
intersections.clear();
T x = static_cast<T>(i) / static_cast<T>(26);
T y = static_cast<T>(j) / static_cast<T>(26);
- point_2d<T> test_direction(x, y);
+ point_data<T> test_direction(x, y);
voronoi_helper<T>::find_intersections(test_origin, test_direction,
voronoi_helper<T>::LINE, test_rect, intersections);
if (i && j)
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