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

Subject: [Boost-commit] svn:boost r74949 - in sandbox/gtl: boost/polygon/detail libs/polygon/test
From: sydorchuk.andriy_at_[hidden]
Date: 2011-10-15 07:47:07

Author: asydorchuk
Date: 2011-10-15 07:47:06 EDT (Sat, 15 Oct 2011)
New Revision: 74949
URL: http://svn.boost.org/trac/boost/changeset/74949

Log:
Migrated node_comparison tests.
Text files modified: 
   sandbox/gtl/boost/polygon/detail/voronoi_calc_kernel.hpp   |    85 ++++++++++++++++-----------             
   sandbox/gtl/libs/polygon/test/voronoi_calc_kernel_test.cpp |   125 ++++++++++++++++++++++++++++++++++++++++
   2 files changed, 175 insertions(+), 35 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-15 07:47:06 EDT (Sat, 15 Oct 2011)
@@ -234,9 +234,29 @@
     template <typename Site>
     class distance_predicate {
     public:
-        typedef typename Site::point_type point_type;
         typedef Site site_type;
         
+        bool operator()(const site_type& left_site,
+                        const site_type& right_site,
+                        const site_type& new_site) const {
+            if (!left_site.is_segment()) {
+                if (!right_site.is_segment()) {
+                    return pp(left_site, right_site, new_site);
+                } else {
+                    return ps(left_site, right_site, new_site, false);
+                }
+            } else {
+                if (!right_site.is_segment()) {
+                    return ps(right_site, left_site, new_site, true);
+                } else {
+                    return ss(left_site, right_site, new_site);
+                }
+            }
+        }
+
+    private:
+        typedef typename Site::point_type point_type;
+
         // Robust predicate, avoids using high-precision libraries.
         // Returns true if a horizontal line going through the new point site
         // intersects right arc at first, else returns false. If horizontal line
@@ -264,7 +284,10 @@
             } else {
                 // If x-coordinates of the sites are equal, we may produce the
                 // result without any further computations.
-                return left_point.y() + right_point.y() < 2.0 * new_point.y();
+                return static_cast<fpt_type>(left_point.y()) +
+                       static_cast<fpt_type>(right_point.y()) <
+                       static_cast<fpt_type>(2) *
+                       static_cast<fpt_type>(new_point.y());
             }
 
             fpt_type dist1 = find_distance_to_point_arc(left_site, new_point);
@@ -318,7 +341,6 @@
             return dist1 < dist2;
         }
 
-    private:
         // Find the x-coordinate (relative to the sweepline position) of the point
         // of the intersection of the horizontal line going through the new site
         // with the arc corresponding to the point site.
@@ -327,7 +349,7 @@
                                             const point_type &point) const {
             fpt_type dx = site.x() - point.x();
             fpt_type dy = site.y() - point.y();
-            return (dx * dx + dy * dy) / (2.0 * dx);
+            return (dx * dx + dy * dy) / (static_cast<fpt_type>(2.0) * dx);
         }
 
         // Find the x-coordinate (relative to the sweepline position) of the point
@@ -342,14 +364,21 @@
             } else {
                 const point_type &segment0 = site.point0(true);
                 const point_type &segment1 = site.point1(true);
-                fpt_type a1 = segment1.x() - segment0.x();
-                fpt_type b1 = segment1.y() - segment0.y();
-                fpt_type a3 = point.x() - segment0.x();
-                fpt_type b3 = point.y() - segment0.y();
+                fpt_type a1 = static_cast<fpt_type>(segment1.x()) -
+                              static_cast<fpt_type>(segment0.x());
+                fpt_type b1 = static_cast<fpt_type>(segment1.y()) -
+                              static_cast<fpt_type>(segment0.y());
+                fpt_type a3 = static_cast<fpt_type>(point.x()) -
+                              static_cast<fpt_type>(segment0.x());
+                fpt_type b3 = static_cast<fpt_type>(point.y()) -
+                              static_cast<fpt_type>(segment0.y());
                 fpt_type k = std::sqrt(a1 * a1 + b1 * b1);
                 // Avoid substraction while computing k.
-                if (b1 >= 0.0) k = 1.0 / (b1 + k);
-                else k = (k - b1) / (a1 * a1);
+                if (b1 >= static_cast<fpt_type>(0)) {
+                    k = static_cast<fpt_type>(1) / (b1 + k);
+                } else {
+                    k = (k - b1) / (a1 * a1);
+                }
                 // Relative error of the robust cross product is 2EPS.
                 // Relative error of the k is atmost 5EPS.
                 // The resulting relative error is atmost 8EPS.
@@ -367,10 +396,14 @@
                 return (!right_site.is_inverse()) ? LESS : MORE;
             }
 
-            fpt_type dif_x = new_point.x() - site_point.x();
-            fpt_type dif_y = new_point.y() - site_point.y();
-            fpt_type a = segment_end.x() - segment_start.x();
-            fpt_type b = segment_end.y() - segment_start.y();
+            fpt_type dif_x = static_cast<fpt_type>(new_point.x()) -
+                             static_cast<fpt_type>(site_point.x());
+            fpt_type dif_y = static_cast<fpt_type>(new_point.y()) -
+                             static_cast<fpt_type>(site_point.y());
+            fpt_type a = static_cast<fpt_type>(segment_end.x()) -
+                         static_cast<fpt_type>(segment_start.x());
+            fpt_type b = static_cast<fpt_type>(segment_end.y()) -
+                         static_cast<fpt_type>(segment_start.y());
 
             if (right_site.is_vertical()) {
                 if (new_point.y() < site_point.y() && !reverse_order)
@@ -388,7 +421,7 @@
             }
 
             fpt_type fast_left_expr = a * (dif_y + dif_x) * (dif_y - dif_x);
-            fpt_type fast_right_expr = (2.0 * b) * dif_x * dif_y;
+            fpt_type fast_right_expr = (static_cast<fpt_type>(2) * b) * dif_x * dif_y;
             if (!(almost_equal(fast_left_expr, fast_right_expr, 4))) {
                 if ((fast_left_expr > fast_right_expr) ^ reverse_order)
                     return reverse_order ? LESS : MORE;
@@ -420,10 +453,10 @@
 
             if (site1.x() < site2.x()) {
                 // The second node contains a new site.
-                return less(node1.left_site(), node1.right_site(), site2);
+                return predicate_(node1.left_site(), node1.right_site(), site2);
             } else if (site1.x() > site2.x()) {
                 // The first node contains a new site.
-                return !less(node2.left_site(), node2.right_site(), site1);
+                return !predicate_(node2.left_site(), node2.right_site(), site1);
             } else {
                 // This checks were evaluated experimentally.
                 if (site1.index() == site2.index()) {
@@ -469,24 +502,6 @@
             return std::make_pair(node.right_site().y(), -1);
         }
 
-        bool less(const site_type& left_site,
-                  const site_type& right_site,
-                  const site_type& new_site) const {
-            if (!left_site.is_segment()) {
-                if (!right_site.is_segment()) {
-                    return predicate_.pp(left_site, right_site, new_site);
-                } else {
-                    return predicate_.ps(left_site, right_site, new_site, false);
-                }
-            } else {
-                if (!right_site.is_segment()) {
-                    return predicate_.ps(right_site, left_site, new_site, true);
-                } else {
-                    return predicate_.ss(left_site, right_site, new_site);
-                }
-            }
-        }
-
     private:
         distance_predicate_type predicate_;
     };

Modified: sandbox/gtl/libs/polygon/test/voronoi_calc_kernel_test.cpp
==============================================================================
--- sandbox/gtl/libs/polygon/test/voronoi_calc_kernel_test.cpp	(original)
+++ sandbox/gtl/libs/polygon/test/voronoi_calc_kernel_test.cpp	2011-10-15 07:47:06 EDT (Sat, 15 Oct 2011)
@@ -7,6 +7,8 @@
 
 // See http://www.boost.org for updates, documentation, and revision history.
 
+#include <map>
+
 #define BOOST_TEST_MODULE voronoi_calc_kernel_test
 #include <boost/test/test_case_template.hpp>
 
@@ -21,11 +23,23 @@
 VCK::event_comparison_predicate<site_type, circle_type> event_comparison;
 VCK::event_equality_predicate<site_type, circle_type> event_equality;
 
+typedef beach_line_node_key<site_type> key_type;
+typedef VCK::node_comparison_predicate<key_type> node_comparison_type;
+typedef std::map<key_type, int, node_comparison_type> beach_line_type;
+typedef beach_line_type::iterator bieach_line_iterator;
+node_comparison_type node_comparison;
+
 #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)
 
+#define CHECK_NODE_COMPARISON(node, nodes, res, sz) \
+    for (int i = 0; i < sz; ++i) { \
+        BOOST_CHECK_EQUAL(node_comparison(node, nodes[i]), res[i]); \
+        BOOST_CHECK_EQUAL(node_comparison(nodes[i], node), !res[i]); \
+    }
+
 BOOST_AUTO_TEST_CASE(event_comparison_test1) {
     site_type site(1, 2, 0);
     CHECK_EVENT_COMPARISON(site, site_type(0, 2, 1), false, true);
@@ -70,3 +84,114 @@
     CHECK_EVENT_COMPARISON(circle, site_type(3, 3, 4), true, false);
     CHECK_EVENT_COMPARISON(circle, site_type(4, 2, 5), true, false);
 }
+
+BOOST_AUTO_TEST_CASE(node_comparison_test1) {
+    beach_line_type beach_line;
+    site_type site1(0, 0, 0);
+    site_type site2(0, 2, 1);
+    site_type site3(1, 0, 2);
+    beach_line[key_type(site1, site2)] = 2;
+    beach_line[key_type(site1, site3)] = 0;
+    beach_line[key_type(site3, site1)] = 1;
+    int cur_index = 0;
+    for (bieach_line_iterator it = beach_line.begin();
+         it != beach_line.end(); ++it, ++cur_index) {
+        BOOST_CHECK_EQUAL(it->second, cur_index);
+    }
+}
+
+BOOST_AUTO_TEST_CASE(node_comparison_test2) {
+    beach_line_type beach_line;
+    site_type site1(0, 1, 0);
+    site_type site2(2, 0, 1);
+    site_type site3(2, 4, 2);
+    beach_line[key_type(site1, site2)] = 0;
+    beach_line[key_type(site2, site1)] = 1;
+    beach_line[key_type(site1, site3)] = 2;
+    beach_line[key_type(site3, site1)] = 3;
+    int cur_index = 0;
+    for (bieach_line_iterator it = beach_line.begin();
+         it != beach_line.end(); ++it, ++cur_index) {
+        BOOST_CHECK_EQUAL(it->second, cur_index);
+    }
+}
+
+BOOST_AUTO_TEST_CASE(node_comparison_test3) {
+    key_type node(site_type(1, 0, 0), site_type(0, 2, 1));
+    key_type nodes[] = {
+        key_type(site_type(2, -10, 2)),
+        key_type(site_type(2, -1, 3)),
+        key_type(site_type(2, 0, 4)),
+        key_type(site_type(2, 1, 4)),
+        key_type(site_type(2, 2, 4)),
+        key_type(site_type(2, 3, 4)),
+    };
+    bool res[] = {false, false, false, false, true, true};
+    CHECK_NODE_COMPARISON(node, nodes, res, 6);
+}
+
+BOOST_AUTO_TEST_CASE(node_comparison_test4) {
+    key_type node(site_type(0, 1, 0), site_type(1, 0, 1));
+    key_type nodes[] = {
+        key_type(site_type(2, -3, 2)),
+        key_type(site_type(2, -2, 2)),
+        key_type(site_type(2, -1, 2)),
+        key_type(site_type(2, 0, 2)),
+        key_type(site_type(2, 1, 2)),
+        key_type(site_type(2, 3, 2)),
+    };
+    bool res[] = {false, true, true, true, true, true};
+    CHECK_NODE_COMPARISON(node, nodes, res, 6);
+}
+
+BOOST_AUTO_TEST_CASE(node_comparison_test5) {
+    key_type node(site_type(0, 0, 0), site_type(1, 2, 1));
+    key_type nodes[] = {
+        key_type(site_type(2, -10, 2)),
+        key_type(site_type(2, 0, 2)),
+        key_type(site_type(2, 1, 2)),
+        key_type(site_type(2, 2, 2)),
+        key_type(site_type(2, 5, 2)),
+        key_type(site_type(2, 20, 2)),
+    };
+    bool res[] = {false, false, true, true, true, true};
+    CHECK_NODE_COMPARISON(node, nodes, res, 6);
+}
+
+BOOST_AUTO_TEST_CASE(node_comparison_test6) {
+    key_type node(site_type(1, 1, 0), site_type(0, 0, 1));
+    key_type nodes [] = {
+        key_type(site_type(2, -3, 2)),
+        key_type(site_type(2, -2, 2)),
+        key_type(site_type(2, 0, 2)),
+        key_type(site_type(2, 1, 2)),
+        key_type(site_type(2, 2, 2)),
+        key_type(site_type(2, 3, 2)),
+        key_type(site_type(2, 5, 2)),
+    };
+    bool res[] = {false, false, false, false, false, false, true};
+    CHECK_NODE_COMPARISON(node, nodes, res, 7);
+}
+
+BOOST_AUTO_TEST_CASE(node_comparison_test7) {
+    key_type node(site_type(0, 0, 0), site_type(0, 2, 1));
+    key_type nodes[] = {
+        key_type(site_type(1, 0, 2)),
+        key_type(site_type(1, 1, 2)),
+        key_type(site_type(1, 2, 2)),
+    };
+    bool res[] = {false, false, true};
+    CHECK_NODE_COMPARISON(node, nodes, res, 3);
+}
+
+BOOST_AUTO_TEST_CASE(node_comparison_test8) {
+    key_type node(site_type(0, 0, 0), site_type(1, 1, 1));
+    key_type nodes[] = {
+        key_type(site_type(1, 0, 2)),
+        key_type(site_type(1, 1, 2)),
+        key_type(site_type(1, 2, 2)),
+        key_type(site_type(1, 1, 1), site_type(0, 0, 0)),
+    };
+    bool res[] = {false, true, true, true};
+    CHECK_NODE_COMPARISON(node, nodes, res, 4);
+}