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.
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:
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.
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
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.
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.
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)
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;
}
@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 ?
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.
