Expand description

Library for boolean operations on polygons.


use iron_shapes::prelude::*;
use iron_shapes_booleanop::BooleanOp;

// Create two polygons.
let p1 = Polygon::from(vec![(0., 0.), (2., 0.), (2., 1.), (0., 1.)]);
let p2 = p1.translate((1., 0.).into()); // Shift p1 by (1, 0).

// Compute the boolean intersection of the two squares.
let intersection = p1.intersection(&p2);
assert_eq!(intersection.polygons.len(), 1);
assert_eq!(intersection.polygons[0], Polygon::from(vec![(1., 0.), (2., 0.), (2., 1.), (1., 1.)]));

// Compute the boolean exclusive-or of the two squares.
// This results in two unconnected polygons. This demonstrates why boolean operations return always
// a `MultiPolygon`.
let intersection = p1.xor(&p2);
assert_eq!(intersection.polygons.len(), 2);


  • This work is originally loosely based: F. Martinez, A. Rueda, F. Feito, “A new algorithm for computing Boolean operations on polygons”, 2013, doi:10.1016/j.advengsoft.2013.04.004

The algorithm implemented here deviates from the reference paper. Most notably, the ordering of lines 6-9 in Listing 2 is done differently to properly handle vertical overlapping edges.


booleanop 🔒

Connect the resulting edges of the sweep line algorithm into polygons.

Extract the connectivity graph of polygons.

sweep_line 🔒

Implement the general sweep line algorithm used for algorithms like Boolean operations and connectivity extraction.


Implement the BooleanOp trait for MultiPolygon<...>.

Implement the BooleanOp trait for Polygon<...>.


Type of boolean operation.

Define the ‘inside’ of a polygon. Significant for self-overlapping polygons.


Trait for geometric primitives that support boolean operations.



Perform boolean operation.

Compute approximate intersection point of two edges in floating point coordinates.

Compute intersection of edges in integer coordinates. For edges that are parallel to the x or y axis the intersection can be computed exactly. For others it will be rounded.

Compute the intersection of edges with rational coordinates. In rational coordinates intersections can be computed exactly.

Perform boolean operation on a set of edges derived from polygons. The edges must form closed contours. Otherwise the output is undefined.