Take the 2-minute tour ×
Geographic Information Systems Stack Exchange is a question and answer site for cartographers, geographers and GIS professionals. It's 100% free, no registration required.

I'm interested in understanding how real-world GIS systems and their data encode Polygons.

Specifically, how do they resolve the ambiguity of a Polygon's interior on a sphere?

Background: in 2D, it's trivial to pick the side of the boundary that has a finite area, since the 2D plane is infinite. However, a sphere is finite, so it's impossible to know which side is inside without making additional assumptions.

Possible approaches that I know of:

  1. Right-hand-rule: exterior boundaries are always specified in clockwise order, and holes are specified in anticlockwise order. (There is of course the left-hand-rule, too).
  2. Smallest area: for any given ring, always pick the side with the smallest area. I'm not sure how you would specify a large-range Polygon: perhaps an empty exterior ring followed by holes?
  3. Equirectangular: Simply consider the equirectangular projection on an infinite 2D plane. However, this assumes features are chopped at the antemeridian, otherwise a fallback would be required to one of the two methods above.

My personal preference is the first approach, but I'm interested in understanding whether this is common in standard GIS systems.

share|improve this question

2 Answers 2

If I understand your question correctly, you want to know how GIS performs a point in spherical polygon test. Here's an algorithm I found at geospatialmethods.org:

  1. Connect the point to the known external point with a great circle arc.
  2. For each great circle arc that is a side of the spherical polygon test if it intersects the arc constructed in step #1 and count the number of intersections.
  3. If the total number of intersections is odd the given point is inside the spherical polygon. if the total number of intersections is even the point is outside the spherical polygon.

I guess it's still based on the planar algorithm of constructing a test ray from the point in question to a point known to be outside the polygon, followed by counting how many edges the ray crosses that you mentioned.

It is also discussed in depth in a NASA JPL paper on algorithms on polygons on a sphere. It's at page 11. There are of course, some optimizations:

First, avoid performing the computationally expensive spherical trigonometry computations when possible by checking the test ray against a pre-computed bounding box before looking at any of the polygon’s edges. If the test ray does intersect the bounding box, Q is checked against each of the polygon’s vertices. There is no point in testing whether Q is on an edge at this point, because that will be revealed when the intersection tests are performed and the rest of the edges can be skipped at that time.

I think you will find the paper most interesting :)

share|improve this answer
    
This appears to answer a different question. A non-self-intersecting, closed polyline partitions a sphere into two connected components. The OP asks how does the GIS determine--or how is it told--which of those components is to be considered "inside" and which "outside"? The Website you quote discusses this issue under the heading "Guess External Point," emphasizing that it is merely guessing which component is intended to be inside. –  whuber Nov 30 '12 at 13:20
    
Oh... drat. Misunderstood his question. I conflated it with the spherical version of the point in polygon test. Will revise it as soon as I find an answer. –  R.K. Nov 30 '12 at 13:33
    
Well, I appreciated the references you found, so I hope you manage to include them in your revised answer :-). –  whuber Nov 30 '12 at 13:38
    
I hope so, too. Or maybe I'll just ask a question and answer it myself ;-) Would be a shame to waste them. –  R.K. Nov 30 '12 at 13:44
    
Thanks for the detailed answer! Unfortunately as @whuber points out, this doesn't answer my specific question. :) I've outlined possible approaches to resolve the inherent ambiguity of where the inside of a polygon is, but I'm interested in knowing what approaches real-world GIS software take. –  Jason Davies Nov 30 '12 at 14:19
up vote 0 down vote accepted

Major GIS systems and their methods for resolving the inherent ambiguity:

  • ESRI: right-foot rule.
  • ArcGIS: right-foot rule.
  • SQL Server 2012: left-foot rule. Prior to SQL Server 2012, larger-than-hemisphere polygons would throw an error.

GeoJSON does not specify an ordering.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.