[Boost-commit] svn:boost r74497 - in sandbox-branches/geometry/index/boost/geometry/extensions/index: . rtree/visitors

Subject: [Boost-commit] svn:boost r74497 - in sandbox-branches/geometry/index/boost/geometry/extensions/index: . rtree/visitors
From: adam.wulkiewicz_at_[hidden]
Date: 2011-09-21 14:50:16

Author: awulkiew
Date: 2011-09-21 14:50:15 EDT (Wed, 21 Sep 2011)
New Revision: 74497
URL: http://svn.boost.org/trac/boost/changeset/74497

Log:
distance calculators that will be used in knn implemented, some names changed to more general in knn results wrappers.
Added:
   sandbox-branches/geometry/index/boost/geometry/extensions/index/distance_calc.hpp   (contents, props changed)
Text files modified: 
   sandbox-branches/geometry/index/boost/geometry/extensions/index/predicates.hpp             |     6 +++++-                                  
   sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/nearest.hpp |    39 +++++++++++++++++++-------------------- 
   2 files changed, 24 insertions(+), 21 deletions(-)

Added: sandbox-branches/geometry/index/boost/geometry/extensions/index/distance_calc.hpp
==============================================================================
--- (empty file)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/distance_calc.hpp	2011-09-21 14:50:15 EDT (Wed, 21 Sep 2011)
@@ -0,0 +1,188 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+//
+// Boost.SpatialIndex - Spatial index distances calculators used in nearest query
+//
+// Copyright 2011 Adam Wulkiewicz.
+// Use, modification and distribution is subject to 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)
+
+#ifndef BOOST_GEOMETRY_EXTENSIONS_INDEX_DISTANCE_CALC_HPP
+#define BOOST_GEOMETRY_EXTENSIONS_INDEX_DISTANCE_CALC_HPP
+
+namespace boost { namespace geometry { namespace index {
+
+namespace detail {
+
+//TODO: awulkiew - consider storing values instead of const references
+// it may be faster and it eliminates problems with storing of references to temporaries
+
+struct distance_near_tag {};
+struct distance_far_tag {};
+struct distance_centroid_tag {};
+
+template <typename Point, typename Tag>
+struct distance_xxx
+    : nonassignable
+{
+    typedef typename index::traits::coordinate_type<Point>::type coordinate_type;
+    typedef typename geometry::default_distance_result<Point, Point>::type distance_type;
+
+    inline explicit distance_xxx(
+        Point const& p,
+        coordinate_type const& distance_near = coordinate_type(0),
+        coordinate_type const& distance_far = std::numeric_limits<coordinate_type>::max()
+    )
+        : point(p)
+        , comparable_near(distance_near * distance_near)
+        , comparable_far(distance_far * distance_far)
+    {}
+
+    Point const& point;
+    distance_type comparable_near;
+    distance_type comparable_far;
+};
+
+} // namespace detail
+
+template <typename Point>
+inline detail::distance_xxx<Point, detail::distance_near_tag>
+distance(
+    Point const& p,
+    typename index::traits::coordinate_type<Point>::type const& near
+        = typename index::traits::coordinate_type<Point>::type(0),
+    typename index::traits::coordinate_type<Point>::type const& far
+        = std::numeric_limits<typename index::traits::coordinate_type<Point>::type>::max()
+)
+{
+    return detail::detail::distance_xxx<Point, detail::distance_near_tag>(p, near, far);
+}
+
+template <typename Point>
+inline detail::distance_xxx<Point, detail::distance_near_tag>
+distance_near(
+    Point const& p,
+    typename index::traits::coordinate_type<Point>::type const& near
+        = typename index::traits::coordinate_type<Point>::type(0),
+    typename index::traits::coordinate_type<Point>::type const& far
+        = std::numeric_limits<typename index::traits::coordinate_type<Point>::type>::max()
+)
+{
+    return detail::detail::distance_xxx<Point, detail::distance_near_tag>(p, near, far);
+}
+
+template <typename Point>
+inline detail::distance_xxx<Point, detail::distance_far_tag>
+distance_far(
+    Point const& p,
+    typename index::traits::coordinate_type<Point>::type const& near
+        = typename index::traits::coordinate_type<Point>::type(0),
+    typename index::traits::coordinate_type<Point>::type const& far
+        = std::numeric_limits<typename index::traits::coordinate_type<Point>::type>::max()
+    )
+{
+    return detail::detail::distance_xxx<Point, detail::distance_far_tag>(p, near, far);
+}
+
+template <typename Point>
+inline detail::distance_xxx<Point, detail::distance_centroid_tag>
+distance_centroid(
+    Point const& p,
+    typename index::traits::coordinate_type<Point>::type const& near
+        = typename index::traits::coordinate_type<Point>::type(0),
+    typename index::traits::coordinate_type<Point>::type const& far
+        = std::numeric_limits<typename index::traits::coordinate_type<Point>::type>::max()
+    )
+{
+    return detail::detail::distance_xxx<Point, detail::distance_centroid_tag>(p, near, far);
+}
+
+namespace detail
+{
+
+template <typename Point, typename Indexable>
+struct distance_calc
+{
+    typedef typename geometry::default_distance_result<Point, Indexable>::type distance_type;
+
+    static inline distance_type apply(Point const& p, Indexable const& i)
+    {
+        return index::mindist(p, i);
+    }
+};
+
+template <typename Point, typename Indexable>
+struct distance_calc<
+    detail::distance_xxx<Point, detail::distance_near_tag>,
+    Indexable>
+{
+    typedef typename geometry::default_distance_result<Point, Indexable>::type distance_type;
+
+    static inline distance_type apply(
+        detail::distance_xxx<Point, detail::distance_near_tag> const& d,
+        Indexable const& i)
+    {
+        return index::mindist(d.point, i);
+    }
+};
+
+// TODO distance_centroid
+
+template <typename Point, typename Indexable>
+struct distance_calc<
+    detail::distance_xxx<Point, detail::distance_far_tag>,
+    Indexable>
+{
+    typedef typename geometry::default_distance_result<Point, Indexable>::type distance_type;
+
+    static inline distance_type apply(
+        detail::distance_xxx<Point, detail::distance_far_tag> const& d,
+        Indexable const& i)
+    {
+        return index::maxdist(d.point, i);
+    }
+};
+
+template <typename Point>
+struct is_distance_ok
+{
+    template <typename DistanceType>
+    static inline bool apply(Point const&, DistanceType const&)
+    {
+        return true;
+    }
+};
+
+template <typename Point, typename Tag>
+struct is_distance_ok< detail::distance_xxx<Point, Tag> >
+{
+    template <typename DistanceType>
+    static inline bool apply(
+        detail::distance_xxx<Point, Tag> const& dx,
+        DistanceType const& d)
+    {
+        return dx.comparable_near <= d && d <= dx.comparable_far;
+    }
+};
+
+} // namespace detail
+
+template <typename PointData, typename Indexable>
+inline typename detail::distance_calc<PointData, Indexable>::distance_type
+distance_calc(PointData const& p, Indexable const& i)
+{
+    return detail::distance_calc<PointData, Indexable>
+        ::apply(p, i);
+}
+
+template <typename PointData, typename DistanceType>
+inline bool
+is_distance_ok(PointData const& p, DistanceType const& d)
+{
+    return detail::is_distance_ok<PointData>
+        ::apply(p, d);
+}
+
+}}} // namespace boost::geometry::index
+
+#endif // BOOST_GEOMETRY_EXTENSIONS_INDEX_DISTANCE_CALC_HPP

Modified: sandbox-branches/geometry/index/boost/geometry/extensions/index/predicates.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/extensions/index/predicates.hpp	(original)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/predicates.hpp	2011-09-21 14:50:15 EDT (Wed, 21 Sep 2011)
@@ -96,7 +96,11 @@
 
 // predicate check
 
-// TODO: use empty definitions here + MPL_ASSERT
+// TODO: use empty definitions here + MPL_ASSERT ?
+// implement default values predicates applied to values in leafs, as a function/functor as simple as possible
+// bool fun(Value const& v);
+// distinguish between geometries and other types by use of geometry::tag
+// in predicate_check_default<..., GeomTag> -> predicate_check_default<..., void>
 
 template <typename Geometry, typename Tag>
 struct predicate_check

Modified: sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/nearest.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/nearest.hpp	(original)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/nearest.hpp	2011-09-21 14:50:15 EDT (Wed, 21 Sep 2011)
@@ -14,6 +14,8 @@
 #include <boost/geometry/extensions/index/algorithms/minmaxdist.hpp>
 #include <boost/geometry/extensions/index/algorithms/maxdist.hpp>
 
+#include <boost/geometry/extensions/index/nearest_calc.hpp>
+
 #include <boost/geometry/extensions/index/rtree/node/node.hpp>
 
 namespace boost { namespace geometry { namespace index {
@@ -32,37 +34,37 @@
     typedef typename geometry::default_distance_result<Point, indexable_type>::type distance_type;
 
     inline nearest_one()
-        : comp_mindist(std::numeric_limits<distance_type>::max())
+        : comp_dist(std::numeric_limits<distance_type>::max())
     {}
 
-    inline void store(Value const& val, distance_type const& curr_mindist)
+    inline void store(Value const& val, distance_type const& curr_comp_dist)
     {
-        if ( curr_mindist < comp_mindist )
+        if ( curr_comp_dist < comp_dist )
         {
-            comp_mindist = curr_mindist;
+            comp_dist = curr_mindist;
             value = val;
         }
     }
 
-    inline bool is_mindist_valid() const
+    inline bool is_comparable_distance_valid() const
     {
-        return comp_mindist < std::numeric_limits<distance_type>::max();
+        return comp_dist < std::numeric_limits<distance_type>::max();
     }
 
-    inline distance_type mindist() const
+    inline distance_type comparable_distance() const
     {
-        return comp_mindist;
+        return comp_dist;
     }
 
     inline size_t get(Value & v)
     {
         v = value;
-        return is_mindist_valid() ? 1 : 0;
+        return is_comparable_distance_valid() ? 1 : 0;
     }
 
 private:
     Value value;
-    distance_type comp_mindist;
+    distance_type comp_dist;
 };
 
 template <typename Value, typename Translator, typename Point>
@@ -79,9 +81,9 @@
         m_neighbors.reserve(m_count + 1);
     }
 
-    inline void store(Value const& val, distance_type const& curr_mindist)
+    inline void store(Value const& val, distance_type const& curr_comp_dist)
     {
-        m_neighbors.push_back(std::make_pair(curr_mindist, val));
+        m_neighbors.push_back(std::make_pair(curr_comp_dist, val));
         std::sort(m_neighbors.begin(), m_neighbors.end(), neighbors_less);
 
         if ( m_count < m_neighbors.size() )
@@ -93,12 +95,12 @@
         // check the furthest distance at the first place, before push_back()
     }
 
-    inline bool is_mindist_valid() const
+    inline bool is_comparable_distance_valid() const
     {
         return m_neighbors.size() == m_count;
     }
 
-    inline distance_type mindist() const
+    inline distance_type comparable_distance() const
     {
         return m_neighbors.size() < m_count ?
             std::numeric_limits<distance_type>::max() :
@@ -134,10 +136,7 @@
     typename Box,
     typename Point,
     typename Predicates,
-    typename Result = typename geometry::default_distance_result<
-            Point,
-            typename Translator::indexable_type
-        >::type
+    typename Result
 >
 class nearest
     : public rtree::visitor<Value, typename Options::parameters_type, Box, typename Options::node_tag, true>::type
@@ -230,11 +229,11 @@
     inline void prune_nodes(ActiveBranchList & abl) const
     {
         // if some value were found
-        if ( m_result.is_mindist_valid() )
+        if ( m_result.is_comparable_distance_valid() )
         {
             // prune if box's mindist is further than value's mindist
             while ( !abl.empty() &&
-                    m_result.mindist() < abl.back().first )
+                    m_result.comparable_distance() < abl.back().first )
             {
                 abl.pop_back();
             }