Check if coordinates are inside a KML polygon

Question

I have a KML file which defines a region (or polygon). I would like to make a function that checks if a given coordinate is inside or outside that polygon.

This is the KML if you want to take a look: http://pastebin.com/LGfn3L8H

I don't want to show any map, I just want to return a boolean.

Answer 1

Point-in-polygon (PiP) is a very well-studied computational geometry problem, so there are lots of algorithms and implementations out there that you can use. Searching SO will probably find several you can copy-paste, even.

There's a catch, though—you're dealing with polygons on the surface of the Earth... which is a sphere, not the infinite Euclidean plane that most PiP algorithms expect to work with. (You can, for example, have triangles whose internal angles add up to greater than π radians.) So naively deploying a PiP algorithm will give you incorrect answers for edge cases.

It's probably easiest to use a library that can account for differences between Euclidean and spherical (or, more precisely, Earth-shaped) geometry—that is, a mapping library like MapKit. There are tricks like the one in this SO answer that let you convert a MKPolygon to a CGPath through map projection, after which you can use the CGPathContainsPoint function to test against the flat 2D polygon corresponding to your Earth-surface polygon.

Of course, to do that you'll also need to get your KML file imported to MapKit. Apple has a sample code project illustrating how to do this.

Answer 2

This can be done with GMSGeometryContainsLocation.

I wrote a method that makes use of the GoogleMapsUtils library's GMUKMLParser.

func findPolygonName(_ location: CLLocationCoordinate2D) {
    var name: String?
outerLoop: for placemark in kmlParser.placemarks {
    if let polygon = (placemark as? GMUPlacemark)?.geometry as? GMUPolygon {
        for path in polygon.paths {
            if GMSGeometryContainsLocation(location, path, true) {
                name = (placemark as? GMUPlacemark)?.title
                break outerLoop
            }
        }
    }
}
    if let n = name, !n.isEmpty {
        locationLabel.text = n
    } else {
        locationLabel.text = "We do not deliver here"
    }
}

This function iterates over the polygon and its path to determine whether the given coordinates are within the path.