georust / rstar

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

RFC: Provide selection methods based on internal iteration #164

Open adamreichold opened 3 months ago

adamreichold commented 3 months ago

This avoids the overhead of allocating an internal buffer to keep track of upcoming nodes when implementing the Iterator trait.

I also found a mistake in the old code from #37 (lack of early return in the parent case) and now the benchmarks also look somewhat nicer, i.e. directly comparing internal and external iteration on the same data set:

locate_at_point (successful)
                        time:   [115.62 ns 116.51 ns 117.43 ns]

locate_at_point_int (successful)
                        time:   [66.831 ns 67.264 ns 67.653 ns]

locate_at_point (unsuccessful)
                        time:   [167.70 ns 168.03 ns 168.34 ns]

locate_at_point_int (unsuccessful)
                        time:   [167.90 ns 168.28 ns 168.64 ns]

Closes #163

rmanoka commented 3 months ago

I'm for having this recursive impl. as an alternative to the iterator approach.