Esercizio 7
Realizza una funzione che dica se due segmenti collocati su un piano si intersecano.
Questo è il classico problema che con carta e matita si esprime
e si risolve all'istante ma nella pratica della programmazione occorre
sforzarsi (un po').
Nel programma principale, predisponiamo
due vettori AB e CD, ciascuno contenente le coordinate del segmento
considerato. Ad esempio dobbiamo interpretare il segmento AB come
illustrato in figura:
Questo vettore AB assieme al vettore CD (vettori di float)vengono
passati alla funzione booleana inter che restituirà 0 (false) se
i segmenti non si intersecano oppure 1 (true) se si intersecano.
Noi intendiamo risolvere il problema coerentemente con le regole
della geometria analitica. Pensiamo di individuare le rette a cui
appartengono i due vettori AB e CD:
e si appoggia alla soluzione prevista per la retta
passante per due punti:
Escludiamo subito il caso in cui i coefficienti
angolari Mab=Mcd=∞ (infinito); perchè avremmo due rette
verticali che non hanno intersezione in campo reale.
//ambedue verticali
if((ab[2]-ab[0]==0) &&(cd[2]-cd[0]==0))return 0;
Ci potrebbe essere il caso in cui le due rette
verticali sono sovrapposte, ma noi ignoriamo questo caso che implica
infinite soluzioni (mentre noi cerchiamo un'unica intersezione).
Lo stesso caso vale se Mab=Mcd=0 in senso orizzontale..
else if((ab[3]-ab[1]==0) &&(cd[3]-cd[1]==0))return
0;
//orizzontali
I casi rimanenti, riguardano il fatto in cui almeno uno dei due
coefficienti angolari non rappresenta una retta ne verticale ne
orizzontale, bensì obliqua.
Si calcolano i coefficienti angolari delle due rette.
Mab=(ab[3]-ab[1])/(ab[2]-ab[0]);
Mcd=(cd[3]-cd[1])/(cd[2]-cd[0]);
if(Mab==Mcd) return 0;
In ogni caso se le due rette sono parallele o coincidenti il risultato
viene scartato, questo perché (appunto) noi cerchiamo una sola intersezione.
Scartati questi casi rimane da valutare il caso in cui, al più,
uno solo dei coefficienti angolari è infinito (retta verticale).
In questo ultimo caso i calcoli sono diversificati a secondo se
sia AB o CD o nessuna delle due ad essere verticale.
class
intersezione{
public static void main (String args []) {
float AB[]={9,7,4,12};
float CD[]={9,5,1,1};
System.out.print(inter(AB,CD));
}//fine main
static boolean inter(float ab[],float cd[]){
float Mab,Mcd,Qab,Qcd,x0,y0;
//ambedue verticali
if((ab[2]-ab[0]==0) &&(cd[2]-cd[0]==0))return false;
else if((ab[3]-ab[1]==0) &&(cd[3]-cd[1]==0))return false;
//orizzontali
else{//almeno una non verticale e non orizzontale
Mab=(ab[3]-ab[1])/(ab[2]-ab[0]);
Mcd=(cd[3]-cd[1])/(cd[2]-cd[0]);
if(Mab==Mcd)return false;
if(ab[2]-ab[0]==0){// AB verticale
x0=ab[0];
Qcd=cd[1]-Mcd*cd[0];
y0=Mcd*x0+Qcd;
if(y0 < Math.max(ab[1],ab[3])&& y0
> Math.min(ab[1],ab[3]))
return true;
else return false;
} else if(cd[2]-cd[0]==0){//CD verticale
x0=cd[0];
Qab=ab[1]-Mab*ab[0];
y0=Mab*x0+Qab;
if(y0 < Math.max(cd[1],cd[3])&&y0 > Math.min(cd[1],cd[3]))
return true;
else return false;
}else{
Qab=ab[1]-Mab*ab[0];
Qcd=cd[1]-Mcd*cd[0];
x0=(Qcd-Qab)/(Mab-Mcd);
y0=Mab*x0+Qab;
//controllo l'appartenenza
dell'intersezione ai due segmenti
if(Mcd==0)//CD orizzontale
if(x0 < Math.max(cd[0],cd[2])&& x0 > Math.min(cd[0],cd[2]))return
true;
else return false;
else if(x0 < Math.max(ab[0],ab[2])&& x0
> Math.min(ab[0],ab[2]))
return true;
else return false;
}
}//fine else - almeno una non verticale e
non orizzontale
}//fine inter
}// fine classe
E' questo, uno dei classici dell'algoritmica che trova soluzioni anche più sintetiche e veloci ma difficilmente si scende al di sotto delle 50 righe di scritto .