| Re: Determing Whether A Point Is Located Inside Polygon
I'm getting close to implementing something.
I have found a reference to extending Wilfried's to work with concave polygons.
Basically, you have to check all triangles and count the number that contain the point. If the number is odd, then the point is in the shape.
It is from a review of different strategies and speeds in Graphics Gems IV.
Chapter 1.4 "Point in Polygon Strategies" pp 24-46. This further quotes Berlin 1985 "Efficiency considerations in image synthesis", SIGGRAPH '85 State of the Art in Image Synthesis seminar notes, July 1985.
It looks like the triangle method using pre-stored half planes is the fastest option for polygons with small numbers of vertices.
There's an interesting angle method (ch 1.3 in Gems IV) which doesn't even involve trigonometry because it can be optimized to simple quadrant classification. The benchmarks suggest it is slightly slower than the "ray" ("Crossings" they call it) algorithm, but should be pretty close with a good optimizing compiler.
Of course, all these standard discussions are for 2d Euclidean Space. We need something for a sphere. A polygon on a sphere has two "sides" - as I see it, the only difference between the inside and the outside is the size. The area of the inside is smaller than the area of outside.
I think we'll need trigonometry for the spherical coordinates.
I'll see what I come up with. C# and on a sphere. I'll be using my own objects, rather than MapPoint Locations.
Richard |