Detección de colisiones.

Avatar de Usuario
Tachikomaia
Mensajes: 12152
Registrado: 10 Ago 2011, 20:39

Detección de colisiones.

Mensaje por Tachikomaia »

Internet me ha vuelto, por ahora.

En cuanto al tema, no pensé que me diera la sensación de que fuera tan complicado. Quizá comunmente es de programación, pero es claro que va más allá.
Supongan que tenemos un plano 2d, con x e y, pero sin negativos (o al menos no son necesarios).
¿Cómo detectar que un punto colisiona (está sobrepuesto, choca) con otro?
Si Punto1._x == Punto2._x && Punto1._y == Punto2._y
Fácil.

Siguiente nivel:
Un punto y una línea.
¿Ideas?
Algo he pensado y leído, me dejó la sensación de que en el fondo son gráficas, ver el inicio y crecimiento (¿la pendiente?). Explicaciones simples por favor, no artículos.
Dicho de otra forma, cómo saber si un punto en x1y1 está en una línea que empieza en x2y2 y termina en x3y3.

Me interesa el tema para circulo-triángulo, pero quiero ir muy despacio porque me resulta complicado.

Si la línea es totalmente horizontal o vertical, respecto al plano, entonces es fácil.
Horizontal:
Si Punto._x => Line.ExtremoIzq._x && Punto._x <= Line.ExtremoDer._x && Punto._y == Line._y
Vertical:
Si Punto._y => Line.ExtremoSup._y && Punto._y <= Line.ExtremoInf._y && Punto._x == Line._x
...algo que sirva para otros casos, para mí es difícil, y algo que sirva para todos más.
Nota: Hecho como si el eje y creciera hacia abajo.

Bueno, gracias, me voy a dormir (compu lenta, tema complicado...). Si van respondiendo voy poniendo más casos hasta llegar al que quiero. En realidad ese es más sencillo porque los triángulos en él no se rotan, pero quiero entender los otros casos.
Si no puedes hacerlo, intenta primero hacer algo más simple aunque similar.
Avatar de Usuario
Tachikomaia
Mensajes: 12152
Registrado: 10 Ago 2011, 20:39

Re: Detección de colisiones.

Mensaje por Tachikomaia »

Posiblemente con proporciones. Si el punto está entre los puntos extremos de la línea (considerada como rectángulo), por ejemplo los xs, habría que calcular qué x tendría el punto y de la línea si dicha y fuese el mismo que el del punto suelto.
Si no puedes hacerlo, intenta primero hacer algo más simple aunque similar.
Avatar de Usuario
hamsun
Mensajes: 223
Registrado: 11 Ene 2016, 02:01

Re: Detección de colisiones.

Mensaje por hamsun »

Imagen
Con (x2,y2) y (x3,y3) tenes la ecuacion punto punto, luego para ver si (x1,y1) pertenece a la recta lo que haces es evaluar la ecuacion (reemplazas x1 en donde esta la x y y1 en donde esta la y), notese que esa ecuacion no te sirve para rectas verticales (te resultaria una division por 0) pero esas rectas tienen la ecuacion x=a, por lo tanto los puntos que estan en esa recta son muy faciles de verificar ya que tienen la forma (a,y) (esto anterior escogiendo el eje horizontal como el eje x y el vertical como el eje y).

La justificacion de la ecuacion de una recta esta en la geometria (semejanza de triangulos), tambien se puede justificar vectoraialmente en donde resulta una ecuacion mas general, no se si te interesa el tema.
Avatar de Usuario
Tachikomaia
Mensajes: 12152
Registrado: 10 Ago 2011, 20:39

Re: Detección de colisiones.

Mensaje por Tachikomaia »

Mis conocimientos de matemática y entendimiento son bastante bajos, so... por ejemplo cuando dices "la forma punto pendiente" no sé a qué se refiere. El concepto de pendiente lo puse pero entre paréntesis, no lo sé. Más despacio xD
Si no puedes hacerlo, intenta primero hacer algo más simple aunque similar.
Avatar de Usuario
hamsun
Mensajes: 223
Registrado: 11 Ene 2016, 02:01

Re: Detección de colisiones.

Mensaje por hamsun »

Es la ecuacion de una funcion lineal (una funcion lineal es una recta que no es paralela al eje y, las que son paralelas al eje "y" te las describi en el mensaje anterior, las rectas verticales) a esa ecuacion me referia cuando te hablé de la justificacion a traves de la geometria, la de la pendiente es una definicion (lo que tiene de especial una recta es que su pendiente para cualquier par de puntos en ella es constante, eso es lo que se demuestra con semejanza de triangulos), la punto-punto (que es la que tienes que utilizar en el problema que propusiste), resulta de reemplazar la pendiente en la ecuacion de la funcion lineal (punto-pendiente).

Esos nombres salen de lo que necesitas para llegar a la ecuacion de la recta (en el plano es de la forma ax+by=c, esta es la forma general en el plano), en la punto-pendiente necesitas la pendiente y un punto, en la punto-punto necesitas 2 puntos.

Te recomiendo leer cositas basicas de matematicas antes de programar, pegarle una hojeadita a algun libro de precalculo o de geometria vectorial, te va a facilitar los razonamientos en la creacion del programa. Por ejemplo lo del circulo y el triangulo sale de la interseccion de un circulo con un triangulo, el circulo tiene una ecuacion sencilla, el triangulo necesita una parametrizacion de 3 vectores.
Avatar de Usuario
Tachikomaia
Mensajes: 12152
Registrado: 10 Ago 2011, 20:39

Re: Detección de colisiones.

Mensaje por Tachikomaia »

Por ahora quisiera que me ayudes con esto que me parece más simple.
Imagen
En el centro está la línea y la cruz marca el punto. Si el punto estuviera en algún área pintada (no de blanco), su colisión con la línea queda descartada, porque está por detrás del inicio de la línea o delante del final. Con 4 ifs se puede chequear, cada uno descarta un área.
Supongamos que x1 y y1 son 0. Y x2 y y2 es 10. Si digo que px y py es 6, me parece que debería servir alguna regla de 3 o algo así.
x___y
0___0
10__10
6___???
Obviamente ??? sería 6, el tema es cómo se calcula. En este caso y=x, pero no siempre es tan fácil...

Otro caso, then:
x___y
0___1
10__9
6___???

10__100%
6__60%

9__100%
???__60%
??? = 9*60/100
5.4+1

O sea...
1- Hago px*100/x2, que me da en qué porcentaje de la línea, en x, se encuentra el punto en x. En el dibujo sería más o menos 20%. Dicho de otro modo, qué tan cerca está del extremo derecho, 100 es lo máximo. Llamemos a esto Porce.
2- Hago y2*Porce/100+y1. Eso me da el y del punto de la línea que tiene el mismo x que el punto. Entonces ya puedo ver que, si los y son iguales, hay colisión, y sino no :mrgreen:

Está bien?

¿Pero qué pasa cuando x1 es > 0? Veamos:
x___y
2___3
6__8
4___???

Sé que el porcentaje debería ser 50, porque 4 está entre medio de 2 y 6, o sea que sería:
???__100%
4__50%
Y en ??? tengo un 2 y 6 ¿cómo se relacionarían como para que se ajuste? Debería ser... 4*100/50=400/50=8, o sea:
px*100/(x1+x2)
No arroja resultados erróneos en casos anteriores.

Entonces:
1: px*100/(x2+x1) = Porce.
2: y2*Porce/100+y1 = Porcey
3: Chequeo py y Porcey, si son iguales hay colisión y sino no.

¿Bien? Pero algo no me cierra, eso de que se sumen los x para hallar el porcentaje... ¿cual es la explicación de por qué debe hacerse? Más allá de porque se ajuste al resultado buscado.

Intentaré hacer un programilla que chequeé usando este método.
Si no puedes hacerlo, intenta primero hacer algo más simple aunque similar.
Avatar de Usuario
Tachikomaia
Mensajes: 12152
Registrado: 10 Ago 2011, 20:39

Re: Detección de colisiones.

Mensaje por Tachikomaia »

"lo que tiene de especial una recta es que su pendiente para cualquier par de puntos en ella es constante"
Entonces eso era como me imaginaba, pero en la wiki mencionaron derivadas y en definitiva dicen tanto o de una forma tan complicada que me dan ganas de presionar esc xD
Si no puedes hacerlo, intenta primero hacer algo más simple aunque similar.
Avatar de Usuario
hamsun
Mensajes: 223
Registrado: 11 Ene 2016, 02:01

Re: Detección de colisiones.

Mensaje por hamsun »

Perdon por no quererme complicar con lo de los porcentajes, estoy tostado todavia, esa universidad esta brava. Por otro lado tambien estoy oxidado en programacion, un dia de estos tengo que repasar.


x1<=px<=x2
y1<=py<=y2
Con esto tenemos que (px,py) esta en lo blanco.


(px,py) esta en la recta si y solo si (py-y1)/(px-x1)=(y2-y1)/(x2-x1) esto es lo de la ecuacion punto-punto evaluando (px,py) en la ecuacion.
Avatar de Usuario
Tachikomaia
Mensajes: 12152
Registrado: 10 Ago 2011, 20:39

Re: Detección de colisiones.

Mensaje por Tachikomaia »

hamsun escribió:Perdon por no quererme complicar con lo de los porcentajes, estoy tostado todavia, esa universidad esta brava.
El cálculo de porcentajes es cosa de escuela, preparatoria o como se diga en tu país xD
Es más básico que las cosas que mencionaste.
x1<=px<=x2
y1<=py<=y2
Con esto tenemos que (px,py) esta en lo blanco.
Exacto.
(px,py) esta en la recta si y solo si (py-y1)/(px-x1)=(y2-y1)/(x2-x1) esto es lo de la ecuacion punto-punto evaluando (px,py) en la ecuacion.
Puedo llegar a esa conclusión por mis propios medios? Es decir, cómo se llega a ella, por qué funciona? Se puede llegar con Google pero no me refiero a eso xD

PD: No puedo hacer el programa de prueba porque no sé cómo hacer rectas random. Well, sí podría rotar una, pero cambiarle de tamaño no, o sea, si lo hago se agranda el grosor, en realidad varío el tamaño de una imagen. Veré cómo queda anyway.
Si no puedes hacerlo, intenta primero hacer algo más simple aunque similar.
Avatar de Usuario
hamsun
Mensajes: 223
Registrado: 11 Ene 2016, 02:01

Re: Detección de colisiones.

Mensaje por hamsun »

No es que no entienda los porcentajes si no que viendo por encima no me cuadraban tus ecuaciones, tal vez esten bien pero en otro momento las reviso.

Vealo de esta forma (x,y) pertenece a la recta determinada por (x1,y1) y (x2,y2) si pasa esto (y-y1)/(x-x1)=(y2-y1)/(x2-x1) una interpretacion de la ecuacion es que en cada miembro de la ecuacion hay una pendiente, pero cualquier pendiente de la recta es la misma, por eso la igualdad. Vea el miembro izquierdo de la ecuacion como (x,y) variando y (x1,y1) fijo, en vez de (x1,y1) se puede tomar un punto arbitrario en la recta, es como coger un punto de referencia.

La pendiente es constante por semejanza de triangulos, o por proporciones que veo que con eso tenes contacto.
Responder