Since learning about Simplex Noise and how to use it I’ve started researching Voronoi Tessellation.

Voronoi Tessellation is fancifully defined as:

Let  be a metric space with distance function . Let be a set of indices and let  be a tuple (ordered collection) of nonempty subsets (the sites) in the space . The Voronoi cell, or Voronoi region, , associated with the site is the set of all points in  whose distance to  is not greater than their distance to the other sites , where  is any index different from . In other words, if  denotes the distance between the point  and the subset , then

So what’s this in English? Basically you have an area (this can be either 2D or 3D) and you have cells dispersed across it. Each and every position in the area needs to know which cell it is closest to.

Here’s a Voronoi Tessellation I made using Java using 1000 cells and a huge 6200² pixel canvas.

The java algorithm I used for Voronoi Tessellation is as follow:

int n = 0;
Random rand = new Random();
I = new BufferedImage(size, size, BufferedImage.TYPE_INT_RGB);
//Initalise pixelx, pixely, and colour arrays
px = new int[total_cells];
py = new int[total_cells];
color = new int[total_cells];
//Assign a random colour to each element in the colour array
//Not really part of the algorithm but we need it for visualisation
for (int i = 0; i < total_cells; i++) {
    px[i] = rand.nextInt(size);
    py[i] = rand.nextInt(size);
    color[i] = rand.nextInt(16777215);
}
//Nested for loop. Traverse every pixel one-by-one
for (int pixel_coord_x = 0; pixel_coord_x < size; pixel_coord_x++) {
    for (int pixel_coord_y = 0; pixel_coord_y < size; pixel_coord_y++) {
        n = 0;
        //Traverse every cell one-by-one
        for (int current_cell = 0; current_cell < total_cells; current_cell++) {
            //If the distance between the current cell and the traversed pixel from the for loop
            //is less than the value stored in n make n equal to the current cell.  
            //I.e. n becomes associated with the closest cell.
            if (    distance(px[current_cell], pixel_coord_x, py[current_cell], pixel_coord_y) 
                   < 
                    distance(px[n], pixel_coord_x, py[n], pixel_coord_y)) 
            {
                n = current_cell;
            }
        }
        //Do something with the data
        //In this case we set the pixel colour on a Buffered Image (varable bI) 
        bI.setRGB(pixel_coord_x, pixel_coord_y, color[n]);
    }
}

 

Good fun.