Dedicado a mis proyectos en Gambas ,un lenguaje de programación parecido al Visual Basic + Java pero ampliamente mejorado y...¡¡para gnu/linux!!.La potencia del gnu/linux sumada a la facilidad del Basic



Consultas, Desarrollo de programas y petición de presupuestos:



jueves, 27 de enero de 2011

Saber si un punto está dentro o fuera de polígono





He encontrado este algoritmo, muy interesante, para determinar si un punto esta dentro o fuera de un poligono irregular.

Método 1:  El algoritmo basado en Jordan

nota: la explicacion lo he encontrado en este foro: http://foro.gabrielortiz.com/index.asp?Topic_ID=24147, gracias a Gabriel)

Transcribo literalmente:
Hay varios algoritmos para la determinación de si un punto está dentro de un polígono. La función más fácil de implementar es la del "trazado de rayos", que consiste en trazar una línea con origen en el punto designado por el usuario paralela a alguno de los ejes (X ó Y, da igual). Analíticamente, cuentas el número de intersecciones que se producen con cada una de las líneas del polígono. Si el número de intersecciones es impar, entonces está dentro. Si el número de intersecciones es par, entonces está fuera. El principio se puede ver en esta imagen:





La geometría analítica que necesitas es bastante sencilla de programar. No hay matemáticas muy complicadas como puedes ver en el código que te paso para C que fácilmente puedes adaptar a PHP o al lenguaje con el que estés desarrollando. La función devuelve los valores Fuera o Dentro.

#define MIN(x,y) (x < y ? x : y)
#define MAX(x,y) (x > y ? x : y)
#define INSIDE 0
#define OUTSIDE 1

typedef struct {
double x,y;
} Point;

int InsidePolygon(Point *polygon,int N,Point p)
{
int counter = 0;
int i;
double xinters;
Point p1,p2;

p1 = polygon[0];
for (i=1;i<=N;i++) {
   p2 = polygon[i % N];
   if (p.y > MIN(p1.y,p2.y)) {
   if (p.y <= MAX(p1.y,p2.y)) {
      if (p.x <= MAX(p1.x,p2.x)) {
          if (p1.y != p2.y) {
              xinters = (p.y-p1.y)*(p2.x-p1.x)/(p2.y-p1.y)+p1.x;
              if (p1.x == p2.x || p.x <= xinters)
                counter++;
              }
           }
       } 
    }
   p1 = p2;
}

if (counter % 2 == 0)
return(Fuera);
else
return(Dentro);
}



Otra formula de comprobar si un punto esta fuera o dentro de un poligono:
El algoritmo –Radial-
Existe una alternativa fiable y precisa al método de jordan: se trata de un algoritmo al que hemos llamado "radial", por su peculiar manera de abordar el problema. Es un proceso extremadamente simple, que responde al análisis de la siguiente expresión: , donde cada término equivale a la diferencia de ángulos entre dos radios consecutivos (grafico 5).

Gráfico 5
El procedimiento consiste en recorrer ordenadamente todos los lados del polígono, calculando el ángulo formado por sus extremos y las rectas que los unen al punto P (por supuesto, siempre se tomarán los ángulos menores o iguales a radianes). El signo a considerar será: positivo, si el sentido de crecimiento del ángulo es antihorario, y negativo en caso contrario, o viceversa.
En el ejemplo, llamaremos (1) al ángulo comprendido entre V1 y V2, (2) al comprendido entre V2 y V3, y así sucesivamente. El último término es (9), y corresponde al ángulo medido entre V9 y V1. Obsérvese que los ángulos (2) y (4) son negativos.
Pues bien, si sumamos todos los términos, tan solo podremos obtener dos posibles resultados: 0 o 2. En el primer caso, significará que el punto P está fuera del polígono, y en el segundo que está forzosamente dentro. Así de simple.
Obsérvese que, en el ejemplo:
1+ 2+ 3+ 4+5+ 6+ 7+ 8+ 9 igual a 2
, luego P es interior al polígono
No existen casos especiales ni situaciones ambiguas, e incluso, para aplicaciones especiales, es posible dejar al criterio del programador el considerar si un punto coincidente con un lado o vértice del polígono, se debe considerar interior o exterior al mismo. Para ello basta con decidir si el signo de los ángulos que sean iguales a radianes debe ser positivo o negativo. Normalmente, lo coherente es interpretarlos como negativos, de modo que el punto sea considerado externo al polígono, ya que en caso contrario y, si tuviéramos dos polígonos adyacentes, estaríamos asumiendo que el punto P se encuentra dentro de ambos polígonos simultáneamente.
Consideraciones adicionales
Tal y como se ha podido constatar, el procedimiento es muy simple, fiable, rápido, y preciso.
Con respecto a la sencillez, no caben muchos más comentarios; todo el proceso se reduce a medir ángulos y sumarlos. En todos los casos, el procedimiento es idéntico. No existen posiciones especiales del punto P o de los vértices del polígono que obliguen a tener en cuenta casos particulares.
La fiabilidad viene dada por su sencillez. Cualquier resultado diferente de 0 o 2 , implica necesariamente una anomalía en el polígono (polígono abierto, o lados entrecruzados). Pero incluso se soportan algunas "impurezas" en el trazado del polígono, tal como vértices duplicados, sean estos consecutivos o no.
En cuanto a la velocidad de proceso, cabe resaltar que, frente al elevado grado de crecimiento del tiempo de proceso de algunos algoritmos en función del número de vértices del polígono, el algoritmo radial tiene un crecimiento absolutamente lineal, ya que no requiere ningún preprocesado para identificar el tipo de polígono (convexo o cóncavo), o para detectar a priori algunas situaciones anómalas.
Por último, la precisión viene dada por la exactitud en el cálculo de los ángulos, y depende, claro está, de la máquina sobre la que se ejecute el programa. Si el número de vértices es muy elevado, podríamos llegar a obtener valores distintos de 0 o 2 , aunque siempre muy próximos a ellos. Por lo tanto, es conveniente establecer un pequeño margen para el resultado de la sumatoria final: De todos modos, en el peor de los casos, disponemos de un margen de error admisible, siempre que E menor que radianes. Es decir, todos aquellos valores de la por debajo de pi deberán corisiderarse 0, y aquellos que estén por encima de ese valor, deberán tomarse como 2.
Sin embargo, esta última consideración es poco realista. Veamos: aún considerando que nuestra máquina pueda cometer un error de una millonésima de grado en cada medida de ángulo, lo cual ya es un error considerable, y teniendo en cuenta que nuestro margen de error está situado por debajo de los 180 grados, estaríamos hablando de "posibles errores" en el momento de enfrentarnos a un polígono de más de ciento ochenta millones de vértices, algo infrecuente en una cartografía convencional.

Nota:
Fuente: http://www.mappinginteractivo.com/plantilla-ante.asp?id_articulo=611