|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r74558 - 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-25 05:54:45
Author: awulkiew
Date: 2011-09-25 05:54:42 EDT (Sun, 25 Sep 2011)
New Revision: 74558
URL: http://svn.boost.org/trac/boost/changeset/74558
Log:
knn query distance predicates (first version) implemented
Text files modified:
sandbox-branches/geometry/index/boost/geometry/extensions/index/distance_predicates.hpp | 82 +++++++++--------
sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/distance_predicates.hpp | 190 ++++++++++++++++++++++++++++++++-------
sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/rtree.hpp | 81 ++++++++++++----
sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/nearest.hpp | 71 ++++++++------
sandbox-branches/geometry/index/tests/additional_glut_vis.cpp | 70 ++++++++++----
5 files changed, 344 insertions(+), 150 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-25 05:54:42 EDT (Sun, 25 Sep 2011)
@@ -10,6 +10,10 @@
#ifndef BOOST_GEOMETRY_EXTENSIONS_INDEX_DISTANCE_PREDICATES_HPP
#define BOOST_GEOMETRY_EXTENSIONS_INDEX_DISTANCE_PREDICATES_HPP
+#include <boost/geometry/extensions/index/algorithms/comparable_distance_near.hpp>
+#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 {
namespace detail {
@@ -271,10 +275,10 @@
}
};
-// distance_check
+// distance_predicate_check
-template <typename Point, typename Tag>
-struct distance_check
+template <typename Point, typename Indexable, typename Tag>
+struct distance_predicate_check
{
template <typename DistanceType>
static inline bool apply(Point const&, DistanceType const&)
@@ -283,9 +287,10 @@
}
};
-template <typename Point, typename AlgoTag, typename Tag>
-struct distance_check<
+template <typename Point, typename AlgoTag, typename Indexable, typename Tag>
+struct distance_predicate_check<
detail::distance_unbounded<Point, AlgoTag>,
+ Indexable,
Tag>
{
template <typename DistanceType>
@@ -297,9 +302,10 @@
}
};
-template <typename Point, typename AlgoTag, typename Tag>
-struct distance_check<
+template <typename Point, typename AlgoTag, typename Indexable, typename Tag>
+struct distance_predicate_check<
detail::distance_half_bounded<Point, AlgoTag, detail::distance_min_tag>,
+ Indexable,
Tag>
{
template <typename DistanceType>
@@ -311,9 +317,10 @@
}
};
-template <typename Point, typename AlgoTag, typename Tag>
-struct distance_check<
+template <typename Point, typename AlgoTag, typename Indexable, typename Tag>
+struct distance_predicate_check<
detail::distance_half_bounded<Point, AlgoTag, detail::distance_max_tag>,
+ Indexable,
Tag>
{
template <typename DistanceType>
@@ -325,9 +332,10 @@
}
};
-template <typename Point, typename AlgoTag, typename Tag>
-struct distance_check<
+template <typename Point, typename AlgoTag, typename Indexable, typename Tag>
+struct distance_predicate_check<
detail::distance_bounded<Point, AlgoTag>,
+ Indexable,
Tag>
{
template <typename DistanceType>
@@ -339,38 +347,34 @@
}
};
-// move distance_calc and distance_comp into geometry::index ?
+// 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;
+};
-// 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>
+template <typename Point, typename AlgoTag>
+struct distance_point< detail::distance_bounded<Point, AlgoTag> >
+{
+ typedef Point type;
+};
} // 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_DISTANCE_PREDICATES_HPP
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-25 05:54:42 EDT (Sun, 25 Sep 2011)
@@ -11,6 +11,8 @@
#ifndef BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_DISTANCE_PREDICATES_HPP
#define BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_DISTANCE_PREDICATES_HPP
+#include <boost/geometry/extensions/index/distance_predicates.hpp>
+
namespace boost { namespace geometry { namespace index {
namespace detail {
@@ -26,7 +28,10 @@
// distance_calc
template <typename Point, typename Indexable>
-struct distance_calc<Point, Indexable, node_distance_predicate_tag>
+struct distance_calc<
+ Point,
+ Indexable,
+ rtree::node_distance_predicate_tag>
{
typedef typename geometry::default_distance_result<Point, Indexable>::type result_type;
@@ -36,60 +41,85 @@
}
};
-// TODO - finish specializations for nodes
-
-template <typename Point, typename AlgoTag, typename Indexable, typename Tag>
+template <typename Point, typename AlgoTag, typename Indexable>
struct distance_calc<
detail::distance_unbounded<Point, AlgoTag>,
Indexable,
- Tag>
+ rtree::node_distance_predicate_tag>
{
- typedef typename distance_calc_impl<Point, Indexable, AlgoTag>::result_type result_type;
+ typedef typename geometry::default_distance_result<Point, Indexable>::type result_type;
static inline result_type apply(
detail::distance_unbounded<Point, AlgoTag> const& dx,
Indexable const& i)
{
- return distance_calc_impl<Point, Indexable, AlgoTag>::apply(dx.point, i);
+ return index::comparable_distance_near(dx.point, i);
}
};
-template <typename Point, typename AlgoTag, typename LimitTag, typename Indexable, typename Tag>
+template <typename Point, typename AlgoTag, typename Indexable>
struct distance_calc<
- detail::distance_half_bounded<Point, AlgoTag, LimitTag>,
+ detail::distance_half_bounded<Point, AlgoTag, detail::distance_min_tag>,
Indexable,
- Tag>
+ rtree::node_distance_predicate_tag>
{
- typedef typename distance_calc_impl<Point, Indexable, AlgoTag>::result_type result_type;
+ 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)
+ );
+ }
+};
+
+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>
+{
+ typedef typename geometry::default_distance_result<Point, Indexable>::type result_type;
static inline result_type apply(
- detail::distance_half_bounded<Point, AlgoTag, LimitTag> const& dx,
+ detail::distance_half_bounded<Point, AlgoTag, detail::distance_max_tag> const& dx,
Indexable const& i)
{
- return distance_calc_impl<Point, Indexable, AlgoTag>::apply(dx.point, i);
+ return index::comparable_distance_near(dx.point, i);
}
};
-template <typename Point, typename AlgoTag, typename Indexable, typename Tag>
+template <typename Point, typename AlgoTag, typename Indexable>
struct distance_calc<
detail::distance_bounded<Point, AlgoTag>,
Indexable,
- Tag>
+ rtree::node_distance_predicate_tag>
{
- typedef typename distance_calc_impl<Point, Indexable, AlgoTag>::result_type result_type;
+ 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_bounded<Point, AlgoTag> const& dx,
Indexable const& i)
{
- return distance_calc_impl<Point, Indexable, AlgoTag>::apply(dx.point, i);
+ return std::make_pair(
+ index::comparable_distance_near(dx.point, i),
+ index::comparable_distance_far(dx.point, i)
+ );
}
};
-// distance_check
+// distance_predicate_check
-template <typename Point, typename Tag>
-struct distance_check
+template <typename Point, typename Indexable>
+struct distance_predicate_check<
+ Point,
+ Indexable,
+ rtree::node_distance_predicate_tag>
{
template <typename DistanceType>
static inline bool apply(Point const&, DistanceType const&)
@@ -98,10 +128,11 @@
}
};
-template <typename Point, typename AlgoTag, typename Tag>
-struct distance_check<
+template <typename Point, typename AlgoTag, typename Indexable>
+struct distance_predicate_check<
detail::distance_unbounded<Point, AlgoTag>,
- Tag>
+ Indexable,
+ rtree::node_distance_predicate_tag>
{
template <typename DistanceType>
static inline bool apply(
@@ -112,24 +143,26 @@
}
};
-template <typename Point, typename AlgoTag, typename Tag>
-struct distance_check<
+template <typename Point, typename AlgoTag, typename Indexable>
+struct distance_predicate_check<
detail::distance_half_bounded<Point, AlgoTag, detail::distance_min_tag>,
- Tag>
+ Indexable,
+ rtree::node_distance_predicate_tag>
{
template <typename DistanceType>
static inline bool apply(
detail::distance_half_bounded<Point, AlgoTag, detail::distance_min_tag> const& dx,
- DistanceType const& comparable_d)
+ DistanceType const& d)
{
- return dx.comparable_limit <= comparable_d;
+ return dx.comparable_limit <= d.second;
}
};
-template <typename Point, typename AlgoTag, typename Tag>
-struct distance_check<
+template <typename Point, typename AlgoTag, typename Indexable>
+struct distance_predicate_check<
detail::distance_half_bounded<Point, AlgoTag, detail::distance_max_tag>,
- Tag>
+ Indexable,
+ rtree::node_distance_predicate_tag>
{
template <typename DistanceType>
static inline bool apply(
@@ -140,20 +173,105 @@
}
};
-template <typename Point, typename AlgoTag, typename Tag>
-struct distance_check<
+template <typename Point, typename AlgoTag, typename Indexable>
+struct distance_predicate_check<
detail::distance_bounded<Point, AlgoTag>,
- Tag>
+ Indexable,
+ rtree::node_distance_predicate_tag>
{
template <typename DistanceType>
static inline bool apply(
detail::distance_bounded<Point, AlgoTag> const& dx,
- DistanceType const& comparable_d)
+ DistanceType const& d)
{
- return dx.comparable_min <= comparable_d && comparable_d <= dx.comparable_max;
+ 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)
+ {
+ return sd < nd.first;
+ }
+};
+
+} // namespace rtree
+
// move distance_calc and distance_comp into geometry::index ?
// TODO: awulkiew - pruning for nodes! <- inside detail::rtree so NOT HERE
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-25 05:54:42 EDT (Sun, 25 Sep 2011)
@@ -40,6 +40,7 @@
namespace boost { namespace geometry { namespace index {
// TODO copying
+// TODO move extensional/debug visitors to the other folder
template <
typename Value,
@@ -94,28 +95,28 @@
// TODO: awulkiew - change Point to Geometry?
// return number of elements instead of bool?
- template <typename Point>
- inline size_t nearest(Point const& pt, value_type & v) const
+ template <typename DistancePredicate>
+ inline size_t nearest(DistancePredicate const& p, value_type & v) const
{
- return nearest_one(pt, detail::empty(), v);
+ return nearest_one(p, detail::empty(), v);
}
- template <typename Point, typename Predicates>
- inline size_t nearest(Point const& pt, Predicates const& pred, value_type & v) const
+ template <typename DistancePredicate, typename Predicates>
+ inline size_t nearest(DistancePredicate const& p, Predicates const& pred, value_type & v) const
{
- return nearest_one(pt, pred, v);
+ return nearest_one(p, pred, v);
}
- template <typename Point, typename OutIter>
- inline size_t nearest(Point const& pt, size_t k, OutIter out_it) const
+ template <typename DistancePredicate, typename OutIter>
+ inline size_t nearest(DistancePredicate const& p, size_t k, OutIter out_it) const
{
- return nearest_k(pt, k, detail::empty(), out_it);
+ return nearest_k(p, k, detail::empty(), out_it);
}
- template <typename Point, typename Predicates, typename OutIter>
- inline size_t nearest(Point const& pt, size_t k, Predicates const& pred, OutIter out_it) const
+ template <typename DistancePredicate, typename Predicates, typename OutIter>
+ inline size_t nearest(DistancePredicate const& p, size_t k, Predicates const& pred, OutIter out_it) const
{
- return nearest_k(pt, k, pred, out_it);
+ return nearest_k(p, k, pred, out_it);
}
inline void insert(value_type const& value)
@@ -187,28 +188,52 @@
}
private:
- template <typename Point, typename Predicates>
- inline size_t nearest_one(Point const& pt, Predicates const& pred, value_type & v) const
+ template <typename DistancePredicate, typename Predicates>
+ inline size_t nearest_one(DistancePredicate const& p, Predicates const& pred, value_type & v) const
{
- typedef detail::rtree::visitors::nearest_one<value_type, translator_type, Point> result_type;
+ typedef detail::rtree::visitors::nearest_one<
+ value_type,
+ translator_type,
+ typename detail::distance_point<DistancePredicate>::type
+ > result_type;
+
result_type result;
- detail::rtree::visitors::nearest<value_type, options_type, translator_type, box_type, Point, Predicates, result_type>
- nearest_v(m_translator, pt, pred, result);
+ detail::rtree::visitors::nearest<
+ value_type,
+ options_type,
+ translator_type,
+ box_type,
+ DistancePredicate,
+ Predicates,
+ result_type
+ > nearest_v(m_translator, p, pred, result);
detail::rtree::apply_visitor(nearest_v, *m_root);
return result.get(v);
}
- template <typename Point, typename Predicates, typename OutIter>
- inline size_t nearest_k(Point const& pt, size_t k, Predicates const& pred, OutIter out_it) const
+ 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
{
- typedef detail::rtree::visitors::nearest_k<value_type, translator_type, Point> result_type;
+ typedef detail::rtree::visitors::nearest_k<
+ value_type,
+ translator_type,
+ typename detail::distance_point<DistancePredicate>::type
+ > result_type;
+
result_type result(k);
- detail::rtree::visitors::nearest<value_type, options_type, translator_type, box_type, Point, Predicates, result_type>
- nearest_v(m_translator, pt, pred, result);
+ detail::rtree::visitors::nearest<
+ value_type,
+ options_type,
+ translator_type,
+ box_type,
+ DistancePredicate,
+ Predicates,
+ result_type
+ > nearest_v(m_translator, p, pred, result);
detail::rtree::apply_visitor(nearest_v, *m_root);
@@ -263,6 +288,18 @@
return tree.nearest(pt, k, pred, out_it);
}
+template <typename Value, typename Options, typename Translator>
+inline size_t size(rtree<Value, Options, Translator> const& tree)
+{
+ return tree.size();
+}
+
+template <typename Value, typename Options, typename Translator>
+inline bool empty(rtree<Value, Options, Translator> const& tree)
+{
+ return tree.empty();
+}
+
}}} // namespace boost::geometry::index
#endif // BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_RTREE_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-25 05:54:42 EDT (Sun, 25 Sep 2011)
@@ -10,11 +10,7 @@
#ifndef BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_VISITORS_NEAREST_HPP
#define BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_VISITORS_NEAREST_HPP
-#include <boost/geometry/extensions/index/algorithms/comparable_distance_near.hpp>
-#include <boost/geometry/extensions/index/algorithms/comparable_distance_far.hpp>
-#include <boost/geometry/extensions/index/algorithms/comparable_distance_centroid.hpp>
-
-#include <boost/geometry/extensions/index/distance_predicates.hpp>
+#include <boost/geometry/extensions/index/rtree/distance_predicates.hpp>
#include <boost/geometry/extensions/index/rtree/node/node.hpp>
@@ -134,7 +130,7 @@
typename Options,
typename Translator,
typename Box,
- typename PointData,
+ typename DistancePredicate,
typename Predicates,
typename Result
>
@@ -147,10 +143,17 @@
typedef typename rtree::internal_node<Value, typename Options::parameters_type, Box, typename Options::node_tag>::type internal_node;
typedef typename rtree::leaf<Value, typename Options::parameters_type, Box, typename Options::node_tag>::type leaf;
- typedef typename geometry::default_distance_result<PointData, Box>::type node_distance_type;
+ 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;
- inline nearest(Translator const& t, PointData const& point_data, Predicates const& pr, Result & r)
- : m_tr(t), m_point_data(point_data), m_pred(pr)
+ inline nearest(Translator const& t, DistancePredicate const& dist_pred, Predicates const& pred, Result & r)
+ : m_tr(t), m_dist_pred(dist_pred), m_pred(pred)
, m_result(r)
{}
@@ -159,11 +162,10 @@
inline void operator()(internal_node const& n)
{
// array of active nodes
- /*index::pushable_array<
+ index::pushable_array<
std::pair<node_distance_type, const node *>,
Options::parameters_type::max_elements
- > active_branch_list;*/
- std::vector< std::pair<node_distance_type, const node *> > active_branch_list;
+ > active_branch_list;
typedef typename rtree::elements_type<internal_node>::type elements_type;
elements_type const& elements = rtree::elements(n);
@@ -172,14 +174,18 @@
for (typename elements_type::const_iterator it = elements.begin();
it != elements.end(); ++it)
{
+ // if current node meets predicates
if ( index::predicates_check<rtree::node_predicates_tag>(m_pred, it->first) )
{
- active_branch_list.push_back(
- std::make_pair(
- index::comparable_distance_near(m_point_data, it->first),
- it->second
- )
- );
+ // calculate node's distance(s) for distance predicate
+ node_distance_type node_dist_data = node_distance_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) )
+ {
+ // add current node's data into the list
+ active_branch_list.push_back( std::make_pair(node_dist_data, it->second) );
+ }
}
}
@@ -188,7 +194,7 @@
return;
// sort array
- std::sort(active_branch_list.begin(), active_branch_list.end(), abl_mindist_less);
+ std::sort(active_branch_list.begin(), active_branch_list.end(), node_distance_less());
// recursively visit nodes
for ( size_t i = 0 ;; ++i )
@@ -212,25 +218,23 @@
for (typename elements_type::const_iterator it = elements.begin();
it != elements.end(); ++it)
{
+ // if value meets predicates
if ( index::predicates_check<rtree::value_predicates_tag>(m_pred, m_tr(*it)) )
{
- // store value
- m_result.store(
- *it,
- index::comparable_distance_near(m_point_data, m_tr(*it))
- );
+ // calculate values distance for distance predicate
+ value_distance_type dist = value_distance_calc::apply(m_dist_pred, m_tr(*it));
+
+ // if distance meets distance predicate
+ if ( value_distance_predicate_check::apply(m_dist_pred, dist) )
+ {
+ // store value
+ m_result.store(*it, dist);
+ }
}
}
}
private:
- inline static bool abl_mindist_less(
- std::pair<node_distance_type, const node *> const& p1,
- std::pair<node_distance_type, const node *> const& p2)
- {
- return p1.first < p2.first;
- }
-
template <typename ActiveBranchList>
inline void prune_nodes(ActiveBranchList & abl) const
{
@@ -239,7 +243,8 @@
{
// prune if box's mindist is further than value's mindist
while ( !abl.empty() &&
- m_result.comparable_distance() < abl.back().first )
+ distance_node_pruning_check<DistancePredicate, Box>
+ ::apply(m_result.comparable_distance(), abl.back().first) )
{
abl.pop_back();
}
@@ -247,7 +252,7 @@
}
Translator const& m_tr;
- PointData const& m_point_data;
+ DistancePredicate const& m_dist_pred;
Predicates const& m_pred;
Result & m_result;
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-25 05:54:42 EDT (Sun, 25 Sep 2011)
@@ -26,24 +26,51 @@
boost::geometry::index::rstar<4, 2> > t;
std::vector<B> vect;
-bool is_nearest = false;
+size_t found_count = 0;
P search_point;
+float min_distance = 20;
+float max_distance = 30;
+size_t count = 10;
std::vector<B> nearest_boxes;
+void draw_search_area()
+{
+ float x = boost::geometry::get<0>(search_point);
+ float y = boost::geometry::get<1>(search_point);
+ float z = t.depth();
+
+ // search point
+ glBegin(GL_TRIANGLES);
+ glVertex3f(x, y, z);
+ glVertex3f(x + 1, y, z);
+ glVertex3f(x + 1, y + 1, z);
+ glEnd();
+
+ // search min circle
+
+ glBegin(GL_LINE_LOOP);
+ for(float a = 0 ; a < 3.14158f * 2 ; a += 3.14158f / 180)
+ glVertex3f(x + min_distance * ::cos(a), y + min_distance * ::sin(a), z);
+ glEnd();
+
+ // search max circle
+
+ glBegin(GL_LINE_LOOP);
+ for(float a = 0 ; a < 3.14158f * 2 ; a += 3.14158f / 180)
+ glVertex3f(x + max_distance * ::cos(a), y + max_distance * ::sin(a), z);
+ glEnd();
+}
+
void render_scene(void)
{
glClear(GL_COLOR_BUFFER_BIT);
boost::geometry::index::gl_draw(t);
- if ( is_nearest )
+ if ( found_count > 0 )
{
glColor3f(1.0f, 0.5f, 0.0f);
- glBegin(GL_TRIANGLES);
- glVertex3f(boost::geometry::get<0>(search_point), boost::geometry::get<1>(search_point), t.depth());
- glVertex3f(boost::geometry::get<0>(search_point) + 1, boost::geometry::get<1>(search_point), t.depth());
- glVertex3f(boost::geometry::get<0>(search_point) + 1, boost::geometry::get<1>(search_point) + 1, t.depth());
- glEnd();
+ draw_search_area();
for ( size_t i = 0 ; i < nearest_boxes.size() ; ++i )
boost::geometry::index::detail::rtree::visitors::detail::gl_draw_indexable(nearest_boxes[i], t.depth());
@@ -75,6 +102,9 @@
void mouse(int button, int state, int x, int y)
{
+ namespace bg = boost::geometry;
+ namespace bgi = bg::index;
+
if ( button == GLUT_LEFT_BUTTON && state == GLUT_DOWN )
{
float x = ( rand() % 100 );
@@ -88,12 +118,12 @@
vect.push_back(b);
std::cout << "inserted: ";
- boost::geometry::index::detail::rtree::visitors::detail::print_indexable(std::cout, b);
+ bgi::detail::rtree::visitors::detail::print_indexable(std::cout, b);
std::cout << '\n';
std::cout << "\n" << t << "\n";
- std::cout << ( boost::geometry::index::are_boxes_ok(t) ? "boxes OK\n" : "WRONG BOXES!\n" );
- std::cout << ( boost::geometry::index::are_levels_ok(t) ? "levels OK\n" : "WRONG LEVELS!\n" );
+ std::cout << ( bgi::are_boxes_ok(t) ? "boxes OK\n" : "WRONG BOXES!\n" );
+ std::cout << ( bgi::are_levels_ok(t) ? "levels OK\n" : "WRONG LEVELS!\n" );
std::cout << "\n";
}
else if ( button == GLUT_RIGHT_BUTTON && state == GLUT_DOWN )
@@ -104,16 +134,16 @@
size_t i = rand() % vect.size();
B b = vect[i];
- boost::geometry::index::remove(t, b);
+ bgi::remove(t, b);
vect.erase(vect.begin() + i);
std::cout << "removed: ";
- boost::geometry::index::detail::rtree::visitors::detail::print_indexable(std::cout, b);
+ bgi::detail::rtree::visitors::detail::print_indexable(std::cout, b);
std::cout << '\n';
std::cout << "\n" << t << "\n";
- std::cout << ( boost::geometry::index::are_boxes_ok(t) ? "boxes OK\n" : "WRONG BOXES!\n" );
- std::cout << ( boost::geometry::index::are_levels_ok(t) ? "levels OK\n" : "WRONG LEVELS!\n" );
+ std::cout << ( bgi::are_boxes_ok(t) ? "boxes OK\n" : "WRONG BOXES!\n" );
+ std::cout << ( bgi::are_levels_ok(t) ? "levels OK\n" : "WRONG LEVELS!\n" );
std::cout << "\n";
}
else if ( button == GLUT_MIDDLE_BUTTON && state == GLUT_DOWN )
@@ -123,16 +153,16 @@
search_point = P(x, y);
nearest_boxes.clear();
- is_nearest = t.nearest(search_point, 3, std::back_inserter(nearest_boxes));
+ found_count = t.nearest(bgi::distance_centroid(search_point, min_distance, max_distance), count, std::back_inserter(nearest_boxes));
- if ( is_nearest )
+ if ( found_count > 0 )
{
std::cout << "search point: ";
- boost::geometry::index::detail::rtree::visitors::detail::print_indexable(std::cout, search_point);
+ bgi::detail::rtree::visitors::detail::print_indexable(std::cout, search_point);
std::cout << "\nfound: ";
for ( size_t i = 0 ; i < nearest_boxes.size() ; ++i )
{
- boost::geometry::index::detail::rtree::visitors::detail::print_indexable(std::cout, nearest_boxes[i]);
+ bgi::detail::rtree::visitors::detail::print_indexable(std::cout, nearest_boxes[i]);
std::cout << '\n';
}
}
@@ -140,8 +170,8 @@
std::cout << "nearest not found\n";
std::cout << "\n" << t << "\n";
- std::cout << ( boost::geometry::index::are_boxes_ok(t) ? "boxes OK\n" : "WRONG BOXES!\n" );
- std::cout << ( boost::geometry::index::are_levels_ok(t) ? "levels OK\n" : "WRONG LEVELS!\n" );
+ std::cout << ( bgi::are_boxes_ok(t) ? "boxes OK\n" : "WRONG BOXES!\n" );
+ std::cout << ( bgi::are_levels_ok(t) ? "levels OK\n" : "WRONG LEVELS!\n" );
std::cout << "\n";
}
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