Master Canvas & SVG Boolean Operations: Winding Rules, Bentley-Ottmann, Martinez Algorithm

🙋🏻‍♀️ Editor's note: The author, a former Ant Group front‑end engineer, discusses Canvas/SVG Boolean operations in depth, including winding rules, segmentation, intersection, segment inside/outside annotation, extended curves, selection results, and forced even‑odd rules.

Preface

The structure of the Alipay LOGO is a familiar example: a rounded rectangle background with a "support" vector shape subtracted from it. This demonstrates how arbitrary vector shapes can be combined using union, subtraction, intersection, and difference—collectively known as polygon Boolean operations. While similar to bitmap masks, Boolean operations are more powerful and involve geometric concepts.

Winding Rules

Vector rendering requires defining the interior of a closed shape, typically using the winding number. Edges are ordered clockwise or counter‑clockwise. By casting a ray from any point and counting edge crossings (+1 for counter‑clockwise, –1 for clockwise), the sum determines the winding number, which can be positive, zero, or negative. Two common fill rules are non‑zero (non‑zero winding number = interior) and even‑odd (odd winding number = interior).

In Canvas/SVG the default is non‑zero, but it can be changed:

<code>ctx.fill('nonzero'); // default, can omit
ctx.fill('evenodd'); // even‑odd rule

// SVG
<path fill-rule="nonzero" />
<path fill-rule="evenodd" />
</code>

Bentley‑Ottmann

Bentley‑Ottmann is a sweep‑line algorithm that finds all intersections among line segments in O(n log n) time, far faster than the naïve O(n²) approach. It processes events at segment start points, end points, and intersection points, maintaining an active list of segments intersected by the sweep line.

Segmentation

The first step is to split any non‑x‑monotonic curves. By differentiating the curve and locating extrema, the curve is divided into pieces that are strictly increasing or decreasing in x, ensuring reliable segment annotation later.

Intersection

For each segment, compute its bounding box (bbox). The sweep line visits the left edge (segment start) and right edge (segment end) of each bbox. When the sweep line reaches a start, the segment is added to the active list; when it reaches an end, the segment is removed. Only segments whose bboxes overlap are tested for true intersection, and intersecting segments are split at the intersection point.

Segment Inside/Outside

Each edge of a polygon has two sides: one interior and one exterior. By annotating each side with solid (inside) or hollow (outside) circles, the algorithm can later decide which edges to keep for a given Boolean operation.

Segment Annotation

Three sweep passes are performed:

Scan only the red polygon to annotate its edges.

Scan only the blue polygon to annotate its edges.

Scan both polygons together to annotate each edge with the opposite polygon's information.

Key observations:

The bottommost edge in the active list always has the opposite side outside.

When two edges intersect, they swap vertical order.

For overlapping edges, the parity of the overlap count determines whether the interior/exterior status is the same or opposite.

Extended Curves

Curves are treated as many tiny straight segments; the same ordering rules apply based on y‑values at equal x. Proper x‑monotonic splitting is essential to preserve this equivalence.

Selection Result

After annotation, each edge has four circles (top/bottom for red and blue). Each circle can be solid (1) or hollow (0), yielding 16 possible states, encoded as a 4‑bit binary number. A lookup table determines which states are kept for each Boolean operation (INTERSECT, UNION, SUBTRACT, XOR, etc.).

<code>const INTERSECT = [
  0,0,0,1,
  0,0,0,1,
  0,0,0,1,
  1,1,1,0,
];
</code>

Edges marked for retention are linked into chains to form closed polygon regions.

Force Even‑Odd

The Martinez method assumes a forced even‑odd rule, ensuring that overlapping edges are handled consistently. Sketch appears to use a similar approach, supporting both even‑odd and non‑zero rules.

References

F. Martinez, "A new algorithm for computing Boolean operations on polygons", 2008.

BI Barbara, "The method of finding points of intersection of two cubic bezier curves using the sylvester matrix".

@velipso, "Polygon‑clipping‑pt2".