Optimized KD Tree

A k-d partition, then repeated passes that merge whichever rectangles happen to line up.

Subdivide, then undo some of it

The first phase is an ordinary k-d subdivision: split a rectangle in two, recurse, stop when a cell is too small.

float r = 0.5f - b1 / 2f + (float)Rand() * b1 / 2f;
bool verticalSplit = Rand() > 0.5;
if (Rand() < Balance2) verticalSplit = area[2] < area[3];

At Balance1 = 1 the split is exactly at the midpoint every time, so this partition is much more regular than a freely-cut one — which is what makes the second phase possible.

Step 01

Half the raw partition.

Step 02

All of it. Because the cuts are at midpoints, a great many pairs of neighbouring rectangles share a full edge — the same length, exactly aligned — and those pairs can be replaced by a single rectangle without changing the region covered.

Merging

for (int i = 0; i < optimizations; i++)
{
    if (ShuffleBeforeOptimize != 0) Shuffle(rects);
    OptimizeRects(rects);
}

Each pass walks the rectangle list looking for exactly that: two rectangles that abut along a complete shared edge. Where it finds a pair it replaces them with their union.

Step 03

One pass. The cell count has dropped noticeably, and the surviving cells have a wider range of aspect ratios than the partition produced.

Step 04

Two passes. The second pass is not redundant, because a merge creates new opportunities: two cells that each merged with a neighbour may now themselves share a full edge, which they did not before.

Step 05

Three passes. The returns diminish quickly — each pass finds fewer pairs than the one before, and by the third the partition is close to stable.

Why shuffle

ShuffleBeforeOptimize reorders the list before each pass. That matters because merging is greedy: when a rectangle has two possible partners, the one it takes depends on which is encountered first, and that choice forecloses the other.

Shuffling makes each pass explore a different order and therefore reach a different local optimum. It is the difference between a deterministic layout and one that varies with the seed even though the partition underneath it does not.

A hand-rolled generator

This piece does not use Random. It uses an integer hash advanced by a counter:

private double Rand()
{
    int s = _rseed;
    _rseed++;
    int v = (s >> 1) ^ s;
    int r = (int)(1103515245L * v);
    r = (int)(1103515245L * (r ^ (r >> 3)));
    r = r ^ (r >> 16);
    return (double)r / 1103515245.0 % 1.0;
}

That is a counter-based generator carried over from the Turtletoy original, where it replaced a Math.random() that could not be seeded. Because it is a pure function of the counter, it produces the same sequence on every platform — which makes this piece more portable than the ones using System.Random, by accident rather than by design.

Six renderings

Rendering	Colour	Key parameters
Cyan Subdivide	cyan on black	All defaults
Lime Partition	lime on `#111111`	`MinSize` 1.0, `Balance2` 0.5
Pink Grid	pink on `#0a0a0a`	`MinSize` 2.0, `Spacing` 2.0
Amber Fracture	amber on `#080808`	`Balance1` 0.7, `Balance2` 0.4
Violet Streams	violet on `#0d0d0d`	`Optimizations` 6, `ShuffleBeforeOptimize` 1
Glacier	slate on `#050505`	`Balance3` 0.65

Gallery presentation

Gallery presents the same cyan subdivision on a wall, behind a mat, inside a frame — SkiaSharp.Extensions’ MuseumFrame wrapping the piece rather than the piece drawing its own surround. The generative parameters are identical to Cyan Subdivide — same seed, same algorithm — only the presentation changes. The artwork is contain-fitted into the opening and isolated from the dark gallery wall by an off-white mat and a framed, shadowed edge.

Determinism

The generator is a counter-based hash seeded from the preset and advanced once per call, in a fixed order. There is no System.Random anywhere, so the piece is stable across runtimes as well as across runs.

Origin

Ported from a Turtletoy sketch; the original JavaScript is kept beside the source as main.js, with its link in url.

Progression 05

Variant 07