Hello. I was investigating the use of rstar for my project, and for what I see in the Point trait, it won't be possible because I only know the number of dimensions at runtime. It would be nice to support a dynamic number of dimensions, set when the RTree is created.

Hi,
Thanks for your great work.

I have a list of geo_type Polygon and would like to insert them in rtree. Actually I am obliged to convert each segment in Line and link properties of the polygon by index.
Is there an easier way ?

This API is present in the equivalent RTree struct in https://github.com/Stoeoef/spade.

It appears that removing a object when the MIN_SIZE = 1 causes capacity overflow panic.

Could anyone elaobrate why? mabye this behaviour should be documented?

The code below reproduces the issue for me, on version 0.9.3

use rstar::{RStarInsertionStrategy, RTree, RTreeParams};

pub struct WierdParams;

impl RTreeParams for WierdParams {
    const MIN_SIZE: usize = 1;
    const MAX_SIZE: usize = 4;
    const REINSERTION_COUNT: usize = 1;
    type DefaultInsertionStrategy = RStarInsertionStrategy;
}

fn main() {
    let mut items: Vec<[f32; 2]> = Vec::new();
    for i in 0..2 {
        items.push([i as f32, i as f32]);
    }
    let mut tree: RTree<_, WierdParams> = RTree::bulk_load_with_params(items);
    println!("{:?}", tree.remove(&[1.0, 1.0]).is_some());
}

According to https://docs.rs/rstar/latest/rstar/trait.Point.html, Point can be built from arrays/tuples of dimension up to 9. Is there any specific reason why 9 is chosen to be the upper limit?

It would be nice if rstar had first class support for other geometry crates, e.g. nalgebra or cgmath.

Up to now, users either need to

• Implement their own point type (boiler plate / cannot easily use third-party point types due to orphan rule)
• Use the built in point type (like [f64; 2], has only limited functionality)

One promising path forward might be adding support for the mint crate crate. Adding Point impls for the mint types should allow to add them to an R-Tree directly. Both cgmath and nalgebra support mint already.

This issue originated from #25

On page
https://docs.rs/rstar/0.2.0/rstar/trait.RTreeObject.html

there is link to AABB:

https://docs.rs/rstar/0.2.0/rstar/structs.AABB.html

which is broken, should be

https://docs.rs/rstar/0.2.0/rstar/struct.AABB.html

It returns the distance squared (or rather, the result of distance_2). The function name is misleading and the documentation

Returns (element, distance) tuples of the tree sorted by their distance to a given point.

doubles down on that.

As a minimum, the docs need to change. Ideally, deprecate this function and replace it with one called nearest_neighbor_iter_with_distance_2, for clarity and consistency.

Hello, I'd like to know if its possible to adapt the crate to non-euclidean spaces.

For instance I'm interested in using rstar to speed up search operations on the following space:

On these pictures you can see a point cloud that represents radius vectors. I need to have a way to quickly enumerate all points within a certain bounding box defined by angles and distances. Depending on settings it can look almost as a square or as a thin sector. So, reducing search space by a simple bounding circle is not always efficient.

So I was wondering, if its possible to use something like (r, theta) as a primitive box to be directly used inside rstar? One issue I see is that in my case angles form a continious space, so a box near 0° would include some points in the 0°.. 5° and 355°..359° ranges.

Thanks in advance!

Ie. a distance of 1,000,000 fits into i32, but squared it will not. Maybe have an associated type for the return value, defaulting to Point::Scalar?

Thanks for the wonderful crate. As downstream users of this crate, some of the maintainers of the georust organization (incl. me) wanted to check if you need a hand with the maintenance of this crate. We should be able to do our best with keeping the deps. up-to-date, esp. with yanked / vulnerable ones, but hopefully also help with improving the efficiency / adding useful functionalities to the crate.

If you are up for it, we would also be very happy to add this crate to the georust organization (which I believe you are already a part of) and make you the main author / admin, along with a couple of maintainers to help with keeping the crate updated. Otherwise, if you wish to keep the crate as is, you may add a couple of us as maintainers here to help you (pls. see cc-ed contacts below). Happy to help and apologies if the request sounds overbearing as that is definitely not the intention.

cc: @michaelkirk @urschrei

It would be useful to have an analogue of SimpleEdge::length2 for Line.

Firsts of all thanks for this amazing crate. I'm already using it in two of my projects.

The problem I have is that I'd like to have my objects referenced through an Rc pointer while being inside the RTree but the compiler complains saying that:

the trait bound std::rc::Rcshape::Shape: rstar::point::Point is not satisfied

Without the Rc<_> it works perfectly. If you think this is something reasonable and can give me some advice I can even try to make a contribution ot this repo with that.

Thanks

Would be nice to have a RectangleWithData object, otherwise rectangle areas involve mostly reimplementing Rectangle.
Also, why not store data in RTree without requiring a type to support it?

Hello! I'm using an R*-Tree to hold 3D graphical data, organized as points. I'm trying to figure out how I could determine whether the AABB for a given leaf node in the tree is within view of a camera.

One way I've thought of to define the view would be to approximate the camera view as a Cone, with a central axis along the camera's view direction and sufficient radius to match up with the camera's FOV. However, I can't tell from the documentation how I might implement a Cone geometry as an AABB Envelope in order to perform intersection tests on the R*-Tree data structure.

Another thought that came to mind would be trying ray-based intersections across the tree. However, I don't know how I would approximate the camera's view with so many rays to do intersection tests, using this library.

Does anybody have any thoughts or suggestions?
Thanks so much in advance for any insights!

I would like to associate extra data with each point I insert, so I am defining a struct like

pub struct MyPoint<T> {
    pub x: f32,
    pub y: f32,
    pub v: T
}

The trouble is that when implementing Point for this type, I need to implement generate, which wants me to create a T from nothing. When T is some opaque type from a library I don't control, it can be impossible to implement generate.

Would it be possible to drop generate from the Point trait? If not, could the RTree API itself allow us to associate a value with each point? In the meantime, my workaround is to wrap T in Option, but that is a bit messy.

I'd like to check for all intersections between two RTrees. The most efficient way to do this is to recurse down the nodes, checking the envelopes along the way. However, RTreeNode (and related structs) is in structures::node, which isn't public (although structures::aabb is). Could we expose structures::node in lib.rs like we do aabb? Happy to write the (very small) PR if that helps.

Analogous to RTree::lookup_in_circle. At the moment, as far as I can tell, I have to use locate_in_envelope_intersecting and then repeatedly check to see whether the item is further away than the radius using distance_2.

First, thank you very much for this crate, it has worked very well for me so far. I like the API and the flexibility, and of course the performance!

I have a case where I want to determine intersection candidates between triangles and tetrahedra. I have two separate RTrees for other purposes (e.g. finding closest triangle/tetrahedron to a point): one for triangles and one for tetrahedra. Unfortunately, intersection_candidates_with_other_tree only accepts &Self as input, despite the fact that it only works with the envelopes of the two objects, which are the same (AABB). Would it be possible to relax intersection_candidates_with_other_tree so that it takes any other which shares the same envelope?

See e.g. https://github.com/georust/rstar/runs/6240513070?check_suite_focus=true

Thank you for rstar.

In spade I use lookup_in_rectangle for search objects that completely or partly belongs to bounding box.
What should I use instead of it, locate_in_envelope_intersecting or lookup_in_rectangle or join results of both methods? If object lay inside envelope is it intersection in your terminology?

Iterating over a subset of RTree elements, modifying some elements and potentially removing some is not possible efficiently at the moment.

A retain function as for Vec for an RTree would simplify this dramatically. Basically, after applying a selection function, i.e. selecting all elements in an envelope, that contains a mutable reference to its elements, applying a modification function afterwards would allow efficient tree modifications without additional cloning.

Currently, one would first select all elements in an envelope, then iterate over them, modifiying some and cloning those that need to be deleted. After the iterator has finished, the elements marked for deletion are removed one by one.

From what I have seen, the current RTreeNode implementation does not offer a unique (hashable, implements == correctly) key for each RTreeNode.

More specifically, I believe there are many usecases where one might need some sort of internal "access" to the node, meaning a way to add some sort of data to each one. In my case, this "data" is a tuple of values. However, since there is nothing correctly hashable in each RTreeNode, I can not find a way to create a Hashmap for ex. in order to store the data I need. The only info that is always available for each RTreeNode is the envelope, however two nodes can have the same envelope which means that this is not an appropriate key.

Adding some way to extract a (preferably hashable) unique ID for each RTreeNode would be useful in many ways, since it can allow a more "free" approach to traversal and can also allow child to parent referances instead of just parent to child.

I'm working on developing a continuous collision detection system, and just realized that for what I'm doing it makes more sense to use object-oriented capsules. Basically, I have a large set of hyperspheres that are each moving with their own individual velocities, and I need to know when they start or stop intersecting. My plan is to create a tree with n + 1 dimensions, where the extra dimension is time. A sphere's location will then include time as well as it's position. A minimal volume capsule that is oriented along the line segment defined by the sphere's center's start and end point removes most uninteresting points quickly, which is the whole point of having the r* tree.

My problem is that rstar doesn't implement a capsule Envelope type, so I need to figure out how to do it myself, which is the point of this issue. I need to understand the various required methods better so that I can properly implement my capsule type. So, here are my questions:

• new_empty creates a new, empty envelope, but the docs don't state what the expected shape of the envelope is. Looking at the code for AABB, it looks like we're supposed to create an envelope that encompasses the maximum volume possible. Is this correct?
• For merge, is it allowed to move self's center? What about its orientation? Based on the AABB code, it appears that the center is recalculated each time, so I'm guessing that moving the center is OK, I just want to be sure. I don't think this is a problem for merged as you're creating a brand new envelope, but if it is, I'd like to know.
• area really means volume, correct? How accurate does this need to be? If we have to round this value, do we round up or down?
• How accurate does intersection_area have to be? Do we round up or down? As a side note, the intersections of capsules are not in general capsules. Calculating this volume is going to be slow; is there a good way to avoid doing this as much as possible?
• For distance_2 Is this always supposed to be the distance from the point to the closest point enclosed by the envelope? This seems to be what the AABB code is effectively doing, but I just want to be sure.
• Can you explain min_max_dist_2 a bit more? I'm still not getting it.
• What is margin_value? What is the margin? If I have to round a value, do I round up or down?
• Which point should I use to sort the envelopes by in sort_envelopes? How does it apply to envelopes that are object oriented rather than axis-oriented? I'm thinking about two capsules whose centers coincide and are the same shape, but one is rotated 180 degrees relative to the other. Physically they are the same, but since their endpoints are reversed, this could have an effect.
• What precisely is partition_envelopes trying to accomplish??? I really can't tell.

rstar currently supports bulk-loading using the OMT algorithm. However, using a Hilbert curve to order the nodes can result in a tree with better storage utilisation and less overlap. There is an extant implementation for an R tree at https://github.com/flatgeobuf/flatgeobuf/blob/master/src/rust/src/packed_r_tree.rs#L193 that should be relatively easily portable.

A related issue is then the creation of a new bulk-loading API which allows selection of the bulk loading algorithm, depending on the application.

Cascaded unions are a desirable feature for the geo library. However, the algorithm requires post-order traversal of the tree in order to work, but iteration order is currently not specified.

First off, thank you for your hard work on this crate.

I have run into a failure case on my machine when computing a nearest_neighbor for a query point against an rtree of a set of points (resembling a torus, so nothing crazy).

nearest_neighbor returns a different result for a tree built using bulk_load vs. a tree built using a sequence of .insert calls. More specifically, the result is correct for the bulk_loaded tree.

The test case is in this gist: https://gist.github.com/elrnv/9cedf04fdc11ab30e37118a47bb6e436

Unfortunately I couldn't prune the set of points much, but I hope this test helps in debugging :)

Hi! Thanks for the crate! How can I implement an RTreeObject trait for a simple 2d point structure? Eg.

pub struct Point {
  pub id: i32,
  pub lat: f64,
  pub lon: f64,
}

@urschrei @michaelkirk I see you have made many clean-ups, and polishes leading up-to a release, but haven't released yet. Should we release a version 0.9.0 in the next couple days? I couldn't find a checklist for it, so jotting down the steps here:

• Check rstar/CHANGELOG.md and ensure fixed issues are referenced, and closed
• Publish rstar to crates.io
• Create and push a tag marking released version

Anything else to be done?

closes #53

First of all, once again thank you for building and maintaining this awesome lib :).

I have a test that checks if the nearest_neighbour is inside the locate_within_distance neighbourhood.
I believe this invariant should be upheld by the library or at least documented if not.
I think this is related to #13. So for now using nearest_neighbour_iter().next() fixes the issue.

The test code is as below:

#[cfg(test)]
mod tests {
    #[test]
    fn nearest_neighbor_test() {
        let q = [0.6249998211860657, 0.21650643646717072, -0.0000004867678171649459];
        let pts = samples();
        let tree_a = rstar::RTree::bulk_load(pts.clone());
        let rad = 0.6858711216511891;
        let nbrhood: Vec<_> = tree_a.locate_within_distance(q, rad).collect();

        let nearest = tree_a.nearest_neighbor_iter(&q).next().unwrap(); // Works
        let nearest = tree_a.nearest_neighbor(&q).unwrap(); // Does not work.
        std::dbg!(&nbrhood);
        std::dbg!(&nearest);
        assert!(nbrhood.contains(&nearest));
    }

    fn samples() -> Vec<[f64; 3]> {
        vec![
            [ -4.259259223937988, -0.5, -4.259259223937988, ],
            [ -4.629629611968994, -0.5, -4.629629611968994, ],
            [ -3.1481480598449707, -0.5, -4.259259223937988, ],
            [ -3.5185184478759766, -0.5, -4.629629611968994, ],
            [ -2.037036895751953, -0.5, -4.259259223937988, ],
            [ -2.407407283782959, -0.5, -4.629629611968994, ],
            [ -0.9259257316589355, -0.5, -4.259259223937988, ],
            [ -1.2962961196899414, -0.5, -4.629629611968994, ],
            [ 0.18518543243408203, -0.5, -4.259259223937988, ],
            [ -0.18518495559692383, -0.5, -4.629629611968994, ],
            [ 1.2962965965270996, -0.5, -4.259259223937988, ],
            [ 0.9259262084960938, -0.5, -4.629629611968994, ],
            [ 2.407407760620117, -0.5, -4.259259223937988, ],
            [ 2.0370373725891113, -0.5, -4.629629611968994, ],
            [ 3.5185189247131348, -0.5, -4.259259223937988, ],
            [ 3.148148536682129, -0.5, -4.629629611968994, ],
            [ 4.629629770914714, -0.5, -4.259259223937988, ],
            [ 4.259259541829427, -0.5, -4.629629611968994, ],
            [ -4.259259223937988, -0.5, -3.1481480598449707, ],
            [ -4.629629611968994, -0.5, -3.5185184478759766, ],
            [ -3.1481480598449707, -0.5, -3.1481480598449707, ],
            [ -3.5185184478759766, -0.5, -3.5185184478759766, ],
            [ -2.037036895751953, -0.5, -3.1481480598449707, ],
            [ -2.407407283782959, -0.5, -3.5185184478759766, ],
            [ -0.9259257316589355, -0.5, -3.1481480598449707, ],
            [ -1.2962961196899414, -0.5, -3.5185184478759766, ],
            [ 0.18518543243408203, -0.5, -3.1481480598449707, ],
            [ -0.18518495559692383, -0.5, -3.5185184478759766, ],
            [ 1.2962965965270996, -0.5, -3.1481480598449707, ],
            [ 0.9259262084960938, -0.5, -3.5185184478759766, ],
            [ 2.407407760620117, -0.5, -3.1481480598449707, ],
            [ 2.0370373725891113, -0.5, -3.5185184478759766, ],
            [ 3.5185189247131348, -0.5, -3.1481480598449707, ],
            [ 3.148148536682129, -0.5, -3.5185184478759766, ],
            [ 4.629629770914714, -0.5, -3.1481480598449707, ],
            [ 4.259259541829427, -0.5, -3.5185184478759766, ],
            [ -4.259259223937988, -0.5, -2.037036895751953, ],
            [ -4.629629611968994, -0.5, -2.407407283782959, ],
            [ -3.1481480598449707, -0.5, -2.037036895751953, ],
            [ -3.5185184478759766, -0.5, -2.407407283782959, ],
            [ -2.037036895751953, -0.5, -2.037036895751953, ],
            [ -2.407407283782959, -0.5, -2.407407283782959, ],
            [ -0.9259257316589355, -0.5, -2.037036895751953, ],
            [ -1.2962961196899414, -0.5, -2.407407283782959, ],
            [ 0.18518543243408203, -0.5, -2.037036895751953, ],
            [ -0.18518495559692383, -0.5, -2.407407283782959, ],
            [ 1.2962965965270996, -0.5, -2.037036895751953, ],
            [ 0.9259262084960938, -0.5, -2.407407283782959, ],
            [ 2.407407760620117, -0.5, -2.037036895751953, ],
            [ 2.0370373725891113, -0.5, -2.407407283782959, ],
            [ 3.5185189247131348, -0.5, -2.037036895751953, ],
            [ 3.148148536682129, -0.5, -2.407407283782959, ],
            [ 4.629629770914714, -0.5, -2.037036895751953, ],
            [ 4.259259541829427, -0.5, -2.407407283782959, ],
            [ -4.259259223937988, -0.5, -0.9259257316589355, ],
            [ -4.629629611968994, -0.5, -1.2962961196899414, ],
            [ -3.1481480598449707, -0.5, -0.9259257316589355, ],
            [ -3.5185184478759766, -0.5, -1.2962961196899414, ],
            [ -2.037036895751953, -0.5, -0.9259257316589355, ],
            [ -2.407407283782959, -0.5, -1.2962961196899414, ],
            [ -0.9259257316589355, -0.5, -0.9259257316589355, ],
            [ -1.2962961196899414, -0.5, -1.2962961196899414, ],
            [ 0.18518543243408203, -0.5, -0.9259257316589355, ],
            [ -0.18518495559692383, -0.5, -1.2962961196899414, ],
            [ 1.2962965965270996, -0.5, -0.9259257316589355, ],
            [ 0.9259262084960938, -0.5, -1.2962961196899414, ],
            [ 2.407407760620117, -0.5, -0.9259257316589355, ],
            [ 2.0370373725891113, -0.5, -1.2962961196899414, ],
            [ 3.5185189247131348, -0.5, -0.9259257316589355, ],
            [ 3.148148536682129, -0.5, -1.2962961196899414, ],
            [ 4.629629770914714, -0.5, -0.9259257316589355, ],
            [ 4.259259541829427, -0.5, -1.2962961196899414, ],
            [ -4.259259223937988, -0.5, 0.18518543243408203, ],
            [ -4.629629611968994, -0.5, -0.18518495559692383, ],
            [ -3.1481480598449707, -0.5, 0.18518543243408203, ],
            [ -3.5185184478759766, -0.5, -0.18518495559692383, ],
            [ -2.037036895751953, -0.5, 0.18518543243408203, ],
            [ -2.407407283782959, -0.5, -0.18518495559692383, ],
            [ -0.9259257316589355, -0.5, 0.18518543243408203, ],
            [ -1.2962961196899414, -0.5, -0.18518495559692383, ],
            [ 0.18518543243408203, -0.5, 0.18518543243408203, ],
            [ -0.18518495559692383, -0.5, -0.18518495559692383, ],
            [ 1.2962965965270996, -0.5, 0.18518543243408203, ],
            [ 0.9259262084960938, -0.5, -0.18518495559692383, ],
            [ 2.407407760620117, -0.5, 0.18518543243408203, ],
            [ 2.0370373725891113, -0.5, -0.18518495559692383, ],
            [ 3.5185189247131348, -0.5, 0.18518543243408203, ],
            [ 3.148148536682129, -0.5, -0.18518495559692383, ],
            [ 4.629629770914714, -0.5, 0.18518543243408203, ],
            [ 4.259259541829427, -0.5, -0.18518495559692383, ],
            [ -4.259259223937988, -0.5, 1.2962965965270996, ],
            [ -4.629629611968994, -0.5, 0.9259262084960938, ],
            [ -3.1481480598449707, -0.5, 1.2962965965270996, ],
            [ -3.5185184478759766, -0.5, 0.9259262084960938, ],
            [ -2.037036895751953, -0.5, 1.2962965965270996, ],
            [ -2.407407283782959, -0.5, 0.9259262084960938, ],
            [ -0.9259257316589355, -0.5, 1.2962965965270996, ],
            [ -1.2962961196899414, -0.5, 0.9259262084960938, ],
            [ 0.18518543243408203, -0.5, 1.2962965965270996, ],
            [ -0.18518495559692383, -0.5, 0.9259262084960938, ],
            [ 1.2962965965270996, -0.5, 1.2962965965270996, ],
            [ 0.9259262084960938, -0.5, 0.9259262084960938, ],
            [ 2.407407760620117, -0.5, 1.2962965965270996, ],
            [ 2.0370373725891113, -0.5, 0.9259262084960938, ],
            [ 3.5185189247131348, -0.5, 1.2962965965270996, ],
            [ 3.148148536682129, -0.5, 0.9259262084960938, ],
            [ 4.629629770914714, -0.5, 1.2962965965270996, ],
            [ 4.259259541829427, -0.5, 0.9259262084960938, ],
            [ -4.259259223937988, -0.5, 2.407407760620117, ],
            [ -4.629629611968994, -0.5, 2.0370373725891113, ],
            [ -3.1481480598449707, -0.5, 2.407407760620117, ],
            [ -3.5185184478759766, -0.5, 2.0370373725891113, ],
            [ -2.037036895751953, -0.5, 2.407407760620117, ],
            [ -2.407407283782959, -0.5, 2.0370373725891113, ],
            [ -0.9259257316589355, -0.5, 2.407407760620117, ],
            [ -1.2962961196899414, -0.5, 2.0370373725891113, ],
            [ 0.18518543243408203, -0.5, 2.407407760620117, ],
            [ -0.18518495559692383, -0.5, 2.0370373725891113, ],
            [ 1.2962965965270996, -0.5, 2.407407760620117, ],
            [ 0.9259262084960938, -0.5, 2.0370373725891113, ],
            [ 2.407407760620117, -0.5, 2.407407760620117, ],
            [ 2.0370373725891113, -0.5, 2.0370373725891113, ],
            [ 3.5185189247131348, -0.5, 2.407407760620117, ],
            [ 3.148148536682129, -0.5, 2.0370373725891113, ],
            [ 4.629629770914714, -0.5, 2.407407760620117, ],
            [ 4.259259541829427, -0.5, 2.0370373725891113, ],
            [ -4.259259223937988, -0.5, 3.5185189247131348, ],
            [ -4.629629611968994, -0.5, 3.148148536682129, ],
            [ -3.1481480598449707, -0.5, 3.5185189247131348, ],
            [ -3.5185184478759766, -0.5, 3.148148536682129, ],
            [ -2.037036895751953, -0.5, 3.5185189247131348, ],
            [ -2.407407283782959, -0.5, 3.148148536682129, ],
            [ -0.9259257316589355, -0.5, 3.5185189247131348, ],
            [ -1.2962961196899414, -0.5, 3.148148536682129, ],
            [ 0.18518543243408203, -0.5, 3.5185189247131348, ],
            [ -0.18518495559692383, -0.5, 3.148148536682129, ],
            [ 1.2962965965270996, -0.5, 3.5185189247131348, ],
            [ 0.9259262084960938, -0.5, 3.148148536682129, ],
            [ 2.407407760620117, -0.5, 3.5185189247131348, ],
            [ 2.0370373725891113, -0.5, 3.148148536682129, ],
            [ 3.5185189247131348, -0.5, 3.5185189247131348, ],
            [ 3.148148536682129, -0.5, 3.148148536682129, ],
            [ 4.629629770914714, -0.5, 3.5185189247131348, ],
            [ 4.259259541829427, -0.5, 3.148148536682129, ],
            [ -4.259259223937988, -0.5, 4.629629770914714, ],
            [ -4.629629611968994, -0.5, 4.259259541829427, ],
            [ -3.1481480598449707, -0.5, 4.629629770914714, ],
            [ -3.5185184478759766, -0.5, 4.259259541829427, ],
            [ -2.037036895751953, -0.5, 4.629629770914714, ],
            [ -2.407407283782959, -0.5, 4.259259541829427, ],
            [ -0.9259257316589355, -0.5, 4.629629770914714, ],
            [ -1.2962961196899414, -0.5, 4.259259541829427, ],
            [ 0.18518543243408203, -0.5, 4.629629770914714, ],
            [ -0.18518495559692383, -0.5, 4.259259541829427, ],
            [ 1.2962965965270996, -0.5, 4.629629770914714, ],
            [ 0.9259262084960938, -0.5, 4.259259541829427, ],
            [ 2.407407760620117, -0.5, 4.629629770914714, ],
            [ 2.0370373725891113, -0.5, 4.259259541829427, ],
            [ 3.5185189247131348, -0.5, 4.629629770914714, ],
            [ 3.148148536682129, -0.5, 4.259259541829427, ],
            [ 4.629629770914714, -0.5, 4.629629770914714, ],
            [ 4.259259541829427, -0.5, 4.259259541829427, ],
            ]
    }
}

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

I'm seeing unreachable! panics when I insert certain configurations of points. An example which reproducibly fails for me is here: https://gist.github.com/alec-deason/6218fb2fd6262bdd63473e417e050004

I've stripped that down so that changing the position of any of the last few points even slightly will flip it from failing to succeeding. Adding or removing any points either from the bulk loaded set or the ones that are inserted later makes the failure go away. Also inserting all of he points one at a time rather than bulk loading the initial set causes the failure to go away in this example, though I haven't experimented enough to see if the failure only appears with bulk loading.

The program that generated this list of points hits this failure case regularly but not with every set it generates. I have seen it hit the unreachable! panic in both algorithm::rstar::forced_insertion and algorithm::rstar::recursive_insert, which look to be the same underlying failure.

I'm using nightly. I see the same behavior with rstar 0.8.1 and with the latest commits.

I have a bit of a unique use case where the physical locations of the objects I'm putting in my tree frequently change.
Thanks to your very good documentation, I figured that the time needed to remove, modify, and then re-insert all the objects that changed would be O(n * log(n)). That doesn't seem very practical.

So my next choice is to instead build a new tree on every cycle. My data is not stored in a vector, so I must first construct a vector and then feed it into the tree. That becomes O(n + log(n)). That's a lot better but I still think there's room for improvement.

Would it be possible to to make bulk_load accept any iterator to supply it with objects?
If that's not possible, could it be modified to just borrow the vector, rather than consume it? That would at least save me some time on the memory allocation.

Or maybe there's an easier solution to this problem that I somehow missed?

Would it be possible to implement distance metrics which respect periodic boundaries? This type of data structure has been implemented in the C++ package periortree, but I think an implementation in Rust would be great for the scientific Rust community.

Hello,

My use case involves a data structure that can be 1GB or more in size and has to be persisted in permanent storage (aka a database). Since it's millions of small objects, using bulk insert is probably not a good idea with O(n*log n) complexity.

I could just serialize the whole tree into a single blob and write that to disk. However, besides doubling the memory requirements, every single change would also make it necessary to serialize everything again.

A typical solution for B-trees is to store the non-leaf nodes as separate objects on disk and load them on demand. This should also be possible with R*trees, and ParentNode even implements Serialize and Deserialize. However, I don't see a way to construct an RTree object from this, and this would also need accessors for adding, removing and modifying nodes (and it even has to be async since it involves I/O).

Is there a chance that this feature might be implemented in this crate?

It would be nice to have release in crates.io with dependency on heapless 0.7,
this fix duplication deps problem for me.

The repository on https://crates.io/crates/rstar refers to https://github.com/Stoeoef/rstar rather than https://github.com/georust/rstar. It looks like all references to the old repo are updated in this repo so I assume that crates.io has to be updated through crates.io itself.
Also it seems that dependabot uses this information which also points users to Stoeoef/rstar rather than georust/rstart.

Hey,

I am currently facing some issues while trying to use this crate with custom objects.

What I am trying to do, is some kind of lazy removal. Take a look at the example code below:

use rstar::{RTree, RTreeObject, AABB, PointDistance};

#[derive(PartialEq)]
struct Element {
    is_valid : bool,
    position : [f32; 2],
    // ..
}

impl RTreeObject for Element {
    type Envelope = AABB<[f32; 2]>;

    fn envelope(&self) -> Self::Envelope {
        AABB::from_point(self.position)
    }
}

impl PointDistance for Element {
    fn distance_2(&self, point : &[f32; 2]) -> f32 {
        let dx = self.position[0] - point[0];
        let dy = self.position[1] - point[1];

        dx * dx + dy * dy
    }
}

fn main() {
    let mut tree = RTree::new();

    {
        tree.insert(Element { is_valid : true, position: [0.0, 0.2] });
        tree.insert(Element { is_valid : false, position: [1.0, 0.2] });
    }

    while let Some(el) = tree.nearest_neighbor(&[1.0, 2.0]) {
        if !el.is_valid {
            // Compiler error here: Borrow twice
            tree.remove(el);
        } else {
            // ..
            break;
        }
    }
}

Essentially the problem is that the tree owns all the data, so I cannot back-reference the objects in the tree and therefor cannot remove any elements in the tree.

Implementing Copy or Clone is not feasible as the objects I want to store could be quite large. A possible workaround is to simply insert Rc<RefCell<Something>> into the tree and make the data owned by something else, though this is very verbose.

What I imagine a nice(r) solution would be something like pop_nearest or so.

It appears that == is technically not the only criterion required for the remove methods of RTree<T>. The passed-in &T also needs to hold the same envelope, otherwise remove cannot continue the tree traversal.

https://github.com/Stoeoef/rstar/blob/26e4d86987ff922bd705f1ae77a3c1b1903a3f3c/rstar/src/algorithm/removal.rs#L15-L22

where should_unpack_parent is

https://github.com/Stoeoef/rstar/blob/26e4d86987ff922bd705f1ae77a3c1b1903a3f3c/rstar/src/algorithm/selection_functions.rs#L140-L146

A similar issue exists with contains. The documentation should probably be updated to reflect this.

The SelectionIterator type is not documented nor public. It restricts the usage to define a custom function to return the iterator. Suppose we could make it public as well as the algorithm mod?

I'm trying something like:

impl<P> CustomPoint<P> where P: Point {
    fn new(cenet: P, size: f64) {
        let p = center.add( value );
        ...
    }
}

and it drops the error: items from traits can only be used if the trait is in scope

In 'rstar-demo' there is an example:

pub fn create_random_points<P: Point<Scalar = f32>>(num_points: usize) -> Vec<P>

and it's works, but the same doesn't work for me.

Summary

I'm building a continuous collision detector to detect when n-dimensional spheres start and stop intersecting one another. This crate seems like a really good fit for that need if SelectionFunction is fully documented and exposed. That is, I want to be able to implement the trait on my own function, and pass that function into an RTree, and get the output from the iterator.

Detailed Explanation

I'm building a simple radio communications simulator that uses a simple binary model of communications; that is, if two nodes are within some distance of one another, they can communicate, if they aren't, then they can't. This is virtually identical to a continuous collision library in that I need to calculate the exact moment the next pair of nodes either come into contact with one another, or go out of contact with one another. The trick is that nodes are able to change velocities at any point in time. I'm able to handle this by maintaining a 2n-dimensional r* tree, where dimensions [1, n] are for the position, and [n+1, 2n] are for the velocities of the nodes, and by applying the following (simplified set of) rules:

• If two objects have the same velocity, then no event is generated as they will either remain in contact, or stay out of contact.
• If two objects are within the communications radius, and their velocities are different, then they are guaranteed to go out of contact at some point in the future. The precise time when that will occur is a function of both where the node is, and its velocity. If I already know that the next event will occur at some time t, and that the velocity/position of some subtree ensures that those members cannot break the connection before time t, then I can simply avoid recursing into that portion of the tree, saving some time.
• If a node is outside of comms range, and its velocity is such that it will be traveling away from the node of interest, then I don't need to worry about it. For some portions of the tree, this really obvious (e.g., if the other node is in the positive X direction and it is moving the positive X direction, I don't need to do any more comparisons), and should be easy to figure out using Envelopes.

In short, the selection function I want to create is really all about work avoidance. If I do it right, I'll have a few false positives that really need to be tested, but not that many.

All of the removal functions use the lower-level helper function RTree::remove_with_selection_function, which simply depth-first searches the entire tree until it finds a node that matches the selection criteria. Even when the selection function is a point coordinate (i.e. RTree::remove_at_point), this search does not take advantage of the spatial properties of the RTree data structure, so it is an O(N) operation.

Even the function RTree::pop_nearest_neighbor, which performs a R-tree optimized search query and then immediately deletes the corresponding node, does not take advantage of the optimized query results when removing the node -- it resorts to another O(N) search to remove the node.

I am not claiming that this implementation is incorrect, but I think this is an important performance characteristic that should be documented.

As an example of the consequences of this performance characteristic, my use case was essentially to implement a solution to the Traveling Salesman problem. I'm optimizing the traversal of a large collection of vector shapes. I can start the path traversal from many different positions over time, so the tradeoff of one-time tree construction time for repeated fast queries makes sense. In pseudo-code form, my algorithm is:

clone the tree
current point = some initial point
path = empty list
while (cloned tree not empty) {
    current point = nearest neighbor to current point
    add the current point to the path
    remove the current point from the cloned tree
}

Having an O(N) operation inside this loop defeats my purpose. If I had known that the removal function was O(N), I would have chosen a different solution. Again, I'm not saying that the rstar code should change, only that the documentation should describe the performance so that people can make an informed decision if it is suitable to their application.

(I concede that the need to clone the tree may also be a good reason to look for a different solution to my problem.)

I don't think the node removal problem is unique to the rstar crate. Now that I'm alert to this factor, I've surveyed other crates that implement spatial data structures.

Most other spatial data structure crates simply don't support node removal at all (acacia, quadtree-cd, gaia_quadtree, ntree, fart-aabb).

Two crates (quadtree_rs and aabb-quadtree) provide for node removal. They both improve the performance of node removal somewhat by identifying tree items with a unique numeric handle. Items are stored in a hash map using the item handle as a key, so node removal has the performance of the hash_map. The spatial data structures themselves do not hold the items; they only item handles. This is a big tradeoff. Item lookup with this crates entails not only a spatial query, but a hash_map query.

I've been testing inserting geometric objects into rstar. I noticed a ~20x speedup with some test data (300k MultiPolygons) between inserting geometries where RTreeObject::envelope() was implemented with a direct call to bounding_rect to inserting wrapper structs that include both the geometry and a pre-cached envelope. This 20x speedup includes the time in the latter case to loop over the geometries and create each's envelope.

In retrospect, it's not too surprising that envelope() would need to be called multiple times, but I didn't see a mention of it on the RTreeObject page.

I am trying to do the following operations on an RTree so that I can use it as a set:

• Insert a point if not already present
• merge (union) two RTrees without duplicates

For the first operation this can be done with existing methods on RTree:

if !tree.contains(&p) { tree.insert(p); }

However, while I don't know the internals of RTree I'm guessing this approach traverses the tree twice when it's only necessary to traverse it once. Am I right that we could do this operation more efficiently if we worked with the internals of RTree, for example adding an insert_unique method? The above approach is probably good enough for my use case anyways.

The second operation is a little harder. Here is my code for merging two trees if I didn't care about duplicates:

let tree = RTree::bulk_load(
    left.iter()
    .chain(right.iter())
    .copied()
    .collect()
);

From there I guess I could iterate over the tree checking whether each element equals it's second nearest neighbor to remove duplicates, but this feels hacky. I'd imagine that if we had some sort of insert_unique method, then we could rewrite bulk_load using insert_unique in place of insert to get a method that makes a tree without duplicates.

Another alternative is I can just accept duplicates in my set. Then in order to pop / remove an element I would have to remove all instances like this:

while let Some(_) = tree.remove(&p) {}

which wouldn't be too costly if there's only two or three of each element at most.

So I think my options for using RTree as a set are:

• Continue hacking together set operations using the exposed API on RTree, probably getting a half or a third the performance of what's possible.
• Work with the internals of RTree to do these operations more efficiently. I could either structure this as a wrapper struct around RTree in my own crate, or contribute this to rstar. I'd imagine I'd have to be the one to contribute this to rstar, since I think this use case is not a very common one.

So what are people's thoughts? Is anyone else interested in having an RTreeSet in rstar? How much worse will my performance be if I continue using the hacky lazy approach?

Hi, I'm trying to make a game on a square grid. Objects can move one of 8 cardinal directions each step. So the distance metric is modified to reflect this constraint. Things mostly seem to work, but troubleshooting a bug lead to discovering unexpected behavior with the locate_within_distance call.

Reproduce (on 0.9.3):

use rstar::{PointDistance, RTree, RTreeNum, RTreeObject, AABB};

#[derive(Debug)]
struct Point2D<T>(pub T, pub T);

impl<T: RTreeNum> RTreeObject for Point2D<T> {
    type Envelope = AABB<(T, T)>;

    fn envelope(&self) -> Self::Envelope {
        AABB::from_point((self.0, self.1))
    }
}

impl<T: RTreeNum + std::cmp::Ord> PointDistance for Point2D<T> {
    fn distance_2(&self, p: &(T, T)) -> T {
        let dx = self.0 - p.0;
        let dy = self.1 - p.1;
        // 8-way movement distance
        let d = std::cmp::max(dx.abs(), dy.abs());
        d * d
    }
}

fn main() {
    let mut rtree = RTree::new();
    rtree.insert(Point2D(0, 0));
    println!("{rtree:?}");
    let nearest = rtree.nearest_neighbor_iter_with_distance_2(&(1, 1)).next();
    println!("{nearest:?}");
    let within = rtree.locate_within_distance((1, 1), 1).next();
    println!("{within:?}");
}

Output:

RTree { size: 1, items: {Point2D(0, 0)} }
Some((Point2D(0, 0), 1))
None // <- d2 of (0, 0) should be within 1

It looks like while you've release 0.6.0, you haven't pushed the code to GitHub yet; could you please push it?

Hi, I'm a little confused about r*-tree terminology, but as far as I can see from demo and so on by adding points the rtree-boxes/rectangles are automatically created? That is, I do not need to implement the splitting algorithm myself?

Hello,

for a project of mine, a long distance route plotter for the game Elite: Dangerous, I'm using an R*-Tree as my main data structure for nearest-neighbor queries, my data set contains about 87 million 3D-Points with some metadata attached, and constructing an R*-Tree with the following parameters:

pub struct LargeNodeParameters;
impl RTreeParams for LargeNodeParameters {
    const MIN_SIZE: usize = 20;
    const MAX_SIZE: usize = 40;
    const REINSERTION_COUNT: usize = Self::MAX_SIZE - Self::MIN_SIZE - 1;
    type DefaultInsertionStrategy = RStarInsertionStrategy;
}

takes around 30 seconds on my machine, query performance is excellent at ~23M queries per second distributed across 32 threads

i have done a quick skim over the bulk-loading code and I've also skimmed the paper it is based on bit it goes a bit over my head. my main question is: would it be feasible to parallelize the bulk loading using something like rayon to improve performance?

I've experimented with splitting my data up and constructing multiple trees i can query in parallel but didn't have too much success with that.

best regards,

Earthnuker

Hi,

thank you for this great library.
I encountered an issue while testing on older Linux machine.
Short version: everything works fine on the machine where I build release but when I test on the machine with older Linux I get an error:
"version `GLIBC_2.27' not found"
By commenting out the code I identified that the problem appears only if I call RTree::bulk_load. Calling insted RTree::new() followed by tree.insert() calls eliminated the error.

Details:

1. I'm building a dynamic library (cdylib) which is called from java
2. ldd --version on build machine returns:

ldd (Ubuntu GLIBC 2.27-3ubuntu1) 2.27

3. ldd --version on test machine:

ldd (Ubuntu GLIBC 2.23-0ubuntu7) 2.23

4. While trying to call .so library from java through JNA on the test machine I get the error:

java.lang.UnsatisfiedLinkError: /lib/x86_64-linux-gnu/libm.so.6: version `GLIBC_2.27' not found (required by /home/user/dev/project1/resources/libtest.so)

Tried with stable rust 1.42 and 1.43, target x86_64-unknown-linux-gnu

I'm not sure if any other details may be necessary. I definitely isolated this issue to single line with bulk_load call.