Determing Whether A Point Is Located Inside Polygon

Wilfried Mestdagh wrote this article on determing whether a vehicle is located inside or outside a convex polygon. "Simplify the polygon by make triangles from it one by one, until we have a triangle where the point is inside. At the end we only have to verify if the point is in the last triangle."

Article at -- Determing Whether A Point Is Located Inside Polygon (http://www.mp2kmag.com/a139--.mappoint.html)

Lot of polygon in GIS ARE NOT convex , so , what do you do in this case ?

Personally I would be tempted to use a GIS engine such as MapInfo's MapX in the background instead of reinventing the wheel. Last time I checked, MapX starting prices were not very cheap however, maybe you can find an open source or cheaper engine to run in the background. (UMN MapServer?).

Eric

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

Sorry I forgot to reply earlier.

This actually came up at a job site a couple weeks ago, a person started to describe it so I said "yes of course the ray algorithm" having read your post. I actually have C code for it although I won't pretend to understand how it all works yet..

To answer your question - yes I think it would be a terrific topic for an article, very practical for MapPoint developers.

Eric

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

I know at least from experience, a lot of times lat/lon are converted to UTM zones for calculations, that might be an approach.

Eric