packing algorithm in rtree in boost

Question

Hi all I understand that if rtree is created with range values in boost it would use packing algorithm. I need an example of rtree using packing algorithm. Here is my code that uses quadratic algorithm

    using  point = bg::model::point < int, 2, bg::cs::cartesian >;
    using  pointI = std::pair<point, std::size_t>;
 vector<point> contourCenters // has some value
bgi::rtree< pointI, bgi::quadratic<16> > rtree;
vector< pointI > cloud;

for (size_t i = 0; i < contourCenters.size(); ++i)
{
    int x = contourCenters[i].get < 0 >();
    int y = contourCenters[i].get < 1 >();

    cout << "Contour Centers: (" << x << "," << y << ")";
    cloud.push_back(mp(x, y, i));
    rtree.insert(make_pair(contourCenters[i], i));
}

I would like to create rtree with packing algorithm as it seems to be the fastest one in boost. Kindly guide me how to create a rtree with packing algorithm in boost.

Sacrificial

Answer 1

You'd just need to use the range constructor.

For that to work, the range must have been created before constructing the rtree. The simplest way to achieve that in your example would be to build your cloud vector first, and then construct the index from it:

Live On Coliru

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

namespace bg = boost::geometry;
namespace bgi = bg::index;
using  point  = bg::model::point <int, 2, bg::cs::cartesian>;
using  pointI = std::pair<point, std::size_t>;

pointI mp(int x, int y, size_t v) {
    return std::make_pair(point(x,y), v);
}

int main()
{
    std::vector<point> contourCenters; // has some value
    std::vector<pointI> cloud;

    size_t id_gen = 0;
    std::transform(
            contourCenters.begin(), contourCenters.end(),
            back_inserter(cloud), 
            [&](point const& p) { return std::make_pair(p, id_gen++); }
        );

    for(pointI& pi : cloud)
        std::cout << "Contour Centers: (" << bg::get<0>(pi.first) << "," << bg::get<1>(pi.first) << ")";

    bgi::rtree<pointI, bgi::quadratic<16> > rtree(cloud);
}

I replaced the loop with std::transform for good style, but you could keep the loop as you had it.

Thylacine

Thanks for an elegant solution. If I see boost documentation boost.org/doc/libs/1_58_0/libs/geometry/doc/html/geometry/… it says there are four variants of RTree. if this quadratic rtree becomes placement rtree when initialized this way. What will happen if I change the rtree definition line to following: bgi::rtree<pointI, bgi::rstar<16> > rtree(cloud); – Sacrificial

@Prem: This constructor uses a special bulk loading algorithm, so I don't think the packing algorithm matters unless you later add/remove elements from the tree. – Worthy

"nemo boost.org/doc/libs/1_58_0/libs/geometry/doc/html/geometry/… as per this documentation I would like to create rtree based on packing algorithm... which seems to be the most efficient way to store and retrieve data when using boost library to create rtree. Can you please guide me how to do that? I could create r*tree and quadretic tree but don't know how to create rtree based on packing algorithm. – Sacrificial

Any chance you could go into a little more detail on this? What goes into contourcenters and cloud? – Ardennes

@Ardennes The cloud is basically a collection of pair<point, id> (so you can query and correlate the found point to external data using the id) – Thylacine

I'm not sure if I'm completely barking up the wrong tree here, but can this code be used to fit smaller rectangles into a larger rectangle? I googled for boost bin packing and got this result but I admit I don't understand what I'm looking at. – Ardennes

@Ardennes that's a different thing indeed. en.wikipedia.org/wiki/Bin_packing_problem (rtrees are spatial indexes, and the packs are just a way to serialize them, in that context) – Thylacine

Is there anything in boost to help me with the binpacking? I don't have enough basic knowledge to ask a stackoverflow-acceptable question and I really appreciate your help here :) – Ardennes