Come posso determinare il punto di intersezione di due linee in GDI +?

Question

Sto usando .NET per creare un'applicazione con una superficie di disegno, simile a Visio. L'interfaccia utente collega due oggetti sullo schermo con Graphics.DrawLine. Questa semplice implementazione funziona bene, ma quando la superficie diventa più complessa, ho bisogno di un modo più robusto per rappresentare gli oggetti. Uno di questi solidi requisiti è determinare il punto di intersezione per due linee in modo che io possa indicare la separazione tramite un qualche tipo di grafico.

Quindi la mia domanda è: qualcuno può suggerire un modo per farlo? Forse con una tecnica diversa (forse GraphViz) o un algoritmo?

Answer 1

La rappresentazione delle linee con y = mx + c è problematica per la computer grafica, poiché le linee verticali richiedono che m sia infinito.

Inoltre, le linee nella computer grafica hanno un punto iniziale e finale, a differenza delle linee matematiche di estensione infinita. Di solito si è interessati a un incrocio di linee solo se il punto di incrocio si trova su entrambi i segmenti di linea in questione.

Se hai due segmenti di linea, uno dai vettori x1 a x1 + v1 e uno dai vettori x2 a x2 + v2, allora definisci:

a = (v2.v2 v1.(x2-x1) - v1.v2 v2.(x2-x1)) / ((v1.v1)(v2.v2) - (v1.v2)^2)
b = (v1.v2 v1.(x2-x1) - v1.v1 v2.(x2-x1)) / ((v1.v1)(v2.v2) - (v1.v2)^2)

dove per i vettori p = (px, py), q = (qx, qy), p.q è il prodotto punto (px * qx + py * qy). Prima controlla se (v1.v1) (v2.v2) = (v1.v2) ^ 2 - in tal caso, le linee sono parallele e non si incrociano.

Se non sono paralleli, allora se 0 < = a < = 1 e 0 < = b < = 1, il punto di intersezione si trova su entrambi i segmenti di linea, ed è dato dal punto

x1 + a * v1

Modifica La derivazione delle equazioni per aeb è la seguente. Il punto di intersezione soddisfa l'equazione del vettore

x1 + a*v1 = x2 + b*v2

Prendendo il prodotto punto di questa equazione con v1 e con v2, otteniamo due equazioni:

v1.v1*a - v2.v1*b = v1.(x2-x1)
v1.v2*a - v2.v2*b = v2.(x2-x1)

che formano due equazioni lineari per a e b. Risolvere questo sistema (moltiplicando la prima equazione per v2.v2 e la seconda per v1.v1 e sottraendo, o altrimenti) fornisce le equazioni per a e b.

Answer 2

chiedi al dott. matematica

Answer 3

Se si ruota il riquadro di riferimento per allinearlo con il primo segmento di linea (quindi l'origine è ora l'inizio della prima linea e il vettore per la prima linea si estende lungo l'asse X) la domanda diventa, dove la seconda linea ha colpito l'asse X nel nuovo sistema di coordinate. Questa è una domanda molto più semplice a cui rispondere. Se la prima linea è chiamata A ed è definita da A.O come l'origine della linea e "A.V" è il vettore della linea in modo che A.O + A.V sia il punto finale della linea. Il frame di riferimento può essere definito dalla matrice:

    | A.V.X   A.V.Y   A.O.X |
M = | A.V.Y  -A.V.X   A.O.Y |
    |   0       0       1   |

In coordinate omogenee questa matrice fornisce una base per il frame di riferimento che mappa la linea da B a 0 a 1 sull'asse X. Ora possiamo definire la linea trasformata * come:

C.O = M*(B.O)
C.V = M*(B.O + B.V) - C.O

Dove l'operatore C correttamente definito per coordinate omogenee (in questo caso una proiezione da 3 spazi a 2 spazi). Ora non resta che verificare e vedere dove Y colpisce l'asse X, il che equivale a risolvere t lato dell'equazione parametrica di x per C.V.Y = 0:

C.O.Y + t * C.V.Y = 0
     -C.O.Y
t = --------
      C.V.Y

Se C.V.X è compreso nell'intervallo da 0 a 1, allora <=> colpisce l'asse X all'interno del segmento di linea. Il punto in cui atterra sull'asse X è dato dal lato X dell'equazione parametrica per <=>:

x = C.O.X + t * C.V.X

Se <=> è compreso nell'intervallo da 0 a 1, l'intersezione si trova sul segmento di linea <=>. Possiamo quindi trovare il punto nel sistema di coordinate originale con:

p = A.O + A.V * x

Ovviamente dovresti prima controllare per vedere se uno dei segmenti di linea ha lunghezza zero. Anche se <=> hai segmenti di linea paralleli. Se <=> è anche zero, hai segmenti di linea colinear.