Cannot remove element from boost::geometry::index::rtree by its index

Question

I'm creating a boost geometry rtree.

From the sample page I create:

typedef bg::model::point<float, 2, bg::cs::cartesian> point;
typedef bg::model::box<point> box;
typedef std::pair<box, unsigned> value;

I want to add value elements to the tree:

bgi::rtree< value, bgi::quadratic<16> > rtree;
box b(point(2.0f, 2.0f), point(2.5f, 2.5f));
// insert new value
rtree.insert(std::make_pair(b, 2));

Now I'd like to know if it's possible to remove an element by knowing the box identifier (or all elements of it if it's possible to set more elements with same id).

What I want to do is something like removing the element that I've added above like calling something like:

rtree.remove(2); // why I can't do this?

How can I accomplish this?

Answer 1

You'll have to use an iterator. The possible overloads are

remove(value_type const &)
remove(Iterator, Iterator)
remove(ConvertibleOrRange const &)

First you should find the values to remove by searching (potentially running a query, but I assume you don't need that, because your problem would not exist.)

So, you might want to use std::find_if. I'm not sure how the performance can be improved (without resorting to a reverse map). I guess your profiler should be used for providing reassurance there.

Update: Proof Of Concept

The naive approach fails:

// UNDEFINED BEHAVIOUR:
template <typename Rtree, typename Id>
size_t remove_ids_loop(Rtree& rtree, Id const& id) {
    using V = typename Rtree::value_type;
    static_assert(sizeof(V) == 0, "don't use; UNDEFINED BEHAVIOUR!");

    size_t removed = 0;
    std::for_each(rtree.begin(), rtree.end(), [&](V const& v) { 
            if (id == v.second)
                removed += rtree.remove(v);
        });

    return removed;
}

This is because as documented:

⚠ Warning

The modification of the rtree may invalidate the iterators.

Simple approach:

template <typename Rtree, typename Id>
size_t remove_ids_bulk(Rtree& rtree, Id const& id) {
    using V = typename Rtree::value_type;
    std::vector<V> v;
    std::copy_if(rtree.begin(), rtree.end(), back_inserter(v), [id](V const& v) { return v.second == id; });

    return rtree.remove(v.begin(), v.end());
}

This sidesteps the race by doing the query separate from the removal. Note this might be more efficient because we pass the whole range at once.

Note: this should be ok with duplicate entries, because rtree::remove only deletes one value at a time.

Live Demo

Live On Coliru

#include <boost/geometry.hpp>
#include <boost/geometry/index/rtree.hpp>

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

typedef bg::model::point<float, 2, bg::cs::cartesian> point;
typedef bg::model::box<point> box;

typedef std::pair<box, unsigned> value;

template <typename Rtree, typename Id>
size_t remove_ids_bulk(Rtree& rtree, Id const& id) {
    using V = typename Rtree::value_type;
    std::vector<V> v;
    std::copy_if(rtree.begin(), rtree.end(), back_inserter(v), [id](V const& v) { return v.second == id; });

    return rtree.remove(v.begin(), v.end());
}

// UNDEFINED BEHAVIOUR:
template <typename Rtree, typename Id>
size_t remove_ids_loop(Rtree& rtree, Id const& id) {
    using V = typename Rtree::value_type;
    static_assert(sizeof(V) == 0, "don't use; UNDEFINED BEHAVIOUR!");

    size_t removed = 0;
    std::for_each(rtree.begin(), rtree.end(), [&](V const& v) { 
            if (id == v.second)
                removed += rtree.remove(v);
        });

    return removed;
}

int main() {
    //I want to add value elements to the tree:

    bgi::rtree< value, bgi::quadratic<16> > rtree;
    box b(point(2.0f, 2.0f), point(2.5f, 2.5f));
    // insert new value
    rtree.insert(std::make_pair(b, 2));
    std::cout << "Elements: " << rtree.size() << "\n";

    // remove id 2
    remove_ids_bulk(rtree, 2u);
    std::cout << "Elements: " << rtree.size() << "\n";
}

Prints

Elements: 1
Elements: 0