TheScienceGuy's blog

How to check if 2 rays intersect?
By TheScienceGuy, history, 3 years ago, In English

We are given the 2D coordinates (all integers) of 2 points: the first point is where the ray starts and it goes through the second point. We are given another ray in the same way. How do we determine if they have a point of intersection? I would like to know the general algorithm and its explanation, don't mind about the extreme cases (e.g. when the rays have the same starting point). P.S. I saw a similar question on stack exchange, but the answers were not backed up by explanation.

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
3 years ago, # |
  Vote: I like it +7 Vote: I do not like it

just calculate their points of intersection as lines and then check if the intersection point is in the right direction on the rays

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

There's an easy way to check if two segments intersect, using cross products (for each segment, make sure its endpoints lie on opposite sides of the other segment). So, maybe you could just take two "very far away" points on each ray, and check that they intersect.

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

One way is obviously to just solve the 2 linear equations, and check if the solution is inside the rays.

I had an another idea for this, don't know if it's 100% correct tho.

(separately see the case for parallel rays, i.e same slope)

Now we know, that the rays if extended in both directions will definitely intersect(since we are dealing with 2D). So they are lines instead of rays for now.

Now ternary search on distance b/w the points of these two lines with the same x coordinate. This distance seems to form a suitable curve for ternary search with x. (at one point it's 0, and to both left and right of it, this distance monotonically increases)[This is the part where I don't have proof].

Now we have the point of intersection, we can check if it lies inside the ray given for both 2 rays.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    for proof of why this distance is monotonically increasing when going away from point of intersection:

    Let's say the slope of these two lines are tan(theta) and tan(phi).

    say we are at x which is r distance away from x where intersection happens, now the distance we are measuring is r * abs(tan(theta) — tan(phi)), which is directly proportional to r. Hence as the distance from point of intersection increases, the distance increases.

    → Reply