What is a Quadtree?

Wikipedia says:

Quadtrees are most often used to partition a two-dimensional space by recursively subdividing it into four quadrants or regions. The data associated with a leaf cell varies by application, but the leaf cell represents a “unit of interesting spatial information”.

These subdivisions reduce the amount of computation needed to query 2D data because instead of checking every single point, you can check only those within the same cell, or nearby cells. It’s useful for collision detection, image processing, or finding nearby landmarks on a map. Daniel Shiffman has an excellent series about quadtrees on The Coding Train.

How will they be used?

The design for this site was “heavily influenced” by Monica Dinculescu’s, though I’ve added a dark mode, mobile menu, collapsible code blocks, project filtering, and style customisations. I enjoy the Trunchet tiles Monica uses on her site but thought I could do something to make it more me.

Making Tiles

As I’m not going to be querying any of my data, I can get away with plotting random points on a grid. Using quadtress could be considered a bit of an overengineered solution then, but I think it’s still useful to explore a new algorithm. By changing the number of points and the capacity of each cell, I can generate infinite arrangements of cells and use the boundaries of those as tiles. The result is a structured grid with enough variation to make it interesting. I wanted to show some personality on this site so I started with a grid full of images related to my interests from places like Unsplash and Pexels. On the projects page I even experimented with using the current filter tags. The results ended up being too busy and took too long to load.

The images from Unsplash were already sized to fit each cell so it was hard to optimize them further, but fortunately every modern device comes preloaded with a standardised set of vector images - emoji! No matter the size they’re displayed at, they are quick to render and take up a small number of bytes. Yes, they look different between devices but for how they’re going to be used this really doesn’t matter. So that solved the issue with loading times, but what about the grid being too busy? Each cell has only a 20% chance of being filled by an emoji and I created functions for a number of shapes to fill in the rest. A small set of blocky shapes with a simple color palette produces a Bauhaus-esque aesthetic. The shapes are arc, circle, cross, grid, semicircle, stripes (straight or diagonal), and triangles (isosceles or right-angle).

By putting these inside a RenderShape class I could use the constructor to simplify the common parameters for every shape and reduce the overall size of the JavaScript file. I can add new shapes to the class without having to worry about how it’s called either, as this is handled at runtime:

class RenderShape(){
    constructor(ctx, originX, originY, width, count){
        //...
        //give each shape a side to stick to
        this.position = count % 4;
    }
    arc();
    circle();
    cross();
    grid();
    semicircle();
    stripes();
    triangles();
}

//return every property that is a function, but not the constructor
let shapes = Object.getOwnPropertyNames(Object.getPrototypeOf(renderShape)).filter(item => {
    return typeof renderShape[item] === 'function' && item != "constructor";
});
let index = Math.round(Math.random() * shapes.length) % shapes.length;
let shape = shapes[index];

Here you can change the capacity and point count to see the difference it makes:

That’s all I have for now! Try coming back near Halloween or Christmas to see what the tiles look like then 😉