@thi.ng/distance
    TypeScript icon, indicating that this package has built-in type declarations

    2.0.3 • Public • Published

    distance

    npm version npm downloads Twitter Follow

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

    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.

    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

    Installation

    yarn add @thi.ng/distance

    ES module import:

    <script type="module" src="https://cdn.skypack.dev/@thi.ng/distance"></script>

    Skypack documentation

    For Node.js REPL:

    # with flag only for < v16
    node --experimental-repl-await
    
    > const distance = await import("@thi.ng/distance");
    

    Package sizes (gzipped, pre-treeshake): ESM: 1.13 KB

    Dependencies

    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

    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

    Install

    npm i @thi.ng/distance

    DownloadsWeekly Downloads

    219

    Version

    2.0.3

    License

    Apache-2.0

    Unpacked Size

    51.6 kB

    Total Files

    22

    Last publish

    Collaborators

    • thi.ng