polygon-clipping

What is polygon-clipping?

The polygon-clipping npm package is a library for performing boolean operations on polygons, such as union, intersection, difference, and xor. It is useful for computational geometry tasks, particularly in GIS (Geographic Information Systems) and CAD (Computer-Aided Design) applications.

What are polygon-clipping's main functionalities?

Union

The union operation combines two or more polygons into a single polygon that covers the area of all input polygons.

const polygonClipping = require('polygon-clipping');
const polygon1 = [[[0, 0], [4, 0], [4, 4], [0, 4], [0, 0]]];
const polygon2 = [[[2, 2], [6, 2], [6, 6], [2, 6], [2, 2]]];
const union = polygonClipping.union(polygon1, polygon2);
console.log(union);

Intersection

The intersection operation finds the overlapping area between two or more polygons.

const polygonClipping = require('polygon-clipping');
const polygon1 = [[[0, 0], [4, 0], [4, 4], [0, 4], [0, 0]]];
const polygon2 = [[[2, 2], [6, 2], [6, 6], [2, 6], [2, 2]]];
const intersection = polygonClipping.intersection(polygon1, polygon2);
console.log(intersection);

Difference

The difference operation subtracts the area of one polygon from another, resulting in the parts of the first polygon that are not overlapped by the second polygon.

const polygonClipping = require('polygon-clipping');
const polygon1 = [[[0, 0], [4, 0], [4, 4], [0, 4], [0, 0]]];
const polygon2 = [[[2, 2], [6, 2], [6, 6], [2, 6], [2, 2]]];
const difference = polygonClipping.difference(polygon1, polygon2);
console.log(difference);

XOR

The XOR operation finds the areas that are covered by either of the polygons but not by both.

const polygonClipping = require('polygon-clipping');
const polygon1 = [[[0, 0], [4, 0], [4, 4], [0, 4], [0, 0]]];
const polygon2 = [[[2, 2], [6, 2], [6, 6], [2, 6], [2, 2]]];
const xor = polygonClipping.xor(polygon1, polygon2);
console.log(xor);

Other packages similar to polygon-clipping

turf

Turf is a powerful geospatial analysis library for JavaScript. It provides a wide range of spatial operations, including boolean operations on polygons. Compared to polygon-clipping, Turf offers a broader set of geospatial functions but may be more complex to use for simple polygon operations.

jsts

JSTS (JavaScript Topology Suite) is a JavaScript library for processing geometries. It includes a variety of spatial operations, such as union, intersection, and difference. JSTS is more comprehensive in terms of geometry processing capabilities but can be more heavyweight compared to polygon-clipping.

martinez-polygon-clipping

Martinez Polygon Clipping is another library for performing boolean operations on polygons. It is similar to polygon-clipping in terms of functionality but uses a different algorithm (Martinez-Rueda) for polygon clipping, which may result in different performance characteristics.

README

polygon-clipping

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

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

Settings

Global settings are set via environment variables.

• POLYGON_CLIPPING_MAX_QUEUE_SIZE and POLYGON_CLIPPING_MAX_SWEEPLINE_SEGMENTS: Aims to prevent infinite loops - usually caused by floating-point math round-off errors. Defaults are 1,000,000.

Changelog

This project adheres to Semantic Versioning.

The full changelog is available at CHANGELOG.md.

Authors

• Mike Fogel
• Alexander Milevski
• Vladimir Ovsyannikov

Sponsors

• Alantgeo
• 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)