How do I find the intersection point of two line SEGMENTS, if one exists?

Question

I have two line segments described as below:

# Segment 1
((x1, y1), (x2, y2))

# Segment 2
((x1, y1), (x2, y2))

I need a way to find their intersection point if one exists, using no third-party modules. I know people have asked this question before, but every single answer I've found either doesn't always work or uses a third-party module.

So far, I've seen these questions and their "answers": How do I compute the intersection point of two lines? How can I check if two segments intersect?

Answer 1

Here's a very simple algorithm using basic algebra. There are more efficient ways to do this, as shown in the question OP shared, but for people that don't know any linear algebra they won't be particularly helpful.

Given two segments, you can use their endpoints to find the equation for each line using the point-slope formula, y - y1 = m (x - x1).

Once you've found the equation for each line, set them equal to each other and algebraically solve for x. Once you find x, plug that into either equation to get y and your intersection point will be (x, y).

Finally, check that this intersection point lies on both segments.

If you cannot solve for x it means the lines don't intersect. One easy test would be to first check if the slopes of the two lines are the same before doing the rest of the work. If they are, the lines are parallel and will never intersect unless their intercepts are also the same, in which case the lines will intersect everywhere.

Do the algebra symbolically with pen and paper first, then translate the formula for the intersection point into code. Then build out the other logic.

Vertical lines require slightly different logic. If both are vertical then you'd need to check if the segments share the same x values. If they do then check if any of the y coordinates overlap.

If only one segment is vertical, then find the equation for the non-vertical line, and evaluate it at the x coordinate of the vertical line. That'll give you the y coordinate of the potential intersection. If that y value is between the two y coordinates of the vertical line AND the x coordinate is on the non-vertical segment, then the segments intersect.

There are plenty of opportunities for short-circuiting here, try to find them yourself during implementation.

It may help to implement a custom class to represent your segments:

class Segment:
    def __init__(self, *, x1: float, x2: float, y1: float, y2: float) -> None:
        self.x1 = x1
        self.y1 = y1
        self.x2 = x2
        self.y2 = y2

    def __contains__(self, x: float) -> bool:
        """
        Check if `x` lies on this segment (implements the `in` operator, 
        allowing for expressions like `x in some_segment`)
        """
        pass

    def slope(self) -> float:
        try:
            return (self.y2 - self.y1) / (self.x2 - self.x1)
        except ZeroDivisionError:
            print("this segment is vertical!")
            return float("inf")

    def equation(self):
        """The equation for the line formed by this segment"""
        pass

    def intersects(self, other) -> bool:
        """Check if two Segment objects intersect each other"""
        pass