|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r74604 - in sandbox-branches/geometry/index: boost/geometry/extensions/index boost/geometry/extensions/index/filters boost/geometry/extensions/index/rtree boost/geometry/extensions/index/rtree/visitors tests
From: adam.wulkiewicz_at_[hidden]
Date: 2011-09-28 19:29:52
Author: awulkiew
Date: 2011-09-28 19:29:50 EDT (Wed, 28 Sep 2011)
New Revision: 74604
URL: http://svn.boost.org/trac/boost/changeset/74604
Log:
additional predicates implemented.
Text files modified:
sandbox-branches/geometry/index/boost/geometry/extensions/index/filters/nearest_filter.hpp | 2
sandbox-branches/geometry/index/boost/geometry/extensions/index/filters/query_filter.hpp | 2
sandbox-branches/geometry/index/boost/geometry/extensions/index/predicates.hpp | 160 +++++++++++++++++++++++++++++++++++++--
sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/predicates.hpp | 102 ++++++++++++++++++++++++
sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/nearest.hpp | 2
sandbox-branches/geometry/index/tests/rtree_function.hpp | 29 ++++++-
6 files changed, 278 insertions(+), 19 deletions(-)
Modified: sandbox-branches/geometry/index/boost/geometry/extensions/index/filters/nearest_filter.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/extensions/index/filters/nearest_filter.hpp (original)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/filters/nearest_filter.hpp 2011-09-28 19:29:50 EDT (Wed, 28 Sep 2011)
@@ -40,6 +40,8 @@
namespace detail {
+// TODO: awulkiew - consider removing references from predicates
+
template<typename DistancesPredicates, typename Predicates>
struct nearest_filtered
{
Modified: sandbox-branches/geometry/index/boost/geometry/extensions/index/filters/query_filter.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/extensions/index/filters/query_filter.hpp (original)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/filters/query_filter.hpp 2011-09-28 19:29:50 EDT (Wed, 28 Sep 2011)
@@ -38,6 +38,8 @@
namespace detail {
+// TODO: awulkiew - consider removing reference from predicates
+
template<typename Predicates>
struct query_filtered
{
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-28 19:29:50 EDT (Wed, 28 Sep 2011)
@@ -25,6 +25,13 @@
struct empty {};
+template <typename ValuePredicate>
+struct value
+{
+ value(ValuePredicate const& vpred) : value_predicate(vpred) {}
+ ValuePredicate value_predicate;
+};
+
template <typename Geometry>
struct covered_by
{
@@ -33,6 +40,13 @@
};
template <typename Geometry>
+struct disjoint
+{
+ disjoint(Geometry const& g) : geometry(g) {}
+ Geometry geometry;
+};
+
+template <typename Geometry>
struct intersects
{
intersects(Geometry const& g) : geometry(g) {}
@@ -53,11 +67,39 @@
Geometry geometry;
};
-template <typename ValuePredicate>
-struct value
+template <typename Geometry>
+struct not_covered_by
{
- value(ValuePredicate const& vpred) : value_predicate(vpred) {}
- ValuePredicate value_predicate;
+ not_covered_by(Geometry const& g) : geometry(g) {}
+ Geometry geometry;
+};
+
+template <typename Geometry>
+struct not_disjoint
+{
+ not_disjoint(Geometry const& g) : geometry(g) {}
+ Geometry geometry;
+};
+
+template <typename Geometry>
+struct not_intersects
+{
+ not_intersects(Geometry const& g) : geometry(g) {}
+ Geometry geometry;
+};
+
+template <typename Geometry>
+struct not_overlaps
+{
+ not_overlaps(Geometry const& g) : geometry(g) {}
+ Geometry geometry;
+};
+
+template <typename Geometry>
+struct not_within
+{
+ not_within(Geometry const& g) : geometry(g) {}
+ Geometry geometry;
};
} // namespace detail
@@ -67,6 +109,12 @@
return detail::empty();
}
+template <typename ValuePredicate>
+inline detail::value<ValuePredicate> value(ValuePredicate const& vpred)
+{
+ return detail::value<ValuePredicate>(vpred);
+}
+
template <typename Geometry>
inline detail::covered_by<Geometry> covered_by(Geometry const& g)
{
@@ -74,6 +122,12 @@
}
template <typename Geometry>
+inline detail::disjoint<Geometry> disjoint(Geometry const& g)
+{
+ return detail::disjoint<Geometry>(g);
+}
+
+template <typename Geometry>
inline detail::intersects<Geometry> intersects(Geometry const& g)
{
return detail::intersects<Geometry>(g);
@@ -91,10 +145,34 @@
return detail::within<Geometry>(g);
}
-template <typename ValuePredicate>
-inline detail::value<ValuePredicate> value(ValuePredicate const& vpred)
+template <typename Geometry>
+inline detail::not_covered_by<Geometry> not_covered_by(Geometry const& g)
{
- return detail::value<ValuePredicate>(vpred);
+ return detail::not_covered_by<Geometry>(g);
+}
+
+template <typename Geometry>
+inline detail::not_disjoint<Geometry> not_disjoint(Geometry const& g)
+{
+ return detail::not_disjoint<Geometry>(g);
+}
+
+template <typename Geometry>
+inline detail::not_intersects<Geometry> not_intersects(Geometry const& g)
+{
+ return detail::not_intersects<Geometry>(g);
+}
+
+template <typename Geometry>
+inline detail::not_overlaps<Geometry> not_overlaps(Geometry const& g)
+{
+ return detail::not_overlaps<Geometry>(g);
+}
+
+template <typename Geometry>
+inline detail::not_within<Geometry> not_within(Geometry const& g)
+{
+ return detail::not_within<Geometry>(g);
}
namespace detail
@@ -131,6 +209,16 @@
}
};
+template <typename ValuePredicate, typename Tag>
+struct predicate_check<value<ValuePredicate>, Tag>
+{
+ template <typename Value, typename Indexable>
+ static inline bool apply(value<ValuePredicate> const& p, Value const& v, Indexable const&)
+ {
+ return p.value_predicate(v);
+ }
+};
+
template <typename Geometry, typename Tag>
struct predicate_check<covered_by<Geometry>, Tag>
{
@@ -142,6 +230,16 @@
};
template <typename Geometry, typename Tag>
+struct predicate_check<disjoint<Geometry>, Tag>
+{
+ template <typename Value, typename Indexable>
+ static inline bool apply(disjoint<Geometry> const& p, Value const&, Indexable const& i)
+ {
+ return geometry::disjoint(i, p.geometry);
+ }
+};
+
+template <typename Geometry, typename Tag>
struct predicate_check<intersects<Geometry>, Tag>
{
template <typename Value, typename Indexable>
@@ -171,13 +269,53 @@
}
};
-template <typename ValuePredicate, typename Tag>
-struct predicate_check<value<ValuePredicate>, Tag>
+template <typename Geometry, typename Tag>
+struct predicate_check<not_covered_by<Geometry>, Tag>
{
template <typename Value, typename Indexable>
- static inline bool apply(value<ValuePredicate> const& p, Value const& v, Indexable const&)
+ static inline bool apply(not_covered_by<Geometry> const& p, Value const&, Indexable const& i)
{
- return p.value_predicate(v);
+ return !geometry::covered_by(i, p.geometry);
+ }
+};
+
+template <typename Geometry, typename Tag>
+struct predicate_check<not_disjoint<Geometry>, Tag>
+{
+ template <typename Value, typename Indexable>
+ static inline bool apply(not_disjoint<Geometry> const& p, Value const&, Indexable const& i)
+ {
+ return !geometry::disjoint(i, p.geometry);
+ }
+};
+
+template <typename Geometry, typename Tag>
+struct predicate_check<not_intersects<Geometry>, Tag>
+{
+ template <typename Value, typename Indexable>
+ static inline bool apply(not_intersects<Geometry> const& p, Value const&, Indexable const& i)
+ {
+ return !geometry::intersects(i, p.geometry);
+ }
+};
+
+template <typename Geometry, typename Tag>
+struct predicate_check<not_overlaps<Geometry>, Tag>
+{
+ template <typename Value, typename Indexable>
+ static inline bool apply(not_overlaps<Geometry> const& p, Value const&, Indexable const& i)
+ {
+ return !geometry::overlaps(i, p.geometry);
+ }
+};
+
+template <typename Geometry, typename Tag>
+struct predicate_check<not_within<Geometry>, Tag>
+{
+ template <typename Value, typename Indexable>
+ static inline bool apply(not_within<Geometry> const& p, Value const&, Indexable const& i)
+ {
+ return !geometry::within(i, p.geometry);
}
};
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-28 19:29:50 EDT (Wed, 28 Sep 2011)
@@ -21,6 +21,36 @@
// then predicates_check must be implemented for nodes as well
template <typename Geometry>
+struct predicate_check<Geometry, rtree::node_tag>
+{
+ template <typename Value, typename Indexable>
+ static inline bool apply(Geometry const& g, Value const&, Indexable const& i)
+ {
+ return geometry::intersects(i, g);
+ }
+};
+
+template <>
+struct predicate_check<empty, rtree::node_tag>
+{
+ template <typename Geometry, typename Value, typename Indexable>
+ static inline bool apply(Geometry const&, Value const&, Indexable const&)
+ {
+ return true;
+ }
+};
+
+template <typename ValuePredicate>
+struct predicate_check<value<ValuePredicate>, rtree::node_tag>
+{
+ template <typename Value, typename Box>
+ static bool apply(value<ValuePredicate> const&, Value const&, Box const&)
+ {
+ return true;
+ }
+};
+
+template <typename Geometry>
struct predicate_check<covered_by<Geometry>, rtree::node_tag>
{
template <typename Value, typename Box>
@@ -31,6 +61,26 @@
};
template <typename Geometry>
+struct predicate_check<disjoint<Geometry>, rtree::node_tag>
+{
+ template <typename Value, typename Box>
+ static bool apply(disjoint<Geometry> const& p, Value const&, Box const& i)
+ {
+ return !geometry::covered_by(i, p.geometry);
+ }
+};
+
+template <typename Geometry>
+struct predicate_check<intersects<Geometry>, rtree::node_tag>
+{
+ template <typename Value, typename Indexable>
+ static inline bool apply(intersects<Geometry> const& p, Value const&, Indexable const& i)
+ {
+ return geometry::intersects(i, p.geometry);
+ }
+};
+
+template <typename Geometry>
struct predicate_check<overlaps<Geometry>, rtree::node_tag>
{
template <typename Value, typename Box>
@@ -54,16 +104,62 @@
}
};
-template <typename ValuePredicate>
-struct predicate_check<value<ValuePredicate>, rtree::node_tag>
+template <typename Geometry>
+struct predicate_check<not_covered_by<Geometry>, rtree::node_tag>
{
template <typename Value, typename Box>
- static bool apply(value<ValuePredicate> const&, Value const&, Box const&)
+ static bool apply(not_covered_by<Geometry> const& p, Value const&, Box const& i)
+ {
+ return !geometry::covered_by(i, p.geometry);
+ }
+};
+
+template <typename Geometry>
+struct predicate_check<not_disjoint<Geometry>, rtree::node_tag>
+{
+ template <typename Value, typename Box>
+ static bool apply(not_disjoint<Geometry> const& p, Value const&, Box const& i)
+ {
+ return !geometry::disjoint(i, p.geometry);
+ }
+};
+
+template <typename Geometry>
+struct predicate_check<not_intersects<Geometry>, rtree::node_tag>
+{
+ template <typename Value, typename Box>
+ static bool apply(not_intersects<Geometry> const& p, Value const&, Box const& i)
{
+ return !geometry::covered_by(i, p.geometry);
+ }
+};
+
+template <typename Geometry>
+struct predicate_check<not_overlaps<Geometry>, rtree::node_tag>
+{
+ template <typename Value, typename Box>
+ static bool apply(not_overlaps<Geometry> const& p, Value const&, Box const& i)
+ {
+ bool inters = geometry::intersects(i, p.geometry);
+
+ //return !inters || ( inters && !geometry::overlaps(i, p.geometry) );
+
+ // TODO: awulkiew - write working condition
+
return true;
}
};
+template <typename Geometry>
+struct predicate_check<not_within<Geometry>, rtree::node_tag>
+{
+ template <typename Value, typename Box>
+ static bool apply(not_within<Geometry> const& p, Value const&, Box const& i)
+ {
+ return !geometry::within(i, p.geometry);
+ }
+};
+
} // namespace detail
}}} // namespace boost::geometry::index
Modified: sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/nearest.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/nearest.hpp (original)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/nearest.hpp 2011-09-28 19:29:50 EDT (Wed, 28 Sep 2011)
@@ -125,6 +125,8 @@
std::vector< std::pair<distance_type, Value> > m_neighbors;
};
+// TODO: awulkiew - add additional pruning before adding nodes to the ABL
+
template <
typename Value,
typename Options,
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-28 19:29:50 EDT (Wed, 28 Sep 2011)
@@ -126,7 +126,7 @@
}
template <typename Cont, typename Translator>
- bool results_comp(Cont const& c1, Cont const& c2, Translator const& tr)
+ bool results_compare(Cont const& c1, Cont const& c2, Translator const& tr)
{
if ( c1.size() != c2.size() )
return false;
@@ -168,7 +168,10 @@
res2.push_back(*it);
}
- BOOST_CHECK( helpers::results_comp(res1, res2, t.get_translator()) );
+ std::stringstream ss;
+ ss << "\nPredicate: " << typeid(Predicate).name() << "\nres1: " << res1.size() << ", res2: " << res2.size() << '\n';
+
+ BOOST_CHECK_MESSAGE( helpers::results_compare(res1, res2, t.get_translator()), ss.str());
}
}
@@ -227,7 +230,10 @@
if ( k < res2.size() )
res2.resize(k);
- BOOST_CHECK( helpers::results_comp(res1, res2, t.get_translator()) );
+ std::stringstream ss;
+ ss << "\nPredicate: " << typeid(Predicate).name() << "\nres1: " << res1.size() << ", res2: " << res2.size() << '\n';
+
+ BOOST_CHECK_MESSAGE( helpers::results_compare(res1, res2, t.get_translator()), ss.str());
}
}
}
@@ -244,15 +250,21 @@
namespace bgi = boost::geometry::index;
helpers::random_query_check<B>(t, v, 5, helpers::value_randomizer<B>(10, 5));
+ helpers::random_query_check<bgi::detail::covered_by<B> >(t, v, 5, helpers::value_randomizer<B>(10, 5));
+ helpers::random_query_check<bgi::detail::disjoint<B> >(t, v, 5, helpers::value_randomizer<B>(10, 5));
helpers::random_query_check<bgi::detail::intersects<B> >(t, v, 5, helpers::value_randomizer<B>(10, 5));
helpers::random_query_check<bgi::detail::within<B> >(t, v, 5, helpers::value_randomizer<B>(10, 5));
- helpers::random_query_check<bgi::detail::covered_by<B> >(t, v, 5, helpers::value_randomizer<B>(10, 5));
+ helpers::random_query_check<bgi::detail::not_covered_by<B> >(t, v, 5, helpers::value_randomizer<B>(10, 5));
+ helpers::random_query_check<bgi::detail::not_disjoint<B> >(t, v, 5, helpers::value_randomizer<B>(10, 5));
+ helpers::random_query_check<bgi::detail::not_intersects<B> >(t, v, 5, helpers::value_randomizer<B>(10, 5));
+ helpers::random_query_check<bgi::detail::not_within<B> >(t, v, 5, helpers::value_randomizer<B>(10, 5));
helpers::random_nearest_check<bgi::detail::empty>(t, v, 5, helpers::value_randomizer<P>(10, 0), 3, bgi::empty);
helpers::random_nearest_check<B>(t, v, 5, helpers::value_randomizer<P>(10, 0), 3, helpers::value_randomizer<B>(10, 5));
helpers::random_nearest_check<bgi::detail::intersects<B> >(t, v, 5, helpers::value_randomizer<P>(10, 0), 3, helpers::value_randomizer<B>(10, 5));
helpers::random_nearest_check<bgi::detail::within<B> >(t, v, 5, helpers::value_randomizer<P>(10, 0), 3, helpers::value_randomizer<B>(10, 5));
helpers::random_nearest_check<bgi::detail::covered_by<B> >(t, v, 5, helpers::value_randomizer<P>(10, 0), 3, helpers::value_randomizer<B>(10, 5));
+ helpers::random_nearest_check<bgi::detail::disjoint<B> >(t, v, 5, helpers::value_randomizer<P>(10, 0), 3, helpers::value_randomizer<B>(10, 5));
}
};
@@ -265,10 +277,16 @@
namespace bgi = boost::geometry::index;
helpers::random_query_check<B>(t, v, 5, helpers::value_randomizer<B>(10, 5));
+ helpers::random_query_check<bgi::detail::covered_by<B> >(t, v, 5, helpers::value_randomizer<B>(10, 5));
+ helpers::random_query_check<bgi::detail::disjoint<B> >(t, v, 5, helpers::value_randomizer<B>(10, 5));
helpers::random_query_check<bgi::detail::intersects<B> >(t, v, 5, helpers::value_randomizer<B>(10, 5));
helpers::random_query_check<bgi::detail::overlaps<B> >(t, v, 5, helpers::value_randomizer<B>(10, 5));
helpers::random_query_check<bgi::detail::within<B> >(t, v, 5, helpers::value_randomizer<B>(10, 5));
- helpers::random_query_check<bgi::detail::covered_by<B> >(t, v, 5, helpers::value_randomizer<B>(10, 5));
+ helpers::random_query_check<bgi::detail::not_covered_by<B> >(t, v, 5, helpers::value_randomizer<B>(10, 5));
+ helpers::random_query_check<bgi::detail::not_disjoint<B> >(t, v, 5, helpers::value_randomizer<B>(10, 5));
+ helpers::random_query_check<bgi::detail::not_intersects<B> >(t, v, 5, helpers::value_randomizer<B>(10, 5));
+ helpers::random_query_check<bgi::detail::not_overlaps<B> >(t, v, 5, helpers::value_randomizer<B>(10, 5));
+ helpers::random_query_check<bgi::detail::not_within<B> >(t, v, 5, helpers::value_randomizer<B>(10, 5));
helpers::random_nearest_check<bgi::detail::empty>(t, v, 5, helpers::value_randomizer<P>(10, 0), 3, bgi::empty);
helpers::random_nearest_check<B>(t, v, 5, helpers::value_randomizer<P>(10, 0), 3, helpers::value_randomizer<B>(10, 5));
@@ -276,6 +294,7 @@
helpers::random_nearest_check<bgi::detail::overlaps<B> >(t, v, 5, helpers::value_randomizer<P>(10, 0), 3, helpers::value_randomizer<B>(10, 5));
helpers::random_nearest_check<bgi::detail::within<B> >(t, v, 5, helpers::value_randomizer<P>(10, 0), 3, helpers::value_randomizer<B>(10, 5));
helpers::random_nearest_check<bgi::detail::covered_by<B> >(t, v, 5, helpers::value_randomizer<P>(10, 0), 3, helpers::value_randomizer<B>(10, 5));
+ helpers::random_nearest_check<bgi::detail::disjoint<B> >(t, v, 5, helpers::value_randomizer<P>(10, 0), 3, helpers::value_randomizer<B>(10, 5));
}
};
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