Блог пользователя TheScienceGuy

How to check if 2 rays intersect?
Автор TheScienceGuy, история, 4 года назад, По-английски

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.

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

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

→ Ответить
»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить
»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    → Ответить