This project is part of the @thi.ng/umbrella monorepo.
N-dimensional distance metrics & K-nearest neighborhoods for point queries.
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 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.
An INeighborhood
implementation for nearest neighbor queries around a given
target location, initial query radius and IDistance
metric to determine
proximity.
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.
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.
- @thi.ng/geom-accel - n-D spatial indexing data structures with a shared ES6 Map/Set-like API
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
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' ] ]
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
}
© 2021 Karsten Schmidt // Apache Software License 2.0