Polygon Libraries

Problem

For drawing areas of shadings, hydrology, zones, etc., we need to transform a set of points, drawn using a brush, into a polygon. Furthermore, we want to be able to create unions of polygons so that areas can be expanded and differences of polygons to reduce areas.

Constraints

• Algorithms need to be fast enough so that users won't recognize any delays.

Assumptions

• We assume that there are no alternative packages readily available that offer significantly better performance or features than the ones we have explored.

Solutions

graham_scan

graham-scan is an implementation of the Graham Scan algorithm to calculate a convex hull from a given set of points.

• Easy to integrate.
• It only provides convex hull calculation.

hull.js

hull.js provides functions for calculating convex and concave hulls from a given set of points.

• Concavity can be configured by a parameter.
• Very easy to integrate.
• Fast calculation.

polygon-clipping

polygon-clipping provides boolean polygon operations like intersection, union, and difference.

• Well maintained.

Further packages

• There are several other packages like flatten-js/boolean-op. However, most of them haven't been updated in a long time.

Note: Click here to see an image that shows the difference between convex and concave hulls.

Decision

We decided to use hull.js for calculating hulls and polygon-clipping for union operations.

Rationale

Hull Calculation

• hull.js is very easy to integrate. We already tested it in the drawing layer and it was easy to calculate a polygon by passing a set of drawn points.
• The calculation is very fast.
• We can configure how precisely the polygon should match the drawn shape.

Boolean Operation

• polygon-clipping provides all the operations we need to unify polygons and it is regularly updated.