search

georust / rstar

R*-tree spatial index for the Rust ecosystem
https://docs.rs/rstar
Apache License 2.0
414 stars 68 forks source link

Question: Why there is parameters verification that point dimension must be at least 2? #111

Closed ytskuh closed 1 year ago

ytskuh commented 1 year ago

I would like to create a R*-tree for points that could have a single dimension, but it says "thread 'main' panicked at 'Point dimension too small - must be at least 2'"

urschrei commented 1 year ago

Could you explain more about what you're trying to achieve? Preferably with a minimal reproducible example. I mostly work with geometries in R2, so I have to admit that I simply don't understand the phrase "points that could have a single dimension".

michaelkirk commented 1 year ago

I'm not sure it makes sense to use an RTree for less than 2 dimensions.

If I wanted to efficiently insert and query over a 1 dimensional range, I think I'd use a btree:

https://doc.rust-lang.org/stable/std/collections/struct.BTreeMap.html#method.range

Or do you mean that your points will be a mix of 1 and 2(+) dimensions?

ytskuh commented 1 year ago

I am working with a program that works with problems could be set in different dimensions - I just want to solve all situation with the same piece of code. It's right that btree or other solution is better for one dimensional problem. And I have found the crate that is more suitable for me (kd_tree)

grovesNL commented 5 months ago

@urschrei I have a use case where I currently use a BTreeMap<u32, u32> to represent intervals (key as the start, value as the end). It's really read heavy because I do a lot of range queries over it to see which intervals overlap. I think a one-dimensional RTree could be a better alternative for this use case and I'm currently attempting to do performance testing, but ran into this point dimension limitation. I'm going to work through it on a fork so I can test it out anyway, but just wanted to mention my use case here.

@michaelkirk BTreeMap is good but there are optimizations you can apply with a 1D bounding box/envelope that wouldn't apply to a generic BTree. My intuition is that a 1D r*-tree could perform better, but I haven't confirmed this yet.