polyclip-ts

What is polyclip-ts?

The polyclip-ts package is a TypeScript library for performing polygon clipping operations. It allows you to perform boolean operations on polygons such as union, intersection, difference, and XOR. This is useful in computational geometry, computer graphics, and GIS applications.

What are polyclip-ts's main functionalities?

Union of Polygons

This feature allows you to compute the union of two or more polygons. The code sample demonstrates how to use the `union` function to combine two overlapping squares into a single polygon.

const { union } = require('polyclip-ts');
const polygon1 = [[0, 0], [2, 0], [2, 2], [0, 2]];
const polygon2 = [[1, 1], [3, 1], [3, 3], [1, 3]];
const result = union([polygon1, polygon2]);
console.log(result);

Intersection of Polygons

This feature allows you to find the intersection area of two polygons. The code sample shows how to use the `intersection` function to find the overlapping area of two squares.

const { intersection } = require('polyclip-ts');
const polygon1 = [[0, 0], [2, 0], [2, 2], [0, 2]];
const polygon2 = [[1, 1], [3, 1], [3, 3], [1, 3]];
const result = intersection([polygon1, polygon2]);
console.log(result);

Difference of Polygons

This feature allows you to compute the difference between two polygons. The code sample demonstrates how to use the `difference` function to subtract one square from another.

const { difference } = require('polyclip-ts');
const polygon1 = [[0, 0], [2, 0], [2, 2], [0, 2]];
const polygon2 = [[1, 1], [3, 1], [3, 3], [1, 3]];
const result = difference(polygon1, polygon2);
console.log(result);

XOR of Polygons

This feature allows you to compute the exclusive OR (XOR) of two polygons. The code sample shows how to use the `xor` function to find the non-overlapping areas of two squares.

const { xor } = require('polyclip-ts');
const polygon1 = [[0, 0], [2, 0], [2, 2], [0, 2]];
const polygon2 = [[1, 1], [3, 1], [3, 3], [1, 3]];
const result = xor([polygon1, polygon2]);
console.log(result);

Other packages similar to polyclip-ts

clipper-lib

The clipper-lib package is a popular library for polygon clipping and offsetting. It is written in JavaScript and provides similar functionalities to polyclip-ts, such as union, intersection, difference, and XOR operations. Clipper-lib is known for its robustness and performance, especially in handling complex polygons.

polygon-clipping

The polygon-clipping package is another library for performing boolean operations on polygons. It is designed to handle complex and self-intersecting polygons efficiently. Compared to polyclip-ts, polygon-clipping offers similar functionalities but is optimized for performance and accuracy in edge cases.

README

polyclip-ts

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

Installing

If you use npm, npm install polyclip-ts. You can also download the latest release on GitHub. For vanilla HTML in modern browsers, import polyclip-ts from Skypack:

<script type="module">
import * as polyclip from "https://cdn.skypack.dev/polyclip-ts";

polyclip.intersection(…)
</script>

For legacy environments, you can load polyclip-ts’s UMD bundle from an npm-based CDN such as jsDelivr; a polyclip global is exported:

<script src="https://cdn.jsdelivr.net/npm/polyclip-ts/dist/polyclip-ts.umd.min.js"></script>
<script>
polyclip.intersection(…)
</script>

Quickstart

import * as polyclip from "polyclip-ts"

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       (geom, ...moreGeoms)
polyclip.intersection(geom, ...moreGeoms)
polyclip.xor         (geom, ...moreGeoms)

/* The moreGeoms will be subtracted from the geom */
polyclip.difference  (geom, ...moreGeoms)

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.

Authors

• Luiz F. M. Barboza
• Mike Fogel
• Alexander Milevski
• Vladimir Ovsyannikov

Based on

• A simple algorithm for Boolean operations on polygons by Francisco Martinez, Antonio Jesus Rueda, Francisco Ramon Feito (2009)