boost::geometry::rtree::contains return multiple identical results

Question

I'm trying to evaluate several RTree implementations and have hit an issue with boost::geometry::rtree::contains (boost version 1.55). What I'm doing is trying to get a list of all boxes that contain a point. It returns the right boxes but it returns the same ones several times. I'm not sure why this is, libspatialindex does not do it.

Here's my code:

void testBoostRTree(const Polygons& polygons)
{
    using namespace boost::geometry;

    typedef model::point<double, 2, cs::cartesian> BoostPoint;
    typedef model::box<BoostPoint> BoostBox;
    typedef model::polygon<BoostPoint, true, true> BoostPolygon; // clockwise, closed.
    typedef std::pair<BoostBox, unsigned int> RTreeValue;

    index::rtree<RTreeValue, index::rstar<16, 4>> rtree;
    std::vector<BoostPoint> centrePoints;

    for (const auto& p : polygons)
    {
        BoostPolygon bp;

        for (const auto& point : p.m_points)
        {
             bp.outer().push_back(BoostPoint(point.first, point.second));
        } 

        BoostBox box = return_envelope<BoostBox>(bp);
        rtree.insert(std::make_pair(box, p.m_id));

        centrePoints.push_back(return_centroid<BoostPoint>(box));
    }

    std::vector<RTreeValue> hits;
    for (const auto& cp : centrePoints)
    {
         std::cout << "* Query point: "  << get<0>(cp) << ", " << get<1>(cp) << "\n";
         hits.clear();

         rtree.query(index::contains(cp), std::back_inserter(hits));

         for (const auto& r : hits)
         {
             std::cout << r.second << "\n";
         }
    }
}

I have verified that the points being checked are correct. I also don't really want to have to do iterator faffery in order to use std::set instead of std::vector.

Here's some sample results:

* Query point: 51.4181, 0.20462
278566
278566
278566
278566
278566
278566
261819
261821
261819
261820
261820
261821
13741
278566
278566
...

Compare these to results from libspatialindex:

* Query 51.4181 0.20462 
261819
261820
261821
13741
278566

I've scoured the documentation and source code but I can't find anything obvious that I'm doing wrong.

Answer 1

Since you didn't write what exactly is inserted into the rtree I can't reproduce the problem.

In the currently implemented version of the rtree (Boost 1.55) every Value you insert is indexed. I guess you could think that it works more like std::multiset than std::set. So if for some reason the same Values are generated and inserted into the rtree, you may notice duplicates in the output.