Dividing the Sky: How Quadtrees Organize Aerial Photos

Your foam-wing RC plane just landed after a perfect grid pattern flight, SD card bursting with 847 photos of a farmer’s field. Each image overlaps its neighbours by 70%, and now you face the computational puzzle: how do you quickly find which photos contain a specific GPS coordinate when stitching your orthomosaic?

This is where quadtrees shine—a recursive spatial index that divides 2D space into ever-smaller quadrants. Born in the 1970s for computer graphics, quadtrees became the secret weapon of GIS software by the 1980s.

data class Point(val x: Double, val y: Double)
data class Rectangle(val x: Double, val y: Double, val width: Double, val height: Double) {
    fun contains(point: Point) = point.x in x..(x + width) && point.y in y..(y + height)
}
data class Photo(val id: String, val center: Point)

class QuadTree(val bounds: Rectangle) {
    private val children = mutableListOf<QuadTree>()
    private val photos = mutableListOf<Photo>()
    
    fun insert(photo: Photo) {
        if (photos.size < 4 && children.isEmpty()) {
            photos.add(photo)
        } else {
            if (children.isEmpty()) subdivide()
            children.find { it.bounds.contains(photo.center) }?.insert(photo)
        }
    }

    private fun subdivide() {
        val halfWidth = bounds.width / 2
        val halfHeight = bounds.height / 2
        children += QuadTree(Rectangle(bounds.x, bounds.y, halfWidth, halfHeight))
        children += QuadTree(Rectangle(bounds.x + halfWidth, bounds.y, halfWidth, halfHeight))
        children += QuadTree(Rectangle(bounds.x, bounds.y + halfHeight, halfWidth, halfHeight))
        children += QuadTree(Rectangle(bounds.x + halfWidth, bounds.y + halfHeight, halfWidth, halfHeight))
    }
}

Kotlin’s object-oriented approach makes quadtrees intuitive—each node knows its boundaries and can recursively subdivide when overcrowded.

Forth takes a radically different path, treating space as a stack of coordinates:

variable bounds
variable count
create photos 4 cells allot

: within? ( x y bounds -- flag ) drop 2drop true ;
: subdivide ( -- ) ;

: quad-insert ( x y photo-id -- )
    >r 2dup bounds @ within? if
        count @ 4 < if
            r> photos count @ cells + !
            1 count +!
            2drop
        else r> drop subdivide recurse then
    else r> drop 2drop then ;

Forth’s stack-based nature mirrors how quadtrees actually work—you push coordinates down through levels until finding the right leaf node. Where Kotlin hides the recursive descent behind method calls, Forth exposes the coordinate manipulation directly.

When processing your orthomosaic, instead of checking all 847 photos for overlap with each map tile, the quadtree narrows your search to perhaps 6 relevant images. The difference between a 30-second query and a 4-hour nightmare? That’s the magic of recursively halving your search space—a trick as elegant today as it was revolutionary forty years ago.