[Boost-commit] svn:boost r72029 - in trunk/boost/geometry: algorithms algorithms/detail algorithms/detail/equals util

Subject: [Boost-commit] svn:boost r72029 - in trunk/boost/geometry: algorithms algorithms/detail algorithms/detail/equals util
From: barend.gehrels_at_[hidden]
Date: 2011-05-18 14:06:36

Author: barendgehrels
Date: 2011-05-18 14:06:34 EDT (Wed, 18 May 2011)
New Revision: 72029
URL: http://svn.boost.org/trac/boost/changeset/72029

Log:
Fixed geometry::equals for high precision
Text files modified: 
   trunk/boost/geometry/algorithms/detail/equals/collect_vectors.hpp |    29 +++++++++++++++++++----------           
   trunk/boost/geometry/algorithms/detail/partition.hpp              |     2 +-                                      
   trunk/boost/geometry/algorithms/equals.hpp                        |     5 +----                                   
   trunk/boost/geometry/util/math.hpp                                |    35 +++++++++++++++++++++++++++++------     
   4 files changed, 50 insertions(+), 21 deletions(-)

Modified: trunk/boost/geometry/algorithms/detail/equals/collect_vectors.hpp
==============================================================================
--- trunk/boost/geometry/algorithms/detail/equals/collect_vectors.hpp	(original)
+++ trunk/boost/geometry/algorithms/detail/equals/collect_vectors.hpp	2011-05-18 14:06:34 EDT (Wed, 18 May 2011)
@@ -14,8 +14,6 @@
 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_EQUALS_COLLECT_VECTORS_HPP
 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_EQUALS_COLLECT_VECTORS_HPP
 
-#include <algorithm>
-#include <deque>
 
 #include <boost/numeric/conversion/cast.hpp>
 #include <boost/range.hpp>
@@ -26,9 +24,8 @@
 #include <boost/geometry/core/cs.hpp>
 #include <boost/geometry/core/interior_rings.hpp>
 #include <boost/geometry/geometries/concepts/check.hpp>
-#include <boost/geometry/strategies/side.hpp>
 
-#include <boost/geometry/util/select_most_precise.hpp>
+#include <boost/geometry/util/math.hpp>
 
 
 
@@ -41,10 +38,10 @@
 {
     typedef T type;
 
-    collected_vector()
+    inline collected_vector()
     {}
 
-    collected_vector(T const& px, T const& py,
+    inline collected_vector(T const& px, T const& py,
             T const& pdx, T const& pdy)
         : x(px)
         , y(py)
@@ -58,7 +55,8 @@
     T dx, dy;
     T dx_0, dy_0;
 
-    bool operator<(collected_vector<T> const& other) const
+    // For sorting
+    inline bool operator<(collected_vector<T> const& other) const
     {
         if (math::equals(x, other.x))
         {
@@ -77,10 +75,15 @@
 
     inline bool same_direction(collected_vector<T> const& other) const
     {
-        return math::equals(dx, other.dx)
-            && math::equals(dy, other.dy);
+        // For high precision arithmetic, we have to be 
+        // more relaxed then using ==
+        // Because 2/sqrt( (0,0)<->(2,2) ) == 1/sqrt( (0,0)<->(1,1) ) 
+        // is not always true (at least, it is not for ttmath)
+        return math::equals_with_epsilon(dx, other.dx)
+            && math::equals_with_epsilon(dy, other.dy);
     }
 
+    // For std::equals
     inline bool operator==(collected_vector<T> const& other) const
     {
         return math::equals(x, other.x)
@@ -145,7 +148,13 @@
                 first = false;
             }
         }
-        // TODO: if first one has same direction as last one, remove first one...
+
+        // If first one has same direction as last one, remove first one
+        if (boost::size(collection) > 1 
+            && collection.front().same_direction(collection.back()))
+        {
+            collection.erase(collection.begin());
+        }
     }
 };
 

Modified: trunk/boost/geometry/algorithms/detail/partition.hpp
==============================================================================
--- trunk/boost/geometry/algorithms/detail/partition.hpp	(original)
+++ trunk/boost/geometry/algorithms/detail/partition.hpp	2011-05-18 14:06:34 EDT (Wed, 18 May 2011)
@@ -79,7 +79,7 @@
 }
 
 
-// Match collection 1 with collection 2
+// Match collection with itself
 template <typename InputCollection, typename Policy>
 static inline void handle_one(InputCollection const& collection,
         index_vector_type const& input,

Modified: trunk/boost/geometry/algorithms/equals.hpp
==============================================================================
--- trunk/boost/geometry/algorithms/equals.hpp	(original)
+++ trunk/boost/geometry/algorithms/equals.hpp	2011-05-18 14:06:34 EDT (Wed, 18 May 2011)
@@ -15,9 +15,7 @@
 #define BOOST_GEOMETRY_ALGORITHMS_EQUALS_HPP
 
 
-
 #include <cstddef>
-#include <deque>
 #include <vector>
 
 #include <boost/mpl/if.hpp>
@@ -139,8 +137,7 @@
         std::sort(c2.begin(), c2.end());
 
         // Just check if these vectors are equal.
-        return c1.size() == c2.size()
-            && std::equal(c1.begin(), c1.end(), c2.begin());
+        return std::equal(c1.begin(), c1.end(), c2.begin());
     }
 };
 

Modified: trunk/boost/geometry/util/math.hpp
==============================================================================
--- trunk/boost/geometry/util/math.hpp	(original)
+++ trunk/boost/geometry/util/math.hpp	2011-05-18 14:06:34 EDT (Wed, 18 May 2011)
@@ -32,27 +32,38 @@
 {
 
 
-template <typename T, bool Floating>
+template <typename Type, bool, typename TypeForEpsilon = Type>
 struct equals
 {
-    static inline bool apply(T const& a, T const& b)
+    static inline bool apply(Type const& a, Type const& b)
     {
         return a == b;
     }
 };
 
-template <typename T>
-struct equals<T, true>
+template <typename Type, typename TypeForEpsilon>
+struct equals<Type, true, TypeForEpsilon>
 {
-    static inline bool apply(T const& a, T const& b)
+    static inline bool apply(Type const& a, Type const& b)
     {
         // See http://www.parashift.com/c++-faq-lite/newbie.html#faq-29.17,
         // FUTURE: replace by some boost tool or boost::test::close_at_tolerance
-        return std::abs(a - b) <= std::numeric_limits<T>::epsilon() * std::abs(a);
+        Type const epsilon = std::numeric_limits<TypeForEpsilon>::epsilon();
+        return abs(a - b) <= epsilon * abs(a);
     }
 };
 
 
+template <typename Type, bool> 
+struct equals_with_epsilon {};
+
+template <typename Type>
+struct equals_with_epsilon<Type, false> : public equals<Type, true, double> {};
+
+template <typename Type>
+struct equals_with_epsilon<Type, true> : public equals<Type, true> {};
+
+
 /*!
 \brief Short construct to enable partial specialization for PI, currently not possible in Math.
 */
@@ -101,6 +112,18 @@
         >::apply(a, b);
 }
 
+template <typename T1, typename T2>
+inline bool equals_with_epsilon(T1 const& a, T2 const& b)
+{
+    typedef typename select_most_precise<T1, T2>::type select_type;
+    return detail::equals_with_epsilon
+        <
+            select_type, 
+            boost::is_floating_point<select_type>::type::value
+        >::apply(a, b);
+}
+
+
 
 double const d2r = geometry::math::pi<double>() / 180.0;
 double const r2d = 1.0 / d2r;