# @allmaps/triangulate

> Allmaps Triangulation Library

Latest version **1.0.0-beta.34** (published 2026-09-22) · MIT license · 0 weekly downloads

## Install

```sh
npm install @allmaps/triangulate
pnpm add @allmaps/triangulate
yarn add @allmaps/triangulate
bun add @allmaps/triangulate
```

## Health

**Score 60/100 (C)** — status: active.

Positive: esm support; no vulnerabilities; recently updated; high maintenance score.

Warnings: low downloads; no types.

## Facts

| | |
|---|---|
| Version | 1.0.0-beta.34 |
| Published | 2026-09-22 |
| First published | 2023-08-21 |
| Weekly downloads | 0 |
| License | MIT |
| TypeScript types | none |
| Module format | ESM |
| Dependencies | 6 |
| Unpacked size | 26.4 KB |
| Known vulnerabilities | 0 |
| Install scripts | no |
| GitHub stars | 143 |
| Author | Manuel Claeys Bouuaert |
| Maintainers | bertspaan |
| Keywords | allmaps, triangulate, polygon triangulation, Constrained Delaunay Triangulation, Delaunator, Constrainautor |

## Links

- npm: https://www.npmjs.com/package/@allmaps/triangulate
- Repository: https://github.com/allmaps/allmaps
- Homepage: https://allmaps.org
- Issues: https://github.com/allmaps/allmaps/issues
- npm.io page: https://npm.io/package/@allmaps/triangulate

## Dependencies (6)

- [kdbush](https://npm.io/package/kdbush.md) ^4.1.0
- [delaunator](https://npm.io/package/delaunator.md) ^5.0.1
- [@allmaps/types](https://npm.io/package/@allmaps/types.md) ^1.0.0-beta.24
- [@allmaps/stdlib](https://npm.io/package/@allmaps/stdlib.md) ^1.0.0-beta.42
- [robust-predicates](https://npm.io/package/robust-predicates.md) ^3.0.3
- [@kninnug/constrainautor](https://npm.io/package/@kninnug/constrainautor.md) ^4.0.1

## Recent versions

- 1.0.0-beta.34 (latest) — 2026-09-22
- 1.0.0-beta.26 (beta) — 2025-05-22
- 1.0.0-beta.33 — 2026-05-28
- 1.0.0-beta.32 — 2026-02-09
- 1.0.0-beta.31 — 2025-11-27
- 1.0.0-beta.30 — 2025-11-10
- 1.0.0-beta.29 — 2025-07-19
- 1.0.0-beta.28 — 2025-07-09
- 1.0.0-beta.27 — 2025-07-07
- 1.0.0-beta.25 — 2025-03-12
- 1.0.0-beta.23 — 2024-10-31
- 1.0.0-beta.22 — 2024-08-20
- 1.0.0-beta.21 — 2024-08-16
- 1.0.0-beta.20 — 2024-05-29
- 1.0.0-beta.19 — 2024-03-19
- … 14 more at https://npm.io/package/@allmaps/triangulate/versions

## README

# @allmaps/triangulate

This package provides methods to triangulate a polygon: i.e. return a set of triangles that partition the polygon.

It does this in a constrained way, where the triangles meet certain conditions: if a `distance` parameter is provided, the triangles are not larger than `distance`, and in general don't contain very sharp angles or very blunt angles.

This package is used internally in [@allmaps/render](../../packages/render/) to triangulate the full mask of a georeferenced map (using the GCPs as Steiner points and the appliable mask as Steiner polygons) into a set of triangles that can be rendered with WebGL.

## How it works

It uses a modern **constrained Delaunay triangulation algorithm** for polygons, built using [Delaunator](https://github.com/mapbox/delaunator) and [Constrainautor](https://github.com/kninnug/Constrainautor).

To learn more on how it works, check out this [Observable notebook](https://observablehq.com/d/efde1d04f1a9bc17).

In short, triangles are made firstly using a grid of points within the bounding box of the polygon, spaced `distance` apart, and with points resulting from the polygons edges (interpolated using `distance`), provided Steiner points and points from the Steiner Polygons. From all these points, a Delaunay triangulation is performed. This results in most grid cell resulting in two well-conditioned triangles. Then the triangulation is constrained with the edges of the interpolated polygon and the edges of the interpolated Steiner polygons.

## Installation

This is an ESM-only module that works in browsers and Node.js.

Install with pnpm:

```sh
pnpm install @allmaps/triangulate
```

## Usage

This package exposes two functions: `triangulate()` simply triangulates a polygon and returns the triangles, and `triangulateToUnique()` returns a set of objects that describe the triangulation using an array of unique points and edges between them.

In the simplest case, it can be used as follows:

```js
import { triangulate } from '@allmaps/triangulate'

// Note that polygons are in double brackets (an array of an outer ring, and possibly inner rings if there are holes) and their rings are not round-trip (the first coordinate is not repeated at the and)
const polygon = [
  [
    [0.592, 0.953],
    [0.304, 2.394],
    [2.904, 2.201],
    [2.394, 0.232]
  ]
]

const distance = 1

// Compute constrained triangulation of `polygon` using a grid of size `distance`
const triangles = triangulate(polygon, distance)

// triangles = [
//   [
//     [ 1.304, 1.232 ],
//     [ 1.4655588463411926, 0.6034795070965593 ],
//     [ 0.592, 0.953 ]
//   ],
//   ...
// ]
```

To both functions, the following options can be passed:

* `steinerPoints`: Steiner points. These become a third group of points taken into account when building the triangles.
* `steinerPolygons`: Steiner polygons. These are polygons whose points need to be added as Steiner points, and whose edges (interpolated using distance) also need to be constrained.
* `minimumTriangleAngle`: The minimum angle (in radians) of the resulting triangles. Using this options, sliver polygons that are possibly produced by internal functions can be removed. Default: `0.01`.
* `computeInsideSteinerPolygons`: Whether or not to compute, for each triangle, whether they are inside the Steiner polygons or not.

## License

MIT

## API

## Notes

### Stability

* Constrainautor doesn't allow self-intersection polygons and will raise an error for such inputs.

### Benchmark

For a 10 point polygon (with diameter ~ 200), here are some benchmarks for computing the triangulation with given distances:

* `triangulate(polygon, 1000)` (no grid points): 74544 ops/s to compute 8 triangles
* `triangulate(polygon, 100)`: 56849 ops/s to compute 11 triangles
* `triangulate(polygon, 10)`: 2163 ops/s to compute 435 triangles
* `triangulate(polygon, 1)`: 3 ops/s to compute 38352 triangles

See [`./bench/index.js`](`./bench/index.js`).

To run the benchmark, run `npm run bench`.

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