2 Layer Rtree

[giorgostheo]

I am trying to create a structure that indexes datapoints with two 2d fields per point.

The idea is that I create an Rtree that indexes the first pair of points and in each leaf, all the points that are inside that leaf are then put on a "nested" rtree that indexes the second pair of points.

My main issue is that I find manually traversing a tree difficult. I am very new to Rust so that might be why. Is there a way for me to retrieve the MBRs of each leaf in a tree as well as iterate through them as if I am searching for neighbors given a query point (order matters)?

[rmanoka]

I am trying to create a structure that indexes datapoints with two 2d fields per point.

I'm a bit confused when you say "two 2d fields per point". Can you explain the use-case a bit more? Specifically, what types of queries do you intend on the structure?

If you are trying to store a pair of points, with support for neighbor queries that gives either point: then you can store the pair of points separately as a vector: Vec<(Point, Point)>, and then store both the points in the same RTree, along with the index and whether it is the left or right point. So your tree would be RTree<GeoWithData<Point, (usize, bool)>>. Thus, the r-tree would contain 2*n points if you start off with a vector with n pairs of points. For each point in the r-tree, the (usize, bool) stores the index in the vec, and whether it is the left or the right side of the pair of points. Does that work?

[giorgostheo]

Yeah mb, I should have explained in more detail.

I work with spatio-textual data, meaning each datapoint has both a spatial (2d coords) and a textual (semantic vectors that are dim reduced to 2d vectors) representation. The Idea is that an Rtree is created to index the spatial vectors and each leaf node (node that contains only leafs and not other parent nodes) is then indexes using an Rtree on the semantic vecs of the points that it contains. The paper that this arch. is proposed is this one if anyone is interested.

What I have created so far is a behemoth of terrible code that i will attach in case it helps in any way. My main issues are the following:

• I do not think that there is way to add additional data to each point that is put in the Rtree using the current implementation. Extra data can be the index of each point in an array for example, or any other datapoint that is useful. Java implementations for example do provide such functionality and both in my case and in many other it is important imo. I can create a separate issue for this if that helps.
• Traversing the tree is difficult for me rn (proly because I am bad at rust as you can obviously see based on my code). If there is any input on this I would appreciate it a lot.

My code is the following (it is awful). Gh wants txt (change to rs if you need to). main.txt

[rmanoka]

Have you tried using GeomWithData ? It allows you to store additional data in the r-tree data/leaf nodes.

[giorgostheo]

Thanks for that, this func seems very usefull. I would suggest maybe adding it to the insert part of the doc just so it easier for newcomers to find out about it, since it is needed in many cases.

Thanks for the help!