# Random Shape generator

**URL:** <https://discourse.processing.org/t/random-shape-generator/28843>\
**Category:** Coding Questions\
**Created:** [March 25, 2021, 7:19pm UTC](https://discourse.processing.org/t/random-shape-generator/28843 "2021-03-25T19:19:53Z")\
**Posts on this page:** 13\
**Page:** 1

<div class="post-metadata">

**Author:** ![Flolo](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/flolo/32/13874_2.png) [@Flolo](https://discourse.processing.org/u/Flolo)\
**Post date:** [March 25, 2021, 7:19pm UTC](https://discourse.processing.org/t/random-shape-generator/28843/1 "2021-03-25T19:19:53Z")

</div>

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:**

 ![Right](https://canada1.discourse-cdn.com/flex036/uploads/processingfoundation1/original/2X/5/5bc8fde9a83409d46281ccd88ba0d5b115193dac.png)

**What the result looks like:**

 ![Wrong](https://canada1.discourse-cdn.com/flex036/uploads/processingfoundation1/original/2X/b/bfff3e37b54c7d0fb3349749a41932362d056cc1.png)

You have to press the Spacebar to connect the dots.

Here is the code:

```auto
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 🙂

---

<div class="post-metadata">

**Author:** ![jb4x](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/jb4x/32/789_2.png) [@jb4x](https://discourse.processing.org/u/jb4x)\
**Post date:** [March 25, 2021, 8:27pm UTC](https://discourse.processing.org/t/random-shape-generator/28843/2 "2021-03-25T20:27:36Z")

</div>

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](https://canada1.discourse-cdn.com/flex036/uploads/processingfoundation1/original/2X/c/c2cf9a278c206702b1db8ee249504e35b42a2d28.png)

My first thought was to use a [convex hull algorithm](https://en.wikipedia.org/wiki/Convex_hull_algorithms) 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](https://en.wikipedia.org/wiki/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.

---

<div class="post-metadata">

**Author:** ![Chrisir](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/chrisir/32/45_2.png) [@Chrisir](https://discourse.processing.org/u/Chrisir)\
**Post date:** [March 25, 2021, 8:38pm UTC](https://discourse.processing.org/t/random-shape-generator/28843/3 "2021-03-25T20:38:10Z")

</div>

good suggestions here!

You can also simulate the next line and check with [Collision Detection](http://jeffreythompson.org/collision-detection/line-line.php) 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

---

<div class="post-metadata">

**Author:** ![josephh](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/josephh/32/210_2.png) [@josephh](https://discourse.processing.org/u/josephh)\
**Post date:** [March 25, 2021, 8:58pm UTC](https://discourse.processing.org/t/random-shape-generator/28843/4 "2021-03-25T20:58:03Z")

</div>

Hi,

@jb4x said :

> [@jb4x](#):
>
> The other thing I was thinking about would be to use an algorithm used to solve the [travelling salesman problem](https://en.wikipedia.org/wiki/Travelling_salesman_problem) and in particular the ant colony optimization.

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

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

[![](https://img.youtube.com/vi/X-iSQQgOd1A/maxresdefault.jpg "Coding Adventure: Ant and Slime Simulations") ](https://www.youtube.com/watch?v=X-iSQQgOd1A)

---

<div class="post-metadata">

**Author:** ![jb4x](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/jb4x/32/789_2.png) [@jb4x](https://discourse.processing.org/u/jb4x)\
**Post date:** [March 25, 2021, 8:59pm UTC](https://discourse.processing.org/t/random-shape-generator/28843/5 "2021-03-25T20:59:14Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![Flolo](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/flolo/32/13874_2.png) [@Flolo](https://discourse.processing.org/u/Flolo)\
**Post date:** [April 7, 2021, 1:06pm UTC](https://discourse.processing.org/t/random-shape-generator/28843/6 "2021-04-07T13:06:45Z")

</div>

Hey, I watched this [video](https://youtu.be/BAejnwN4Ccw) by [Daniel Shiffman](https://thecodingtrain.com/) and copied the [code](https://github.com/CodingTrain/website/blob/main/CodingChallenges/CC_035.1_TSP/Processing/CC_035_1_TSP/CC_035_1_TSP.pde) 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:

```auto
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;
}

```

---

<div class="post-metadata">

**Author:** ![micycle](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/micycle/32/201_2.png) [@micycle](https://discourse.processing.org/u/micycle)\
**Post date:** [April 7, 2021, 1:47pm UTC](https://discourse.processing.org/t/random-shape-generator/28843/7 "2021-04-07T13:47:52Z")

</div>

I think you’ll have problems here unless you opt for a proper concave hull [algorithm](https://github.com/search?l=Java&q=concave+hull&type=Repositories).

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.

![](https://github.com/micycle1/PGS/raw/master/resources/morphology/concaveHull.gif)

Note that the way to generate a random **convex** shape is much [simpler](https://cglab.ca/~sander/misc/ConvexGeneration/convex.html).  
 ![](https://github.com/micycle1/PGS/raw/master/resources/pgs/randomPolygon.gif)

---

<div class="post-metadata">

**Author:** ![solub](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/solub/32/333_2.png) [@solub](https://discourse.processing.org/u/solub)\
**Post date:** [April 8, 2021, 10:19am UTC](https://discourse.processing.org/t/random-shape-generator/28843/8 "2021-04-08T10:19:15Z")

</div>

Following @micycle’s suggestion, you can also use the Hemesh library for computing the concave hull of a polygon. See [this post](https://discourse.processing.org/t/connecting-outermost-dots-with-a-single-line/16395/9) for examples.

---

<div class="post-metadata">

**Author:** ![micycle](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/micycle/32/201_2.png) [@micycle](https://discourse.processing.org/u/micycle)\
**Post date:** [April 14, 2021, 12:50pm UTC](https://discourse.processing.org/t/random-shape-generator/28843/9 "2021-04-14T12:50:17Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![solub](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/solub/32/333_2.png) [@solub](https://discourse.processing.org/u/solub)\
**Post date:** [April 14, 2021, 5:43pm UTC](https://discourse.processing.org/t/random-shape-generator/28843/10 "2021-04-14T17:43:32Z")

</div>

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

```auto
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)

```

 ![HPath](https://canada1.discourse-cdn.com/flex036/uploads/processingfoundation1/original/2X/6/6509b1f472ea5a227a10d0aea956f680f8cbd705.png)

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

 ![comp](https://canada1.discourse-cdn.com/flex036/uploads/processingfoundation1/original/2X/7/7cb8381ca07b65664d49d50987762542282a8d80.jpeg)

> **Delaunay Graph version**
>
> ```auto
> 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)
> 
> ```

---

<div class="post-metadata">

**Author:** ![jb4x](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/jb4x/32/789_2.png) [@jb4x](https://discourse.processing.org/u/jb4x)\
**Post date:** [April 14, 2021, 8:09pm UTC](https://discourse.processing.org/t/random-shape-generator/28843/11 "2021-04-14T20:09:31Z")

</div>

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**
>
> ```auto
> 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;
> }
> 
> ```

 ![image](https://canada1.discourse-cdn.com/flex036/uploads/processingfoundation1/original/2X/6/663e2b71ea5a26d09ae9bebb714cf364defb30f1.png)

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

---

<div class="post-metadata">

**Author:** ![solub](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/solub/32/333_2.png) [@solub](https://discourse.processing.org/u/solub)\
**Post date:** [April 14, 2021, 9:05pm UTC](https://discourse.processing.org/t/random-shape-generator/28843/12 "2021-04-14T21:05:55Z")

</div>

> [@jb4x](#):
>
> an easier way to create those kind of shape

@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:

 ![RCircle](https://canada1.discourse-cdn.com/flex036/uploads/processingfoundation1/original/2X/3/3842cdd168bcec7be98878ddb56d5f1d99bccf1b.png)

> **Random Radius**
>
> ```auto
> 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.

---

<div class="post-metadata">

**Author:** ![jb4x](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/jb4x/32/789_2.png) [@jb4x](https://discourse.processing.org/u/jb4x)\
**Post date:** [April 14, 2021, 9:13pm UTC](https://discourse.processing.org/t/random-shape-generator/28843/13 "2021-04-14T21:13:26Z")

</div>

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 =)