PHP: detect Point in Polygon


PHP function to detect Point in Polygon:

function contains($point, $polygon)
{
    if($polygon[0] != $polygon[count($polygon)-1])
        $polygon[count($polygon)] = $polygon[0];
    $j = 0;
    $oddNodes = false;
    $x = $point[1];
    $y = $point[0];
    $n = count($polygon);
    for ($i = 0; $i < $n; $i++)
    {
        $j++;
        if ($j == $n)
        {
            $j = 0;
        }
        if ((($polygon[$i][0] < $y) && ($polygon[$j][0] >= $y)) || (($polygon[$j][0] < $y) && ($polygon[$i][0] >=
            $y)))
        {
            if ($polygon[$i][1] + ($y - $polygon[$i][0]) / ($polygon[$j][0] - $polygon[$i][0]) * ($polygon[$j][1] -
                $polygon[$i][1]) < $x)
            {
                $oddNodes = !$oddNodes;
            }
        }
    }
    return $oddNodes;
}

Test for convex polygon:

point in convex polygon

$polygon = array(
    array(0,0),
    array(0,5),
    array(4,3),
    array(3,0),
    array(0,0),
);

$point1 = array(3,3);

echo contains($point1,$polygon)?'IN':'OUT';
echo "<br />";

$point2 = array(4,4);

echo contains($point2,$polygon)?'IN':'OUT';

Result:
IN
OUT

Test for concave polygon:
concave polygon

$polygon = array(
    array(0,0),
    array(0,5),
    array(2,2),
    array(4,3),
    array(4,0),
    array(2,1),
    array(0,0),
);
 
$point1 = array(1,4);
 
echo contains($point1,$polygon)?'IN':'OUT';
echo "<br />";
 
$point2 = array(3,2);
 
echo contains($point2,$polygon)?'IN':'OUT';
echo "<br />";
 
$point3 = array(2,0.5);
 
echo contains($point3,$polygon)?'IN':'OUT';

Result:
OUT
IN
OUT

Note: we only apply this method for simple polygon (non-self-intersecting polygon).

Test for complex polygon (self-intersecting polygon)

self-intersecting polygon

$polygon = array(
    array(0,5),
    array(3,5),
    array(3,0),
    array(4,3),
    array(0,5),
);
 
$point1 = array(1,4);
 
echo contains($point1,$polygon)?'IN':'OUT';
echo "<br />";
 
$point2 = array(3,2);
 
echo contains($point2,$polygon)?'IN':'OUT';
echo "<br />";
 
$point3 = array(2,0.5);
 
echo contains($point3,$polygon)?'IN':'OUT';

Result:
OUT
OUT
OUT

Error for point 2.

Related Post

, , ,

No comments yet.

Leave a Reply