polygon-clipping

Apply boolean Polygon clipping operations (intersection, union, difference, xor) to your Polygons & MultiPolygons.


Quickstart

``javascript
const polygonClipping = require('polygon-clipping')

const poly1 = [[[0,0],[2,0],[0,2],[0,0]]]
const poly2 = [[[-1,0],[1,0],[0,1],[-1,0]]]

polygonClipping.union (poly1, poly2 / , poly3, ... /)
polygonClipping.intersection(poly1, poly2 / , poly3, ... /)
polygonClipping.xor (poly1, poly2 / , poly3, ... /)
polygonClipping.difference (poly1, poly2 / , poly3, ... /)
`

API

`javascript
/ All functions take one or more [multi]polygon(s) as input /

polygonClipping.union (, ...)
polygonClipping.intersection(, ...)
polygonClipping.xor (, ...)

/ The clipGeoms will be subtracted from the subjectGeom /
polygonClipping.difference(, ...)
`

$3

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 even-odd 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.

$3

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.

Changelog

This project adheres to Semantic Versioning.

The full changelog is available at CHANGELOG.md.

Authors

* Mike Fogel
* Alexander Milevski
* Vladimir Ovsyannikov

Sponsors

* EasyTerritory

Please contact Mike Fogel if you or your company is interested in sponsoring work on specific bug fixes or feature requests.

Based on

* A new algorithm for computing Boolean operations on polygons by Francisco Martinez, Antonio Jesus Rueda, Francisco Ramon Feito (2009)