KD Tree

Split a rectangle in two, split the halves, and stop when a cell gets too small to bother with.

Split, recurse, stop

A k-d tree partitions space by repeatedly cutting it with axis-aligned planes. Here the space is a rectangle and the planes are lines:

if (verticalSplit)
{
    area1 = new[] { area[0], area[1], area[2], area[3] * r };
    area2 = new[] { area[0], area[1] + area[3] * r, area[2], area[3] * (1f - r) };
}

Parent removed, two children added, and each child considered for splitting again. The finished drawing is the leaves.

Step 01

One split.

Three coins, each doing something different

The piece’s character comes entirely from three balance parameters, and they are not interchangeable.

Balance1 — where the cut falls.

var b1 = 1f - Balance1;
var r = 0.5f - b1 / 2f + (float)rng.NextDouble() * b1 / 2f;

At Balance1 = 1 the cut is exactly at the midpoint every time and the drawing is a grid of powers of two. At 0 it is anywhere in the left half. The presets sit near 0.5, which gives a cut a little left of centre with modest variation — enough irregularity to be alive, not enough to produce slivers.

Balance2 — which axis is cut.

var verticalSplit = rng.NextDouble() > 0.5;
if (rng.NextDouble() < Balance2)
    verticalSplit = area[2] < area[3];

The axis starts as a fair coin, and then with probability Balance2 is overridden by the sensible choice: cut the longer side. At 0.85 that override applies most of the time, which is why the cells stay roughly square rather than degenerating into strips — and why the occasional cell that got the coin instead reads as a deliberate long rectangle.

Balance3 — whether to recurse.

if (rng.NextDouble() > MathF.Pow(Balance3, 3))
    Subdivide(…);

Note the cube. At Balance3 = 0.15 the stopping probability is 0.15³ ≈ 0.0034, so a cell that is big enough to split almost always does. The tree is bounded by MinSize, not by this coin — the coin exists to leave the occasional large cell undivided, and cubing it makes those genuinely rare.

Step 02

Two rounds.

Step 03

Four. The tree is already unbalanced: some branches have hit the minimum size and stopped while others are still splitting, and it is MinSize that decides which.

Step 04

Seven rounds.

Depth is not uniform

Step 05

The leaves. A cell is a leaf when it is smaller than MinSize + Spacing in either direction, or when the recursion coin came up against it. Because the split position is random, two sibling cells reach that threshold at different depths — so the finished partition has cells that are seven splits deep next to cells that are three.

That is the whole visual argument for a k-d tree over a grid: the cell sizes cluster but do not repeat, and the layout looks composed without anything having composed it.

The gap

Every cell is inset by Spacing / 2 on each side before it is drawn, so neighbouring cells separate by a full Spacing and the partition reads as tiles rather than as a web of shared lines. Cells that would collapse under the inset are skipped:

if (bx <= ax || by <= ay) continue;

which is what stops the smallest leaves from drawing as degenerate marks.

The renderings

Rendering	Shape	Density	Ink
Void Cyan	rectangles	medium	cyan on black
Void Lime	rectangles	fine	lime on near-black
Void Magenta	triangle pairs	medium	magenta on near-black
Void Amber	rectangles	sparse	amber on warm near-black
Void Violet	triangle pairs	fine	violet on deep near-black
Void Cyan — Museum	rectangles	medium	cyan on black, museum frame

Shape = 1 replaces each rectangle with a pair of triangles, chosen per cell — the same partition read as a different set of tiles.

The museum rendering presents the lead preset in a full museum frame — wall, mat, and frame — as a gallery piece rather than a direct sample.

Determinism

One Random is created per draw, seeded from the preset, and consumed in the recursion’s own depth-first order: split position, axis coin, axis override, then two recursion coins. The generator is System.Random, which the project’s determinism policy flags as not guaranteed stable across .NET versions.