Boolean operations for iron-shapes

This project implements boolean operations on polygons.

The code has been initially forked from https://github.com/21re/rust-geo-booleanop.

Large parts have been rewritten to fit better the needs of electronic design automation tools. This includes for instance support for integer coordinates. Also future work will include finding interactions and overlaps between polygons. This can be used for electrical connectivity checks and netlist extraction from chip layouts.

lib.rs:

Library for boolean operations on polygons.

Example

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);

References

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

• More systematic approach: PDF, archived