Issue with removing points from a boost::geometry::index::rtree

Question

I'm using boost 1.56 on OS X, installed through homebrew.

I'm running into a compilation problem - specifically, it appears that I cannot remove values from a boost::geometry::index::rtree.

Here's the code I've come up with so far:

#include <iostream>
#include <vector>
#include <string>
#include <boost/geometry.hpp>
#include <boost/geometry/geometries/point.hpp>
#include <boost/geometry/geometries/box.hpp>
#include <boost/geometry/index/rtree.hpp>

namespace bg = boost::geometry;
namespace bgm = bg::model;
namespace bgi = bg::index;

typedef bgm::point<float, 2, bg::cs::spherical_equatorial<bg::degree> > Point;
typedef bgm::box<Point> Box;
typedef std::pair<Box, int> BoxIdPair;

int main(int argc, char** argv) {
  bgi::rtree<BoxIdPair, bgi::rstar<16>> tree;
  // Some tree filling code excised from here for the sake of a minimal example.
  BoxIdPair b1 = std::make_pair(Box(Point(24, 19), Point(35, 26)), 100);
  BoxIdPair b2 = std::make_pair(Box(Point(41, 112), Point(54, 148)), 150);
  BoxIdPair b3 = std::make_pair(Box(Point(34, 24), Point(36, 100)), 92);
  BoxIdPair b4 = std::make_pair(Box(Point(21, 8), Point(43, 15)), 8);
  tree.insert(b1);
  tree.insert(b2);
  tree.insert(b3);
  tree.insert(b4);
  while (!tree.empty()) {
    std::cout << "Tree contains " << tree.size() << "box-id values." << std::endl;
    // 1. Choose arbitrary BoxIdPair to be the leader of a new canopy.
    //    Remove it from the tree. Insert it into the canopy map, with its corresponding id.
    Point origin(0.0, 0.0);
    std::vector<BoxIdPair> result_set;
    tree.query(bgi::nearest(origin, 1), std::back_inserter(result_set));
    Box b = result_set[0].first;
    int id = result_set[0].second;
    tree.remove(result_set[0]); // This is the line that is giving me difficulty, I think.

    // Additional code cut for minimal example
  }
}

This code does not compile! Specifically, here is the invocation:

clang++ -g -std=c++11 -L/usr/local/Cellar/boost/1.56.0/lib -I/usr/local/Cellar/boost/1.56.0/include test.cc -o test

And here are the errors emitted by the compiler (link to pastebin for brevity): http://pastebin.com/d7E0A4Ee

The three relevant errors are:

test.cc:71:10: note: in instantiation of member function 'boost::geometry::index::rtree<std::__1::pair<boost::geometry::model::box<boost::geometry::model::point<float, 2,
      boost::geometry::cs::spherical_equatorial<boost::geometry::degree> > >, int>, boost::geometry::index::rstar<16, 4, 4, 32>,
      boost::geometry::index::indexable<std::__1::pair<boost::geometry::model::box<boost::geometry::model::point<float, 2, boost::geometry::cs::spherical_equatorial<boost::geometry::degree> > >, int> >,
      boost::geometry::index::equal_to<std::__1::pair<boost::geometry::model::box<boost::geometry::model::point<float, 2, boost::geometry::cs::spherical_equatorial<boost::geometry::degree> > >, int> >,
      std::__1::allocator<std::__1::pair<boost::geometry::model::box<boost::geometry::model::point<float, 2, boost::geometry::cs::spherical_equatorial<boost::geometry::degree> > >, int> > >::remove' requested here
tree.remove(result_set[0]);
     ^
/usr/local/Cellar/boost/1.56.0/include/boost/geometry/strategies/concepts/within_concept.hpp:183:21: note: candidate template ignored: couldn't infer template argument 'ApplyMethod'
    static void apply(ApplyMethod const&)

^

test.cc:71:10: note: in instantiation of member function 'boost::geometry::index::rtree<std::__1::pair<boost::geometry::model::box<boost::geometry::model::point<float, 2,
  boost::geometry::cs::spherical_equatorial<boost::geometry::degree> > >, int>, boost::geometry::index::rstar<16, 4, 4, 32>,
      boost::geometry::index::indexable<std::__1::pair<boost::geometry::model::box<boost::geometry::model::point<float, 2, boost::geometry::cs::spherical_equatorial<boost::geometry::degree> > >, int> >,
      boost::geometry::index::equal_to<std::__1::pair<boost::geometry::model::box<boost::geometry::model::point<float, 2, boost::geometry::cs::spherical_equatorial<boost::geometry::degree> > >, int> >,
      std::__1::allocator<std::__1::pair<boost::geometry::model::box<boost::geometry::model::point<float, 2, boost::geometry::cs::spherical_equatorial<boost::geometry::degree> > >, int> > >::remove' requested here
tree.remove(result_set[0]);
     ^
/usr/local/Cellar/boost/1.56.0/include/boost/mpl/assert.hpp:83:5: note: candidate function [with C = false] not viable: no known conversion from 'boost::mpl::failed
  ************(boost::geometry::nyi::not_implemented_error<boost::geometry::info::BOX, boost::geometry::info::BOX, void>::THIS_OPERATION_IS_NOT_OR_NOT_YET_IMPLEMENTED::************)(types<boost::geometry::info::BOX,
  boost::geometry::info::BOX, void>)' to 'typename assert<false>::type' (aka 'mpl_::assert<false>') for 1st argument
int assertion_failed( typename assert<C>::type );

^

test.cc:71:10: note: in instantiation of member function 'boost::geometry::index::rtree<std::__1::pair<boost::geometry::model::box<boost::geometry::model::point<float, 2,
  boost::geometry::cs::spherical_equatorial<boost::geometry::degree> > >, int>,   boost::geometry::index::rstar<16, 4, 4, 32>,
      boost::geometry::index::indexable<std::__1::pair<boost::geometry::model::box<boost::geometry::model::point<float, 2, boost::geometry::cs::spherical_equatorial<boost::geometry::degree> > >, int> >,
  boost::geometry::index::equal_to<std::__1::pair<boost::geometry::model::box<boost::geometry::model::point<float, 2, boost::geometry::cs::spherical_equatorial<boost::geometry::degree> > >, int> >,
  std::__1::allocator<std::__1::pair<boost::geometry::model::box<boost::geometry::model::point<float, 2, boost::geometry::cs::spherical_equatorial<boost::geometry::degree> > >, int> > >::remove' requested here
tree.remove(result_set[0]);
     ^
/usr/local/Cellar/boost/1.56.0/include/boost/geometry/algorithms/detail/relate/relate.hpp:282:1: note: candidate template ignored: substitution failure [with MatrixOrMask =
  boost::mpl::vector<boost::geometry::detail::relate::static_mask<'T', '*', 'F', '*', '*', 'F', '*', '*', '*'>, boost::geometry::detail::relate::static_mask<'*', 'T', 'F', '*', '*', 'F', '*', '*', '*'>,
  boost::geometry::detail::relate::static_mask<'*', '*', 'F', 'T', '*', 'F', '*', '*', '*'>, boost::geometry::detail::relate::static_mask<'*', '*', 'F', '*', 'T', 'F', '*', '*', '*'>, mpl_::na, mpl_::na, mpl_::na, mpl_::na,
  mpl_::na, mpl_::na, mpl_::na, mpl_::na, mpl_::na, mpl_::na, mpl_::na, mpl_::na, mpl_::na, mpl_::na, mpl_::na, mpl_::na>, Geometry1 = boost::geometry::model::box<boost::geometry::model::point<float, 2,
  boost::geometry::cs::spherical_equatorial<boost::geometry::degree> > >, Geometry2 = boost::geometry::model::box<boost::geometry::model::point<float, 2, boost::geometry::cs::spherical_equatorial<boost::geometry::degree> >
  >]
relate(Geometry1 const& geometry1,
^

Anyone have thoughts on what might be going wrong? I'm mystified.

sehe · Accepted Answer · 2015-03-27T19:53:27.067

3

I've looked your code over and it seems fine. You're just running into a limitation with the choosen coordinate system where your coordinate isn't fully supported (yet).

You can verify this by changing the coordinate (this renders the data a bit funny, but it's about compilation success here). See this test program that shows different, equivalent approaches to deleting items:

Live On Coliru

#include <iostream>
#include <vector>
#include <string>
#include <boost/geometry.hpp>
#include <boost/geometry/io/io.hpp>
#include <boost/geometry/geometries/box.hpp>
#include <boost/geometry/geometries/point.hpp>
#include <boost/geometry/index/distance_predicates.hpp>
#include <boost/geometry/index/predicates.hpp>
#include <boost/geometry/index/rtree.hpp>

namespace bg  = boost::geometry;
namespace bgi = bg::index;
namespace bgm = bg::model;

//typedef bgm::point<float, 2, bg::cs::spherical_equatorial<bg::degree> > Point;
typedef bgm::point<float, 2, bg::cs::cartesian> Point;
typedef bgm::box<Point> Box;
typedef std::pair<Box, int> BoxIdPair;

int main() {
    using Tree = bgi::rtree<BoxIdPair, bgi::rstar<16> >;
    Tree tree;

    // Some tree filling code excised from here for the sake of a minimal example.
    tree.insert({ { Point(24,  19), Point(35,  26) }, 100 });
    tree.insert({ { Point(41, 112), Point(54, 148) }, 150 });
    tree.insert({ { Point(34,  24), Point(36, 100) },  92 });
    tree.insert({ { Point(21,   8), Point(43,  15) },   8 });

    while (!tree.empty()) {
        std::cout << "Tree contains " << tree.size() << " box-id values." << std::endl;
        // 1. Choose arbitrary BoxIdPair to be the leader of a new canopy.
        //    Remove it from the tree. Insert it into the canopy map, with its
        //    corresponding id.
        Point origin(0.0, 0.0);

        auto first = bgi::qbegin(tree, bgi::nearest(origin, 1)), 
             last  = bgi::qend(tree);

        if (first != last) {
            tree.remove(*first); // assuming single result
        }
    }
    std::cout << "Tree emptied\n";
}

Note Don't use the iterator-based remove() with iterators into the same rtree because remove() may invalidate them.

Note All of the remove() overloads end up deferring to raw_remove internally.

~~I'm not completely sure why it's not working. It appears that a trait that determines whether an index operation is interruptible is not defined for this particular combinarion of Geometries.~~

Update Thanks to Adam's comment below we know that it is because internally within() is used to decide which node should be checked during the tree traversal. And within(box, box) is currently not implemented for non-cartesian coordinate systems.

edited Mar 27 '15 at 19:53

answered Dec 23 '14 at 22:21

sehe

374,641
47
450
633

The limitation seems a bit arbitrary, especially since it only applies to `remove` in this case. Here's a minimal example that you could use when asking on the dev mailing list: http://coliru.stacked-crooked.com/a/f8417a454c645642 – sehe Dec 23 '14 at 22:34
Also note that when using the `nearest` predicate you will get the matches in order of increasing distance, so you can be much more efficient by querying one time instead of repeating a query for 1 item in a loop; see **[nearest neighbors using a circle](http://stackoverflow.com/questions/22909171/boostgeometry-nearest-neighbors-using-a-circle/22910024#22910024)**, in particular the comments by the library developer. – sehe Dec 23 '14 at 22:48
There is a serious problem in the above code. `remove()` may invalidate the iterators! Btw, this is why it's called `remove()`, not `erase()`. But I see why it seems to be obvious to do it this way. I suppose, the compilation could fail if the rtree iterators was passed or a runtime assertion could fail if the iterators were created for the same rtree object. But if the iterators was wrapped in an iterator of some other type (Boost.Range adaptors) the problem would still exist. – Adam Wulkiewicz Mar 27 '15 at 17:43
To be perfectly clear. The function is called `remove()` because one should pass into it a value or a range of values not owned by the rtree index. STL's `erase()` takes an iterator pointing to an element of a container. – Adam Wulkiewicz Mar 27 '15 at 17:58
@AdamWulkiewicz Are you saying the end iterator gets invalidated when the object is deleted? Because the iterator range effectively is - by definition - only empty or 1-element. I mean, it's a very good warning to give here, and I _already_ mention that all of these end up doing _the same_ call to `raw_remove` (so they're effectively equivalent). Do you think, aside from "suggestiveness" there is a real problem with the operation shown? – sehe Mar 27 '15 at 18:18
To be honest I'm not sure. It wasn't implemented with this special case in mind so it's not guaranteed behavior. There is a chance it'd work but in general iterators shouldn't be used this way. E.g. the implementation might change in the future. Furthermore from a user's point of view, a general guideline would be better, like "don't use rtree iterators after remove or insert", without any exceptions. We could talk about the details, though mailing list would be better for this I suppose. – Adam Wulkiewicz Mar 27 '15 at 19:27
Well. "Iterators shouldn't be used in this way" doesn't make sense "in general". I understand what you mean. There's an aliasing issue where the results could be undefined if the reference passed to `raw_remove` is to an element of the rtree itself. It seems an important point to add to the documentation. I'll add a warning and make the answer safer. – sehe Mar 27 '15 at 19:41
1

Btw, the `remove()` doesn't compile for boxes defined in spherical_equatorial CS because internally `within()` is used to decide which node should be checked during the tree traversal. And `within(box, box)` is currently not implemented for non-cartesian coordinate systems. – Adam Wulkiewicz Mar 27 '15 at 19:42
@AdamWulkiewicz Thanks for your precisions and the exact reason why the original code wouldn't compile. I've improved the answer accordingly. – sehe Mar 27 '15 at 19:54
Sorry, I should be precise. Consider a case when an iterator iterates over elements stored in one leaf, the first element is removed, but there is an underflow. The whole node and potentially it's parents (all containers of values and children nodes) are destroyed. The iterator tracks them and when incremented it may want to access invalid memory. In your example it's incremented in for loop and `remove()` taking a range (at least currently). – Adam Wulkiewicz Mar 27 '15 at 20:47
@AdamWulkiewicz apparently there's something wrong or you need to refresh the browser window :) (there is neither a for loop nor remove taking a range anymore) – sehe Mar 27 '15 at 20:49
Actually it'd be the same in the case of STL containers. You can see it as erase-increment pattern. It'd work if the iterator was incremented BEFORE `remove()`. But only in this case, when you're sure that only one Value will be returned. – Adam Wulkiewicz Mar 27 '15 at 20:50
@AdamWulkiewicz appreciated. I got this before when you said "It wasn't implemented with this special case in mind [...] shouldn't be used this way". Can you verify that the answer looks okay now, because it does look like you didn't see my [edit of 57 minutes ago](http://stackoverflow.com/posts/27628863/revisions) in your last comments – sehe Mar 27 '15 at 20:52
Refreshed, looks good :) Thanks! Anyway, if you think the docs should be improved or there is a bug in the implementation, feel free to fill a ticket or propose a change on the mailing list or GitHub. There is already an info about the invalidation in the docs (since 1.57, in Queries section) but maybe it should be mentioned in other parts of the docs as well... Btw, if I was guessing, I think `query()` to which a raw pointer to BoxIdPair (or iterator of 1-element std::array) was passed instead of `back_inserter` should be the fastest. But it'd be more error-prone (`1` could be increased). – Adam Wulkiewicz Mar 27 '15 at 21:10
@AdamWulkiewicz I based all of the above on the code by the OP, I had no reason to deviate because I was just concerned with establishing that it works for other CS and didn't depend on the particular `remove()` overload used. (Nice tip on using the raw pointer to single object as output iterator) – sehe Mar 27 '15 at 21:13

Issue with removing points from a boost::geometry::index::rtree

^

^

1 Answers1

Linked