Boost logo

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