Aiutatemi con questo algoritmo, vi prego! Sto esaurendo

[x-t]

Salve a tutti.
Ho qualche problemino con un algoritmo.
Di seguito vi posto il metodo (io l'ho fatto in java, ma ovviamente non è un problema di linguaggio). Questo deve verificare se 2 segmenti si intersecano (il tutto in coordinate cartesiane).
In ingresso prende 2 coppie x, y; ogni coppia rappresenta un segmento.
La funzione deve restituire vero se si intersecano, falso altrimenti.
____________________________________________________
public boolean si_intersecano(double x11,double y11,double x21,double y21,double x12,double y12,double x22,double y22){
//primo segmento
//x11
//y11
//x21
//y21
//secondo segmento
//x12
//y12
//x22
//y22

double a= (y21-y11);
double b=(x11-x21);
double c=x11*(y11-y21)+y11*(x21-x11);//l'equazione ax + by + c=0 rappresenta la retta che contiene il segmento 1, caratterizzato dai punti: (x11,y11) (x21,y21)
double d=(y22-y12);
double e=(x12-x22);
double f=x12*(y12-y22)+y12*(x22-x12);//l'equazione dx + ey + f=0 rappresenta la retta che contiene il secondo segmento, caratterizzato dai punti: (x12,y12) (x22,y22)
double xint=0;//punto di intersezione x
if((a*e-b*d)!=0) xint=(-c*e+b*f)/(a*e-b*d);

double yint=0;//punto di intersezione y
if((a*e-b*d)!=0) yint=(-f*a+c*d)/(a*e-b*d);
if((a*e-b*d)==0 ) return false;
//se le rette sono parallele o sovrapposte ritorno falso,
//so che non è giusto, ma nel mio caso mi va bene



//ora dobbiamo verificare che il punto di intersezione appartenga ad entrambi i segmenti
double maxx1;
double maxy1;
double maxx2;
double maxy2;
double minx1;
double miny1;
double minx2;
double miny2;
if(x11>x21) {maxx1=x11; minx1=x21;} else {maxx1=x21; minx1=x11;}
if(y11>y21) {maxy1=y11; miny1=y21;} else {maxy1=y21; miny1=y11;}
if(x12>x22) {maxx2=x12; minx2=x22;} else {maxx2=x22; minx2=x12;}
if(y12>y22) {maxy2=y12; miny2=y22;} else {maxy2=y22; miny2=y12;}

if (xint<=maxx1 && xint<=maxx2 && xint>=minx1 && xint>=minx2 && yint<=maxy1 && yint<=maxy2 && yint>=miny1 && yint >= miny2) return true;
else return false;
}
__________________________________________________________
Dunque, risolvo un sistema di equazioni in 2 incognite, ottengo l'intersezione, e verifico che l'intersezione appartenga ad entrambi i segmenti.
Eppure, non funziona sempre!
Non capisco proprio dove sia il problema! sto esaurendo!
IMPORTANTE! anche se l'algoritmo considera 2 eventuali segmenti sovrapposti come segmenti che non si intersecano, questo non è importante ai miei fini, perchè nel mio caso è una situazione che non si presenta mai.
Il problema è da qualche altra parte, ma non capisco proprio dove.Aiutooooooooooo

[Perry_Rhodan]

Forse dico una cagata, nel qual caso scusami, ma non è che entra in gioco l'epsilon di macchina?
Cioè quando si confrontano dei valori double i due numeri potrebbero apparire diversi alla macchina anche se invece dovrebbero essere uguali, semplicemente perchè differiscono per una o più delle cifre meno significative a causa degli errori di arrotondamento.

es:

per la macchina A==B solo se tutti i bit di A e B coincidono

Ma se A e B hanno valori che differiscono di pochissimo tanto da essere praticamente uguali, per il computer continueranno ad essere diversi anche se questa differenza è solo dovuta agli arrotondamenti dei calcoli.

Contando l'epsilon di macchina dovresti avere:

A==B se |A-B|<= epsilon

Scusa se sono stato un po' contorto nella spiegazione :)

[Perry_Rhodan]

guarda questa faq java, forse può esserti utile:

http://www.javastaff.com/faq.php#r204

[x-t]

ok....tutto risolto....ho trovato un algoritmo già bello e pronto....
Cmq (parlo con Perry_Rhodan), no, il problema non era quello; nel mio codice si trattava solo di trovare un'intersezione e fare delle verifiche di tipo maggiore minore ecc (che non potevano riguardare, nel mio caso, valori così piccoli da poter dare questi problemi)... quindi quei tipi di problemi non potevano presentarsi. Il problema riguardava sicuramente qualche oscura maligna riga di codice scritta male che voleva farmi esaurire.
Se qualcuno, in un futuro remoto, dovesse capitare nel mio stesso problema, può trovare l'algoritmo a questo indirizzo: http://www.cg-cad.com/ttlisp132.htm (non immediato da capire, ma quello che conta è che è funzionale al massimo).
Nel mio caso l'ho portato in java (con le opportune modifiche), e ho cambiato gli int con i double, e tutto ha funzionato alla perfezione! Santo subito chi l'ha messo su internet!
Grazie comunque dell'interessamento Perry_Rhodan !

[a2000.1]

...
Se qualcuno, in un futuro remoto, dovesse capitare nel mio stesso problema, può trovare l'algoritmo a questo indirizzo: http://www.cg-cad.com/ttlisp132.htm (non immediato da capire, ma quello che conta è che è funzionale al massimo).
...


mah :rolleyes: