Calcolo delle intersezioni tra i segmenti di linea

Question

Ci sono un sacco di domande sulle intersezioni tra i segmenti di linea qui su Stackowerflow e eccone un'altra! Ci dispiace, ma ho bisogno di aiuto per capire come calcolare le intersezioni. Ho letto molte delle domande qui e ho visto diversi esempi su altri siti web, ma sono ancora confuso e non capisco! Non mi piace copiare e incollare il codice senza come funzionano le cose.

Finora so che ho intenzione di confrontare i punti di ogni segmento di linea come Ax, Ay, Bx, By, Cx, Cy, Dx, Dy. Qualcuno potrebbe spiegare per me quello che sto per calcolare, quale sarebbe il risultato del calcolo se c'è un'intersezione?

Questo è uno dei codici di esempio che ho visto. Immagino di non aver bisogno del punto di intersezione, solo per sapere se le linee si intersecano o meno.

public static Point lineIntersect(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4) { 
    double denom = (y4 - y3) * (x2 - x1) - (x4 - x3) * (y2 - y1); 
    if (denom == 0.0) { // Lines are parallel. 
    return null; 
    } 
    double ua = ((x4 - x3) * (y1 - y3) - (y4 - y3) * (x1 - x3))/denom; 
    double ub = ((x2 - x1) * (y1 - y3) - (y2 - y1) * (x1 - x3))/denom; 
    if (ua >= 0.0f && ua <= 1.0f && ub >= 0.0f && ub <= 1.0f) { 
     // Get the intersection point. 
     return new Point((int) (x1 + ua*(x2 - x1)), (int) (y1 + ua*(y2 - y1))); 
    } 

    return null; 
    } 

Devo anche calcolare un valore mediano come in questo esempio di codice?

For lines through points (x0,y0) and (x1,y1), let xm = (x0+x1)/2, ym = (y0+y1)/2 (median of line segment). 
Then a = (y1-y0) and b = (x0-x1). 
If you evaluate c = a(x-xm)+b(y-ym), c=0 for (x,y) on the line, and the sign(c) tells you which side a point is on 

Answer 1

Il primo pezzo di codice che spettacolo si basa sul vettore cross-prodotto, che è stato spiegato qui How do you detect where two line segments intersect? in grande dettaglio.

IMO, un modo più semplice per capirlo è risolvere un sistema di equazioni. In primo luogo, guarda le linee in generale e poi ritaglia i segmenti da esse. Sotto uso le notazioni per determinati segmenti ((x1, x2), (y1, y2)) e ((x3, x4), (y3, y4)).

1. Verifica se una delle righe è verticale (x1 == x2 o x3 == x4).

   a. Se entrambi sono verticali e x1 != x3, quindi nessuna intersezione.

   b. Se entrambi sono verticali e x1 == x3, verificare se (y1, y2) e (y3, y4) si sovrappongono.

   c. Se solo uno è verticale (ad esempio, il primo), quindi crea l'equazione della seconda riga (come descritto di seguito), trova il punto in cui due linee si intersecano (sostituendo x1 nell'equazione della seconda riga) e verifica se questo punto è all'interno di entrambi i segmenti (simile al punto 5).

   d. In caso contrario, procedere.

2. Utilizzare le coordinate dei punti per creare equazioni di linee nel modulo y = a*x + b (come here).

   a1 = (y2-y1)/(x2-x1) 
   b1 = y1 - a1*x1 
   a2 = (y4-y3)/(x4-x3) 
   b2 = y3 - a2*x3 
   

3. Controllare se le linee sono parallele (stessa pendenza a). In caso affermativo, controlla se hanno intercettazione uguale allo b. In caso affermativo, verificare se i segmenti 1D (x1, x2) e (x3, x4) si sovrappongono. Se sì, i tuoi segmenti si sovrappongono. Il caso in cui le linee sono parallele può essere ambiguo. Se si sovrappongono, puoi considerarlo come un'intersezione (può anche essere un punto se le loro estremità si toccano) o no. Nota: se stai lavorando con i float, sarebbe un po 'più complicato, immagino che vorresti ignorarlo. Nel caso in cui si hanno solo numeri interi Verificando a1 = a2 è equivalente a:

   if((y2-y1)*(x4-x3) == (x2-x1)*(y4-y3)) 
   

4. Se le linee non sono parallele. Il punto di intersezione equivale a una soluzione di un sistema di equazioni che rappresentano le due linee.In realtà, l'intersezione tra y = a1*x + b1 e y = a2*x + b2 significa sostanzialmente che entrambe le equazioni sono valide. Risolvi questo sistema equiparando i due lati destro e ti darà il punto di intersezione. In realtà, è necessario solo x coordinate del punto di intersezione (disegnarlo e vedrete perché):

   x0 = -(b1-b2)/(a1-a2) 
   

5. ultimo passo è quello di verificare se il punto di intersezione x0 bugie all'interno di entrambi i segmenti. Cioè, min(x1, x2) < x0 < max(x1, x2) e min(x3, x4) < x0 < max(x3, x4). Se sì, le tue linee si intersecano!

Answer 2

public void fixData() 
{ 
    slope = (p2.getY() - p1.getY())/(p2.getX() - p1.getX()); 
    yInt = p1.getY() - slope * p1.getX(); 
    xInt = (-yInt)/slope; 
} 

Answer 3

ho davvero @ risposta di sashkello e trovate per essere più intuitiva e facile da spiegare che l'attuazione vettore. In particolare quando si aggiunge questo tipo di codice a un codice base.

Lo proverò dicendo che è possibile utilizzare il metodo Helper di Line2D di Java.

Line2D.linesIntersect(double x1, double y1, 
         double x2, double y2, 
         double x3, double y3, 
         double x4, double y4) 

L'unico inconveniente è che richiede di prendere in considerazione i segmenti da intersecano anche quando sono tocchino (su entrambi i punti finali e la linea stessa).

Ad esempio, le linee sottostanti sono considerate intersecanti perché condividono il punto (1,1).

L1 = [(0,0),(1,1)] 
L2 = [(1,1),(2,3)] 

Se questo è un problema è possibile aggiungere 4 controlli per vedere se i punti sono uguali.

Se hai dubbi su un punto che cade su un punto all'interno della linea, questo richiede un po 'più di lavoro e forse stai meglio implementandolo tu stesso in modo da poter eseguire i controlli nell'algoritmo stesso.

Se nessuno di questi casi limite riguarda te, allora Line2D.linesIntersect è per te. :)