Determinando si existe una coordenada dentro de un polígono

Question

Estoy trabajando en una aplicación de software de seguimiento y geocerca abierta y me está resultando un poco difícil calcular las matemáticas para el geofencing.

Necesito determinar si existe una coordenada dentro de un polígono o no. Sin embargo, la parte difícil es que el polígono no tiene un número determinado de lados. Necesito poder calcular por cincuenta lados o por cinco lados.

Mi investigación dice que la manera más fácil es tomar mi punto (que llamaré x) y un punto fuera del polígono (llamarlo y) y determinar si la línea ((xx, xy), (yx, yy)) se cruza con los límites del polígono. Si se cruza con un número impar de veces, el punto x debe estar dentro del polígono.

Sabiendo eso, sin embargo, no puedo encontrar la forma de expresar esto en un algoritmo. Obviamente tendré que recorrer las diversas líneas construyendo el polígono, pero la verificación que hago me elude. ¿Alguien puede ser de ayuda? Por favor, sepan que no estoy pidiendo la solución necesariamente. Cualquier cosa que me ayude a resolver la respuesta es una ayuda enorme.

Muy apreciado.

Answer 1

Ver here

Básicamente hay un acercamiento (Creo que es el Teorema de la curva de Jordan) que cuenta el número de veces que un rayo intersecta los segmentos de línea que forman el polígono. Si el resultado es par, el punto está fuera del polígono, de lo contrario, el punto queda dentro del polígono.

HTH

EDITAR Hay otro SO pregunta que se refiere a esta pregunta que se puede encontrar here

Answer 2

Supongo que estás en un avión (2D).

• Calcular las pendientes de cada lado (en algún sistema de coordenadas) y la pendiente de la línea desde el punto X al punto Y (línea XY).
• Para todos los lados donde la pendiente no es igual a la pendiente de XY, calcule el punto de intersección.
• Para cada punto, determine si el punto de intersección está en el segmento de línea XY y el segmento de línea que define el lado. Si es así, cruzaste ese lado. (Compruebe las coordenadas de la intersección y vea si los componentes x e y están incluidos en el rango de valores para cada segmento de línea.)
• Cuente el número de cruces, y usted tiene su respuesta.

Answer 3

Calcular la winding number del polígono y el punto.

Answer 4

Una clave aquí es darse cuenta de que usted es libre de elegir cualquier punto Y que desee. Una buena elección es el punto (xx, -infinity). En otras palabras, el punto directamente hacia abajo desde el punto en cuestión e infinitamente lejos. Ahora la pregunta es: cuántos de los bordes del polígono cruzan la coordenada X debajo del punto en cuestión. Por lo tanto, solo se deben considerar los segmentos de línea que se encuentran a horcajadas sobre la coordenada X.

Si su punto es P = (x, y), y los puntos finales del segmento son P1 = (x1, y1) y P2 = (x2, y2) la coordenada y del segmento donde cruza x está dada por sy = (x-x1) * (y2-y1)/(x2-x1) + y1

Comprobar si sy < y (sólo si x1 < x < x2 o x2 < x < x1). Si hay un número impar de estos, P está dentro.

Existen problemas sutiles cuando una de las verticidades del polígono se encuentra exactamente en la misma posición y del punto en cuestión. Tendrás que tener cuidado con ese caso.

Answer 5

Justin,

También puede ser necesario para definir mejor "fuera del polígono" para construir un segmento.

Tome el min & max de todos los x & coordenadas y y construir un rectángulo (xmin, ymin), (xmax, ymin), (xmax, ymax), (xmin, ymax). Cualquier punto fuera del rectángulo definitivamente estaría fuera del polígono, luego continúe como otros lo han mostrado arriba. Cada segmento de polígono y la línea construida se define por una ecuación y = ax + b y, para cada segmento, un rango xlo y xhi. Tu línea construida cruza un segmento en el rango o no. Es decir, la solución de las dos ecuaciones simultáneas en el rango de segmentos existe o no. Simplemente cuente la cantidad de soluciones que existen para obtener el número de intersecciones.

Answer 6

Prueba de esto,

public static bool PointinPolygon(Point[] points, Point p) 
    { 
     bool result = false; 

     for(int i = 0; i < points.Length - 1; i++) 
     { 
      if((((points[ i + 1 ].Y <= p.Y) && (p.Y < points[ i ].Y)) || ((points[ i ].Y <= p.Y) && (p.Y < points[ i + 1 ].Y))) && (p.X < (points[ i ].X - points[ i + 1 ].X) * (p.Y - points[ i + 1 ].Y)/(points[ i ].Y - points[ i + 1 ].Y) + points[ i + 1 ].X)) 
      { 
       result = !result; 
      } 
     } 
     return result; 
    }