[Boost-commit] svn:boost r84237 - trunk/boost/geometry/index/detail/algorithms

Subject: [Boost-commit] svn:boost r84237 - trunk/boost/geometry/index/detail/algorithms
From: adam.wulkiewicz_at_[hidden]
Date: 2013-05-11 18:37:04

Author: awulkiew
Date: 2013-05-11 18:37:03 EDT (Sat, 11 May 2013)
New Revision: 84237
URL: http://svn.boost.org/trac/boost/changeset/84237

Log:
geometry.index: path_intersection optimized for 2-point linestrings.
Text files modified: 
   trunk/boost/geometry/index/detail/algorithms/path_intersection.hpp    |    46 +++++++++++++++------------             
   trunk/boost/geometry/index/detail/algorithms/segment_intersection.hpp |    66 ++++++++++++++++++++------------------- 
   2 files changed, 60 insertions(+), 52 deletions(-)

Modified: trunk/boost/geometry/index/detail/algorithms/path_intersection.hpp
==============================================================================
--- trunk/boost/geometry/index/detail/algorithms/path_intersection.hpp	(original)
+++ trunk/boost/geometry/index/detail/algorithms/path_intersection.hpp	2013-05-11 18:37:03 EDT (Sat, 11 May 2013)
@@ -34,34 +34,40 @@
 {
     typedef typename default_length_result<Linestring>::type length_type;
 
-    static inline bool apply(Indexable const& b, Linestring const& path, length_type & distance)
+    static inline bool apply(Indexable const& b, Linestring const& path, length_type & comparable_distance)
     {
         typedef typename ::boost::range_value<Linestring>::type point_type;
-        typedef typename default_relative_distance_type<Indexable, point_type>::type relative_distance_type;
         typedef typename ::boost::range_const_iterator<Linestring>::type const_iterator;        
+        typedef typename ::boost::range_size<Linestring>::type size_type;
+        
+        const size_type count = ::boost::size(path);
 
-        if ( ::boost::size(path) < 2 )
-            return false;
-
-        const_iterator it0 = ::boost::begin(path);
-        const_iterator it1 = ::boost::begin(path) + 1;
-        const_iterator last = ::boost::end(path);
-
-        distance = 0;
-
-        for ( ; it1 != last ; ++it0, ++it1 )
+        if ( count == 2 )
         {
-            typename default_distance_result<point_type, point_type>::type
-                dist = geometry::distance(*it0, *it1);
+            return index::detail::segment_intersection(b, *::boost::begin(path), *(::boost::begin(path)+1), comparable_distance);
+        }
+        else if ( 2 < count )
+        {
+            const_iterator it0 = ::boost::begin(path);
+            const_iterator it1 = ::boost::begin(path) + 1;
+            const_iterator last = ::boost::end(path);
+
+            comparable_distance = 0;
 
-            relative_distance_type rel_dist;
-            if ( index::detail::segment_intersection(b, *it0, *it1, rel_dist) )
+            for ( ; it1 != last ; ++it0, ++it1 )
             {
-                distance += dist * rel_dist;
-                return true;
+                typename default_distance_result<point_type, point_type>::type
+                    dist = geometry::distance(*it0, *it1);
+
+                length_type rel_dist;
+                if ( index::detail::segment_intersection(b, *it0, *it1, rel_dist) )
+                {
+                    comparable_distance += dist * rel_dist;
+                    return true;
+                }
+                else
+                    comparable_distance += dist;
             }
-            else
-                distance += dist;
         }
 
         return false;

Modified: trunk/boost/geometry/index/detail/algorithms/segment_intersection.hpp
==============================================================================
--- trunk/boost/geometry/index/detail/algorithms/segment_intersection.hpp	(original)
+++ trunk/boost/geometry/index/detail/algorithms/segment_intersection.hpp	2013-05-11 18:37:03 EDT (Sat, 11 May 2013)
@@ -15,21 +15,21 @@
 
 namespace boost { namespace geometry { namespace index { namespace detail {
 
-template <typename Indexable, typename Point>
-struct default_relative_distance_type
-{
-    typedef typename select_most_precise<
-        typename select_most_precise<
-            typename traits::coordinate_type<Indexable>::type,
-            typename traits::coordinate_type<Point>::type
-        >::type,
-        float // TODO - use bigger type, calculated from the size of coordinate types
-    >::type type;
-
-
-    BOOST_MPL_ASSERT_MSG((!::boost::is_unsigned<type>::value),
-        THIS_TYPE_SHOULDNT_BE_UNSIGNED, (type));
-};
+//template <typename Indexable, typename Point>
+//struct default_relative_distance_type
+//{
+//    typedef typename select_most_precise<
+//        typename select_most_precise<
+//        typename traits::coordinate_type<Indexable>::type,
+//        typename traits::coordinate_type<Point>::type
+//        >::type,
+//        float // TODO - use bigger type, calculated from the size of coordinate types
+//    >::type type;
+//
+//
+//    BOOST_MPL_ASSERT_MSG((!::boost::is_unsigned<type>::value),
+//        THIS_TYPE_SHOULDNT_BE_UNSIGNED, (type));
+//};
 
 namespace dispatch {
 
@@ -40,16 +40,15 @@
     BOOST_STATIC_ASSERT(I < traits::dimension<Point>::value);
     BOOST_STATIC_ASSERT(traits::dimension<Point>::value == traits::dimension<Box>::value);
 
-    typedef typename default_relative_distance_type<Box, Point>::type relative_distance_type;
-
-    // WARNING! - relative_distance_type must be IEEE float for this to work
+    // WARNING! - RelativeDistance must be IEEE float for this to work
 
+    template <typename RelativeDistance>
     static inline bool apply(Box const& b, Point const& p0, Point const& p1,
-                             relative_distance_type & t_near, relative_distance_type & t_far)
+                             RelativeDistance & t_near, RelativeDistance & t_far)
     {
-        relative_distance_type ray_d = geometry::get<I>(p1) - geometry::get<I>(p0);
-        relative_distance_type tn = ( detail::get<min_corner, I>(b) - geometry::get<I>(p0) ) / ray_d;
-        relative_distance_type tf = ( detail::get<max_corner, I>(b) - geometry::get<I>(p0) ) / ray_d;
+        RelativeDistance ray_d = geometry::get<I>(p1) - geometry::get<I>(p0);
+        RelativeDistance tn = ( detail::get<min_corner, I>(b) - geometry::get<I>(p0) ) / ray_d;
+        RelativeDistance tf = ( detail::get<max_corner, I>(b) - geometry::get<I>(p0) ) / ray_d;
         if ( tf < tn )
             ::std::swap(tn, tf);
 
@@ -68,10 +67,10 @@
     BOOST_STATIC_ASSERT(0 < CurrentDimension);
 
     typedef box_segment_intersection_dim<Box, Point, CurrentDimension - 1> for_dim;
-    typedef typename for_dim::relative_distance_type relative_distance_type;
 
+    template <typename RelativeDistance>
     static inline bool apply(Box const& b, Point const& p0, Point const& p1,
-                             relative_distance_type & t_near, relative_distance_type & t_far)
+                             RelativeDistance & t_near, RelativeDistance & t_far)
     {
         return box_segment_intersection<Box, Point, CurrentDimension - 1>::apply(b, p0, p1, t_near, t_far)
             && for_dim::apply(b, p0, p1, t_near, t_far);
@@ -82,10 +81,10 @@
 struct box_segment_intersection<Box, Point, 1>
 {
     typedef box_segment_intersection_dim<Box, Point, 0> for_dim;
-    typedef typename for_dim::relative_distance_type relative_distance_type;
 
+    template <typename RelativeDistance>
     static inline bool apply(Box const& b, Point const& p0, Point const& p1,
-                             relative_distance_type & t_near, relative_distance_type & t_far)
+                             RelativeDistance & t_near, RelativeDistance & t_far)
     {
         return for_dim::apply(b, p0, p1, t_near, t_far);
     }
@@ -107,12 +106,15 @@
 struct segment_intersection<Indexable, Point, box_tag>
 {
     typedef dispatch::box_segment_intersection<Indexable, Point, detail::traits::dimension<Indexable>::value> impl;
-    typedef typename impl::relative_distance_type relative_distance_type;
 
-    static inline bool apply(Indexable const& b, Point const& p0, Point const& p1, relative_distance_type & relative_distance)
+    template <typename RelativeDistance>
+    static inline bool apply(Indexable const& b, Point const& p0, Point const& p1, RelativeDistance & relative_distance)
     {
-        relative_distance_type t_near = -(::std::numeric_limits<relative_distance_type>::max)();
-        relative_distance_type t_far = (::std::numeric_limits<relative_distance_type>::max)();
+        static const bool check = !::boost::is_integral<RelativeDistance>::value;
+        BOOST_MPL_ASSERT_MSG(check, RELATIVE_DISTANCE_MUST_BE_FLOATING_POINT_TYPE, (RelativeDistance));
+
+        RelativeDistance t_near = -(::std::numeric_limits<RelativeDistance>::max)();
+        RelativeDistance t_far = (::std::numeric_limits<RelativeDistance>::max)();
 
         return impl::apply(b, p0, p1, t_near, t_far) &&
                (t_near <= 1) &&
@@ -122,11 +124,11 @@
 
 } // namespace dispatch
 
-template <typename Indexable, typename Point> inline
+template <typename Indexable, typename Point, typename RelativeDistance> inline
 bool segment_intersection(Indexable const& b,
                           Point const& p0,
                           Point const& p1,
-                          typename default_relative_distance_type<Indexable, Point>::type & relative_distance)
+                          RelativeDistance & relative_distance)
 {
     // TODO check Indexable and Point concepts