Is a point inside or outside a polygon which is on the surface of a globe

Question

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.

Pictorial

Your question isn't really clear: polygons cannot be curved (by definition) so are you instead asking how to determine whether a point is on the surface of a sphere? That's actually easy: it's on the surface if the distance to the centre of the sphere == the sphere's radius. – Hebraist

I believe he means if you take a series of points on the sphere and construct a closed shape between them. The finer points about how to connect polygon points into edges seems ambiguous (you can connect them directly then project onto the sphere, maybe?) – Snuggle

correct, a polygon in my world is a series of points on the sphere and I construct a closed shape between them – Pictorial

This page is relevant, but far from an answer on it's own publib.boulder.ibm.com/infocenter/db2luw/v8/index.jsp?topic=/… – Snuggle

@richard: Sorry, I probably should have got that from the 'geocoding' tag, yeah :) – Hebraist

Hold on a minute while I finish drawing this square around me....there! LOL, now you're all my prisoners! You'll have to pay a toll if you ever want to get out of my world-encompassing polygon! – Throat

This really seems like we are solving this kid's homework problem. – Chatoyant

@Gray, actually I disagree. I could think of many real world applications (just think of google earth for starters) – Snuggle

@Snuggle The finer points about how to connect polygon points into edges seems ambiguous - no, there's an obviously most reasonable way. That is to take the shortest possible path along the surface of the sphere that connects the two points. This path will also, as it happens, be an arc of a great circle. – Spring

Answer 1

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

Chambless

You don't have to decide anything if your polygon describes a great circle. There is still an interior and an exterior. – Raman

Answer 2

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.

Triggerhappy

Thanks, I understand the basic theory. Do you know of a Java api that does this? Or somewhere I can find an algorithm? – Pictorial

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. worldwind.arc.nasa.gov/java – Kaiak

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. – Triggerhappy

This would definitely work for convex shapes, but wouldn't always work for concave shapes. Consider a Pacman shape, and the point is Pacman's eye. The point would be considered "outside" for one half of Pacman's mouth. – Actuary