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.

// 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]); particles[i].add(field[x][y]); 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)); } } }

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

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.

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

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.

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

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;

QuadTree2D quadTree = new QuadTree2D(screenHeight,0,0,screenWidth);

//...

and draw() changed to:

//...

fill(colors[i]);

// nearest node

Point2D nearestNode = (Point2D)quadTree.get(px,py);

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?

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;

QuadTree2D quadTree = new QuadTree2D(screenHeight,0,0,screenWidth);

//...

and draw() changed to:

//...

fill(colors[i]);

// nearest node

Point2D nearestNode = (Point2D)quadTree.get(px,py);

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

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.