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.

user66332
  • 189
  • 2
  • 13
  • Are you working on the surface of a sphere, or just on a flat 2D plane? – e.James Mar 09 '09 at 22:55
  • I am working with Lat/Lon but I can easily convert to Cartesian which I would assume is a flat 2D plane. – user66332 Mar 09 '09 at 22:57
  • Unfortunately, it isn't. The conversion between Lat/Lon and cartesian gets very messy. It isn't a simple mapping from one to the other. – e.James Mar 09 '09 at 23:00
  • Anyway, interesting question... I'll have to think about it :) – e.James Mar 09 '09 at 23:01
  • PS: You're getting a lot of answers which deal only with normal 2D geometry. You may want to make it clear that you're dealing with the surface of a sphere. – e.James Mar 09 '09 at 23:12
  • What is the range of latitudes and longitudes over the problem domain? If it's small, you can use the 2D answers that have been provided. If it's larger, the curvature of the earth is going to be significant and they won't give you the right answer. – MarkJ Mar 09 '09 at 23:59
  • The distance from the ray origin to the polygons will most likely not be more the 20km and probably more in the range of 0-5km. – user66332 Mar 10 '09 at 00:36

4 Answers4

1

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
  • 24,862
  • 16
  • 85
  • 145
  • 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 Mar 09 '09 at 22:58
  • 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. – user66332 Mar 09 '09 at 22:59
1

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
  • 554,122
  • 78
  • 1,158
  • 1,373
  • 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? – user66332 Mar 09 '09 at 23:02
  • +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 Mar 09 '09 at 23:03
  • unknown, he means the start point. A ray only has one terminal point by definition.... – Sol Mar 09 '09 at 23:04
  • 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 Mar 09 '09 at 23:05
  • 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? – user66332 Mar 09 '09 at 23:11
  • 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 Mar 09 '09 at 23:13
  • 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 Mar 09 '09 at 23:20
1

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.

Community
  • 1
  • 1
Jason Cohen
  • 81,399
  • 26
  • 107
  • 114
  • 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. – user66332 Mar 10 '09 at 01:25
0

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

Question 1.E GodeGuru

Erik Forbes
  • 35,357
  • 27
  • 98
  • 122
user66332
  • 189
  • 2
  • 13
  • Lost, but wayback machine has it at https://web.archive.org/web/20171024132840/http://www.codeguru.com/cpp/cpp/algorithms/article.php/c5115/Geographic-Distance-and-Azimuth-Calculations.htm – timday Sep 04 '21 at 16:02