|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r74593 - in sandbox-branches/geometry/index: boost/geometry/extensions/index boost/geometry/extensions/index/rtree boost/geometry/extensions/index/rtree/visitors tests
From: adam.wulkiewicz_at_[hidden]
Date: 2011-09-27 15:31:03
Author: awulkiew
Date: 2011-09-27 15:31:01 EDT (Tue, 27 Sep 2011)
New Revision: 74593
URL: http://svn.boost.org/trac/boost/changeset/74593
Log:
Distances predicates version 2 implemented. Now the user may use different predicates for knn point, min and max distances.
Added:
sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/tags.hpp (contents, props changed)
sandbox-branches/geometry/index/boost/geometry/extensions/index/tuples.hpp (contents, props changed)
Text files modified:
sandbox-branches/geometry/index/boost/geometry/extensions/index/distance_predicates.hpp | 729 ++++++++++++++++++++++++++++-----------
sandbox-branches/geometry/index/boost/geometry/extensions/index/predicates.hpp | 11
sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/distance_predicates.hpp | 356 +++++++------------
sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/predicates.hpp | 34 -
sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/rtree.hpp | 22
sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/nearest.hpp | 67 ++-
sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/query.hpp | 4
sandbox-branches/geometry/index/tests/additional_glut_vis.cpp | 9
sandbox-branches/geometry/index/tests/main.cpp | 2
sandbox-branches/geometry/index/tests/rtree_function.hpp | 4
10 files changed, 748 insertions(+), 490 deletions(-)
Modified: sandbox-branches/geometry/index/boost/geometry/extensions/index/distance_predicates.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/extensions/index/distance_predicates.hpp (original)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/distance_predicates.hpp 2011-09-27 15:31:01 EDT (Tue, 27 Sep 2011)
@@ -14,9 +14,9 @@
#include <boost/geometry/extensions/index/algorithms/comparable_distance_far.hpp>
#include <boost/geometry/extensions/index/algorithms/comparable_distance_centroid.hpp>
-namespace boost { namespace geometry { namespace index {
+#include <boost/geometry/extensions/index/tuples.hpp>
-namespace detail {
+namespace boost { namespace geometry { namespace index {
//TODO: awulkiew - consider storing values instead of const references
// it may be faster and it eliminates problems with storing of references to temporaries
@@ -27,351 +27,672 @@
// what if objects are in different systems?
// should index algorithms work exactly like comparable_distance or not?
-// data
+namespace detail {
+
+// relations
+
+template <typename T>
+struct near
+{
+ near(T const& v) : value(v) {}
+ T value;
+};
+
+template <typename T>
+struct centroid
+{
+ centroid(T const& v) : value(v) {}
+ T value;
+};
+
+template <typename T>
+struct far
+{
+ far(T const& v) : value(v) {}
+ T value;
+};
+
+// tags
+
+struct near_tag {};
+struct centroid_tag {};
+struct far_tag {};
+
+// relation
+
+template <typename T>
+struct relation
+{
+ typedef T value_type;
+ typedef near_tag tag;
+ static inline T const& value(T const& v) { return v; }
+ static inline T & value(T & v) { return v; }
+};
+
+template <typename T>
+struct relation< near<T> >
+{
+ typedef T value_type;
+ typedef near_tag tag;
+ static inline T const& value(near<T> const& r) { return r.value; }
+ static inline T & value(near<T> & r) { return r.value; }
+};
+
+template <typename T>
+struct relation< centroid<T> >
+{
+ typedef T value_type;
+ typedef centroid_tag tag;
+ static inline T const& value(centroid<T> const& r) { return r.value; }
+ static inline T & value(centroid<T> & r) { return r.value; }
+};
+
+template <typename T>
+struct relation< far<T> >
+{
+ typedef T value_type;
+ typedef far_tag tag;
+ static inline T const& value(far<T> const& r) { return r.value; }
+ static inline T & value(far<T> & r) { return r.value; }
+};
+
+} // namespace detail
+
+// relations generators
+
+template <typename T>
+detail::near<T> near(T const& v)
+{
+ return detail::near<T>(v);
+}
+
+template <typename T>
+detail::centroid<T> centroid(T const& v)
+{
+ return detail::centroid<T>(v);
+}
+
+template <typename T>
+detail::far<T> far(T const& v)
+{
+ return detail::far<T>(v);
+}
+
+// distance predicates
-struct distance_near_tag {};
-struct distance_far_tag {};
-struct distance_centroid_tag {};
+namespace detail {
+
+template <typename PointRelation>
+struct unbounded
+ : nonassignable
+{
+ inline explicit unbounded(PointRelation const& pr)
+ : point_relation(pr)
+ {}
-struct distance_min_tag {};
-struct distance_max_tag {};
+ PointRelation point_relation;
+};
-template <typename Point, typename Tag>
-struct distance_unbounded
+template <typename PointRelation, typename MinRelation>
+struct min_bounded
: nonassignable
{
- typedef typename index::traits::coordinate_type<Point>::type coordinate_type;
+ typedef typename detail::relation<PointRelation>::value_type point_type;
+ typedef typename geometry::default_distance_result<point_type, point_type>::type distance_type;
- inline explicit distance_unbounded(Point const& p)
- : point(p)
+ 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) )
{}
- Point const& point;
+ PointRelation point_relation;
+ distance_type comparable_min;
};
-template <typename Point, typename Tag, typename LimitTag>
-struct distance_half_bounded
+template <typename PointRelation, typename MaxRelation>
+struct max_bounded
: nonassignable
{
- typedef typename index::traits::coordinate_type<Point>::type coordinate_type;
- typedef typename geometry::default_distance_result<Point, Point>::type distance_type;
+ typedef typename detail::relation<PointRelation>::value_type point_type;
+ typedef typename geometry::default_distance_result<point_type, point_type>::type distance_type;
- inline explicit distance_half_bounded(Point const& p, coordinate_type const& distance_limit)
- : point(p)
- , comparable_limit(distance_limit * distance_limit)
+ 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) )
{}
- Point const& point;
- distance_type comparable_limit;
+ PointRelation point_relation;
+ distance_type comparable_max;
};
-template <typename Point, typename Tag>
-struct distance_bounded
+template <typename PointRelation, typename MinRelation, typename MaxRelation>
+struct bounded
: nonassignable
{
- typedef typename index::traits::coordinate_type<Point>::type coordinate_type;
- typedef typename geometry::default_distance_result<Point, Point>::type distance_type;
+ typedef typename detail::relation<PointRelation>::value_type point_type;
+ typedef typename geometry::default_distance_result<point_type, point_type>::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)
+ 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) )
{}
- Point const& point;
+ PointRelation point_relation;
distance_type comparable_min;
distance_type comparable_max;
};
} // namespace detail
-// generators
+// distance predicates generators
-template <typename Point>
-inline detail::distance_unbounded<Point, detail::distance_near_tag>
-distance_near(Point const& p)
+template <typename PointRelation>
+inline detail::unbounded<PointRelation>
+unbounded(PointRelation const& pr)
{
- return detail::distance_unbounded<Point, detail::distance_near_tag>(p);
+ return detail::unbounded<PointRelation>(pr);
}
-template <typename Point>
-inline detail::distance_unbounded<Point, detail::distance_far_tag>
-distance_far(Point const& p)
+template <typename PointRelation, typename MinRelation>
+inline detail::min_bounded<PointRelation, MinRelation>
+min_bounded(PointRelation const& pr, MinRelation const& minr)
{
- return detail::distance_unbounded<Point, detail::distance_far_tag>(p);
+ return detail::min_bounded<PointRelation, MinRelation>(pr, minr);
}
-template <typename Point>
-inline detail::distance_unbounded<Point, detail::distance_centroid_tag>
-distance_centroid(Point const& p)
+template <typename PointRelation, typename MaxRelation>
+inline detail::max_bounded<PointRelation, MaxRelation>
+max_bounded(PointRelation const& pr, MaxRelation const& maxr)
{
- return detail::distance_unbounded<Point, detail::distance_centroid_tag>(p);
+ return detail::max_bounded<PointRelation, MaxRelation>(pr, maxr);
}
-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)
+template <typename PointRelation, typename MinRelation, typename MaxRelation>
+inline detail::bounded<PointRelation, MinRelation, MaxRelation>
+bounded(PointRelation const& pr, MinRelation const& minr, MaxRelation const& maxr)
{
- return detail::distance_half_bounded<Point, detail::distance_near_tag, detail::distance_min_tag>(p, distance_min);
+ return detail::bounded<PointRelation, MinRelation, MaxRelation>(pr, minr, maxr);
}
-template <typename Point>
-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& distance_min)
+// algorithms
+
+namespace detail{
+
+// point_relation
+
+template <typename PointRelation>
+struct point_relation
{
- return detail::distance_half_bounded<Point, detail::distance_far_tag, detail::distance_min_tag>(p, distance_min);
-}
+ typedef PointRelation type;
+};
-template <typename Point>
-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)
+template <typename PointRelation>
+struct point_relation< detail::unbounded<PointRelation> >
{
- return detail::distance_half_bounded<Point, detail::distance_centroid_tag, detail::distance_min_tag>(p, distance_min);
-}
+ typedef PointRelation type;
+};
-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& distance_min,
- typename index::traits::coordinate_type<Point>::type const& distance_max)
+template <typename PointRelation, typename MinRelation>
+struct point_relation< detail::min_bounded<PointRelation, MinRelation> >
{
- return detail::distance_bounded<Point, detail::distance_near_tag>(p, distance_min, distance_max);
-}
+ typedef PointRelation type;
+};
-template <typename Point>
-inline detail::distance_bounded<Point, detail::distance_far_tag>
-distance_far(
- Point const& p,
- typename index::traits::coordinate_type<Point>::type const& distance_min,
- typename index::traits::coordinate_type<Point>::type const& distance_max)
+template <typename PointRelation, typename MaxRelation>
+struct point_relation< detail::max_bounded<PointRelation, MaxRelation> >
{
- return detail::distance_bounded<Point, detail::distance_far_tag>(p, distance_min, distance_max);
-}
+ typedef PointRelation type;
+};
-template <typename Point>
-inline detail::distance_bounded<Point, detail::distance_centroid_tag>
-distance_centroid(
- Point const& p,
- typename index::traits::coordinate_type<Point>::type const& distance_min,
- typename index::traits::coordinate_type<Point>::type const& distance_max)
+template <typename PointRelation, typename MinRelation, typename MaxRelation>
+struct point_relation< detail::bounded<PointRelation, MinRelation, MaxRelation> >
{
- return detail::distance_bounded<Point, detail::distance_centroid_tag>(p, distance_min, distance_max);
-}
+ typedef PointRelation type;
+};
-// algorithms
+
+} // namespace detail
namespace detail
{
-// distance_calc_impl
+// cdist
+
+template <typename T, typename Tag>
+struct cdist
+{
+ T value;
+};
+
+// cdist_merge
+
+template <typename CDistTuple, typename CDist>
+struct cdist_merge
+{
+ typedef typename index::tuples::add_unique<
+ CDistTuple,
+ CDist
+ >::type type;
+};
+
+template <typename T, typename Tag, typename OtherTag>
+struct cdist_merge<
+ cdist<T, Tag>,
+ cdist<T, OtherTag> >
+{
+ typedef boost::tuple<
+ cdist<T, Tag>,
+ cdist<T, OtherTag>
+ > type;
+};
-template <typename Point, typename Indexable, typename AlgoTag>
-struct distance_calc_impl
+template <typename T, typename Tag>
+struct cdist_merge<
+ cdist<T, Tag>,
+ cdist<T, Tag> >
{
- BOOST_MPL_ASSERT_MSG(
- (false),
- NOT_IMPLEMENTED_FOR_THIS_TAG_TYPE,
- (distance_calc_impl));
+ typedef cdist<T, Tag> type;
};
-template <typename Point, typename Indexable>
-struct distance_calc_impl<Point, Indexable, detail::distance_near_tag>
+// cdist_value_type
+
+template <typename CDistTuple>
+struct cdist_value
{
- typedef typename geometry::default_distance_result<Point, Indexable>::type result_type;
+ typedef typename cdist_value<
+ typename boost::tuples::element<0, CDistTuple>::type
+ >::type type;
- static inline result_type apply(Point const& p, Indexable const& i)
+ template <typename Tag>
+ static inline type & get(CDistTuple & cdtup)
{
- return index::comparable_distance_near(p, i);
+ return boost::get<
+ index::tuples::find_index<
+ CDistTuple,
+ cdist<type, Tag>
+ >::value
+ >(cdtup).value;
+ }
+
+ template <typename Tag>
+ static inline type const& get(CDistTuple const& cdtup)
+ {
+ return boost::get<
+ index::tuples::find_index<
+ CDistTuple,
+ cdist<type, Tag>
+ >::value
+ >(cdtup).value;
}
};
-template <typename Point, typename Indexable>
-struct distance_calc_impl<Point, Indexable, detail::distance_far_tag>
+template <typename T, typename Tag>
+struct cdist_value<
+ cdist<T, Tag>
+>
{
- typedef typename geometry::default_distance_result<Point, Indexable>::type result_type;
+ typedef T type;
- static inline result_type apply(Point const& p, Indexable const& i)
+ template <typename Tag2>
+ static inline type & get(cdist<T, Tag> & cd)
{
- return index::comparable_distance_far(p, i);
+ // TODO MPL_ASSERT tuples::equal<CDist, cdist<T, Tag>>::value
+ return cd.value;
+ }
+
+ template <typename Tag2>
+ static inline type const& get(cdist<T, Tag> const& cd)
+ {
+ // TODO MPL_ASSERT tuples::equal<CDist, cdist<T, Tag>>::value
+ return cd.value;
}
};
-template <typename Point, typename Indexable>
-struct distance_calc_impl<Point, Indexable, detail::distance_centroid_tag>
+} // namespace detail
+
+namespace detail {
+
+// distances_calc_impl_rel
+
+template <typename RelDist>
+struct distances_calc_impl_rel
+{
+ // TODO MPL_ASSERT not implemented for this RelDist
+};
+
+template <typename T>
+struct distances_calc_impl_rel<
+ cdist<T, detail::near_tag>
+>
{
- typedef typename geometry::default_distance_result<Point, Indexable>::type result_type;
+ template <typename Point, typename Indexable>
+ typename geometry::default_distance_result<Point, Indexable>::type
+ static inline apply(Point const& p, Indexable const& i)
+ {
+ return index::comparable_distance_near(p, i);
+ }
+};
- static inline result_type apply(Point const& p, Indexable const& i)
+template <typename T>
+struct distances_calc_impl_rel<
+ cdist<T, detail::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::comparable_distance_centroid(p, i);
}
};
-// distance_calc
+template <typename T>
+struct distances_calc_impl_rel<
+ cdist<T, detail::far_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::comparable_distance_far(p, i);
+ }
+};
+
+// distances_calc_impl_tuple
-template <typename Point, typename Indexable, typename Tag>
-struct distance_calc
+template <typename Distances, typename Point, typename Indexable, size_t N>
+struct distances_calc_impl_tuple
{
- typedef typename geometry::default_distance_result<Point, Indexable>::type result_type;
+ // 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);
+ }
+};
- static inline result_type apply(Point const& p, Indexable const& i)
+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)
{
- return index::comparable_distance_near(p, i);
+ boost::get<0>(d).value =
+ distances_calc_impl_rel<
+ typename boost::tuples::element<0, Distances>::type
+ >::apply(p, i);
+ }
+};
+
+// distances_calc_impl
+
+template <typename Distances, typename Point, typename Indexable>
+struct distances_calc_impl
+{
+ 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);
+ }
+};
+
+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)
+ {
+ d.value = distances_calc_impl_rel<
+ cdist<T, Tag>
+ >::apply(p, i);
}
};
-template <typename Point, typename AlgoTag, typename Indexable, typename Tag>
-struct distance_calc<
- detail::distance_unbounded<Point, AlgoTag>,
+// distances_calc
+
+template <typename PointRelation, typename Indexable, typename Tag>
+struct distances_calc
+{
+ 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, typename Tag>
+struct distances_calc<
+ detail::unbounded<PointRelation>,
Indexable,
- Tag>
+ Tag
+>
{
- typedef typename distance_calc_impl<Point, Indexable, AlgoTag>::result_type result_type;
+ 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;
- static inline result_type apply(
- detail::distance_unbounded<Point, AlgoTag> const& dx,
- Indexable const& i)
+ typedef detail::cdist<distance_type, point_relation_tag> result_type;
+
+ static inline result_type apply(detail::unbounded<PointRelation> const& pp, Indexable const& i)
{
- return distance_calc_impl<Point, Indexable, AlgoTag>::apply(dx.point, 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 Point, typename AlgoTag, typename LimitTag, typename Indexable, typename Tag>
-struct distance_calc<
- detail::distance_half_bounded<Point, AlgoTag, LimitTag>,
+template <typename PointRelation, typename MinRelation, typename Indexable, typename Tag>
+struct distances_calc<
+ detail::min_bounded<PointRelation, MinRelation>,
Indexable,
- Tag>
+ Tag
+>
{
- typedef typename distance_calc_impl<Point, Indexable, AlgoTag>::result_type result_type;
+ 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;
- static inline result_type apply(
- detail::distance_half_bounded<Point, AlgoTag, LimitTag> const& dx,
- Indexable const& i)
+ 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)
{
- return distance_calc_impl<Point, Indexable, AlgoTag>::apply(dx.point, 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 Point, typename AlgoTag, typename Indexable, typename Tag>
-struct distance_calc<
- detail::distance_bounded<Point, AlgoTag>,
+template <typename PointRelation, typename MaxRelation, typename Indexable, typename Tag>
+struct distances_calc<
+ detail::max_bounded<PointRelation, MaxRelation>,
Indexable,
- Tag>
+ Tag
+>
{
- typedef typename distance_calc_impl<Point, Indexable, AlgoTag>::result_type result_type;
+ 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, typename Tag>
+struct distances_calc<
+ detail::bounded<PointRelation, MinRelation, MaxRelation>,
+ Indexable,
+ 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::distance_bounded<Point, AlgoTag> const& dx,
+ detail::bounded<PointRelation, MinRelation, MaxRelation> const& pp,
Indexable const& i)
{
- return distance_calc_impl<Point, Indexable, AlgoTag>::apply(dx.point, i);
+ result_type res;
+ distances_calc_impl<result_type, point_type, Indexable>
+ ::apply(res, relation<PointRelation>::value(pp.point_relation), i);
+ return res;
}
};
-// distance_predicate_check
+// distances_predicates_check
+
+// TODO explicitly define DistanceType ?
+// Indexable/Box is used in distances_predicates_check only for purpose of
+// this explicit DistanceType definition
+
+// move distance_calc and distance_comp into geometry::index ?
-template <typename Point, typename Indexable, typename Tag>
-struct distance_predicate_check
+template <typename PointRelation, typename Indexable, typename Tag>
+struct distances_predicates_check
{
- template <typename DistanceType>
- static inline bool apply(Point const&, DistanceType const&)
+ template <typename Distances>
+ static inline bool apply(PointRelation const&, Distances const&)
{
return true;
}
};
-template <typename Point, typename AlgoTag, typename Indexable, typename Tag>
-struct distance_predicate_check<
- detail::distance_unbounded<Point, AlgoTag>,
+template <typename PointRelation, typename Indexable, typename Tag>
+struct distances_predicates_check<
+ detail::unbounded<PointRelation>,
Indexable,
- Tag>
+ Tag
+>
{
- template <typename DistanceType>
- static inline bool apply(
- detail::distance_unbounded<Point, AlgoTag> const&,
- DistanceType const&)
+ template <typename Distances>
+ static inline bool apply(detail::unbounded<PointRelation> const&, Distances const&)
{
return true;
}
};
-template <typename Point, typename AlgoTag, typename Indexable, typename Tag>
-struct distance_predicate_check<
- detail::distance_half_bounded<Point, AlgoTag, detail::distance_min_tag>,
+template <typename PointRelation, typename MinRelation, typename Indexable, typename Tag>
+struct distances_predicates_check<
+ detail::min_bounded<PointRelation, MinRelation>,
Indexable,
- Tag>
+ Tag
+>
{
- template <typename DistanceType>
+ typedef typename detail::relation<MinRelation>::tag min_relation_tag;
+
+ template <typename Distances>
static inline bool apply(
- detail::distance_half_bounded<Point, AlgoTag, detail::distance_min_tag> const& dx,
- DistanceType const& comparable_d)
+ detail::min_bounded<PointRelation, MinRelation> const& pred,
+ Distances const& d)
{
- return dx.comparable_limit <= comparable_d;
+ return pred.comparable_min <=
+ detail::cdist_value<Distances>::template get<min_relation_tag>(d);
}
};
-template <typename Point, typename AlgoTag, typename Indexable, typename Tag>
-struct distance_predicate_check<
- detail::distance_half_bounded<Point, AlgoTag, detail::distance_max_tag>,
+template <typename PointRelation, typename MaxRelation, typename Indexable, typename Tag>
+struct distances_predicates_check<
+ detail::max_bounded<PointRelation, MaxRelation>,
Indexable,
- Tag>
+ Tag
+>
{
- template <typename DistanceType>
+ typedef typename detail::relation<MaxRelation>::tag max_relation_tag;
+
+ template <typename Distances>
static inline bool apply(
- detail::distance_half_bounded<Point, AlgoTag, detail::distance_max_tag> const& dx,
- DistanceType const& comparable_d)
+ detail::max_bounded<PointRelation, MaxRelation> const& pred,
+ Distances const& d)
{
- return comparable_d <= dx.comparable_limit;
+ return pred.comparable_max <=
+ detail::cdist_value<Distances>::template get<max_relation_tag>(d);
}
};
-template <typename Point, typename AlgoTag, typename Indexable, typename Tag>
-struct distance_predicate_check<
- detail::distance_bounded<Point, AlgoTag>,
+template <typename PointRelation, typename MinRelation, typename MaxRelation, typename Indexable, typename Tag>
+struct distances_predicates_check<
+ detail::bounded<PointRelation, MinRelation, MaxRelation>,
Indexable,
- Tag>
+ Tag
+>
{
- template <typename DistanceType>
+ 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::distance_bounded<Point, AlgoTag> const& dx,
- DistanceType const& comparable_d)
+ detail::bounded<PointRelation, MinRelation, MaxRelation> const& pred,
+ Distances const& d)
{
- return dx.comparable_min <= comparable_d && comparable_d <= dx.comparable_max;
+ 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_point
-
-template <typename Point>
-struct distance_point
-{
- typedef Point type;
-};
-
-template <typename Point, typename AlgoTag>
-struct distance_point< detail::distance_unbounded<Point, AlgoTag> >
-{
- typedef Point type;
-};
-
-template <typename Point, typename AlgoTag, typename LimitTag>
-struct distance_point< detail::distance_half_bounded<Point, AlgoTag, LimitTag> >
-{
- typedef Point type;
-};
-
-template <typename Point, typename AlgoTag>
-struct distance_point< detail::distance_bounded<Point, AlgoTag> >
-{
- typedef Point type;
-};
+// TODO calculate all of this for Boxes only!
+// for Points calculate only 1 distance allways
} // namespace detail
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-27 15:31:01 EDT (Tue, 27 Sep 2011)
@@ -25,15 +25,12 @@
struct empty {};
-//TODO: awulkiew - consider storing Geometry instead of Geometry const&
-// it's faster and eliminates problems with storing of references to temporaries
-
template <typename Geometry>
struct covered_by
: nonassignable
{
covered_by(Geometry const& g) : geometry(g) {}
- Geometry const& geometry;
+ Geometry geometry;
};
template <typename Geometry>
@@ -41,7 +38,7 @@
: nonassignable
{
intersects(Geometry const& g) : geometry(g) {}
- Geometry const& geometry;
+ Geometry geometry;
};
template <typename Geometry>
@@ -49,7 +46,7 @@
: nonassignable
{
overlaps(Geometry const& g) : geometry(g) {}
- Geometry const& geometry;
+ Geometry geometry;
};
template <typename Geometry>
@@ -57,7 +54,7 @@
: nonassignable
{
within(Geometry const& g) : geometry(g) {}
- Geometry const& geometry;
+ Geometry geometry;
};
} // namespace detail
Modified: sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/distance_predicates.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/distance_predicates.hpp (original)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/distance_predicates.hpp 2011-09-27 15:31:01 EDT (Tue, 27 Sep 2011)
@@ -1,7 +1,7 @@
// Boost.Geometry (aka GGL, Generic Geometry Library)
//
// Boost.SpatialIndex - Spatial index distance predicates, calculators and checkers
-// used in nearest query - rtree's specializations
+// used in nearest query - rtree's nodes specializations
//
// Copyright 2011 Adam Wulkiewicz.
// Use, modification and distribution is subject to the Boost Software License,
@@ -12,298 +12,206 @@
#define BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_DISTANCE_PREDICATES_HPP
#include <boost/geometry/extensions/index/distance_predicates.hpp>
+#include <boost/geometry/extensions/index/rtree/tags.hpp>
namespace boost { namespace geometry { namespace index {
namespace detail {
-namespace rtree
-{
-
-struct value_distance_predicate_tag {};
-struct node_distance_predicate_tag {};
-
-} // namespace rtree
-
// distance_calc
-template <typename Point, typename Indexable>
-struct distance_calc<
- Point,
- Indexable,
- rtree::node_distance_predicate_tag>
+template <typename PointRelation, typename Box>
+struct distances_calc<
+ PointRelation,
+ Box,
+ rtree::node_tag>
{
- typedef typename geometry::default_distance_result<Point, Indexable>::type result_type;
+ typedef typename detail::relation<PointRelation>::value_type point_type;
+ typedef typename geometry::default_distance_result<point_type, Box>::type distance_type;
- static inline result_type apply(Point const& p, Indexable const& i)
+ typedef detail::cdist<distance_type, detail::near_tag> result_type;
+
+ static inline result_type apply(PointRelation const& p, Box const& i)
{
- return index::comparable_distance_near(p, i);
+ result_type res;
+ distances_calc_impl<result_type, point_type, Box>
+ ::apply(res, relation<PointRelation>::value(p), i);
+ return res;
}
};
-template <typename Point, typename AlgoTag, typename Indexable>
-struct distance_calc<
- detail::distance_unbounded<Point, AlgoTag>,
- Indexable,
- rtree::node_distance_predicate_tag>
+template <typename PointRelation, typename Box>
+struct distances_calc<
+ detail::unbounded<PointRelation>,
+ Box,
+ rtree::node_tag
+>
{
- typedef typename geometry::default_distance_result<Point, Indexable>::type result_type;
+ typedef typename detail::relation<PointRelation>::value_type point_type;
+ typedef typename geometry::default_distance_result<point_type, Box>::type distance_type;
- static inline result_type apply(
- detail::distance_unbounded<Point, AlgoTag> const& dx,
- Indexable const& i)
+ typedef detail::cdist<distance_type, detail::near_tag> result_type;
+
+ static inline result_type apply(detail::unbounded<PointRelation> const& pp, Box const& i)
{
- return index::comparable_distance_near(dx.point, 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 Point, typename AlgoTag, typename Indexable>
-struct distance_calc<
- detail::distance_half_bounded<Point, AlgoTag, detail::distance_min_tag>,
- Indexable,
- rtree::node_distance_predicate_tag>
+template <typename PointRelation, typename MinRelation, typename Box>
+struct distances_calc<
+ detail::min_bounded<PointRelation, MinRelation>,
+ Box,
+ rtree::node_tag
+>
{
- typedef typename geometry::default_distance_result<Point, Indexable>::type distance_type;
- typedef std::pair<distance_type, distance_type> result_type;
-
- static inline result_type apply(
- detail::distance_half_bounded<Point, AlgoTag, detail::distance_min_tag> const& dx,
- Indexable const& i)
- {
- return std::make_pair(
- index::comparable_distance_near(dx.point, i),
- index::comparable_distance_far(dx.point, i)
- );
+ 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::near_tag>,
+ cdist<distance_type, detail::far_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 Point, typename AlgoTag, typename Indexable>
-struct distance_calc<
- detail::distance_half_bounded<Point, AlgoTag, detail::distance_max_tag>,
- Indexable,
- rtree::node_distance_predicate_tag>
+template <typename PointRelation, typename MaxRelation, typename Box>
+struct distances_calc<
+ detail::max_bounded<PointRelation, MaxRelation>,
+ Box,
+ rtree::node_tag
+>
{
- typedef typename geometry::default_distance_result<Point, Indexable>::type result_type;
+ 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::near_tag> result_type;
- static inline result_type apply(
- detail::distance_half_bounded<Point, AlgoTag, detail::distance_max_tag> const& dx,
- Indexable const& i)
+ static inline result_type apply(detail::max_bounded<PointRelation, MaxRelation> const& pp, Box const& i)
{
- return index::comparable_distance_near(dx.point, 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 Point, typename AlgoTag, typename Indexable>
-struct distance_calc<
- detail::distance_bounded<Point, AlgoTag>,
- Indexable,
- rtree::node_distance_predicate_tag>
+template <typename PointRelation, typename MinRelation, typename MaxRelation, typename Box>
+struct distances_calc<
+ detail::bounded<PointRelation, MinRelation, MaxRelation>,
+ Box,
+ rtree::node_tag
+>
{
- typedef typename geometry::default_distance_result<Point, Indexable>::type distance_type;
- typedef std::pair<distance_type, distance_type> result_type;
+ typedef typename detail::relation<PointRelation>::value_type point_type;
+ typedef typename geometry::default_distance_result<point_type, Box>::type distance_type;
- static inline result_type apply(
- detail::distance_bounded<Point, AlgoTag> const& dx,
- Indexable const& i)
- {
- return std::make_pair(
- index::comparable_distance_near(dx.point, i),
- index::comparable_distance_far(dx.point, i)
- );
+ typedef typename detail::cdist_merge<
+ cdist<distance_type, detail::near_tag>,
+ cdist<distance_type, detail::far_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_predicate_check
-template <typename Point, typename Indexable>
-struct distance_predicate_check<
- Point,
- Indexable,
- rtree::node_distance_predicate_tag>
+template <typename PointRelation, typename Box>
+struct distances_predicates_check<
+ PointRelation,
+ Box,
+ rtree::node_tag>
{
- template <typename DistanceType>
- static inline bool apply(Point const&, DistanceType const&)
+ template <typename Distances>
+ static inline bool apply(PointRelation const&, Distances const&)
{
return true;
}
};
-template <typename Point, typename AlgoTag, typename Indexable>
-struct distance_predicate_check<
- detail::distance_unbounded<Point, AlgoTag>,
- Indexable,
- rtree::node_distance_predicate_tag>
+template <typename PointRelation, typename Box>
+struct distances_predicates_check<
+ detail::unbounded<PointRelation>,
+ Box,
+ rtree::node_tag>
{
- template <typename DistanceType>
+ template <typename Distances>
static inline bool apply(
- detail::distance_unbounded<Point, AlgoTag> const&,
- DistanceType const&)
+ detail::unbounded<PointRelation> const&,
+ Distances const&)
{
return true;
}
};
-template <typename Point, typename AlgoTag, typename Indexable>
-struct distance_predicate_check<
- detail::distance_half_bounded<Point, AlgoTag, detail::distance_min_tag>,
- Indexable,
- rtree::node_distance_predicate_tag>
+template <typename PointRelation, typename MinRelation, typename Box>
+struct distances_predicates_check<
+ detail::min_bounded<PointRelation, MinRelation>,
+ Box,
+ rtree::node_tag>
{
- template <typename DistanceType>
+ template <typename Distances>
static inline bool apply(
- detail::distance_half_bounded<Point, AlgoTag, detail::distance_min_tag> const& dx,
- DistanceType const& d)
+ detail::min_bounded<PointRelation, MinRelation> const& pred,
+ Distances const& d)
{
- return dx.comparable_limit <= d.second;
+ return pred.comparable_min
+ <= cdist_value<Distances>::template get<detail::far_tag>(d);
}
};
-template <typename Point, typename AlgoTag, typename Indexable>
-struct distance_predicate_check<
- detail::distance_half_bounded<Point, AlgoTag, detail::distance_max_tag>,
- Indexable,
- rtree::node_distance_predicate_tag>
+template <typename PointRelation, typename MaxRelation, typename Box>
+struct distances_predicates_check<
+ detail::max_bounded<PointRelation, MaxRelation>,
+ Box,
+ rtree::node_tag>
{
- template <typename DistanceType>
+ template <typename Distances>
static inline bool apply(
- detail::distance_half_bounded<Point, AlgoTag, detail::distance_max_tag> const& dx,
- DistanceType const& comparable_d)
+ detail::max_bounded<PointRelation, MaxRelation> const& pred,
+ Distances const& d)
{
- return comparable_d <= dx.comparable_limit;
+ return cdist_value<Distances>::template get<detail::near_tag>(d)
+ <= pred.comparable_max;
}
};
-template <typename Point, typename AlgoTag, typename Indexable>
-struct distance_predicate_check<
- detail::distance_bounded<Point, AlgoTag>,
- Indexable,
- rtree::node_distance_predicate_tag>
+template <typename PointRelation, typename MinRelation, typename MaxRelation, typename Box>
+struct distances_predicates_check<
+ detail::bounded<PointRelation, MinRelation, MaxRelation>,
+ Box,
+ rtree::node_tag>
{
- template <typename DistanceType>
+ template <typename Distances>
static inline bool apply(
- detail::distance_bounded<Point, AlgoTag> const& dx,
- DistanceType const& d)
- {
- return dx.comparable_min <= d.second && d.first <= dx.comparable_max;
- }
-};
-
-// TODO implement alternative version for Indexable being a Point - don't need to calculate the distance 2x
-// TODO explicitly define DistanceType ?
-
-namespace rtree
-{
-
-// distance less comparator
-
-template <typename Point, typename Indexable>
-struct distance_less
-{
- template <typename DistanceType>
- inline bool operator()(DistanceType const& d1, DistanceType const& d2)
- {
- return d1 < d2;
- }
-};
-
-template <typename Point, typename AlgoTag, typename Indexable>
-struct distance_less<
- detail::distance_half_bounded<Point, AlgoTag, detail::distance_min_tag>,
- Indexable
->
-{
- template <typename DistanceType>
- inline bool operator()(DistanceType const& d1, DistanceType const& d2)
- {
- return d1.first < d2.first;
- }
-};
-
-template <typename Point, typename AlgoTag, typename Indexable>
-struct distance_less<
- detail::distance_bounded<Point, AlgoTag>,
- Indexable
->
-{
- template <typename DistanceType>
- inline bool operator()(DistanceType const& d1, DistanceType const& d2)
- {
- return d1.first < d2.first;
- }
-};
-
-// TODO distance_node_pruning_check
-
-template <typename Point, typename Indexable>
-struct distance_node_pruning_check
-{
- template <typename SmallestDistanceType, typename NodeDistanceType>
- static inline bool apply(SmallestDistanceType const& sd, NodeDistanceType const& nd)
- {
- return sd < nd;
- }
-};
-
-template <typename Point, typename AlgoTag, typename Indexable>
-struct distance_node_pruning_check<
- detail::distance_half_bounded<Point, AlgoTag, detail::distance_min_tag>,
- Indexable
->
-{
- template <typename SmallestDistanceType, typename NodeDistanceType>
- static inline bool apply(SmallestDistanceType const& sd, NodeDistanceType const& nd)
- {
- return sd < nd.first;
- }
-};
-
-template <typename Point, typename AlgoTag, typename Indexable>
-struct distance_node_pruning_check<
- detail::distance_bounded<Point, AlgoTag>,
- Indexable
->
-{
- template <typename SmallestDistanceType, typename NodeDistanceType>
- static inline bool apply(SmallestDistanceType const& sd, NodeDistanceType const& nd)
+ detail::bounded<PointRelation, MinRelation, MaxRelation> const& pred,
+ Distances const& d)
{
- return sd < nd.first;
+ return pred.comparable_min
+ <= cdist_value<Distances>::template get<detail::far_tag>(d)
+ && cdist_value<Distances>::template get<detail::near_tag>(d)
+ <= pred.comparable_max;
}
};
-} // namespace rtree
-
-// 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)
-
-// for values, proper distance values are calculated min, max or centroid
-// and tested with comp_near and/or comp_far
-
-// + 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);
-//}
-
}}} // namespace boost::geometry::index
#endif // BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_DISTANCE_PREDICATES_HPP
Modified: sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/predicates.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/predicates.hpp (original)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/predicates.hpp 2011-09-27 15:31:01 EDT (Tue, 27 Sep 2011)
@@ -11,33 +11,27 @@
#define BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_PREDICATES_HPP
#include <boost/geometry/extensions/index/predicates.hpp>
+#include <boost/geometry/extensions/index/rtree/tags.hpp>
namespace boost { namespace geometry { namespace index {
namespace detail {
-
-namespace rtree {
-
-struct value_predicates_tag {};
-struct node_predicates_tag {};
-
-} // namespace rtree
//template <typename Geometry>
//struct predicate_check<Geometry, rtree::node_predicates_tag>
//{
-// template <typename Indexable>
-// static inline bool apply(Geometry const& g, Indexable const& i)
+// template <typename Box>
+// static inline bool apply(Geometry const& g, Box const& i)
// {
// return geometry::intersects(i, g);
// }
//};
template <typename Geometry>
-struct predicate_check<covered_by<Geometry>, rtree::node_predicates_tag>
+struct predicate_check<covered_by<Geometry>, rtree::node_tag>
{
- template <typename Indexable>
- static bool apply(covered_by<Geometry> const& p, Indexable const& i)
+ template <typename Box>
+ static bool apply(covered_by<Geometry> const& p, Box const& i)
{
return geometry::intersects(i, p.geometry);
}
@@ -46,18 +40,18 @@
//template <typename Geometry>
//struct predicate_check<intersects<Geometry>, rtree::node_predicates_tag>
//{
-// template <typename Indexable>
-// static inline bool apply(intersects<Geometry> const& p, Indexable const& i)
+// template <typename Box>
+// static inline bool apply(intersects<Geometry> const& p, Box const& i)
// {
// return geometry::intersects(i, p.geometry);
// }
//};
template <typename Geometry>
-struct predicate_check<overlaps<Geometry>, rtree::node_predicates_tag>
+struct predicate_check<overlaps<Geometry>, rtree::node_tag>
{
- template <typename Indexable>
- static inline bool apply(overlaps<Geometry> const& p, Indexable const& i)
+ template <typename Box>
+ static inline bool apply(overlaps<Geometry> const& p, Box const& i)
{
// TODO: awulkiew - possibly change to the version without border case
// e.g. intersects_without_border(0,0x1,1, 1,1x2,2) should give false
@@ -66,10 +60,10 @@
};
template <typename Geometry>
-struct predicate_check<within<Geometry>, rtree::node_predicates_tag>
+struct predicate_check<within<Geometry>, rtree::node_tag>
{
- template <typename Indexable>
- static bool apply(within<Geometry> const& p, Indexable const& i)
+ template <typename Box>
+ static bool apply(within<Geometry> const& p, Box const& i)
{
// TODO: awulkiew - possibly change to the version without border case
// e.g. intersects_without_border(0,0x1,1, 1,1x2,2) should give false
Modified: sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/rtree.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/rtree.hpp (original)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/rtree.hpp 2011-09-27 15:31:01 EDT (Tue, 27 Sep 2011)
@@ -188,13 +188,16 @@
}
private:
- template <typename DistancePredicate, typename Predicates>
- inline size_t nearest_one(DistancePredicate const& p, Predicates const& pred, value_type & v) const
+ template <typename DistancesPredicates, typename Predicates>
+ inline size_t nearest_one(DistancesPredicates const& p, Predicates const& pred, value_type & v) const
{
+ typedef typename detail::point_relation<DistancesPredicates>::type point_relation;
+ typedef typename detail::relation<point_relation>::value_type point_type;
+
typedef detail::rtree::visitors::nearest_one<
value_type,
translator_type,
- typename detail::distance_point<DistancePredicate>::type
+ point_type
> result_type;
result_type result;
@@ -204,7 +207,7 @@
options_type,
translator_type,
box_type,
- DistancePredicate,
+ DistancesPredicates,
Predicates,
result_type
> nearest_v(m_translator, p, pred, result);
@@ -214,13 +217,16 @@
return result.get(v);
}
- template <typename DistancePredicate, typename Predicates, typename OutIter>
- inline size_t nearest_k(DistancePredicate const& p, size_t k, Predicates const& pred, OutIter out_it) const
+ template <typename DistancesPredicates, typename Predicates, typename OutIter>
+ inline size_t nearest_k(DistancesPredicates const& p, size_t k, Predicates const& pred, OutIter out_it) const
{
+ typedef typename detail::point_relation<DistancesPredicates>::type point_relation;
+ typedef typename detail::relation<point_relation>::value_type point_type;
+
typedef detail::rtree::visitors::nearest_k<
value_type,
translator_type,
- typename detail::distance_point<DistancePredicate>::type
+ point_type
> result_type;
result_type result(k);
@@ -230,7 +236,7 @@
options_type,
translator_type,
box_type,
- DistancePredicate,
+ DistancesPredicates,
Predicates,
result_type
> nearest_v(m_translator, p, pred, result);
Added: sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/tags.hpp
==============================================================================
--- (empty file)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/tags.hpp 2011-09-27 15:31:01 EDT (Tue, 27 Sep 2011)
@@ -0,0 +1,24 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+//
+// Boost.SpatialIndex - tags related to rtree used in various files
+//
+// 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_RTREE_TAGS_HPP
+#define BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_TAGS_HPP
+
+namespace boost { namespace geometry { namespace index {
+
+namespace detail { namespace rtree {
+
+struct value_tag {};
+struct node_tag {};
+
+}} // namespace detail::rtree
+
+}}} // namespace boost::geometry::index
+
+#endif // BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_TAGS_HPP
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-27 15:31:01 EDT (Tue, 27 Sep 2011)
@@ -130,7 +130,7 @@
typename Options,
typename Translator,
typename Box,
- typename DistancePredicate,
+ typename DistancesPredicates,
typename Predicates,
typename Result
>
@@ -143,16 +143,15 @@
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 index::detail::distance_calc<DistancePredicate, Box, rtree::node_distance_predicate_tag> node_distance_calc;
- typedef typename node_distance_calc::result_type node_distance_type;
- typedef index::detail::distance_predicate_check<DistancePredicate, Box, rtree::node_distance_predicate_tag> node_distance_predicate_check;
- typedef rtree::distance_less<DistancePredicate, Box> node_distance_less;
-
- typedef index::detail::distance_calc<DistancePredicate, typename Translator::indexable_type, rtree::value_distance_predicate_tag> value_distance_calc;
- typedef typename value_distance_calc::result_type value_distance_type;
- typedef index::detail::distance_predicate_check<DistancePredicate, typename Translator::indexable_type, rtree::value_distance_predicate_tag> value_distance_predicate_check;
+ typedef index::detail::distances_calc<DistancesPredicates, Box, rtree::node_tag> node_distances_calc;
+ typedef typename node_distances_calc::result_type node_distances_type;
+ typedef index::detail::distances_predicates_check<DistancesPredicates, Box, rtree::node_tag> node_distances_predicates_check;
+
+ typedef index::detail::distances_calc<DistancesPredicates, typename Translator::indexable_type, rtree::value_tag> value_distances_calc;
+ typedef typename value_distances_calc::result_type value_distances_type;
+ typedef index::detail::distances_predicates_check<DistancesPredicates, typename Translator::indexable_type, rtree::value_tag> value_distances_predicates_check;
- inline nearest(Translator const& t, DistancePredicate const& dist_pred, Predicates const& pred, Result & r)
+ inline nearest(Translator const& t, DistancesPredicates const& dist_pred, Predicates const& pred, Result & r)
: m_tr(t), m_dist_pred(dist_pred), m_pred(pred)
, m_result(r)
{}
@@ -163,7 +162,7 @@
{
// array of active nodes
index::pushable_array<
- std::pair<node_distance_type, const node *>,
+ std::pair<node_distances_type, const node *>,
Options::parameters_type::max_elements
> active_branch_list;
@@ -175,13 +174,13 @@
it != elements.end(); ++it)
{
// if current node meets predicates
- if ( index::predicates_check<rtree::node_predicates_tag>(m_pred, it->first) )
+ if ( index::predicates_check<rtree::node_tag>(m_pred, it->first) )
{
// calculate node's distance(s) for distance predicate
- node_distance_type node_dist_data = node_distance_calc::apply(m_dist_pred, it->first);
+ node_distances_type node_dist_data = node_distances_calc::apply(m_dist_pred, it->first);
// if current node distance(s) meets distance predicate
- if ( node_distance_predicate_check::apply(m_dist_pred, node_dist_data) )
+ if ( node_distances_predicates_check::apply(m_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) );
@@ -194,7 +193,7 @@
return;
// sort array
- std::sort(active_branch_list.begin(), active_branch_list.end(), node_distance_less());
+ std::sort(active_branch_list.begin(), active_branch_list.end(), abl_less);
// recursively visit nodes
for ( size_t i = 0 ;; ++i )
@@ -219,16 +218,23 @@
it != elements.end(); ++it)
{
// if value meets predicates
- if ( index::predicates_check<rtree::value_predicates_tag>(m_pred, m_tr(*it)) )
+ if ( index::predicates_check<rtree::value_tag>(m_pred, m_tr(*it)) )
{
// calculate values distance for distance predicate
- value_distance_type dist = value_distance_calc::apply(m_dist_pred, m_tr(*it));
+ value_distances_type distances = value_distances_calc::apply(m_dist_pred, m_tr(*it));
// if distance meets distance predicate
- if ( value_distance_predicate_check::apply(m_dist_pred, dist) )
+ if ( value_distances_predicates_check::apply(m_dist_pred, distances) )
{
+ typedef typename index::detail::point_relation<DistancesPredicates>::type point_relation_type;
+ typedef typename index::detail::relation<point_relation_type>::tag point_relation_tag;
+
// store value
- m_result.store(*it, dist);
+ m_result.store(
+ *it,
+ index::detail::cdist_value<value_distances_type>
+ ::template get<point_relation_tag>(distances)
+ );
}
}
}
@@ -243,16 +249,33 @@
{
// prune if box's mindist is further than value's mindist
while ( !abl.empty() &&
- distance_node_pruning_check<DistancePredicate, Box>
- ::apply(m_result.comparable_distance(), abl.back().first) )
+ prune_node(m_result.comparable_distance(), abl.back().first) )
{
abl.pop_back();
}
}
}
+ static inline bool abl_less(
+ std::pair<node_distances_type, const node *> const& p1,
+ std::pair<node_distances_type, const node *> const& p2)
+ {
+ return index::detail::cdist_value<node_distances_type>
+ ::template get<index::detail::near_tag>(p1.first)
+ < index::detail::cdist_value<node_distances_type>
+ ::template get<index::detail::near_tag>(p2.first);
+ }
+
+ template <typename Distance>
+ static inline bool prune_node(Distance const& smallest_dist, node_distances_type const& d)
+ {
+ return smallest_dist
+ < index::detail::cdist_value<node_distances_type>
+ ::template get<index::detail::near_tag>(d);
+ }
+
Translator const& m_tr;
- DistancePredicate const& m_dist_pred;
+ DistancesPredicates const& m_dist_pred;
Predicates const& m_pred;
Result & m_result;
Modified: sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/query.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/query.hpp (original)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/query.hpp 2011-09-27 15:31:01 EDT (Tue, 27 Sep 2011)
@@ -37,7 +37,7 @@
for (typename elements_type::const_iterator it = elements.begin();
it != elements.end(); ++it)
{
- if ( index::predicates_check<rtree::node_predicates_tag>(pred, it->first) )
+ if ( index::predicates_check<rtree::node_tag>(pred, it->first) )
rtree::apply_visitor(*this, *it->second);
}
}
@@ -50,7 +50,7 @@
for (typename elements_type::const_iterator it = elements.begin();
it != elements.end(); ++it)
{
- if ( index::predicates_check<rtree::value_predicates_tag>(pred, tr(*it)) )
+ if ( index::predicates_check<rtree::value_tag>(pred, tr(*it)) )
{
out_iter = *it;
++out_iter;
Added: sandbox-branches/geometry/index/boost/geometry/extensions/index/tuples.hpp
==============================================================================
--- (empty file)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/tuples.hpp 2011-09-27 15:31:01 EDT (Tue, 27 Sep 2011)
@@ -0,0 +1,185 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+//
+// Boost.SpatialIndex - tags related to rtree used in various files
+//
+// 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_TUPLES_HPP
+#define BOOST_GEOMETRY_EXTENSIONS_INDEX_TUPLES_HPP
+
+#include <boost/tuple/tuple.hpp>
+
+// TODO move this to index/tuples and separate algorithms
+
+namespace boost { namespace geometry { namespace index {
+
+namespace tuples {
+
+// find_index
+
+namespace detail {
+
+template <typename Tuple, typename El, size_t N>
+struct find_index;
+
+template <typename Tuple, typename El, size_t N, typename CurrentEl>
+struct find_index_impl
+{
+ static const size_t value = find_index<Tuple, El, N - 1>::value;
+};
+
+template <typename Tuple, typename El, size_t N>
+struct find_index_impl<Tuple, El, N, El>
+{
+ static const size_t value = N - 1;
+};
+
+template <typename Tuple, typename El, typename CurrentEl>
+struct find_index_impl<Tuple, El, 1, CurrentEl>
+{
+ BOOST_MPL_ASSERT_MSG(
+ (false),
+ ELEMENT_NOT_FOUND,
+ (find_index_impl));
+};
+
+template <typename Tuple, typename El>
+struct find_index_impl<Tuple, El, 1, El>
+{
+ static const size_t value = 0;
+};
+
+template <typename Tuple, typename El, size_t N>
+struct find_index
+{
+ static const size_t value =
+ find_index_impl<
+ Tuple,
+ El,
+ N,
+ typename boost::tuples::element<N - 1, Tuple>::type
+ >::value;
+};
+
+} // namespace detail
+
+template <typename Tuple, typename El>
+struct find_index
+{
+ static const size_t value =
+ detail::find_index<
+ Tuple,
+ El,
+ boost::tuples::length<Tuple>::value
+ >::value;
+};
+
+// types_equal
+
+template <typename T1, typename T2>
+struct equal
+{
+ static const bool value = false;
+};
+
+template <typename T>
+struct equal<T, T>
+{
+ static const bool value = true;
+};
+
+// has
+
+namespace detail {
+
+template <typename Tuple, typename El, size_t N>
+struct has
+{
+ static const bool value
+ = equal<
+ typename boost::tuples::element<N - 1, Tuple>::type,
+ El
+ >::value
+ || has<Tuple, El, N - 1>::value;
+};
+
+template <typename Tuple, typename El>
+struct has<Tuple, El, 1>
+{
+ static const bool value
+ = equal<
+ typename boost::tuples::element<0, Tuple>::type,
+ El
+ >::value;
+};
+
+} // namespace detail
+
+template <typename Tuple, typename El>
+struct has
+{
+ static const bool value
+ = detail::has<
+ Tuple,
+ El,
+ boost::tuples::length<Tuple>::value
+ >::value;
+};
+
+// add
+
+template <typename Tuple, typename El>
+struct add
+{
+ BOOST_MPL_ASSERT_MSG(
+ (false),
+ NOT_IMPLEMENTED_FOR_THIS_TUPLE_TYPE,
+ (add));
+};
+
+template <typename T1, typename T>
+struct add<boost::tuple<T1>, T>
+{
+ typedef boost::tuple<T1, T> type;
+};
+
+template <typename T1, typename T2, typename T>
+struct add<boost::tuple<T1, T2>, T>
+{
+ typedef boost::tuple<T1, T2, T> type;
+};
+
+// add_if
+
+template <typename Tuple, typename El, bool Cond>
+struct add_if
+{
+ typedef Tuple type;
+};
+
+template <typename Tuple, typename El>
+struct add_if<Tuple, El, true>
+{
+ typedef typename add<Tuple, El>::type type;
+};
+
+// add_unique
+
+template <typename Tuple, typename El>
+struct add_unique
+{
+ typedef typename add_if<
+ Tuple,
+ El,
+ !has<Tuple, El>::value
+ >::type type;
+};
+
+} // namespace tuples
+
+}}} // namespace boost::geometry::index
+
+#endif // BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_TAGS_HPP
Modified: sandbox-branches/geometry/index/tests/additional_glut_vis.cpp
==============================================================================
--- sandbox-branches/geometry/index/tests/additional_glut_vis.cpp (original)
+++ sandbox-branches/geometry/index/tests/additional_glut_vis.cpp 2011-09-27 15:31:01 EDT (Tue, 27 Sep 2011)
@@ -153,7 +153,14 @@
search_point = P(x, y);
nearest_boxes.clear();
- found_count = t.nearest(bgi::distance_centroid(search_point, min_distance, max_distance), count, std::back_inserter(nearest_boxes));
+ found_count = t.nearest(
+ bgi::bounded(
+ search_point,
+ bgi::far(min_distance),
+ bgi::near(max_distance)),
+ count,
+ std::back_inserter(nearest_boxes)
+ );
if ( found_count > 0 )
{
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-27 15:31:01 EDT (Tue, 27 Sep 2011)
@@ -23,6 +23,8 @@
#include <tests/rtree_function.hpp>
#include <tests/rtree_filters.hpp>
+#include <boost/geometry/extensions/index/rtree/rtree.hpp>
+
BOOST_AUTO_TEST_CASE( last_test_case )
{
tests_rtree_filters_hpp();
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-27 15:31:01 EDT (Tue, 27 Sep 2011)
@@ -164,7 +164,7 @@
for ( typename Cont::const_iterator it = c.begin() ; it != c.end() ; ++it )
{
- if ( bgi::predicates_check<bgi::detail::rtree::value_predicates_tag>(pred, t.get_translator()(*it)) )
+ if ( bgi::predicates_check<bgi::detail::rtree::value_tag>(pred, t.get_translator()(*it)) )
res2.push_back(*it);
}
@@ -213,7 +213,7 @@
for ( typename Cont::const_iterator it = c.begin() ; it != c.end() ; ++it )
{
- if ( bgi::predicates_check<bgi::detail::rtree::value_predicates_tag>(pred, t.get_translator()(*it)) )
+ if ( bgi::predicates_check<bgi::detail::rtree::value_tag>(pred, t.get_translator()(*it)) )
res2.push_back(*it);
}
std::sort(
Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk