Creating voronoi patterns

Hi again everyone, I’m trying to code a program to generate voronoi diagrams,
however I’m having issues generating the function that draws arcs in between each line.

Voronoi generation is supposed to produce this type of effect

Voronoi_growth_euclidean

at the moment I’m establishing the intersection of the points as the radius grows by looping through the global array and just checking the point distance and radius. This works so far and I can find the angle of intersection by taking the normal, thats fine too.

However when I try to draw an arc either from point b to point a, or point a to point b using calculated angles I get errors such as the arcs will draw seemingly randomly, and therefore provides nothing consistent.

I have checked my angles by passing them through a line function and I can draw lines from the center of the arc out to point a and point b consistently but the arcs are a mystery.

Apologies but openprocessing produces an override error when I copied the code.


ArrayList<Point> grid = new ArrayList<Point>();
ArrayList<Pair> Collisions = new ArrayList<Pair>();
Button reset;
int W = 1200, H = 660, total = 4, toggle = 0,toggle2 = 0, limit = 5, counter = 0;
float inc = 5;

void gen(){
  
  for(int i=0;i<total;i++){
    float x = random(W);
    float y = random(H);
    grid.add(new Point(x,y,i));
  }
}

class Button{
  
  float x,y,w,h;
  int toggle = 0;
  String label;
  boolean pressed = false;
  Button(float xx, float yy, float ww, float hh, String Label){
    
    x = xx;
    y = yy;
    w = ww;
    h = hh;
    label = Label;
  }
  void draw(){
    noStroke();
    fill(255);
    rect(x,y,w,h);
    fill(0);
    text(label,x+5,y+h-5);
  }
  
  boolean pos(){
    
    return x < mouseX && mouseY < x + w && y< mouseY && mouseY < y + h;
  }
  
  void click(){
    if(pos()){
      toggle ++;
    }
    
    if(toggle==2){
      toggle = 0;
    }
  }
};


void Reset(){
  if (reset.toggle==1){
    grid = new ArrayList<Point>();
    gen();
  }
}

void settings(){
  //size(W,H,FX2D);
  size(W,H);
}

void setup(){
  reset = new Button(1140,10,50,20, "reset");
  gen();
}

void draw(){
  
  
  frameRate(60);
  background(51);
  if(inc<0){
      fill(255);
    text("revese" ,1160,90);
    }
  Reset();
  reset.draw();
  //reset.click();
  text(reset.toggle,10,10);
  for(int i=0;i<grid.size();i++){
    
    grid.get(i).draw();
    grid.get(i).p_angle();
    if(toggle==1){
    grid.get(i).update();
    }
    grid.get(i).voronoi();
    
  }
  trim();
  for(int i=0;i<Collisions.size();i++){
   //Collisions.get(i).p_angle(); 
  }
  
};

void mousePressed(){
  if(mouseButton == LEFT && ! reset.pos()){
  toggle++;
  if(toggle == 2){
    toggle = 0;
  }}
  
  if(mouseButton == RIGHT && ! reset.pos()){
    
    inc = -inc;
  }
  if(mouseButton == LEFT && reset.pos()){
  reset.click();
  }
  
};

void mouseClicked(){
  //mouse();
  counter ++;
  
};

void mouseReleased(){
  reset.toggle = 0;
}

class Point{
  float x,y,theta,D = 0, r , _r =0;
  boolean update = true,draw = true;
  int id,ID;
  ArrayList<Float> Arc_height = new ArrayList<Float>();
  ArrayList<Point> collisions = new ArrayList<Point>();
  ArrayList<PVector> intersects = new ArrayList<PVector>();
  ArrayList<Float> lines = new ArrayList<Float>();
  
  //PVector [] lines = {};
  ArrayList<Float> angles = new ArrayList<Float>();
  ArrayList<Float> arcs = new ArrayList<Float>();
  color col ;
  Point(float xx, float yy,int Id){
    x = xx;
    y = yy;
    id = Id;
    r = D/2;
    ID = -1;
    col = color(random(0,255),random(0,255),random(0,255));
  }
  
  void init(){
    
  }
  
  void draw(){
    //if(id<1){
    strokeWeight(10);
    stroke(col);
    //noStroke();
    point(x,y);
    noFill();
    //fill(col);
    strokeWeight(2);
    //arc(x,y,r,r,0,360);
    //text(arcs.size(),x,y);
  //}
    
    for(int i=0;i<intersects.size();i++){
      PVector b = intersects.get(i);
      stroke(col);
      strokeWeight(4);
      //float xx = collisions.get(ID).intersects.get(ID).x;
      //float yy = collisions.get(ID).intersects.get(ID).y;
      
      //float xa = (xx + x)/2;
      //float ya = (yy + y)/2;
      point(b.x,b.y);
      
      //point(xa,ya);
      
    }
    
    //if(arcs.size()%2==0){
    //for(int i=arcs.size()-1;i>0;i-=2){
    //  //for(int i = arcs.size() - (ID+1)*2;i<arcs.size();i+=2){
    //    //for(int i=0;i<arcs.size();i+=2){
    //  float theta1 = arcs.get(i);
    //  float theta2 = arcs.get(i+1);
      
    //  strokeWeight(5);
    //  //stroke(51);
    //  stroke(col);
    //  noFill();
      //fill(51);
      //arc(x,y,r,r,theta1,theta2);
    //}
  //}
    
  };
  
  void update(){
    if(update){
    D += inc ;
    }
    r = D/2;
    
  };
  
  void voronoi(){
    fill(0);
    text(intersects.size(),x,y);
    text(ID,x,y+10);
    //text(lines.size(),x,y+20);
    text(Arc_height.size(),x,y+20);
    if(arcs.size()>=limit*2){
      //text("hello",10,10);
      //arcs.remove(1);
      //arcs.remove(0);
    }
    
    for(int i=0;i<grid.size();i++){
      
      Point a = grid.get(i);
      
      float d = dist(x,y,a.x,a.y);
      boolean b = collisions.contains(a);
      boolean c = a.collisions.contains(this);
        
      if(a.update&&d<=a.r/2+r/2&&a!=this){
        
        if(!b){
        ID++;
        collisions.add(a);
        
        Arc_height.add(r/2);
        intersects.add(new PVector(intersect(a,ID).x,intersect(a,ID).y));
        }}
        if(!a.update&&d<=r/2+a.r/2&&a!=this){
          
        if(!b){
        ID++;
        collisions.add(a);
        
        Arc_height.add(r/2);
        intersects.add(new PVector(intersect(a,ID).x,intersect(a,ID).y));
        
        }}}
        if(collisions.size()>limit){
          update = false;
        }
    };
    
  PVector intersect(Point a,int id){
    
    float c = Arc_height.get(id);
    PVector b = new PVector();
    
      float theta = atan2(a.y - y,a.x - x);
      b.x = x + (c) * cos(theta);
      b.y = y + (c) * sin(theta);
    
    return b;
  }
  
  void perimeter(){
    
  };
  
  void p_angle(){
    
    int t = collisions.size();
    
    if(ID>1){
     //t = collisions.size() - 1;
    }
      for(int i=0;i<t;i++){
        
        PVector k = new PVector(intersects.get(i).x,intersects.get(i).y);
        
        PVector a = intersects.get(i);
        
        float c = Arc_height.get(i);
        
        float theta1 = - atan2((a.x-x),a.y-y);
        
        float b = r/2-c;
        float l1 = sqrt(2*(b)*r/2 - (b)*(b));
        
        PVector p1 = new PVector(k.x + l1 * cos(theta1), k.y + l1 * sin(theta1));
        PVector p2 = new PVector(k.x  - l1 * cos(theta1),k.y - l1 * sin(theta1));
        
        float theta_a = atan2(p1.y - y,p1.x - x);
        float theta_b = atan2(p2.y - y,p2.x - x);
        
        float ta = 100;
        float tb = 340;
        
        float aa = theta_a*PI/180;
        float ba = theta_b*PI/180;
        stroke(col);
        strokeWeight(2);
        line(p1.x,p1.y,p2.x,p2.y);
        stroke(0);
        //strokeWeight(5);
        point(p1.x,p1.y);
        text("p1",p1.x+10,p1.y);
        stroke(255);
        point(p2.x,p2.y);
        //if(ID==0){
        noFill();
        strokeWeight(2);
        //arc(x,y,r,r,-theta_b,-theta_a);
        stroke(col);
        
        //arc(x,y,r,r,theta_a,theta_b);
        line(x,y,x+r/2 * cos(theta_a),y+r/2 * sin(theta_a));
        line(x,y,x+r/2 * cos(theta_b),y+r/2 * sin(theta_b));
        arc(x,y,r/2,r/2,theta_b,theta_a);
        //}
        if(ID>0){
          if(i<collisions.size()-1){
            
            Point n = collisions.get(i + 1);
            
            PVector kn = new PVector(intersects.get(i+1).x,intersects.get(i+1).y);
            float theta2 = - atan2((kn.x-x),kn.y-y);
            
            float c2 = Arc_height.get(i+1);
            
            float b2 = r/2-c2;
            float l2 = sqrt(2*(b2)*r/2 - (b2)*(b2));
            
            PVector p3 = new PVector(kn.x + l2 * cos(theta2), kn.y + l2 * sin(theta2));
            PVector p4 = new PVector(kn.x  - l2 * cos(theta2),kn.y - l2 * sin(theta2));
            
            float theta_c = atan2(p3.y - y,p3.x - x);
            float theta_d = atan2(p4.y - y,p4.x - x);
            
            noFill();
            stroke(col);
            //if(
            
            //arc(x,y,r,r,theta_d,theta_c);
          }
          else if(i>= collisions.size()-1){
            
            Point n = collisions.get(0);
            
            PVector kn = new PVector(intersects.get(0).x,intersects.get(0).y);
            
            float theta2 = - atan2((kn.x-x),kn.y-y);
            
            float c2 = Arc_height.get(0);
            
            float b2 = r/2-c2;
            float l2 = sqrt(2*(b2)*r/2 - (b2)*(b2));
            
            PVector p3 = new PVector(kn.x + l2 * cos(theta2), kn.y + l2 * sin(theta2));
            PVector p4 = new PVector(kn.x  - l2 * cos(theta2),kn.y - l2 * sin(theta2));
            
            float theta_c = atan2(p3.y - y,p3.x - x);
            float theta_d = atan2(p4.y - y,p4.x - x);
            
            noFill();
            stroke(col);
            //arc(x,y,r,r,theta_d,theta_c);
          }
        }
      }
  };
  
};
1 Like

The arc function is drawn in the p_angle() function, of the point class.

Hi @paulgoux,

Sorry I’m not replying to your specific question but just suggesting another approach that is quite common.

You could instead draw right cones of equal size in 3D and view them orthogonally from above. This would be both simpler to implement and faster to run as you wouldn’t have to compute distances or angles at each frame.

An example sketch (Python mode)

W, H = 1000, 600 #Dimensions of canvas
N = 10 #Number of cells
S = 60 #Sharpness of the cone (number of sides)
R = 0 #Radius of the cone
theta = radians(360) / S #Angle between vertices

def setup():
    size(1000, 600, P3D)
    ortho(-W>>1, W>>1, -H>>1, H>>1)
    noStroke()
    smooth(8)
    
    global cells, maxR

    cells = [Cell() for i in range(N)] #Array list containing cell objects
    maxR = dist(0, 0, W, H) #Maximum radius
    
    
    
def draw():
    background('#FFFFFF')
    global R
    
    for c in cells:
        c.render()
    
    R += frameCount *.01 #Increase radius of cones
    
    if R >= maxR:
        noLoop()



class Cell(object):
    def __init__(self):
        self.pos = PVector(random(width), random(height)) #random location
        self.col = (random(255), random(255), random(255)) #random color
        
    def render(self):
        # Translating coordinates
        pushMatrix()
        translate(self.pos.x, self.pos.y, 0)
        
        # Drawing a Cone (3D)
        fill(self.col[0], self.col[1], self.col[2])
        beginShape(TRIANGLE_STRIP)
        for i in xrange(S):
            vertex(0, 0, 0)
            vertex(R * cos(theta*i), R * sin(theta*i), -R)
            vertex(R * cos(theta*(i+1)), R * sin(theta*(i+1)), -R)
        endShape()
        
        # Drawing point at its center
        pushStyle()
        strokeWeight(8)
        stroke(0)
        point(0, 0, 0)
        popStyle()
        
        popMatrix()

4 Likes

does this provide a way to grab the vertices? Sorry I’m not familiar with python yet so I’m having difficulty understanding the code, I get the gist but would like to know if I can use it. Essentially I want to use the voronoi patterns to create a random maze, using the maze algorithm. Where I have to be able to show or hide one vertex depending on where the seeking tile is moving.

I think I’ve managed to port the most of it, the only thing I dont understand is the xrange in the for loop.

int W = 1000, H = 600;
int N = 10;
int S = 60;
int R = 0 ;
float theta = radians(360)/S;
int maxR;
ArrayList<Cell> cells = new ArrayList<Cell>();

void settings(){
  size(W,H,P3D);
};

void setup(){
    //size(1000, 600, P3D)
    ortho(-W>>1, W>>1, -H>>1, H>>1);
    noStroke();
    smooth(8);
}


void draw(){
    background(51);
    
    //for c in cells:
    for(int i=0;i<cells.size();i++){
        cells.get(i).render();
    }
    R += frameCount *.01;
    
    if (R >= maxR){
        noLoop();
    }
}


class Cell{
    
        PVector pos = new PVector(random(width), random(height));
        color col = color(random(255), random(255), random(255));
        
    void render(){
        // Translating coordinates
        pushMatrix();
        translate(pos.x, pos.y, 0);
        
        // Drawing a Cone (3D)
        fill(col);
        beginShape(TRIANGLE_STRIP);
        //for i in xrange(S):
        for(int i=0;i<xrange;i++){
            vertex(0, 0, 0);
            vertex(R * cos(theta*i), R * sin(theta*i), -R);
            vertex(R * cos(theta*(i+1)), R * sin(theta*(i+1)), -R);
        }
        endShape();
        
        // Drawing point at its center
        pushStyle();
        strokeWeight(8);
        stroke(0);
        point(0, 0, 0);
        popStyle();
        
        popMatrix();
    }
}

A Java transcription.

For some reason this sketch is much slower at rendering the cones than the Python version… I might be doing something wrong.

int W = 1000, H = 600; //Dimensions of canvas
int N = 10; //Number of cells
int S = 60; //Sharpness of the cone (number of sides)
float R = 0; //Radius of the cone
float maxR = dist(0, 0, W, H); //Maximum radius
float theta = radians(360) / S; //Angle between vertices

ArrayList<Cell> cells = new ArrayList<Cell>();

void setup(){
  size(1000, 600, P3D);
  ortho(-W>>1, W>>1, -H>>1, H>>1);
  noStroke();
  smooth(8);
        
  for (int i=0; i<N; i++) {
    cells.add(new Cell());
  }
  
}
    
    
void draw(){
    background(255);
    
    for (Cell c : cells) {
        c.render();
    }
    
    
    R += frameCount *.01; //Increase radius of cones
    
    if (R >= maxR){
        noLoop();
    }
}


class Cell {
  
  PVector pos = new PVector(random(W), random(H)); //random location
  PVector col = new PVector(random(255), random(255), random(255)); //random color

  void render(){
    //Translating coordinates
    pushMatrix();
    translate(pos.x, pos.y, 0);
        
    //Drawing a Cone (3D)
    fill(col.x, col.y, col.z);
    beginShape(TRIANGLE_STRIP);
    for (int i=0; i<S; i++) {
       vertex(0, 0, 0);
       vertex(R * cos(theta*i), R * sin(theta*i), -R);
       vertex(R * cos(theta*(i+1)), R * sin(theta*(i+1)), -R);
    endShape();
    }
        
    //Drawing point at its center
    pushStyle();
    strokeWeight(8);
    stroke(0);
    point(0, 0, 0);
    popStyle();
        
    popMatrix();
  }
}
1 Like

I think thats due to the renderer, P2D is also very much slower than the alternative FX2D.

Well now might be a good a time as any to start learning python I guess. I’ve already installed python and pycharm, how do I get started with processing?

Also I still don’t quite understand how the cones help create the voronoi diagram.

It seems smooth(8) is slowing the Java sketch, you might want to remove that line or lower its value.

If speed is an issue I wouldn’t recommend Python mode as it is usually slower than original Java code. If you still want to give it a try, just click on “Add Mode” on the top-right corner of the Processing IDE and select “Python”.

I honestly think the picture I posted is self-explanatory.

I get it now, it just flattens the perspective. I was thinking it was also retrieving the locations of intersections.

Thanks for all your help!

1 Like

If by vertices you mean the intersection points between Voronoi cells, the answer is no.

You could use third-party libraries to build diagrams and easily get access to these points. Here below 2 examples sketches using Hemesh and Toxiclibs.

Hemesh library (Python)

add_library('hemesh')

def setup():
    size(1000, 600, P3D) # P3D is mandatory
    background(255)
    strokeWeight(8)
    smooth(8)
    
    render = WB_Render(this)
    
    sites = [WB_Point(random(width), random(height)) for i in xrange(20)]
    diagram = WB_VoronoiCreator.getVoronoi2D(sites, .3).getCells()
    
    # Drawing sites (red points)
    pushStyle()
    strokeWeight(10)
    stroke(255, 40, 100)
    for s in sites:
        point(s.x, s.y, s.z)
    popStyle()
    
    

    for cell in diagram:
        
        # Drawing vertices (black points)
        for i in xrange(cell.getPolygon().getNumberOfPoints()):
            v = cell.getPolygon().getPoint(i) #coordinates of vertex
            point(v.x, v.y, v.z)
        
        
        # Drawing Voronoi cells (black polygons)
        pushStyle()
        strokeWeight(1)
        render.drawPolygonEdges(cell.getPolygon())
        popStyle()
    
    noLoop()

Toxiclibs library (Java)

import toxi.geom.*;
import toxi.geom.mesh2d.*;
import toxi.util.*;
import toxi.util.datatypes.*;
import toxi.processing.*;
ToxiclibsSupport gfx;

ArrayList<PVector> vertices = new ArrayList();

void setup(){
    size(1000, 600, P2D);
    background(255);
    strokeWeight(1);
    smooth(8);
    noFill();
    
    Voronoi voronoi = new Voronoi();
    gfx = new ToxiclibsSupport(this);
    
    for (int i=0; i<20; i++) {
      voronoi.addPoint(new Vec2D(random(width), random(height)));
    }

    //Display sites (red points)
    pushStyle();
    strokeWeight(7);
    stroke(255, 40, 100);
    for (Vec2D p : voronoi.getSites()) {
        point(p.x(), p.y());
    }
    popStyle();
    
    
    for (Polygon2D poly : voronoi.getRegions()) {
      gfx.polygon2D(poly);
      for (Vec2D v : poly.vertices) {
        vertices.add(new PVector(v.x(), v.y()));
      }
    }
    
    
    pushStyle();
    strokeWeight(8);
    for (PVector v : vertices) {
        point(v.x, v.y);
    }
    popStyle();
    
    noLoop();
}

See Hemesh example sketch in Java here and Toxiclibs Voronoi documentation for further details.

4 Likes

Another option is the “mesh” library and it’s Voronoi class.

http://leebyron.com/mesh/

3 Likes

Indeed. We could also mention “IGeo” and its IVoronoi2D class. The library got recently updated and is now Processing 3 compatible (yay!). Not sure it is operable with the P2D renderer though.

4 Likes

Thanks for all your replies guys. I have taken some time to code my own voronoi pattern generator. Here is what I have so far. Couldnt post the code on openProcessing as it failed with an override error, not sure why. Will post on github later for those who are interested, but I don’t know how to yet.

For now here is a rar file on my google drive for those interested.

For now I have made use of line intersection verification, and point line collision to achieve the desired effect, using only the standard 2d renderer. There are still a few issues to figure out though. First my line intersection check isn’t perfect, the code works fine but it doesnt produce a complete voronoid grid.

see bellow

the line intersection checks all other Point object checks there lines and checks if the line using its(x,y) and the other points (x,y), is clear, this only works at first but later fails as it doesn’t recognize open space, and just utilizes line of sight.

I shall continue to work on this. I will add shape filling later, atm I’m just using the line function.

1 Like

finally revisiting this, I think this was a bit beyond me at the time I started tackling this. Theres the fact that it uses P3D the fact that it uses ortho, and the fact that it uses math. My math was never my strong point and P3D is something which I didnt quite understand at the time. I still dont now but now I’m finally ready to make the jump.

So I’ve looked over the sketch and understand why it is slower

here is the updated code and this should perform as well as python

int W = 1000, H = 600; //Dimensions of canvas
int N = 1000; //Number of cells
int S = 60; //Sharpness of the cone (number of sides)
float R = 0; //Radius of the cone
float maxR = dist(0, 0, W, H); //Maximum radius
float theta = radians(360) / S; //Angle between vertices

ArrayList<Cell> cells = new ArrayList<Cell>();

void setup(){
  size(1000, 600, P3D);
  ortho(-W>>1, W>>1, -H>>1, H>>1);
  noStroke();
  //smooth(8);
        
  for (int i=0; i<N; i++) {
    cells.add(new Cell());
  }
  
};
    
    
void draw(){
    background(255);
    
    for (Cell c : cells) {
        c.render();
    }
    
    
    R += frameCount *.01; //Increase radius of cones
    
    if (R >= maxR){
        noLoop();
    }
}


class Cell {
  
  PVector pos = new PVector(random(W), random(H)); //random location
  PVector col = new PVector(random(255), random(255), random(255)); //random color

  void render(){
    //Translating coordinates
    pushMatrix();
    translate(pos.x, pos.y, 0);
        
    //Drawing a Cone (3D)
    fill(col.x, col.y, col.z);
    beginShape(TRIANGLE_STRIP);
    for (int i=0; i<S; i++) {
       vertex(0, 0, 0);
       vertex(R * cos(theta*i), R * sin(theta*i), -R);
       vertex(R * cos(theta*(i+1)), R * sin(theta*(i+1)), -R);
    
    }
    endShape();
        
    //Drawing point at its center
    pushStyle();
    strokeWeight(2);
    stroke(0);
    point(0, 0, 0);
    popStyle();
        
    popMatrix();
  }
}

culprit was endShape() which was being called inside the for loop.

For sure this is the best solution if one simply wants to create the pattern and nothing else. You could even add a sobel Shader to simulate the vertices.

2 Likes

with a graphics canvas and a sobel. There are double edges so cnny would be a better approach, however ortho does not work on canvas elements even if its set to p3d

.

int W = 1000, H = 600; //Dimensions of canvas
int N = 1000; //Number of cells
int S = 60; //Sharpness of the cone (number of sides)
float R = 0; //Radius of the cone
float maxR = dist(0, 0, W, H); //Maximum radius
float theta = radians(360) / S; //Angle between vertices

ArrayList<Cell> cells = new ArrayList<Cell>();

PShader sobel,sobel1;
PImage img;
PGraphics c;
void setup(){
  size(1000, 600, P3D);
  img = loadImage("b3.jpg");
  
  
  sobel = loadShader("edges.glsl");
  sobel1 = loadShader("sobel.glsl");
  c = createGraphics(width,height,P3D);
  c.noStroke();
  c.smooth(8);
  c.ortho(-W>>1, W>>1, -H>>1, H>>1);
        
  for (int i=0; i<N; i++) {
    cells.add(new Cell());
  }
  
};
    
    
void draw(){
    background(255);
    sobel1.set("u_mult",1.0);
    shader(sobel1);
    c.beginDraw();
    for (Cell c : cells) {
        c.render();
    }
    c.endDraw();
    
    
    R += frameCount *.1; //Increase radius of cones
    
    if (R >= maxR){
        noLoop();
    }
    image(c,0,0);
}


class Cell {
  
  PVector pos = new PVector(random(W), random(H)); //random location
  PVector col = new PVector(random(255), random(255), random(255)); //random color

  void render(){
    //Translating coordinates
    
    c.pushMatrix();
    c.translate(pos.x, pos.y, 0);
        
    //Drawing a Cone (3D)
    c.fill(col.x, col.y, col.z);
    c.noStroke();
    c.beginShape(TRIANGLE_STRIP);
    for (int i=0; i<S; i++) {
       c.vertex(0, 0, 0);
       c.vertex(R * cos(theta*i), R * sin(theta*i), -R);
       c.vertex(R * cos(theta*(i+1)), R * sin(theta*(i+1)), -R);
    
    }
    c.endShape();
        
    //Drawing point at its center
    c.pushStyle();
    c.strokeWeight(2);
    c.stroke(0);
    c.point(0, 0, 0);
    c.popStyle();
        
    c.popMatrix();
    
  }
};
1 Like