# The Voronoi Diagram

If we place some points on the surface and draw areas where each point is the nearest one — we would get the Voronoi diagram.

One of the first documented appliance of this diagram concept happens while the cholera disease was covering the europe in 1854 AC. There was an idea that the disease is living in the water, so people decided to split the city into areas based on the nearest wells and pumps distances. Final map was marked with the death statistics and it revealed the sources of infection spread.

Nowadays Voronoi Diagrams are applied to all areas where we have some point data. From web development where areas near active elements can be treated as click areas and make UI more user-friendly for people with reduced pointing abilities to 3D graphics, and procedural texture generation.

## Lets implement a naive solution

The simplest solution would be in placing a bunch of points and just calculating the smallest distance from each screen pixels to that points. After that I would color the whole area accordingly to the point number.

```
px.frameRate = 12;
const voronoiLayer = px.createLayer(1);
const pointsLayer = px.createLayer(2);
const pointCount = 9;
rect(0, 0, w, h, 0x000000);
let points = [];
let maxSpeed = w/6;
for(let i = 0; i < pointCount; i++){
let point = new Point(rand(w), rand(h));
point.dx = rand(maxSpeed) - maxSpeed/2;
point.dy = rand(maxSpeed) - maxSpeed/2;
point.color = color(
rand(0x66),
rand(0x99),
rand(0x88)
);
points.push(point);
}
update = (dt, t)=>{
pointsLayer.clear();
for(let i = 0; i < pointCount; i++){
let point = points[i];
point.x = (point.x + w + point.dx*dt) % w;
point.y = (point.y + h + point.dy*dt) % h;
pointsLayer.circle(point.x, point.y, 1.5, lighter(point.color,2));
pointsLayer.point(point.x, point.y, darker(point.color,2));
}
let x, y, i,
pixel = new Point(0,0);
for(x = 0; x < w; x++){
for(y = 0; y < h; y++){
pixel.set(x, y);
let nearest = points[0],
minDistance = nearest.distancePow2(pixel);
for(i = 1; i < pointCount; i++){
let point = points[i],
distance = point.distancePow2(pixel);
if( distance < minDistance ){
minDistance = distance;
nearest = point;
}
}
voronoiLayer.point(x, y, nearest.color);
}
}
}
```