views:

1284

answers:

4

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.

+1  A: 

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.

Neil N
Good point on the Lat/Long comment! Reprojecting all of the points into a better coordinate system for the specific location (ie: UTM) would be required for this to be accurate.
Reed Copsey
I have implemented Winding Point to check if a point is inside of a polygon but I don't see how I can use that to see if a ray intersects a polygon.
ahh right, your using ray, not point.. I will edit my answer
Neil N
+1  A: 

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.

Reed Copsey
How do I calculate the endpoint of a ray given only its start point and a direction? Would I somehow have to use a bounding box to for the polygon?
+1 even though I'd just skip the first step. What's the point of it? Calculating whether or not the ray's point is inside the polygon is about as hard as just finding the closest intersection point....
Sol
unknown, he means the start point. A ray only has one terminal point by definition....
Sol
Sol: He wanted the intersection point. If the starting point is inside the polygon, you need to trap that, since the intersection point == starting point. If it's outside the polygon, it's the ray-segment intersect point.Unknown: I was referring to the starting point of the ray. ;)
Reed Copsey
Ok, I have several polygons though and a ray that could be updating frequently. Is calculating a ray/line intersection for every line in every polygon then taking the closest intersection point very efficient?
just to toss this out there... technically a ray on the surface of the earth is not infinite, it will hit its starting point in approximately 13,000 miles of circumnavigation.
Neil N
Depends on how many polygons you're dealing with, and how complex they are. The computations are quick in 2D, though, so it's probably not too bad. If this is a continually updating process (ie: real-time monitoring), caching the "last" segment and checking it first might be possible.
Reed Copsey
+1  A: 

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.

Jason Cohen
Ok, so I think A would be my ray origin and E is my directional vector? If so Im still confused how I am going to use Lat/Lon with this and convert my heading into a vector.
A: 

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

Question 1.E GodeGuru