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();
}