Algoritmo del punto en un polígono en PHP

El algoritmo del punto en un polígono permite comprobar mediante programación si un punto está dentro de un polígono o fuera de ello. Una forma común de abordar el problema es contar cuántas veces una línea trazada desde el punto (en cualquier dirección) se cruza con el borde del polígono. Si lo cruza un número par de veces (o ninguna), entonces el punto está fuera. Si lo cruza un número impar de veces, el punto está dentro. Funciona incluso para formas complejas que tienen muchas coordenadas y por lo tanto crean borde muy detallado.

Veamos un ejemplo antes de pasar al código.

Esta figura demuestra cómo se puede comprobar si un punto está dentro o fuera de un polígono.Aquí, las líneas trazadas desde el punto 1 cruzan el borde 2 veces o ninguna, porque el punto está afuera.

El punto 2 se encuentra adentro y por lo tanto, las líneas trazadas desde este punto y el polígntienen una o tres intersecciones.

Incluso en casos especiales, como el punto 3, podemos ver que funciona: la línea cruza el borde del polígono dos veces y, entonces, está afuera.

Uso este método en el código PHP de abajo, que devuelve uno de estos 4 posibles valores:

  • inside (= adentro) si el punto está dentro del polígono.
  • outside (= afuera) si el punto está fuera del polígono.
  • vertex (= vértice) si el punto se encuentra exactamente en un vértice Y $pointOnVertex = true (line 2)
  • boundary (= borde) si el punto está en un segmento. Si $pointOnVertex = false, entonces también se devolverá boundary si el punto se encuentra en un vértice.

Uso del código PHP del punto en un polígono

Establezca los valores del o de los punto(s) y una matriz que contenga los vértices del polígono (en la forma “coordenadaX coordenadaY”), y luego llame la función pointInPolygon. Las primeras y últimas coordenadas del polígono deben ser idénticas, para “cerrar el círculo”.

Como se puede ver en el siguiente ejemplo, es fácil comprobar varios puntos a la vez. El código también funciona con coordenadas negativas, tanto para las vértices del polígono como para los puntos que haya que comprobar.

Ejemplo del punto en un polígonoEsto dará por resultado:

point 1 (50 70): vertex (= vértice)
point 2 (70 40): inside (= adentro)
point 3 (-20 30): inside (= adentro)
point 4 (100 10): outside (= afuera)
point 5 (-10 -10): outside (= afuera)
point 6 (40 -20): inside (= adentro)
point 7 (110 -20): boundary (= borde)

35 pensamientos en “Algoritmo del punto en un polígono en PHP

    1. Michael Autor

      Yo escribí este código. ¡Muchas gracias por tu comentario!


      If you find this script useful, please consider making a donation to show me your appreciation; any amount will be welcome. Regardless, this script will always be available for free.
      Donate through PayPal

      Responder
      1. Pablo Lopez

        Michael, quiero consultarte si este código funcionará con puntos y poligonos en un plano de google maps. Tengo entendido que los puntos se definien en Mysql de tipo float(10,6). Un saludo y espero tu respuesta.

        Responder
        1. Michael Autor

          Hola Pablo,

          No lo hemos checado con datos de Google, pero debería de funcionar.
          Nunca hemos tenido problemas en nuestras pruebas con límites de países y coordenadas de nuestra propia base de datos worldCities (con formato DECIMAL(9,7) para la latitud y DECIMAL(10,7) para la longitud, pero la cantidad de decimales no afecta el funcionamiento del código).

          Saludos


          If you find this script useful, please consider making a donation to show me your appreciation; any amount will be welcome. Regardless, this script will always be available for free.
          Donate through PayPal

          Responder
          1. Pablo Lopez

            Michael, intenté con estos puntos de google:
            $pointLocation = new pointLocation();
            $points = array(“-27.787667 -64.259569”);
            $polygon = array(“-27.787586 -64.260427″,”-27.787012 -64.259467″, “-27.787795 -64.258663”, “-27.788464 -64.259816”, “-27.787586 -64.260427”);
            // Las últimas coordenadas tienen que ser las mismas que las primeras, para “cerrar el círculo”
            foreach($points as $key => $point) {
            echo “point ” . ($key+1) . ” ($point): ” . $pointLocation->pointInPolygon($point, $polygon) . “”;
            }

            El punto está dentro del polígono, pero cuando corro el script me dice que está afuera:

            point 1 (-27.787667 -64.259569): outside

            Qué puede estar fallando?. Desde ya muchas gracias por tu tiempo y tu actitud de ayudar.

          2. Michael Autor

            Hola Pablo,

            Me dí cuenta que no funcionaba tu ejemplo porque las coordenadas del punto estaban separadas por una tabulación en lugar de un espacio (aunque no se vea aquí en tu comentario). Al corregirlo, indica que está dentro del polígono. ¡Qué bueno que lo hayas podido resolver!

            Saludos


            If you find this script useful, please consider making a donation to show me your appreciation; any amount will be welcome. Regardless, this script will always be available for free.
            Donate through PayPal

          3. eduardo

            buen dia tengo una pregunta que como se yo cuando la interaccion de dos lineas en un poligonoi, donde si el punto es par esta afuera y si es impar esta dentro del poligono.

    1. Michael Autor

      Gracias Jose María. Que bueno que te sea útil.

      Saludos.


      If you find this script useful, please consider making a donation to show me your appreciation; any amount will be welcome. Regardless, this script will always be available for free.
      Donate through PayPal

      Responder
  1. Francisco

    La idea es excelente pero tu script esta mal llevado, te envio datos para que lo analices.

    $points = array(“50 50”);
    $polygon = array(“700 0″,”900 0″,”900 200″,”750 200″,”750 100”);

    Responder
    1. Michael Autor

      Hola,

      Como indicado en el artículo y el código de ejemplo, el último punto del polígono tiene que ser el mismo que el primero (para “cerrar el círculo”), así que tienes que hacer el cambio siguiente:
      $polygon = array(“700 0″,”900 0″,”900 200″,”750 200″,”750 100″,”700 0″);

      Así funciona perfectamente.

      Saludos


      If you find this script useful, please consider making a donation to show me your appreciation; any amount will be welcome. Regardless, this script will always be available for free.
      Donate through PayPal

      Responder
  2. carlos daniel

    Hey!! Muchas gracias por el aporte. Funciona perfecto… He estado tratando de adaptarlo para que acepte una precisión (por ejemplo 0.000391 (sobre todo para GPS que no son 100% precisos)).. donde se podría poner éste rango?

    Responder
  3. Cesar Baca

    Excelente, este algoritmo me ha salvado la vida..despues de pensarla mil y mil veces y luego comprobar y agregar mis parametros logro funcionar..mil gracias ya tengo una aplicacion de google maps con poligonos ufff me salvaste la vida, mil gracias bro , mis respectos!!

    Responder
    1. Michael Autor

      ¡Muchas gracias por tu comentario!


      If you find this script useful, please consider making a donation to show me your appreciation; any amount will be welcome. Regardless, this script will always be available for free.
      Donate through PayPal

      Responder
  4. Javi

    Buenísimo aporte, mis felicitaciones. Sólo aclarar que para su correcto funcionamiento los vértices del polígono deben darse por orden (parece una tontería pero me ha llevado 1 hora darme cuenta de por qué no me funcionaba), es decir, vértices correlativos siguiendo el perímetro. Yo los ponía sin orden y no me funcionaba 🙂

    Responder
    1. Michael Autor

      ¡Muchas gracias por tu comentario!
      Sí, claro, los puntos tienen que estar en el orden correcto para crear el poligono adecuado 😉
      Saludos


      If you find this script useful, please consider making a donation to show me your appreciation; any amount will be welcome. Regardless, this script will always be available for free.
      Donate through PayPal

      Responder
    1. Michael Autor

      Gracias a ti por tu comentario. Me da gusto que te sea útil.


      If you find this script useful, please consider making a donation to show me your appreciation; any amount will be welcome. Regardless, this script will always be available for free.
      Donate through PayPal

      Responder
  5. jhon jairo

    amigo buen codigo, pero dime que parte de la prueba estoy haciendo mal pls, porque aparte de no funcionar, se totea (se que esto es una publicacion vieja, pero se ve que puede ser muy util a la comunidad).

    $point) {
    echo “point ” . ($key+1) . ” ($point): ” . $pointLocation->pointInPolygon($point, $polygon) . “”;
    }
    ?>

    el error en concreto:

    point 1 (25.841767994251835 -80.28121936523439): outside

    Notice: Undefined offset: 1 in C:\xampp\htdocs\MYD\modulos\pruebaPOLYGON\pointLocation.php on line 77
    point 2 (25.91219693108349): outside

    el primer punto si esta fuera, pero el segundo deberia tomarlo como que esta adentro.

    Responder
    1. jhon jairo

      perdon perdon, jejejej ya vi el error, es que olvide colocar el valor de la longitud en el segundo punto XD!! fallo mio, muchas gracias amigo, estupenda solucion.

      Responder
      1. Michael Autor

        Qué bueno que hayas encontrado tu error.
        Saludos


        If you find this script useful, please consider making a donation to show me your appreciation; any amount will be welcome. Regardless, this script will always be available for free.
        Donate through PayPal

        Responder
    1. Michael Autor

      ¡Gracias por tu comentario, Marcelo!


      If you find this script useful, please consider making a donation to show me your appreciation; any amount will be welcome. Regardless, this script will always be available for free.
      Donate through PayPal

      Responder
    1. Michael Autor

      ¡Gracias por tu comentario, Miguel!


      If you find this script useful, please consider making a donation to show me your appreciation; any amount will be welcome. Regardless, this script will always be available for free.
      Donate through PayPal

      Responder
  6. José María

    Hola Michael gran trabajo. Me encuentro con una duda. Si creas un array con coordenadas de varios polígonos, el primero de los polígonos no encuentra que el punto esté dentro (cuando lo está realmente), pero por ejemplo otros puntos que están en otros polígonos, sí que los encuentra acertadamente.

    Este es el ejemplo:
    Array ( [0] => 37.364358914717755 -5.989565849304199 [1] => 37.36858828480959 -5.9893083572387695 [2] => 37.36892935265444 -5.9857892990112305 [3] => 37.3615619422531 -5.985960960388184 [4] => 37.363813172179285 -5.989136695861816 [5] => 37.38147957088128 -5.985403060913086 [6] => 37.39307301476918 -5.968408584594727 [7] => 37.382570794963435 -5.953130722045898 [8] => 37.376841691380825 -5.971841812133789 [9] => 37.37629603964236 -5.985231399536133 [10] => 37.375341139548176 -5.952787399291992 [11] => 37.38093395288545 -5.950899124145508 [12] => 37.3791606669827 -5.940771102905273 [13] => 37.37124857287921 -5.943517684936523 [14] => 37.360265748932 -5.9824419021606445 [15] => 37.36476821901685 -5.9783220291137695 [16] => 37.360129306227435 -5.9706830978393555 [17] => 37.3569228312597 -5.9761762619018555 [18] => 37.364358914717755 -5.989565849304199 )

    latitud= 37.365560065882455
    longitud= -5.987659377909836

    Esa coordenada dice que está fuera, cuando está dentro. Y la coordenada primera del array es igual a la última.

    ¿Es porque está pensado solo para un solo polígono y no admite varios?. Si fuese así, lo raro es que con otras coordenadas de los 4 polígonos que forma este array, detecta perfectamente el resto tanto los que están dentro como los que no lo están.

    Muchas gracias y enhorabuena por tu trabajo y por compartirlo.

    Responder
    1. Michael Autor

      Hoal José María,
      Gracias por tu comentario!
      Sí, tienes que poner las coordenadas de un solo polígono en el array, ya que como lo haces, no hay manera de saber cuales coordenadas pertenecen a cual polígono. Entonces, tienes que iniciar el script tantas veces como tengas polígonos (y puntos). Supongo que si funciona en algunos casos poniendo todo junto, es por simple casualidad 😉
      Saludos,
      Michaël


      If you find this script useful, please consider making a donation to show me your appreciation; any amount will be welcome. Regardless, this script will always be available for free.
      Donate through PayPal

      Responder

Leave a comment