Wie kann ich den Schnittpunkt zweier Linien in GDI + bestimmen?

Question

Ich verwende .NET eine Anwendung mit einer Zeichenfläche zu machen, ähnlich wie Visio. Die Benutzeroberfläche verbindet zwei Objekte auf dem Bildschirm mit Graphics.DrawLine. Diese einfache Implementierung funktioniert gut, aber da die Oberfläche komplexer wird, ich brauche eine robustere Art und Weise die Objekte darzustellen. Eine dieser robusten Anforderungen ist der Schnittpunkt für zwei Linien bestimmen, so dass ich Trennung über eine Art von Grafik anzeigen kann.

Also meine Frage ist, kann jemand empfehlen, einen Weg, dies zu tun? Vielleicht mit einer anderen Technik (vielleicht GraphViz) oder einem Algorithmus?

Answer 1

Die Darstellung von Linien, die durch y = mx + c ist problematisch für Computergrafik, weil vertikale Linien m erfordern unendlich sein.

Darüber hinaus Linien in der Computergrafik einen Start- und Endpunkt, im Gegensatz zu mathematischen Linien, die in Umfang unendlich sind. Eine davon ist in der Regel nur Interesse an einer Kreuzung der Linien, wenn der Kreuzungspunkt liegt auf den beiden Liniensegmenten in Frage.

Wenn Sie zwei Liniensegmente, ein aus Vektoren x1 bis x1 + v1 und eine von Vektoren x2 x2 + v2, dann definieren:

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)

Dabei gilt für die Vektoren p = (px, py), Q = (qx, qy), p.q ist das Skalarprodukt (px py * qx + qy *). Prüfen Sie zunächst, ob (v1.v1) (v2.v2) = (v1.v2) ^ 2 -. Wenn ja, die Linien sind parallel und nicht kreuzen

Wenn sie nicht parallel sind, dann, wenn 0 <= a <= 1 und 0 <= b <= 1, der Schnittpunkt liegt auf beide der Liniensegmente, und ist durch den Punkt gegeben

x1 + a * v1

Bearbeiten Die Ableitung der Gleichungen für a und b ist wie folgt. Der Schnittpunkt erfüllt die Vektorgleichung

x1 + a*v1 = x2 + b*v2

Mit dem Punktprodukt dieser Gleichung mit v1 nehmen und mit v2, erhalten wir zwei Gleichungen:

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

, die für a und b zwei lineare Gleichungen bilden. dieses System zu lösen (durch die erste Gleichung durch v2.v2 und die zweite von v1.v1 und Subtrahieren multipliziert oder auf andere Weise) ergibt die Gleichungen für a und b.

Answer 2

dr fragen. math

Answer 3

Wenn Sie drehen Sie Ihren Referenzrahmen mit dem ersten Liniensegment auszurichten (so der Ursprung ist nun der Beginn der ersten Zeile, und der Vektor für die erste Zeile erstreckt sich entlang der X-Achse) wird die Frage, woher kommt die zweite Zeile traf die X-Achse in dem neuen Koordinatensystem. Dies ist eine viel einfachere Frage zu beantworten. Wenn die erste Zeile wird A genannt, und es wird durch A.O als Ursprung der Linie und ‚A.V‘ ist der Vektor der Linie definiert ist, so dass der Punkt A.O + A.V des Leitungsendes ist. Der Referenzrahmen kann durch die Matrix definiert werden:

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

In homogenen Koordinaten Diese Matrix stellt eine Basis für den Referenzrahmen, die die Linie A auf 0 bis 1 auf der X-Achse bildet. Wir können nun definieren die transformierte Linie B wie:

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

Wo der * Bediener richtig für homogene Koordinaten definiert (ein Vorsprung von 3 auf 2 Raum Raum in diesem Fall). Jetzt alles, was bleibt, ist zu überprüfen und sehen, wo C die X-Achse trifft, die die gleiche ist wie Y Seite der Parametergleichung von C für t Lösung:

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

Wenn t im Bereich von 0 bis 1 ist, dann trifft C die X-Achse innerhalb des Liniensegmentes. Der Platz auf der X-Achse landet durch die X-Seite der Parametergleichung für C gegeben:

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

Wenn x im Bereich von 0 bis 1 ist, dann ist der Schnittpunkt auf dem Liniensegment A. Wir können dann finden den Punkt im ursprünglichen Koordinatensystem mit:

p = A.O + A.V * x

Sie hätte natürlich zuerst zu überprüfen, um zu sehen, ob entweder Liniensegment Länge Null ist. wenn C.V.Y = 0 Auch Sie haben parallele Liniensegmente. Wenn C.V.X auch null Sie kolinearen Liniensegmente haben.