N-dimensional distance metrics & K-nearest neighborhoods for point queries
npm install @thi.ng/distance
!npm downloads

> [!NOTE]
> This is one of 214 standalone projects, maintained as part
> of the @thi.ng/umbrella monorepo
> and anti-framework.
>
> 🚀 Please help me to work full-time on these projects by sponsoring me on
> GitHub. Thank you! ❤️
- About
- Distance metrics
- Neighborhoods
- Nearest
- KNearest
- Radial
- Status
- Support packages
- Related packages
- Installation
- Dependencies
- Usage examples
- API
- Authors
- License
N-dimensional distance metrics & K-nearest neighborhoods for point queries.
The package provides theIDistance
interface for custom distance metric implementations & conversions from/to raw
distance values. The following preset metrics are provided too:
| Preset | Number | nD | 2D | 3D | Comments |
|--------------------|------------|--------|--------|--------|----------------------------------------------------------------------|
| EUCLEDIAN | | ✅ | | | Eucledian distance |
| EUCLEDIAN1 | ✅ | | | | |
| EUCLEDIAN2 | | | ✅ | | |
| EUCLEDIAN3 | | | | ✅ | |
| HAVERSINE_LATLON | | | ✅ | | Great-circle distance for lat/lon geo locations |
| HAVERSINE_LONLAT | | | ✅ | | Great-circle distance for lon/lat geo locations |
| 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 usedIDeref
interface to obtain the final query results.
Custom neighborhood selections can be defined via theINeighborhood
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.
#### Radial
An unbounded and unsorted version of KNearest, selecting _all_
items around the target location and given search radius. Qualifying neighbors
will be accumulated in order of processing via an internal array.
STABLE - used in production
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/distance-transform - Binary image to Distance Field transformation
- @thi.ng/geom-accel - n-D spatial indexing data structures with a shared ES6 Map/Set-like API
- @thi.ng/k-means - k-means & k-medians with customizable distance functions and centroid initializations for n-D vectors
- @thi.ng/vectors - Optimized 2d/3d/4d and arbitrary length vector operations, support for memory mapping/layouts
``bash`
yarn add @thi.ng/distance
ESM import:
`ts`
import * as dist from "@thi.ng/distance";
Browser ESM import:
`html`
For Node.js REPL:
`js`
const dist = await import("@thi.ng/distance");
Package sizes (brotli'd, pre-treeshake): ESM: 1.41 KB
- @thi.ng/api
- @thi.ng/checks
- @thi.ng/errors
- @thi.ng/heaps
- @thi.ng/math
- @thi.ng/vectors
Note: @thi.ng/api is in _most_ cases a type-only import (not used at runtime)
One project in this repo's
/examples
directory is using this package:
| Screenshot | Description | Live demo | Source |
|:---------------------------------------------------------------------------------------------------------------------|:------------------------------------------|:----------------------------------------------------|:---------------------------------------------------------------------------------|
|
| K-nearest neighbor search in an hash grid | Demo | Source |
`ts
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' ] ]
`
If this project contributes to an academic publication, please cite it as:
`bibtex``
@misc{thing-distance,
title = "@thi.ng/distance",
author = "Karsten Schmidt",
note = "https://thi.ng/distance",
year = 2021
}
© 2021 - 2026 Karsten Schmidt // Apache License 2.0