/polygon-clipping

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

Primary LanguageJavaScriptMIT LicenseMIT

polygon-clipping

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

npm version build status test coverage

Quickstart

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

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

polygonClipping.union       (<geom>, ...<geoms>)
polygonClipping.intersection(<geom>, ...<geoms>)
polygonClipping.xor         (<geom>, ...<geoms>)

/* The clipGeoms will be subtracted from the subjectGeom */
polygonClipping.difference(<subjectGeom>, ...<clipGeoms>)

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

v0.9 (2018-10-17)

  • Performance improvements (#26)
  • Bug fixes (#36, #38)

v0.8 (2018-08-30)

  • Export a default es6 module (#33)
  • Allow self-crossing rings using even-odd rule (#30)
  • Fix bug with nearly vertical segments being split (#29)
  • Fix bug with coincident segments being split slightly differently (#22)

v0.7 (2018-06-06)

v0.6.1 (2018-04-01)

  • Performance improvements
  • Drop (within rounding error) infinitely thin rings from output (#14)

v0.6 (2018-03-26)

  • Ensure output rings are not self-intersecting (#11)
  • Allow self-touching (but not crossing) input rings (#10)
  • Support empty MultiPolygons as input
  • Performance improvements (reduced memory footprint and lower CPU time)
  • Handle segments with many coincidents (#7)
  • Handle very thin input polygons (#6)

v0.5 (2018-03-01)

  • Remove clean() from module.exports (#3)
  • Expand difference() operation to optionally take multiple clippings (#1)
  • Use splay-tree instead of avl to power the sweep line status tree (#2)

v0.4 (2018-02-27)

  • First release as new package after fork from martinez

Authors

Based on