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) \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 sono concordi, il rettangolo è esterno alla retta
• se sono discordi, la retta interseca il rettangolo

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

• $x_{R_min} \le x_{min} \le x_{R,max}$
• $x_{R_min} \le x_{max} \le x_{R,max}$
• $x_{min} \le x_{R,min} \le x_{max}$
• $x_{min} \le x_{R,max} \le x_{max}$

e almeno delle seguenti altre

• $y_{R_min} \le y_{min} \le y_{R,max}$
• $y_{R_min} \le y_{max} \le y_{R,max}$
• $y_{min} \le y_{R,min} \le y_{max}$
• $y_{min} \le y_{R,max} \le y_{max}$