Voronoi Tessellation

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

Voronoi Tessellation is fancifully defined as:

Let ${\textstyle X}$ be a metric space with distance function ${\textstyle d}$ . Let ${\textstyle K}$ be a set of indices and let ${\textstyle (P_{k})_{k\in K}}$ be a tuple (ordered collection) of nonempty subsets (the sites) in the space ${\textstyle X}$ . The Voronoi cell, or Voronoi region, ${\textstyle R_{k}}$ , associated with the site ${\textstyle P_{k}}$ is the set of all points in ${\textstyle X}$ whose distance to ${\textstyle P_{k}}$ is not greater than their distance to the other sites ${\textstyle P_{j}}$ , where ${\textstyle j}$ is any index different from ${\textstyle k}$ . In other words, if denotes the distance between the point ${\textstyle x}$ and the subset ${\textstyle A}$ , 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.

Voronoi Tessellation

Submit a Comment Cancel reply

Recent Posts