edutecnica

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 .