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.