Point-in-Polygon PHP Errors

Question

I am using a point-in-polygon check in php, but I am getting major errors - as in points that are not in the polygon are coming up as inside.

My basic functions are typed out below (found here, modified from a class to a simple function: http://www.assemblysys.com/dataServices/php_pointinpolygon.php). The only thing I can think of is some kind of rounding errors someplace?

As one example, I am trying to determine whether a point is in Central Park, a simple square, but I get positives from points outside the park.

Thanks for any insight,

-D

$central_park = array('40.768109,-73.981885', '40.800636,-73.958067', '40.796900,-73.949184', '40.764307,-73.972959');

$test_points = array('40.7546755,-73.9758343', '40.764405,-73.973951', '40.7594219,-73.9733896', '40.768137896318315,-73.9814176061', '40.7982394,-73.9523718', '40.685135,-73.973562', '40.7777062,-73.9632719', '40.764109,-73.975948', '40.758908,-73.9813128', '40.7982782,-73.9525028', '40.7463886,-73.9817654', '40.7514592,-73.9760405', '40.7514592,-73.9760155', '40.7514592,-73.9759905', '40.7995079,-73.955431', '40.7604354,-73.9758778', '40.7642878,-73.9730075', '40.7655335,-73.9800484', '40.7521678,-73.9777978', '40.7521678,-73.9777728')

function pointStringToCoordinates($pointString) {
    $coordinates = explode(",", $pointString);
    return array("x" => trim($coordinates[0]), "y" => trim($coordinates[1]));
}

function isWithinBoundary($point,$polygon){

    $point = pointStringToCoordinates($point);

    $vertices = array();

    foreach ($polygon as $vertex) {
        $vertices[] = pointStringToCoordinates($vertex); 
    }

    // Check if the point is inside the polygon or on the boundary
    $intersections = 0; 
    $vertices_count = count($vertices);

    for ($i=1; $i < $vertices_count; $i++) {

        $vertex1 = $vertices[$i-1]; 
        $vertex2 = $vertices[$i];

        if ($vertex1['y'] == $vertex2['y'] and $vertex1['y'] == $point['y'] and $point['x'] > min($vertex1['x'], $vertex2['x']) and $point['x'] < max($vertex1['x'], $vertex2['x'])) { // Check if point is on an horizontal polygon boundary
            $result = TRUE;
        }

        if ($point['y'] > min($vertex1['y'], $vertex2['y']) and $point['y'] <= max($vertex1['y'], $vertex2['y']) and $point['x'] <= max($vertex1['x'], $vertex2['x']) and $vertex1['y'] != $vertex2['y']) { 

            $xinters = ($point['y'] - $vertex1['y']) * ($vertex2['x'] - $vertex1['x']) / ($vertex2['y'] - $vertex1['y']) + $vertex1['x']; 

            if ($xinters == $point['x']) { // Check if point is on the polygon boundary (other than horizontal)
                $result = TRUE;
            }

            if ($vertex1['x'] == $vertex2['x'] || $point['x'] <= $xinters) {
                $intersections++; 
            }

        } 

    }

    // If the number of edges we passed through is even, then it's in the polygon. 
    if ($intersections % 2 != 0) {
        $result = TRUE;
    } else {
        $result = FALSE;
    }

    return $result;

}

Answer 1

There were a couple of problems with the original code, closing the polygons fixed one of these but the code also gave incorrect results for points on the boundary lines of the polygon. The if..else statement at the end of the isWithinBoundary function only needs to be executed if a point IS NOT on a boundary. As a point on the boundary won't actually intersect the boundary then the count of intersections would always be odd for a boundary point meaning that this final IF statement would always return FALSE for a boundary point.

I have tweaked the code a little, this version is a self contained page that has some simple test data and it outputs the decisions being made.

<?php
    $myPolygon = array('4,3', '4,6', '7,6', '7,3','4,3');

    $test_points = array('0,0','1,1','2,2','3,3','3.99999,3.99999','4,4','5,5','6,6','6.99999,5.99999','7,7');
    echo "The test polygon has the co-ordinates ";
    foreach ($myPolygon as $polypoint){
        echo $polypoint.", ";
    }
    echo "<br/>"; 
    foreach ($test_points as $apoint)
    {
        echo "Point ".$apoint." is ";
        if (!isWithinBoundary($apoint,$myPolygon))
        {
            echo " NOT ";
        }
        echo "inside the test polygon<br />";
    }

    function pointStringToCoordinates($pointString) 
    {
            $coordinates = explode(",", $pointString);
            return array("x" => trim($coordinates[0]), "y" => trim($coordinates[1]));
    }

    function isWithinBoundary($point,$polygon)
    {
        $result =FALSE;
        $point = pointStringToCoordinates($point);
        $vertices = array();
        foreach ($polygon as $vertex) 
        {
            $vertices[] = pointStringToCoordinates($vertex); 
        }
        // Check if the point is inside the polygon or on the boundary
        $intersections = 0; 
        $vertices_count = count($vertices);
        for ($i=1; $i < $vertices_count; $i++) 
        {
            $vertex1 = $vertices[$i-1]; 
            $vertex2 = $vertices[$i];
            if ($vertex1['y'] == $vertex2['y'] and $vertex1['y'] == $point['y'] and $point['x'] > min($vertex1['x'], $vertex2['x']) and $point['x'] < max($vertex1['x'], $vertex2['x'])) 
            { 
                // This point is on an horizontal polygon boundary
                $result = TRUE;
                // set $i = $vertices_count so that loop exits as we have a boundary point
                $i = $vertices_count;
            }
            if ($point['y'] > min($vertex1['y'], $vertex2['y']) and $point['y'] <= max($vertex1['y'], $vertex2['y']) and $point['x'] <= max($vertex1['x'], $vertex2['x']) and $vertex1['y'] != $vertex2['y']) 
            { 
                $xinters = ($point['y'] - $vertex1['y']) * ($vertex2['x'] - $vertex1['x']) / ($vertex2['y'] - $vertex1['y']) + $vertex1['x']; 
                if ($xinters == $point['x']) 
                { // This point is on the polygon boundary (other than horizontal)
                    $result = TRUE;
                    // set $i = $vertices_count so that loop exits as we have a boundary point
                    $i = $vertices_count;
                }
                if ($vertex1['x'] == $vertex2['x'] || $point['x'] <= $xinters) 
                {
                    $intersections++; 
                }
            } 
        }
        // If the number of edges we passed through is even, then it's in the polygon. 
        // Have to check here also to make sure that we haven't already determined that a point is on a boundary line
        if ($intersections % 2 != 0 && $result == FALSE) 
        {
            $result = TRUE;
        } 
        return $result;
    }
?>

You've probably spotted and fixed these problems yourself by now, but this might help other people who find and use this code.

Answer 2

Well, once again I find myself foolishly answering my own foolish question.

I was not closing the polygon by appending the first coordinate to the last spot in the array. This caused a very distinctive look of the mismatched points - they all appeared to be spilling out of the polygon from the unbounded end.

So this -

$central_park = array('40.768109,-73.981885', '40.800636,-73.958067', '40.796900,-73.949184', '40.764307,-73.972959');

Should be this -

$central_park = array('40.768109,-73.981885', '40.800636,-73.958067', '40.796900,-73.949184', '40.764307,-73.972959', '40.764307,-73.972959');

And that's how I was dumb today. Thank you.

Answer 3

The problem with your code is that the variable $result is overwritten by this code

if ($intersections % 2 != 0) {
    $result = TRUE;
} else {
    $result = FALSE;
}

even if $result == TRUE here:

if ($xinters == $point['x']) {
    $result = TRUE;
}

In the original code there was an 'return' which was correct instead of your is wrong.