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:

• se il rettangolo è esterno alla retta passante per il segmento, sicuramente non c'è intersezione tra il segmento e il rettangolo
• la precedente condizione è necessaria per l'intersezione, ma non sufficiente; dovremo verificare anche che le proiezioni del segmento e del rettangolo sui due assi cartesiani si intersecano.

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) y + \left( x_2 - x_1 \right) y_1 = 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 sono concordi, il rettangolo è esterno alla retta
• se sono discordi, la retta interseca il rettangolo