Procedura C++ per determinare se due segmenti intersecano

Question

Ultimamente sto lavorando un po 'con la geometria computazionale e sto cercando di trovare un modo per verificare se due segmenti di linea si intersecano. Ho pensato che posso usare la direzione antioraria (CCW in breve) per determinarlo. Ecco il mio codice finora:

struct point { double x, y }; 

double CCW(point a, point b, point c) 
{ return (b.x-a.x)*(c.y-a.y) - (b.y-a.y)*(c.x-a.x); } 

int intersect(point a, point b, point c, point d) 
{ return (CCW(a,b,c)*CCW(a,b,d)<0 && CCW(c,d,b)*CCW(c,d,a)<0); } 

Il codice di cui sopra ha lavorato per i casi di test sono entrato, ed è abbastanza leggibile e molto facile da implementare. Ma dopo aver cercato sul web, ho trovato un altro modo per risolvere il problema dell'intersezione del segmento. Il codice è simile al mio, ma ha ancora alcune affermazioni if che la mia implementazione omette. Ecco il codice:

struct line { point s, e; }; 

int middle(int a, int b, int c) { 
    int t;  
    if (a > b) { 
    t = a; 
    a = b; 
    b = t; 
    } 
    if (a <= c && c <= b) return 1; 
    return 0; 
} 

int intersect(line a, line b) { 
    if ((CCW(a.s, a.e, b.s) * CCW(a.s, a.e, b.e) < 0) && 
    (CCW(b.s, b.e, a.s) * CCW(b.s, b.e, a.e) < 0)) return 1; 

    if (CCW(a.s, a.e, b.s) == 0 && middle(a.s.x, a.e.x, b.s.x) && middle(a.s.y, a.e.y, b.s.y)) return 1; 
    if (CCW(a.s, a.e, b.e) == 0 && middle(a.s.x, a.e.x, b.e.x) && middle(a.s.y, a.e.y, b.e.y)) return 1; 
    if (CCW(b.s, b.e, a.s) == 0 && middle(b.s.x, b.e.x, a.s.x) && middle(b.s.y, b.e.y, a.s.y)) return 1; 
    if (CCW(b.s, b.e, a.e) == 0 && middle(b.s.x, b.e.x, a.e.x) && middle(b.s.y, b.e.y, a.e.y)) return 1; 

    return 0; 
} 

Qualcuno potrebbe spiegare che è la differenza tra le due implementazioni, e che è più sicuro da usare? Grazie in anticipo.

Answer 1

La funzione trovata rileva anche il caso in cui i segmenti di linea si trovano all'interno della stessa linea. In tal caso, diventa un problema unidimensionale di trovare se i due segmenti di linea si sovrappongono. In questo caso il tuo codice restituirà false. Se questo è preferito o no dipende dall'applicazione.

Esempio:

point a={1,0}, b={3,0}, c={2,0}, d={4,0}; 

intersect(a,b,c,d); // your function will return false, 
        // but the one you found will return true 

La funzione che hai trovato esamina anche i casi in cui il punto finale di una linea segmento si trova lungo l'altra linea segmento:

Esempio:

point a={1,0}, b={3,0}, c={2,0}, d={2,3}; 

intersect(a,b,c,d); // your function will return false, 
        // but the one you found will return true