2010-10-27 19 views
5

Come posso rilevare se una linea (direzione d e -d dal punto p) e un segmento di linea (tra i punti p1 e p2) si interseca in 2D? Se lo fanno, come posso ottenere il loro punto di intersezione.Intersezione Linea e Segmento Linea

Ci sono molti esempi su come rilevare se due segmenti di linea si intersecano, ma questo dovrebbe essere un caso ancora più semplice.

ho trovato questo ma non capisco cosa è un side-esercente: http://www.loria.fr/~lazard//ARC-Visi3D/Pant-project/files/Line_Segment_Line.html

+0

Si prega di inviare le espressioni per la linea e il segmento, in modo che possiamo allineare le risposte. Tnx! –

+0

È un'attività 2D o 3D? – user434507

risposta

5

Se questo è un compito 2D (la riga e la menzogna segmento nello stesso piano e che sono specificati dal 2-dimensionale coordinate), è facile.

Costruire un vettore normale a d (la direzione della linea).

Prodotti punto calcolo d * (p1-p) e d * (p2-p). Se hanno lo stesso segno, non c'è intersezione. Se hanno segni opposti, c'è un incrocio. Con un po 'di riflessione, puoi capire come calcolare la posizione dell'intersezione in termini di p, p1-p e p2-p.

+0

Perché è necessario costruire un vettore normale a d? Non sembra che tu usi nella spiegazione successiva ... –

+0

Penso che ciò che chiami "d" nei successivi prodotti punto sia in realtà la direzione normale. –

3

È possibile verificare semplicemente se due linee (la linea e una linea del segmento di linea) intersecano e valutano il punto di intersezione.

riga 1: (x, y) (t) = p + t * d; linea 2: (x, y) (t) = P1 + k * (p2 - p1)

Nel punto di intersezione: p + t * d = p1 + k * (p2 - p1) - due equazioni (per x e per y)

Da queste equazioni è possibile trovare semplicemente i parametri k e t.Se 0 < k < 1 il punto di intersezione è a (p1, p2)

Se vedi k o T si può semplicemente calcolare il punto di intersezione da (x, y) (t) = p + t * d o (x, y) (t) = p1 + k * (p2 - p1)

0

lasciate p(x,y) e a sua direzione dell'equazione linea è D = a.x+b dove b = y - a.x

let p1(x1,y1) e p2(x2,y2) un segmento equazione è D' = a'.x+b' per qualsiasi x in [x1;x2] dove a' = (y2-y1)/(x2-x1) e b' = y2 - a'.x2 = y1 - a'.x1

hai un incrocio se c'è un x tra [x1;x2] per i quali D = D' quindi se X = (b'-b)/(a-a') appartengono alla [x1;x2] allora Y = a.X+b = a'.X+b ti dà il punto P(X,Y)

intersezione per esempio:

let p(255,255), a = 1 =>b = 0

let p1(60,179) e p2(168,54)

=>a' = -125/108

=>b' = 24596/99

=>X = (24596/99 - 0)/(1+125/108) = 115,1587983

=>Y = (24596/99 - 0)/(1+125/108) = 115,1587983

X è compreso tra 60 e 168, per cui v'è un intersecare Punto I a P(X,Y)

Problemi correlati