Crate iron_shapes_booleanop

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

Modules

• booleanop 🔒
• connect_edges 🔒
  Connect the resulting edges of the sweep line algorithm into polygons.
• connectivity_extraction
  Extract the connectivity graph of polygons.
• init_events 🔒
• sweep_line 🔒
  Implement the general sweep line algorithm used for algorithms like Boolean operations and connectivity extraction.

Macros

• impl_booleanop_multipolygon 🔒
  Implement the BooleanOp trait for MultiPolygon<...>.
• impl_booleanop_polygon 🔒
  Implement the BooleanOp trait for Polygon<...>.

Enums

• Operation
  Type of boolean operation.
• PolygonSemantics
  Define the ‘inside’ of a polygon. Significant for self-overlapping polygons.

Traits

• BooleanOp
  Trait for geometric primitives that support boolean operations.

Functions

• edge_intersection_float
  Compute approximate intersection point of two edges in floating point coordinates.
• edge_intersection_integer
  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.
• edge_intersection_rational
  Compute the intersection of edges with rational coordinates. In rational coordinates intersections can be computed exactly.
• edges_boolean_op
  Perform boolean operation on a set of edges derived from polygons. The edges must form closed contours. Otherwise the output is undefined.