Stuck with types in rstar crate (R-Tree index)

help
1

I'm trying to do a simple thing:

  1. save a few points in R-Tree index
  2. check many linestrings, if they're close enough to any of these points

There's rstar crate for this. But how are we supposed to use it?

There's a folder with a demo, but demos/examples in Rust crates usually do the tiniest, simplest possible thing, far from real use. So I skipped the demo and went straight to the main type (RTree) and read how to declare/instantiate it.

The docs tell that it's a generic (RTree<T>), and you need T: RTreeObject.

Ok, I need to make a type implementing RTreeObject trait. What's in the trait?

RTreeObject must have a type with Envelope inside:

pub trait RTreeObject {
    type Envelope: Envelope;
    fn envelope(&self) -> Self::Envelope;
}

Ok, so the type inside must implement Envelope. What's inside it?

pub trait Envelope: Clone + Copy + PartialEq + Debug {
    type Point: Point;

It must contain a type with Point trait. What's a Point?

Oh, it's a type that must have a type with trait RTreeNum inside!

pub trait Point: Copy + Clone + PartialEq + Debug {
    type Scalar: RTreeNum;

It's a 4th trait to implement, by the way, and we're not finished yet.

pub trait RTreeNum: Bounded + Num + Clone + Copy + Signed + PartialOrd + Debug { }

Defines a number type that is compatible with rstar.
rstar works out of the box with the following standard library types:
...
This type cannot be implemented directly. Instead, it is required to implement all required traits from the num_traits crate.

I must/can not implement this trait, but I should... implement traits from the crate? What?!

The docs in the crate don't give any certainty.

Does this mean the trait is just a union of traits? RTreeNum: Bounded + Num + Clone + Copy + Signed + PartialOrd + Debug { }

Should I just pick a type that will happen to satisfiy these traits? (And if it doesn't, the compiler will inform me after I code up the entire chain of types.)

The Examples

I decided to give a look at the demo. A 2-D index is declared here:

type DemoTree2D = RTree<TreePointType2D>;
type TreePointType2D = [f32; 2];

What?! It's just an array of f32s?! So many required traits in the docs, and the example just takes an array?!

But what about the Envelope trait? IIUC, it must be implemented for arrays to let this compile. Maybe there's such an implementation? I check the Envelope page, and it's not implemented for arrays.

What's going on there?

2

This says that RTreeNum can't be implemented directly (it's sealed). It will be implemented automatically (due to a blanket impl) if you implement all of its supertraits (some of which are from the standard library, others are from the de facto standard numeric library called "num_traits"). You likely won't have to do that, either – that set of traits basically describes a primitive numeric type (such as i32 or f64).

No, the type parameter of RTree is not the Envelope, it's the RTreeObject. And sure enough, that's implemented for [f32; 2] because it implements Point (impl Point for [S; 2] where S: RTreeNum), and there is a blanket impl RTreeObject for P where P: Point.

1 Like
3

Oh, I see. That's the key. Thanks a lot!

4

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.