Add Octree/Quadtree vector-backed implementations 'VecOctree'/'VecQuadtree'

[Stwend]

I've experimented with an alternate implementation of the Octree that stores all its point data in one large vector slab and stores indices to that slab in an octree: https://github.com/Stwend/spart_octree_vec

Deleting a point will mark its index in the slab as a tombstone, inserting a point will first try resurrecting a tombstone instead of pushing to the slab. As of now , bulk insertion is just a dummy that calls insert() on all suplied points in order with no optimization.

Benchmarks on my machine suggest improvements across the board:
Insert/Delete: both -65%
KNN Queries: -35%
Range queries: -75%

Tests are all still succeeding and the vector-backed implementation would also lend itself for easy iteration over all points.

If this has a chance of being added to this crate I'll open a PR draft for some further testing and a sibling implementation for QuadTree.

[habedi]

Hi. This sounds like an interesting idea for optimization. I need to think about this. I'll let you know.

[habedi]

Hi,

I'm OK with adding the new vector-backed implementations of the Octree and Quadtree to Spart.
Although I have a few considerations:

1. Implementations should exist in parallel with existing Octree and Quadtree implementations. For example, they could be named VecQuadtree and VecOctree.
2. It's important that the implementations are decoupled and more or less self-sufficient from other tree implementations.
3. Implementations should have unit tests (inside the respective Rust module) and, optionally, some property-based and integration tests (stored in the tests/ directory).
4. Preferably, they should have an interface similar to the existing Octree and Quadtree implementations.

Please let me know what you think.

@Stwend

[Stwend]

Hi, sounds good! I'll prepare a PR next week.

On a side note, I also tried to move tree capacity to a generic argument (Octree<T, const C: usize>) in hopes of unlocking more compiler optimizations, benchmarks didn't pick up any change whatsoever though.