[Boost-commit] svn:boost r74947 - in sandbox/gtl: boost/polygon boost/polygon/detail libs/polygon/test

Subject: [Boost-commit] svn:boost r74947 - in sandbox/gtl: boost/polygon boost/polygon/detail libs/polygon/test
From: sydorchuk.andriy_at_[hidden]
Date: 2011-10-14 18:35:15

Author: asydorchuk
Date: 2011-10-14 18:35:14 EDT (Fri, 14 Oct 2011)
New Revision: 74947
URL: http://svn.boost.org/trac/boost/changeset/74947

Log:
Migrated event_comparison tests.
Refactored event_comparison predicates.
Added:
   sandbox/gtl/libs/polygon/test/voronoi_calc_kernel_test.cpp   (contents, props changed)
Text files modified: 
   sandbox/gtl/boost/polygon/detail/voronoi_calc_kernel.hpp  |    81 ++++++++++++++++++++++++--------------- 
   sandbox/gtl/boost/polygon/voronoi_builder.hpp             |    14 ++----                                  
   sandbox/gtl/libs/polygon/test/Jamfile.v2                  |     1                                         
   sandbox/gtl/libs/polygon/test/voronoi_structures_test.cpp |     1                                         
   4 files changed, 55 insertions(+), 42 deletions(-)

Modified: sandbox/gtl/boost/polygon/detail/voronoi_calc_kernel.hpp
==============================================================================
--- sandbox/gtl/boost/polygon/detail/voronoi_calc_kernel.hpp	(original)
+++ sandbox/gtl/boost/polygon/detail/voronoi_calc_kernel.hpp	2011-10-14 18:35:14 EDT (Fri, 14 Oct 2011)
@@ -143,15 +143,25 @@
     static kOrientation get_orientation(const Point &point1,
                                         const Point &point2,
                                         const Point &point3) {
-        return get_orientation(robust_cross_product(point1.x() - point2.x(),
-                                                    point1.y() - point2.y(),
-                                                    point2.x() - point3.x(),
-                                                    point2.y() - point3.y()));
+        fpt_type dx1 = static_cast<fpt_type>(point1.x()) -
+                       static_cast<fpt_type>(point2.x());
+        fpt_type dx2 = static_cast<fpt_type>(point2.x()) -
+                       static_cast<fpt_type>(point3.x());
+        fpt_type dy1 = static_cast<fpt_type>(point1.y()) -
+                       static_cast<fpt_type>(point2.y());
+        fpt_type dy2 = static_cast<fpt_type>(point2.y()) -
+                       static_cast<fpt_type>(point3.y());
+        return get_orientation(robust_cross_product(dx1, dy1, dx2, dy2));
     }
 
-    template <typename Site>
-    struct site_comparison_predicate {
+    template <typename Site, typename Circle>
+    class event_comparison_predicate {
+    public:
         typedef Site site_type;
+        typedef Circle circle_type;
+
+        static const unsigned int ULPS = 64;
+        static const unsigned int ULPSx2 = (ULPS << 1);
 
         bool operator()(const site_type &lhs, const site_type &rhs) const {
             if (lhs.x0() != rhs.x0()) return lhs.x0() < rhs.x0();
@@ -169,27 +179,36 @@
                 return get_orientation(lhs.point1(), lhs.point0(), rhs.point1()) == LEFT;
             }
         }
-    };
-
-    template <typename Site>
-    struct site_equality_predicate {
-        typedef Site site_type;
 
-        bool operator()(const site_type &lhs, const site_type &rhs) const {
-            return lhs.point0() == rhs.point0() &&
-                   lhs.point1() == rhs.point1();
+        bool operator()(const site_type &lhs, const circle_type &rhs) const {
+            if (almost_equal(static_cast<fpt_type>(lhs.x()),
+                             static_cast<fpt_type>(rhs.lower_x()), ULPS)) {
+                if (almost_equal(static_cast<fpt_type>(lhs.y()),
+                                 static_cast<fpt_type>(rhs.lower_y()), ULPS)) return false;
+                return static_cast<fpt_type>(lhs.y()) <
+                       static_cast<fpt_type>(rhs.lower_y());
+            }
+            return static_cast<fpt_type>(lhs.x()) <
+                   static_cast<fpt_type>(rhs.lower_x());
+        }
+
+        bool operator()(const circle_type &lhs, const site_type &rhs) const {
+            if (almost_equal(static_cast<fpt_type>(lhs.lower_x()),
+                             static_cast<fpt_type>(rhs.x()), ULPS)) {
+                if (almost_equal(static_cast<fpt_type>(lhs.lower_y()),
+                                 static_cast<fpt_type>(rhs.y()), ULPS)) return false;
+                return static_cast<fpt_type>(lhs.lower_y()) <
+                       static_cast<fpt_type>(rhs.y());
+            }
+            return static_cast<fpt_type>(lhs.lower_x()) <
+                   static_cast<fpt_type>(rhs.x());    
         }
-    };
-
-    template <typename Circle>
-    struct circle_comparison_predicate {
-        typedef Circle circle_type;
-
-        static const unsigned int ULPS = 128;
 
         bool operator()(const circle_type &lhs, const circle_type &rhs) const {
-            if (almost_equal(lhs.lower_x(), rhs.lower_x(), ULPS)) {
-                if (almost_equal(lhs.lower_y(), rhs.lower_y(), ULPS)) {
+            if (almost_equal(static_cast<fpt_type>(lhs.lower_x()),
+                             static_cast<fpt_type>(rhs.lower_x()), ULPSx2)) {
+                if (almost_equal(static_cast<fpt_type>(lhs.lower_y()),
+                                 static_cast<fpt_type>(rhs.lower_y()), ULPSx2)) {
                     return false;
                 }
                 return lhs.lower_y() < rhs.lower_y();
@@ -199,19 +218,17 @@
     };
 
     template <typename Site, typename Circle>
-    struct event_comparison_predicate {
+    class event_equality_predicate {
+    public:
         typedef Site site_type;
         typedef Circle circle_type;
 
-        static const unsigned int ULPS = 64;
-
-        bool operator()(const site_type &lhs, const circle_type &rhs) const {
-            if (almost_equal(lhs.x(), rhs.lower_x(), ULPS)) {
-                if (almost_equal(lhs.y(), rhs.lower_y(), ULPS)) return false;
-                return lhs.y() < rhs.lower_y();
-            }
-            return lhs.x() < rhs.lower_x();
+        template <typename T1, typename T2>
+        bool operator()(const T1 &lhs, const T2 &rhs) {
+            return !comparison_predicate_(lhs, rhs) && !comparison_predicate_(rhs, lhs);
         }
+    private:
+        event_comparison_predicate<Site, Circle> comparison_predicate_;
     };
 
     template <typename Site>

Modified: sandbox/gtl/boost/polygon/voronoi_builder.hpp
==============================================================================
--- sandbox/gtl/boost/polygon/voronoi_builder.hpp	(original)
+++ sandbox/gtl/boost/polygon/voronoi_builder.hpp	2011-10-14 18:35:14 EDT (Fri, 14 Oct 2011)
@@ -179,17 +179,13 @@
 
         typedef detail::point_2d<coordinate_type> point_type;
         typedef detail::site_event<coordinate_type> site_event_type;
-        typedef calc_kernel_type::site_comparison_predicate<site_event_type>
-            site_comparison_predicate;
-        typedef calc_kernel_type::site_equality_predicate<site_event_type>
-            site_equality_predicate;
         typedef typename std::vector<site_event_type>::const_iterator
             site_event_iterator_type;
         typedef detail::circle_event<coordinate_type> circle_event_type;
-        typedef calc_kernel_type::circle_comparison_predicate<circle_event_type>
-            circle_comparison_predicate;
         typedef calc_kernel_type::event_comparison_predicate<site_event_type, circle_event_type>
             event_comparison_predicate;
+        typedef calc_kernel_type::event_equality_predicate<site_event_type, circle_event_type>
+            event_equality_predicate;
         typedef calc_kernel_type::circle_formation_predicate<site_event_type, circle_event_type>
             circle_formation_predicate_type;
         typedef typename output_type::voronoi_edge_type edge_type;
@@ -203,7 +199,7 @@
             bool operator()(const event_type &lhs, const event_type &rhs) const {
                 return predicate(rhs.first, lhs.first);
             }
-            circle_comparison_predicate predicate;
+            event_comparison_predicate predicate;
         } event_comparison_type;
         typedef detail::ordered_queue<event_type, event_comparison_type>
             circle_event_queue_type;
@@ -215,11 +211,11 @@
         // segment itself).
         void init_sites_queue() {
             // Sort the site events.
-            sort(site_events_.begin(), site_events_.end(), site_comparison_predicate());
+            sort(site_events_.begin(), site_events_.end(), event_comparison_predicate());
 
             // Remove duplicates.
             site_events_.erase(unique(
-                site_events_.begin(), site_events_.end(), site_equality_predicate()), site_events_.end());
+                site_events_.begin(), site_events_.end(), event_equality_predicate()), site_events_.end());
 
             // Number the sites.
             for (size_t cur = 0; cur < site_events_.size(); ++cur)

Modified: sandbox/gtl/libs/polygon/test/Jamfile.v2
==============================================================================
--- sandbox/gtl/libs/polygon/test/Jamfile.v2	(original)
+++ sandbox/gtl/libs/polygon/test/Jamfile.v2	2011-10-14 18:35:14 EDT (Fri, 14 Oct 2011)
@@ -29,6 +29,7 @@
 alias "voronoi-unit"
     :
         [ run voronoi_builder_test.cpp ]
+        [ run voronoi_calc_kernel_test.cpp ]
         [ run voronoi_clipping_test.cpp ]
         [ run voronoi_fpt_kernel_test.cpp ]
         [ run voronoi_structures_test.cpp ]

Added: sandbox/gtl/libs/polygon/test/voronoi_calc_kernel_test.cpp
==============================================================================
--- (empty file)
+++ sandbox/gtl/libs/polygon/test/voronoi_calc_kernel_test.cpp	2011-10-14 18:35:14 EDT (Fri, 14 Oct 2011)
@@ -0,0 +1,72 @@
+// Boost.Polygon library voronoi_calc_kernel_test.cpp file
+
+//          Copyright Andrii Sydorchuk 2010-2011.
+// 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_calc_kernel_test
+#include <boost/test/test_case_template.hpp>
+
+#include "boost/polygon/detail/voronoi_structures.hpp"
+#include "boost/polygon/detail/voronoi_calc_kernel.hpp"
+using namespace boost::polygon::detail;
+
+typedef voronoi_calc_kernel<int> VCK;
+typedef point_2d<int> point_type;
+typedef site_event<int> site_type;
+typedef circle_event<double> circle_type;
+VCK::event_comparison_predicate<site_type, circle_type> event_comparison;
+VCK::event_equality_predicate<site_type, circle_type> event_equality;
+
+#define CHECK_EVENT_COMPARISON(A, B, R1, R2) \
+    BOOST_CHECK_EQUAL(event_comparison(A, B), R1); \
+    BOOST_CHECK_EQUAL(event_comparison(B, A), R2); \
+    BOOST_CHECK_EQUAL(event_equality(A, B), !R1 && !R2)
+
+BOOST_AUTO_TEST_CASE(event_comparison_test1) {
+    site_type site(1, 2, 0);
+    CHECK_EVENT_COMPARISON(site, site_type(0, 2, 1), false, true);
+    CHECK_EVENT_COMPARISON(site, site_type(1, 3, 2), true, false);
+    CHECK_EVENT_COMPARISON(site, site_type(1, 2, 3), false, false);
+}
+
+BOOST_AUTO_TEST_CASE(event_comparison_test2) {
+    site_type site(0, 2, 0, 0, 0);
+    CHECK_EVENT_COMPARISON(site, site_type(0, 2, 1), true, false);
+    CHECK_EVENT_COMPARISON(site, site_type(0, 0, 2), false, true);
+    CHECK_EVENT_COMPARISON(site, site_type(0, -2, 0, -1, 3), false, true);
+    CHECK_EVENT_COMPARISON(site, site_type(0, -2, 1, 1, 4), true, false);
+    CHECK_EVENT_COMPARISON(site, site_type(0, 0, 1, 1, 5), true, false);
+}
+
+BOOST_AUTO_TEST_CASE(event_comparison_test3) {
+    site_type site(10, 10, 0, 0, 0);
+    CHECK_EVENT_COMPARISON(site, site_type(0, 0, 1), false, true);
+    CHECK_EVENT_COMPARISON(site, site_type(0, -1, 2), false, true);
+    CHECK_EVENT_COMPARISON(site, site_type(0, 1, 3), false, true);
+    CHECK_EVENT_COMPARISON(site, site_type(0, 1, 0, 10, 4), false, true);
+    CHECK_EVENT_COMPARISON(site, site_type(0, -10, 0, -1, 5), false, true);
+    CHECK_EVENT_COMPARISON(site, site_type(0, 0, 10, 9, 6), true, false);
+    CHECK_EVENT_COMPARISON(site, site_type(0, 0, 9, 10, 7), false, true);
+}
+
+BOOST_AUTO_TEST_CASE(event_comparison_test4) {
+    circle_type circle(1, 2, 3);
+    CHECK_EVENT_COMPARISON(circle, circle_type(1, 2, 3), false, false);
+    CHECK_EVENT_COMPARISON(circle, circle_type(1, 3, 3), true, false);
+    CHECK_EVENT_COMPARISON(circle, circle_type(1, 2, 4), true, false);
+    CHECK_EVENT_COMPARISON(circle, circle_type(0, 2, 2), false, true);
+    CHECK_EVENT_COMPARISON(circle, circle_type(-1, 2, 3), false, false);
+}
+
+BOOST_AUTO_TEST_CASE(event_comparison_test5) {
+    circle_type circle(1, 2, 3);
+    CHECK_EVENT_COMPARISON(circle, site_type(0, 100, 1), false, true);
+    CHECK_EVENT_COMPARISON(circle, site_type(3, 0, 2), false, true);
+    CHECK_EVENT_COMPARISON(circle, site_type(3, 2, 3), false, false);
+    CHECK_EVENT_COMPARISON(circle, site_type(3, 3, 4), true, false);
+    CHECK_EVENT_COMPARISON(circle, site_type(4, 2, 5), true, false);
+}

Modified: sandbox/gtl/libs/polygon/test/voronoi_structures_test.cpp
==============================================================================
--- sandbox/gtl/libs/polygon/test/voronoi_structures_test.cpp	(original)
+++ sandbox/gtl/libs/polygon/test/voronoi_structures_test.cpp	2011-10-14 18:35:14 EDT (Fri, 14 Oct 2011)
@@ -112,5 +112,4 @@
     node_data.edge(&data);
     BOOST_CHECK_EQUAL(node_data.edge() == &data, true);
     BOOST_CHECK_EQUAL(node_data.circle_event() == &data, true);
-    BOOST_CHECK_EQUAL(&data != NULL, true);
 }