@arbendium/polyclip
v0.1.0
Published
Apply boolean polygon clipping operations (intersection, union, difference, xor) to your Polygons & MultiPolygons.
Downloads
12
Maintainers
Readme
polyclip
Apply boolean polygon clipping operations (intersection
, union
, difference
, xor
) to your Polygons & MultiPolygons.
Quickstart
import * as polyclip from "polyclip"
const poly1 = [[[0,0],[2,0],[0,2],[0,0]]]
const poly2 = [[[-1,0],[1,0],[0,1],[-1,0]]]
polyclip.union (poly1, poly2 /* , poly3, ... */)
polyclip.intersection(poly1, poly2 /* , poly3, ... */)
polyclip.xor (poly1, poly2 /* , poly3, ... */)
polyclip.difference (poly1, poly2 /* , poly3, ... */)
API
/* All functions take one or more [multi]polygon(s) as input */
polyclip.union (geometry, ...otherGeometries)
polyclip.intersection(geometry, ...otherGeometries)
polyclip.xor (geometry, ...otherGeometries)
/* The `otherGeometries` will be subtracted from `geometry` */
polyclip.difference (geometry, ...otherGeometries)
Input
Each positional argument may be either a Polygon or a MultiPolygon. The GeoJSON spec is followed, with the following notes/modifications:
- MultiPolygons may contain touching or overlapping Polygons.
- rings are not required to be self-closing.
- rings may contain repeated points, which are ignored.
- rings may be self-touching and/or self-crossing. Self-crossing rings will be interpreted using the non-zero rule.
- winding order of rings does not matter.
- inner rings may extend outside their outer ring. The portion of inner rings outside their outer ring is dropped.
- inner rings may touch or overlap each other.
Output
For non-empty results, output will always be a MultiPolygon containing one or more non-overlapping, non-edge-sharing Polygons. The GeoJSON spec is followed, with the following notes/modifications:
- outer rings will be wound counter-clockwise, and inner rings clockwise.
- inner rings will not extend outside their outer ring.
- rings will not overlap, nor share an edge with each other.
- rings will be self-closing.
- rings will not contain repeated points.
- rings will not contain superfluous points (intermediate points along a straight line).
- rings will not be self-touching nor self-crossing.
- rings may touch each other, but may not cross each other.
In the event that the result of the operation is the empty set, output will be a MultiPolygon with no Polygons: []
.
Correctness
Run: npm test
The tests are broken up into unit tests and end-to-end tests. The end-to-end tests are organized as GeoJSON files, to make them easy to visualize thanks to GitHub's helpful rendering of GeoJSON files. Browse those tests here.
Performance
The Martinez-Rueda-Feito polygon clipping algorithm is used to compute the result in O((n+k)*log(n))
time, where n
is the total number of edges in all polygons involved and k
is the number of intersections between edges.
Authors
Based on
- A simple algorithm for Boolean operations on polygons by Francisco Martinez, Antonio Jesus Rueda, Francisco Ramon Feito (2009)