Incrocio
Punto di intersezione di linee
a1, b1, c1 - coefficienti della prima riga,
a2, b2, c2 - coefficienti della seconda riga,
x, y - punto di intersezione.
\(x = {-(c1 \cdot b2 - c2 \cdot b1) \over (a1 \cdot b2 - a2 \cdot b1)} \\ y = {-(a1 \ cdot c2 - a2 \cdot c1) \over (a1 \cdot b2 - a2 \cdot b1)} \)
Sappiamo già come controllare le linee per l'intersezione (non sono parallele) e trovare il loro punto di intersezione.
Ora impariamo come farlo con i segmenti.
Innanzitutto, impariamo come verificarne semplicemente l'intersezione.
I segmenti si intersecano se le estremità di uno sono sui lati opposti dell'altro e viceversa (questo è facilmente verificabile dal prodotto incrociato). L'unico caso in cui ciò non funzionerà: i segmenti si trovano su una linea retta. Per questo, è necessario verificare l'intersezione del cosiddetto. bounding box (bounding box del segmento) - controlla l'intersezione della proiezione dei segmenti su X e Y.
assi.
Ora che sappiamo come controllare i segmenti per l'intersezione, impariamo a trovare il punto (o segmento) della loro intersezione:
- se non si intersecano, allora è chiaro che tale punto non esiste;
- altrimenti, costruiremo linee rette su cui giacciono questi segmenti.
Se sono paralleli, allora i segmenti giacciono sulla stessa linea, e dobbiamo trovare il segmento di intersezione - dal massimo dei bordi di sinistra dei segmenti al minimo dei bordi di destra (il punto è minore dell'altro punto, se è a sinistra, in caso di uguaglianza X-coordinate - se è inferiore).
Se le linee non sono parallele, trova il punto della loro intersezione e restituiscilo.