Найти точку в полигоне PHP

У меня типичный вопрос с геометрическим типом данных mysql, polygon.

У меня есть многоугольные данные в виде массива широт и долгот, например:

[["x":37.628134, "y":-77.458334], ["x":37.629867, "y":-77.449021], ["x":37.62324, "y":-77.445416], ["x":37.622424, "y":-77.457819]]

И у меня есть точка (Vertex) с координатами широты и долготы, например:

 $location = new vertex($_GET["longitude"], $_GET["latitude"]);

Теперь я хочу найти, находится ли эта вершина (точка) внутри многоугольника. Как я могу это сделать в php?

Это функция, преобразованная из другого языка в PHP:

 $vertices_x = array(37.628134, 37.629867, 37.62324, 37.622424); // x-coordinates of the vertices of the polygon $vertices_y = array(-77.458334,-77.449021,-77.445416,-77.457819); // y-coordinates of the vertices of the polygon $points_polygon = count($vertices_x) - 1; // number vertices - zero-based array $longitude_x = $_GET["longitude"]; // x-coordinate of the point to test $latitude_y = $_GET["latitude"]; // y-coordinate of the point to test if (is_in_polygon($points_polygon, $vertices_x, $vertices_y, $longitude_x, $latitude_y)){ echo "Is in polygon!"; } else echo "Is not in polygon"; function is_in_polygon($points_polygon, $vertices_x, $vertices_y, $longitude_x, $latitude_y) { $i = $j = $c = 0; for ($i = 0, $j = $points_polygon ; $i < $points_polygon; $j = $i++) { if ( (($vertices_y[$i] > $latitude_y != ($vertices_y[$j] > $latitude_y)) && ($longitude_x < ($vertices_x[$j] - $vertices_x[$i]) * ($latitude_y - $vertices_y[$i]) / ($vertices_y[$j] - $vertices_y[$i]) + $vertices_x[$i]) ) ) $c = !$c; } return $c; }

Дополнительно: Для получения дополнительных функций я советую вам использовать класс polygon.php, доступный здесь . Создайте класс, используя ваши вершины, и вызовите функцию isInside с вашей isInside качестве входной информации, чтобы иметь другую функцию, isInside вашу проблему.

Популярный ответ выше содержит опечатки. В другом месте этот код был очищен. Исправленный код выглядит следующим образом:

 <?php /** From: http://www.daniweb.com/web-development/php/threads/366489 Also see http://en.wikipedia.org/wiki/Point_in_polygon */ $vertices_x = array(37.628134, 37.629867, 37.62324, 37.622424); // x-coordinates of the vertices of the polygon $vertices_y = array(-77.458334,-77.449021,-77.445416,-77.457819); // y-coordinates of the vertices of the polygon $points_polygon = count($vertices_x); // number vertices $longitude_x = $_GET["longitude"]; // x-coordinate of the point to test $latitude_y = $_GET["latitude"]; // y-coordinate of the point to test //// For testing. This point lies inside the test polygon. // $longitude_x = 37.62850; // $latitude_y = -77.4499; if (is_in_polygon($points_polygon, $vertices_x, $vertices_y, $longitude_x, $latitude_y)){ echo "Is in polygon!"; } else echo "Is not in polygon"; function is_in_polygon($points_polygon, $vertices_x, $vertices_y, $longitude_x, $latitude_y) { $i = $j = $c = 0; for ($i = 0, $j = $points_polygon-1 ; $i < $points_polygon; $j = $i++) { if ( (($vertices_y[$i] > $latitude_y != ($vertices_y[$j] > $latitude_y)) && ($longitude_x < ($vertices_x[$j] - $vertices_x[$i]) * ($latitude_y - $vertices_y[$i]) / ($vertices_y[$j] - $vertices_y[$i]) + $vertices_x[$i]) ) ) $c = !$c; } return $c; } ?>

Вот возможный алгоритм.

Определите новую систему координат с вашей точкой интереса в центре.
В вашей новой системе координат преобразуйте все ваши вершины многоугольника в полярные координаты.
Пройдите по многоугольнику, отслеживая чистое изменение угла, Δθ. Всегда используйте наименьшее возможное значение для каждого изменения угла.
Если после прохождения многоугольника ваше полное Δθ равно 0, вы находитесь за пределами полигона. С другой стороны, если это ± 2π, то вы внутри.
Если, случайно, Δθ> 2π или Δθ <-2π, это означает, что у вас есть многоугольник, который удваивается обратно на себя.

Написание кода остается как упражнение. 🙂

Если ваши многоугольники самозакрываются, то есть конечная вершина – это линия между последней точкой и первой точкой, тогда вам нужно добавить переменную и условие в ваш цикл, чтобы иметь дело с конечной вершиной. Вам также необходимо передать количество вершин равным количеству точек.

Вот принятый ответ, измененный для обработки самозакрывающихся полигонов:

 $vertices_x = array(37.628134, 37.629867, 37.62324, 37.622424); // x-coordinates of the vertices of the polygon $vertices_y = array(-77.458334,-77.449021,-77.445416,-77.457819); // y-coordinates of the vertices of the polygon $points_polygon = count($vertices_x); // number vertices = number of points in a self-closing polygon $longitude_x = $_GET["longitude"]; // x-coordinate of the point to test $latitude_y = $_GET["latitude"]; // y-coordinate of the point to test if (is_in_polygon($points_polygon, $vertices_x, $vertices_y, $longitude_x, $latitude_y)){ echo "Is in polygon!"; } else echo "Is not in polygon"; function is_in_polygon($points_polygon, $vertices_x, $vertices_y, $longitude_x, $latitude_y) { $i = $j = $c = $point = 0; for ($i = 0, $j = $points_polygon ; $i < $points_polygon; $j = $i++) { $point = $i; if( $point == $points_polygon ) $point = 0; if ( (($vertices_y[$point] > $latitude_y != ($vertices_y[$j] > $latitude_y)) && ($longitude_x < ($vertices_x[$j] - $vertices_x[$point]) * ($latitude_y - $vertices_y[$point]) / ($vertices_y[$j] - $vertices_y[$point]) + $vertices_x[$point]) ) ) $c = !$c; } return $c; }

Спасибо! Я нашел эту страницу, и ее принятый ответ очень полезен, и я с гордостью предлагаю этот вариант.