Subject: [Boost-commit] svn:boost r74519 - in sandbox-branches/geometry/index: boost/geometry/extensions/index boost/geometry/extensions/index/rtree/visitors tests
From: adam.wulkiewicz_at_[hidden]
Date: 2011-09-22 14:21:23
Author: awulkiew
Date: 2011-09-22 14:21:22 EDT (Thu, 22 Sep 2011)
New Revision: 74519
URL: http://svn.boost.org/trac/boost/changeset/74519
Log:
knn distance calculators added + naming errors fixed
Text files modified:
sandbox-branches/geometry/index/boost/geometry/extensions/index/distance_calc.hpp | 291 ++++++++++++++++++++++++++-------------
sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/nearest.hpp | 10
sandbox-branches/geometry/index/tests/main.cpp | 6
sandbox-branches/geometry/index/tests/rtree_filters.hpp | 2
sandbox-branches/geometry/index/tests/rtree_function.hpp | 10 +
sandbox-branches/geometry/index/tests/translators.hpp | 2
6 files changed, 213 insertions(+), 108 deletions(-)
Modified: sandbox-branches/geometry/index/boost/geometry/extensions/index/distance_calc.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/extensions/index/distance_calc.hpp (original)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/distance_calc.hpp 2011-09-22 14:21:22 EDT (Thu, 22 Sep 2011)
@@ -17,155 +17,259 @@
//TODO: awulkiew - consider storing values instead of const references
// it may be faster and it eliminates problems with storing of references to temporaries
+// data
+
struct distance_near_tag {};
struct distance_far_tag {};
struct distance_centroid_tag {};
+struct distance_min_tag {};
+struct distance_max_tag {};
+
template <typename Point, typename Tag>
-struct distance_xxx
+struct distance_unbounded
+ : nonassignable
+{
+ typedef typename index::traits::coordinate_type<Point>::type coordinate_type;
+
+ inline explicit distance_unbounded(Point const& p)
+ : point(p)
+ {}
+
+ Point const& point;
+};
+
+template <typename Point, typename Tag, typename LimitTag>
+struct distance_half_bounded
: 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()
- )
+ inline explicit distance_half_bounded(Point const& p, coordinate_type const& distance_limit)
: point(p)
- , comparable_near(distance_near * distance_near)
- , comparable_far(distance_far * distance_far)
+ , comparable_limit(distance_limit * distance_limit)
{}
Point const& point;
- distance_type comparable_near;
- distance_type comparable_far;
+ distance_type comparable_limit;
+};
+
+template <typename Point, typename Tag>
+struct distance_bounded
+ : 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_bounded(Point const& p, coordinate_type const& distance_min, coordinate_type const& distance_max)
+ : point(p)
+ , comparable_min(distance_min * distance_min)
+ , comparable_max(distance_max * distance_max)
+ {}
+
+ Point const& point;
+ distance_type comparable_min;
+ distance_type comparable_max;
};
} // namespace detail
+// generators
+
+template <typename Point>
+inline detail::distance_unbounded<Point, detail::distance_near_tag>
+distance_near(Point const& p)
+{
+ return detail::detail::distance_unbounded<Point, detail::distance_near_tag>(p);
+}
+
+template <typename Point>
+inline detail::distance_unbounded<Point, detail::distance_far_tag>
+distance_far(Point const& p)
+{
+ return detail::detail::distance_unbounded<Point, detail::distance_far_tag>(p);
+}
+
+template <typename Point>
+inline detail::distance_unbounded<Point, detail::distance_centroid_tag>
+distance_centroid(Point const& p)
+{
+ return detail::detail::distance_unbounded<Point, detail::distance_centroid_tag>(p);
+}
+
+template <typename Point>
+inline detail::distance_half_bounded<Point, detail::distance_near_tag, detail::distance_min_tag>
+distance_near(
+ Point const& p,
+ typename index::traits::coordinate_type<Point>::type const& distance_min)
+{
+ return detail::detail::distance_half_bounded<Point, detail::distance_near_tag, detail::distance_min_tag>(p, distance_min);
+}
+
template <typename Point>
-inline detail::distance_xxx<Point, detail::distance_near_tag>
-distance(
+inline detail::distance_half_bounded<Point, detail::distance_far_tag, detail::distance_min_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()
-)
+ typename index::traits::coordinate_type<Point>::type const& distance_min)
{
- return detail::detail::distance_xxx<Point, detail::distance_near_tag>(p, near, far);
+ return detail::detail::distance_half_bounded<Point, detail::distance_far_tag, detail::distance_min_tag>(p, distance_min);
}
template <typename Point>
-inline detail::distance_xxx<Point, detail::distance_near_tag>
+inline detail::distance_half_bounded<Point, detail::distance_centroid_tag, detail::distance_min_tag>
+distance_centroid(
+ Point const& p,
+ typename index::traits::coordinate_type<Point>::type const& distance_min)
+{
+ return detail::detail::distance_half_bounded<Point, detail::distance_centroid_tag, detail::distance_min_tag>(p, distance_min);
+}
+
+template <typename Point>
+inline detail::distance_bounded<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()
-)
+ typename index::traits::coordinate_type<Point>::type const& distance_min,
+ typename index::traits::coordinate_type<Point>::type const& distance_max)
{
- return detail::detail::distance_xxx<Point, detail::distance_near_tag>(p, near, far);
+ return detail::detail::distance_bounded<Point, detail::distance_near_tag>(p, distance_min, distance_max);
}
template <typename Point>
-inline detail::distance_xxx<Point, detail::distance_far_tag>
+inline detail::distance_bounded<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()
- )
+ typename index::traits::coordinate_type<Point>::type const& distance_min,
+ typename index::traits::coordinate_type<Point>::type const& distance_max)
{
- return detail::detail::distance_xxx<Point, detail::distance_far_tag>(p, near, far);
+ return detail::detail::distance_bounded<Point, detail::distance_far_tag>(p, distance_min, distance_max);
}
template <typename Point>
-inline detail::distance_xxx<Point, detail::distance_centroid_tag>
+inline detail::distance_bounded<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()
- )
+ typename index::traits::coordinate_type<Point>::type const& distance_min,
+ typename index::traits::coordinate_type<Point>::type const& distance_max)
{
- return detail::detail::distance_xxx<Point, detail::distance_centroid_tag>(p, near, far);
+ return detail::detail::distance_bounded<Point, detail::distance_centroid_tag>(p, distance_min, distance_max);
}
+// algorithms
+
namespace detail
{
+// TODO:
+// to use it properly in case of rtree nodes there must be additional template parameter added: Tag
+// and typedef ... result_type - in case of bounded distance or half-bounded min maxdist must be calculated as well
+
+// distance_calc_result<Point, Indexable>::type or distance_calc<Point, Indexable>::result_type
+// sorting is needed only in rtree nodes so it shouldn't be here, use detail::rtree instead
+// should comp be here or only in detail::rtree?
+
+// in addition, maby don't use Tag, just implement different structure in detail::rtree specialized for rtree?
+// in addition, maby don't use Tag in predicates?
+
+// rename distance_calc -> comparable_distance_calc ? or calculate_comparable_distance or distance_data_calc?
+
+template <typename Point, typename Indexable, typename AlgoTag>
+struct distance_calc_impl
+{
+ // TODO MPL_ASSERT
+};
+
template <typename Point, typename Indexable>
-struct distance_calc
+struct distance_calc_impl<Point, Indexable, detail::distance_near_tag>
{
- typedef typename geometry::default_distance_result<Point, Indexable>::type distance_type;
+ typedef typename geometry::default_distance_result<Point, Indexable>::type result_type;
- static inline distance_type apply(Point const& p, Indexable const& i)
+ static inline result_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>
+struct distance_calc_impl<Point, Indexable, detail::distance_far_tag>
{
- typedef typename geometry::default_distance_result<Point, Indexable>::type distance_type;
+ typedef typename geometry::default_distance_result<Point, Indexable>::type result_type;
- static inline distance_type apply(
- detail::distance_xxx<Point, detail::distance_near_tag> const& dx,
- Indexable const& i)
+ static inline result_type apply(Point const& p, Indexable const& i)
{
- return index::mindist(dx.point, i);
+ return index::maxdist(p, i);
}
};
-// TODO distance_centroid
+// TODO distance_calc_impl<Point, Indexable, detail::distance_centroid_tag>
+// rename:
+// mindist -> comparable_distance_near
+// maxdist -> comparable_distance_far
+// add comparable_distance_centroid
-template <typename Point, typename Indexable>
+template <typename Point, typename Indexable, typename Tag>
+struct distance_calc
+{
+ typedef typename geometry::default_distance_result<Point, Indexable>::type result_type;
+
+ static inline result_type apply(Point const& p, Indexable const& i)
+ {
+ return index::mindist(p, i);
+ }
+};
+
+template <typename Point, typename AlgoTag, typename Indexable, typename Tag>
struct distance_calc<
- detail::distance_xxx<Point, detail::distance_far_tag>,
- Indexable>
+ detail::distance_unbounded<Point, AlgoTag>,
+ Indexable,
+ Tag>
{
- typedef typename geometry::default_distance_result<Point, Indexable>::type distance_type;
+ typedef typename distance_calc_impl<Point, Indexable, AlgoTag>::result_type result_type;
- static inline distance_type apply(
- detail::distance_xxx<Point, detail::distance_far_tag> const& dx,
+ static inline result_type apply(
+ detail::distance_unbounded<Point, AlgoTag> const& dx,
Indexable const& i)
{
- return index::maxdist(dx.point, i);
+ return distance_calc_impl<Point, Indexable, AlgoTag>::apply(dx.point, i);
}
};
-template <typename Point>
-struct distance_comp
+template <typename Point, typename AlgoTag, typename LimitTag, typename Indexable, typename Tag>
+struct distance_calc<
+ detail::distance_half_bounded<Point, AlgoTag, LimitTag>,
+ Indexable,
+ Tag>
{
- template <typename DistanceType>
- static inline bool apply(Point const&, DistanceType const&)
+ typedef typename distance_calc_impl<Point, Indexable, AlgoTag>::result_type result_type;
+
+ static inline result_type apply(
+ detail::distance_half_bounded<Point, AlgoTag, LimitTag> const& dx,
+ Indexable const& i)
{
- return true;
+ return distance_calc_impl<Point, Indexable, AlgoTag>::apply(dx.point, i);
}
};
-template <typename Point, typename Tag>
-struct distance_comp< detail::distance_xxx<Point, Tag> >
+template <typename Point, typename AlgoTag, typename Indexable, typename Tag>
+struct distance_calc<
+ detail::distance_bounded<Point, AlgoTag>,
+ Indexable,
+ Tag>
{
- template <typename DistanceType>
- static inline bool apply(
- detail::distance_xxx<Point, Tag> const& dx,
- DistanceType const& d)
+ typedef typename distance_calc_impl<Point, Indexable, AlgoTag>::result_type result_type;
+
+ static inline result_type apply(
+ detail::distance_bounded<Point, AlgoTag> const& dx,
+ Indexable const& i)
{
- return dx.comparable_near <= d && d <= dx.comparable_far;
+ return distance_calc_impl<Point, Indexable, AlgoTag>::apply(dx.point, i);
}
};
-// TODO: awulkiew - pruning for nodes!
+// TODO distance_comp
+// move distance_calc and distance_comp into geometry::index ?
+
+// TODO: awulkiew - pruning for nodes! <- inside detail::rtree so NOT HERE
// if 0 < comp_near node is pruned if maxdist(point, node_box) < comp_near
// if comp_far < INF node is pruned if comp_far < min_dist(point, node_box)
// still nodes must be sorted by min_dist(point, node_box)
@@ -173,42 +277,27 @@
// for values, proper distance values are calculated min, max or centroid
// and tested with comp_near and/or comp_far
-// implement versions with only one comp or without comp distances?
-// less tests == speed increase
-// near_between, near_lesser, near_greater
-// far_xxx
-// centroid_xxx, center_xxx
-
-// distance_range, distance_bound, distance_upper_bound
-
-// distance_between<near | far| centroid tag> - now distance_xxx
-// distance_xxxxxx<near|far|centroid, less|more>
-// distance_point_only
-
-// distance_calc for each <near|far|centroid>
-// distance_comp for each class and xxxxxx<less|more>
-
// + something in case of nodes
// additional calculation of maxdist in case of distance_between and
// distance_xxxxx<more>
} // 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
-distance_comp(PointData const& p, DistanceType const& d)
-{
- return detail::distance_comp<PointData>
- ::apply(p, d);
-}
+//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
+//distance_comp(PointData const& p, DistanceType const& d)
+//{
+// return detail::distance_comp<PointData>
+// ::apply(p, d);
+//}
}}} // namespace boost::geometry::index
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-22 14:21:22 EDT (Thu, 22 Sep 2011)
@@ -14,7 +14,7 @@
#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/distance_calc.hpp>
#include <boost/geometry/extensions/index/rtree/node/node.hpp>
@@ -147,7 +147,7 @@
typedef typename rtree::internal_node<Value, typename Options::parameters_type, Box, typename Options::node_tag>::type internal_node;
typedef typename rtree::leaf<Value, typename Options::parameters_type, Box, typename Options::node_tag>::type leaf;
- typedef typename geometry::default_distance_result<Point, Box>::type node_distance_type;
+ typedef typename geometry::default_distance_result<PointData, Box>::type node_distance_type;
inline nearest(Translator const& t, PointData const& point_data, Predicates const& pr, Result & r)
: m_tr(t), m_point_data(point_data), m_pred(pr)
@@ -175,7 +175,7 @@
if ( index::predicates_check<rtree::node_predicates_tag>(m_pred, it->first) )
{
active_branch_list.push_back(
- std::make_pair(index::mindist(m_point, it->first), it->second)
+ std::make_pair(index::mindist(m_point_data, it->first), it->second)
);
}
}
@@ -212,7 +212,7 @@
if ( index::predicates_check<rtree::value_predicates_tag>(m_pred, m_tr(*it)) )
{
// store value
- m_result.store(*it, index::mindist(m_point, m_tr(*it)));
+ m_result.store(*it, index::mindist(m_point_data, m_tr(*it)));
}
}
}
@@ -241,7 +241,7 @@
}
Translator const& m_tr;
- Point const& m_point_data;
+ PointData const& m_point_data;
Predicates const& m_pred;
Result & m_result;
Modified: sandbox-branches/geometry/index/tests/main.cpp
==============================================================================
--- sandbox-branches/geometry/index/tests/main.cpp (original)
+++ sandbox-branches/geometry/index/tests/main.cpp 2011-09-22 14:21:22 EDT (Thu, 22 Sep 2011)
@@ -17,13 +17,15 @@
::srand( (unsigned)::time(NULL) );
}
+//#define TEST_PRINT_INFO
+
#include <tests/translators.hpp>
#include <tests/rtree_function.hpp>
-#include <tests/rtree_filters.hpp>
+//#include <tests/rtree_filters.hpp>
BOOST_AUTO_TEST_CASE( last_test_case )
{
- tests_rtree_filters_hpp();
+ //tests_rtree_filters_hpp();
#ifdef _MSC_VER
std::cin.get();
Modified: sandbox-branches/geometry/index/tests/rtree_filters.hpp
==============================================================================
--- sandbox-branches/geometry/index/tests/rtree_filters.hpp (original)
+++ sandbox-branches/geometry/index/tests/rtree_filters.hpp 2011-09-22 14:21:22 EDT (Thu, 22 Sep 2011)
@@ -31,7 +31,9 @@
void tests_rtree_filters_hpp()
{
+#ifdef TEST_PRINT_INFO
std::cout << "tests/rtree_filters.hpp\n";
+#endif
typedef boost::geometry::model::point<float, 2, boost::geometry::cs::cartesian> P;
typedef boost::geometry::model::box<P> B;
Modified: sandbox-branches/geometry/index/tests/rtree_function.hpp
==============================================================================
--- sandbox-branches/geometry/index/tests/rtree_function.hpp (original)
+++ sandbox-branches/geometry/index/tests/rtree_function.hpp 2011-09-22 14:21:22 EDT (Thu, 22 Sep 2011)
@@ -298,7 +298,9 @@
BOOST_AUTO_TEST_CASE(tests_rtree_function_box3f)
{
+#ifdef TEST_PRINT_INFO
std::cout << "tests/rtree_function_box3f\n";
+#endif
namespace bg = boost::geometry;
namespace bgi = bg::index;
@@ -314,7 +316,9 @@
BOOST_AUTO_TEST_CASE(tests_rtree_function_box2f)
{
+#ifdef TEST_PRINT_INFO
std::cout << "tests/rtree_function_box2f\n";
+#endif
namespace bg = boost::geometry;
namespace bgi = bg::index;
@@ -330,7 +334,9 @@
BOOST_AUTO_TEST_CASE(tests_rtree_function_point2f)
{
+#ifdef TEST_PRINT_INFO
std::cout << "tests/rtree_function_point2f\n";
+#endif
namespace bg = boost::geometry;
namespace bgi = bg::index;
@@ -368,7 +374,9 @@
BOOST_AUTO_TEST_CASE(tests_rtree_function_pair_box2f_int)
{
+#ifdef TEST_PRINT_INFO
std::cout << "tests/rtree_function_pair_box2f_int\n";
+#endif
namespace bg = boost::geometry;
namespace bgi = bg::index;
@@ -407,7 +415,9 @@
BOOST_AUTO_TEST_CASE(tests_rtree_function_shared_ptr_pair_box2f_int)
{
+#ifdef TEST_PRINT_INFO
std::cout << "tests/rtree_function_shared_ptr_pair_box2f_int\n";
+#endif
namespace bg = boost::geometry;
namespace bgi = bg::index;
Modified: sandbox-branches/geometry/index/tests/translators.hpp
==============================================================================
--- sandbox-branches/geometry/index/tests/translators.hpp (original)
+++ sandbox-branches/geometry/index/tests/translators.hpp 2011-09-22 14:21:22 EDT (Thu, 22 Sep 2011)
@@ -34,7 +34,9 @@
BOOST_AUTO_TEST_CASE(tests_translators)
{
+#ifdef TEST_PRINT_INFO
std::cout << "tests/translators\n";
+#endif
namespace bg = boost::geometry;
namespace bgm = bg::model;