This project is part of the @thi.ng/umbrella monorepo.

## About

N-dimensional distance metrics & K-nearest neighborhoods for point queries.

### Distance metrics

The package provides the
`IDistance`

interface for custom distance metric implementations & conversions from/to raw
distance values. The following preset metrics are provided too:

Preset |
Number |
n-D |
2D |
3D |
Comments |
---|---|---|---|---|---|

`EUCLEDIAN` |
Eucledian distance | ||||

`EUCLEDIAN1` |
|||||

`EUCLEDIAN2` |
|||||

`EUCLEDIAN3` |
|||||

`DIST_SQ` |
Squared dist (avoids `Math.sqrt` ) |
||||

`DIST_SQ1` |
|||||

`DIST_SQ2` |
|||||

`DIST_SQ3` |
|||||

`defManhattan(n)` |
Manhattan distance | ||||

`MANHATTAN2` |
|||||

`MANHATTAN3` |

### Neighborhoods

Neighborhoods can be used to select n-D spatial items around a given target
location and an optional catchment radius (infinite by default). Neighborhoods
also use one of the given distance metrics and implement the widely used
`IDeref`

interface to obtain the final query results.

Custom neighborhood selections can be defined via the
`INeighborhood`

interface. Currently, there are two different implementations available, each
providing several factory functions to instantiate and provide defaults for
different dimensions. See documentation and examples below.

#### Nearest

An `INeighborhood`

implementation for nearest neighbor queries around a given
target location, initial query radius and `IDistance`

metric to determine
proximity.

#### KNearest

An `INeighborhood`

implementation for K-nearest neighbor queries around a given
target location, initial query radius and `IDistance`

metric to determine
proximity. The K-nearest neighbors will be accumulated via an internal
heap and
results can be optionally returned in order of proximity (via `.deref()`

or
`.values()`

). For K=1 it will be more efficient to use `Nearest`

to avoid the
additional overhead.

### Status

**ALPHA** - bleeding edge / work-in-progress

Search or submit any issues for this package

Work is underway integrating this approach into the spatial indexing data structures provided by the @thi.ng/geom-accel package.

### Related packages

- @thi.ng/geom-accel - n-D spatial indexing data structures with a shared ES6 Map/Set-like API

## Installation

`yarn add @thi.ng/distance`

```
// ES module
<script type="module" src="https://unpkg.com/@thi.ng/distance?module" crossorigin></script>
// UMD
<script src="https://unpkg.com/@thi.ng/distance/lib/index.umd.js" crossorigin></script>
```

Package sizes (gzipped, pre-treeshake): ESM: 825 bytes / CJS: 929 bytes / UMD: 970 bytes

## Dependencies

## API

```
import * as d from "@thi.ng/distance";
const items = { a: 5, b: 16, c: 9.5, d: 2, e: 12 };
// collect the 3 nearest numbers for target=10 and using
// infinite selection radius and squared distance metric (defaults)
const k = d.knearestN(10, 3);
// consider each item for inclusion
Object.entries(items).forEach(([id, x]) => k.consider(x, id));
// retrieve result tuples of [distance, value]
k.deref()
// [ [ 25, 'a' ], [ 4, 'e' ], [ 0.25, 'c' ] ]
// result values only
k.values()
// [ 'a', 'e', 'c' ]
// neighborhood around 10, K=3 w/ max radius 5
// also use Eucledian distance and sort results by proximity
const k2 = d.knearestN(10, 3, 5, d.EUCLEDIAN1, true);
Object.entries(items).forEach(([id, x]) => k2.consider(x, id));
k2.deref()
// [ [ 0.5, 'c' ], [ 2, 'e' ], [ 5, 'a' ] ]
```

## Authors

Karsten Schmidt

If this project contributes to an academic publication, please cite it as:

```
@misc{thing-distance,
title = "@thi.ng/distance",
author = "Karsten Schmidt",
note = "https://thi.ng/distance",
year = 2021
}
```

## License

© 2021 Karsten Schmidt // Apache Software License 2.0