When you use the Pathfinder panel in Illustrator, the boolean tools in Figma, or the Shape Builder in design software, you are invoking algorithms that date back to computational geometry research in the 1970s and 80s. Boolean operations - union, intersection, difference, and XOR - combine shapes using the same logic as set operations in mathematics. They are fundamental tools for constructing complex geometry from simple primitives.
These operations transformed computer-aided design. Before boolean operations, creating complex shapes meant painstakingly drawing every outline by hand, calculating where curves should meet, and ensuring paths closed correctly. With booleans, designers could compose complexity from simplicity: draw two overlapping circles, subtract one from the other, and instantly create a crescent moon.
But the apparent simplicity hides significant algorithmic complexity. Finding where shapes intersect, determining which boundary segments to keep, handling edge cases and numerical precision - these challenges have occupied researchers for decades. Understanding how boolean operations work explains both their power and their occasional mysterious failures.
Set theory foundations
Boolean operations on shapes mirror operations on sets in mathematics. Think of each shape as a set of points - all the (x, y) coordinates that lie inside the shape. Set operations then define how to combine these point sets. Union (A ∪ B) includes all points inside A or B or both - effectively merging two shapes into one. Intersection (A ∩ B) includes only points inside both A and B - the overlapping region. Difference (A - B) includes points inside A but not inside B - cutting one shape out of another. XOR or symmetric difference (A ⊕ B) includes points inside exactly one shape but not both - combining while removing overlap.
Boolean Operations
Union: Combine both shapes into one
This set-theoretic framing provides clean mathematical definitions, but implementing these operations on arbitrary polygons and curves requires translating set membership tests into geometric algorithms. The boundary of the result shape consists of portions of the input boundaries - the challenge is determining which portions to keep.
The basic algorithm: finding boundaries
The fundamental insight behind boolean algorithms is that result boundaries come from input boundaries. If you perform a union of two overlapping circles, the result boundary consists of an arc from the first circle and an arc from the second circle, connected at intersection points. The algorithm must find these intersection points, then determine which input boundary segments to include.
Step 1: Find all intersection points between the two shapes. For straight line segments, this involves solving systems of linear equations. For Bézier curves, it requires numerical methods - typically recursive subdivision until segments are approximately linear.
Step 2: Split the input boundaries at intersection points, creating a graph of boundary segments. Each segment now connects two intersection points (or connects an intersection point to itself for non-intersecting portions).
Step 3: Label each segment based on its relationship to the other shape. A segment from shape A might be inside B, outside B, or coincident with B's boundary.
Step 4: Select segments based on the desired operation. For union, keep segments from A that are outside B and segments from B that are outside A. For intersection, keep segments that are inside the other shape. For difference A-B, keep segments from A that are outside B and segments from B that are inside A (traversed in reverse).
Step 5: Connect the selected segments into closed paths forming the result shape.
Finding intersections
The first step - computing where edges of the two shapes cross - is straightforward for straight line segments. Given segments from (x₁, y₁) to (x₂, y₂) and from (x₃, y₃) to (x₄, y₄), solve the system of linear equations to find the intersection point. Check that the solution lies within both segments (parameter t between 0 and 1 for both).
// Line segment intersection
function lineIntersection(
p1: Point, p2: Point, // First segment
p3: Point, p4: Point // Second segment
): Point | null {
const d = (p1.x - p2.x) * (p3.y - p4.y) -
(p1.y - p2.y) * (p3.x - p4.x)
// Parallel lines - no intersection
if (Math.abs(d) < EPSILON) return null
const t = ((p1.x - p3.x) * (p3.y - p4.y) -
(p1.y - p3.y) * (p3.x - p4.x)) / d
const u = -((p1.x - p2.x) * (p1.y - p3.y) -
(p1.y - p2.y) * (p1.x - p3.x)) / d
// Check if intersection lies within both segments
if (t < 0 || t > 1 || u < 0 || u > 1) return null
return {
x: p1.x + t * (p2.x - p1.x),
y: p1.y + t * (p2.y - p1.y)
}
}For Bézier curves, there is no closed-form solution in general. The standard approach is recursive subdivision: split each curve at its midpoint, check if the bounding boxes of the resulting subcurves overlap, and recurse on overlapping pairs. When subcurves are small enough to be approximately linear, apply line intersection. This is the approach used by most vector graphics libraries.
The Weiler-Atherton algorithm
Once intersections are found, we must determine which boundary segments to keep. The Weiler-Atherton algorithm (1977) handles this by creating a data structure that links the two polygon boundaries with intersection points inserted. Each intersection point connects to four edges: entering and leaving on both polygons.
To trace the result, start at an intersection point and walk along the boundary of one polygon. At the next intersection, switch to the other polygon (the direction of switch depends on the operation). Continue until returning to the starting point. This traces one contour of the result; repeat for any unvisited intersection points to find additional contours.
The algorithm elegantly handles complex cases: polygons with multiple separate intersections, polygons that create holes in each other, and non-convex polygons. Its main limitation is handling numerical edge cases where intersections occur at vertices or along coincident edges.
The Martinez-Rueda algorithm
A more modern approach, the Martinez-Rueda algorithm, uses a sweep line technique. Imagine a vertical line sweeping across the plane from left to right. The algorithm maintains a list of polygon edges that intersect the current sweep line, sorted by y-coordinate. As the line sweeps, it processes events: edge starts, edge ends, and intersections.
The sweep line approach is efficient - O((n+k) log n) where n is the number of edges and k is the number of intersections - and naturally handles many edge cases that trip up other algorithms. It also extends easily to operations on multiple polygons simultaneously, useful for complex boolean expressions.
Numerical robustness challenges
In theory, boolean operations are straightforward. In practice, floating-point arithmetic creates nightmares. Two edges that should intersect might miss by 0.000001 due to rounding. An intersection point that should lie exactly on a vertex might be computed slightly off. These tiny errors can cause catastrophic failures: missing intersection points, incorrect inside/outside labels, result paths that fail to close.
Robust implementations use various strategies: epsilon comparisons instead of exact equality, snap-to-grid for intersection points, topological consistency checks that detect and repair errors, and symbolic or exact arithmetic for critical computations. Some systems use integer arithmetic throughout, converting coordinates to fixed-point representations to avoid floating-point issues entirely.
Fill rules and winding numbers
A polygon can self-intersect, creating ambiguity about which regions are 'inside.' Consider a five-pointed star drawn with a single path that crosses itself multiple times. Is the central pentagon inside or outside? The answer depends on the fill rule.
The even-odd fill rule says a point is inside if a ray from that point crosses the boundary an odd number of times. The non-zero winding rule counts crossings with a sign based on direction: crossing from left to right adds 1, right to left subtracts 1. A point is inside if the total is non-zero. These rules give different results for self-intersecting paths.
Boolean operations must respect fill rules. A union of two shapes using even-odd fill differs from union using non-zero fill if the shapes have overlapping interiors with consistent winding. Correctly tracking winding numbers through boolean operations adds another layer of complexity to already complex algorithms.
Constructive solid geometry
Boolean operations extend naturally to 3D, where they are called Constructive Solid Geometry (CSG). A 3D model can be built by combining primitive shapes (spheres, cubes, cylinders) using union, intersection, and difference. Subtract a cylinder from a cube to create a hole. Intersect two cubes to create a complex corner piece.
CSG is intuitive for designing mechanical parts and architectural elements. It represents objects implicitly - as trees of boolean operations on primitives - rather than explicitly as boundary meshes. This representation is compact and parametric (changing a sphere's radius automatically updates all operations involving it) but must be converted to explicit geometry for rendering.
Practical applications
Boolean operations are everywhere in design and manufacturing. Logo design combines and cuts shapes to create distinctive marks. Font design uses them for counters (the holes in letters like 'o' and 'p') and composite characters. CAD systems use them for modeling complex mechanical parts. CNC machines use them to compute tool paths. Even collision detection in games uses boolean-like operations to determine if objects overlap.
Map applications use boolean operations to compute intersections of geographic regions, calculate areas of overlap, and merge adjacent territories. Medical imaging uses them to segment organs and tumors from 3D scans. Architecture software uses them to cut openings for doors and windows in walls.
Boolean operations transform how we construct shapes - instead of drawing complex outlines directly, we can combine simple shapes, cut holes, and build up complexity through logical operations. The mathematics is challenging, the implementations are intricate, but the result is intuitive tools that feel like playing with digital clay.