Dato un segmento delimitato dai punti $P_1 \left( x_1, y_1 \right)$ e $P_2 \left( x_2, y_2 \right)$, verifichiamo se interseca un rettangolo di coordinate $R_1 \left( x_{R,1}, y_{R,1} \right)$, $R_2 \left( x_{R,2}, y_{R,2} \right)$, $R_3 \left( x_{R,3}, y_{R,3} \right)$ e $R_4 \left( x_{R,4}, y_{R,4} \right)$. In realtà il metodo che vedremo può essere esteso ad un poligono irregolare qualsiasi.
Affronteremo la verifica dell'intersezione tra un segmento e un rettangolo con un doppio controllo:
L'equazione della retta passante per il segmento è data da
$$r \left( x, y \right) = \left( y_2 - y_1 \right) \left( x - x_1 \right) - \left( x_2 - x_1 \right) \left( y - y_1 \right) = 0 $$
Analizzando il segno di $r \left( x_{R,1}, y_{R,1} \right)$, $r \left( x_{R,2}, y_{R,2} \right)$, $r \left( x_{R,3}, y_{R,3} \right)$ e $r \left( x_{R,4}, y_{R,4} \right)$ possiamo verificare se il rettangolo è esterno o meno alla retta:
Se La prima verifica ha avuto esito negativo, sicuramente non c'è intersezione tra il rettangolo e il segmento. In caso contrario, prima di poter affermare che l'intersezione c'è, abbiamo una ulteriore verifica.
Facciamo prima di tutto le posizioni
$$x_{min} = min \left\{ x_{1}, x_{2} \right\}$$
$$x_{max} = min \left\{ x_{1}, x_{2} \right\}$$
$$x_{R,min} = min \left\{ x_{R,1}, x_{R,2}, x_{R,3}, x_{R,4} \right\}$$
$$x_{R,max} = max \left\{ x_{R,1}, x_{R,2}, x_{R,3}, x_{R,4} \right\}$$
$$y_{R,min} = min \left\{ y_{R,1}, y_{R,2}, y_{R,3}, y_{R,4} \right\}$$
$$y_{R,max} = max \left\{ y_{R,1}, y_{R,2}, y_{R,3}, y_{R,4} \right\}$$
Le due proiezioni si intersecano se si verifica almeno una delle seguenti condizioni
e almeno delle seguenti altre