Nightingale Posing Mischievously

    DefinitelyTyped icon, indicating that this package has TypeScript declarations provided by the separate @types/concaveman package

    1.2.0 • Public • Published


    A very fast 2D concave hull algorithm in JavaScript (generates a general outline of a point set).

    Build Status Coverage Status

    sample concave hull


    var points = [[10, 20], [30, 12.5], ...];
    var polygon = concaveman(points);

    Signature: concaveman(points[, concavity = 2, lengthThreshold = 0])

    • points is an array of [x, y] points.
    • concavity is a relative measure of concavity. 1 results in a relatively detailed shape, Infinity results in a convex hull. You can use values lower than 1, but they can produce pretty crazy shapes.
    • lengthThreshold: when a segment length is under this threshold, it stops being considered for further detalization. Higher values result in simpler shapes.


    The algorithm is based on ideas from the paper A New Concave Hull Algorithm and Concaveness Measure for n-dimensional Datasets, 2012 by Jin-Seo Park and Se-Jong Oh.

    This implementation dramatically improves performance over the one stated in the paper (O(rn), where r is a number of output points, to O(n log n)) by introducing a fast k nearest points to a segment algorithm, a modification of a depth-first kNN R-tree search using a priority queue.


    TypeScript type definitions are available trough npm install --save @types/concaveman.


    C++ Port

    In 2019, a C++ port has been created, allowing for efficient usage from C/C++, Python (via cffi) and other languages featuring an FFI and/or plug-in mechanism for C (e.g. a MATLAB MEX file should be easy to prepare).


    npm i concaveman@1.2.0





    Unpacked Size

    14.9 kB

    Total Files


    Last publish


    • mbx-npm-ci-production
    • mbx-npm-ci-staging
    • mbx-npm-advanced-actions-production
    • mbx-npm-advanced-actions-staging
    • mbx-npm-09-production
    • mbx-npm-08-production
    • mbx-npm-07-production
    • mbx-npm-06-production
    • mbx-npm-05-production
    • mbx-npm-04-production
    • mbx-npm-03-production
    • mbx-npm-02-production
    • mbx-npm-01-production
    • mbx-npm-02-staging
    • mapbox-npm-01
    • mapbox-npm-02
    • mapbox-npm-07
    • mapbox-npm-03
    • mapbox-npm-04
    • mapbox-npm-09
    • mapbox-npm-05
    • mapbox-npm-06
    • mapbox-npm-08
    • mapbox-npm-advanced-actions
    • mapbox-npm-ci
    • mapbox-npm
    • mapbox-admin
    • mapbox-machine-user