poly-decomp-es

This is a maintained fork of poly-decomp.js, originally created by Stefan Hedman @schteppe.

poly-decomp-es is a library for decomposing a 2D polygon into convex pieces.

npm install poly-decomp-es
yarn add poly-decomp-es

Launch the demo!

The library implements two algorithms, one optimal (but slow) and one less optimal (but fast).

It's is a manual port of the C++ library Poly Decomp by Mark Penner.

Basic usage

1import { decomp, makeCCW, quickDecomp } from 'poly-decomp-es'
2
3// Create a concave polygon
4const concavePolygon = [
5  [-1, 1],
6  [-1, 0],
7  [1, 0],
8  [1, 1],
9  [0.5, 0.5],
10]
11
12// Make sure the polygon has counter-clockwise winding. Skip this step if you know it's already counter-clockwise.
13makeCCW(concavePolygon)
14
15// Decompose into convex polygons, using the faster algorithm
16const convexPolygons = quickDecomp(concavePolygon)
17
18// ==> [  [[1,0],[1,1],[0.5,0.5]],  [[0.5,0.5],[-1,1],[-1,0],[1,0]]  ]
19
20// Decompose using the slow (but optimal) algorithm
21const optimalConvexPolygons = decomp(concavePolygon)
22
23// ==> [  [[-1,1],[-1,0],[1,0],[0.5,0.5]],  [[1,0],[1,1],[0.5,0.5]]  ]

Advanced usage

1import { isSimple, makeCCW, quickDecomp } from 'poly-decomp-es'
2
3// Get user input as an array of points.
4const polygon = getUserInput()
5
6// Check if the polygon self-intersects
7if (isSimple(polygon)) {
8  // Reverse the polygon to make sure it uses counter-clockwise winding
9  makeCCW(polygon)
10
11  // Decompose into convex pieces
12  const convexPolygons = quickDecomp(polygon)
13
14  // Draw each point on an HTML5 Canvas context
15  for (let i = 0; i < convexPolygons.length; i++) {
16    const convexPolygon = convexPolygons[i]
17
18    ctx.beginPath()
19    const firstPoint = convexPolygon[0]
20    ctx.moveTo(firstPoint[0], firstPoint[1])
21
22    for (let j = 1; j < convexPolygon.length; j++) {
23      const point = convexPolygon[j]
24      const x = point[0]
25      const y = point[1]
26      c.lineTo(x, y)
27    }
28    ctx.closePath()
29    ctx.fill()
30  }
31}

Documentation

type Point = [number, number]

type Polygon = Point[]

quickDecomp(polygon: Polygon): Polygon[]

1import { quickDecomp } from 'poly-decomp-es'
2
3const convexPolygons = quickDecomp(polygon)

Slices the polygon into convex sub-polygons, using a fast algorithm. Note that the input points objects will be re-used in the result array.

If the polygon is not simple, the decomposition will produce unexpected results.

decomp(polygon: Polygon): Polygon[] | false

1import { decomp } from 'poly-decomp-es'
2
3const convexPolygons = decomp(polygon)

Decomposes the polygon into one or more convex sub-polygons using an optimal algorithm. Note that the input points objects will be re-used in the result array.

Returns false if the decomposition fails.

isSimple(polygon: Polygon): boolean

1import { isSimple, quickDecomp } from 'poly-decomp-es'
2
3if (isSimple(polygon)) {
4  // Polygon does not self-intersect - it's safe to decompose.
5  const convexPolygons = quickDecomp(polygon)
6}

Returns true if the polygon does not self-intersect. Use this to check if the input polygon is OK to decompose.

makeCCW(polygon: Polygon): void

1import { makeCCW } from 'poly-decomp-es'
2
3console.log('Polygon with clockwise winding:', polygon)
4makeCCW(polygon)
5console.log('Polygon with counter-clockwise winding:', polygon)

Reverses the polygon, if its vertices are not ordered counter-clockwise. Note that the input polygon array will be modified in place.

removeCollinearPoints(polygon: Polygon, thresholdAngle = 0): void

1import { removeCollinearPoints } from 'poly-decomp-es'
2
3const before = polygon.length
4removeCollinearPoints(polygon, 0.1)
5const numRemoved = before - polygon.length
6console.log(numRemoved + ' collinear points could be removed')

Removes collinear points in the polygon. This means that if three points are placed along the same line, the middle one will be removed. The thresholdAngle is measured in radians and determines whether the points are collinear or not. Note that the input array will be modified in place.

removeDuplicatePoints(polygon: Polygon, precision = 0): void

1import { removeDuplicatePoints } from 'poly-decomp-es'
2
3const polygon = [
4  [0, 0],
5  [1, 1],
6  [2, 2],
7  [0, 0],
8]
9removeDuplicatePoints(polygon, 0.01)
10
11// polygon is now [[1,1],[2,2],[0,0]]