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

Fix empty rect behavior by reverting 84d12654104e783011f24267145fb6bfccd2a30e #181

Closed michaelkirk closed 2 weeks ago

michaelkirk commented 2 weeks ago

reverts #162

I'm not really a regular rstar contributor, and I don't know that a simple reversion is the best way to solve this problem.

michaelkirk commented 2 weeks ago

A more rigorous solution would probably make use of an explicit empty state, e.g. Option<AABB>::None

michaelkirk commented 2 weeks ago

I guess we can infer empty based on the "nonsense" state of min > max, so maybe can solve the root issue by adding logic without changing the type signatures.

adamreichold commented 2 weeks ago

I don't know that a simple reversion is the best way to solve this problem.

I don't think we can just revert it as now the removed test case test_locate_within_distance_on_empty_tree would panic again. There also was quite a bit of boy scouting in that commit which we should not loose in any case.

I guess we can infer empty based on the "nonsense" state of min > max, so maybe can solve the root issue by adding logic without changing the type signatures.

There are certainly different options, but I am also wary of making merged more expensive to compute. I wonder if switch to a "(centre, diameter)" representation of the AABB as is done for periodic boundary conditions might be a more fundamental change to make the empty state more tame, i.e. represented by "diameter = 0".

adamreichold commented 2 weeks ago

One option I see is to revert the empty representation back to "(max_value, min_value)" but change the Point trait impls to use only saturating arithmetic.

michaelkirk commented 2 weeks ago

I'm happy to have you take this in any direction - but I think getting the wrong answer is almost always a bigger concern than getting a slightly slower answer.

michaelkirk commented 2 weeks ago

Unfortunately, I'm out of time for today, but please feel free to solve the problem with or without my particular solution.

adamreichold commented 2 weeks ago

One option I see is to revert the empty representation back to "(max_value, min_value)" but change the Point trait impls to use only saturating arithmetic.

Sadly, I see no viable option to wire this through our trait bounds ending in RTreeNum expect detaching from the Num-based hierarchy. So I do think the max/min representation is indeed superior, but I would prefer a more targeted revert and alternative fix for #161 as proposed in #184.

michaelkirk commented 2 weeks ago

superseded by https://github.com/georust/rstar/pull/184