¿Cómo se calcula si 2 líneas están orientadas hacia o lejos?

10

Dados los 4 puntos que describen 2 segmentos de línea, ¿cómo calcula si la línea A está hacia o lejos de la línea B?

Las 2 líneas tienen una longitud fija y se pueden medir como distancia desde x1 / y1 hasta x2 / y2.

ingrese la descripción de la imagen aquí

mathematics geometry lines beziers curves Robinicks
fuente
¿Cómo es el caso con la curva de Bezier diferente del caso con líneas rectas? ¿Tiene una curva que podría encerrar completamente la otra línea (de modo que cada dirección apunte "hacia")?
bummzack
1
Probablemente necesite aclarar sus términos. En Geometría, una "línea" se extiende infinitamente en cualquier dirección, en oposición a una media línea o segmento, por lo que 2 líneas siempre se cruzan a menos que sean paralelas. ¿Sobre cuál preguntas? Has dibujado una flecha, que implica dirección, que para mí implica un segmento o, como máximo, media línea. ¿Y cuál es su definición de "hacia" y "lejos"?
Hackworth
La curva de Bezier podría ser más difícil de representar en la igualdad requerida para resolver una prueba de intersección de línea de rayos. Por cierto, voy a cambiar la palabra que representa tu flecha a "rayo". Es posible que obtenga una respuesta más rápida. Contestaré esto si tengo tiempo durante el almuerzo si nadie más lo hace. Si no, esta es una tarea extremadamente común en los juegos. Google "Prueba de intersección de segmento de línea de rayos". Sospecho que la prueba de curva de Bezier es similar, pero nunca la he probado.
brandon
3
Deberías dividir tu pregunta en dos. La parte con segmentos de línea es muy fácil. La parte con curvas bezier es extremadamente compleja y solo tiene una solución numérica aproximada.
sam hocevar
He dividido mi pregunta en 2, según lo solicitado. La segunda parte está aquí: gamedev.stackexchange.com/questions/21463/…
Robinicks

Respuestas:

11

Dejar AyB sea ​​dos puntos en la línea negra. Deja Cy Dser tu segmento azul. El signo de la zcoordenada del producto cruzado AB^ACle indica si Cestá "a la izquierda" o "a la derecha" de la línea negra. Del mismo modo, el producto cruzado AB^CDle indica si CDdirige "izquierda" o "derecha" de la línea negra.

Realmente no queremos saber si es izquierda o derecha; todo lo que queremos es asegurarnos de que tengan la misma dirección o la dirección opuesta, por eso multiplicamos los dos valores.

Por lo tanto, el siguiente pseudocódigo debería funcionar:

z1 = (xB-xA)*(yC-yA) - (yB-yA)*(xC-xA);
z2 = (xB-xA)*(yD-yC) - (yB-yA)*(xD-xC);
z3 = z1 * z2;

if (z3 < 0)
    ; /* Pointing towards (BUT maybe even crossing) */
else if (z3 > 0 || z2 != 0)
    ; /* Pointing away */
else
    ; /* Parallel */

Me temo que necesito algo de tiempo para escribir una solución adecuada para la curva de Bezier. ¿La siguiente situación es hacia o lejos?

¿Problema?

sam hocevar
fuente
Para la curva, creo que podría encontrar la tangente de la curva en el punto más cercano a su segmento de línea y usarla de la misma manera que prueba sus otros segmentos de línea. Probablemente un poco más difícil de lo que parece :)
notlesh 12/12/11
@stephelton: Mire nuevamente la segunda imagen para las curvas bezier, apuntando hacia una curva que se curva hacia afuera. O considere una curva con una tangente paralela al segmento que posiblemente se cruza, pero que se curva hacia el segmento y se cruza.
Cascabel
+1 para el trollface y buenas matemáticas :). Sin embargo, su diagrama 'hacia' en realidad todavía tiene un 'lejos': simplemente mueva el punto de partida por encima de la línea.
Jonathan Dickinson
@JonathanDickinson gracias, ¡actualicé la imagen para que quede un poco más claro cuál es mi interrogatorio!
sam hocevar
2

Asumiendo que el punto de inicio es el círculo verde, y el punto final es la flecha roja

Calcule la distancia entre el punto inicial como DS y el segmento negro, y haga lo mismo para el punto final (flecha roja) que DE. Si DS> DE, entonces el segmento está apuntando hacia. si DE> DS, está apuntando hacia afuera. Si ambos son iguales, los dos son paralelos.

Puede encontrar cómo calcular la distancia desde un punto a un segmento aquí , y a una curva bezier cuadrática aquí . Sin embargo, dependiendo de la forma de la curva de Bezier, podría arrojar resultados extraños (la curva puede cruzarse a sí misma)

Ravachol
fuente
DS> DE está garantizado para trabajar solo para líneas rectas. Puede fallar para Beziers. Además, no conoce su definición de "hacia". Si la extensión de la flecha cruzaría una línea definida por 2 puntos, pero no el segmento definido por los mismos puntos, ¿sigue siendo "hacia"?
Hackworth
Estoy hablando de dos segmentos, no de líneas, por lo que no hay una "extensión de la flecha". Además, no importa dónde apunte la flecha, ya que estamos hablando de distancias aquí. El punto más cercano en la línea negra podría ser un punto inicial / final de la línea negra, no importa. Los dos segmentos podrían ser colineales, este método aún funcionaría según lo previsto. Para las curvas bezier que mencioné, daría resultados extraños dependiendo de la forma de la curva.
Ravachol