Subject: [Boost-commit] svn:boost r84209 - in trunk/boost/geometry/index: . detail detail/rtree detail/rtree/visitors
From: adam.wulkiewicz_at_[hidden]
Date: 2013-05-09 14:01:27
Author: awulkiew
Date: 2013-05-09 14:01:25 EDT (Thu, 09 May 2013)
New Revision: 84209
URL: http://svn.boost.org/trac/boost/changeset/84209
Log:
geometry.index: introduced distance query - a generalized nearest query. distance calculation simplified. nearest query implemented using distance query. added path() predicate and query implemented using distance query as well.
Text files modified:
trunk/boost/geometry/index/detail/distance_predicates.hpp | 787 +--------------------------------------
trunk/boost/geometry/index/detail/predicates.hpp | 111 +++-
trunk/boost/geometry/index/detail/rtree/query_iterators.hpp | 26
trunk/boost/geometry/index/detail/rtree/visitors/nearest_query.hpp | 263 ++++---------
trunk/boost/geometry/index/predicates.hpp | 36 +
trunk/boost/geometry/index/rtree.hpp | 72 +--
6 files changed, 263 insertions(+), 1032 deletions(-)
Modified: trunk/boost/geometry/index/detail/distance_predicates.hpp
==============================================================================
--- trunk/boost/geometry/index/detail/distance_predicates.hpp (original)
+++ trunk/boost/geometry/index/detail/distance_predicates.hpp 2013-05-09 14:01:25 EDT (Thu, 09 May 2013)
@@ -15,36 +15,13 @@
#include <boost/geometry/index/detail/algorithms/comparable_distance_near.hpp>
#include <boost/geometry/index/detail/algorithms/comparable_distance_far.hpp>
#include <boost/geometry/index/detail/algorithms/comparable_distance_centroid.hpp>
-
-#include <boost/geometry/index/detail/tuples.hpp>
+#include <boost/geometry/index/detail/algorithms/path_intersection.hpp>
#include <boost/geometry/index/detail/tags.hpp>
-// TODO - optimization
-// For Boxes and Points all types of distances may be calculated
-// - near, far and centroid. For points those are the same distance
-// calculate them for Boxes only!
-// for Points calculate only 1 distance
-
namespace boost { namespace geometry { namespace index { namespace detail {
// ------------------------------------------------------------------ //
-// distance_predicates_type
-// ------------------------------------------------------------------ //
-
-template <typename NearestPredicate>
-struct distance_predicates_type
-{
- typedef void type;
-};
-
-template <typename DistancePredicates>
-struct distance_predicates_type< detail::nearest<DistancePredicates> >
-{
- typedef DistancePredicates type;
-};
-
-// ------------------------------------------------------------------ //
// relations
// ------------------------------------------------------------------ //
@@ -116,767 +93,67 @@
};
// ------------------------------------------------------------------ //
-// distance predicates
-// ------------------------------------------------------------------ //
-
-//template <typename PointRelation>
-//struct unbounded
-// : nonassignable
-//{
-// inline explicit unbounded(PointRelation const& pr)
-// : point_relation(pr)
-// {}
-//
-// PointRelation point_relation;
-//};
-//
-//template <typename PointRelation, typename MinRelation>
-//struct min_bounded
-// : nonassignable
-//{
-// typedef typename detail::relation<PointRelation>::value_type point_type;
-// typedef typename geometry::default_distance_result<point_type, point_type>::type distance_type;
-//
-// inline min_bounded(PointRelation const& pr, MinRelation const& min_rel)
-// : point_relation(pr)
-// , comparable_min(
-// relation<MinRelation>::value(min_rel) *
-// relation<MinRelation>::value(min_rel) )
-// {}
-//
-// PointRelation point_relation;
-// distance_type comparable_min;
-//};
-//
-//template <typename PointRelation, typename MaxRelation>
-//struct max_bounded
-// : nonassignable
-//{
-// typedef typename detail::relation<PointRelation>::value_type point_type;
-// typedef typename geometry::default_distance_result<point_type, point_type>::type distance_type;
-//
-// inline max_bounded(PointRelation const& pr, MaxRelation const& max_rel)
-// : point_relation(pr)
-// , comparable_max(
-// relation<MaxRelation>::value(max_rel) *
-// relation<MaxRelation>::value(max_rel) )
-// {}
-//
-// PointRelation point_relation;
-// distance_type comparable_max;
-//};
-//
-//template <typename PointRelation, typename MinRelation, typename MaxRelation>
-//struct bounded
-// : nonassignable
-//{
-// typedef typename detail::relation<PointRelation>::value_type point_type;
-// typedef typename geometry::default_distance_result<point_type, point_type>::type distance_type;
-//
-// inline bounded(PointRelation const& pr, MinRelation const& min_rel, MaxRelation const& max_rel)
-// : point_relation(pr)
-// , comparable_min(
-// relation<MinRelation>::value(min_rel) *
-// relation<MinRelation>::value(min_rel) )
-// , comparable_max(
-// relation<MaxRelation>::value(max_rel) *
-// relation<MaxRelation>::value(max_rel) )
-// {}
-//
-// PointRelation point_relation;
-// distance_type comparable_min;
-// distance_type comparable_max;
-//};
-
-// ------------------------------------------------------------------ //
-// point_relation trait
-// ------------------------------------------------------------------ //
-
-template <typename PointRelation>
-struct point_relation
-{
- typedef PointRelation type;
-};
-
-//template <typename PointRelation>
-//struct point_relation< detail::unbounded<PointRelation> >
-//{
-// typedef PointRelation type;
-//};
-//
-//template <typename PointRelation, typename MinRelation>
-//struct point_relation< detail::min_bounded<PointRelation, MinRelation> >
-//{
-// typedef PointRelation type;
-//};
-//
-//template <typename PointRelation, typename MaxRelation>
-//struct point_relation< detail::max_bounded<PointRelation, MaxRelation> >
-//{
-// typedef PointRelation type;
-//};
-//
-//template <typename PointRelation, typename MinRelation, typename MaxRelation>
-//struct point_relation< detail::bounded<PointRelation, MinRelation, MaxRelation> >
-//{
-// typedef PointRelation type;
-//};
-
-// ------------------------------------------------------------------ //
-// helpers
+// calculate_distance
// ------------------------------------------------------------------ //
-// algorithms
-
-// cdist
-
-template <typename T, typename Tag>
-struct cdist
-{
- T value;
-};
-
-// cdist_merge
-
-template <typename CDistTuple, typename CDist>
-struct cdist_merge
-{
- typedef typename detail::tuples::add_unique<
- CDistTuple,
- CDist
- >::type type;
-};
-
-template <typename T, typename Tag, typename OtherTag>
-struct cdist_merge<
- cdist<T, Tag>,
- cdist<T, OtherTag> >
+template <typename Predicate, typename Indexable, typename Tag>
+struct calculate_distance
{
- typedef boost::tuple<
- cdist<T, Tag>,
- cdist<T, OtherTag>
- > type;
-};
-
-template <typename T, typename Tag>
-struct cdist_merge<
- cdist<T, Tag>,
- cdist<T, Tag> >
-{
- typedef cdist<T, Tag> type;
-};
-
-// cdist_value_type
-
-template <typename CDistTuple>
-struct cdist_value
-{
- typedef typename cdist_value<
- typename boost::tuples::element<0, CDistTuple>::type
- >::type type;
-
- template <typename Tag>
- static inline type & get(CDistTuple & cdtup)
- {
- return boost::get<
- tuples::find_index<
- CDistTuple,
- cdist<type, Tag>
- >::value
- >(cdtup).value;
- }
-
- template <typename Tag>
- static inline type const& get(CDistTuple const& cdtup)
- {
- return boost::get<
- tuples::find_index<
- CDistTuple,
- cdist<type, Tag>
- >::value
- >(cdtup).value;
- }
-};
-
-template <typename T, typename Tag>
-struct cdist_value<
- cdist<T, Tag>
->
-{
- typedef T type;
-
- template <typename Tag2>
- static inline type & get(cdist<T, Tag> & cd)
- {
- BOOST_MPL_ASSERT_MSG(
- (boost::is_same< cdist<T, Tag2>, cdist<T, Tag> >::value),
- TAGS_DO_NOT_MATCH,
- (cdist_value));
-
- return cd.value;
- }
-
- template <typename Tag2>
- static inline type const& get(cdist<T, Tag> const& cd)
- {
- BOOST_MPL_ASSERT_MSG(
- (boost::is_same< cdist<T, Tag2>, cdist<T, Tag> >::value),
- TAGS_DO_NOT_MATCH,
- (cdist_value));
-
- return cd.value;
- }
-};
-
-// distances_calc_impl_rel
-
-template <typename RelDist>
-struct distances_calc_impl_rel
-{
- BOOST_MPL_ASSERT_MSG(
- (false),
- NOT_IMPLEMENTED_FOR_THIS_RELATION,
- (distances_calc_impl_rel));
-};
-
-template <typename T>
-struct distances_calc_impl_rel<
- cdist<T, detail::to_nearest_tag>
->
-{
- template <typename Point, typename Indexable>
- typename geometry::default_distance_result<Point, Indexable>::type
- static inline apply(Point const& p, Indexable const& i)
- {
- return index::detail::comparable_distance_near(p, i);
- }
-};
-
-template <typename T>
-struct distances_calc_impl_rel<
- cdist<T, detail::to_centroid_tag>
->
-{
- template <typename Point, typename Indexable>
- typename geometry::default_distance_result<Point, Indexable>::type
- static inline apply(Point const& p, Indexable const& i)
- {
- return index::detail::comparable_distance_centroid(p, i);
- }
-};
-
-template <typename T>
-struct distances_calc_impl_rel<
- cdist<T, detail::to_furthest_tag>
->
-{
- template <typename Point, typename Indexable>
- typename geometry::default_distance_result<Point, Indexable>::type
- static inline apply(Point const& p, Indexable const& i)
- {
- return index::detail::comparable_distance_far(p, i);
- }
+ BOOST_MPL_ASSERT_MSG((false), INVALID_PREDICATE_OR_TAG, (calculate_distance));
};
-// distances_calc_impl_tuple
-
-template <typename Distances, typename Point, typename Indexable, unsigned N>
-struct distances_calc_impl_tuple
+// this handles nearest() with default Point parameter, to_nearest() and bounds
+template <typename PointRelation, typename Indexable, typename Tag>
+struct calculate_distance< nearest<PointRelation>, Indexable, Tag >
{
- // TODO MPL ASSERT 0 < N
- static inline void apply(Distances & d, Point const& p, Indexable const&i)
- {
- boost::get<N - 1>(d).value =
- distances_calc_impl_rel<
- typename boost::tuples::element<N - 1, Distances>::type
- >::apply(p, i);
-
- distances_calc_impl_tuple<
- Distances,
- Point,
- Indexable,
- N - 1
- >::apply(d, p, i);
- }
-};
+ typedef detail::relation<PointRelation> relation;
+ typedef typename relation::value_type point_type;
+ typedef typename geometry::default_distance_result<point_type, Indexable>::type result_type;
-template <typename Distances, typename Point, typename Indexable>
-struct distances_calc_impl_tuple<Distances, Point, Indexable, 1>
-{
- static inline void apply(Distances & d, Point const& p, Indexable const&i)
+ static inline bool apply(nearest<PointRelation> const& p, Indexable const& i, result_type & result)
{
- boost::get<0>(d).value =
- distances_calc_impl_rel<
- typename boost::tuples::element<0, Distances>::type
- >::apply(p, i);
+ result = index::detail::comparable_distance_near(relation::value(p.point_or_relation), i);
+ return true;
}
};
-// distances_calc_impl
-
-template <typename Distances, typename Point, typename Indexable>
-struct distances_calc_impl
+template <typename Point, typename Indexable>
+struct calculate_distance< nearest< to_centroid<Point> >, Indexable, value_tag>
{
- static inline void apply(Distances & d, Point const& p, Indexable const&i)
- {
- distances_calc_impl_tuple<
- Distances,
- Point,
- Indexable,
- boost::tuples::length<Distances>::value
- >::apply(d, p, i);
- }
-};
+ typedef Point point_type;
+ typedef typename geometry::default_distance_result<point_type, Indexable>::type result_type;
-template <typename T, typename Tag, typename Point, typename Indexable>
-struct distances_calc_impl<
- cdist<T, Tag>,
- Point,
- Indexable
->
-{
- static inline void apply(cdist<T, Tag> & d, Point const& p, Indexable const&i)
+ static inline bool apply(nearest< to_centroid<Point> > const& p, Indexable const& i, result_type & result)
{
- d.value = distances_calc_impl_rel<
- cdist<T, Tag>
- >::apply(p, i);
+ result = index::detail::comparable_distance_centroid(p.point_or_relation.value, i);
+ return true;
}
};
-// ------------------------------------------------------------------ //
-// distance_calc and distances_predicates_check
-// ------------------------------------------------------------------ //
-
-template <typename PointRelation, typename Indexable, typename Tag>
-struct distances_calc
-{
- BOOST_MPL_ASSERT_MSG(
- (false),
- NOT_IMPLEMENTED_FOR_THIS_TAG,
- (distances_calc));
-};
-
-template <typename PointRelation, typename Indexable, typename Tag>
-struct distances_predicates_check
-{
- BOOST_MPL_ASSERT_MSG(
- (false),
- NOT_IMPLEMENTED_FOR_THIS_TAG,
- (distances_predicates_check));
-};
-
-// ------------------------------------------------------------------ //
-// distance_calc for value_tag
-// ------------------------------------------------------------------ //
-
-template <typename PointRelation, typename Indexable>
-struct distances_calc<PointRelation, Indexable, value_tag>
+template <typename Point, typename Indexable>
+struct calculate_distance< nearest< to_furthest<Point> >, Indexable, value_tag>
{
- typedef typename detail::relation<PointRelation>::value_type point_type;
- typedef typename detail::relation<PointRelation>::tag point_relation_tag;
- typedef typename geometry::default_distance_result<point_type, Indexable>::type distance_type;
-
- typedef detail::cdist<distance_type, point_relation_tag> result_type;
-
- static inline result_type apply(PointRelation const& p, Indexable const& i)
- {
- result_type res;
- distances_calc_impl<result_type, point_type, Indexable>
- ::apply(res, relation<PointRelation>::value(p), i);
- return res;
- }
-};
-
-//template <typename PointRelation, typename Indexable>
-//struct distances_calc<
-// detail::unbounded<PointRelation>,
-// Indexable,
-// value_tag
-//>
-//{
-// typedef typename detail::relation<PointRelation>::value_type point_type;
-// typedef typename detail::relation<PointRelation>::tag point_relation_tag;
-// typedef typename geometry::default_distance_result<point_type, Indexable>::type distance_type;
-//
-// typedef detail::cdist<distance_type, point_relation_tag> result_type;
-//
-// static inline result_type apply(detail::unbounded<PointRelation> const& pp, Indexable const& i)
-// {
-// result_type res;
-// distances_calc_impl<result_type, point_type, Indexable>
-// ::apply(res, relation<PointRelation>::value(pp.point_relation), i);
-// return res;
-// }
-//};
-//
-//template <typename PointRelation, typename MinRelation, typename Indexable>
-//struct distances_calc<
-// detail::min_bounded<PointRelation, MinRelation>,
-// Indexable,
-// value_tag
-//>
-//{
-// typedef typename detail::relation<PointRelation>::value_type point_type;
-// typedef typename detail::relation<PointRelation>::tag point_relation_tag;
-// typedef typename geometry::default_distance_result<point_type, Indexable>::type distance_type;
-// typedef typename detail::relation<MinRelation>::tag min_relation_tag;
-//
-// typedef typename detail::cdist_merge<
-// cdist<distance_type, point_relation_tag>,
-// cdist<distance_type, min_relation_tag>
-// >::type result_type;
-//
-// static inline result_type apply(detail::min_bounded<PointRelation, MinRelation> const& pp, Indexable const& i)
-// {
-// result_type res;
-// distances_calc_impl<result_type, point_type, Indexable>
-// ::apply(res, relation<PointRelation>::value(pp.point_relation), i);
-// return res;
-// }
-//};
-//
-//template <typename PointRelation, typename MaxRelation, typename Indexable>
-//struct distances_calc<
-// detail::max_bounded<PointRelation, MaxRelation>,
-// Indexable,
-// value_tag
-//>
-//{
-// typedef typename detail::relation<PointRelation>::value_type point_type;
-// typedef typename detail::relation<PointRelation>::tag point_relation_tag;
-// typedef typename geometry::default_distance_result<point_type, Indexable>::type distance_type;
-// typedef typename detail::relation<MaxRelation>::tag max_relation_tag;
-//
-// typedef typename detail::cdist_merge<
-// cdist<distance_type, point_relation_tag>,
-// cdist<distance_type, max_relation_tag>
-// >::type result_type;
-//
-// static inline result_type apply(detail::max_bounded<PointRelation, MaxRelation> const& pp, Indexable const& i)
-// {
-// result_type res;
-// distances_calc_impl<result_type, point_type, Indexable>
-// ::apply(res, relation<PointRelation>::value(pp.point_relation), i);
-// return res;
-// }
-//};
-//
-//template <typename PointRelation, typename MinRelation, typename MaxRelation, typename Indexable>
-//struct distances_calc<
-// detail::bounded<PointRelation, MinRelation, MaxRelation>,
-// Indexable,
-// value_tag
-//>
-//{
-// typedef typename detail::relation<PointRelation>::value_type point_type;
-// typedef typename detail::relation<PointRelation>::tag point_relation_tag;
-// typedef typename geometry::default_distance_result<point_type, Indexable>::type distance_type;
-// typedef typename detail::relation<MinRelation>::tag min_relation_tag;
-// typedef typename detail::relation<MaxRelation>::tag max_relation_tag;
-//
-// typedef typename detail::cdist_merge<
-// typename detail::cdist_merge<
-// cdist<distance_type, point_relation_tag>,
-// cdist<distance_type, min_relation_tag>
-// >::type,
-// cdist<distance_type, max_relation_tag>
-// >::type result_type;
-//
-// static inline result_type apply(
-// detail::bounded<PointRelation, MinRelation, MaxRelation> const& pp,
-// Indexable const& i)
-// {
-// result_type res;
-// distances_calc_impl<result_type, point_type, Indexable>
-// ::apply(res, relation<PointRelation>::value(pp.point_relation), i);
-// return res;
-// }
-//};
+ typedef Point point_type;
+ typedef typename geometry::default_distance_result<point_type, Indexable>::type result_type;
-// ------------------------------------------------------------------ //
-// distance_predicates_check for value_tag
-// ------------------------------------------------------------------ //
-
-template <typename PointRelation, typename Indexable>
-struct distances_predicates_check<PointRelation, Indexable, value_tag>
-{
- template <typename Distances>
- static inline bool apply(PointRelation const&, Distances const&)
+ static inline bool apply(nearest< to_furthest<Point> > const& p, Indexable const& i, result_type & result)
{
+ result = index::detail::comparable_distance_far(p.point_or_relation.value, i);
return true;
}
};
-//template <typename PointRelation, typename Indexable>
-//struct distances_predicates_check<
-// detail::unbounded<PointRelation>,
-// Indexable,
-// value_tag
-//>
-//{
-// template <typename Distances>
-// static inline bool apply(detail::unbounded<PointRelation> const&, Distances const&)
-// {
-// return true;
-// }
-//};
-//
-//template <typename PointRelation, typename MinRelation, typename Indexable>
-//struct distances_predicates_check<
-// detail::min_bounded<PointRelation, MinRelation>,
-// Indexable,
-// value_tag
-//>
-//{
-// typedef typename detail::relation<MinRelation>::tag min_relation_tag;
-//
-// template <typename Distances>
-// static inline bool apply(
-// detail::min_bounded<PointRelation, MinRelation> const& pred,
-// Distances const& d)
-// {
-// return pred.comparable_min <=
-// detail::cdist_value<Distances>::template get<min_relation_tag>(d);
-// }
-//};
-//
-//template <typename PointRelation, typename MaxRelation, typename Indexable>
-//struct distances_predicates_check<
-// detail::max_bounded<PointRelation, MaxRelation>,
-// Indexable,
-// value_tag
-//>
-//{
-// typedef typename detail::relation<MaxRelation>::tag max_relation_tag;
-//
-// template <typename Distances>
-// static inline bool apply(
-// detail::max_bounded<PointRelation, MaxRelation> const& pred,
-// Distances const& d)
-// {
-// return pred.comparable_max <=
-// detail::cdist_value<Distances>::template get<max_relation_tag>(d);
-// }
-//};
-//
-//template <typename PointRelation, typename MinRelation, typename MaxRelation, typename Indexable>
-//struct distances_predicates_check<
-// detail::bounded<PointRelation, MinRelation, MaxRelation>,
-// Indexable,
-// value_tag
-//>
-//{
-// typedef typename detail::relation<MinRelation>::tag min_relation_tag;
-// typedef typename detail::relation<MaxRelation>::tag max_relation_tag;
-//
-// template <typename Distances>
-// static inline bool apply(
-// detail::bounded<PointRelation, MinRelation, MaxRelation> const& pred,
-// Distances const& d)
-// {
-// return pred.comparable_min
-// <= detail::cdist_value<Distances>::template get<min_relation_tag>(d)
-// && detail::cdist_value<Distances>::template get<max_relation_tag>(d)
-// <= pred.comparable_max;
-// }
-//};
-
-// ------------------------------------------------------------------ //
-// distance_calc for bounds_tag
-// ------------------------------------------------------------------ //
-
-template <typename PointRelation, typename Box>
-struct distances_calc<
- PointRelation,
- Box,
- bounds_tag>
+template <typename Linestring, typename Indexable, typename Tag>
+struct calculate_distance< path<Linestring>, Indexable, Tag>
{
- typedef typename detail::relation<PointRelation>::value_type point_type;
- typedef typename geometry::default_distance_result<point_type, Box>::type distance_type;
-
- typedef detail::cdist<distance_type, detail::to_nearest_tag> result_type;
-
- static inline result_type apply(PointRelation const& p, Box const& i)
- {
- result_type res;
- distances_calc_impl<result_type, point_type, Box>
- ::apply(res, relation<PointRelation>::value(p), i);
- return res;
- }
-};
-
-//template <typename PointRelation, typename Box>
-//struct distances_calc<
-// detail::unbounded<PointRelation>,
-// Box,
-// bounds_tag
-//>
-//{
-// typedef typename detail::relation<PointRelation>::value_type point_type;
-// typedef typename geometry::default_distance_result<point_type, Box>::type distance_type;
-//
-// typedef detail::cdist<distance_type, detail::to_nearest_tag> result_type;
-//
-// static inline result_type apply(detail::unbounded<PointRelation> const& pp, Box const& i)
-// {
-// result_type res;
-// distances_calc_impl<result_type, point_type, Box>
-// ::apply(res, relation<PointRelation>::value(pp.point_relation), i);
-// return res;
-// }
-//};
-//
-//template <typename PointRelation, typename MinRelation, typename Box>
-//struct distances_calc<
-// detail::min_bounded<PointRelation, MinRelation>,
-// Box,
-// bounds_tag
-//>
-//{
-// typedef typename detail::relation<PointRelation>::value_type point_type;
-// typedef typename geometry::default_distance_result<point_type, Box>::type distance_type;
-//
-// typedef typename detail::cdist_merge<
-// cdist<distance_type, detail::to_nearest_tag>,
-// cdist<distance_type, detail::to_furthest_tag>
-// >::type result_type;
-//
-// static inline result_type apply(detail::min_bounded<PointRelation, MinRelation> const& pp, Box const& i)
-// {
-// result_type res;
-// distances_calc_impl<result_type, point_type, Box>
-// ::apply(res, relation<PointRelation>::value(pp.point_relation), i);
-// return res;
-// }
-//};
-//
-//template <typename PointRelation, typename MaxRelation, typename Box>
-//struct distances_calc<
-// detail::max_bounded<PointRelation, MaxRelation>,
-// Box,
-// bounds_tag
-//>
-//{
-// typedef typename detail::relation<PointRelation>::value_type point_type;
-// typedef typename geometry::default_distance_result<point_type, Box>::type distance_type;
-//
-// typedef cdist<distance_type, detail::to_nearest_tag> result_type;
-//
-// static inline result_type apply(detail::max_bounded<PointRelation, MaxRelation> const& pp, Box const& i)
-// {
-// result_type res;
-// distances_calc_impl<result_type, point_type, Box>
-// ::apply(res, relation<PointRelation>::value(pp.point_relation), i);
-// return res;
-// }
-//};
-//
-//template <typename PointRelation, typename MinRelation, typename MaxRelation, typename Box>
-//struct distances_calc<
-// detail::bounded<PointRelation, MinRelation, MaxRelation>,
-// Box,
-// bounds_tag
-//>
-//{
-// typedef typename detail::relation<PointRelation>::value_type point_type;
-// typedef typename geometry::default_distance_result<point_type, Box>::type distance_type;
-//
-// typedef typename detail::cdist_merge<
-// cdist<distance_type, detail::to_nearest_tag>,
-// cdist<distance_type, detail::to_furthest_tag>
-// >::type result_type;
-//
-// static inline result_type apply(detail::bounded<PointRelation, MinRelation, MaxRelation> const& pp, Box const& i)
-// {
-// result_type res;
-// distances_calc_impl<result_type, point_type, Box>
-// ::apply(res, relation<PointRelation>::value(pp.point_relation), i);
-// return res;
-// }
-//};
-
-// ------------------------------------------------------------------ //
-// distance_predicates_check for bounds_tag
-// ------------------------------------------------------------------ //
+ typedef typename geometry::default_length_result<Linestring>::type result_type;
-template <typename PointRelation, typename Box>
-struct distances_predicates_check<
- PointRelation,
- Box,
- bounds_tag>
-{
- template <typename Distances>
- static inline bool apply(PointRelation const&, Distances const&)
+ static inline bool apply(path<Linestring> const& p, Indexable const& i, result_type & result)
{
- return true;
+ return index::detail::path_intersection(i, p.linestring, result);
}
};
-//template <typename PointRelation, typename Box>
-//struct distances_predicates_check<
-// detail::unbounded<PointRelation>,
-// Box,
-// bounds_tag>
-//{
-// template <typename Distances>
-// static inline bool apply(
-// detail::unbounded<PointRelation> const&,
-// Distances const&)
-// {
-// return true;
-// }
-//};
-//
-//template <typename PointRelation, typename MinRelation, typename Box>
-//struct distances_predicates_check<
-// detail::min_bounded<PointRelation, MinRelation>,
-// Box,
-// bounds_tag>
-//{
-// template <typename Distances>
-// static inline bool apply(
-// detail::min_bounded<PointRelation, MinRelation> const& pred,
-// Distances const& d)
-// {
-// return pred.comparable_min
-// <= cdist_value<Distances>::template get<detail::to_furthest_tag>(d);
-// }
-//};
-//
-//template <typename PointRelation, typename MaxRelation, typename Box>
-//struct distances_predicates_check<
-// detail::max_bounded<PointRelation, MaxRelation>,
-// Box,
-// bounds_tag>
-//{
-// template <typename Distances>
-// static inline bool apply(
-// detail::max_bounded<PointRelation, MaxRelation> const& pred,
-// Distances const& d)
-// {
-// return cdist_value<Distances>::template get<detail::to_nearest_tag>(d)
-// <= pred.comparable_max;
-// }
-//};
-//
-//template <typename PointRelation, typename MinRelation, typename MaxRelation, typename Box>
-//struct distances_predicates_check<
-// detail::bounded<PointRelation, MinRelation, MaxRelation>,
-// Box,
-// bounds_tag>
-//{
-// template <typename Distances>
-// static inline bool apply(
-// detail::bounded<PointRelation, MinRelation, MaxRelation> const& pred,
-// Distances const& d)
-// {
-// return pred.comparable_min
-// <= cdist_value<Distances>::template get<detail::to_furthest_tag>(d)
-// && cdist_value<Distances>::template get<detail::to_nearest_tag>(d)
-// <= pred.comparable_max;
-// }
-//};
-
}}}} // namespace boost::geometry::index::detail
#endif // BOOST_GEOMETRY_INDEX_RTREE_DISTANCE_PREDICATES_HPP
Modified: trunk/boost/geometry/index/detail/predicates.hpp
==============================================================================
--- trunk/boost/geometry/index/detail/predicates.hpp (original)
+++ trunk/boost/geometry/index/detail/predicates.hpp 2013-05-09 14:01:25 EDT (Thu, 09 May 2013)
@@ -129,14 +129,25 @@
Geometry geometry;
};
-template <typename DistancePredicates>
+template <typename PointOrRelation>
struct nearest
{
- nearest(DistancePredicates const& dpred, unsigned k)
- : distance_predicates(dpred)
+ nearest(PointOrRelation const& por, unsigned k)
+ : point_or_relation(por)
+ , count(k)
+ {}
+ PointOrRelation point_or_relation;
+ unsigned count;
+};
+
+template <typename Linestring>
+struct path
+{
+ path(Linestring const& ls, unsigned k)
+ : linestring(ls)
, count(k)
{}
- DistancePredicates distance_predicates;
+ Linestring linestring;
unsigned count;
};
@@ -377,6 +388,16 @@
}
};
+template <typename Linestring>
+struct predicate_check<path<Linestring>, value_tag>
+{
+ template <typename Value, typename Box>
+ static inline bool apply(path<Linestring> const&, Value const&, Box const&)
+ {
+ return true;
+ }
+};
+
// ------------------------------------------------------------------ //
// predicate_check_default for bounds
// ------------------------------------------------------------------ //
@@ -571,6 +592,16 @@
}
};
+template <typename Linestring>
+struct predicate_check<path<Linestring>, bounds_tag>
+{
+ template <typename Value, typename Box>
+ static inline bool apply(path<Linestring> const&, Value const&, Box const&)
+ {
+ return true;
+ }
+};
+
// ------------------------------------------------------------------ //
// predicates_length
// ------------------------------------------------------------------ //
@@ -805,13 +836,19 @@
// predicates_is_nearest
template <typename P>
-struct predicates_is_nearest
+struct predicates_is_distance
{
static const unsigned value = 0;
};
template <typename DistancePredicates>
-struct predicates_is_nearest< nearest<DistancePredicates> >
+struct predicates_is_distance< nearest<DistancePredicates> >
+{
+ static const unsigned value = 1;
+};
+
+template <typename Linestring>
+struct predicates_is_distance< path<Linestring> >
{
static const unsigned value = 1;
};
@@ -819,46 +856,46 @@
// predicates_count_nearest
template <typename T>
-struct predicates_count_nearest
+struct predicates_count_distance
{
- static const unsigned value = predicates_is_nearest<T>::value;
+ static const unsigned value = predicates_is_distance<T>::value;
};
//template <typename F, typename S>
-//struct predicates_count_nearest< std::pair<F, S> >
+//struct predicates_count_distance< std::pair<F, S> >
//{
-// static const unsigned value = predicates_is_nearest<F>::value
-// + predicates_is_nearest<S>::value;
+// static const unsigned value = predicates_is_distance<F>::value
+// + predicates_is_distance<S>::value;
//};
template <typename Tuple, unsigned N>
-struct predicates_count_nearest_tuple
+struct predicates_count_distance_tuple
{
static const unsigned value =
- predicates_is_nearest<typename boost::tuples::element<N-1, Tuple>::type>::value
- + predicates_count_nearest_tuple<Tuple, N-1>::value;
+ predicates_is_distance<typename boost::tuples::element<N-1, Tuple>::type>::value
+ + predicates_count_distance_tuple<Tuple, N-1>::value;
};
template <typename Tuple>
-struct predicates_count_nearest_tuple<Tuple, 1>
+struct predicates_count_distance_tuple<Tuple, 1>
{
static const unsigned value =
- predicates_is_nearest<typename boost::tuples::element<0, Tuple>::type>::value;
+ predicates_is_distance<typename boost::tuples::element<0, Tuple>::type>::value;
};
//template <typename T0, typename T1, typename T2, typename T3, typename T4, typename T5, typename T6, typename T7, typename T8, typename T9>
-//struct predicates_count_nearest< boost::tuple<T0, T1, T2, T3, T4, T5, T6, T7, T8, T9> >
+//struct predicates_count_distance< boost::tuple<T0, T1, T2, T3, T4, T5, T6, T7, T8, T9> >
//{
-// static const unsigned value = predicates_count_nearest_tuple<
+// static const unsigned value = predicates_count_distance_tuple<
// boost::tuple<T0, T1, T2, T3, T4, T5, T6, T7, T8, T9>,
// boost::tuples::length< boost::tuple<T0, T1, T2, T3, T4, T5, T6, T7, T8, T9> >::value
// >::value;
//};
template <typename Head, typename Tail>
-struct predicates_count_nearest< boost::tuples::cons<Head, Tail> >
+struct predicates_count_distance< boost::tuples::cons<Head, Tail> >
{
- static const unsigned value = predicates_count_nearest_tuple<
+ static const unsigned value = predicates_count_distance_tuple<
boost::tuples::cons<Head, Tail>,
boost::tuples::length< boost::tuples::cons<Head, Tail> >::value
>::value;
@@ -867,50 +904,50 @@
// predicates_find_nearest
template <typename T>
-struct predicates_find_nearest
+struct predicates_find_distance
{
- static const unsigned value = predicates_is_nearest<T>::value ? 0 : 1;
+ static const unsigned value = predicates_is_distance<T>::value ? 0 : 1;
};
//template <typename F, typename S>
-//struct predicates_find_nearest< std::pair<F, S> >
+//struct predicates_find_distance< std::pair<F, S> >
//{
-// static const unsigned value = predicates_is_nearest<F>::value ? 0 :
-// (predicates_is_nearest<S>::value ? 1 : 2);
+// static const unsigned value = predicates_is_distance<F>::value ? 0 :
+// (predicates_is_distance<S>::value ? 1 : 2);
//};
template <typename Tuple, unsigned N>
-struct predicates_find_nearest_tuple
+struct predicates_find_distance_tuple
{
- static const bool is_found = predicates_find_nearest_tuple<Tuple, N-1>::is_found
- || predicates_is_nearest<typename boost::tuples::element<N-1, Tuple>::type>::value;
+ static const bool is_found = predicates_find_distance_tuple<Tuple, N-1>::is_found
+ || predicates_is_distance<typename boost::tuples::element<N-1, Tuple>::type>::value;
- static const unsigned value = predicates_find_nearest_tuple<Tuple, N-1>::is_found ?
- predicates_find_nearest_tuple<Tuple, N-1>::value :
- (predicates_is_nearest<typename boost::tuples::element<N-1, Tuple>::type>::value ?
+ static const unsigned value = predicates_find_distance_tuple<Tuple, N-1>::is_found ?
+ predicates_find_distance_tuple<Tuple, N-1>::value :
+ (predicates_is_distance<typename boost::tuples::element<N-1, Tuple>::type>::value ?
N-1 : boost::tuples::length<Tuple>::value);
};
template <typename Tuple>
-struct predicates_find_nearest_tuple<Tuple, 1>
+struct predicates_find_distance_tuple<Tuple, 1>
{
- static const bool is_found = predicates_is_nearest<typename boost::tuples::element<0, Tuple>::type>::value;
+ static const bool is_found = predicates_is_distance<typename boost::tuples::element<0, Tuple>::type>::value;
static const unsigned value = is_found ? 0 : boost::tuples::length<Tuple>::value;
};
//template <typename T0, typename T1, typename T2, typename T3, typename T4, typename T5, typename T6, typename T7, typename T8, typename T9>
-//struct predicates_find_nearest< boost::tuple<T0, T1, T2, T3, T4, T5, T6, T7, T8, T9> >
+//struct predicates_find_distance< boost::tuple<T0, T1, T2, T3, T4, T5, T6, T7, T8, T9> >
//{
-// static const unsigned value = predicates_find_nearest_tuple<
+// static const unsigned value = predicates_find_distance_tuple<
// boost::tuple<T0, T1, T2, T3, T4, T5, T6, T7, T8, T9>,
// boost::tuples::length< boost::tuple<T0, T1, T2, T3, T4, T5, T6, T7, T8, T9> >::value
// >::value;
//};
template <typename Head, typename Tail>
-struct predicates_find_nearest< boost::tuples::cons<Head, Tail> >
+struct predicates_find_distance< boost::tuples::cons<Head, Tail> >
{
- static const unsigned value = predicates_find_nearest_tuple<
+ static const unsigned value = predicates_find_distance_tuple<
boost::tuples::cons<Head, Tail>,
boost::tuples::length< boost::tuples::cons<Head, Tail> >::value
>::value;
Modified: trunk/boost/geometry/index/detail/rtree/query_iterators.hpp
==============================================================================
--- trunk/boost/geometry/index/detail/rtree/query_iterators.hpp (original)
+++ trunk/boost/geometry/index/detail/rtree/query_iterators.hpp 2013-05-09 14:01:25 EDT (Thu, 09 May 2013)
@@ -143,9 +143,9 @@
};
template <typename Value, typename Options, typename Translator, typename Box, typename Allocators, typename Predicates, unsigned NearestPredicateIndex>
-class nearest_query_iterator
+class distance_query_iterator
{
- typedef visitors::nearest_query_incremental<Value, Options, Translator, Box, Allocators, Predicates, NearestPredicateIndex> visitor_type;
+ typedef visitors::distance_query_incremental<Value, Options, Translator, Box, Allocators, Predicates, NearestPredicateIndex> visitor_type;
typedef typename visitor_type::node_pointer node_pointer;
public:
@@ -155,11 +155,11 @@
typedef typename Allocators::difference_type difference_type;
typedef typename Allocators::const_pointer pointer;
- inline nearest_query_iterator(Translator const& t, Predicates const& p)
+ inline distance_query_iterator(Translator const& t, Predicates const& p)
: m_visitor(t, p)
{}
- inline nearest_query_iterator(node_pointer root, Translator const& t, Predicates const& p)
+ inline distance_query_iterator(node_pointer root, Translator const& t, Predicates const& p)
: m_visitor(t, p)
{
detail::rtree::apply_visitor(m_visitor, *root);
@@ -176,45 +176,45 @@
return boost::addressof(m_visitor.dereference());
}
- nearest_query_iterator & operator++()
+ distance_query_iterator & operator++()
{
m_visitor.increment();
return *this;
}
- nearest_query_iterator operator++(int)
+ distance_query_iterator operator++(int)
{
- nearest_query_iterator temp = *this;
+ distance_query_iterator temp = *this;
this->operator++();
return temp;
}
- friend bool operator==(nearest_query_iterator const& l, nearest_query_iterator const& r)
+ friend bool operator==(distance_query_iterator const& l, distance_query_iterator const& r)
{
return l.m_visitor == r.m_visitor;
}
- friend bool operator==(nearest_query_iterator const& l, end_query_iterator<Value, Allocators>)
+ friend bool operator==(distance_query_iterator const& l, end_query_iterator<Value, Allocators>)
{
return l.m_visitor.is_end();
}
- friend bool operator==(end_query_iterator<Value, Allocators>, nearest_query_iterator const& r)
+ friend bool operator==(end_query_iterator<Value, Allocators>, distance_query_iterator const& r)
{
return r.m_visitor.is_end();
}
- friend bool operator!=(nearest_query_iterator const& l, nearest_query_iterator const& r)
+ friend bool operator!=(distance_query_iterator const& l, distance_query_iterator const& r)
{
return !(l.m_visitor == r.m_visitor);
}
- friend bool operator!=(nearest_query_iterator const& l, end_query_iterator<Value, Allocators>)
+ friend bool operator!=(distance_query_iterator const& l, end_query_iterator<Value, Allocators>)
{
return !l.m_visitor.is_end();
}
- friend bool operator!=(end_query_iterator<Value, Allocators>, nearest_query_iterator const& r)
+ friend bool operator!=(end_query_iterator<Value, Allocators>, distance_query_iterator const& r)
{
return !r.m_visitor.is_end();
}
Modified: trunk/boost/geometry/index/detail/rtree/visitors/nearest_query.hpp
==============================================================================
--- trunk/boost/geometry/index/detail/rtree/visitors/nearest_query.hpp (original)
+++ trunk/boost/geometry/index/detail/rtree/visitors/nearest_query.hpp 2013-05-09 14:01:25 EDT (Thu, 09 May 2013)
@@ -15,63 +15,13 @@
namespace detail { namespace rtree { namespace visitors {
-// TODO: awulkiew - maybe it's a good idea to check if curr_mindist < comp_mindist and then check predicates
-// in store() or divide store() into 2 functions e.g. should_store() and store()
-// - well not with this algorithm of storing k-th neighbor
-
-//template <typename Value, typename Translator, typename Point>
-//struct nearest_query_result_one
-//{
-//public:
-// typedef typename geometry::default_distance_result<
-// Point,
-// typename translator::indexable_type<Translator>::type
-// >::type distance_type;
-//
-// inline nearest_query_result_one(Value & value)
-// : m_value(value)
-// , m_comp_dist((std::numeric_limits<distance_type>::max)())
-// {}
-//
-// inline void store(Value const& val, distance_type const& curr_comp_dist)
-// {
-// if ( curr_comp_dist < m_comp_dist )
-// {
-// m_comp_dist = curr_comp_dist;
-// m_value = val;
-// }
-// }
-//
-// inline bool is_comparable_distance_valid() const
-// {
-// return m_comp_dist < (std::numeric_limits<distance_type>::max)();
-// }
-//
-// inline distance_type comparable_distance() const
-// {
-// return m_comp_dist;
-// }
-//
-// inline size_t finish()
-// {
-// return is_comparable_distance_valid() ? 1 : 0;
-// }
-//
-//private:
-// Value & m_value;
-// distance_type m_comp_dist;
-//};
-
-template <typename Value, typename Translator, typename Point, typename OutIt>
-class nearest_query_result_k
+template <typename Value, typename Translator, typename DistanceType, typename OutIt>
+class distance_query_result
{
public:
- typedef typename geometry::default_distance_result<
- Point,
- typename indexable_type<Translator>::type
- >::type distance_type;
+ typedef DistanceType distance_type;
- inline explicit nearest_query_result_k(size_t k, OutIt out_it)
+ inline explicit distance_query_result(size_t k, OutIt out_it)
: m_count(k), m_out_it(out_it)
{
BOOST_GEOMETRY_INDEX_ASSERT(0 < m_count, "Number of neighbors should be greater than 0");
@@ -146,10 +96,10 @@
typename Box,
typename Allocators,
typename Predicates,
- unsigned NearestPredicateIndex,
- typename Result
+ unsigned DistancePredicateIndex,
+ typename OutIter
>
-class nearest_query
+class distance_query
: public rtree::visitor<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag, true>::type
{
public:
@@ -159,31 +109,21 @@
typedef typename rtree::internal_node<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type internal_node;
typedef typename rtree::leaf<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type leaf;
- typedef index::detail::predicates_element<NearestPredicateIndex, Predicates> nearest_predicate_access;
- typedef typename index::detail::distance_predicates_type<typename nearest_predicate_access::type>::type distance_predicates_type;
-
- typedef index::detail::distances_calc<distance_predicates_type, Box, index::detail::bounds_tag> node_distances_calc;
- typedef typename node_distances_calc::result_type node_distances_type;
- typedef index::detail::distances_predicates_check<distance_predicates_type, Box, index::detail::bounds_tag> node_distances_predicates_check;
-
- typedef index::detail::distances_calc<
- distance_predicates_type,
- typename indexable_type<Translator>::type,
- index::detail::value_tag
- > value_distances_calc;
- typedef typename value_distances_calc::result_type value_distances_type;
- typedef index::detail::distances_predicates_check<
- distance_predicates_type,
- typename indexable_type<Translator>::type,
- index::detail::value_tag
- > value_distances_predicates_check;
+ typedef index::detail::predicates_element<DistancePredicateIndex, Predicates> nearest_predicate_access;
+ typedef typename nearest_predicate_access::type nearest_predicate_type;
+ typedef typename indexable_type<Translator>::type indexable_type;
+
+ typedef index::detail::calculate_distance<nearest_predicate_type, indexable_type, value_tag> calculate_value_distance;
+ typedef index::detail::calculate_distance<nearest_predicate_type, Box, bounds_tag> calculate_node_distance;
+ typedef typename calculate_value_distance::result_type value_distance_type;
+ typedef typename calculate_node_distance::result_type node_distance_type;
static const unsigned predicates_len = index::detail::predicates_length<Predicates>::value;
- inline nearest_query(parameters_type const& parameters, Translator const& translator, Predicates const& pred, Result & r)
+ inline distance_query(parameters_type const& parameters, Translator const& translator, Predicates const& pred, OutIter out_it)
: m_parameters(parameters), m_translator(translator)
, m_pred(pred)
- , m_result(r)
+ , m_result(nearest_predicate_access::get(m_pred).count, out_it)
{}
inline void operator()(internal_node const& n)
@@ -193,7 +133,7 @@
// array of active nodes
typedef typename index::detail::rtree::container_from_elements_type<
elements_type,
- std::pair<node_distances_type, typename Allocators::node_pointer>
+ std::pair<node_distance_type, typename Allocators::node_pointer>
>::type active_branch_list_type;
active_branch_list_type active_branch_list;
@@ -210,25 +150,22 @@
if ( index::detail::predicates_check<index::detail::bounds_tag, 0, predicates_len>(m_pred, 0, it->first) )
{
// calculate node's distance(s) for distance predicate
- node_distances_type node_dist_data = node_distances_calc::apply(dist_pred(), it->first);
-
- // TODO: awulkiew - consider at first calculating near distance only,
- // comparing it with m_result.comparable_distance if it's valid,
- // after that calculate the rest of distances and check predicates
+ node_distance_type node_distance;
+ // if distance isn't ok - move to the next node
+ if ( !calculate_node_distance::apply(predicate(), it->first, node_distance) )
+ {
+ continue;
+ }
// if current node is further than found neighbors - don't analyze it
if ( m_result.has_enough_neighbors() &&
- is_node_prunable(m_result.greatest_comparable_distance(), node_dist_data) )
+ is_node_prunable(m_result.greatest_comparable_distance(), node_distance) )
{
continue;
}
- // if current node distance(s) meets distance predicate
- if ( node_distances_predicates_check::apply(dist_pred(), node_dist_data) )
- {
- // add current node's data into the list
- active_branch_list.push_back( std::make_pair(node_dist_data, it->second) );
- }
+ // add current node's data into the list
+ active_branch_list.push_back( std::make_pair(node_distance, it->second) );
}
}
@@ -265,57 +202,46 @@
if ( index::detail::predicates_check<index::detail::value_tag, 0, predicates_len>(m_pred, *it, m_translator(*it)) )
{
// calculate values distance for distance predicate
- value_distances_type distances = value_distances_calc::apply(dist_pred(), m_translator(*it));
-
- // TODO: awulkiew - consider at first calculating point relation distance only,
- // comparing it with m_result.comparable_distance if it's valid,
- // after that calculate the rest of distances and check predicates
-
- // if distance meets distance predicate
- if ( value_distances_predicates_check::apply(dist_pred(), distances) )
+ value_distance_type value_distance;
+ // if distance is ok
+ if ( calculate_value_distance::apply(predicate(), m_translator(*it), value_distance) )
{
- typedef typename index::detail::point_relation<distance_predicates_type>::type point_relation_type;
- typedef typename index::detail::relation<point_relation_type>::tag point_relation_tag;
-
// store value
- m_result.store(
- *it,
- index::detail::cdist_value<value_distances_type>
- ::template get<point_relation_tag>(distances)
- );
+ m_result.store(*it, value_distance);
}
}
}
}
+ inline size_t finish()
+ {
+ return m_result.finish();
+ }
+
private:
static inline bool abl_less(
- std::pair<node_distances_type, typename Allocators::node_pointer> const& p1,
- std::pair<node_distances_type, typename Allocators::node_pointer> const& p2)
+ std::pair<node_distance_type, typename Allocators::node_pointer> const& p1,
+ std::pair<node_distance_type, typename Allocators::node_pointer> const& p2)
{
- return index::detail::cdist_value<node_distances_type>
- ::template get<index::detail::to_nearest_tag>(p1.first)
- < index::detail::cdist_value<node_distances_type>
- ::template get<index::detail::to_nearest_tag>(p2.first);
+ return p1.first < p2.first;
}
template <typename Distance>
- static inline bool is_node_prunable(Distance const& greatest_dist, node_distances_type const& d)
+ static inline bool is_node_prunable(Distance const& greatest_dist, node_distance_type const& d)
{
- return greatest_dist <= index::detail::cdist_value<node_distances_type>
- ::template get<index::detail::to_nearest_tag>(d);
+ return greatest_dist <= d;
}
- inline distance_predicates_type const& dist_pred() const
+ nearest_predicate_type const& predicate() const
{
- return nearest_predicate_access::get(m_pred).distance_predicates;
+ return nearest_predicate_access::get(m_pred);
}
parameters_type const& m_parameters;
Translator const& m_translator;
Predicates m_pred;
- Result & m_result;
+ distance_query_result<Value, Translator, value_distance_type, OutIter> m_result;
};
template <
@@ -325,9 +251,9 @@
typename Box,
typename Allocators,
typename Predicates,
- unsigned NearestPredicateIndex
+ unsigned DistancePredicateIndex
>
-class nearest_query_incremental
+class distance_query_incremental
: public rtree::visitor<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag, true>::type
{
public:
@@ -337,31 +263,14 @@
typedef typename rtree::internal_node<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type internal_node;
typedef typename rtree::leaf<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type leaf;
- typedef index::detail::predicates_element<NearestPredicateIndex, Predicates> nearest_predicate_access;
- typedef typename index::detail::distance_predicates_type<typename nearest_predicate_access::type>::type distance_predicates_type;
- typedef typename geometry::default_distance_result<
- typename index::detail::relation<
- typename index::detail::point_relation<distance_predicates_type>::type
- >::value_type,
- typename indexable_type<Translator>::type
- >::type value_distance_type;
-
- typedef index::detail::distances_calc<distance_predicates_type, Box, index::detail::bounds_tag> node_distances_calc;
- typedef typename node_distances_calc::result_type node_distances_type;
- typedef index::detail::distances_predicates_check<distance_predicates_type, Box, index::detail::bounds_tag> node_distances_predicates_check;
- typedef typename index::detail::cdist_value<node_distances_type>::type node_distance_type;
-
- typedef index::detail::distances_calc<
- distance_predicates_type,
- typename indexable_type<Translator>::type,
- index::detail::value_tag
- > value_distances_calc;
- typedef typename value_distances_calc::result_type value_distances_type;
- typedef index::detail::distances_predicates_check<
- distance_predicates_type,
- typename indexable_type<Translator>::type,
- index::detail::value_tag
- > value_distances_predicates_check;
+ typedef index::detail::predicates_element<DistancePredicateIndex, Predicates> nearest_predicate_access;
+ typedef typename nearest_predicate_access::type nearest_predicate_type;
+ typedef typename indexable_type<Translator>::type indexable_type;
+
+ typedef index::detail::calculate_distance<nearest_predicate_type, indexable_type, value_tag> calculate_value_distance;
+ typedef index::detail::calculate_distance<nearest_predicate_type, Box, bounds_tag> calculate_node_distance;
+ typedef typename calculate_value_distance::result_type value_distance_type;
+ typedef typename calculate_node_distance::result_type node_distance_type;
typedef typename Allocators::size_type size_type;
typedef typename Allocators::const_reference const_reference;
@@ -373,7 +282,7 @@
typedef typename internal_elements::const_iterator internal_iterator;
typedef typename rtree::elements_type<leaf>::type leaf_elements;
- typedef std::pair<node_distances_type, node_pointer> branch_data;
+ typedef std::pair<node_distance_type, node_pointer> branch_data;
typedef typename index::detail::rtree::container_from_elements_type<
internal_elements, branch_data
>::type active_branch_list_type;
@@ -394,7 +303,7 @@
};
typedef std::vector<internal_stack_element> internal_stack_type;
- inline nearest_query_incremental(Translator const& translator, Predicates const& pred)
+ inline distance_query_incremental(Translator const& translator, Predicates const& pred)
: m_translator(::boost::addressof(translator))
, m_pred(pred)
, current_neighbor((std::numeric_limits<size_type>::max)())
@@ -475,7 +384,7 @@
return (std::numeric_limits<size_type>::max)() == current_neighbor;
}
- friend bool operator==(nearest_query_incremental const& l, nearest_query_incremental const& r)
+ friend bool operator==(distance_query_incremental const& l, distance_query_incremental const& r)
{
BOOST_ASSERT_MSG(l.current_neighbor != r.current_neighbor ||
(std::numeric_limits<size_type>::max)() == l.current_neighbor ||
@@ -503,21 +412,22 @@
if ( index::detail::predicates_check<index::detail::bounds_tag, 0, predicates_len>(m_pred, 0, it->first) )
{
// calculate node's distance(s) for distance predicate
- node_distances_type node_dist_data = node_distances_calc::apply(dist_pred(), it->first);
+ node_distance_type node_distance;
+ // if distance isn't ok - move to the next node
+ if ( !calculate_node_distance::apply(predicate(), it->first, node_distance) )
+ {
+ continue;
+ }
// if current node is further than found neighbors - don't analyze it
if ( max_count() <= neighbors.size() &&
- is_node_prunable(neighbors.back().first, node_dist_data) )
+ is_node_prunable(neighbors.back().first, node_distance) )
{
continue;
}
- // if current node distance(s) meets distance predicate
- if ( node_distances_predicates_check::apply(dist_pred(), node_dist_data) )
- {
- // add current node's data into the list
- internal_stack.back().branches.push_back( std::make_pair(node_dist_data, it->second) );
- }
+ // add current node's data into the list
+ internal_stack.back().branches.push_back( std::make_pair(node_distance, it->second) );
}
}
@@ -547,22 +457,14 @@
if ( index::detail::predicates_check<index::detail::value_tag, 0, predicates_len>(m_pred, *it, (*m_translator)(*it)) )
{
// calculate values distance for distance predicate
- value_distances_type distances = value_distances_calc::apply(dist_pred(), (*m_translator)(*it));
-
- // if distance meets distance predicate
- if ( value_distances_predicates_check::apply(dist_pred(), distances) )
+ value_distance_type value_distance;
+ // if distance is ok
+ if ( calculate_value_distance::apply(predicate(), (*m_translator)(*it), value_distance) )
{
- typedef typename index::detail::point_relation<distance_predicates_type>::type point_relation_type;
- typedef typename index::detail::relation<point_relation_type>::tag point_relation_tag;
-
- // store value if it's closer than the furthest neighbour
- value_distance_type dist = index::detail::cdist_value<value_distances_type>
- ::template get<point_relation_tag>(distances);
-
// if there is not enough values or current value is closer than furthest neighbour
- if ( not_enough_neighbors || dist < greatest_distance )
+ if ( not_enough_neighbors || value_distance < greatest_distance )
{
- neighbors.push_back(std::make_pair(dist, boost::addressof(*it)));
+ neighbors.push_back(std::make_pair(value_distance, boost::addressof(*it)));
}
}
}
@@ -576,11 +478,10 @@
}
private:
- static inline bool abl_less(std::pair<node_distances_type, typename Allocators::node_pointer> const& p1,
- std::pair<node_distances_type, typename Allocators::node_pointer> const& p2)
+ static inline bool abl_less(std::pair<node_distance_type, typename Allocators::node_pointer> const& p1,
+ std::pair<node_distance_type, typename Allocators::node_pointer> const& p2)
{
- return index::detail::cdist_value<node_distances_type>::template get<index::detail::to_nearest_tag>(p1.first)
- < index::detail::cdist_value<node_distances_type>::template get<index::detail::to_nearest_tag>(p2.first);
+ return p1.first < p2.first;
}
static inline bool neighbors_less(std::pair<value_distance_type, const Value *> const& p1,
@@ -599,8 +500,7 @@
if ( first->branches.size() <= first->current_branch )
continue;
- node_distance_type curr_dist = index::detail::cdist_value<node_distances_type>
- ::template get<index::detail::to_nearest_tag>(first->branches[first->current_branch].first);
+ node_distance_type curr_dist = first->branches[first->current_branch].first;
if ( curr_dist < result )
result = curr_dist;
}
@@ -608,20 +508,19 @@
}
template <typename Distance>
- static inline bool is_node_prunable(Distance const& greatest_dist, node_distances_type const& d)
+ static inline bool is_node_prunable(Distance const& greatest_dist, node_distance_type const& d)
{
- return greatest_dist <= index::detail::cdist_value<node_distances_type>
- ::template get<index::detail::to_nearest_tag>(d);
+ return greatest_dist <= d;
}
- inline distance_predicates_type const& dist_pred() const
+ inline unsigned max_count() const
{
- return nearest_predicate_access::get(m_pred).distance_predicates;
+ return nearest_predicate_access::get(m_pred).count;
}
- inline unsigned max_count() const
+ nearest_predicate_type const& predicate() const
{
- return nearest_predicate_access::get(m_pred).count;
+ return nearest_predicate_access::get(m_pred);
}
const Translator * m_translator;
Modified: trunk/boost/geometry/index/predicates.hpp
==============================================================================
--- trunk/boost/geometry/index/predicates.hpp (original)
+++ trunk/boost/geometry/index/predicates.hpp 2013-05-09 14:01:25 EDT (Thu, 09 May 2013)
@@ -211,8 +211,8 @@
\brief Generate nearest() predicate.
When nearest predicate is passed to the query, k-nearest neighbour search will be performed.
-
-The simplest way of defining the knn query is passing a \c Point to which \c Values must be closest.
+\c nearest() predicate takes a \c Point from which distance to \c Values is calculated
+and the maximum number of \c Values that should be returned.
\par Example
\verbatim
@@ -235,6 +235,38 @@
return detail::nearest<Point>(point, k);
}
+#ifdef BOOST_GEOMETRY_INDEX_DETAIL_EXPERIMENTAL
+
+/*!
+\brief Generate path() predicate.
+
+When path predicate is passed to the query, the returned values are k values on the path closest to
+its begin. \c path() predicate takes a \c Linestring defining the path and the maximum
+number of \c Values that should be returned.
+
+\par Example
+\verbatim
+bgi::query(spatial_index, bgi::path(pt, 5), std::back_inserter(result));
+bgi::query(spatial_index, bgi::path(pt, 5) && bgi::intersects(box), std::back_inserter(result));
+\endverbatim
+
+\warning
+Only one distance predicate (\c nearest() or \c path()) may be used in a query.
+
+\ingroup predicates
+
+\param point The point from which distance is calculated.
+\param k The maximum number of values to return.
+*/
+template <typename Linestring> inline
+detail::path<Linestring>
+path(Linestring const& linestring, unsigned k)
+{
+ return detail::path<Linestring>(linestring, k);
+}
+
+#endif // BOOST_GEOMETRY_INDEX_DETAIL_EXPERIMENTAL
+
namespace detail {
// operator! generators
Modified: trunk/boost/geometry/index/rtree.hpp
==============================================================================
--- trunk/boost/geometry/index/rtree.hpp (original)
+++ trunk/boost/geometry/index/rtree.hpp 2013-05-09 14:01:25 EDT (Thu, 09 May 2013)
@@ -733,11 +733,11 @@
if ( !m_members.root )
return 0;
- static const unsigned nearest_count = detail::predicates_count_nearest<Predicates>::value;
- static const bool is_nearest = 0 < nearest_count;
- BOOST_MPL_ASSERT_MSG((nearest_count <= 1), PASS_ONLY_ONE_NEAREST_PREDICATE, (Predicates));
+ static const unsigned distance_predicates_count = detail::predicates_count_distance<Predicates>::value;
+ static const bool is_distance_predicate = 0 < distance_predicates_count;
+ BOOST_MPL_ASSERT_MSG((distance_predicates_count <= 1), PASS_ONLY_ONE_DISTANCE_PREDICATE, (Predicates));
- return query_dispatch(predicates, out_it, boost::mpl::bool_<is_nearest>());
+ return query_dispatch(predicates, out_it, boost::mpl::bool_<is_distance_predicate>());
}
#ifdef BOOST_GEOMETRY_INDEX_DETAIL_EXPERIMENTAL
@@ -762,24 +762,24 @@
template <typename Predicates>
typename boost::mpl::if_c<
- detail::predicates_count_nearest<Predicates>::value == 0,
+ detail::predicates_count_distance<Predicates>::value == 0,
detail::rtree::spatial_query_iterator<value_type, options_type, translator_type, box_type, allocators_type, Predicates>,
- detail::rtree::nearest_query_iterator<
+ detail::rtree::distance_query_iterator<
value_type, options_type, translator_type, box_type, allocators_type, Predicates,
- detail::predicates_find_nearest<Predicates>::value
+ detail::predicates_find_distance<Predicates>::value
>
>::type
qbegin(Predicates const& predicates) const
{
- static const unsigned nearest_count = detail::predicates_count_nearest<Predicates>::value;
- BOOST_MPL_ASSERT_MSG((nearest_count <= 1), PASS_ONLY_ONE_NEAREST_PREDICATE, (Predicates));
+ static const unsigned distance_predicates_count = detail::predicates_count_distance<Predicates>::value;
+ BOOST_MPL_ASSERT_MSG((distance_predicates_count <= 1), PASS_ONLY_ONE_DISTANCE_PREDICATE, (Predicates));
typedef typename boost::mpl::if_c<
- detail::predicates_count_nearest<Predicates>::value == 0,
+ detail::predicates_count_distance<Predicates>::value == 0,
detail::rtree::spatial_query_iterator<value_type, options_type, translator_type, box_type, allocators_type, Predicates>,
- detail::rtree::nearest_query_iterator<
+ detail::rtree::distance_query_iterator<
value_type, options_type, translator_type, box_type, allocators_type, Predicates,
- detail::predicates_find_nearest<Predicates>::value
+ detail::predicates_find_distance<Predicates>::value
>
>::type iterator_type;
@@ -791,24 +791,24 @@
template <typename Predicates>
typename boost::mpl::if_c<
- detail::predicates_count_nearest<Predicates>::value == 0,
+ detail::predicates_count_distance<Predicates>::value == 0,
detail::rtree::spatial_query_iterator<value_type, options_type, translator_type, box_type, allocators_type, Predicates>,
- detail::rtree::nearest_query_iterator<
+ detail::rtree::distance_query_iterator<
value_type, options_type, translator_type, box_type, allocators_type, Predicates,
- detail::predicates_find_nearest<Predicates>::value
+ detail::predicates_find_distance<Predicates>::value
>
>::type
qend(Predicates const& predicates) const
{
- static const unsigned nearest_count = detail::predicates_count_nearest<Predicates>::value;
- BOOST_MPL_ASSERT_MSG((nearest_count <= 1), PASS_ONLY_ONE_NEAREST_PREDICATE, (Predicates));
+ static const unsigned distance_predicates_count = detail::predicates_count_distance<Predicates>::value;
+ BOOST_MPL_ASSERT_MSG((distance_predicates_count <= 1), PASS_ONLY_ONE_DISTANCE_PREDICATE, (Predicates));
typedef typename boost::mpl::if_c<
- detail::predicates_count_nearest<Predicates>::value == 0,
+ detail::predicates_count_distance<Predicates>::value == 0,
detail::rtree::spatial_query_iterator<value_type, options_type, translator_type, box_type, allocators_type, Predicates>,
- detail::rtree::nearest_query_iterator<
+ detail::rtree::distance_query_iterator<
value_type, options_type, translator_type, box_type, allocators_type, Predicates,
- detail::predicates_find_nearest<Predicates>::value
+ detail::predicates_find_distance<Predicates>::value
>
>::type iterator_type;
@@ -1182,7 +1182,7 @@
strong
*/
template <typename Predicates, typename OutIter>
- size_type query_dispatch(Predicates const& predicates, OutIter out_it, boost::mpl::bool_<false> const& /*is_nearest*/) const
+ size_type query_dispatch(Predicates const& predicates, OutIter out_it, boost::mpl::bool_<false> const& /*is_distance_predicate*/) const
{
detail::rtree::visitors::spatial_query<value_type, options_type, translator_type, box_type, allocators_type, Predicates, OutIter>
find_v(m_members.translator(), predicates, out_it);
@@ -1199,37 +1199,23 @@
strong
*/
template <typename Predicates, typename OutIter>
- size_type query_dispatch(Predicates const& predicates, OutIter out_it, boost::mpl::bool_<true> const& /*is_nearest*/) const
+ size_type query_dispatch(Predicates const& predicates, OutIter out_it, boost::mpl::bool_<true> const& /*is_distance_predicate*/) const
{
- static const unsigned nearest_index = detail::predicates_find_nearest<Predicates>::value;
- typedef index::detail::predicates_element<nearest_index, Predicates> nearest_predicate_access;
- typedef typename index::detail::distance_predicates_type<typename nearest_predicate_access::type >::type distance_predicates_type;
- typedef typename detail::point_relation<distance_predicates_type>::type point_relation;
- typedef typename detail::relation<point_relation>::value_type point_type;
-
- typedef detail::rtree::visitors::nearest_query_result_k<
- value_type,
- translator_type,
- point_type,
- OutIter
- > result_type;
-
- result_type result(nearest_predicate_access::get(predicates).count, out_it);
-
- detail::rtree::visitors::nearest_query<
+ static const unsigned distance_predicate_index = detail::predicates_find_distance<Predicates>::value;
+ detail::rtree::visitors::distance_query<
value_type,
options_type,
translator_type,
box_type,
allocators_type,
Predicates,
- nearest_index,
- result_type
- > nearest_v(m_members.parameters(), m_members.translator(), predicates, result);
+ distance_predicate_index,
+ OutIter
+ > distance_v(m_members.parameters(), m_members.translator(), predicates, out_it);
- detail::rtree::apply_visitor(nearest_v, *m_members.root);
+ detail::rtree::apply_visitor(distance_v, *m_members.root);
- return result.finish();
+ return distance_v.finish();
}
struct members_holder