Detect if geolocation is in complex polygon or not

Question

We are currently using the following algorithm to detect if a geographic point is inside a complex polygon or not. This works fine, except when the polygon crosses the 180° longitude line.

For example the point (-170, 60) is not detected in polygon 160,65,0 160,15,0 -160,15,0 -160,65,0 160,65,0

Look at the following image: [Img]http://tinypic.com/r/14x2xl1[/img] I want everything in the red box. Not the yellow box!

    public static bool IsCoordinateInPolygon(IList<KMLCoordinate> polygon, KMLCoordinate testPoint)
    {

        bool result = false;
        int j = polygon.Count - 1;
        for (int i = 0; i < polygon.Count; i++)
        {
            if (polygon[i].Latitude < testPoint.Latitude && polygon[j].Latitude >= testPoint.Latitude || polygon[j].Latitude < testPoint.Latitude && polygon[i].Latitude >= testPoint.Latitude)
            {
                if (polygon[i].Longitude + (testPoint.Latitude - polygon[i].Latitude) / (polygon[j].Latitude - polygon[i].Latitude) * (polygon[j].Longitude - polygon[i].Longitude) < testPoint.Longitude)
                {
                    result = !result;
                }
            }
            j = i;
        }
        return result;

    }

Does anybody have a better algorithm?

Answer 1

Spheric coordinate system has it quirks

To avoid them use 3D orthogonal/orthonormal cartesian coordinate system instead

1. convert your polygon vertexes and geolocation

   so (long,lat,alt) -> (x,y,z). here you find how to do it. You do not need to apply local transform just the first spheric to 3D cartesian transformation (bullet #1.)

2. use any inside polygon test ...

   I usually count the number of intersections between line cast from your geolocation to any direction and polygon boundary lines.

   • if it is odd then point is inside
   • if it is even then the point is outside
   • if point lies on any line of polygon then it is inside
   • if your casted line hits any vertex then either take in mind (do not count multiple hits at this vertex) or change the direction a bit and try again

   

[Notes]

Do not forget to handle all as 3D vectors not 2D !!!