georust / rstar Goto Github PK
View Code? Open in Web Editor NEWR*-tree spatial index for the Rust ecosystem
Home Page: https://docs.rs/rstar
License: Apache License 2.0
R*-tree spatial index for the Rust ecosystem
Home Page: https://docs.rs/rstar
License: Apache License 2.0
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
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?
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,
}
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
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_load
ed 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 :)
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
[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
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
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)?
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?
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 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:
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?
@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:
rstar/CHANGELOG.md
and ensure fixed issues are referenced, and closedrstar
to crates.ioAnything else to be done?
closes #53
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.
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'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.
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.
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
.
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.
It would be useful to have an analogue of SimpleEdge::length2
for Line
.
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?
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
?
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've been testing inserting geometric objects into rstar. I noticed a ~20x speedup with some test data (300k MultiPolygon
s) 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.
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!
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.
I am trying to do the following operations on an RTree so that I can use it as a set:
RTree
s without duplicatesFor 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:
RTree
, probably getting a half or a third the performance of what's possible.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,
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 ?
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.
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
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
.
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?
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:
ldd (Ubuntu GLIBC 2.27-3ubuntu1) 2.27
ldd (Ubuntu GLIBC 2.23-0ubuntu7) 2.23
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.
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.
where should_unpack_parent
is
A similar issue exists with contains
. The documentation should probably be updated to reflect this.
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.
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.
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.
It would be nice to have release in crates.io with dependency on heapless 0.7,
this fix duplication deps problem for me.
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 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.
It looks like while you've release 0.6.0, you haven't pushed the code to GitHub yet; could you please push it?
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!
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());
}
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.
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.
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:
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.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.
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.
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?
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?
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.