Найти точку в многоугольнике PHP - PullRequest
Новая
       47

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

22 голосов
/ 21 февраля 2011

У меня типичный вопрос с геометрическим типом данных 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]]

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

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

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

Ответы [ 6 ]

41 голосов
/ 21 февраля 2011

Это функция, которую я преобразовал из другого языка в 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 с вашей контрольной точкой в ​​качестве входных данных, чтобы другая функция решала вашу проблему.

11 голосов
/ 15 мая 2012

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

<?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;
}
?>
2 голосов
/ 04 октября 2013

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

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

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

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

2 голосов
/ 21 февраля 2011

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

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

Написание кода оставлено в качестве упражнения.:)

1 голос
/ 14 марта 2019

Вышеупомянутое решение не работает, как я ожидаю, вместо использования вышеупомянутого решения вы можете предпочесть следующие решения

  1. с PHP 

    function pointInPolygon($point, $polygon, $pointOnVertex = true) {
    $this->pointOnVertex = $pointOnVertex;

    // Transform string coordinates into arrays with x and y values
    $point = $this->pointStringToCoordinates($point);
    $vertices = array(); 
    foreach ($polygon as $vertex) {
        $vertices[] = $this->pointStringToCoordinates($vertex); 
    }

    // Check if the lat lng sits exactly on a vertex
    if ($this->pointOnVertex == true and $this->pointOnVertex($point, $vertices) == true) {
        return "vertex";
    }

    // Check if the lat lng 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
            return "boundary";
        }
        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 lat lng is on the polygon boundary (other than horizontal)
                return "boundary";
            }
            if ($vertex1['x'] == $vertex2['x'] || $point['x'] <= $xinters) {
                $intersections++; 
            }
        } 
    } 
    // If the number of edges we passed through is odd, then it's in the polygon. 
    if ($intersections % 2 != 0) {
        return "inside";
    } else {
        return "outside";
    }
}

function pointOnVertex($point, $vertices) {
  foreach($vertices as $vertex) {
      if ($point == $vertex) {
          return true;
      }
  }

}

function pointStringToCoordinates($pointString) {
    $coordinates = explode(" ", $pointString);
    return array("x" => $coordinates[0], "y" => $coordinates[1]);
}
// Function to check lat lng
function check(){
    $points = array("22.367582 70.711816", "21.43567582 72.5811816","22.367582117085913 70.71181669186944","22.275334996986643 70.88614147123701","22.36934302329968 70.77627818998701"); // Array of latlng which you want to find
    $polygon = array(
        "22.367582117085913 70.71181669186944",
        "22.225161442616514 70.65582486840117",
        "22.20736264867434 70.83229276390898",
        "22.18701840565626 70.9867880031668",
        "22.22452581029355 71.0918447658621",
        "22.382709129816103 70.98884793969023",
        "22.40112042636022 70.94078275414336",
        "22.411912121843205 70.7849142238699",
        "22.367582117085913 70.71181669186944"
    );
    // The last lat lng must be the same as the first one's, to "close the loop"
    foreach($points as $key => $point) {
        echo "(Lat Lng) " . ($key+1) . " ($point): " . $this->pointInPolygon($point, $polygon) . "<br>";
    }
}

  2. С MySql 

CREATE TABLE `TestPoly` (
   `id` int(11) NOT NULL,
   `name` varchar(255) NOT NULL,
   `pol` polygon NOT NULL
 )

SET @g = 'POLYGON((22.367582117085913 70.71181669186944, 22.225161442616514 70.65582486840117, 22.20736264867434 70.83229276390898, 22.18701840565626 70.9867880031668, 22.22452581029355 71.0918447658621, 22.382709129816103 70.98884793969023, 22.40112042636022 70.94078275414336, 22.411912121843205 70.7849142238699, 22.367582117085913 70.71181669186944))';
INSERT INTO TestPoly (pol) VALUES (ST_GeomFromText(@g))

set @p = GeomFromText('POINT(22.4053386588057 70.86240663480157)');
select * FROM TestPoly where ST_Contains(pol, @p);
0 голосов
/ 05 марта 2019

Я создал код в php codeigniter, в моем контроллере я создал две функции, как показано ниже 

public function checkLatLng(){
    $vertices_y = array(22.774,22.174,22.466,22.666,22.966,22.321);    // x-coordinates of the vertices of the polygon (LATITUDES)
    $vertices_x = array(70.190,70.090,77.118,77.618,77.418,77.757); // y-coordinates of the vertices of the polygon (LONGITUDES)
    $points_polygon = count($vertices_x)-1; 
    $longitude_x = $this->input->get("longitude");  // Your Longitude
    $latitude_y = $this->input->get("latitude");    // Your Latitude
    if ($this->is_in_polygon($points_polygon, $vertices_x, $vertices_y, $longitude_x, $latitude_y)){
        echo "Is in polygon!";
    }
    else
        echo "Is not in polygon";
}

Еще одна функция для проверки широты ниже 

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

ДляВаша цель тестирования Я прошел ниже вещей

широта = 22.808059

долгота = 77.522014

Мой многоугольник

enter image description here

...