polygon

import polygon from "polygon";
import math3d from "math3d";

let frame = [math3d.vec2(-0.5, -0.5), math3d.vec2(0.5, -0.5), math3d.vec2(0.5, 0.5), math3d.vec2(-0.5, 0.5)];
let tab = [math3d.vec2(0.4, -0.1), math3d.vec2(0.8, -0.1), math3d.vec2(0.8, 0.1), math3d.vec2(0.4, 0.1)];
let window = [math3d.vec2(-0.3, -0.3), math3d.vec2(0.3, -0.3), math3d.vec2(0.3, 0.3), math3d.vec2(-0.3, 0.3)];

let plate = polygon.unite(&polygon.shape(frame[..]), &polygon.shape(tab[..]));
let cut = polygon.subtract(&plate, &polygon.shape(window[..]));
let r = cut.get(0);                        // one region: an outline and one hole
let tris = polygon.triangulate(r);         // indices into r.points, three per triangle

polygon works with areas: outlines added together and taken away from each other, the result as regions with holes, and triangles that cover a region and leave its holes out. Use it to cut a part from a sheet (a frame with a window, a vent grille, a slot), to build a level’s floor from rooms, or to get a face’s triangles for the GPU. geom has the functions for one simple polygon (area, containment, convex hull, ear clipping without holes); polygon is the step up to holes and booleans.

Points are math3d.Vec2 (f32, y up). Counter-clockwise means a positive area with y up; on a y-down screen it looks clockwise.

Regions and shapes

A region is one connected area: an outer ring and the holes in it. A shape is a set of regions.

pub struct Region {
    points: Vec_Vec2;          // every ring's points, ring after ring
    ends: collections.Vec_i64; // where each ring ends in points
}
pub struct Shape { regions: Vec_Region; }

Every region the module returns keeps these rules:

• Ring 0 is the outer ring, counter-clockwise. The other rings are holes, clockwise, each inside the outer ring and outside the others. So when you walk any ring point to point, the solid is on your left.
• A ring has at least 3 points, no point twice in a row and no point on the straight line through its neighbours. No ring crosses itself or another ring. Rings may touch at a point (a hole touching the outline, two holes touching), never along an edge.
• Each ring starts at its lowest point (the leftmost of those), so the same area always comes back as the same points, whichever order you gave things in.

The regions of a shape don’t overlap and share no edge. Two regions may touch at a point: two squares corner to corner stay two regions. Regions are in order of their outer ring’s first point (y, then x), holes the same within a region.

Region and Shape own their memory, and a copy is a deep copy.

Making shapes

shape accepts any outline. One that crosses itself is resolved by the nonzero rule: a point is inside when the outline winds around it at least once, either way. A bow tie becomes two triangles, a five-pointed star drawn in one stroke becomes the whole star (its middle wound twice counts once). Fewer than three points, points all on one line, zero area, or a coordinate that is NaN or infinite give an empty shape, never a trap.

Adding and taking away

(union is a keyword in tape, hence unite.)

// a plate minus ten slots
var grille = polygon.shape(plate_outline[..]);
var i: i64 = 0;
while (i < 10) {
    let x: f32 = 0.75 + (i as f32) * 1.125;
    let slot = [math3d.vec2(x, 1.0), math3d.vec2(x + 0.5, 1.0),
                math3d.vec2(x + 0.5, 3.0), math3d.vec2(x, 3.0)];
    grille = polygon.subtract(&grille, &polygon.shape(slot[..]));
    i = i + 1;
}

The awkward cases are the ones that work exactly: shapes sharing an edge or part of one (two squares side by side unite into one rectangle of four points), touching at a corner, the same shape twice (unite gives it back, subtract and xor give nothing), one inside the other, and shapes apart. A shape you built by hand, even one whose regions overlap, is read by the nonzero rule over all its rings.

Reading a region

A ring is a view into the region’s points: it is valid while the region is unchanged. ring(i) with i out of range stops the program with a trap.

The side walls of an extruded plate are each ring walked point to point:

var k: i64 = 0;
while (k < r.ring_count()) {
    let ring = r.ring(k);
    var i: i64 = 0;
    while (i < ring.len) {
        let a = ring[i];
        let b = ring[(i + 1) % ring.len];
        // a wall from a to b; the solid is on the left, so the outward
        // normal is (b.y - a.y, a.x - b.x), the same rule for every ring
        i = i + 1;
    }
    k = k + 1;
}

for (r in s.regions.iter()) goes through copies of the regions.

Triangles

triangulate(r) covers a region with triangles and leaves its holes out. It returns a collections.Vec_i64 of indices into r.points, three per triangle, each counter-clockwise and none of zero area. A region of n points and h holes gives at most n + 2h - 2 triangles.

let tris = polygon.triangulate(r);
var i: i64 = 0;
while (i < tris.len()) {
    let a = r.points.get(tris.get(i));
    let b = r.points.get(tris.get(i + 1));
    let c = r.points.get(tris.get(i + 2));
    i = i + 3;
}

The indices point into the region’s own points, so the top face of a plate is r.points and these indices, the bottom face the same points lower with each triangle’s order reversed; an index buffer for the GPU converts them to u32. Each hole is joined to the outline by a bridge, an edge used twice, so a bridge’s two points appear in more triangles than their neighbours; there are no new points. Ear clipping gives thin triangles along long outlines, which a flat face doesn’t mind.

A region you built yourself that breaks the rules above (a hole outside the outline, rings wound the wrong way, ends past the points) still triangulates without stopping the program, but what comes back is then not specified.

Exactness

A boolean puts both shapes on an integer grid of its own, about a billion steps across the largest coordinate, and decides everything there with exact integer arithmetic. So:

• Points equal as f32 are equal on the grid: a shared edge is found as shared, a touching corner as touching, never as a near miss.
• A point you gave comes back exactly when its coordinates are at least 1/64 of the largest one in the two shapes (a plate 1 wide keeps every point down to about 0.01 exactly); a smaller coordinate moves by at most a billionth of the largest.
• A new point where two edges cross is the nearest point whose coordinates are exact f32 values, so what you get back keeps every rule above when you read it as f32.

Far from the origin works the same: a 1 by 1 square at (10000, 10000) unites with its neighbour exactly.

Cost

Edges are paired by a sweep over their boxes, so typical outlines cost about n log n for n edges, and the worst case (every edge crossing every other) n². Working out which side of each edge is inside is n times the edges across from it, n² at worst. On a plate of a few hundred points (six round holes and two round ends), a boolean takes about 0.2 ms natively and triangulating it 0.4 ms; the VM is some thirty times slower. Thousands of points work, more slowly.

Not here

• Curves. Outlines are points: flatten a circle or a letter first (curve, font).
• Growing or shrinking a shape (offsetting, rounded corners) and quality meshes (constrained Delaunay) are not in the standard library yet.

Last modified: 2026-11-02 13:48:44 UTC