Finding the intersection between two lines

Today, we are going to unlock the mysteries behind finding the intersection between two lines.

Now, this might sound as if we are about to embark on a journey to solve some formidable calculus problem, but fear not!

We are merely diving into some delightful elementary algebra. So let's get started, shall we?

Setup

In our setup, we are going to draw two lines on a graph. Line A - B goes from point A to point B. Similarly, Line C - D travels from point C, to point D.

Step 1: The Slope

To find the slope, remember this: you need to know how much your line goes up or down (the $y$ -change) for each step it takes to the left or right (the $x$ -change).

In mathematics, this is beautifully represented by the formula:

m_{AB} = \frac{x_B - x_A}{y_B - yA}

This, my dears, is the slope of Line A - B, denoted as $m_{AB}$ . Why we represent slopes with the letter $m$ is beyound me, but it is what it is.

We calculate it by subtracting the $y$ -coordinate of point A from the $y$ -coordinate of point B and dividing it by the difference between the $x$ -coordinates of point B and point A.

In plain english, the slope is the answer for the question: For each step horizontal step we take, how many steps do we take vertically?

Repeat this step for Line C - D to find its slope.

Show me the code

I know you're not here for the convoluted math formulas with their single letter variable names, what are we? Savages?

You want to see some code! So let's get to it, shall we?

typescript

const findSlope = (a: Vec2, b: Vec2) => {
  return (b.y - a.y) / (b.x - a.x);
};

Much better! We have a function that takes two points and returns the slope of the line that connects them.

Caveat: Vertical Lines

Vertical lines are a special case. Because they don't move at all horizontally, they happen to cause a division by zero. Which in JavaScript, gives us the special value Infinity.

We will deal with this case later.

Step 2: Find the y-intercept for each line

A line’s y-intercept is like a home base, the safe spot at y when x equals zero. To find it, we employ the following equation:

y - mx = b

Where m is our previously calculated slope, y and x are the coordinates of any point on the line, and b, our goal, represents the y-intercept.

As a function of x and y:

b(x, y) = y - mx

Or in bits and bytes:

typescript

const findYIntercept = (point: Vec2, slope: number) => {
  return point.y - slope * point.x;
};

Step 3: Find the intersection point of the two lines at infinity

Ever the romantic, I fancy the idea of two lines intersecting at the horizon, somewhere far beyond our reach.

To find this point, we pit the equations of our two lines against each other, et voila, we have our $x$ coordinate. Substituting $y$ into either line's equation reveals the $y$ coordinate.

So remember, we have our slopes: $m_{AB}$ and $m_{CD}$

And our two y-intercepts $b_{AB}$ and $b_{CD}$

With these, we can find the intersection point of the two lines at infinity:

x = \frac{b_{CD} - b_{AB}}{m_{AB} - m_{CD}}

y = m_{AB}x + b_{AB}

typescript

const findIntersection = (a: Vec2, b: Vec2, c: Vec2, d: Vec2) => {
  // Find our slopes
  const abSlope = findSlope(a, b);
  const cdSlope = findSlope(c, d);


  // Find our y-intercepts
  const abIntercept = findYIntercept(a, abSlope);
  const cdIntercept = findYIntercept(c, cdSlope);


  const x = (cdIntercept - abIntercept) / (abSlope - cdSlope);
  const y = abSlope * x + abIntercept;


  return point(x, y);
};

The edge cases in the room

There are a two edge cases to consider:

What if the two lines are parallel?
What if one of the lines is vertical?

So let's address them before we move on.

typescript

const findIntersection = (a: Vec2, b: Vec2, c: Vec2, d: Vec2) => {
  // Find our slopes
  const abSlope = findSlope(a, b);
  const cdSlope = findSlope(c, d);


  // If the two lines are parallel or if they are exactly the same, then their slopes are equal.
  // That means that our lines will never intercept, so we return `null` early one.
  if (abSlope === cdSlope) {
    return null;
  }


  let x: number;
  let y: number;


  // If one of the lines is vertical, then its slope is infinite.
  // Our lines can still intercept if at least one of the other lines is not vertical.
  // So we handle that case separately
  if (!Number.isFinite(abSlope)) {
    x = a.x;
    y = cdSlope * x + findYIntercept(c, cdSlope);
  } else if (!Number.isFinite(cdSlope)) {
    x = c.x;
    y = abSlope * x + findYIntercept(a, abSlope);
  } else {
    const abIntercept = findYIntercept(a, abSlope);
    const cdIntercept = findYIntercept(c, cdSlope);
    x = (cdIntercept - abIntercept) / (abSlope - cdSlope);
    y = abSlope * x + abIntercept;
  }


  return point(x, y);
};

Step 4: Find the intersection within the two line segments

While daydreaming of intersections at the end of the universe can be delightful, sometimes we need to be grounded in reality. The final act of our little escapade is checking if the intersection point we found actually lies within the segments of the lines we're considering.

To do that we can draw a square around our two lines and check if the intersection point we found lies within those squares.

The formula for checking if a point lies within a square is:

x_{min} \leq x \leq x_{max} \land y_{min} \leq y \leq y_{max}

Where $x_{min}$ and $x_{max}$ are the minimum and the maximum between between $x_{A}$ and $x_{B}$ respectively. The same applies for $y_{min}$ and $y_{max}$ .

typescript

const isWithinBoundingBox = (point: Vec2, a: Vec2, b: Vec2) => {
  const minX = Math.min(a.x, b.x);
  const maxX = Math.max(a.x, b.x);
  const minY = Math.min(a.y, b.y);
  const maxY = Math.max(a.y, b.y);


  return (
    point.x >= minX && point.x <= maxX && point.y >= minY && point.y <= maxY
  );
};

Step 5: Putting it all together

And there we have it, darlings. A poetic journey into the world of lines and their intersections. Mathematics, code, and a touch of whimsy. Here's the final result:

typescript

type Vec2 = { x: number; y: number };


const findSlope = (a: Vec2, b: Vec2) => {
  return (b.y - a.y) / (b.x - a.x);
};


const findYIntercept = (point: Vec2, slope: number) => {
  return point.y - slope * point.x;
};


const isWithinBoundingBox = (point: Vec2, a: Vec2, b: Vec2) => {
  const minX = Math.min(a.x, b.x);
  const maxX = Math.max(a.x, b.x);
  const minY = Math.min(a.y, b.y);
  const maxY = Math.max(a.y, b.y);


  return (
    point.x >= minX && point.x <= maxX && point.y >= minY && point.y <= maxY
  );
};


const findIntersection = (a: Vec2, b: Vec2, c: Vec2, d: Vec2) => {
  // Find our slopes
  const abSlope = findSlope(a, b);
  const cdSlope = findSlope(c, d);


  // If the two lines are parallel or if they are exactly the same, then their slopes are equal.
  // That means that our lines will never intercept, so we return `null` early one.
  if (abSlope === cdSlope) {
    return null;
  }


  let x: number;
  let y: number;


  // If one of the lines is vertical, then its slope is infinite.
  // Our lines can still intercept if at least one of the other lines is not vertical.
  // So we handle that case separately
  if (!Number.isFinite(abSlope)) {
    x = a.x;
    y = cdSlope * x + findYIntercept(c, cdSlope);
  } else if (!Number.isFinite(cdSlope)) {
    x = c.x;
    y = abSlope * x + findYIntercept(a, abSlope);
  } else {
    const abIntercept = findYIntercept(a, abSlope);
    const cdIntercept = findYIntercept(c, cdSlope);
    x = (cdIntercept - abIntercept) / (abSlope - cdSlope);
    y = abSlope * x + abIntercept;
  }


  const intersection = point(x, y);


  // If the intersection point is within the bounding boxes of both lines, then we have an intersection.
  const isWithinAB = isWithinBoundingBox(intersection, a, b);
  const isWithinCD = isWithinBoundingBox(intersection, c, d);


  if (isWithinAB && isWithinCD) {
    return intersection;
  }
  return null;
};