Foros - Stratos

 Como hecho de menos que años atras me hubieran explicado mejor algunas cosas en Dibujo Tecnico :P

Tengo en mente calcular las fisicas de mi juego mediante calculo de intersecciones de un punto con una linea o recta (punto de control de un objeto con un mapa o lista de rectas que definen superficies como rampas, techos o paredes) y por el momento mi "invento" ha sido algo tan simple y logico para mis cada dia mas escasos conocimientos matematicos el calcular el angulo del punto de origen de la linea con el punto que supuestamente deberia estar en la misma trayectoria de la linea, mas claro, compruebo si el angulo entre los puntos AB (coordenadas origen y destino de la linea o recta) es el mismo que el de AC (coordenadas origen de la linea con las coordenadas del punto a comprobar):

CitarCoordenadas de la linea o recta
{
    A.X = 0, A.Y = 0
    B.X = 100, B.Y = 100
}

Coordenadas del punto a comprobar
{
    C.X = 50, C.Y = 50
}

@AB = 45º
@AC = 45º

Existe interseccion

Mi pregunta es, existe alguna formula o ecuacion para comprobar esto mismo que fuese mas simple o rapido sin tanto calculo?

Salu2...

P.D.: Ya imagino que alguno me recomendara que use simples mapas de durezas o mascaras de bits para las colsiones pero este metodo me permite guardar en el mismo mapa o lista de rectas el angulo, evitando asi tener que calcularlo en cada test y asi agilizar calculos para rebotes por ejemplo, el id de material (madera, metal, tierra, etc...) que describiria la superficie para configurar los efectos de sonidos de pisadas de personajes, friccion del terreno, etc... y total, para los pocos objetos que moveria el juego al mismo tiempo no habria mucho problema con el rendimiento.

 En Gamedev o Gamasutra seguro que encuentras varios métodos para esto.

 si lo que quieres es comprobar es si el punto pertenece a la recta es tan simple como sacar algunos datos de la misma. si tenemos
Y=MX+N y no sabemos ni M ni N aunque segun veo en tu codigo es bastante facil obtener M, ya que es solo cosa de hacer M=(B.Y-A.Y)/(B.X-A.X)
. para sacar N haces N=A.Y-M*A.X
si quieres comprobar q el punto pertenezca a la recta como veo que es tu caso, es tan simple como chequear si
(y usare tus datos)

(B.Y-A.Y)/(B.X-A.X)*C.X+N-C.Y=0

si esto se cumple es que el punto pertenece a la recta.
usando numeritos seria algo asi

M=(100-0)(100-0)=1
100=1*100+N => N=0

por lo tanto la ecuacion es
Y=MX+N
donde
M=1
N=0

por lo tanto para chequear que el susodicho punto pertenece a la recta es cosa de chequear si
C.Y=M*C.X+N es verdadero, y si lo es es por que el punto esta en la recta

 Muchas gracias por la ayuda, vicho y sobre todo por los detalles y la explicacion aunque me tengo que poner un poco a repasar mis apuntes de Dibujo Tecnico (no los tire?  :ph34r: ) por que con el paso del tiempo me estoy atocinando y me cuesta entender muchas veces cosas como estas :)

sés, estuve navegando unos cuantos dias por google y me perdia entre tanta pagina de matematicas, geometria, y venian explicados muchos algorritmos pero para casos mucho mas complejos que lo que andaba buscando, en resumen, se iban por las ramas y si encima no se tiene mucha idea del tema te pierdes el doble :P Sobre GameDev y Gamasutra, a la primera suelo acudir en muchas ocasiones para buscar implementaciones o informacion de algunas tecnicas, en este caso no cai en mirar alli que seguro hubiera encontrado mucho acerca del tema, gracias por ese punto recordatorio :)

Salu2...

 Esa no es la forma correcta programacionalmente ;).

Direccion de la recta = Vector2( B.X - A.X, B.Y - A.Y);

Normal a la recta = Vector2( A.Y - B.Y,  B.X - A.X ) normalizado;

Dezplazamiento del origen = - Producto punto de la Normal a la recta por A o por B (que comodo!)

Distancia del punto C a la recta = Producto punto de la normal + Dezplazamiento del origen

Si la distancia es 0 el punto C esta en la recta ...

Si no queremos normalizar nos vasta con:

0 = (A.Y-B.Y) * (C.X-A.X) + (B.X-A.X) * (C.Y-A.Y)

Pero puede fallar por el error de la precision ... con lo cual tendremos que agregar un delta ...

Y si normalizamos ya nos ahorramos todos los problemas de precision ...

Delta > Absoluto ( N.x * (C.X-A.X) + N.y * (C.Y-A.Y) ) siendo N el vector dirección normalizado.

Esta es la forma programacional de resolver el problema, pues se evita la división por 0 de la recta y la precision es constante en punto fijo.

Saludos.

 A ver, que esto se pone interesante :D No entendi muy bien tu explicacion Pogacha pero leyendo algunas de las paginas que encontre sobre geometria y recordando lo que di sobre normalizar vectores, producto, modulo y ciertos conceptos mas que tengo presentes pero no recuerdo :P me he puesto a tratar de llevar a codigo tu explicacion anterior. Echa un vistazo y dime como lo ves:
Public Function GetIntersect3(Src As Vector, Dest As Vector, Point As Vector) As Boolean
   Dim D As Vector, N As Vector, Normal As Vector
   Dim dSrc As Double, Product As Double, Dist As Double

   'Direccion de la recta = Vector2( B.X - A.X, B.Y - A.Y);
   D.X = Dest.X - Src.X: D.Y = Dest.Y - Src.Y

   'Normal a la recta = Vector2( A.Y - B.Y, B.X - A.X ) normalizado;
   N.X = Src.Y - Dest.Y: N.Y = Dest.X - Src.X
   Call NormalizeVector(Normal, N)

   'Dezplazamiento del origen = - Producto punto de la Normal a la recta por A o por B (que comodo!)
   Product = (Normal.X * Point.X) + (Normal.Y * Point.Y)
   dSrc = -((Product * Src.X) + (Product * Src.Y))

   'Distancia del punto C a la recta = Producto punto de la normal + Dezplazamiento del origen
   Dist = Product + dSrc

   'Si la distancia es 0 el punto C esta en la recta ...
   If Dist = 0 Then GetIntersect3 = True

End Function

Public Sub NormalizeVector(Out As Vector, Src As Vector)
   Dim m As Double

   'Hayamos el modulo del vector:
   m = Sqr((Src.X * Src.X) + (Src.Y * Src.Y))

   'Normalizamos el vector:
   Out.X = Src.X / m
   Out.Y = Src.Y / m

End Sub
Tiene la pinta de estar correcto ya que he hecho algunas pruebas y parece que funciona pero por si las moscas me gustaria que lo miraras y me dijeras si hay algo que no este bien. Cada implmentacion esta basada en base a cada explicacion que me distes.

Salu2...

 Public Function GetIntersect3(Src As Vector, Dest As Vector, Point As Vector) As Boolean
   Dim D As Vector, N As Vector, Normal As Vector
   Dim dSrc As Double, Product As Double, Dist As Double

   'Direccion de la recta = Vector2( B.X - A.X, B.Y - A.Y);
   D.X = Dest.X - Src.X: D.Y = Dest.Y - Src.Y

   'Normal a la recta = Vector2( A.Y - B.Y, B.X - A.X ) normalizado;
   N.X = Src.Y - Dest.Y: N.Y = Dest.X - Src.X
   Call NormalizeVector(Normal, N)

   'Dezplazamiento del origen = - Producto punto de la Normal a la recta por A o por B (que comodo!)
   'Lo escribí mal!
   'Dezplazamiento del origen = - Producto punto entre la Normal a la recta y A (o B) (que comodo!)

   dSrc = -((Normal.X * Src.X) + (Normal.Y * Src.Y))
   dDest = -((Normal.X * Dest.X) + (Normal.Y * Dest.Y))
  'Ambas te tienen que dar lo mismo, compruebalo ...

   Proyeccion = (Normal.X * Point.X) + (Normal.Y * Point.Y)

   'Distancia del punto C a la recta = Producto punto de la normal + Dezplazamiento del origen
   Dist = Proyeccion + dSrc

   ' Se puede optimizar sensiblemente sin tener que sacar dSrc ni Proyeccion haciendo:
   Dist = (Normal.X * (Point.X-Src.X)) + (Normal.Y * (Point.Y-Src.Y))

   'Si la distancia es 0 el punto C esta en la recta ...
   'If Dist = 0 Then GetIntersect3 = True

   'Ya que esta normalizado seria bueno agregar un delta (lo cercano que ya consideras dentro de la recta) pues puede haber un error de precision
   If Abs(Dist) < 0.00001 Then GetIntersect3 = True

End Function

Public Sub NormalizeVector(Out As Vector, Src As Vector)
   Dim m As Double

   'Hayamos el modulo del vector:
   m = Sqr((Src.X * Src.X) + (Src.Y * Src.Y))

   'Normalizamos el vector:

   'Para evitar la division por 0 y optimizar el codigo:
   if m <> 0 then m = 1.0/m;

   Out.X = Src.X * m
   Out.Y = Src.Y * m

End Sub
A ver si ahí te anda ...

Edit: Corregido sobre el dist

 ¿onde andará mi libro de algebra lineal? ¿onde? (ole)

hace mucho ya que no toco estas cosas

 

Cita de: "zxs"¿onde andará mi libro de algebra lineal? ¿onde? (ole)

hace mucho ya que no toco estas cosas

Calla, que yo hace solo 3 meses que di temas de vectores en unas clases preparatorias, que triste xD

Pogacha, no me funciona en todos los casos tu codigo (el de vicho tampoco), funcionar en el hecho de que no me devuelve Verdadero aun estando el punto sobre la linea en casos irregulares que no tengan angulos de 45º por ejemplo (como empece a trabajar el tema con angulos me dedico a variar las posiciones de los vectores y suelo revisar los angulos que generan). Mi primer codigo el que realizaba la prueba de los angulos tuve que hacer que pasara a enteros los angulos, que eran tipo Single (float en C/C++) para obtener un valor mas proximo a la linea, si no tampoco me funcionaba ya que la precision de los decimales alejaba un poco un valor de otro. De esta forma realizando tantas variantes de los valores de los vectores como quiera parece no fallar. Estoy tratando de hacer lo mismo con tu codigo pero de momento no he logrado resultados :-/

Salu2...

 No es mi metodo, es el metodo general, te lo enseñan en algebra I y tiene siglos de antiguedad ...

Sean A y B vectores no coincidentes y pertenecientes a la recta, y sea P un punto sobre el cual quiero saber si se encuentra sobre la recta.

Direccion = (B - A) / | B - A |

La direccion es el vector normalizado del resultante de la diferencia de ambos.

Normal.x = Direccion.y
Normal.y = -Direccion.x

Para encontrar la normal a un vector 2d solo debo invertir x por y y cambiar el signo a uno de ellos. Demostración: extiende los vectores a 3d y haz el cruz correspondiente por la normal a ambos ( 0, 0, 1).

D = Normal.x * (P.x-A.x) + Normal.y * (P.y-A.y);  

La distancia del punto a la recta es igual a la magnitud de la proyección del punto sobre la normal (producto punto) menos la distancia de la recta al origen segun su normal (producto de su normal y un punto perteneciente a la misma), por propiedades de la suma y el producto el producto punto de N.P - N.A es igual a N.(P-A)

Si esta distancia (D) es igual a cero entonces esta en la recta, pero como la presicion puede alterar sensiblemente el resultado se suele buscar un epsilon que sea el error permitido ( habia dicho delta pero estaba mal  :P la letra epsilon se designa para tales fines ) .

Entonces si |D| < Epsilon suponemos que esta en la recta.

Esto es elemental, no hay posibilidad de error ... te aseguro que este es el metodo.

No le confio a mi implementación en Basic asi que en C para no hacer lio:
Vamos que se entiende!
#define EPSILON 1.0     // Dejamos 1.0 de error posible

struct Vector {
 float x, y;
};

int ComprobarPuntoEnRectaRecta(Vector A, Vector B, Vector P)
{
 float d;
 Vector D, N;
 
 D.x = B.x - A.x;
 D.y = B.y - A.y;

 d = sqrt(D.x*D.x + D.y*D.y);

 if( d > 0.0f) d = 1.0f / d;
 N.x = D.y * d;
 N.y = -D.x * d;

 d = N.x * (P.x - A.x) + N.y * (P.y - A.y);

 return fabs(d) < EPSILON; // Devuelve 1 si esta y 0 si no
}

 considera tambien que hay puntos que pueden pertenecer a la recta pero no al trazo. por lo tanto seria bueno hacer un chequeo max-min.

 

Cita de: "Pogacha"No es mi metodo, es el metodo general, te lo enseñan en algebra I y tiene siglos de antiguedad ...

Era una mera forma de referirme a la implementacion que me explicastes de la de vicho, ya imagino que esto se dara en universidad (y quizas en bachiller... pero yo curse el de artes  :ph34r:)

Cita de: "Pogacha"Esto es elemental, no hay posibilidad de error ... te aseguro que este es el metodo.

No lo dudo (y mas cuando el que tiene idea en esto eres tu y yo no tengo en absoluto) pero he traducido el codigo, lo he probado y sigue sin funcionar :(

Traduccion del codigo a VB:
Nota: En VB expresiones como 1.0 se convierten a 1! (realmente a 1# que seria tipo Double creo) En "teoria" 1.0 y 1! es lo mismo...
Public Function GetIntersect(A As Vertex, B As Vertex, P As Vertex) As Boolean
   Const EPSILON As Single = 1.5!   '#define EPSILON 1.0     // Dejamos 1.0 de error posible

   Dim Dir As Single 'float d;
   Dim D As Vertex, N As Vertex 'Vector D, N;

   D.X = B.X - A.X 'D.x = B.x - A.x;
   D.Y = B.Y - A.Y 'D.y = B.y - A.y;

   Dir = Sqr(D.X * D.X + D.Y * D.Y) 'd = sqrt(D.x*D.x + D.y*D.y);

   If Dir > 0! Then Dir = 1! / Dir 'if( d > 0.0f) d = 1.0f / d;
   N.X = D.Y * Dir 'N.x = D.y * d;
   N.Y = -D.X * Dir 'N.y = -D.x * d;

   Dir = N.X * (P.X - A.X) + N.Y * (P.Y - A.Y) 'd = N.x * (P.x - A.x) + N.y * (P.y - A.y);

   GetIntersect = Abs(Dir) < EPSILON 'return fabs(d) < EPSILON; // Devuelve 1 si esta y 0 si no

End Function
En otro foro me han comentado otro metodo, que desgraciadamente, tampoco funciona:
Public Function GetIntersect(A As Vertex, B As Vertex, P As Vertex) As Boolean
Dim m As Double, n As Double

'Pendiente a la recta:
m = (B.Y - A.Y) / (B.X - A.X)

'Termino independiente:
n = (A.Y * B.X - B.Y * A.X) / (B.X - A.X)

'Ecuacion de la recta:
GetIntersect = (P.Y = (4 / 3) * P.X + 0) Or (P.Y = (4 / 3) * P.X)

End Function
No pense que algo tan sencillo en apariencia fuese tan costoso de resolver :(

Compruebalo tu mismo, te paso el programa que utilizo para testear las rutinas: IntersectPointLine.rar

Dentro viene un txt con las teclas de uso del programa y una breve leyenda de los elementos en pantalla. Tambien viene incluida la dx_lib32 y una utilidad para registrarla y des-registrarla comodamente.

Cuando lo ejecutes activa el modo 2, eso hara que el programa utilice tu rutina para realizar la comprobacion. Para facilitar el test activa el incremento automatico del eje Y en el vector C, de esta forma podras arrastrar el vector C de forma que vaya cayendo hacia abajo (controlas el eje X con el raton) y poder ir arrastrandolo por la linea comprobando donde realiza las colisiones. El eje Y del vector C cuando sale de pantalla resetea su posicion a 0 automaticamente. Veras que realiza las colsiones muy lejos de la linea cuanto mas lejos esta del vecto A y mas cerca del vector B (con angulos regulares de AB como 45º la precision es casi total). Con mi metodo de los angulos la perdida de precision es inapreciable casi (2 pixeles cuanto mas lejos esta de A y mas cerca de B y dependiendo del angulo tambien).

Salu2...

 1 - por las dudas, una recta no tiene principio ni fin, un segmento si, para acotar la prueba hasta el segmento debes agregar que se fije si el punto esta dentro de la caja de contención del segmento. Supongo que esto es obvio.

2 - El sqrt se refiere al square root (raiz cuadrada). No es si el sqr del basic es lo mismo.

3 - Fijate que las componentes de los vectores sean flotantes por que sino vamos fritos y creo que es ese el error según el programa que me mandas. Las normales tienen modulo 1 o sea que sus componentes tienen valores de (-1 a 1) puedes usar un truco de punto fijo si fuera el caso o si no declara a la normal fuera como dos
Dim Nx As Single, Ny as Single 'float Nx, Ny;
y de esta manera no tendras que modificar tu estructura vertex

4 - El segundo programa usa la misma técnica que proponia vicho, la mas tentadora en un principio, pero tiene el problema de la division por 0 y la diferencia de presicion a diferentes pendientes. No controlé que estuviera bien tampoco, ando mal de tiempo :(

Saludos.

...

 

Cita de: "Pogacha"1 - por las dudas, una recta no tiene principio ni fin, un segmento si, para acotar la prueba hasta el segmento debes agregar que se fije si el punto esta dentro de la caja de contención del segmento. Supongo que esto es obvio.

La colision solo la realizaba en el metodo de los angulos para evitar que me diera por correcto un angulo fuera del alcance de la linea. No lo tengo implementado en el otro metodo pero lo añadire.

Cita de: "Pogacha"2 - El sqrt se refiere al square root (raiz cuadrada). No es si el sqr del basic es lo mismo.

En teoria se supone que si :ph34r:

QUOTE (MSDN 6.0)

Sqr (Función)       Devuelve un tipo Double que especifica la raíz cuadrada de un número. Sintaxis Sqr(número) El númeroargumento es un tipoDouble o cualquierexpresión numérica válida mayor o igual a cero.[/quote] Cita de: "Pogacha"3 - Fijate que las componentes de los vectores sean flotantes por que sino vamos fritos y creo que es ese el error según el programa que me mandas. Las normales tienen modulo 1 o sea que sus componentes tienen valores de (-1 a 1) puedes usar un truco de punto fijo si fuera el caso o si no declara a la normal fuera como dos Dim Nx As Single, Ny as Single 'float Nx, Ny; y de esta manera no tendras que modificar tu estructura vertex Mmm, mira por donde puede venir por ahi el error ya que el tipo Vertex que aparece en mi codigo es un tipo de la dx_lib32 y sus componentes son todos tipo Long. Voy a hacer una implementacion Vector a pelo en el ejemplo y vuelvo a probar (no cai en este detalle (nooo) ) Cita de: "Pogacha"4 - El segundo programa usa la misma técnica que proponia vicho, la mas tentadora en un principio, pero tiene el problema de la division por 0 y la diferencia de presicion a diferentes pendientes. No controlé que estuviera bien tampoco, ando mal de tiempo :( No te preocupes, bastante que le estas dedicando tiempo a este tema, que ya es suficiente de agradecer :) Voy a probar el codigo con la modificacion del nuevo tipo Vector y te cuento. Agregare tambien la implementacion de Lex para probar. Salu2... Título: Existe Una Formula Mas Rapida/sencilla/logica? Publicado por: [EX3] en 13 de Mayo de 2006, 06:07:12 AM  Confirmado Pogacha, era problema de la estructura Vertex de dx_lib32 y sus componentes tipo Long, con la clase Vector y sus componentes tipo Single va 100% precisa a la linea (ole) Siento haber tenido mi descuido con lo de la estructura y el tipo de dato que usa, no me percate y por ello te he tenido 3 dias revisando un codigo que funcionaba desde el principio, perdon por las molestias y muchas gracias por tu tiempo :) Te dejo el programa arreglado para que lo veas ;) IntersectPointLine(FINAL).rar Lex, tu codigo no me funciono en ninguno de los casos :( Salu2... Título: Existe Una Formula Mas Rapida/sencilla/logica? Publicado por: Lex en 13 de Mayo de 2006, 03:17:40 PM ... Título: Existe Una Formula Mas Rapida/sencilla/logica? Publicado por: Pogacha en 13 de Mayo de 2006, 03:43:38 PM  Que bueno que te ha funcionado al fin! No necesitas cambiar la estructura vector, tan solo ajustar la normal para que sean 2 flotantes independientes. Saludos. Título: Existe Una Formula Mas Rapida/sencilla/logica? Publicado por: [EX3] en 14 de Mayo de 2006, 04:20:09 AM   Cita de: "Pogacha"No necesitas cambiar la estructura vector, tan solo ajustar la normal para que sean 2 flotantes independientes. Saludos. Cierto, no lo habia mirado, como la normal es el unico vector que recibiria valores que se trabajan en punto flotante el tipo Vertex seria igual de valido para los argumentos de entrada de la funcion :) Cita de: "Lex"quizás mirando el código de tu aplicación podría ver en qué falla lo mio Todo tuyo ;) He añadido al paquete actual los fuentes. Vienen tambien las implementaciones que me hicieron en los foros de DivSite.net (foros de Fenix) en el codigo del proyecto. Salu2... Título: Existe Una Formula Mas Rapida/sencilla/logica? Publicado por: Lex en 15 de Mayo de 2006, 11:50:09 PM ... Título: Existe Una Formula Mas Rapida/sencilla/logica? Publicado por: [EX3] en 16 de Mayo de 2006, 12:36:45 AM  En serio, entre lo del Select Case y lo de no renombrar unas variables en una implementacion que me pasaron en otro foro si no fuera por que tengo 22 años diria que estoy empezando a chochear (nooo) Aun con esas como te comente en el MSN el codigo que me pasastes no funcionaba en todos los casos, pero esta ultima modificacion que le has hecho parece que va 100% perfecta :) Yo estaba ya tratando con mi logica "anti-matematicamente-correcta" de buscar una solucion mediante comparativas que no iba a ser tan optimizada como el codigo de pogacha o el tuyo. Y pensar que me quede en los umbrales de estos temas cuando abandone el curso preparatorio del modulo, menudo acierto por mi parte (nooo) Salu2... Text only | Text with Images SMF 2.1.4 | SMF © 2013, Simple Machines