Dadas las coordenadas del principio y el final de dos segmentos de línea que se cruzan, ¿cómo encuentro las coordenadas de su intersección?

Question

Hay dos segmentos de línea. Sé con seguridad que se cruzan (por lo que no tengo que comprobarlo). Para ambos segmentos de línea conozco las coordenadas de sus dos extremos. ¿Con qué fórmula puedo encontrar las coordenadas de su intersección?

Conozco el método que puedo utilizar (encontrar las ecuaciones de sus líneas y resolverlas), pero me da pereza y quiero simplemente tener una fórmula lista para usar.

Answer 1

Un segmento de línea de $(x_1,y_1)$ a $(x_2,y_2)$

otro segmento de línea de $(x_3,y_3)$ a $(x_4,y_4)$

el conjunto de puntos del primer segmento de línea es $$A = \{ (x_1 + (x_2-x_1)u,y_1 + (y_2-y_1)u) \in \mathbb R^2 \mid u \in [0,1] \}$$

el conjunto de puntos del segundo segmento de línea es $$B = \{ (x_3 + (x_4-x_3)t,y_3 + (y_4-y_3)t) \in \mathbb R^2 \mid t \in [0,1] \}$$

queremos encontrar $$A \cap B$$ lo que significa encontrar $u \in [0,1]$ , $t \in [0,1]$ tal que $$(x_1 + (x_2-x_1)u,y_1 + (y_2-y_1)u)=(x_3 + (x_4-x_3)t,y_3 + (y_4-y_3)t)$$

dividir en componentes

$$x_1 + (x_2-x_1)u=x_3 + (x_4-x_3)t$$

$$y_1 + (y_2-y_1)u=y_3 + (y_4-y_3)t$$

resolver para $u$ eliminando $t$

$$\frac{(x_1-x_3) + (x_2-x_1)u}{(x_4-x_3)}=\frac{(y_1-y_3) + (y_2-y_1)u}{(y_4-y_3)}$$

$$\frac{(y_4-y_3)(x_1-x_3) - (x_4-x_3)(y_1-y_3)}{(x_4-x_3)(y_2-y_1) - (y_4-y_3)(x_2-x_1)} = u$$

ahora puedes encontrar la intersección de dos líneas calculando esto $u$ y comprobar que está entre 0 y 1, luego calcular t (que es fácil una vez que se conoce u) y comprobar que también está entre 0 y 1.

Answer 2

Hay una omisión en el método. Si ambos segmentos son paralelos a diferentes ejes, puede dar una respuesta incorrecta o no calcular en absoluto. Usted puede tomar por ejemplo {{0,0},{0,-3}} y {{2,3},{2,-3}} Y también debe considerar el caso cuando son paralelos

Answer 3

Mientras esperaba la respuesta, yo también lo resolví, y descubrí que era más sencillo de lo que pensaba. Si las coordenadas de un segmento son (x1, y1), (x2, y2) y las coordenadas del otro son (u1, v1), (u2, v2), entonces las coordenadas de su intersección son:

x = -1 * ((x1 - x2) * (u1 * v2 - u2 * v1) - (u2 - u1) * (x2 * y1 - x1 * y2)) / ((v1 - v2) * (x1 - x2) - (u2 - u1) * (y2 - y1))

y = -1 * (u1 * v2 * y1 - u1 * v2 * y2 - u2 * v1 * y1 + u2 * v1 * y2 - v1 * x1 * y2 + v1 * x2 * y1 + v2 * x1 * y2 - v2 * x2 * y1) / (-1 * u1 * y1 + u1 * y2 + u2 * y1 - u2 * y2 + v1 * x1 - v1 * x2 - v2 * x1 + v2 * x2)

Lo resolví usando wolfram alpha: http://www.wolframalpha.com/input/?i=%28x2-x1%29%28y-y1%29%3D%28y2-y1%29%28x-x1%29%2C%28u2-u1%29%28y-v1%29%3D%28v2-v1%29%28x-u1%29+for+x%2C+y