Ошибка PHP в Point-in-Polygon

Question

Я использую проверку точки в многоугольнике в php, но я получаю серьезные ошибки - как в точках, которые не в многоугольнике, появляются как внутри.

Мои основные функции набраныниже (найденный здесь, измененный из класса в простую функцию: http://www.assemblysys.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

Было несколько проблем с исходным кодом, закрытие полигонов исправило одну из них, но код также дал неверные результаты для точек на границах многоугольника.Оператор if..else в конце функции isWithinBoundary должен выполняться только в том случае, если точка НЕ ​​находится на границе.Поскольку точка на границе фактически не пересекает границу, то количество пересечений всегда будет нечетным для граничной точки, а это означает, что этот последний оператор 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;
}

В исходном кодебыло «возвращение», которое было правильным, а вы - неправильным.