Vector math for line-to-line intersection


#1

While learning about vectors, I worked through this to better understand line-to-line intersection math instead of simply using it “because it works”.

final int N = 4; // Fixed number to make two segments
int MAX_DIST = 20;

// Control points
PVector[] p = new PVector[N];

boolean held = false;
int nearest = -1;
float startx = 0;
float starty = 0;
float DIV_TOO_FAR = 0.00001;

// Calculates the intersection with vectors.
// Surely this uses the same math as solving the equations.
// Input:
//   Two line segments defined by points "a-b" and "c-d"
//   A PVector instance to hold the location of the intersection
// Returns:
//   True if segments cross, else false
//   Result vector is updated with the intersection point
boolean intersection(PVector a, PVector b, PVector c, PVector d, PVector result)
{
  // center everything on point "d"
  PVector axis = c.copy().sub(d);
  float axLen = axis.mag();
  axis.normalize();
  PVector workingA = a.copy().sub(d);
  PVector workingB = b.copy().sub(d);

  // create a perpendicular vector to "c-d"
  PVector rightang = new PVector(-axis.y, axis.x);

  // In short: rotate everything so "c-d" becomes the y-axis
  //   rightang becomes x-axis
  PVector mappedA = new PVector(workingA.dot(rightang), workingA.dot(axis));
  PVector mappedB = new PVector(workingB.dot(rightang), workingB.dot(axis));
  // More detail: mappedA and -B are projections of "a" and "b" onto the lines
  //   "c-d" and "rightang", creating Axis Aligned 2D coordinates

  // Get the axis-aligned segment
  PVector dir = mappedA.sub(mappedB);

  // This is the same math used for 2D axis-aligned-bounding-boxes but only used
  //   for one intersection instead of two edges
  // In other words:
  //   "How much do we change segment 'a-b's length to reach segment 'c-d'?"
  // Result can be +/- INF, meaning segments are parallel
  // Relying on the floating point to handle div by 0.0 --> INF
  //   is implementation dependant. Your hardware may vary.
  float tx = 1.0 / DIV_TOO_FAR;
  if (abs(dir.x) > DIV_TOO_FAR)
    tx = -mappedB.x / dir.x;
  
  // when the original line segment "a-b" is extended/shortened by tx,
  //   the end of that segment is the intersecting point
  PVector inters = a.copy().sub(b).mult(tx).add(b);
  result.set(inters);
  
  // Segment/segment intersection:
  // Logic is that if the first segment would have to expand or reverse to
  //   reach the point at 'inters', then the segments do not cross
  float ty = inters.sub(d).dot(axis);
  boolean intersecting = (tx >= 0) && (tx <= 1.0) && (ty >= 0) && (ty <= axLen);
  
  return intersecting;
}

void setup()
{
  size(800,600,P2D);

  // Initial points, this setup is parallel
  p[0] = new PVector(width/4, height/4);
  p[1] = new PVector(width - (width/4), height/4);
  p[2] = new PVector(width/4, height - (height/4));
  p[3] = new PVector(width - (width/4), height - (height/4));
  
  noFill();
  frameRate(60);
  background(0);
}

void mouseMoved()
{
  float neardist = width + height;
  for (int i=0; i<N; i++)
  {
    float nd = dist(p[i].x,p[i].y, mouseX,mouseY);
    if (nd < neardist)
    {
      nearest = i;
      neardist = nd;
    }
  }
  if (MAX_DIST < neardist)
  {
    nearest = -1;
  }
}

void mousePressed()
{
  if (-1 != nearest)
  {
    held = true;
    startx = mouseX - p[nearest].x;
    starty = mouseY - p[nearest].y;
  }
}

void mouseReleased()
{
  held = false;
}

void draw()
{
  // This section allows you to move the control points
  if (held)
  {
    p[nearest].x = constrain(mouseX-startx,0,width); // suggested by jeremydouglass
    p[nearest].y = constrain(mouseY-starty,0,height);
    background(0);
  }
  
  // Show control points
  for (int i=0; i<N; i++)
  {
    if (i == nearest)
    {
      stroke(0,255,0);
    }
    else
    {
      stroke(0,0,255);
    }
    ellipse( p[i].x,p[i].y, MAX_DIST,MAX_DIST );
  }
  
  PVector cros = new PVector();
  boolean test = intersection(p[0], p[1], p[2] ,p[3], cros);
  
  int col = test ? color(255,0,0) : color(255,0,255);
  stroke(col);
  line(p[0].x,p[0].y, p[1].x,p[1].y);
  line(p[2].x,p[2].y, p[3].x,p[3].y);
  
  stroke(0,255,0);
  ellipse(cros.x,cros.y, 4,4);
}

#2

Nice. I did something similar but this is better. Will be using this soon for a printmaking project!