tag - Encontrar Punto en el polígono PHP

strip_tags()

Question

Tengo una pregunta típica con el tipo de datos geométrico de mysql, polígono.

Tengo los datos de polígonos, en forma de un conjunto de latitudes y longitudes, por ejemplo:

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

Y tengo un punto (Vértice) con coordenadas de latitud y longitud, ej:

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

Ahora quiero saber si este vértice (punto) está dentro del polígono. ¿Cómo puedo hacer esto en PHP?

Answer 1

Aquí hay un posible algoritmo.

1. Defina un nuevo sistema de coordenadas con su punto de interés en el centro.
2. En su nuevo sistema de coordenadas, convierta todos sus vértices de polígonos en coordenadas polares.
3. Recorra el polígono, siguiendo el cambio neto en el ángulo, angle. Utilice siempre el valor más pequeño posible para cada cambio de ángulo.
4. Si, una vez que has atravesado el polígono, tu ∆θ total es 0, entonces estás fuera del polígono. Por otro lado, si es ± 2π, entonces estás dentro.
5. Si, por casualidad, ∆θ> 2π o ∆θ <-2π, eso significa que tienes un polígono que se duplica sobre sí mismo.

Escribir el código se deja como ejercicio. :)

Answer 2

Esta es una función que he convertido de otro lenguaje a 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;
}

Adicional: Para obtener más funciones, le aconsejo que use la clase polygon.php disponible aquí . Cree la clase utilizando sus vértices y llame a la función isInside con su punto de prueba como entrada para que otra función resuelva su problema.

Answer 3

He creado código en php codeigniter, en mi controlador he creado dos funciones como las siguientes

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

Otra función para verificar el lat-lng está abajo.

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

Para su propósito de prueba pasé debajo de las cosas

latitud = 22.808059

longitud = 77.522014

Mi poligono

Answer 4

La respuesta popular anterior contiene errores tipográficos. Por otra parte, este código ha sido limpiado. El código corregido es el siguiente:

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

Answer 5

Si sus polígonos se cierran automáticamente, es decir, su vértice final es la línea entre su último punto y su primer punto, entonces debe agregar una variable y una condición a su bucle para tratar el vértice final. También debe pasar el número de vértices como igual al número de puntos.

Aquí está la respuesta aceptada modificada para tratar con los polígonos de cierre automático:

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

¡Gracias! Encontré esta página y su respuesta aceptada es muy útil y me enorgullece ofrecer esta variación.