buildQuadTree

Builds an adaptive quadtree over area for shapeFunction, down to maxDepth, collapsing every subtree that turns out to be fully inside or fully outside the shape into a single QuadTree.Full/QuadTree.Empty node.

The referenced article builds a full, uniform tree first and only collapses it in a second pass, relying on Haskell's laziness to fuse the two at runtime so the full tree is never actually resident in memory. This does that fusion directly and eagerly: each subtree is collapsed as soon as its four children are known, so a uniform region is discarded down to a single node right away instead of momentarily existing as up to 4^maxDepth separate leaf nodes.

Note that this still evaluates shapeFunction at every leaf's corners everywhere in area: there is no sound way to tell a coarse cell is uniform from just its own four corners (a shape can hide entirely inside a cell without ever reaching a corner), so full resolution still has to be sampled once before anything can collapse back up. What's avoided is only ever materializing that full-resolution tree as a whole in memory.

shapeFunction is evaluated through clampToBorder, so a shape extending past area still collapses to a tree whose boundary-straddling leaves close off along the edge of area -- see findContoursAdaptive.