Old Project, New Version

Gallery
21

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.

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

PointListIntersections--screenshot
PointListIntersections--screenshot1000×1044 32 KB

1 Like
22

Yes sir, that’s quite good. I haven’t spent enough time with that yet, but one thing I noticed with my code is that the bigger the circle, the further the points are spaced as the number of points is fixed. So, I would zoom right into where the intersection should be and find multiple points for one circle and maybe one point for another. That made it trickier to visualize the intersection. When I started playing with drawing latitude and longitude lines, I noticed the point spacing was equal for a purely latitude or longitude line and sometimes a point might even land on the intersection.

I’ll be baaaack, thanks for the link.

1 Like
23

One thing bugging me and that is that I need to provide a link to navigationalalgorithms.com . That is where I got the basic point generator. I modified it but started with what Andres Ruiz wrote. Here is the link to the paper. http://www.mediafire.com/file/pp89of9q9fk4rbi/rotmatricesCoP.zip/file The title is “Use of Rotation Matrices to Plot a Circle of Equal Altitude” and is inside the zip file.

I’ve read some of his other papers too and I think there could be an efficient way to calculate an intersection using some of the functions I already have.