Fully document and make 'SelectionFunction' available for user use

[ckaran]

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.

[Stoeoef]

Thanks for the suggestion!

I'm rather happy with how SelectionFunction turned out, hearing that it can be useful for others only strengthens that. I think the only change that is required (besides making it public and documenting) is to remove the default implementation for should_unpack_leaf. I'm not sure it is sensible for a general use case. Re-adding it later is also a non-breaking change.

I'm still trying to wrap my head around how a 2n-dimensional r-tree storing positions and velocities would look like - what's even a nearest neighbour in that space? - but if you are positive that exposing SelectionFunc is already enough, I don't see a particular reason for keeping it private. Feel free to open a PR on this if you want! Otherwise, I'll be tackling this soon™, it's not that much after all.

[ckaran]

I'm still trying to wrap my head around how a 2n-dimensional r-tree storing positions and velocities would look like - what's even a nearest neighbour in that space?

The trick isn't the nearest neighbor, its the ability to search within an envelope with locate_in_envelope. But you're right, my original plan wouldn't actually work, you really need two trees, one for position and one for velocity. My original idea was that you'd construct an envelope that contained positions and velocities that could intersect a given location over some period of time (e.g., time range of 1 second). However, when I came home I realized that doing so would create an envelope that was significantly larger than it had to be, potentially returning far more vertices to search over than necessary. By maintaining two trees, you can reduce the volume of each envelope considerably, which helps out a lot.

but if you are positive that exposing SelectionFunc is already enough, I don't see a particular reason for keeping it private.

I think it is, but I'm not 100% sure. Only way to know is to try it and see! :grin:

Feel free to open a PR on this if you want! Otherwise, I'll be tackling this soon™, it's not that much after all.

I wish I could, but I'm 99% certain that I won't get a chance to do it before you've already handled it. WAY too many irons in the fire!

[Stoeoef]

Done with 0.6.0.

I guess a nice example would be in order for documentation as well, but.... ah well.

[ckaran]

Thank you! I look forward to seeing it when you push it.