• fullscreen
• emergent_voronoi.pde
• ```// Emergent Voronoi
// based on an algorithm presented by Coates
// Alasdair Turner 2010

PVector [] nodes;
PVector [] particles;
color [] colors;
PVector [][] field;

void setup()
{
size(400,400);
colorMode(HSB);
smooth();
nodes = new PVector [10];
colors = new color [4000];
particles = new PVector [4000];
field = new PVector [width][height];
reset();
frameRate(24);
}

void draw()
{
background(255);
noStroke();
fill(128);
for (int i = 0; i < nodes.length; i++) {
ellipse(nodes[i].x,nodes[i].y,20,20);
}
for (int i = 0; i < particles.length; i++) {
int x = round(particles[i].x);
int y = round(particles[i].y);
if (x > 0 && x < width && y > 0 && y < height) {
fill(colors[i]);
ellipse(particles[i].x,particles[i].y,4,4);
}
}
}

void mousePressed()
{
reset();
}

void reset()
{
background(0);
for (int i = 0; i < nodes.length; i++) {
nodes[i] = new PVector(random(0,width),random(0,height));
}
for (int i = 0; i < particles.length; i++) {
colors[i] = color(random(255),random(204),204);
particles[i] = new PVector(random(0,width),random(0,height));
}
// Although this is perhaps against the spirit of
// an "emergent" voronoi pattern, I precalculate a
// vector field to move the particles
// If I had a massively parallel computer, I would
// be stricter, and let each particle determine its
// own distance from the nearest node.  But I don't!
for (int x = 0; x < width; x++) {
for (int y = 0; y < height; y++) {
int nearest_node = -1;
float nearest_dist = 0.0f;
int nnearest_node = -1;
float nnearest_dist = 0.0f;
field[x][y] = new PVector();
for (int i = 0; i < nodes.length; i++) {
float d = dist(x,y,nodes[i].x,nodes[i].y);
if (nearest_node == -1 || d < nearest_dist) {
nnearest_node = nearest_node;
nnearest_dist = nearest_dist;
nearest_node = i;
nearest_dist = d;
}
else if (nnearest_node == -1 || d < nnearest_dist) {
nnearest_node = i;
nnearest_dist = d;
}
}
field[x][y] = new PVector(x-nodes[nearest_node].x,y-nodes[nearest_node].y);
field[x][y].mult(0.1*(nnearest_dist-nearest_dist)/(nnearest_dist+nearest_dist));
}
}
}

```

### tweaks (0)

This sketch is running as Java applet, exported from Processing.

## Emergent Voronoi diagram

16

This is an implementation of an emergent Voronoi diagram, following an algorithm presented in programming.architecture by Paul Coates. It adapts the algorithm slightly to give a good convergence. Coates simply says "move away from the nearest node", which is wonderfully elegant!

Click for another pattern.

Graham Seed
11 Feb 2010
That's really neat.

I've just looked up Coates book on Amazon and think I'll be placing an order!!

I'm going to try coding this up using a background grid for faster spatial hashing.
Alasdair Turner
12 Feb 2010
I look forward to that! As you can see, my particles don't interact with each other - they only react to the 10 fixed-position nodes - for the very reason that something like spatial hashing would be necessary for anything more complex.

However, there is an element similar to hashing, in that the particles pick up their movement from the underlying vector field, which has been precalculated over a grid. I am not sure this really adds too much efficiency, as once again, there is only the distance to 10 objects to check each time.
Graham Seed
12 Feb 2010
Hi

I coded up your emergent voronoi using a QuadTree; I think this is the best since it gives O(sqrt(n)) lookp for nearest neighbour; via import of a Java class:

//...
int screenWidth = 900;
int screenHeight = 900;

//...

and draw() changed to:

//...
fill(colors[i]);

// nearest node
particlePoint.set((float)px,(float)py);
float d = (float)particlePoint.distanceBetweenTwoPoints(nearestNode);
d *= 0.1;
Vector2D awayDirectionVector = particlePoint.subtract(nearestNode);
Point2D awayPoint = particlePoint.pointAlongVector(awayDirectionVector,d,0.001);
particles[i].set((float)awayPoint.getX(),(float)awayPoint.getY(),0.0f);

ellipse(particles[i].x,particles[i].y,4,4);
//...

It works ok on my laptop with 500 nodes and 50,000 particles.

I noticed a property of the emergent voronoi. As soon as it emerges it diverges. If you leave a run to continue the particles gradually work their way off the screen by following the direction of the perpendicular bisectors between neighbouring points.

I've been trying to think of a test to fix a point once it's acheived convergence; ie found a perpendicular bisector. The only test I can think of is to fix a point when it's approx. half way between its two nearest neghbours, which is the voronoi definition.

Since I just placed my order for Coates' book, I don't know if he suggests a stop criteria. Any thoughts?
Alasdair Turner
13 Feb 2010
I think interaction between particles themselves may be the key to stability: either through an attraction or a repulsion between them, "locking" them in place. This would probably need spatial hashing as you first suggested. Paul Coates is quite intellectual in his approach, so although the algorithm is sketched, his main interest is how to approach architecture via algorithms. He mentions Voronoi diagrams at the same time as bubble structures, where both types of particle repel each other.
You need to login/register to comment.