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.

sehe · Accepted Answer · 2015-07-09 15:53:22Z

15

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.

answered Jul 9, 2015 at 15:53

sehe

400k49 gold badges475 silver badges673 bronze badges

Sign up to request clarification or add additional context in comments.

8 Comments

Prem Over a year ago

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);

Nemo Over a year ago

@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.

Prem Over a year ago

"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.

xaxxon Over a year ago

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

sehe Over a year ago

@xaxxon 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)

|

Collectives™ on Stack Overflow

packing algorithm in rtree in boost

1 Answer 1

8 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

8 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related