@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
    • Parameters
  • triangulatePoly2tri
    • Parameters
• Types
  • poly2tri.Triangle
• triangulateToUnique
  • Parameters

Triangulation

triangulate

Triangulates a polygon

Parameters

• polygon Ring Polygon
• distance 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 Polygon
• distance 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.

poly2tri.Triangle

Triangle object from poly2tri package

Type: Object

triangulateToUnique

Triangulates a polygon and return unique points. Grid points typically occure in 6 triangles This function reutrns the list of unique points, and returns the triangles as uniquePointsIndexTriangles with indices refering to the unique points

Parameters

• polygon Ring Polygon
• distance number Distance between the Steiner points placed in a grid inside the polygon

Returns {uniquePointsIndexTriangles: Array<UniquePointsIndexTriangle>, uniquePoints: Array<Point>} Object with uniquePointsIndexTriangles and uniquePoints

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 triangles
• triangulate(polygon, bboxDiameter / 10): 10924 ops/s to compute 86 triangles
• triangulate(polygon, bboxDiameter / 40): 1115 ops/s to compute 1048 triangles
• triangulate(polygon, bboxDiameter / 100): 167 ops/s to compute 6216 triangles

See ./bench/index.js.

To run the benchmark, run npm run bench.