5

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?

Spektre
  • 49,595
  • 11
  • 110
  • 380
TWT
  • 2,511
  • 1
  • 23
  • 37
  • 4
    https://en.wikipedia.org/wiki/Point_in_polygon – Paul Ruane Oct 17 '13 at 10:00
  • If you've got a polygon that lies across `+/- 180` just offset all longitudes by `+180`. Whether or not the point is inside the polygon will not be affected by such a transformation. You don't even need to test the position of the polygon and offset if it lies awkwardly, you could make the transformation for all tests – High Performance Mark Oct 17 '13 at 10:40
  • 1
    A polygon on the surface of a sphere divides it into two areas. How do you decide which area is the "inside" and which one is the "outside"? (On a plane this is easy: the infinite one is the outside) – RBarryYoung Oct 19 '13 at 00:18
  • 1
    Please, correct the image. It won't work. – Gangnus Jan 13 '14 at 16:15

1 Answers1

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

    is point inside polygon?

[Notes]

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

Community
  • 1
  • 1
Spektre
  • 49,595
  • 11
  • 110
  • 380