Let's dive into a visual math problem!

This animation uses Lloyd's algorithm to produce an interesting effect.

The result should be a stippled image such that the points:

• Represent a pixel of a source image
• Vary in size based on the brightness of the pixel
• Vary in colour based on the colour of the pixel
• 'Relax' toward a point, as explained below

The Concepts

Stippling

Stippling is the process of creating imagery from simple dots. You draw the dots closer to each other to create shades.

_{My portrait, created using a stippling technique}

Voronoi Diagram

Imagine you draw 20 random 'seed' points onto a blank canvas.

For each of these seed points, we draw a polygon around it, such that each pixel in the polygon is closer to the current seed point, than any other point.

This is a Voronoi diagram:

_{https://en.wikipedia.org/wiki/Voronoi_diagram}

Centroid

The centroid of a polygon is the central point of the polygon; or the average of all the points across the polygon.

A Weighted Centroid is where we apply higher weights to points in the polygon based on the brightness of the image at that point - we will use this later.

Lerp

Lerping (linear interpolation) is simply moving a point in a straight line towards another point.

The Algorithm

Okay, so how do we make this animation happen?

First, we load a source image and choose some random pixels above a brightness threshold. These pixels become the first set of seed points.

Then we run this algorithm 60 times per second:

1. Compute the Voronoi polygons using the seed points
2. For each pixel, find the centroid weight based on the brightness of the pixel
3. For each point:
   1. Compute the centroid based on the centroid weights for this point's Voronoi polygon
   2. Lerp the point towards the weighted centroid
   3. Draw the point with a size and colour based on the related pixel's brightness and colour, respectively
4. Rerun the algorithm, feeding in the updated points as the seed points

Here is the result: