Random Shape generator

Hey, I want to write a program that randomly draws dots on the window and then connects them. The special thing about it is: the lines are not allowed to cross each other.

What the result should look like:

What the result looks like:

You have to press the Spacebar to connect the dots.

Here is the code:

ArrayList<Dot> dots;
ArrayList<Dot> connections;
Dot start;
Dot current;
void setup() {
  size(600, 600);

  dots = new ArrayList<Dot>();
  connections = new ArrayList<Dot>();

  spawnDots();
  //thread("spawnDots");
}
void spawnDots() {
  for (int i = 0; i < 10; i++) {
    Dot d = new Dot(random(width), random(height));
    d.calcDistToCenter();
    dots.add(d);
    //delay(250);
  }
  start = dots.get(0);
  current = start;
  connections.add(start);
}
void draw() {
  background(0);
  for (int i = 0; i < dots.size(); i++) {
    Dot d = dots.get(i);
    d.show();
  }
  noFill();
  strokeWeight(2);
  stroke(255, 127);
  beginShape();
  for (Dot d : connections) {
    vertex(d.pos.x, d.pos.y);
  }
  endShape();
}
void keyPressed() {
  if (key == ' ') {
    calcNextDot();
  }
}
void calcNextDot() {
  int winnerIndex = 0;
  float winnerDist = 9999999;
  for (int i = 0; i < dots.size(); i++) {
    Dot d = dots.get(i);
    d.calcDistTo(current.pos);
    float f = d.distToCenter + d.distToCurrent;
    if (f < winnerDist && connections.contains(d) == false) {
      winnerDist = f;
      winnerIndex = i;
    }
  }
  connections.add(current);

  current = dots.get(winnerIndex);
}
class Dot {
  PVector pos;
  boolean selected = false;
  float size = 5;
  float distToCenter = 0;
  float distToCurrent = 0;
  Dot(float x, float y) {
    pos = new PVector(x, y);
  }
  void show() {
    stroke(255);
    if (start == this) {
      stroke(255, 9, 0);
    }
    if (current == this) {
      stroke(0, 255, 255);
    }
    strokeWeight(size);
    point(pos.x, pos.y);
  }
  void calcDistToCenter() {
    distToCenter = dist(pos.x, pos.y, width/2, height/2);
    //println(distToCenter);
  }
  void calcDistTo(PVector p) {
    distToCurrent = PVector.dist(pos, p);
  }
}

Edit: Sorry I forgot the “Dot” class now its there :slight_smile:

Hello Flolo,

Before going further, I just want to point out that there is not one single solution for your problem. For example on your first picture, you could also have the following red path:
image

My first thought was to use a convex hull algorithm but it will only gives you an outer shell and won’t go through all the points if you want concave shapes.

Maybe it would be a nice starting point though. Once you have the outer shell would could maybe compute distance from the remaining points to each side of your shell. You find the closest edge, delete it and create 2 new edges with the point. Not so sure it will solve the crossing issue…

The other thing I was thinking about would be to use an algorithm used to solve the travelling salesman problem and in particular the ant colony optimization. It is not exactly the same problem but I think it could be twicked to fit your needs.

Or, of course, you can brut force it if you don’t have too many points. Or use one of the previous method to get to a close result and then brut force the remaining part.

3 Likes

good suggestions here!

You can also simulate the next line and check with Collision Detection if we cross an existing line (store all old lines in an ArrayList of class Line (you have to write))

When we have an (unwanted) collision don’t draw the line and try again with a new variable

in theory to close the figure you need to reach angle 360 degrees

the last line can be from the current position to the 0th function

This means the random angle can be within a certain changing range to make sure the figure is developing clock-wise

Warm regards,

Chrisir

1 Like

Hi,

@jb4x said :

A new video about that topic just came out on the Coding Adventure YouTube channel which is amazing :slight_smile:

Go check it out, it’s really worth it!

2 Likes

Haha, I was just watching it few hours ago! Amazing results!

2 Likes

Hey, I watched this video by Daniel Shiffman and copied the code and changed it a bit. Now I only have one problem I want to connect the start and the end node to create a “real” shape. Anyone have an idea?

Here is my code:

PVector[] cities;
int totalCities = 40;

void setup() {
  frameRate(30);
  fullScreen();
  //size(600, 600);
  cities = new PVector[totalCities];
  for (int i = 1; i < totalCities-1; i++) {
    PVector v = new PVector(random(width), random(height));
    cities[i] = v;
  }
  cities[0] = new PVector(10, 10);
  cities[totalCities-1] = new PVector(width-10, height-10);
  //cities[cities.length-1] = cities[0].copy();

  //arrayCopy(cities, bestEver);
}

void draw() {
  background(0);
  fill(255);
  for (int i = 0; i < cities.length; i++) {
    ellipse(cities[i].x, cities[i].y, 8, 8);
  }

  stroke(255);
  strokeWeight(1);
  noFill();
  beginShape();
  for (int i = 0; i < cities.length; i++) {
    vertex(cities[i].x, cities[i].y);
  }
  endShape();

  //stroke(255, 0, 255);
  //strokeWeight(4);
  //noFill();
  //beginShape();
  //for (int i = 0; i < cities.length; i++) {
  //  vertex(bestEver[i].x, bestEver[i].y);
  //}
  //endShape();





  for (int i = 0; i < cities.length-1; i++) {
    PVector a = cities[i];
    PVector b = cities[i+1];
    for (int j = i + 2; j < cities.length-1; j++) {
      PVector a2 = cities[j];
      PVector b2 = cities[j+1];
      if (lineLineCollision(a.x, a.y, b.x, b.y, a2.x, a2.y, b2.x, b2.y) == true) {
        swap(cities, i, j);
      }
    }
  }
}
//void mousePressed() {
//  int indexI = floor(random(cities.length));
//  int indexJ = floor(random(cities.length));
//  swap(cities, indexI, indexJ);
//}
void keyPressed() {
  setup();
}
void swap(PVector[] a, int i, int j) {
  PVector temp = a[i];
  a[i] = a[j];
  a[j] = temp;
}
boolean lineLineCollision(float x1, float y1, float x2, float y2, float x3, float y3, float x4, float y4) {

  // calculate the distance to intersection point
  float uA = ((x4-x3)*(y1-y3) - (y4-y3)*(x1-x3)) / ((y4-y3)*(x2-x1) - (x4-x3)*(y2-y1));
  float uB = ((x2-x1)*(y1-y3) - (y2-y1)*(x1-x3)) / ((y4-y3)*(x2-x1) - (x4-x3)*(y2-y1));

  // if uA and uB are between 0-1, lines are colliding
  if (uA >= 0 && uA <= 1 && uB >= 0 && uB <= 1) {

    // optionally, draw a circle where the lines meet
    //float intersectionX = x1 + (uA * (x2-x1));
    //float intersectionY = y1 + (uA * (y2-y1));
    //fill(255, 0, 0);
    //noStroke();
    //ellipse(intersectionX, intersectionY, 20, 20);

    return true;
  }
  return false;
}

I think you’ll have problems here unless you opt for a proper concave hull algorithm.

The problem with line flipping is that there’s no notion of a closed hull – rather, it just computes a line that passes through all vertices. You don’t know the first and last vertices to close until the line flipping terminates, at which point you’ll have to test a line from the first to last closed vertex, and this will probably fail.

Note that the way to generate a random convex shape is much simpler.

2 Likes

Following @micycle’s suggestion, you can also use the Hemesh library for computing the concave hull of a polygon. See this post for examples.

Revisiting this, if you want a compute a closed path that passes through all points once (rather than a shape hull), then you’re looking to compute the Undirected Hamiltonian cycle of the points (when they’re modelled as a complete graph).

It’s a rather fundamental (NP-complete) graph/combinatorial problem and has fair bit of research interest, with implemented solutions out there.

1 Like

Below an implementation of @jb4x and @micycle’s idea in Processing Python mode. I’m using the HeldKarpTSP class from the JGraphT library for the calculation of the Traveling Salesman Problem (which is an extension of the Hamiltonian circuit problem mentioned above).

from org.jgrapht.graph import SimpleWeightedGraph, DefaultWeightedEdge
from org.jgrapht.alg.tour import HeldKarpTSP

W, H, M, N = 1000, 700, 100, 18

def setup():
    background('#FFFFFF')
    size(W, H)

    # List of random points
    points = [PVector(random(M, W-M), random(M, H-M)) for p in xrange(N)]
    
    # Create Complete Graph
    graph = SimpleWeightedGraph(DefaultWeightedEdge)
    
    for i1, p1 in enumerate(points):
        if not i1: graph.addVertex(i1)
        for i2, p2 in enumerate(points[i1+1:], i1+1):
            if not i1: graph.addVertex(i2)
            edge = DefaultWeightedEdge()
            graph.addEdge(i1, i2, edge)
            graph.setEdgeWeight(edge, p1.dist(p2))
      
    # Path indices (tour)                 
    t = HeldKarpTSP().getTour(graph).getVertexList()

    # Draw path
    for i1, i2 in zip(t, t[1:]):
        p1 = points[i1]
        p2 = points[i2]
        line(p1.x, p1.y, p2.x, p2.y)

Edit: Obviously it works on a Delaunay Graph as well:

Delaunay Graph version
from org.jgrapht.graph import SimpleWeightedGraph, DefaultWeightedEdge
from org.jgrapht.alg.tour import HeldKarpTSP
add_library('hemesh')

W, H, M, N = 1000, 700, 100, 18

def setup():
    background('#FFFFFF')
    size(W, H)
    
    # List of random points
    points = [WB_Point(random(M, W-M), random(M, H-M)) for p in xrange(N)]
    
    # Compute Delaunay triangulation 
    triangulation = WB_Triangulate.triangulate2D(points)
    edges = iter(triangulation.getEdges())

    # Create Delaunay Graph
    graph = SimpleWeightedGraph(DefaultWeightedEdge)
    
    for i1, i2 in zip(edges, edges):
        graph.addVertex(i1)
        graph.addVertex(i2)
        p1 = points[i1]
        p2 = points[i2]
        edge = DefaultWeightedEdge()
        graph.addEdge(i1, i2, edge)
        graph.setEdgeWeight(edge, p1.getDistance(p2))

    # Path indices (tour)
    t = HeldKarpTSP().getTour(graph).getVertexList()
        
    # Draw path
    for i1, i2 in zip(t, t[1:]):
        p1 = points[i1]
        p2 = points[i2]
        line(p1.x, p1.y, p2.x, p2.y)
3 Likes

To add on @solub solution, an easier way to create those kind of shape is to take the barycenter of all your points, and then order them based on their angle compared to a line going through the barycenter:

Code
import java.util.Arrays; // Comparable interface

final int POINTNB = 40;  // Total number of points to use to creat the shape
Point[] points;          // Array to store all the points of the shape
PVector refPt;           // The barycenter

void setup() {
  size(800, 600);
  noStroke();
  background(20);
  
  points = new Point[POINTNB];
  refPt = new PVector(0, 0);
  
  // Create random points on canvas and compute barycenter
  for (int i = 0; i < POINTNB; i++) {
    points[i] = new Point(random(50, width - 50), random(50, height - 50));
    refPt.x += points[i].pos.x;
    refPt.y += points[i].pos.y;
  }
  refPt.div(POINTNB);
  
  // Compute angle between horizontal line going through the barycenter and the line going through the barycenter and the current point
  for (int i = 0; i < POINTNB; i++) {
    points[i].updateAngle(refPt);
  }
  
  // Sort by angle
  Arrays.sort(points);
  
  
  // Draw shape
  noFill();
  stroke(59, 135, 247);
  strokeWeight(2);
  beginShape();
  for (int i = 0; i < POINTNB; i++) {
    vertex(points[i].pos.x, points[i].pos.y);
  }
  endShape(CLOSE);
  
  
  // Draw points
  for (int i = 0; i < POINTNB; i++) {
    points[i].draw();
  }
  fill(230, 20, 20);
  noStroke();
  ellipse(refPt.x, refPt.y, 10, 10);
}


// Class to hold a point
class Point implements Comparable<Point> {
  PVector pos = new PVector();  // x, y coordinate of point
  float a;                      // angle from ref point
  float dia = 5;                // Diameter of point
  
  Point(float x, float y) {
    pos.x = x;
    pos.y = y;
  }
  
  // pointRef is the point used as origin
  // Reference vector is (1, 0)
  // Compute the proper angle based on the barycenter
  void updateAngle(PVector pointRef) {
    a = atan2(pos.y - pointRef.y, pos.x - pointRef.x);
  }
  
  void draw() {
    fill(220);
    noStroke();
    ellipse(pos.x, pos.y, dia, dia);
  }
  
  // Used to sort array
  public int compareTo(Point other){
    if ((other.a > 0 && this.a > 0) || (other.a < 0 && this.a < 0)) {
      println(this.a, other.a, signum(this.a - other.a));
      return signum(this.a - other.a);
    }
    println(this.a, signum(this.a - other.a));
    return signum(-this.a);
  }
}


// Methods to compute sign of a float number
// Modified version of openJDK implementation
public static int signum(float nb) {
    return (int)rawCopySign(nb);
}

public static float rawCopySign(float sign) {
    return Float.intBitsToFloat((Float.floatToRawIntBits(sign)
            & (FloatConsts.SIGN_BIT_MASK))
            | (Float.floatToRawIntBits(1.f)
            & (FloatConsts.EXP_BIT_MASK
            | FloatConsts.SIGNIF_BIT_MASK)));
}

static class FloatConsts {
    public static final int SIGN_BIT_MASK = -2147483648;
    public static final int EXP_BIT_MASK = 2139095040;
    public static final int SIGNIF_BIT_MASK = 8388607;
}

Note that this will only produce “star” like shapes.

2 Likes

@jb4x I would argue this approach doesn’t really output the same kind of shape. As you rightly said after, it mostly creates star-like patterns. In that case, wouldn’t noising the vertices of a circle or randomly changing their radius be even simpler ?

Example:

Random Radius
W, H = 800, 800
num = 20
phi = TAU / float(num)

def setup():
    background('#FFFFFF')
    strokeWeight(4)
    size(W, H)
    
    # Create vertices of a random polygon
    verts = []
    for i in xrange(num):
        r = random(W*.2, W*.35)
        x = cos(i*phi) * r + W/2
        y = sin(i*phi) * r + H/2
        verts.append(PVector(x, y))
        
    # Create a polygon from a list of vertices
    polygon = createPolygon(verts) 
    
    # Draw Polygon
    shape(polygon)


def createPolygon(verts):
    
    '''Create a PShape from a list of vertices'''
    
    poly = createShape()
    poly.beginShape()
    poly.stroke(20)
    poly.strokeWeight(3)
    for v in verts:
        poly.vertex(v.x, v.y)
    poly.endShape(CLOSE)
    
    return poly

I guess another workaround would be to output several of these shapes, slightly offset them randomly so as they would still overlap each other and compute the boolean union of the whole (using “Geomerative” union method for example). I think it would make quite a complex / intricate shape.

1 Like

It would definitely gives the same result as noising the vertices of a circle and the later would indeed be quite simpler.

I just assume that the problem was: given a set of points, find a shape using all of the vertices =)

3 Likes