Boolean operations on polygons (union, intersection, difference, xor).
- Clips polygons for all boolean operations
- Removes unnecessary vertices
- Handles segments that are coincident (overlap perfectly, share vertices, one inside the other, etc)
- Uses formulas that take floating point irregularities into account (via configurable epsilon)
- Provides an API for constructing efficient sequences of operations
- TypeScript implementation
- Demo + Animation
- Companion Tutorial
- Based somewhat on the F. Martinez (2008) algorithm: Paper, Code
Other kind souls have ported this library:
- Java port by @the3deers
- Java port by @Menecats
- .NET port by @idormenco
- Flutter/Dart port by @mohammedX6
- Python port by @KaivnD
- Please make a ticket if you'd like to be added here :-)
npm install @velipso/polybool
Or, for the browser, look in the dist/
directory for a single file build.
import polybool from '@velipso/polybool';
polybool.intersect({
regions: [
[[50,50], [150,150], [190,50]],
[[130,50], [290,150], [290,50]]
],
inverted: false
}, {
regions: [
[[110,20], [110,110], [20,20]],
[[130,170], [130,20], [260,20], [260,170]]
],
inverted: false
});
===> {
regions: [
[[50,50], [110,50], [110,110]],
[[178,80], [130,50], [130,130], [150,150]],
[[178,80], [190,50], [260,50], [260,131.25]]
],
inverted: false
}
import polybool from '@velipso/polybool';
const poly = polybool.union(poly1, poly2);
const poly = polybool.intersect(poly1, poly2);
const poly = polybool.difference(poly1, poly2); // poly1 - poly2
const poly = polybool.differenceRev(poly1, poly2); // poly2 - poly1
const poly = polybool.xor(poly1, poly2);
Where poly1
, poly2
, and the return value are Polygon objects, in the format of:
// polygon format
{
regions: [ // list of regions
// each region is a list of points
[[50,50], [150,150], [190,50]],
[[130,50], [290,150], [290,50]]
],
inverted: false // is this polygon inverted?
}
const segments = polybool.segments(polygon);
const combined = polybool.combine(segments1, segments2);
const segments = polybool.selectUnion(combined);
const segments = polybool.selectIntersect(combined);
const segments = polybool.selectDifference(combined);
const segments = polybool.selectDifferenceRev(combined);
const segments = polybool.selectXor(combined);
const polygon = polybool.polygon(segments);
Depending on your needs, it might be more efficient to construct your own
sequence of operations using the lower-level API. Note that polybool.union
,
polybool.intersect
, etc, are just thin wrappers for convenience.
There are three types of objects you will encounter in the core API:
- Polygons (discussed above, this is a list of regions and an
inverted
flag) - Segments
- Combined Segments
The basic flow chart of the API is:
You start by converting Polygons to Segments using polybool.segments(poly)
.
You convert Segments to Combined Segments using polybool.combine(seg1, seg2)
.
You select the resulting Segments from the Combined Segments using one of the
selection operators polybool.selectUnion(combined)
,
polybool.selectIntersect(combined)
, etc. These selection functions return
Segments.
Once you're done, you convert the Segments back to Polygons using
polybool.polygon(segments)
.
Each transition is costly, so you want to navigate wisely. The selection transition is the least costly.
Suppose you wanted to union a list of polygons together. The naive way to do it would be:
// works but not efficient
let result = polygons[0];
for (let i = 1; i < polygons.length; i++)
result = polybool.union(result, polygons[i]);
return result;
Instead, it's more efficient to use the core API directly, like this:
// works AND efficient
let segments = polybool.segments(polygons[0]);
for (let i = 1; i < polygons.length; i++){
const seg2 = polybool.segments(polygons[i]);
const comb = polybool.combine(segments, seg2);
segments = polybool.selectUnion(comb);
}
return polybool.polygon(segments);
Suppose you want to calculate all operations on two polygons. The naive way to do it would be:
// works but not efficient
return {
union: polybool.union(poly1, poly2),
intersect: polybool.intersect(poly1, poly2),
difference: polybool.difference(poly1, poly2),
differenceRev: polybool.differenceRev(poly1, poly2),
xor: polybool.xor(poly1, poly2)
};
Instead, it's more efficient to use the core API directly, like this:
// works AND efficient
const seg1 = polybool.segments(poly1);
const seg2 = polybool.segments(poly2);
const comb = polybool.combine(seg1, seg2);
return {
union: polybool.polygon(polybool.selectUnion(comb)),
intersect: polybool.polygon(polybool.selectIntersect(comb)),
difference: polybool.polygon(polybool.selectDifference(comb)),
differenceRev: polybool.polygon(polybool.selectDifferenceRev(comb)),
xor: polybool.polygon(polybool.selectXor(comb))
};
As an added bonus, just going from Polygon to Segments and back performs simplification on the polygon.
Suppose you have garbage polygon data and just want to clean it up. The naive way to do it would be:
// union the polygon with nothing in order to clean up the data
// works but not efficient
const cleaned = polybool.union(polygon, { regions: [], inverted: false });
Instead, skip the combination and selection phase:
// works AND efficient
const cleaned = polybool.polygon(polybool.segments(polygon));
Due to the beauty of floating point reality, floating point calculations are not exactly perfect. This is a problem when trying to detect whether lines are on top of each other, or if vertices are exactly the same.
Normally you would expect this to work:
if (A === B)
/* A and B are equal */;
else
/* A and B are not equal */;
But for inexact floating point math, instead we use:
if (Math.abs(A - B) < epsilon)
/* A and B are equal */;
else
/* A and B are not equal */;
You can set the epsilon value using:
import { PolyBool, GeometryEpsilon } from '@velipso/polybool';
const polybool = new PolyBool(new GeometryEpsilon(newEpsilonValue));
The default epsilon value is 0.0000000001
.
If your polygons are really really large or really really tiny, then you will probably have to come up with your own epsilon value -- otherwise, the default should be fine.
If PolyBool
detects that your epsilon is too small or too large, it will throw
an error:
PolyBool: Zero-length segment detected; your epsilon is probably too small or too large