Code for 2D line intersection

I’ve been struggling with finding the intersection between two lines so that the resulting point actually lies on the specified line segments. Most line intersection formulas use an infinite line model, so the point will tend to lie on an infinite extension of the segments. Which is not what I wanted at all.

First I implemented Paul Bourke’s excellent breakdown of the math. Then after much experimentation I realized I could calculate the distances from the intersection point to the end points of the two lines, and then check their combined length against the length of the lines. If the lenghts are the same then the intersection point is actually on the line segment. Quod erat demonstrandum.

The code also checks to see if the two lines are parallel using the dot product of the two vectors. Considering that I’m actually fairly inept at math I feel like I’ve scored a minor victory.

// lineIntersect.pde
// Marius Watz - http://workshop.evolutionzone.com

// calculates valid intersection between two lines,
// so that the intersection will lie on the specified
// line segment.

Point p[];
int num;

void setup() {
  size(500,250);

  num=12;
  p=new Point[num*2];
  for(int i=0; i< num*2; i++) p[i]=new Point(0,0);
  initPt();
}

void draw() {
  background(200);

  p[num-1].set(mouseX,mouseY);

  // check intersections with all lines
  for(int j=0; j< num; j++) {
    line(p[j*2].x,p[j*2].y, p[j*2+1].x,p[j*2+1].y);
    for(int i=0; i< num; i++) if(i!=j) {
      Point pt=findIntersection(
        p[i*2],p[i*2+1], p[j*2],p[j*2+1]);
      if(pt!=null) ellipse(pt.x,pt.y, 14,14);
    }
  }

}

void initPt() {
  for(int i=0; i< num; i++) {
    if(random(100)>50) {
      p[i*2].set(20,random(20,height-20));
      p[i*2+1].set(width-20,random(20,height-20));
    }
    else {
      p[i*2].set(random(20,width-20),20);
      p[i*2+1].set(random(20,width-20),height-20);
    }
  }
}

void mousePressed() {
  initPt();
  p[num-2].set(mouseX,mouseY);
}

// calculates intersection and checks for parallel lines.
// also checks that the intersection point is actually on
// the line segment p1-p2
Point findIntersection(Point p1,Point p2,
  Point p3,Point p4) {
  float xD1,yD1,xD2,yD2,xD3,yD3;
  float dot,deg,len1,len2;
  float segmentLen1,segmentLen2;
  float ua,ub,div;

  // calculate differences
  xD1=p2.x-p1.x;
  xD2=p4.x-p3.x;
  yD1=p2.y-p1.y;
  yD2=p4.y-p3.y;
  xD3=p1.x-p3.x;
  yD3=p1.y-p3.y;  

  // calculate the lengths of the two lines
  len1=sqrt(xD1*xD1+yD1*yD1);
  len2=sqrt(xD2*xD2+yD2*yD2);

  // calculate angle between the two lines.
  dot=(xD1*xD2+yD1*yD2); // dot product
  deg=dot/(len1*len2);

  // if abs(angle)==1 then the lines are parallell,
  // so no intersection is possible
  if(abs(deg)==1) return null;

  // find intersection Pt between two lines
  Point pt=new Point(0,0);
  div=yD2*xD1-xD2*yD1;
  ua=(xD2*yD3-yD2*xD3)/div;
  ub=(xD1*yD3-yD1*xD3)/div;
  pt.x=p1.x+ua*xD1;
  pt.y=p1.y+ua*yD1;

  // calculate the combined length of the two segments
  // between Pt-p1 and Pt-p2
  xD1=pt.x-p1.x;
  xD2=pt.x-p2.x;
  yD1=pt.y-p1.y;
  yD2=pt.y-p2.y;
  segmentLen1=sqrt(xD1*xD1+yD1*yD1)+sqrt(xD2*xD2+yD2*yD2);

  // calculate the combined length of the two segments
  // between Pt-p3 and Pt-p4
  xD1=pt.x-p3.x;
  xD2=pt.x-p4.x;
  yD1=pt.y-p3.y;
  yD2=pt.y-p4.y;
  segmentLen2=sqrt(xD1*xD1+yD1*yD1)+sqrt(xD2*xD2+yD2*yD2);

  // if the lengths of both sets of segments are the same as
  // the lenghts of the two lines the point is actually
  // on the line segment.

  // if the point isn’t on the line, return null
  if(abs(len1-segmentLen1)>0.01 || abs(len2-segmentLen2)>0.01)
    return null;

  // return the valid intersection
  return pt;
}

class Point{
  float x,y;
  Point(float x, float y){
    this.x = x;
    this.y = y;
  }

  void set(float x, float y){
    this.x = x;
    this.y = y;
  }
}