views:

336

answers:

4

How do I determine if a point is inside or outside a polygon that lies on the the surface of the earth?

The inside of the polygon can be determined via the right hand rule, ie. the inside of the polygon is on your right hand side when you walk around the polygon.

The polygon may

  1. Circle either pole
  2. Cross the 180 longitude
  3. Cover more than 50% of the globe

As the globe is a sphere the normal ray crossing algorithms do not work correctly.

+1  A: 

Use planes instead of rays. A "line" on the surface of a sphere defined by two points is an arc of a great circle (circle whose center is the center of the sphere) and is also contained in a plane that contains those two points and the center of the sphere.

Test whether the point is "greater" or "less" than the corresponding plane for each edge of the "polygon" to determine which side of the "line" it is on.

Slartibartfast
Thanks, I understand the basic theory. Do you know of a Java api that does this? Or somewhere I can find an algorithm?
richard
NASA provides an open source Java SDK called WorldWind for geospatial applications. It might be overkill for what you need but it might provide more ideas for your application. http://worldwind.arc.nasa.gov/java/
Tansir1
I'd address it like a math problem. Find a formula for a plane from three points on the plane, plug your point into the formula and see which side of the plane it is on. Lather, rinse, repeat. I'd use xyz coordinates, rather than the cylindrical / spherical coordinate systems, just because planes are simpler that way. Since I'm not familiar with your ray crossing algorithm, I don't know how to adapt this approach to it, but I suspect it is doable.
Slartibartfast
+1  A: 

In fact the normal ray tracing and winding rule approaches work just fine on the surface of a sphere, with a little adjustment.

On the surface of a sphere a 'straight line' is a great circle and distances are measured in angular units rather than metres or inches. To draw a ray from an arbitrary point on the surface of the sphere simply form a great circle through that arbitrary point and any other point on the surface of the sphere. To keep the maths clean choose a second point about pi/2 away from the point whose location you are testing. Apply the usual even-odd rule to the great circle and your test polygon.

The winding rule also translates directly from straight lines in the plane to (segments of) great circles on a sphere.

All you need now are Java implementations of basic spherical geometry operations. I don't have any recommendations on that front, but I guess the Internet will help. For the maths start with Mathworld.

Another approach would be to project your points and polygons from the surface of the sphere to the plane -- which is what map projections do -- the topological relationship of insideness will not be affected by such a transformation.

Oh, and you'll have to decide what to do if your polygon describes a great circle

High Performance Mark
You don't have to decide anything if your polygon describes a great circle. There is still an interior and an exterior.
Alexandre C.
A: 

Since you're interested in a Java API for this, check out this SphericalPolygon class. It's part of a GNU GPL Java package, complete with source.

brainjam