Boost logo

Boost-Commit :

Subject: [Boost-commit] svn:boost r86223 - in branches/release: boost/polygon/detail libs/polygon/test
From: sydorchuk.andriy_at_[hidden]
Date: 2013-10-09 18:17:20


Author: asydorchuk
Date: 2013-10-09 18:17:20 EDT (Wed, 09 Oct 2013)
New Revision: 86223
URL: http://svn.boost.org/trac/boost/changeset/86223

Log:
Polygon: fixing (site, circle) and (circle, circle) comparison.

Text files modified:
   branches/release/boost/polygon/detail/voronoi_predicates.hpp | 49 ++++++++++++++++++++++----------------
   branches/release/libs/polygon/test/polygon_segment_test.cpp | 7 ++++-
   branches/release/libs/polygon/test/voronoi_predicates_test.cpp | 50 ++++++++++++++++++++++++++++++++++++++-
   3 files changed, 81 insertions(+), 25 deletions(-)

Modified: branches/release/boost/polygon/detail/voronoi_predicates.hpp
==============================================================================
--- branches/release/boost/polygon/detail/voronoi_predicates.hpp Wed Oct 9 18:09:39 2013 (r86222)
+++ branches/release/boost/polygon/detail/voronoi_predicates.hpp 2013-10-09 18:17:20 EDT (Wed, 09 Oct 2013) (r86223)
@@ -35,8 +35,7 @@
 
   enum {
     ULPS = 64,
- ULPSx2 = 128,
- ULPSx5 = 320
+ ULPSx2 = 128
   };
 
   template <typename Point>
@@ -161,32 +160,21 @@
 
     bool operator()(const site_type& lhs, const circle_type& rhs) const {
       typename ulp_cmp_type::Result xCmp =
- ulp_cmp(to_fpt(lhs.x0()), to_fpt(rhs.lower_x()), ULPSx5);
- if (xCmp != ulp_cmp_type::EQUAL)
- return xCmp == ulp_cmp_type::LESS;
- typename ulp_cmp_type::Result yCmp =
- ulp_cmp(to_fpt(lhs.y0()), to_fpt(rhs.lower_y()), ULPSx5);
- return yCmp == ulp_cmp_type::LESS;
+ ulp_cmp(to_fpt(lhs.x0()), to_fpt(rhs.lower_x()), ULPS);
+ return xCmp == ulp_cmp_type::LESS;
     }
 
     bool operator()(const circle_type& lhs, const site_type& rhs) const {
       typename ulp_cmp_type::Result xCmp =
- ulp_cmp(to_fpt(lhs.lower_x()), to_fpt(rhs.x0()), ULPSx5);
- if (xCmp != ulp_cmp_type::EQUAL)
- return xCmp == ulp_cmp_type::LESS;
- typename ulp_cmp_type::Result yCmp =
- ulp_cmp(to_fpt(lhs.lower_y()), to_fpt(rhs.y0()), ULPSx5);
- return yCmp == ulp_cmp_type::LESS;
+ ulp_cmp(to_fpt(lhs.lower_x()), to_fpt(rhs.x0()), ULPS);
+ return xCmp == ulp_cmp_type::LESS;
     }
 
     bool operator()(const circle_type& lhs, const circle_type& rhs) const {
- typename ulp_cmp_type::Result xCmp =
- ulp_cmp(to_fpt(lhs.lower_x()), to_fpt(rhs.lower_x()), ULPSx2);
- if (xCmp != ulp_cmp_type::EQUAL)
- return xCmp == ulp_cmp_type::LESS;
- typename ulp_cmp_type::Result yCmp =
- ulp_cmp(to_fpt(lhs.lower_y()), to_fpt(rhs.lower_y()), ULPSx2);
- return yCmp == ulp_cmp_type::LESS;
+ if (lhs.lower_x() != rhs.lower_x()) {
+ return lhs.lower_x() < rhs.lower_x();
+ }
+ return lhs.y() < rhs.y();
     }
 
    private:
@@ -1510,10 +1498,29 @@
           }
         }
       }
+ if (lies_outside_vertical_segment(circle, site1) ||
+ lies_outside_vertical_segment(circle, site2) ||
+ lies_outside_vertical_segment(circle, site3)) {
+ return false;
+ }
       return true;
     }
 
    private:
+ bool lies_outside_vertical_segment(
+ const circle_type& c, const site_type& s) {
+ if (!s.is_segment() || !is_vertical(s)) {
+ return false;
+ }
+ fpt_type y0 = to_fpt(s.is_inverse() ? s.y1() : s.y0());
+ fpt_type y1 = to_fpt(s.is_inverse() ? s.y0() : s.y1());
+ return ulp_cmp(c.y(), y0, ULPS) == ulp_cmp_type::LESS ||
+ ulp_cmp(c.y(), y1, ULPS) == ulp_cmp_type::MORE;
+ }
+
+ private:
+ to_fpt_converter to_fpt;
+ ulp_cmp_type ulp_cmp;
     circle_existence_predicate_type circle_existence_predicate_;
     circle_formation_functor_type circle_formation_functor_;
   };

Modified: branches/release/libs/polygon/test/polygon_segment_test.cpp
==============================================================================
--- branches/release/libs/polygon/test/polygon_segment_test.cpp Wed Oct 9 18:09:39 2013 (r86222)
+++ branches/release/libs/polygon/test/polygon_segment_test.cpp 2013-10-09 18:17:20 EDT (Wed, 09 Oct 2013) (r86223)
@@ -70,8 +70,10 @@
 
 template <typename T>
 struct Segment {
- point_data<T> p0;
- point_data<T> p1;
+ typedef T coordinate_type;
+ typedef point_data<T> point_type;
+ point_type p0;
+ point_type p1;
 };
 
 namespace boost {
@@ -93,6 +95,7 @@
 
   template <typename T>
   struct segment_mutable_traits< Segment<T> > {
+ typedef T coordinate_type;
     typedef point_data<T> point_type;
 
     static void set(

Modified: branches/release/libs/polygon/test/voronoi_predicates_test.cpp
==============================================================================
--- branches/release/libs/polygon/test/voronoi_predicates_test.cpp Wed Oct 9 18:09:39 2013 (r86222)
+++ branches/release/libs/polygon/test/voronoi_predicates_test.cpp 2013-10-09 18:17:20 EDT (Wed, 09 Oct 2013) (r86223)
@@ -132,9 +132,9 @@
 BOOST_AUTO_TEST_CASE(event_comparison_test5) {
   circle_type circle(1, 2, 3);
   CHECK_EVENT_COMPARISON(circle, site_type(0, 100), false, true);
- CHECK_EVENT_COMPARISON(circle, site_type(3, 0), false, true);
+ CHECK_EVENT_COMPARISON(circle, site_type(3, 0), false, false);
   CHECK_EVENT_COMPARISON(circle, site_type(3, 2), false, false);
- CHECK_EVENT_COMPARISON(circle, site_type(3, 3), true, false);
+ CHECK_EVENT_COMPARISON(circle, site_type(3, 3), false, false);
   CHECK_EVENT_COMPARISON(circle, site_type(4, 2), true, false);
 }
 
@@ -514,3 +514,49 @@
   site1.inverse();
   CHECK_CIRCLE_FORMATION_PREDICATE(site1, site2, site3, 1.0, 30.0, 25.0);
 }
+
+BOOST_AUTO_TEST_CASE(circle_formation_predicate_test11) {
+ site_type site1(0, 0, 0, 10);
+ site1.sorted_index(2);
+ site1.inverse();
+ site_type site2(-8, 10);
+ site2.sorted_index(0);
+ site_type site3(-7, 14, -1, 14);
+ site3.sorted_index(1);
+ CHECK_CIRCLE_FORMATION_PREDICATE(site1, site2, site3, -4.0, 10.0, 0.0);
+}
+
+BOOST_AUTO_TEST_CASE(circle_formation_predicate_test12) {
+ site_type site1(0, 0, 0, 10);
+ site1.sorted_index(2);
+ site1.inverse();
+ site_type site2(-8, 10);
+ site2.sorted_index(0);
+ site_type site3(-7, 15, -1, 15);
+ site3.sorted_index(1);
+ CHECK_CIRCLE_EXISTENCE(site1, site2, site3, false);
+}
+
+BOOST_AUTO_TEST_CASE(circle_formation_predicate_test13) {
+ site_type site1(0, 0, 0, 10);
+ site1.sorted_index(2);
+ site1.inverse();
+ site_type site2(-7, -4, -1, -4);
+ site2.sorted_index(1);
+ site2.inverse();
+ site_type site3(-8, 0);
+ site3.sorted_index(0);
+ CHECK_CIRCLE_FORMATION_PREDICATE(site1, site2, site3, -4.0, 0.0, 0.0);
+}
+
+BOOST_AUTO_TEST_CASE(circle_formation_predicate_test14) {
+ site_type site1(0, 0, 0, 10);
+ site1.sorted_index(2);
+ site1.inverse();
+ site_type site2(-7, -5, -1, -5);
+ site2.sorted_index(1);
+ site2.inverse();
+ site_type site3(-8, 0);
+ site3.sorted_index(0);
+ CHECK_CIRCLE_EXISTENCE(site1, site2, site3, false);
+}


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