Boost logo

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