# concaveman

> Fast 2D concave hull algorithm in JavaScript (generates an outline of a point set)

Latest version **2.0.0** (published 2025-07-16) · ISC license · 0 weekly downloads

## Install

```sh
npm install concaveman
pnpm add concaveman
yarn add concaveman
bun add concaveman
```

## Health

**Score 48/100 (D)** — status: stable.

Positive: has types package; esm support; no vulnerabilities; high quality score.

Warnings: low downloads.

Negative: stale.

## Facts

| | |
|---|---|
| Version | 2.0.0 |
| Published | 2025-07-16 |
| First published | 2016-02-11 |
| Weekly downloads | 0 |
| License | ISC |
| TypeScript types | separate (@types/concaveman) |
| Module format | ESM + CommonJS |
| Dependencies | 4 |
| Unpacked size | 14.5 KB |
| Known vulnerabilities | 0 |
| Install scripts | no |
| GitHub stars | 724 |
| Author | Vladimir Agafonkin |
| Maintainers | 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, mbx-npm-ci-staging, mbx-npm-ci-production, mbx-npm-01-production, mbx-npm-02-production, mbx-npm-03-production, mbx-npm-04-production, mbx-npm-05-production, mbx-npm-06-production, mbx-npm-07-production, mbx-npm-08-production, mbx-npm-09-production, mbx-npm-02-staging, mbx-npm-advanced-actions-staging, mbx-npm-advanced-actions-production |
| Keywords | concave, hull, algorithm, geometry, shape, outline |

## Links

- npm: https://www.npmjs.com/package/concaveman
- Repository: https://github.com/mapbox/concaveman
- Homepage: https://github.com/mapbox/concaveman#readme
- Issues: https://github.com/mapbox/concaveman/issues
- npm.io page: https://npm.io/package/concaveman

## Dependencies (4)

- [rbush](https://npm.io/package/rbush.md) ^4.0.1
- [tinyqueue](https://npm.io/package/tinyqueue.md) ^3.0.0
- [point-in-polygon](https://npm.io/package/point-in-polygon.md) ^1.1.0
- [robust-predicates](https://npm.io/package/robust-predicates.md) ^3.0.2

## Recent versions

- 2.0.0 (latest) — 2025-07-16
- 1.2.1 — 2021-08-09
- 1.2.0 — 2020-05-18
- 1.1.1 — 2016-09-26
- 1.1.0 — 2016-02-15
- 1.0.0 — 2016-02-11

## README

## concaveman

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

[![Build Status](https://travis-ci.org/mapbox/concaveman.svg?branch=master)](https://travis-ci.org/mapbox/concaveman)
[![Coverage Status](https://coveralls.io/repos/github/mapbox/concaveman/badge.svg?branch=master)](https://coveralls.io/github/mapbox/concaveman?branch=master)
[![](https://img.shields.io/badge/simply-awesome-brightgreen.svg)](https://github.com/mourner/projects)

<img width="570" alt="sample concave hull" src="https://cloud.githubusercontent.com/assets/25395/12975726/ada2ad10-d0c6-11e5-96c8-6e42c995e0e2.png">

### Usage

```js
import concaveman from 'concaveman';

const points = [[10, 20], [30, 12.5], ...];
const 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.

### Algorithm

The algorithm is based on ideas from the paper [A New Concave Hull Algorithm and Concaveness Measure
for n-dimensional Datasets, 2012](https://jise.iis.sinica.edu.tw/JISESearch/fullText?pId=245&code=5A9B97538372AA1)
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

[TypeScript type definitions](https://github.com/DefinitelyTyped/DefinitelyTyped/tree/master/types/concaveman)
are available through `npm install --save @types/concaveman`.

### Dependencies

- [rbush](https://github.com/mourner/rbush) for point indexing
- [tinyqueue](https://github.com/mourner/tinyqueue) as a priority queue
- [point-in-polygon](https://github.com/substack/point-in-polygon) for point in polygon queries
- [robust-predicates](https://github.com/mourner/robust-predicates) for 3-point orientation tests

### C++ Port

In 2019, a [C++ port](https://github.com/sadaszewski/concaveman-cpp) 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).

---
_Source: https://npm.io/package/concaveman · Machine-readable twin of the npm.io package page. Health data is recomputed on every publish._