# polygon-clipping

Apply boolean Polygon clipping operations (`intersection`

, `union`

, `difference`

, `xor`

) to your Polygons & MultiPolygons.

## Quickstart

`const polygonClipping = const poly1 = 00200200const poly2 = -101001-10 polygonClippingpolygonClippingpolygonClippingpolygonClipping`

## API

`/* All functions take one or more [multi]polygon(s) as input */ polygonClippingpolygonClippingpolygonClipping /* The clipGeoms will be subtracted from the subjectGeom */polygonClipping`

### Input

Each positional argument (`<geom>`

) 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.

### 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.

## Changelog

This project adheres to Semantic Versioning.

The full changelog is available at CHANGELOG.md.

## Authors

## Sponsors

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)