¿Cuál es su algoritmo óptimo sobre cómo calcular el punto de intersección de dos líneas formadas por cuatro puntos en un plano?

Answer 1

No he jugado con el código de geometría durante varios años. No estoy seguro de si es óptimo o no.

Supongo que todos los puntos están en el plano XY.

Primero, debe verificar si P1 y P2 son el mismo punto. En caso afirmativo, solo verifique si P1 (P2) está en la misma línea que P3 y P4:
[matemáticas] \ vec {P1P3} × \ vec {P1P4} == 0 [/ matemáticas]
es decir
[matemáticas] (X3 – X1) * (Y4-Y1) – (X4 – X1) * (Y3-Y1) == 0 [/ matemáticas]

Si no es así, puede calcular los productos cruzados: [math] \ vec {P3P1} × \ vec {P3P2} [/ math] y [math] \ vec {P4P1} × \ vec {P4P2} [/ math]. En realidad, solo las coordenadas Z de los dos productos cruzados pueden ser distintos de cero, que son:
[matemáticas] A = (X1 – X3) * (Y2 – Y3) – (X2 – X3) * (Y1-Y3) [/ matemáticas]
y
[matemáticas] B = (X1 – X4) * (Y2 – Y4) – (X2 – X4) * (Y1-Y4) [/ matemáticas]

Puede considerar que A y B son el área (con signo) de [matemáticas] \ triángulo P3P1P2 [/ matemáticas] y [matemáticas] \ triángulo P4P1P2 [/ matemáticas].

Si A == B, P3 y P4 son el mismo punto o [math] \ vec {P3P4} [/ math] está en paralelo con [math] \ vec {P1P2} [/ math]. Ambos son fáciles de manejar.

De lo contrario, más o menos, tiene
A: B = la distancia de P3 a la línea [matemáticas] \ vec {P1P2} [/ matemáticas]: la distancia de P4 a [matemáticas] \ vec {P1P2} [/ matemáticas]
= [matemáticas] \ vec {P3Q}: \ vec {P4Q} [/ matemáticas]
= [matemáticas] \ vec {P3Q}: \ vec {P3Q} – \ vec {P3P4} [/ matemáticas].
Para que pueda calcular el vector [math] \ vec {P3Q} [/ math] por:
[matemáticas] \ vec {P3Q} = \ dfrac {A} {A – B} * \ vec {P3P4} [/ matemáticas]
donde Q es la intersección que quieres.

[matemáticas] Q = P3 + \ dfrac {A} {A – B} * \ vec {P3P4} [/ matemáticas]
es decir
[matemáticas] Xq = X3 + \ dfrac {A} {A – B} * (X4 – X3) [/ matemáticas]
[matemáticas] Yq = Y3 + \ dfrac {A} {A – B} * (Y4 – Y3) [/ matemáticas]

Answer 2

Tener las coordenadas de los puntos puede calcular la ecuación de la línea que determinan. Después de calcular ambas ecuaciones, simplemente construye un sistema con esos 2 y la solución representa el punto de intersección. Solo ten cuidado con esos casos extremos.