Encontrar los puntos de intersección entre un rectángulo y un segmento

Question

Quiero encontrar los puntos de intersección (máximo 2) entre un segmento (una línea de longitud finita definida por un punto inicial y otro final) y un rectángulo. Ambos están "flotando" en el espacio bidimensional sin estar acotados al centro (0,0) ni a ninguno de los ejes.

¿Hay alguna manera más fácil de encontrar los puntos de intersección que no sea continuar con todas las líneas para que sean infinitas, encontrar los puntos de intersección entre las líneas del rectángulo y la línea del segmento y luego comprobar si los puntos están en el perímetro del rectángulo?

El rectángulo está definido por 4 puntos.

Answer 1

Al final, eso es lo que tendrás que hacer.

Pero si, por ejemplo, esperas que una intersección sea rara, puede valer la pena hacer primero una prueba más simple si hay una intersección en absoluto. Si el segmento de línea viene dado por los puntos extremos $(x_1, y_1)$ y $(x_2, y_2)$ entonces un punto $(x,y)$ está en la misma línea recta si $u\cdot x+v\cdot y+w=0$ con $u:=y_2-y_1$ , $v:=x_1-x_2$ , $w:=x_1 y_2-x_2y_1$ . Además, los dos semiplanos definidos por la línea pueden distinguirse por si $u\cdot x+v\cdot y+w>0$ o $u\cdot x+v\cdot y+w<0$ . Así: introduce los cuatro vértices de tu rectángulo en la expresión $u\cdot x+v\cdot y+w$ . Si los cuatro vértices producen un resultado negativo (o todos los foru producen un resultado positivo), entonces trivialmente no hay ninguna intersección.