# [−][src]Crate acap

As Close As Possible — nearest neighbor search in Rust.

# Overview

The notion of distances between points is captured by the `Proximity`

trait. Its
`distance()`

method returns a `Distance`

, from which the actual numerical distance may be
retrieved with `value()`

. These layers of abstraction allow `acap`

to work with generically
with different distance functions over different types.

There are no restrictions on the distances computed by a `Proximity`

. For example, they don't
have to be symmetric, subadditive, or even positive. Implementations that do have these
desirable properties will additionally implement the `Metric`

marker trait. This distinction
allows `acap`

to support a wide variety of useful metric and non-metric distances.

As a concrete example, consider `Euclidean<[i32; 2]>`

. The `Euclidean`

wrapper equips any
type that has coordinates with the Euclidean distance function as its `Proximity`

implementation:

use acap::distance::Proximity; use acap::euclid::Euclidean; let a = Euclidean([3, 4]); let b = Euclidean([7, 7]); assert_eq!(a.distance(&b), 5);

In this case, `distance()`

doesn't return a number directly; as an optimization, it returns a
`EuclideanDistance`

wrapper. This wrapper stores the squared value of the distance, to avoid
computing square roots until absolutely necessary. Still, it transparently supports comparisons
with numerical values:

use acap::distance::Distance; let d = a.distance(&b); assert!(d > 4 && d < 6); assert_eq!(d, 5); assert_eq!(d.value(), 5.0f32);

For finding the nearest neighbors to a point from a set of other points, the
`NearestNeighbors`

trait provides a uniform interface to many different similarity search
data structures. One such structure is the vantage-point tree, available in `acap`

as
`VpTree`

:

use acap::vp::VpTree; use acap::NearestNeighbors; let tree = VpTree::balanced(vec![ Euclidean([3, 4]), Euclidean([5, 12]), Euclidean([8, 15]), Euclidean([7, 24]), ]);

`VpTree`

implements `NearestNeighbors`

, which has a `nearest()`

method that returns an
optional `Neighbor`

. The `Neighbor`

struct holds the actual neighbor it found, and the
distance it was from the target:

let nearest = tree.nearest(&[7, 7]).unwrap(); assert_eq!(nearest.item, &Euclidean([3, 4])); assert_eq!(nearest.distance, 5);

`NearestNeighbors`

also provides the `nearest_within()`

, `k_nearest()`

, and
`k_nearest_within()`

methods which find up to `k`

neighbors within a possible threshold.

It can be expensive to compute nearest neighbors exactly, especially in high dimensions.
For performance reasons, `NearestNeighbors`

implementations are allowed to return approximate
results. Many implementations have a speed/accuracy tradeoff which can be tuned. Those
implementations which always return exact results will also implement the `ExactNeighbors`

marker trait. For example, a `VpTree`

will be exact when the `Proximity`

function is a
`Metric`

.

## Re-exports

`pub use coords::Coordinates;` |

`pub use distance::Distance;` |

`pub use distance::Metric;` |

`pub use distance::Proximity;` |

`pub use euclid::euclidean_distance;` |

`pub use euclid::Euclidean;` |

`pub use euclid::EuclideanDistance;` |

## Modules

chebyshev | |

coords | |

cos | |

distance | Abstract notions of distance. |

euclid | |

exhaustive | Exhaustive nearest neighbor search. |

hamming | |

kd | |

lp | |

taxi | |

vp |

## Structs

Neighbor | A nearest neighbor. |

## Traits

ExactNeighbors | Marker trait for NearestNeighbors implementations that always return exact results. |

NearestNeighbors | A nearest neighbor search index. |

Neighborhood | Accumulates nearest neighbor search results. |