cogset

Trait cogset::Point [-] [+] [src]

pub trait Point {
    fn dist(&self, other: &Self) -> f64;

    fn dist_monotonic(&self, other: &Self) -> f64 { ... }
    fn monotonic_transform(x: f64) -> f64 { ... }
    fn monotonic_inverse(x: f64) -> f64 { ... }
    fn dist_lower_bound(&self, other: &Self) -> f64 { ... }
}

A point in some (metric) space.

Example

use cogset::Point;

struct TwoD {
    x: f64, y: f64
}

impl Point for TwoD {
    fn dist(&self, other: &TwoD) -> f64 {
        self.dist_monotonic(other).sqrt()
    }

    // these three methods together are optional, but can provide an
    // optimisation for some algorithms (if one is implemented the
    // others must be too)
    fn dist_monotonic(&self, other: &TwoD) -> f64 {
        let dx = self.x - other.x;
        let dy = self.y - other.y;
        dx * dx + dy * dy
    }
    fn monotonic_transform(x: f64) -> f64 {
        x * x
    }
    fn monotonic_inverse(x: f64) -> f64 {
        x.sqrt()
    }

    // another optimisation for some algorithms (if `dist` is
    // cheap to compute this can just be left off entirely)
    fn dist_lower_bound(&self, other: &TwoD) -> f64 {
        (self.x - other.x).abs()
    }
}

Required Methods

fn dist(&self, other: &Self) -> f64

Accurately compute the distance from self to other.

This should be real and non-negative, or else algorithms may return unexpected results.

Provided Methods

fn dist_monotonic(&self, other: &Self) -> f64

Accurately compute some monotonic function of the distance from self to other.

This should satisfy a.dist_monotonic(b) == Self::monotonic_transform(a.dist(b)) where Self::monotonic_transform has been implemented to be increasing and non-negative.

This can be used to optimize algorithms that care only about the ordering of distances, not their magnitude, since it may be implemented more efficiently than a.dist(b) itself. For example, for the 2-D Euclidean distance between (x0, y0) and (x1, y1), dist_monotonic could be Δ = (x0 - x1)2 + (y0 - y1)2 (i.e. monotonic_transform is x ↦ x2) instead of sqrt(Δ) as dist requires.

Warning: changes to this should be reflected by changes to monotonic_transform and monotonic_inverse.

fn monotonic_transform(x: f64) -> f64

Perform the increasing and non-negative transformation that dist_monotonic applies to dist.

It should satisfy:

  • a.dist_monotonic(b) == Self::monotonic_transform(a.dist(b)) for all points a and b,

  • Self::monotonic_transform(x) < Self::monotonic_transform(y) if and only if x < y, for x >= 0, y >= 0.

Warning: changes to this should be reflected by changes to dist_monotonic and monotonic_inverse.

fn monotonic_inverse(x: f64) -> f64

Perform the inverse of monotonic_transform to x.

This should satisfy Self::monotonic_transform(Self::monotonic_inverse(x)) == x and similarly with the application order reversed.

Warning: changes to this should be reflected by changes to dist_monotonic and monotonic_transform.

fn dist_lower_bound(&self, other: &Self) -> f64

Compute an estimate of the distance from self to other.

This should be less than or equal to self.dist(other) or else algorithms may return unexpected results.

Implementors