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.