Cómo comprobar si algún punto (o parte) de una línea está dentro o toca un rectángulo

Question

Quiero comprobar si una línea (o cualquier punto de una línea) está dentro de un rectángulo o se cruza con un rectángulo.

Tengo (x0, y0) y (x1, y1) como puntos de inicio y final de una línea. También , (Ax, Ay) y (Bx, By) como los puntos superior izquierda e inferior derecha de un rectángulo

Por ejemplo,

 ____________ 
    |   | 
---|-----  | Result: true 
    |   | 
    |____________| 

    /
    _/__________ 
|/   | 
/   |  Result: true 
/|   | 
|____________| 


    ____________ 
    |   | 
    | -------- | Result: true 
    |   | 
    |____________| ----------  Result: false 

Puede alguien sugerir cómo hacer esto? No quiero saber qué punto es eso, solo quiero saber si está allí o no.

Muchas gracias por la ayuda

Answer 1

El primer y tercer casos son triviales - simplemente devuelve true si los puntos finales de la línea se encuentra dentro de la caja (es decir,> Ax y Ay, < BX y por).

El segundo presenta un problema: ya no podemos confiar en los puntos finales de nuestra línea. En este caso, tendremos que probar la línea con cada borde del rectángulo.

La ecuación para nuestra línea será (x1 - x0)*x + (y1 - y0)*y + x0*y0 - x1*y1 = 0, y podemos construir una ecuación similar para cada lado del rectángulo usando las esquinas. A continuación, al sustituir la ecuación por los lados del rectángulo en nuestra línea, obtendremos la intersección.

Finalmente, verificamos que el punto esté dentro de los límites del lado del rectángulo, y también dentro del segmento de línea que estamos considerando.

Hay una explicación más detallada de esto en this discussion.