Punto contenido dentro de un póligono
Una necesidad muy común en el desarrollo de videojuegos es la de determinar si un punto esta contenido dentro de un polígono irregular. Por ejemplo en el caso de una aventura gráfica es necesario para averiguar si el usuario ha pulsado sobre una determinada región que podría ser un objeto, otro personaje, etc.
Dentro de la librería matemática que he creado se encuentra la clase polígono que implementa dicha funcionalidad. Así como una serie de clases que también son utilizadas en el algoritmo como la clases Vector o la clase Angulo
El algoritmo para determinar si el punto esta incluido dentro del área del polígono es bastante sencillo, pero requiere algunos cálculos.
Inicialmente se une el punto que se quiere averiguar si esta dentro o fuera del polígono con cada uno de los vértices del polígono, con lo cual se obtendrán tantos segmentos como vértices tenga el polígono.
Después hay que ir sumando los ángulos que forman esos segmentos. La suma hay que realizarla en orden, es decir primero sumar el ángulo que forma el segmento del punto al vertice1 con el segmento del punto al vertice2 con el ángulo que forma el segmento del punto al vertice2 con el segmento del punto al vertice3. Y así sucesivamente en orden hasta terminar sumando el ángulo que forma el segmento del último vértice con el del primer vértice.
Si el ángulo total resultante de la suma de ángulos es 0 grados entonces el punto estará fuera del polígono, si es 2PI entonces estará dentro.
Al realizar los cálculos probablemente se acumulen errores de redondeo así que a lo mejor el resultado no es exactamente 0 o 2 PI, por lo que no se debe comparar con 0 o 2PI si no ver si esta cerca de esos valores.
El código del método que determina si el punto pertenece al polígono es el siguiente:
-
''' <summary>
-
''' Devuelve si el punto pertenece al poligono
-
''' </summary>
-
''' <param name="pPunto"></param>
-
''' <returns></returns>
-
''' <remarks></remarks>
-
Public Function Incluye(ByVal pPunto As Point) As Boolean
-
Dim a As New Angulo(0)
-
Dim v1 As Vector
-
Dim v2 As Vector
-
Dim i As Integer
-
-
If Vertices.Count <3 Then
-
Throw New ApplicationException("El polígono debe tener al menos tres vértices y tiene " & Vertices.Count & " vertices.")
-
End If
-
-
'Trazamos un vector desde el punto a cada uno de los
-
'vertices
-
'Calculamos el angulo que forma cada vector con el
-
'vector del vertice adyacente (el vector del ultimo
-
'vertice formará un angulo con el vector primer vertice)
-
'Sumamos todos los angulo
-
For i = 0 To Vertices.Count - 1
-
v1 = New Vector(pPunto, Vertices(i))
-
v2 = New Vector(pPunto, Vertices((i + 1) Mod Vertices.Count))
-
a = a + Vector.Angulo(v1, v2)
-
Next
-
-
'Si el angulo resultante es 360º entones el punto estará
-
'dentro del poligono
-
'Si el angulo es 0 grados estará fuera.
-
'Como se han podido acumular pequeños errores al hacer
-
'los calculos establecemos que si el valor absoluto
-
'de los grados es menor de 180 esta fuera (realmente
-
'será cercano a 0º) y si no dentro (estará cercano a 360)
-
-
Return Math.Abs(a.Grados)> 180
-
-
End Function
El polígono viene dado por una lista de puntos que representan los vértices.
Para determinar el ángulo entre dos vectores utilizamos la siguiente función:
-
''' <summary>
-
''' Devuelve el angulo que forman los dos vectores expresado en radianes
-
''' </summary>
-
''' <param name="v1"></param>
-
''' <param name="v2"></param>
-
''' <returns>El angulo expresado en radianes</returns>
-
''' <remarks></remarks>
-
Public Shared Function Angulo(ByVal v1 As Vector, ByVal v2 As Vector) As Angulo
-
If Vector.ModuloDelProductoVectorialConSigno(v1, v2)> 0 Then
-
Return New Angulo(Math.Acos((Vector.ProductoEscalar(v1, v2) / (v1.Modulo * v2.Modulo))))
-
Else
-
'Si el modulo del producto vectorial es negativo
-
'el angulo será negativo
-
Return New Angulo(-1 * Math.Acos((Vector.ProductoEscalar(v1, v2) / (v1.Modulo * v2.Modulo))))
-
End If
-
-
End Function
El cálculo del producto escalar de dos vectores y del módulo del producto vectorial es muy sencillo:
-
''' <summary>
-
''' Devuelve el producto escalar de dos vectores
-
''' </summary>
-
''' <param name="v1"></param>
-
''' <param name="v2"></param>
-
''' <returns></returns>
-
''' <remarks></remarks>
-
Public Shared Function ProductoEscalar(ByVal v1 As Vector, ByVal v2 As Vector) As Integer
-
Return ((v1.X * v2.X) + (v1.Y * v2.Y))
-
End Function
-
-
''' <summary>
-
''' Devuelve el módulo del vector resultante de hacer el
-
''' productor vectorial de dos vectores
-
''' </summary>
-
''' <param name="v1"></param>
-
''' <param name="v2"></param>
-
''' <returns></returns>
-
''' <remarks></remarks>
-
Public Shared Function ModuloDelProductoVectorialConSigno(ByVal v1 As Vector, ByVal v2 As Vector) As Integer
-
Return ((v1.X * v2.Y) - (v1.Y * v2.X))
-
End Function
Septiembre 4th, 2007 at 9:34
Perdón por salirme del tema del post, pero me interesa bastante saber cómo haces para mostrar el código resaltado en esas cajas de texto. ¿Es un plugin o algo para wordpress o lo has hecho tú?
Septiembre 4th, 2007 at 10:27
Buenas,
Es un plugin que me baje. Lo tuve que modificar porque tenia algunos errores y le meti algunas mejoras como lo de maximizar.
Permite colorear código de varios lenguajes.
Mandame un email (Email: brauXsoftYgmailZcom (eliminar la X, sustituir la Y por @ y la Z por .) y esta tarde te lo envio
Saludos
Septiembre 11th, 2007 at 4:46
Vaya, jamas se me hubiera ocurrido hacerlo asi. Yo tambien me he encontrado con la necesidad de crear un algoritmo con la misma funcion y andaba bastante perdido. Recibi bastante ayuda en stratos, y al final lo he podido crear yo mismo. Si hubiera leido antes esta entrada… XD
La solucion que aplique fue muy diferente. Dadas las coordenadas de los vertices, trazaba una recta imaginaria. Despues, a traves de un for iba comprobando si la recta cruzaba el espacio contenido entre cada pareja de vertices. Cuando la recta es atravesada un numero impar de veces, coincide siempre con cuando esta dentro del poligono, si es par, es porque esta fuera.
Asi a voz de pronto suena un poco raro, pero si lo plasmas en papel se ve muy claro.
Te dejo adjunto el script que cree. Es GML, por lo que te sonara mucho a pseudocodigo, pero creo que se entiende bien. la variable global.vertice es un array con las IDs de los objetos que utilice para representar los vertices:
//
// Argument0 debe ser un objeto de referencia
// Argument1 es el numero maximo de vertices permitidos
// Devuelve true si el objeto esta dentro y false si esta fuera
//
var corte,vmax;
corte=false;
v_max=argument1-1;
//cerramos el poligono
global.vertice[v_max]=global.vertice[0];
for(i=0; i global.vertice[i+1].y)
|| (argument0.y >= global.vertice[i].y && argument0.y global.vertice[i+1])
|| (argument0.x >=global.vertice[i].x && argument0.x
Septiembre 11th, 2007 at 4:48
La leche, me ha cortado el script justo por la mitad y ahora no lo puedo editar.
Lo dejo entero de nuevo:
//
// Argument0 debe ser un objeto de referencia
// Argument1 es el numero maximo de vertices permitidos
// Devuelve true si el objeto esta dentro y false si esta fuera
//
var corte,vmax;
corte=false;
v_max=argument1-1;
//cerramos el poligono
global.vertice[v_max]=global.vertice[0];
for(i=0; i global.vertice[i+1].y)
|| (argument0.y >= global.vertice[i].y && argument0.y global.vertice[i+1])
|| (argument0.x >=global.vertice[i].x && argument0.x
Septiembre 11th, 2007 at 4:51
Vaya, pues no me deja, supongo que sera por un problema con las etiquetas. Si te interesa te paso el script por otro lado. Perdona por guarrearte el blog.
Septiembre 11th, 2007 at 18:24
Esta entrada la escribir a raíz de leer tu post de stratos, por si le podía ser de utilidad a mas gente. El código es el mismo que te puse allí.
Si quieres puedes mandarme el script por correo y edito tu comentario para incluirlo.
Septiembre 11th, 2007 at 23:30
Vaya, me habia contestado tanta gente que ni me habia dado cuenta de que eras tu uno de los que me ayudasteis en Stratos.
Te he mandado el codigo en GML por un MP en el foro.
por cierto ¿Que etiqueta se usa en wordpress para meter codigo? ¿ [*code] ? te lo comento por si alguna vez tengo que volver a escribir algun codigo o algo.
Septiembre 18th, 2007 at 1:45
Muy buena idea. Yo necesito implementar algo similar para coordenadas globales (GPS) pero muchas veces mis poligonos no son uniformes. alguna idea de como realizarlo? (ej el logo de marlboro) Gracias!
Septiembre 18th, 2007 at 20:51
Este algoritmo funciona tanto para polígonos regulares como irregulares y tanto para cóncavos como para convexos. Por lo tanto debería funcionar para el caso que comentas.
El algoritmo no funcionaria para áreas que tengan “huecos” en su interior, pero en ese caso realmente no sería un polígono.
Saludos
Febrero 19th, 2008 at 16:34
Hola!
Estuve buscando por todas partes y encontre este post y el de stratos-ad; sólo tengo una preguntilla:
Cuando defines los ‘Vector’ y los ‘Vertices’ que són; ¿Clases? Estructuras? me gustaria saberlo ya que ando muy interesado en eso y no puedo probar el código porqué no entiendo esa cosilla. Gracias.
Febrero 19th, 2008 at 21:35
Buenas!
Vértices no es mas que un array de puntos determinados por su coordenada X e Y.
Vector es lo mismo que en matemáticas, un segmento dirigido que va de un punto a otro. El constructor acepta como parámetros dos puntos, el origen y el destino. El vector se puede expresar como un solo punto ya que el vector se puede considerar que va desde el origen de coordenadas (punto 0,0) hasta ese punto.
Espero haberte sido de ayuda.
Un saludo
Febrero 21st, 2008 at 17:55
Gracias, ahora ya estoy testando el asunto. Muchas gracias.
Marzo 13th, 2008 at 17:56
Saludos, estoy analizando su codigo pero no he podido probarlo porque desconozco la estructura de la clases “angulo”, “vector” y el metodo “modulo” de la clase vector. Le agradezco mucho si los publica tambien. Gracias.
Abril 24th, 2008 at 1:22
Jose Gregorio, estuve analizando los algoritmos publicados, y segun esto la clase vector es una clase que contiene dos propiedades X e Y y un contructor que lo que hace es restar a los puntos finales(X,Y) los puntos iniciales(X,Y) respectivamente para trasladar el vector hacia el origen y de esta forma poder hallar el angulo que es lo que interesa, con respecto a la clase angulo contiene el valor del angulo en radianes(0 a 3.1416) y utilza un metodo para convertirlo a grados(0-180), si no utilza una variable de punto flotante y luego pasas el valor a grados (angulo en radianes * 180 / pi)
Espero esto te sirva de guia para que tu mismo plantees las clases faltantes
Junio 4th, 2008 at 17:13
Creo que en mi caso no serviria esta funcion
Necesito encontrar si un punto esta contenido dentro de un area cerrada; tendria un numero de lados indeterminado con angulos rectos (es como si se contruyera girando izquierda o derecha 90 grados), concavos o convexos. La verdad sin pararme a pensar me parecia no debiera tener mucho misterio, pero puesto a implementarlo le encuentro mil y un incognitas
tendria los puntos donde gira p1(x1,y1), p2(x2,y2),..,pn(xn,yn) pn enlaza con p1 ….y el punto a comprobar p(x,y).
Alguien ha trabajado con esto?? Gracias
Agosto 18th, 2008 at 6:27
Me interesa un algoritmo que valide si un poligono esta contenido dentro de
otro
Enero 27th, 2009 at 14:16
Increible. Yo comiendome la cabeza intersectando rectas y que forma tan sencilla y facil de hacerlo.
Muchas gracias caballero, lo he traspasado a Delphi y funciona a la perfección.
PD: Te ha faltado incluir la funcion Modulo que está en Vector
Viene a ser algo tal que así:
//devuelve el modulo de un vector
function TVector.Modulo():real;
begin
result:=sqrt(Power(self.X,2)+Power(self.Y,2));
end;
Saludos
Febrero 4th, 2009 at 1:45
Hola me parece interesante, pero yo estoy desarrollando un gis en donde necesito saber si un punto esta dentro o fuera del poligono… agradeceria si alguien lo tiene implementado pro en JAVA…
GRACIAS
Febrero 16th, 2009 at 8:21
Hola Anonimo, yo tambien estoy buscando lo mismo pero en java, conseguiste algo??? agradeceria mucho tu ayuda. fede431982@hotmail.com . salu2
Marzo 8th, 2009 at 9:33
Muchas Gracias Amigo, en verdad estaba buscando ese algoritmo desde hace mucho tiempo, aportes como los tuyos hacen que la WEB sea mejor cada día.
Atte
Rubén Bocanegra
Septiembre 9th, 2009 at 13:04
hola , al del poligono dentro del otro.
tam simple como calcular que todos los puntos del poligono que quieres saber que esta dendro esten dentro del poligono de fuera
Octubre 10th, 2009 at 16:16
Hola! muy interesante el post. Estoy tratando de desarrollar una funcion que me permita conocer si una posicion de GPS esta ubicada dentro de un area definida. La necesito para analizar, mediante reportes, el recorrido de vehiculos. Creo que esta seria la solucion pero como defino todos los parametros (o convierto) los mismos desde los valores que me entrega el gps? desde ya muchas gracias. Roberto
Febrero 10th, 2010 at 14:59
Hola!. Perdon por la molestia, pero tu codigo me resulta muy interesante. El unico problema que tengo es con “vector” y “vertices”. Podrias publicar esas declaraciones?. O bien enviarmela por mail?. Muchas Gracias por todo. Saludos.