8-adjacent distance bug.

[wzli]

Hi, I'm trying to make a game on a square grid. Objects can move one of 8 cardinal directions each step. So the distance metric is modified to reflect this constraint. Things mostly seem to work, but troubleshooting a bug lead to discovering unexpected behavior with the locate_within_distance call.

Reproduce (on 0.9.3):

use rstar::{PointDistance, RTree, RTreeNum, RTreeObject, AABB};

#[derive(Debug)]
struct Point2D<T>(pub T, pub T);

impl<T: RTreeNum> RTreeObject for Point2D<T> {
    type Envelope = AABB<(T, T)>;

    fn envelope(&self) -> Self::Envelope {
        AABB::from_point((self.0, self.1))
    }
}

impl<T: RTreeNum + std::cmp::Ord> PointDistance for Point2D<T> {
    fn distance_2(&self, p: &(T, T)) -> T {
        let dx = self.0 - p.0;
        let dy = self.1 - p.1;
        // 8-way movement distance
        let d = std::cmp::max(dx.abs(), dy.abs());
        d * d
    }
}

fn main() {
    let mut rtree = RTree::new();
    rtree.insert(Point2D(0, 0));
    println!("{rtree:?}");
    let nearest = rtree.nearest_neighbor_iter_with_distance_2(&(1, 1)).next();
    println!("{nearest:?}");
    let within = rtree.locate_within_distance((1, 1), 1).next();
    println!("{within:?}");
}

Output:

RTree { size: 1, items: {Point2D(0, 0)} }
Some((Point2D(0, 0), 1))
None // <- d2 of (0, 0) should be within 1

[rmanoka]

I believe r-tree can only be used with Euclidean metric; what's used (l-infinity) is not a Euclidean norm. I am unsure if there's a different data structure that supports this metric.

Edit: incorrect mouse clicks. I'll leave the issue open for a while.

[rmanoka]

Since you are essentially looking for a rectangular box around the query point, would this example cover your use-case: https://docs.rs/rstar/latest/rstar/struct.RTree.html#example-3 ?

use rstar::{RTree, AABB};
let mut tree = RTree::bulk_load(vec![
  [0.0, 0.0],
  [0.0, 1.0],
  [1.0, 1.0]
]);
let half_unit_square = AABB::from_corners([0.0, 0.0], [0.5, 1.0]);
let unit_square = AABB::from_corners([0.0, 0.0], [1.0, 1.0]);
let elements_in_half_unit_square = tree.locate_in_envelope(&half_unit_square);
let elements_in_unit_square = tree.locate_in_envelope(&unit_square);
assert_eq!(elements_in_half_unit_square.count(), 2);
assert_eq!(elements_in_unit_square.count(), 3);

[wzli]

Yes, querying an square box is a workable substitute, thanks. There could be a disclaimer about euclidean metrics only though, it's not so obvious once you have the freedom to implement your own. And particularly when it goes undetected since most things work as normal.