Come verificare se un punto (o parte) di una linea si trova all'interno o tocca un rettangolo

Question

Voglio verificare se una linea (o qualsiasi punto di una linea) si trova all'interno di un rettangolo o interseca un rettangolo.

Ho (x0, y0) e (x1, y1) come punti iniziali e finali di una linea. Inoltre, (ax, ay) e (BX, da) come i punti alto a sinistra e in basso a destra di un rettangolo

Per esempio,

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

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


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

Qualcuno può suggerire come fare questo? Non voglio sapere che punto è, voglio solo sapere se è lì o no.

Grazie mille per l'aiuto

Answer 1

Il primo e il terzo caso sono banali - semplicemente ritornare vero se sia punto finale della linea è all'interno della scatola (vale a dire> Ax e Ay, < bx e da).

Il secondo presenta un problema: non possiamo più fare affidamento sugli endpoint della nostra linea. In questo caso, dovremo testare la linea con ogni bordo del rettangolo.

L'equazione per la nostra linea sarà (x1 - x0)*x + (y1 - y0)*y + x0*y0 - x1*y1 = 0 e possiamo costruire un'equazione simile per ciascun lato del rettangolo utilizzando gli angoli. In seguito, sostituendo l'equazione per i lati del rettangolo nella nostra linea ci darà l'intersezione.

Infine, controlliamo che il punto si trovi entro i limiti del lato del rettangolo e, analogamente, nel segmento di linea che stiamo considerando.

Esiste un resoconto più dettagliato di questo in this discussion.