• 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]);
          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)); 
        } 
      } 
    } 
    
    

    code

    tweaks (0)

    about this sketch

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

    license

    advertisement

    Alasdair Turner

    Emergent Voronoi diagram

    Add to Faves Me Likey@! 17
    You must login/register to add this sketch to your favorites.

    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;

    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
    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.