TheScienceGuy's blog

By TheScienceGuy, history, 6 weeks 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

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by TheScienceGuy (previous revision, new revision, compare).

»
6 weeks 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

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The problem with that is that the 2 rays could intersect at a very large (x,y) coordinates. I want to implement the solution that does not have to deal with huge numbers.

»
6 weeks 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.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    To check if 2 segments are on different sides of each other, you need to either calculate the signed area of a triangle formed by 3 points from the coordinates set, or calculate the orientation of those triangles. Both of these ways could involve either multiplying huge numbers (the numbers can get be out of bounds), or division (which can create a problem of machine error).

»
6 weeks 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.

  • »
    »
    6 weeks 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.