多边形内的点 PHP 错误

Question

我在 php 中使用多边形内的点检查，但出现了重大错误 - 因为不在多边形内的点出现在内部。

我的基本函数如下（在此处找到，从类修改为简单函数： http:// /www.assemblesys.com/dataServices/php_pointinpolygon.php）。我唯一能想到的是某处存在某种舍入错误？

举一个例子，我试图确定一个点是否在中央公园（一个简单的广场）内，但我从公园外的点得到了积极的结果。

感谢您的任何见解，

-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

原始代码存在几个问题，关闭多边形修复了其中一个问题，但该代码也为多边形边界线上的点给出了错误的结果。仅当点不在边界上时才需要执行 isWithinBoundary 函数末尾的 if..else 语句。由于边界上的点实际上不会与边界相交，因此边界点的相交计数始终为奇数，这意味着最终的 IF 语句对于边界点始终返回 FALSE。

我对代码做了一些调整，这个版本是一个独立的页面，有一些简单的测试数据，它输出正在做出的决定。

<?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;
    }
?>

您现在可能已经自己发现并修复了这些问题，但这可能会帮助其他找到并使用此代码的人。

Answer 2

好吧，我再次发现自己愚蠢地回答了自己愚蠢的问题。

我没有通过将第一个坐标附加到数组中的最后一个点来关闭多边形。这导致了不匹配点的非常独特的外观 - 它们似乎都从无界端溢出多边形。

所以这个 -

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

应该是这个 -

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

这就是我今天的愚蠢之处。谢谢。

Answer 3

您的代码的问题是变量 $result 被此代码覆盖，

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

即使 $result == TRUE 在这里：

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

在原始代码中，有一个“return”，它是正确的，而不是您的错误。