algorithm - applications - Esgrima Geo-punto dentro/fuera del polígono

"computational geometry an introduction"

Question

Me gustaría determinar un polígono e implementar un algoritmo que compruebe si un punto está dentro o fuera del polígono.

¿Alguien sabe si hay algún ejemplo disponible de algún algoritmo similar?

Answer 1

¡Agrego un detalle para ayudar a las personas que viven en el ... sur de la Tierra! Si estás en Brasil (ese es mi caso), nuestra coordenada de GPS son todas negativas. Y todos estos algo dan resultados equivocados.

La forma más fácil si se utilizan los valores absolutos de Lat y Long de todos los puntos. Y en ese caso, algo de Jan Kobersky es perfecto.

Answer 2

Compruebe si un punto está dentro de un polígono o no.

Considera el polígono que tiene vértices a1, a2, a3, a4, a5. El siguiente conjunto de pasos debería ayudar a determinar si el punto P está dentro o fuera del polígono.

Calcule el área vectorial del triángulo formado por el borde a1-> a2 y los vectores que conectan a2 a P y P a a1. De manera similar, calcule el área vectorial de cada uno de los triángulos posibles que tienen un lado como el lado del polígono y los otros dos P que se conectan a ese lado.

Para que un punto esté dentro de un polígono, cada uno de los triángulos debe tener un área positiva. Incluso si uno de los triángulos tiene un área negativa, entonces el punto P sobresale del polígono.

Para calcular el área de un triángulo, los vectores dados representan sus 3 bordes, consulte http://www.jtaylor1142001.net/calcjat/Solutions/VCrossProduct/VCPATriangle.htm

Answer 3

Con mucho, la mejor explicación e implementación se puede encontrar en Punto en Polígono Inclusión de números de liquidación

Incluso hay una implementación de C ++ al final del artículo bien explicado. Este sitio también contiene algunos algoritmos / soluciones excelentes para otros problemas basados ​​en geometría.

He modificado y usado la implementación de C ++ y también he creado una implementación de C #. Definitivamente desea utilizar el algoritmo de Número de Bobina ya que es más preciso que el algoritmo de cruce de borde y es muy rápido.

Answer 4

Creo que hay una solución más sencilla y eficiente.

Aquí está el código en C ++. Debería ser simple convertirlo a C #.

int pnpoly(int npol, float *xp, float *yp, float x, float y)
{
  int i, j, c = 0;
  for (i = 0, j = npol-1; i < npol; j = i++) {
    if ((((yp[i] <= y) && (y < yp[j])) ||
         ((yp[j] <= y) && (y < yp[i]))) &&
        (x < (xp[j] - xp[i]) * (y - yp[i]) / (yp[j] - yp[i]) + xp[i]))
      c = !c;
  }
  return c;
}

Answer 5

Después de buscar en la web y probar varias implementaciones y trasladarlas de C ++ a C #, finalmente obtuve mi código correcto:

        public static bool PointInPolygon(LatLong p, List<LatLong> poly)
    {
        int n = poly.Count();

        poly.Add(new LatLong { Lat = poly[0].Lat, Lon = poly[0].Lon });
        LatLong[] v = poly.ToArray();

        int wn = 0;    // the winding number counter

        // loop through all edges of the polygon
        for (int i = 0; i < n; i++)
        {   // edge from V[i] to V[i+1]
            if (v[i].Lat <= p.Lat)
            {         // start y <= P.y
                if (v[i + 1].Lat > p.Lat)      // an upward crossing
                    if (isLeft(v[i], v[i + 1], p) > 0)  // P left of edge
                        ++wn;            // have a valid up intersect
            }
            else
            {                       // start y > P.y (no test needed)
                if (v[i + 1].Lat <= p.Lat)     // a downward crossing
                    if (isLeft(v[i], v[i + 1], p) < 0)  // P right of edge
                        --wn;            // have a valid down intersect
            }
        }
        if (wn != 0)
            return true;
        else
            return false;

    }

    private static int isLeft(LatLong P0, LatLong P1, LatLong P2)
    {
        double calc = ((P1.Lon - P0.Lon) * (P2.Lat - P0.Lat)
                - (P2.Lon - P0.Lon) * (P1.Lat - P0.Lat));
        if (calc > 0)
            return 1;
        else if (calc < 0)
            return -1;
        else
            return 0;
    }

La función isLeft me estaba dando problemas de redondeo y pasé horas sin darme cuenta de que estaba haciendo la conversión incorrectamente, así que perdóname por el bloque de cojo al final de esa función.

Por cierto, este es el código y el artículo original: http://softsurfer.com/Archive/algorithm_0103/algorithm_0103.htm

Answer 6

El problema es más fácil si tu polígono es convexo. Si es así, puede hacer una prueba simple para cada línea para ver si el punto está dentro o fuera de esa línea (extendiéndose hasta el infinito en ambas direcciones). De lo contrario, para polígonos cóncavos, dibuje un rayo imaginario desde su punto al infinito (en cualquier dirección). Cuenta cuántas veces cruza una línea de límite. Impar significa que el punto está dentro, incluso significa que está fuera.

Este último algoritmo es más complicado de lo que parece. Tendrás que tener mucho cuidado con lo que sucede cuando tu rayo imaginario toque exactamente uno de los vértices del polígono.

Si su rayo imaginario va en la dirección -x, puede elegir solo contar las líneas que incluyen al menos un punto cuya coordenada y sea estrictamente menor que la coordenada y de su punto. Así es como consigues que la mayoría de los casos de borde extraño funcionen correctamente.

Answer 7

La solución completa en asp.Net C #, puede ver el detalle completo aquí, puede ver cómo encontrar el punto (lat, lon) si está dentro o fuera del polígono utilizando la latitud y las longitudes. Enlace de referencia del artículo

private static bool checkPointExistsInGeofencePolygon (string latlnglist, string lat, string lng) {

    List<Loc> objList = new List<Loc>();
    // sample string should be like this strlatlng = "39.11495,-76.873259|39.114588,-76.872808|39.112921,-76.870373|";
    string[] arr = latlnglist.Split(''|'');
    for (int i = 0; i <= arr.Length - 1; i++)
    {
        string latlng = arr[i];
        string[] arrlatlng = latlng.Split('','');

        Loc er = new Loc(Convert.ToDouble(arrlatlng[0]), Convert.ToDouble(arrlatlng[1]));
        objList.Add(er);
    }
    Loc pt = new Loc(Convert.ToDouble(lat), Convert.ToDouble(lng));

    if (IsPointInPolygon(objList, pt) == true)
    {
          return true;
    }
    else
    {
           return false;
    }
}
private static bool IsPointInPolygon(List<Loc> poly, Loc point)
{
    int i, j;
    bool c = false;
    for (i = 0, j = poly.Count - 1; i < poly.Count; j = i++)
    {
        if ((((poly[i].Lt <= point.Lt) && (point.Lt < poly[j].Lt)) |
            ((poly[j].Lt <= point.Lt) && (point.Lt < poly[i].Lt))) &&
            (point.Lg < (poly[j].Lg - poly[i].Lg) * (point.Lt - poly[i].Lt) / (poly[j].Lt - poly[i].Lt) + poly[i].Lg))
            c = !c;
    }
    return c;
}

Answer 8

Si recuerdo correctamente, el algoritmo es dibujar una línea horizontal a través de su punto de prueba. Cuenta cuántas líneas del polígono intersectas para alcanzar tu punto.

Si la respuesta es extraña, estás dentro. Si la respuesta es par, estás fuera.

Edit: Sí, lo he dijo ( Wikipedia ):

Answer 9

Si tiene un polígono simple (ninguna de las líneas se cruza) y no tiene orificios, también puede triangular el polígono, lo que probablemente va a hacer de todos modos en una aplicación GIS para dibujar un TIN y luego probar los puntos en cada triángulo. Si tiene un pequeño número de bordes en el polígono pero un gran número de puntos, esto es rápido.

Para un punto interesante en triángulo ver el texto del enlace

De lo contrario, definitivamente use la regla de enrollamiento en lugar del cruce de bordes, el cruce de bordes tiene problemas reales con los puntos en los bordes, lo cual es muy probable que si sus datos se generan desde un GPS con precisión limitada.

Answer 10

Solo eche un vistazo al problema de punto en polígono (PIP) .

Answer 11

Solo un aviso (usando la respuesta como no puedo comentar), si desea usar el punto en polígono para cercas geográficas, necesita cambiar su algoritmo para trabajar con coordenadas esféricas. La longitud -180 es la misma que la longitud 180 y el punto en el polígono se romperá en tal situación.

Answer 12

Traduje el método c # en PHP y agregué muchos comentarios para entender el código.

Descripción de PolygonHelps:
Compruebe si un punto está dentro o fuera de un polígono. Este procedimiento utiliza coordenadas gps y funciona cuando el polígono tiene un área geográfica pequeña.


ENTRADA:
$ poly: matriz de puntos: lista de vértices de polígonos; [{Punto}, {Punto}, ...];
$ punto: punto a verificar; Punto: {"lat" => "x.xxx", "lng" => "y.yyy"}


Cuando $ c es falso, el número de intersecciones con el polígono es par, por lo que el punto está fuera del polígono;
Cuando $ c es verdadero, el número de intersecciones con el polígono es impar, por lo que el punto está dentro del polígono;
$ n es el número de vértices en el polígono;
Para cada vértice en polígono, el método calcula la línea a través del vértice actual y el vértice anterior y verifica si las dos líneas tienen un punto de intersección.
$ c cambia cuando existe un punto de intersección.
Entonces, el método puede devolver verdadero si el punto está dentro del polígono, de lo contrario, devuelve falso.

class PolygonHelps {

    public static function isPointInPolygon(&$poly, $point){

        $c = false; 
        $n = $j = count($poly);


        for ($i = 0, $j = $n - 1; $i < $n; $j = $i++){

            if ( ( ( ( $poly[$i]->lat <= $point->lat ) && ( $point->lat < $poly[$j]->lat ) ) 
                || ( ( $poly[$j]->lat <= $point->lat ) && ( $point->lat < $poly[$i]->lat ) ) ) 

            && ( $point->lng <   ( $poly[$j]->lng - $poly[$i]->lng ) 
                               * ( $point->lat    - $poly[$i]->lat ) 
                               / ( $poly[$j]->lat - $poly[$i]->lat ) 
                               +   $poly[$i]->lng ) ){

                $c = !$c;
            }
        }

        return $c;
    }
}

Answer 13

el polígono se define como una lista secuencial de pares de puntos A, B, C ... A. ningún lado AB, BC ... cruza cualquier otro lado

Determine la caja Xmin, Xmax, Ymin, Ymax

caso 1 el punto de prueba P se encuentra fuera de la caja

caso 2 el punto de prueba P se encuentra dentro de la caja:

Determine el ''diámetro'' D de la casilla {[Xmin, Ymin] - [Xmax, Ymax]} (y agregue un poco más para evitar posibles confusiones con D en un lado)

Determinar los gradientes M de todos los lados.

Encuentra un gradiente Mt más diferente de todos los gradientes M

La línea de prueba va desde P a gradiente Mt a distancia D.

Establecer el recuento de intersecciones a cero

Para cada uno de los lados AB, BC prueba la intersección de PD con un lado desde su inicio hasta pero NO INCLUYE su final. Incrementa el recuento de intersecciones si es necesario. Tenga en cuenta que una distancia cero de P a la intersección indica que P está en un lado ON

Una cuenta impar indica que P está dentro del polígono

Answer 14

Código C #

bool IsPointInPolygon(List<Loc> poly, Loc point)
{
    int i, j;
    bool c = false;
    for (i = 0, j = poly.Count - 1; i < poly.Count; j = i++)
    {
        if ((((poly[i].Lt <= point.Lt) && (point.Lt < poly[j].Lt)) 
                || ((poly[j].Lt <= point.Lt) && (point.Lt < poly[i].Lt))) 
                && (point.Lg < (poly[j].Lg - poly[i].Lg) * (point.Lt - poly[i].Lt) 
                    / (poly[j].Lt - poly[i].Lt) + poly[i].Lg))

            c = !c;
        }
    }

    return c;
}

Clase loc

public class Loc
{
    private double lt;
    private double lg;

    public double Lg
    {
        get { return lg; }
        set { lg = value; }
    }

    public double Lt
    {
        get { return lt; }
        set { lt = value; }
    }

    public Loc(double lt, double lg)
    {
        this.lt = lt;
        this.lg = lg;
    }
}