Ir al contenido

publicidad

Foto

Interseccion segmento-rectangulo


Este tema ha sido archivado. Esto significa que no puedes responder en este tema.
9 respuestas en este tema

#1

Escrito 09 junio 2010 - 19:38

ALguien conoce algun algoritmo eficaz (porque probe uno y estaba como bug) que te permite calcular si un segmento formado por 2 puntos intersecta con un rectangulo?

El segmento puede ser inclinado en cualquier direccion, el rectangulo no esta inclinado.

Pensé en usar el algoritmo de Sutherland-Hodgman (aunque sea de dibujar, puede servir), pero me surgieron ciertos problemas y me dieron a pensar que ese algoritmo es inviable para esto.

Gracias de antemano

  • Ellolo17

  • Zodiark

  • vida restante: 100%
  • Registrado: 16 nov 2006
  • Mensajes: 6.208
#2

Escrito 09 junio 2010 - 22:17

Yo lo que haria seria, tanto para 2d como para 3d, colocar un sprite o un poligono a lo largo de la recta formada por los dos puntos y recolocarlo en plan "arbol de busqueda" para comprobar si se encuentra por ahi.

Me refiero, tu tienes las dos coordenadas, colocas el "sensor" o compruebas en el punto medio del sector. Si no colisiona compruebas si por coordenadas globales debes ponerlo mas cerca de un vertice o del otro, y tomas como segundo o primer punto el punto medio y haces esto recursivamente hasta que lo encuentre, en cuyo caso devuelve un 1, o hasta que se repita un numero de veces, en cuyo caso devuelve 0.

Lo malo de este algoritmo es que funciona de maravilla para pequeñas distancias y rectangulos decentes, pero cuanto mas pequeño el rectangulo y mas grande la recta mas tarda en comprobar en el peor de los casos pero... esto es un videojuego y como mucho imagino que iras comprobando entre sprites y pixeles, ¿no? pues si el sprite mas pequeño con el que puede colisionar la recta mide x, pues puedes probar que busque en la recta hasta que la distancia entre los dos vertices sea menor que esa x.

Con eso no te tiene que dar ningun problema y se realiza rapido ;)

Un saludo.

  • txesmi

  • Childrer

  • vida restante: 100%
  • Registrado: 14 jun 2009
  • Mensajes: 41
#3

Escrito 09 junio 2010 - 23:37

A mí se me ocurre que podrías utilizar la regla general de intersección entre funciones lineales.

Teniendo tanto el segmento como los lados del cuadrado definidos como funciones lineales
y = mx + n

igualas las funciones del segmento y de cada uno de los lados del cuadrado. Habría que repetirlo con los cuatro lados del cuadrado.
(m1)x + (n1) = (m2)x + (n2)

entonces...
x = ( (n2)-(n1) ) / ( (m1)-(m2) )

al despejar 'y' en cualquiera de las dos funciones compruebas si está dentro del segmento.

nota: si 'm1' y 'm2' son iguales las rectas son paralelas, por lo que no se intersectan.

Salud!

  • txesmi

  • Childrer

  • vida restante: 100%
  • Registrado: 14 jun 2009
  • Mensajes: 41
#4

Escrito 10 junio 2010 - 10:54

Hola,

Primero perdón por el doble post... XD

Seguidamente, he querido desarrollar en lenguaje programatical el concepto matemático antes descrito. Yo soy programador amateur en uno de esos motores condenados al ostracismo por lo que no puedo daros la solución para C pero se parece bastante.

Lo primero sería tener almacenadas las coordenadas tanto del segmento como del cuadrado en sendas matrices:
Esquinas[4][2] -> para el cuadrado
Coordenadas[2][2] -> para el segmento

También declararíamos otras dos matrices para almacenar los componentes Pendiente (m) e intersección (n) de ambas figuras:
Cuadrado[4][2] -> para los cuatro lados del cuadrado
Segmento[2] -> para el segmento

Con las variables declaradas procederíamos al cálculo de los componentes de las funciones:
[code:1]for ( i=0; i<4; i++ )
{
ii = ( i + 1 ) % 4;

if ( Esquinas[i][1]-Esquinas[ii][1] != 0 )
Cuadrado[i][0] = ( (Esquinas[i][1]-Esquinas[ii][1]) / (Esquinas[i][0]-Esquinas[ii][0]) );
else
Cuadrado[i][0] = 1000;

Cuadrado[i][1] = Esquinas[i][1] - ( Esquinas[i][0] * Cuadrado[i][0] );
}[/code] -> para el cuadrado
[code:1]if ( Coordenadas[0][1]-Coordenadas[1][1] != 0 )
Segmento[0] = (Coordenadas[0][1]-Coordenadas[1][1]) / (Coordenadas[0][0]-Coordenadas[1][0]);
else
Segmento[0] = 1000;

Segmento[1] = Coordenadas[0][1] - ( Coordenadas[0][0] * Segmento[0] );[/code] -> para el segmento

Y por último calcularíamos los puntos de intersección entre el segmento y los cuatro lados del cuadrado:
[code:1]for ( i=0; i<4; i++ )
{
if ( Segmento[0] - Cuadrado[i][0] != 0 )
{
Interseccion[i][0] = ( Cuadrado[i][1] - Segmento[1] ) / ( Segmento[0] - Cuadrado[i][0] );
Interseccion[i][1] = ( Interseccion[i][0] * Segmento[0] ) + Segmento[1];
}
else
{
Interseccion[i][0] = 0;
Interseccion[i][1] = 0;
}
}[/code]

Como me suele ocurrir, el desarrollo mental del problema suele tener algún fallo y erré al decir que con comprobar si cada punto de intersección estaba contenido en el segmento valdría para saber si intersectaba con el cuadrado. Así también habría que comprobar que está contenido en el lado objeto del cálculo, o si el cuadrado es regular, si algún punto de intersección está dentro del círculo que circunscribe el cuadrado. Si ambos casos son afirmativos, el segmento intersecta con alguno de los lados del cuadrado.

He escrito un programilla que utiliza este algoritmo y simplemente calcula los cuatro puntos de intersección. Está disponible tanto el código fuente (liteC) como una compilación ejecutable:
http://partidabierta...?cid=31&lid=579

Este algoritmo es extensible a cualquier poliedro de múltiples caras.

Salud!

#5

Escrito 10 junio 2010 - 12:02

ALguien conoce algun algoritmo eficaz (porque probe uno y estaba como bug) que te permite calcular si un segmento formado por 2 puntos intersecta con un rectangulo?

El segmento puede ser inclinado en cualquier direccion, el rectangulo no esta inclinado.

Pensé en usar el algoritmo de Sutherland-Hodgman (aunque sea de dibujar, puede servir), pero me surgieron ciertos problemas y me dieron a pensar que ese algoritmo es inviable para esto.

Gracias de antemano


Antes de nada.... lo quieres para 2D o para 3D?
Un rectangulo seria 2D, pero bueno, puede ser tambien una figura 3D, no?

#6

Escrito 10 junio 2010 - 17:34

ALguien conoce algun algoritmo eficaz (porque probe uno y estaba como bug) que te permite calcular si un segmento formado por 2 puntos intersecta con un rectangulo?

El segmento puede ser inclinado en cualquier direccion, el rectangulo no esta inclinado.

Pensé en usar el algoritmo de Sutherland-Hodgman (aunque sea de dibujar, puede servir), pero me surgieron ciertos problemas y me dieron a pensar que ese algoritmo es inviable para esto.

Gracias de antemano


Antes de nada.... lo quieres para 2D o para 3D?
Un rectangulo seria 2D, pero bueno, puede ser tambien una figura 2D, no?


Lo quiero para 2D

#7

Escrito 10 junio 2010 - 21:00

Si no le tienes miedo al ingles, ahi van dos enlaces:
http://www.allegro.c...s/thread/588948
http://www.gamedev.n...topic_id=434170

Un saludo

  • Ollydbg

  • Bahamut

  • vida restante: 100%
  • Registrado: 05 sep 2008
  • Mensajes: 6.259
#8

Escrito 10 junio 2010 - 21:40

No se si este tutoriual que escribí ya hace tiempo te puede ayudar:

.NET Tutorial 16. Colisiones 2D

Aquí unas fotillos:
Imagen Enviada
Imagen Enviada
Imagen Enviada
Imagen Enviada
Imagen Enviada

Saludos.

  • txesmi

  • Childrer

  • vida restante: 100%
  • Registrado: 14 jun 2009
  • Mensajes: 41
#9

Escrito 27 junio 2010 - 09:37

@NullPointerException

¿Te sirvió alguno de los ejemplos?

Salud!

#10

Escrito 07 julio 2010 - 22:55

Veamos, he probado como tu dijiste, txesmi, pero al final como que no me salia nada, me salen bugs raros, que dice que choca donde en teoria no deberia chocar.

Al final me he decidido usar el "Separation Axis Theorem", que no se como se llama en castellano porque buscandolo en castellano no lo encontre, el problema es que tambien me da algun bug. Entonces, mi plan es hacer como dice Ollydbg que es subdividir el area en triangulos, pero el problema es que siempre, casualmente, me dice que choca justo cuando paso de largo del triangulo y por detras me acerco pero no le doy.

Si usais algun metodo para determinar colisiones entre el suelo y el jugador (en 2D preferentemente), estaria bien que me dijerais que algoritmo aplicais


Este tema ha sido archivado. Esto significa que no puedes responder en este tema.
publicidad