Finding if lat/long point is inside a polygon defined by coordinates

Question

I am currently grabbing the KML used to define the polygons seen here.

I am using the algorithm detailed in this answer to determine if the point is inside the polygon.

The problem I have though is if the point is inside an empty part of the polygon, as seen below.

Click to see the image!

If I pass the coordinates of Indianapolis (shown by the arrow), the algorithm still says that the point is inside the light green polygon, which is false.

When I pass in the coordinates for Indianapolis using the KML defining the image above, these are the results.

string(22) "39.7774501,-86.1090119" 39.7774501,-86.1090119 is outside Marginal Risk
string(22) "39.7774501,-86.1090119" 39.7774501,-86.1090119 is outside Marginal Risk
string(22) "39.7774501,-86.1090119" 39.7774501,-86.1090119 is outside Slight Risk
string(22) "39.7774501,-86.1090119" 39.7774501,-86.1090119 is outside Marginal Risk
string(22) "39.7774501,-86.1090119" 39.7774501,-86.1090119 is outside Marginal Risk
string(22) "39.7774501,-86.1090119" 39.7774501,-86.1090119 is outside Marginal Risk
string(22) "39.7774501,-86.1090119" 39.7774501,-86.1090119 is outside Marginal Risk
string(22) "39.7774501,-86.1090119" 39.7774501,-86.1090119 is outside Marginal Risk
string(22) "39.7774501,-86.1090119" 39.7774501,-86.1090119 is outside Marginal Risk
string(22) "39.7774501,-86.1090119" 39.7774501,-86.1090119 is outside Marginal Risk
string(22) "39.7774501,-86.1090119" 39.7774501,-86.1090119 is outside Marginal Risk
string(22) "39.7774501,-86.1090119" 39.7774501,-86.1090119 is outside Marginal Risk
string(22) "39.7774501,-86.1090119" 39.7774501,-86.1090119 is outside Slight Risk
string(22) "39.7774501,-86.1090119" 39.7774501,-86.1090119 is outside Marginal Risk
string(22) "39.7774501,-86.1090119" 39.7774501,-86.1090119 is outside Marginal Risk
string(22) "39.7774501,-86.1090119" 39.7774501,-86.1090119 is inside General Thunder

Does anybody have an idea on how I can modify the algorithm to work correctly?

Answer 1

The point is inside the green boundaries, but you just want to override that with another polygon.

Assuming that you have multiple polygons, it might be worth keeping track of whether the polygons are shaded (True) or not shaded (False), or some other combination based on what your algorithm actually does.

Pass the shading status as an argument in the test and pointInPolygon functions (something like function test($lat, $lng, $shaded)) and invert the output of pointInPolygon if $shaded is False.

function pointInPolygon($p, $polygon, $shaded) {
    //if you operates with (hundred)thousands of points
    //rest of code
    $output = $c%2!=0;
    if (!$shaded) { //if the area is not shaded, negate the output
        return !$output;
    } else {
        return $output;
    }
}

To find the outside loop, make an array of polygons, and iterate through, checking all combinations, of which is inside which (using the algorithm you already have). Checking one point from one into the full other polygon should work. The polygon that is never inside the others will be the outside loop (shaded). All the others are inside, and inverted and not shaded.

Of course, this is assuming that the loops never cross themselves.

You will need to test the point in all the polylines using the algorithm. If it is within the external loop, and not inside any inside loops, it is shaded; if it is within the external loop, and inside an inside loop, it is not shaded.