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