Ray-Polygon Intersection Point on the surface of a sphere

Question

I have a point (Lat/Lon) and a heading in degrees (true north) for which this point is traveling along. I have numerous stationary polygons (Points defined in Lat/Lon) which may or may not be convex.

My question is, how do I calculate the closest intersection point, if any, with a polygon. I have seen several confusing posts about Ray Tracing but they seem to all relate to 3D when the Ray and Polygon are not on the same Plane and also the Polygons must be convex.

Answer 1

The answer on this page seems to be the most accurate.

Question 1.E GodeGuru

Answer 2

sounds like you should be able to do a simple 2d line intersection...

However I have worked with Lat/Long before and know that they aren't exactly true to any 2d coordinate system.

I would start with a general "IsPointInPolygon" function, you can find a million of them by googling, and then test it on your poly's to see how well it works. If they are accurate enough, just use that. But it is possible that due to the non-square nature of lat/long coordinates, you may have to do some modifications using Spherical geometry.

Answer 3

In 2D, the calculations are fairly simple...

You could always start by checking to make sure the ray's endpoint is not inside the polygon (since that's the intersection point in that case).

If the endpoint is out of the line, you could do a ray/line segment intersection with each of the boundary features of the polygon, and use the closest found location. That handles convex/concave features, etc.

Answer 4

Compute whether the ray intersects each line segment in the polygon using this technique.

The resulting scaling factor in (my accepted) answer (which I called h) is "How far along the ray is the intersection." You're looking for a value between 0 and 1.

If there are multiple intersection points, that's fine! If you want the "first," use the one with the smallest value of h.