[Boost-commit] svn:boost r86222 - in trunk: boost/polygon/detail libs/polygon/test

Subject: [Boost-commit] svn:boost r86222 - in trunk: boost/polygon/detail libs/polygon/test
From: sydorchuk.andriy_at_[hidden]
Date: 2013-10-09 18:09:39

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

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

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

Modified: trunk/boost/polygon/detail/voronoi_predicates.hpp
==============================================================================
--- trunk/boost/polygon/detail/voronoi_predicates.hpp	Wed Oct  9 16:43:29 2013	(r86221)
+++ trunk/boost/polygon/detail/voronoi_predicates.hpp	2013-10-09 18:09:39 EDT (Wed, 09 Oct 2013)	(r86222)
@@ -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: trunk/libs/polygon/test/polygon_segment_test.cpp
==============================================================================
--- trunk/libs/polygon/test/polygon_segment_test.cpp	Wed Oct  9 16:43:29 2013	(r86221)
+++ trunk/libs/polygon/test/polygon_segment_test.cpp	2013-10-09 18:09:39 EDT (Wed, 09 Oct 2013)	(r86222)
@@ -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: trunk/libs/polygon/test/voronoi_predicates_test.cpp
==============================================================================
--- trunk/libs/polygon/test/voronoi_predicates_test.cpp	Wed Oct  9 16:43:29 2013	(r86221)
+++ trunk/libs/polygon/test/voronoi_predicates_test.cpp	2013-10-09 18:09:39 EDT (Wed, 09 Oct 2013)	(r86222)
@@ -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);
+}