[geo-rust] Compare sets of geoms? (requires Float vs Hash/Eq traits)

I have rstar::RTree and try to check if objects should be updated there, by comparing the old ones in the index and the new ones.

The problem is that RTree requires that the geometry has Float inside, but this forbids Hash & Eq, which are required to compare sets of geoms (with HashSet). I thought of BTreeSet, but that requires Ord which is weirder for geometries.

Geo-types docs say that Hash, PartialEq and Eq are supported for T's that support these traits -- and that's not floats, right?

I wrote just a check if old_geoms entriy is in new_geoms vector, and vice versa. But this must be slow, or not? (Apart from being O(n^2))

Is there a light way to check the difference of sets of geoms? Or we're doomed, and I have just to put a warning that such index update is a very costy operation? (I assume that "remove all & insert all new" strategy is costier, given that the update is 1..3 elements, while the rtree is big (100K objects).)

[#derive(... Hash, PartialEq, Eq)]
struct MyRTreeEntry { geom: Point, id: MyId }
impl RTreeObject for MyRTreeEntry {
    type Envelope = AABB<Point>;
    fn envelope(&self) -> AABB<Point> { self.geom.envelope() }
}
let mut tree: RTree<MyRTreeEntry> = ...
let old_entries = vec![entry1, entry2, entry3]; // this should be HashMap ideally
let new_entries = vec![entry3, entry2, entry4]; // this should be HashMap ideally

for e in old_entries.iter() {
    if !new_entries.contains(e) {
        tree.remove(e);
    }
}

for e in new_entries.iter() {
    if !old_entries.contains(e) (
        tree.insert(e);
    }
}

Why does it say that? I couldn't confirm that with a quick glance at the docs.

Anyway, an easy solution would be to wrap ordered_float::NotNan in a newtype and implement all the required traits (Float, Ord, Hash, etc.) for it.

1 Like

Ok, will try.

This simple code reproduces the problem. Even though I also couldn't find where Float is required.

use rstar::RTree;
use geo::Point;

pub struct Test {
	geoindex: RTree<Point<i64>>
}

Error:

937 |     geoindex: RTree<Point<i64>>
    |               ^^^^^^^^^^^^^^^^^ the trait `num_traits::float::Float` is not implemented for `i64`
    |
    = help: the following other types implement trait `num_traits::float::Float`:
              f32
              f64
    = note: required for `geo::Point<i64>` to implement `rstar::Point`
    = note: required for `geo::Point<i64>` to implement `RTreeObject`

Can you implement Hash for RTreeEntry by delegating to the implementation on the id field rather than deriving it? Does each entry have a unique id?

Yes, ids are unique, and it's enforced elsewhere, but I need to watch if the objects and their ids are the same, but geometries have changed.

Actually, what worked was wrapping into OrderedFloat, making struct like Point<OrderedFloat<f64>>. Thanks!

and the code to create such struct:

fn pof(x: f64, y: f64) -> Point<OrderedFloat<f64>> {
	Point::new(x.into(), y.into())
}

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.