Old Project, New Version

[jeremydouglass]

It would be inefficient to do line-line on all points, as that is ~13 million checks to find the intersections between pairs of points, which may intersect 0, 1, or 2 times.

However, that will solve the problem simply.

Collision Detection

Here is an example finding all intersections on two randomly generated lines:

/**
 * PointListIntersections
 * find any/all intersections on two random point lists
 * 2020-05-22 Jeremy Douglass Processing 3.5.4 
 * https://discourse.processing.org/t/old-project-new-version/20156/20
 *
 * This is checking *all* pairs, which is inefficient for ordered data.
 */
 
PVector[] as;
PVector[] bs;
int len = 100;  // how many points per line
int xstep = 5;  // x step on canvas between points

void settings() {
  size(len*xstep, len*xstep);
}

void setup() {
  as = new PVector[len];
  bs = new PVector[len];
  makePoints(xstep);
}
void draw() {
  background(255);

  // randomize the points again
  if(frameCount%120==0) {
    noiseSeed(frameCount);
    makePoints(xstep);
  }
  drawPoints(as, color(255,0,0));
  drawPoints(bs, color(0,0,255));

  drawLines(as, color(255,0,0));
  drawLines(bs, color(0,0,255));
  
  ArrayList<PVector> crosses = findCrosses(as, bs);
  for(PVector cross : crosses) {
    fill(0,255,0,128);
    ellipse(cross.x, cross.y, 10, 10);
  }
}
  
void drawPoints(PVector[] pts, color c) {
  for(int i=0; i<len; i++) {
    fill(c);
    ellipse(pts[i].x, pts[i].y, 3, 3);
  }
}

void drawLines(PVector[] pts, color c) {
  for(int i=1; i<len; i++) {
    stroke(c);
    line(pts[i-1].x, pts[i-1].y, pts[i].x, pts[i].y);
  }
}

void makePoints(int xstep) {
  for(int i=0; i<len; i++) {
    as[i] = new PVector(i*xstep, height * noise(i*0.02));
    bs[i] = new PVector(i*xstep, height - height * noise(i*0.05));
  }
}

ArrayList<PVector> findCrosses (PVector[] as, PVector[] bs) {
  ArrayList<PVector> crosses = new ArrayList<PVector>();
  for(int a=1; a < as.length; a++) {
    for(int b=1; b < bs.length; b++) {
      PVector cross = lineLine(as[a-1].x, as[a-1].y, as[a].x, as[a].y, bs[b-1].x, bs[b-1].y, bs[b].x, bs[b].y);
      if(cross!=null) crosses.add(cross);
    }
  }
  return crosses;
}

PVector lineLine(float x1, float y1, float x2, float y2, float x3, float y3, float x4, float y4) {
  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 >= 0 && uA <= 1 && uB >= 0 && uB <= 1) { // lines are colliding
    float x = x1 + (uA * (x2-x1));
    float y = y1 + (uA * (y2-y1));
    return new PVector(x, y);
  }
  return null;
}