A simple algorithm to determine whether two line segments intersect

The problem of determining whether two line segments sg1 and sg2 on the x,y coordinate plane intersect doesn't seem difficult at all, but it does seem a bit tricky indeed. This post proposes an easy-to-understand algorithm and illustrates the calculation process for proving this algorithm. The algorithm employs only junior high school mathematics and. The Java code below is my implementation of the algorithm.


-----------------------------------

Suppose line segment 1 connects (x1, y1), (x2, y2) and line segment 2 connects (x3, y3), (x4, y4).

If sg1 is perpendicular to x axis, we first check x3 and x4. If both values are larger or smaller than sg1’s x coordinate, then sg1 and sg2 certainly do not intersect. If not, calculate the equation f(x) = mx + i for sg2. If point (x1, m*x1 + i) at sg2 is also a point of sg1, the answer is true. Else, the answer is false. Else, if sg2 is perpendicular to x axis, simply replace sg1 and sg2 for this question and check again.

And if both segments are not perpendicular to the x axis, by junior high school math, the equation for the line connecting (x1, y1) and (x2, y2) is:



Similarly, the equation for the line connecting (x3, y3) and (x4, y4) is:



If the slopes of the two lines are equivalent, sg1 and sg2 do not intersect. If not, then the two lines (1) and (2) must have an intersection at somewhere on the xy coordinate plane. Calculate the intersection and check whether the point is at the segment.

The x coordinate of the intersection of lines (1) and (2) satisfies:



Subsequently, check whether this x value is within the range of x1 and x2. If it is, sg1 and sg2 do intersect; otherwise, they do not intersect.

 

Point.java

package com.packa9e;

public class Point {
 public double x, y;
 public Point(double x, double y) {
  super();
  this.x = x;
  this.y = y;
 }
}

Segment.java

package com.packa9e;

public class Segment {

 public final Point start, end;
 public final boolean isVertical; 
 public final double slope, intercept; 
 
 public Segment(Point start, Point end) {
  this.start = start;
  this.end = end;
  //set isVertical, which indicates whether this Line 
  //is vertical or not on the coordinate plane
  if (start.x == end.x)
   isVertical = true;
  else
   isVertical = false;
  
  //set slope and intercept
  if (!isVertical){
   slope = (start.y - end.y) / (start.x - end.x);
   intercept = (end.x * start.y - start.x * end.y ) /(start.x - end.x); 
  }
  else {
   slope = Double.MAX_VALUE;
   intercept = - Double.MAX_VALUE;
  }
 }
}

IntersectionCheceker.java

package com.packa9e;

public class IntersectionCheceker {

 public final Segment segment1, segment2;
 private Boolean hasIntersection;
 
 public IntersectionCheceker(Segment segment1, Segment segment2){
  this.segment1 = segment1;
  this.segment2 = segment2;
 }
 
 public IntersectionCheceker(double x1, double y1, double x2, double y2,
  double x3, double y3, double x4, double y4){
  Point start1 = new Point(x1, y1);
  Point end1 = new Point(x2, y2);
  Point start2 = new Point(x3, y3);
  Point end2 = new Point(x4, y4);
  this.segment1 = new Segment(start1, end1);
  this.segment2 = new Segment(start2, end2);
 }
 
 public boolean hasIntersection(){
  if (hasIntersection != null)
   return hasIntersection;
  
  if (segment1.isVertical){
   if ( (segment2.start.x - segment1.start.x)*(segment2.end.x - segment1.start.x) > 0 )
    hasIntersection = false;
   else {
    double fx_at_segment1startx = segment1.slope * segment1.start.x + segment1.intercept;
    double smaller, larger;
    if (segment1.start.x < segment1.end.x ){
     smaller = segment1.start.x;larger = segment1.end.x; 
    }
    else {
     larger = segment1.start.x;smaller = segment1.end.x;
    }
    if (smaller <= fx_at_segment1startx && fx_at_segment1startx <= larger)
     hasIntersection = true;
    else
     hasIntersection = false;
   }
  }
  else if (segment2.isVertical){
   hasIntersection = new IntersectionCheceker(segment2, segment1).hasIntersection();
  }
  else { //both segment1 and segment2 are not vertical 
   if (segment1.slope == segment2.slope)
    hasIntersection = false;
   else {
    double x1 = segment1.start.x;
    double y1 = segment1.start.y;
    double x2 = segment1.end.x;
    double y2 = segment1.end.y;
    double x3 = segment2.start.x;
    double y3 = segment2.start.y;
    double x4 = segment2.end.x;
    double y4 = segment2.end.y;
    double x = ((x4*y3-y4*x3)/(x4-x3) - (x2*y1-y2*x1)/(x2-x1))
      /( (y2-y1)/(x2-x1) - (y4-y3)/(x4-x3));
    
    double smaller, larger;
    if (x1 < x2){
     smaller = x1; larger = x2;
    }
    else {
     smaller = x2; larger = x1;
    }
    if (smaller <= x && x <= larger)
     hasIntersection = true;
    else 
     hasIntersection = false; 
   } 
  }
  return hasIntersection;
 }
  
 
 public static void main(String[] args) {
  
  IntersectionCheceker checker1 = new IntersectionCheceker(1, 0, 1.2, 3, 2.4, 5, 3.6, -1);
  boolean hi1 = checker1.hasIntersection();
  System.out.println("IntersectionCheceker.main() 64 hi1 = " + hi1);
 }
}