# concaveman: a concave hull for point sets, with a concavity knob

> concaveman is a JavaScript implementation of a 2D concave hull algorithm, a one function library that turns a point set into a general outline and lets you trade detail against simplicity with a concavity parameter. It suits a mapping or clustering use case that needs a boundary rather than a convex hull, and it is a geometry primitive rather than a full polygon library.

**mapbox/concaveman** — A very fast 2D concave hull algorithm in JavaScript

- Repository: https://github.com/mapbox/concaveman
- Stars: 724 · Forks: 84
- Language: JavaScript
- License: ISC
- Published: 2026-10-21 · Updated: 2026-10-21 · Language: en
- Canonical page: https://hysenlabs.com/projects/mapbox-concaveman

## One function, three parameters, one dependency list

concaveman is a very fast 2D concave hull algorithm in JavaScript, and the description spells out what it produces: a general outline of a point set.

That word outline is the whole design. A convex hull is the smallest convex polygon containing your points, which for a GPS trace or a cluster of markers is usually the wrong answer, because it fills in the concave parts where the data actually curves. A concave hull follows the shape of the data, and concaveman computes that.

The usage is three lines:

```js
import concaveman from 'concaveman';

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

The signature is concaveman(points[, concavity = 2, lengthThreshold = 0]). The points are an array of x, y pairs, the concavity defaults to 2 and the length threshold defaults to 0.

The repository is small in the way a focused library should be. The top-level entries are index.js, the test/ directory, a viz/ directory, an eslint config, a package-lock, a CODEOWNERS file and the licence. The package.json publishes a single file, index.js, and the package is an ES module with type set to module and exports pointing at index.js. The author is Vladimir Agafonkin, the licence is ISC, and the current version is 2.0.0 with a release date of 2025-07-16, the previous being 1.2.1 from 2021.

## Concavity and lengthThreshold are the two knobs, and both distort the result

The two parameters are documented in a way that tells you they are not neutral. Concavity is a relative measure of concavity. A value of 1 gives a relatively detailed shape, and Infinity gives a convex hull. The documentation also says you can use values lower than 1, but that they can produce pretty crazy shapes.

That is a good warning, and it points at the real nature of the parameter. Concavity is not a filter on the output, it is a parameter of the geometry, and moving it changes which points end up on the hull at all. There is no separate accuracy control, so a user who wants a slightly different shape is adjusting the same dial that controls how much of the shape is captured.

The second parameter is lengthThreshold. When a segment length is under this threshold, it stops being considered for further detail. Higher values result in simpler shapes.

The default of 0 means no threshold, so every segment is eligible for refinement and the concavity value alone controls the output. Setting a threshold is how you bound the work and force simplification, and it is the parameter to reach for when a particular dataset produces a shape with more vertices than the consumer can draw.

What the documentation does not give is guidance on choosing between them, or a statement of what the result means formally. The output is a polygon whose vertices are drawn from the input points, but the library's own description calls it a general outline, and the word outline carries the right warning: this is a boundary for drawing, not a guaranteed simple polygon with a documented topology contract.

## The performance claim comes from a specific algorithmic change

The algorithm section is where the library earns its speed claim, and the argument is precise rather than vague.

The algorithm is based on ideas from a 2012 paper, A New Concave Hull Algorithm and Concaveness Measure for n-dimensional Datasets, by Jin-Seo Park and Se-Jong Oh. The implementation is said to dramatically improve performance over the one stated in the paper, changing the complexity from O(rn), where r is the number of output points, to O(n log n).

The mechanism for that improvement is named: a fast k nearest points to a segment algorithm, described as a modification of a depth-first kNN R-tree search using a priority queue.

So the improvement is not a micro-optimisation of the published algorithm but a change in how the nearest-neighbour search is done, from a scan per segment to an indexed search. The dependency list confirms the shape of the implementation: rbush for point indexing, which is the R-tree, tinyqueue as the priority queue, point-in-polygon for the point in polygon queries, and `robust-predicates` for the three-point orientation tests.

That last dependency is the one to understand. Orientation tests are what decide whether a point is to the left or right of a line, and doing that in floating point arithmetic is subject to catastrophic cancellation when points are nearly collinear. The `robust-predicates` library exists to answer that question correctly, and its presence in the dependency list means concaveman is not taking the naive route.

## The dependency stack, and what each piece is doing

The four dependencies are all small and all from the same general orbit, which tells you this is a geometry utility rather than a framework.

rbush is used for point indexing. It is the R-tree that the modified kNN search depends on, and it is what turns the nearest-neighbour query from a linear scan into something logarithmic.

tinyqueue is the priority queue. In a depth-first kNN search with a priority queue, the queue is what orders the traversal, popping the closest candidate first, and that ordering is what makes the search stop early once the required neighbours are found.

point-in-polygon handles the point in polygon queries. That is the test used to decide whether a candidate point is already inside the region being built, which is how the algorithm avoids re-adding a point that the hull already encloses.

`robust-predicates` is used for the 3-point orientation tests. As noted, this is the numerical correctness piece.

Together they make a small, well-understood stack. The devDependencies are just eslint and eslint-config-mourner, and the package.json carries an eslintConfig block extending mourner directly, so the linting rules come from the same author who wrote the library.

The scripts are minimal: pretest runs eslint over index.js and the test files, and test runs node test/test.js. There is no build step, no bundler and no transpilation, which is consistent with publishing a single ES module file.

## TypeScript definitions, a C++ port and the state of the repository

TypeScript type definitions are available through DefinitelyTyped rather than shipping with the package, and the documentation gives the install command:

```bash
npm install --save @types/concaveman
```

That is a small detail with a practical consequence: the types are maintained by a separate project, so they track the library through a pull request rather than being released in lockstep with it.

There is also a C++ port, created in 2019 by a separate author, which the documentation points to as a way to use the algorithm efficiently from C or C++, from Python via cffi, and from other languages with an FFI or a plug-in mechanism for C, with a MATLAB MEX file given as an example of the latter. The approach differs in an important way: the port is a different codebase maintained elsewhere, so behaviour between the two implementations is not guaranteed to be identical, and a project choosing the port is taking on that dependency rather than the JavaScript package.

The maintenance picture is mixed. The repository is not archived and the last push was on 2026-06-24. The release history shows v2.0.0 on 2025-07-16 and then v1.2.1 and v1.2.0 both on 2021-08-09, so the 2.0 release was a four year gap followed by a major version bump, which in a library this small is usually a change in module format rather than in algorithm. The package.json version matches 2.0.0, and type is set to module with exports pointing at index.js, so v2 is the ES module version.

The CI badge points at Travis CI and there is a coverage badge, but both are from the era when the project was on that infrastructure, and the .github/ directory in the tree is where current workflow configuration would live.

## Where concaveman is the wrong tool

The first limit is that this is a geometry primitive, not a polygon library. The output is described as a general outline of a point set, and the documentation does not promise a valid simple polygon with a guaranteed topology. If your consumer needs a polygon it can rely on for point-in-polygon queries, for area computation, for offsetting, or for clipping, you have to reason about what the hull actually guarantees, and the documentation does not answer that in a form you can cite. A full geometry library is the right tool when the contract matters more than the speed.

The second limit is the parameter interaction. Concavity and lengthThreshold both change the output shape, and both are relative measures rather than absolute tolerances. There is no error metric in the output, so a caller cannot ask how far the outline is from the point set. If you need a boundary that provably contains all the points with a known margin, this library does not give you that, and picking a concavity value by eye is the only route the API offers.

The third is language. The JavaScript package is the reference implementation, and the C++ port is a separate project with its own maintenance. A team in Python, Rust or Go has to go through the port or an FFI, and the documentation is explicit that the port exists to make that possible rather than that the two are interchangeable.

The fourth is the age of the 1.x line. The 1.2.x releases are from 2021 and the 2.0.0 release is from 2025, with the last push in June 2026. The algorithm itself is settled and the paper it follows is from 2012, so there is little to expect in the way of new geometry, but a library whose npm release history has a four year gap is a dependency whose maintenance you should check rather than assume.

## Conclusion

concaveman is the right library for a JavaScript project that has a cloud of points and needs a boundary that follows the shape of the data, such as a GPS trace outline, a clustering region or a map marker hull, because it is a single function with a clear shape and the concavity parameter lets you move continuously from a detailed outline to the convex hull. It is the wrong tool for a job that needs topology guarantees, because the output is a boundary around points rather than a valid polygon in the computational geometry sense, and it is the wrong tool if you need to write the geometry in a language other than JavaScript, since the C++ port is a separate project. Before you use it, check the three things the documentation puts in front of you: the concavity value you pick, since the default of 2 is a compromise and Infinity gives the convex hull while values below 1 produce what the documentation calls pretty crazy shapes; the lengthThreshold, since a higher value gives simpler shapes and stops short segments being considered for further detail; and the numerical soundness of the orientation test, because the library depends on `robust-predicates` for the three-point orientation tests that decide which side of a line a point falls on.

## FAQ

### How do I use concaveman in JavaScript?

Import it and pass an array of x, y pairs. The signature is concaveman(points[, concavity = 2, lengthThreshold = 0]), so the simplest call is concaveman(points) on an array such as [[10, 20], [30, 12.5]], and the result is the outline polygon.

### What does the concavity parameter do in concaveman?

It is a relative measure of concavity. A value of 1 gives a relatively detailed shape and Infinity gives a convex hull, and values below 1 are allowed but the documentation warns they can produce pretty crazy shapes. The default is 2.

### Does concaveman have TypeScript types?

TypeScript type definitions are available through DefinitelyTyped rather than in the package itself, and the documentation gives the command npm install --save @types/concaveman. The package itself is published as a single ES module file, index.js.

## Sources

- [Issues](https://github.com/mapbox/concaveman/issues)
- [License: ISC](https://github.com/mapbox/concaveman/blob/master/LICENSE)
- [mapbox/concaveman on GitHub](https://github.com/mapbox/concaveman)
- [README](https://github.com/mapbox/concaveman/blob/master/README.md)
- [Releases](https://github.com/mapbox/concaveman/releases)

---

Hysen Labs editorial analysis, written from the project's own repository and release notes. Cite the canonical page: https://hysenlabs.com/projects/mapbox-concaveman