Skip to content

Latest commit

 

History

History

distance

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

@thi.ng/distance

npm version npm downloads Mastodon Follow

Note

This is one of 199 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

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 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

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.

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.

Status

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.

Support packages

Related packages

  • @thi.ng/geom-accel - n-D spatial indexing data structures with a shared ES6 Map/Set-like API
  • @thi.ng/k-means - Configurable k-means & k-medians (with k-means++ initialization) for n-D vectors
  • @thi.ng/vectors - Optimized 2d/3d/4d and arbitrary length vector operations, support for memory mapping/layouts

Installation

yarn add @thi.ng/distance

ESM import:

import * as dist from "@thi.ng/distance";

Browser ESM import:

<script type="module" src="https://esm.run/@thi.ng/distance"></script>

JSDelivr documentation

For Node.js REPL:

const dist = await import("@thi.ng/distance");

Package sizes (brotli'd, pre-treeshake): ESM: 1.37 KB

Dependencies

Note: @thi.ng/api is in most cases a type-only import (not used at runtime)

Usage examples

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

API

Generated API docs

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

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 - 2024 Karsten Schmidt // Apache License 2.0