| Re: Determing Whether A Point Is Located Inside Polygon
There is also a "ray" algorithm, where you project a line from your point to infinity. Count the number of times the line crosses the boundary of the polygon. If it is odd, then the point is in the polygon.
For a sphere then you probably want to project along a line of latitude or longitude, and make assumptions about the shape not including the international date line, north pole, or something similar (eg. project to 180deg).
Sedgwick's "Algorithms" has a nice optimisation of the above algorithm (for a plane).
I'm probably going to be coding it up in C# for MapPoint in the next few months, so if Eric is interested then I might be persuaded to write an article about it...
Richard |