elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: Recuerda que debes registrarte en el foro para poder participar (preguntar y responder)


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación C/C++ (Moderadores: Eternal Idol, Littlehorse, K-YreX)
| | |-+  Intersección linea - triángulo
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] 2 Ir Abajo Respuesta Imprimir
Autor Tema: Intersección linea - triángulo  (Leído 7,595 veces)
BlackM4ster


Desconectado Desconectado

Mensajes: 499


Error, el teclado no funciona. Pulse F1 para continuar


Ver Perfil WWW
Intersección linea - triángulo
« en: 19 Julio 2014, 06:13 am »

Hola, llevo un tiempo intentando dar con un algoritmo para detectar el punto de intersección (si existe) entre una linea (rayo) y un triángulo. ¿Alguno tiene implementado ya ésto?
Los parámetros a pasar serían:

Código
  1. Vec3f InterseccionRayoTriangulo(Vec3f T1, Vec3f T2, Vec3f T3, Vec3f R1, Vec3f R2)

Siendo T1, T2 y T3 los vértices del triángulo y R1 y R2, los puntos de la linea.

Alguna idea?


En línea

- Pásate por mi web -
https://codeisc.com
leosansan


Desconectado Desconectado

Mensajes: 1.314


Ver Perfil
Re: Intersección linea - triángulo
« Respuesta #1 en: 19 Julio 2014, 14:06 pm »

Hola, llevo un tiempo intentando dar con un algoritmo para detectar el punto de intersección (si existe) entre una linea (rayo) y un triángulo. ¿Alguno tiene implementado ya ésto?
Los parámetros a pasar serían:

Código
  1. Vec3f InterseccionRayoTriangulo(Vec3f T1, Vec3f T2, Vec3f T3, Vec3f R1, Vec3f R2)

Siendo T1, T2 y T3 los vértices del triángulo y R1 y R2, los puntos de la linea.

Alguna idea?

Supongo que T1 y compañía son tipo estrctura donde tienes los vértices de cada uno.

Lo primero es la nomenclatura:

Código
  1. a = ( y2 - y1 ) / ( x2 - x1 ) ///para recta R1 R2
  2. b = y1 - a * x1               ///para recta R1 R2
  3.  
  4. A = ( Y2 - Y1 ) / ( X2 - X1 ) ///para una de las Tini Tfinal
  5. B = Y1 - A * X1               ///para una de las Tini Tfinal
  6.  

donde con minúsculas represento a la recta R1 R2 y con mayúsculas a una de las rectas del triángulo y habrá que hacerlo para cada una de las tres rectas del triángulo, siempre con la misma R1 R2.

Y al meollo de la cuestión, dónde se cortan:

Código
  1. if ( a = A )
  2.  /** no se corta pues son paralelas // **/
  3. else
  4.  /** se cortan y el punto de corte es: **/
  5.  
  6.  x = ( B - b ) / ( a - A )
  7.  
  8.  y = ( a * B - A * b ) / ( a - A )

Así de simple. Existen otros métodos pero como supongo que trabajas con las coordenadas de los vértices me parece el mejor.

Espero no haberla pifiado al copiar los datos, no obstante lo he comprobado con un par de casos y va bien.

¡¡¡¡ Saluditos! ..... !!!!





En línea

BlackM4ster


Desconectado Desconectado

Mensajes: 499


Error, el teclado no funciona. Pulse F1 para continuar


Ver Perfil WWW
Re: Intersección linea - triángulo
« Respuesta #2 en: 19 Julio 2014, 14:12 pm »

Gracias por la respuesta, ahora estoy intentando aplicarlo en 3D, la cosa se complica
En línea

- Pásate por mi web -
https://codeisc.com
leosansan


Desconectado Desconectado

Mensajes: 1.314


Ver Perfil
Re: Intersección linea - triángulo
« Respuesta #3 en: 19 Julio 2014, 16:21 pm »

Gracias por la respuesta, ahora estoy intentando aplicarlo en 3D, la cosa se complica

Un poquitín solamente.

Sin entrar demasiado a estudiar la poscición relativa de las rectas, por entrar de lleno en el meollo del problema, tendrías:

Código
  1. vector de la recta R1 R2:
  2. vx  = ( x2 - x1 ) ... vy  = ( y2 - y1 ) ... vz  = ( z2 - z1 )  
  3.  
  4. ecuacion continua de la recta R1 R2:
  5. ( x - x1 ) / vx = ( y - y1 ) / vy = ( z - z1 ) / vz
  6.  
  7. ecuaciones implicitas de la recta R1 R2:
  8. vz * x - z * vx = x1 * vz - z1 * vx (1)
  9. vz * y - z * vy = y1 * vz - z1 * vy (2)
  10.  
  11. vector de la recta T1 T2:
  12. wx  = ( X2 - X1 ) ... wy  = ( Y2 - Y1 ) ... wz  = ( Z2 - Z1 )  
  13.  
  14. ecuacion continua de la recta T1 T2:
  15. ( x - X1 ) / wx = ( y - Y1 ) / wy = ( z - Z1 ) / wz
  16.  
  17. ecuaciones implicitas de la recta T1 T2:
  18. wz * x - z * wx = X1 * wz - Z1 * wx (3)
  19. wz * y - z * wy = Y1 * wz - Z1 * wy (4)
  20.  
  21.  
  22.  if ( vx / wx = vy / wy = vz / wz )
  23.    son paralelas o coincidentes ==> no punto de corte
  24.  else
  25.    resolver las ecuciones (1), (2), (3) , por ejemplo por la regla de Cramer,
  26.    y sustituir el punto obtenido en (4). Si se cumple la igualdad de (4)
  27.    es que es el punto de corte, si no se cruzan y no hay corte.
  28.  

Espero que te sea útil.  ;)

¡¡¡¡ Saluditos! ..... !!!!


« Última modificación: 19 Julio 2014, 17:09 pm por leosansan » En línea

avesudra


Desconectado Desconectado

Mensajes: 724


Intentando ser mejor cada día :)


Ver Perfil
Re: Intersección linea - triángulo
« Respuesta #4 en: 19 Julio 2014, 17:28 pm »

Un poquitín solamente.

Sin entrar demasiado a estudiar la poscición relativa de las rectas, por entrar de lleno en el meollo del problema, tendrías:

Código
  1. vector de la recta R1 R2:
  2. vx  = ( x2 - x1 ) ... vy  = ( y2 - y1 ) ... vz  = ( z2 - z1 )  
  3.  
  4. ecuacion continua de la recta R1 R2:
  5. ( x - x1 ) / vx = ( y - y1 ) / vy = ( z - z1 ) / vz
  6.  
  7. ecuaciones implicitas de la recta R1 R2:
  8. vz * x - z * vx = x1 * vz - z1 * vx (1)
  9. vz * y - z * vy = y1 * vz - z1 * vy (2)
  10.  
  11. vector de la recta T1 T2:
  12. wx  = ( X2 - X1 ) ... wy  = ( Y2 - Y1 ) ... wz  = ( Z2 - Z1 )  
  13.  
  14. ecuacion continua de la recta T1 T2:
  15. ( x - X1 ) / wx = ( y - Y1 ) / wy = ( z - Z1 ) / wz
  16.  
  17. ecuaciones implicitas de la recta T1 T2:
  18. wz * x - z * wx = X1 * wz - Z1 * wx (3)
  19. wz * y - z * wy = Y1 * wz - Z1 * wy (4)
  20.  
  21.  
  22.  if ( vx / wx = vy / wy = vz / wz )
  23.    son paralelas o coincidentes ==> no punto de corte
  24.  else
  25.    resolver las ecuciones (1), (2), (3) , por ejemplo por la regla de Cramer,
  26.    y sustituir el punto obtenido en (4). Si se cumple la igualdad de (4)
  27.    es que es el punto de corte, si no se cruzan y no hay corte.
  28.  

Espero que te sea útil.  ;)

¡¡¡¡ Saluditos! ..... !!!!



Saludos Leosansan el problema que se plantea aquí es mucho mayor que calcular el corte entre dos rectas, pues en este problema calculando las intersecciones con las tres rectas que forman los tres segmentos del triangulo y la recta que dirige el rayo no has acabado. Simple y llanamente porque la recta puede cortar justo en el centro del triángulo sin cortar a las rectas anteriormente mencionadas, y ante ese planteamiento el método que has posteado es solamente útil cuando el problema se limite solo a Recta-Recta, pero aquí estamos hablando de Recta-Triángulo o rigurosamente hablando a Recta-Plano y solo en una región del plano determinada.

Considerando el problema en más profundidad el corte entre la Recta del rayo y el Plano del triángulo daría un punto de corte, que además habría que comprobar si está dentro del triángulo, cosa que es bastante complicada y que estoy ahora mismo mirando.

La geometría euclídea en un espacio de R3 es bastante complicada en mi opinión cuando se trata de estos casos en los que hay que restringir un elemento aunque será para mí que tengo pocos conocimientos de matemáticas.

Un cordial saludo.
« Última modificación: 19 Julio 2014, 18:18 pm por avesudra » En línea

Regístrate en
leosansan


Desconectado Desconectado

Mensajes: 1.314


Ver Perfil
Re: Intersección linea - triángulo
« Respuesta #5 en: 19 Julio 2014, 18:20 pm »

Saludos Leosansan el problema que se plantea........................ aquí estamos hablando de Recta-Triángulo o rigurosamente hablando a Recta-Plano y solo en una región del plano determinada.

Considerando el problema en más profundidad el corte entre la Recta del rayo y el Plano del triángulo daría un punto de corte, que además habría que comprobar si está dentro del triángulo, cosa que es bastante complicada y que estoy ahora mismo mirando.
..................................


El que planteas es otro punto de vista, válido por supuesto.

Y si ese es el caso bastaría con hallar el punto de corte del rayo con el plano y después determinar si dicho punto es interior o no.

1.*

Para lo primero se resuelve el determinante formado por (x-x1,y-y1,z-z1), siendo (x1,y1,z1) uno de los tres vértices del triángulo y los dos vectores (vx,vy,vz) y (wx,wy,wz) correspondientes a, por ejemplo, T1T2 y T1T3. Ello nos dará la ecuación del plano de la forma típica Ax+By+Cz+D=0.

A continuación se sustituye la recta del rayo en forma paramétrica, donde (ax,ay,az) es el vector del rayo y (X1,Y1,Z1) un punto del mismo (no "problem" porque tenemos dos puntos del rayo por lo que podemos hallar tanto el vector  como un punto del mismo):

x=X1+ax*t
y=X1+ay*t
z=Z1+az*t

como decía, se sustituyen las ecuaciones anteriores en la ecuación del plano, de donde se obtiene el valor de "t" que sustituido en las anteriores ecuaciones paramétricas nos dan el valor del punto intersección del rayo con el plano.

2.*
Ahora queda determinar si es interior o exterior para lo cual hay multitud de métodos. Uno simple, ya que su uso sólo implica calcular áreas de triángulos cosa que es fácil con el producto "vectorial", consiste en calcular las áreas de los triángulos PcorteT1T2, PcorteT2T3, PcorteT3T1 y si es igual al área del triángulo T1T2T3 está dentro, si no está fuera.

Pero insisto es que es una de las diversa maneras de hacerlo, lo indico por la facilidad mencionada del calculo de las áreas.

Y esto dicho a toda pastilla, si me "asiento" un poco seguro que le buscamos la vuelta de una manera más sencilla.  ;)

¡¡¡¡ Saluditos! ..... !!!!



EDITADO: Con la correción de producto vectorial por escalar.  :silbar:
« Última modificación: 19 Julio 2014, 18:58 pm por leosansan » En línea

avesudra


Desconectado Desconectado

Mensajes: 724


Intentando ser mejor cada día :)


Ver Perfil
Re: Intersección linea - triángulo
« Respuesta #6 en: 19 Julio 2014, 18:26 pm »

El que planteas es otro punto de vista, válido por supuesto.

Y si ese es el caso bastaría con hallar el punto de corte del rayo con el plano y después determinar si dicho punto es interior o no.

1.*

Para lo primero se resuelve el determinante formado por (x-x1,y-y1,z-z1), siendo (x1,y1,z1) uno de los tres vértices del triángulo y los dos vectores (vx,vy,vz) y (wx,wy,wz) correspondientes a, por ejemplo, T1T2 y T1T3. Ello nos dará la ecuación del plano de la forma típica Ax+By+Cz+D=0.

A continuación se sustituye la recta del rayo en forma paramétrica, donde (ax,ay,az) es el vector del rayo y (X1,Y1,Z1) un punto del mismo (no "problem" porque tenemos dos puntos del rayo por lo que podemos hallar tanto el vector  como un punto del mismo):

x=X1+ax*t
y=X1+ay*t
z=Z1+az*t

como decía, se sustituyen las ecuaciones anteriores en la ecuación del plano, de donde se obtiene el valor de "t" que sustituido en las anteriores ecuaciones paramétricas nos dan el valor del punto intersección del rayo con el plano.
En efecto es justo lo que yo estaba escribiendo en latex, no se me había ocurrido lo de las áreas, muy inteligente por tu parte.

Un pequeño apunte, el área se calcula con el producto vectorial no con el escalar.

¡Un saludo! Publicaré el proceso cuando termine de escribirlo.
« Última modificación: 19 Julio 2014, 18:49 pm por avesudra » En línea

Regístrate en
leosansan


Desconectado Desconectado

Mensajes: 1.314


Ver Perfil
Re: Intersección linea - triángulo
« Respuesta #7 en: 19 Julio 2014, 18:36 pm »

En efecto es justo lo que yo estaba escribiendo en latex, no se me había ocurrido lo de las áreas, muy inteligente por tu parte.
..................................................

Gracias, gracias.

Sólo una pequeña observación, si alguno de los triángulos  PcorteT1T2, PcorteT2T3, PcorteT3T1 da de área cero es que el punto está "sobre" uno de los lados.

Un fuerte saludo avesudra.
En línea

avesudra


Desconectado Desconectado

Mensajes: 724


Intentando ser mejor cada día :)


Ver Perfil
Re: Intersección linea - triángulo
« Respuesta #8 en: 20 Julio 2014, 01:42 am »

Gracias, gracias.

Sólo una pequeña observación, si alguno de los triángulos  PcorteT1T2, PcorteT2T3, PcorteT3T1 da de área cero es que el punto está "sobre" uno de los lados.

Un fuerte saludo avesudra.
Aquí está resuelto simbólicamente, ahora solo hay que implementarlo.

https://drive.google.com/file/d/0Bw0QWEQBKEXLMjl4ZEt0eVk1T00/edit?usp=sharing

Muchas gracias por tu visión de lo del triángulo. Quizás haga el código.

Saludos.
En línea

Regístrate en
leosansan


Desconectado Desconectado

Mensajes: 1.314


Ver Perfil
Re: Intersección linea - triángulo
« Respuesta #9 en: 20 Julio 2014, 15:03 pm »

Aquí está resuelto simbólicamente, ahora solo hay que implementarlo.
https://drive.google.com/file/d/0Bw0QWEQBKEXLMjl4ZEt0eVk1T00/edit?usp=sharing
Muchas gracias por tu visión de lo del triángulo. Quizás haga el código.
Saludos.

Al menos a mí no se me abre el pdf  :o

Otra opción, si no me falla la geometría,  para ver si el punto es interior o no es calcular los productos vectoriales PcorteT1xPcorteT2, PcorteT2xPcorteT3 ,PcorteT3xPcorteT1 y si son paralelos, o proporcionales tienen el mismo sentido es que el punto es interior. Con ello evitamos el calcular las áreas.

¡¡¡¡ Saluditos! ..... !!!!


« Última modificación: 21 Julio 2014, 14:19 pm por leosansan » En línea

Páginas: [1] 2 Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
Reto - Intersección de 2 cubos
Ejercicios
[D4N93R] 4 7,866 Último mensaje 19 Agosto 2010, 21:36 pm
por [D4N93R]
Calcular la intersección de dos segmentos
Programación C/C++
DickGumshoe 6 15,861 Último mensaje 31 Octubre 2011, 23:11 pm
por DickGumshoe
Intersección de recta y punto
Programación C/C++
kaostias 4 3,749 Último mensaje 26 Noviembre 2013, 18:23 pm
por kaostias
Intersección entre 3 circunferencias o más.
Foro Libre
xustyx 2 5,202 Último mensaje 9 Abril 2015, 16:25 pm
por xustyx
Intersección de dos vectores
Programación C/C++
tokyo13 2 3,998 Último mensaje 30 Junio 2019, 07:17 am
por CalgaryCorpus
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines