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.

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?

bcdan · Accepted Answer · 2015-06-10T11:00:18.150

0

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.

edited Jun 10 '15 at 11:00

answered Jun 10 '15 at 01:20

bcdan

1,438
1
12
25

I'm not sure how to determine if the polygon is shaded or not. The polygons I'm passing into the `pointInPolygon` function are all shaded, the point that I'm passing into `$lat` and `$lng` are not in any polygon. – Alex Neises Jun 10 '15 at 01:28
OK. The polygon of the storm or whatever in the picture is made up of multiple loops. You must know which are regular and which are inverted (the shading inside). You only need to know the outermost boundary (you will need to find this out), then you can assume that the others are inside, and therefore inverted. If the point is inside the outer boundary, but not the inner boundaries, the point is true. – bcdan Jun 10 '15 at 01:32
Just had an idea to find loop status – bcdan Jun 10 '15 at 01:41
The loops do not cross themselves, you can see the current KML [here](http://www.spc.noaa.gov/products/outlook/day1otlk_cat.kml). – Alex Neises Jun 10 '15 at 01:49
Then my idea of comparing polyline points being inside other polylines will work. After that, you can implement my original solution. – bcdan Jun 10 '15 at 01:55
That's what I figured. After looking into the polygons, this problem only occurs when the polygon is inverted, and in my project, these areas are not what I'm focusing on. I will work on implementing your solution tomorrow, but this is what I was looking for. Thank you for your quick reply and great help. – Alex Neises Jun 10 '15 at 01:58

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

1 Answers1