Implement our own spatial lookup data structure

[Michael-F-Bryan]

12 introduced aabb_quadtree as a mechanism for doing lookups based on location (i.e. "which items are within 5mm of P?"), but its API doesn't really line up with how we'd like to use it.

At some point in time we should implement our own quadtree (or N-tree or whatever).

This issue can be used as a list of useful links for implementation, and a wish list based on arcs' needs.

[Michael-F-Bryan]

I really like some of the algorithms explored in A dive into spatial search algorithms

By far one of the most common operations is to ask "which points are within X distance from P?" and get a sorted iterator which yields the closest points objects first.

I'm imagining an API somewhat like this:

/// A `Space` maps from a `BoundingBox` to some type, `K`.
struct Space<K> { ... }

impl<K> Space<K> {
  fn insert(&mut self, key: K, bounds: BoundingBox) { ... }

  /// Does a spatial lookup based purely on the `BoundingBox` inserted with the key, `K`.
  fn query_unsorted(
    &self, 
    location: Point, 
    maximum_distance: f64) -> impl Iterator<Item = &K> + '_ { ... }

    /// Finds all the items within `maximum_distance` of `location`, with the items 
    /// closest to `location` being yielded first.
    ///
    /// The `closest_point` callback is used to invoke the `ClosestPoint` algorithm 
    /// and find the closest point between an `Entity` and `location`.
    ///
    /// # Performance
    ///
    /// If you don't *need* the items to be sorted by distance from `location`, 
    /// prefer to use `Space::query_unsorted()` because it requires less memory
    /// and computation.
    fn query_sorted<F>(
        &self,
        location: Point,
        maximum_distance: f64,
        closest_point: F,
    ) -> impl Iterator<Item = &K> + '_
    where
        F: Fn(&K, Point) -> Closest,
    {
      ...
    }
}

The reason I chose to use a closest_point closure in the query_sorted() method instead of something like ReadStorage<'world, DrawingObject> is so we don't bake in the need for specs or anything other than the Closest enum, making it a lot easier for others to reuse.