-1

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?

Bituvo
  • 72
  • 7
  • Welcome to Stack Overflow! What have you tried so far? Have you written any code? Are you getting any errors? How do your results differ from your desired output? Please also refer to this post on [how to ask homework questions](https://meta.stackoverflow.com/questions/334822/how-do-i-ask-and-answer-homework-questions). – ddejohn Nov 19 '22 at 17:20
  • @ddejohn I already gave examples of what I tried, and this isn't a homework question. I genuinely want to know. Also, I can't give my results because I don't have any! Did you copy and paste this from somewhere without even reading the question because you assumed I am a noob? – Bituvo Nov 19 '22 at 17:24
  • I don't see anything in your post that demonstrates an attempt at solving the problem yourself. – ddejohn Nov 19 '22 at 17:27
  • @ddejohn "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" – Bituvo Nov 19 '22 at 17:30
  • Searching for solutions on this site is not the same as trying to solve the problem yourself. Do you nkow how to find the intersection of two lines? – Beta Nov 19 '22 at 17:34
  • Posting a link to something doesn't demonstrate that you've attempted to solve the problem on your own. You need to show exactly what you've tried and explain what "doesn't always work" means. I also recommend searching on the mathematics stack exchange as this isn't a coding problem. – ddejohn Nov 19 '22 at 17:34
  • @Beta If I knew how to find the intersection point, I wouldn't be asking you guys. – Bituvo Nov 19 '22 at 17:37
  • By "no third-party modules", you mean you don't want to use any library that solves the problem directly, or can't you use numpy for example to make representation & operations easier? Also, **if** you understand how to find the intersection point of two lines, then why can you not add a simple check in the end to ensure the point you found lies in *both* segments? The second post on the first link seems to provide code for the intersection point of two lines, so you can use that as the basis of your own code and then add the check at the end. – Alex P Nov 19 '22 at 17:39
  • If you don't understand the *mathematics* of finding the intersection of two lines, then obtaining code to do it for you will only lead you into more trouble. – Beta Nov 19 '22 at 17:49
  • Assuming he's correct that the existing top results are buggy or of poor quality, I think this is actually a valuable question - I know I've looked for this algorithm before, and it would be worth it to future searchers to have a single and complete solution. – Edward Peters Nov 19 '22 at 18:21

1 Answers1

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
ddejohn
  • 8,775
  • 3
  • 17
  • 30