Calculate intersections between rtrees

Question

I was following the boost geometry rtree documentation. I'm able to perform a spatial query with a box in order to retrieve the list of rtree elements that intersect with it.

I'd like to know if there's a way to perform a spatial query between an rtree and another rtree (of the same type).

Something like:

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

bgi::rtree< value, bgi::quadratic<16> > rtree1;
//... create first rtree
bgi::rtree< value, bgi::quadratic<16> > rtree2;
//... create second rtree
std::vector<value> result_s;
rtree1.query(bgi::intersects(rtree2), std::back_inserter(result_s));
// At this point result_s should contain elements of rtree1 that intersect with rtree2

Is is possible something like that or I can only perform query with elements of the same type of rtree template elements?

I think I've seen some discussion about this on the mailing list once. I'll try to find it later. — sehe
– sehe, Commented Jan 22, 2016 at 17:50

TilmannZ · Accepted Answer · 2016-01-24 13:36:00Z

2

I think what you mean is called a 'spatial join'. The naive approach would iterate through all element of the smaller tree and perform rectangle queries on the larger tree. There is some research about this, just search scholar.google.com for 'spatial join'.

I don't think any of the advanced approaches are significantly better than the naive approach that I described above, but I'm not up to date with that topic.

answered Jan 24, 2016 at 13:36

TilmannZ

1,89914 silver badges20 bronze badges

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

2 Comments

Jepessen Over a year ago

I'm already doing this way and it works. I take every element of the first three and check the spatial join between it and the second tree. But I perform a loop this way. I'd like to know if a spatial join between two rtrees can avoid an entire loop and check intersection recursively only in interesting areas reducing computation time.

TilmannZ Over a year ago

I think there are algorithms, check for example the TOUCH algorithm: infoscience.epfl.ch/record/186338/files/sigfp132-nobari_1.pdf . But I think they require a special tree implementation and are not necessarily that much better, depending on your dataset. I think for an R-Tree where you don't want to modify the code the nested loop-join is the best approach there is.

Collectives™ on Stack Overflow

Calculate intersections between rtrees

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related