@allmaps/triangulate v1.0.0-beta.19
@allmaps/triangulate
This module triangulates a polygon: it returns a set of small triangule that partition the polygon.
It is used in @allmaps/render to triangulate the mask of a georeferenced map into a set of triangles that can be rendered with WebGL.
How it works
It uses a simple constrained Delaunay triangulation algorithm for polygons, built using poly2tri.js.
To learn more on how it works, check out this Observable notebook.
Installation
This is an ESM-only module that works in browsers and Node.js.
Install using npm:
npm install @allmaps/triangulate
Usage
import { triangulate } from '@allmaps/triangulate'
// polygons are not round-trip
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 mesh of size `distance`
const triangles = triangulate(polygon, distance)
// triangles = [
// [
// [1.3012562303117026, 2.3199729029037854],
// [0.304, 2.394],
// [1.304, 2.232]
// ],
// ...
// ]
API
Table of Contents
Triangulation
triangulate
Triangulates a polygon
Parameters
polygon
Ring Polygondistance
number Distance between the Steiner points placed in a grid inside the polygon
Returns Array<Triangle> Array of triangles partitioning the polygon
triangulatePoly2tri
Triangulates a polygon (and returns the full Poly2tri output)
Parameters
polygon
Ring Polygondistance
number Distance between the Steiner points placed in a grid inside the polygon
Returns Array<poly2tri.Triangle> Array of triangles partitioning the polygon
Types
The types used in this module are described below.
Triangle
Triangle as [[x0, y0], [x1, y1], [x2, y2]]
Type: Object
poly2tri.Triangle
Triangle object from poly2tri package
Type: Object
Ring
Polygon object, as an outer Ring only [[number, number], ...]
Type: Object
Notes
Stability
poly2tri
doesn't allow self-intersection polygons and will raise an error for such inputs.- For certain polygon vertex configurations an especially for round numbers or small distance sizes, poly2tri is known to throw errors such as 'point collinearity' or 'pointerror'.
Benchmark
For a 10 point polygon, here are some benchmarks for computing the triangulation with the distance as a fraction of the polygon's bbox diameter:
triangulate(polygon, 1)
: 66719 ops/s to compute 8 trianglestriangulate(polygon, bboxDiameter / 10)
: 10924 ops/s to compute 86 trianglestriangulate(polygon, bboxDiameter / 40)
: 1115 ops/s to compute 1048 trianglestriangulate(polygon, bboxDiameter / 100)
: 167 ops/s to compute 6216 triangles
See ./bench/index.js
.
To run the benchmark, run npm run bench
.
2 months ago
2 months ago
2 months ago
2 months ago
3 months ago
3 months ago
3 months ago
4 months ago
5 months ago
6 months ago
6 months ago
7 months ago
8 months ago
9 months ago
9 months ago