Subject: [Boost-commit] svn:boost r85630 - in trunk: boost/geometry/index boost/geometry/index/detail/algorithms libs/geometry/doc libs/geometry/index/test/rtree
From: adam.wulkiewicz_at_[hidden]
Date: 2013-09-09 18:37:56
Author: awulkiew
Date: 2013-09-09 18:37:55 EDT (Mon, 09 Sep 2013)
New Revision: 85630
URL: http://svn.boost.org/trac/boost/changeset/85630
Log:
[geometry]: iterative queries simplified, docs updated, added qbegin() and qend() free functions, added new functions to the reference matrix, release notes updated.
Text files modified:
trunk/boost/geometry/index/detail/algorithms/segment_intersection.hpp | 6 +
trunk/boost/geometry/index/rtree.hpp | 141 ++++++++++++++++++++++++++++++++++++++-
trunk/libs/geometry/doc/quickref.xml | 6 +
trunk/libs/geometry/doc/release_notes.qbk | 6 +
trunk/libs/geometry/index/test/rtree/test_rtree.hpp | 37 ++++++---
5 files changed, 175 insertions(+), 21 deletions(-)
Modified: trunk/boost/geometry/index/detail/algorithms/segment_intersection.hpp
==============================================================================
--- trunk/boost/geometry/index/detail/algorithms/segment_intersection.hpp Mon Sep 9 16:29:22 2013 (r85629)
+++ trunk/boost/geometry/index/detail/algorithms/segment_intersection.hpp 2013-09-09 18:37:55 EDT (Mon, 09 Sep 2013) (r85630)
@@ -34,8 +34,10 @@
template <typename Box, typename Point, size_t I>
struct box_segment_intersection_dim
{
- BOOST_STATIC_ASSERT(I < dimension<Box>::value);
- BOOST_STATIC_ASSERT(I < dimension<Point>::value);
+ BOOST_STATIC_ASSERT(0 <= dimension<Box>::value);
+ BOOST_STATIC_ASSERT(0 <= dimension<Point>::value);
+ BOOST_STATIC_ASSERT(I < size_t(dimension<Box>::value));
+ BOOST_STATIC_ASSERT(I < size_t(dimension<Point>::value));
BOOST_STATIC_ASSERT(dimension<Point>::value == dimension<Box>::value);
// WARNING! - RelativeDistance must be IEEE float for this to work
Modified: trunk/boost/geometry/index/rtree.hpp
==============================================================================
--- trunk/boost/geometry/index/rtree.hpp Mon Sep 9 16:29:22 2013 (r85629)
+++ trunk/boost/geometry/index/rtree.hpp 2013-09-09 18:37:55 EDT (Mon, 09 Sep 2013) (r85630)
@@ -190,7 +190,7 @@
/*! \brief Unsigned integral type used by the container. */
typedef typename allocators_type::size_type size_type;
- /*! \brief The type-erased const query iterator. */
+ /*! \brief Type of const query iterator. */
typedef index::detail::rtree::iterators::query_iterator<value_type, allocators_type> const_query_iterator;
public:
@@ -772,6 +772,68 @@
This method returns the iterator which may be used to perform iterative queries. For the information
about the predicates which may be passed to this method see query().
+ \par Example
+ \verbatim
+
+ for ( Rtree::const_query_iterator it = tree.qbegin(bgi::nearest(pt, 10000)) ;
+ it != tree.qend() ; ++it )
+ {
+ // do something with value
+ if ( has_enough_nearest_values() )
+ break;
+ }
+ \endverbatim
+
+ \par Throws
+ If predicates copy throws.
+ If allocation throws.
+
+ \param predicates Predicates.
+
+ \return The iterator pointing at the begin of the query range.
+ */
+ template <typename Predicates>
+ const_query_iterator qbegin(Predicates const& predicates) const
+ {
+ return const_query_iterator(qbegin_(predicates));
+ }
+
+ /*!
+ \brief Returns the query iterator pointing at the end of the query range.
+
+ This method returns the iterator which may be used to check if the query has ended.
+
+ \par Example
+ \verbatim
+
+ for ( Rtree::const_query_iterator it = tree.qbegin(bgi::nearest(pt, 10000)) ;
+ it != tree.qend() ; ++it )
+ {
+ // do something with value
+ if ( has_enough_nearest_values() )
+ break;
+ }
+ \endverbatim
+
+ \par Throws
+ Nothing
+
+ \return The iterator pointing at the end of the query range.
+ */
+ const_query_iterator qend() const
+ {
+ return const_query_iterator();
+ }
+
+#ifndef BOOST_GEOMETRY_INDEX_DETAIL_EXPERIMENTAL
+private:
+#endif
+ /*!
+ \brief Returns the query iterator pointing at the begin of the query range.
+
+ This method returns the iterator which may be used to perform iterative queries. For the information
+ about the predicates which may be passed to this method see query().
+
The type of the returned iterator depends on the type of passed Predicates but the iterator of this type
may be assigned to the variable of const_query_iterator type. If you'd like to use the type of the iterator
returned by this method you may get the type e.g. by using C++11 decltype or Boost.Typeof library.
@@ -814,7 +876,7 @@
detail::predicates_find_distance<Predicates>::value
>
>::type
- qbegin(Predicates const& predicates) const
+ qbegin_(Predicates const& predicates) const
{
static const unsigned distance_predicates_count = detail::predicates_count_distance<Predicates>::value;
BOOST_MPL_ASSERT_MSG((distance_predicates_count <= 1), PASS_ONLY_ONE_DISTANCE_PREDICATE, (Predicates));
@@ -869,7 +931,7 @@
detail::predicates_find_distance<Predicates>::value
>
>::type
- qend(Predicates const& predicates) const
+ qend_(Predicates const& predicates) const
{
static const unsigned distance_predicates_count = detail::predicates_count_distance<Predicates>::value;
BOOST_MPL_ASSERT_MSG((distance_predicates_count <= 1), PASS_ONLY_ONE_DISTANCE_PREDICATE, (Predicates));
@@ -922,11 +984,13 @@
\return The iterator pointing at the end of the query range.
*/
detail::rtree::iterators::end_query_iterator<value_type, allocators_type>
- qend() const
+ qend_() const
{
return detail::rtree::iterators::end_query_iterator<value_type, allocators_type>();
}
+public:
+
/*!
\brief Returns the number of stored values.
@@ -1620,6 +1684,75 @@
}
/*!
+\brief Returns the query iterator pointing at the begin of the query range.
+
+This method returns the iterator which may be used to perform iterative queries. For the information
+about the predicates which may be passed to this method see query().
+
+\par Example
+\verbatim
+
+for ( Rtree::const_query_iterator it = qbegin(tree, bgi::nearest(pt, 10000)) ;
+ it != qend(tree) ; ++it )
+{
+ // do something with value
+ if ( has_enough_nearest_values() )
+ break;
+}
+\endverbatim
+
+\par Throws
+If predicates copy throws.
+If allocation throws.
+
+\ingroup rtree_functions
+
+\param tree The rtree.
+\param predicates Predicates.
+
+\return The iterator pointing at the begin of the query range.
+*/
+template <typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator,
+ typename Predicates> inline
+typename rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator>::const_query_iterator
+qbegin(rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> const& tree,
+ Predicates const& predicates)
+{
+ return tree.qbegin(predicates);
+}
+
+/*!
+\brief Returns the query iterator pointing at the end of the query range.
+
+This method returns the iterator which may be used to check if the query has ended.
+
+\par Example
+\verbatim
+
+for ( Rtree::const_query_iterator it = qbegin(tree, bgi::nearest(pt, 10000)) ;
+ it != qend(tree) ; ++it )
+{
+ // do something with value
+ if ( has_enough_nearest_values() )
+ break;
+}
+\endverbatim
+
+\par Throws
+Nothing
+
+\ingroup rtree_functions
+
+\return The iterator pointing at the end of the query range.
+*/
+template <typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator> inline
+typename rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator>::const_query_iterator
+qend(rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> const& tree)
+{
+ return tree.qend();
+}
+
+/*!
\brief Remove all values from the index.
It calls \c rtree::clear().
Modified: trunk/libs/geometry/doc/quickref.xml
==============================================================================
--- trunk/libs/geometry/doc/quickref.xml Mon Sep 9 16:29:22 2013 (r85629)
+++ trunk/libs/geometry/doc/quickref.xml 2013-09-09 18:37:55 EDT (Mon, 09 Sep 2013) (r85630)
@@ -680,6 +680,8 @@
<member><link linkend="geometry.reference.spatial_indexes.boost__geometry__index__rtree.remove_iterator__iterator_">remove(Iterator, Iterator)</link></member>
<member><link linkend="geometry.reference.spatial_indexes.boost__geometry__index__rtree.remove_range_const___">remove(Range const &)</link></member>
<member><link linkend="geometry.reference.spatial_indexes.boost__geometry__index__rtree.query_predicates_const____outiter_">query(Predicates const &, OutIter)</link></member>
+ <member><link linkend="geometry.reference.spatial_indexes.boost__geometry__index__rtree.qbegin_predicates_const___">qbegin(Predicates const &)</link></member>
+ <member><link linkend="geometry.reference.spatial_indexes.boost__geometry__index__rtree.qend__">qend()</link></member>
<member><link linkend="geometry.reference.spatial_indexes.boost__geometry__index__rtree.size__">size()</link></member>
<member><link linkend="geometry.reference.spatial_indexes.boost__geometry__index__rtree.empty__">empty()</link></member>
<member><link linkend="geometry.reference.spatial_indexes.boost__geometry__index__rtree.clear__">clear()</link></member>
@@ -701,6 +703,8 @@
<member><link linkend="geometry.reference.spatial_indexes.group__rtree__functions.remove_rtree_________iterator__iterator_">remove(rtree<...> &, Iterator, Iterator)</link></member>
<member><link linkend="geometry.reference.spatial_indexes.group__rtree__functions.remove_rtree_________range_const___">remove(rtree<...> &, Range const &)</link></member>
<member><link linkend="geometry.reference.spatial_indexes.group__rtree__functions.query_rtree______const____predicates_const____outiter_">query(rtree<...> const &, Predicates const &, OutIter)</link></member>
+ <member><link linkend="geometry.reference.spatial_indexes.group__rtree__functions.qbegin_rtree______const____predicates_const___">qbegin(rtree<...> const &, Predicates const &)</link></member>
+ <member><link linkend="geometry.reference.spatial_indexes.group__rtree__functions.qend_rtree______const___">qend(rtree<...> const &)</link></member>
<member><link linkend="geometry.reference.spatial_indexes.group__rtree__functions.clear_rtree________">clear(rtree<...> &)</link></member>
<member><link linkend="geometry.reference.spatial_indexes.group__rtree__functions.size_rtree______const___">size(rtree<...> const &)</link></member>
<member><link linkend="geometry.reference.spatial_indexes.group__rtree__functions.empty_rtree______const___">empty(rtree<...> const &)</link></member>
@@ -728,7 +732,9 @@
<entry valign="top">
<bridgehead renderas="sect3">Predicates (boost::geometry::index::)</bridgehead>
<simplelist type="vert" columns="1">
+ <member><link linkend="geometry.reference.spatial_indexes.group__predicates.contains_geometry_const___">contains(Geometry const &)</link></member>
<member><link linkend="geometry.reference.spatial_indexes.group__predicates.covered_by_geometry_const___">covered_by(Geometry const &)</link></member>
+ <member><link linkend="geometry.reference.spatial_indexes.group__predicates.covers_geometry_const___">covers(Geometry const &)</link></member>
<member><link linkend="geometry.reference.spatial_indexes.group__predicates.disjoint_geometry_const___">disjoint(Geometry const &)</link></member>
<member><link linkend="geometry.reference.spatial_indexes.group__predicates.intersects_geometry_const___">intersects(Geometry const &)</link></member>
<member><link linkend="geometry.reference.spatial_indexes.group__predicates.overlaps_geometry_const___">overlaps(Geometry const &)</link></member>
Modified: trunk/libs/geometry/doc/release_notes.qbk
==============================================================================
--- trunk/libs/geometry/doc/release_notes.qbk Mon Sep 9 16:29:22 2013 (r85629)
+++ trunk/libs/geometry/doc/release_notes.qbk 2013-09-09 18:37:55 EDT (Mon, 09 Sep 2013) (r85630)
@@ -20,6 +20,10 @@
[*Additional functionality]
* Added centroid for segment type
+* Added intersects() and disjoints() for Segment-Box and Linestring-Box
+* Added rtree creation using packing algorithm
+* Added contains() and covers() spatial query predicates
+* Added iterative queries
[*Documentation]
@@ -43,7 +47,7 @@
* Transform-strategy TODO
* Spikes (could be generated in difference) in integer-based overlays are now avoided during generation
* Cleanup, removed old MSVC2005 project files, let all tests pass green (also in extensions)
-
+* R*-tree balancing algorithm optimized
[/=================]
[heading Boost 1.54]
Modified: trunk/libs/geometry/index/test/rtree/test_rtree.hpp
==============================================================================
--- trunk/libs/geometry/index/test/rtree/test_rtree.hpp Mon Sep 9 16:29:22 2013 (r85629)
+++ trunk/libs/geometry/index/test/rtree/test_rtree.hpp 2013-09-09 18:37:55 EDT (Mon, 09 Sep 2013) (r85630)
@@ -642,6 +642,14 @@
}
}
+// alternative version of std::copy taking iterators of differnet types
+template <typename First, typename Last, typename Out>
+void copy_alt(First first, Last last, Out out)
+{
+ for ( ; first != last ; ++first, ++out )
+ *out = *first;
+}
+
// spatial query
template <typename Rtree, typename Value, typename Predicates>
@@ -666,22 +674,25 @@
exactly_the_same_outputs(rtree, output, rtree | bgi::adaptors::queried(pred));
std::vector<Value> output3;
- std::copy(rtree.qbegin(pred), rtree.qend(pred), std::back_inserter(output3));
+ std::copy(rtree.qbegin(pred), rtree.qend(), std::back_inserter(output3));
compare_outputs(rtree, output3, expected_output);
+ std::vector<Value> output4;
+ std::copy(qbegin(rtree, pred), qend(rtree), std::back_inserter(output4));
+
+ exactly_the_same_outputs(rtree, output3, output4);
+
+#ifdef BOOST_GEOMETRY_INDEX_DETAIL_EXPERIMENTAL
{
- typedef typename Rtree::const_query_iterator QI;
- QI first = rtree.qbegin(pred);
- QI last = rtree.qend(pred);
std::vector<Value> output4;
- std::copy(first, last, std::back_inserter(output4));
+ std::copy(rtree.qbegin_(pred), rtree.qend_(pred), std::back_inserter(output4));
compare_outputs(rtree, output4, expected_output);
- QI last2 = rtree.qend();
output4.clear();
- std::copy(first, last2, std::back_inserter(output4));
+ copy_alt(rtree.qbegin_(pred), rtree.qend_(), std::back_inserter(output4));
compare_outputs(rtree, output4, expected_output);
}
+#endif
}
// rtree specific queries tests
@@ -1029,22 +1040,20 @@
exactly_the_same_outputs(rtree, output, output2);
std::vector<Value> output3;
- std::copy(rtree.qbegin(bgi::nearest(pt, k)), rtree.qend(bgi::nearest(pt, k)), std::back_inserter(output3));
+ std::copy(rtree.qbegin(bgi::nearest(pt, k)), rtree.qend(), std::back_inserter(output3));
compare_nearest_outputs(rtree, output3, expected_output, pt, greatest_distance);
+#ifdef BOOST_GEOMETRY_INDEX_DETAIL_EXPERIMENTAL
{
- typedef typename Rtree::const_query_iterator QI;
- QI first = rtree.qbegin(bgi::nearest(pt, k));
- QI last = rtree.qend(bgi::nearest(pt, k));
std::vector<Value> output4;
- std::copy(first, last, std::back_inserter(output4));
+ std::copy(rtree.qbegin_(bgi::nearest(pt, k)), rtree.qend_(bgi::nearest(pt, k)), std::back_inserter(output4));
compare_nearest_outputs(rtree, output4, expected_output, pt, greatest_distance);
- QI last2 = rtree.qend();
output4.clear();
- std::copy(first, last, std::back_inserter(output4));
+ copy_alt(rtree.qbegin_(bgi::nearest(pt, k)), rtree.qend_(), std::back_inserter(output4));
compare_nearest_outputs(rtree, output4, expected_output, pt, greatest_distance);
}
+#endif
}
// rtree nearest not found