Code zum Berechnen der Schnittpunkte von 2 Geraden

    • VB.NET

    Es gibt 11 Antworten in diesem Thema. Der letzte Beitrag () ist von RodFromGermany.

      Code zum Berechnen der Schnittpunkte von 2 Geraden

      Zum Berechnen der Schnittpunkte zweier Geraden, muss man zuerst die Geraden definieren. Dies geschieht hier über zwei Punkte, Start- und Endpunkt einer Linie.

      Wenn man zwei Geraden definiert hat, kann man mit Hilfe der Operatoren "=" bzw. "<>" überprüfen ob es sich um die selbe Gerade handelt oder nicht.

      Die Klasse verfügt noch über zwei Funktionen:
      parallel_zu: Überprüft ob zwei Geraden Parallel zueinander liegen (kein Schnittpunkt)

      schnittpunkt_mit: Berechnet den Schnittpunkt von dieser und einer zweiten Gerade

      Spoiler anzeigen

      VB.NET-Quellcode

      1. Public Structure Point2d
      2. Public Property X as Double
      3. Public Property Y as Double
      4. End Structure
      6. Public Class Gerade
      7. ''' <summary>
      8. ''' Definiert eine Gerade anhand von zwei Punkten
      9. ''' </summary>
      10. ''' <param name="p1">Erster Punkt</param>
      11. ''' <param name="p2">Zweiter Punkt</param>
      12. ''' <remarks></remarks>
      13. Public Sub New(ByRef p1 As Point2d, ByRef p2 As Point2d)
      14. dx = p1.X - p2.X
      15. dy = p1.Y - p2.Y
      16. a = dy
      17. b = -dx
      18. c = -(a * p1.X + b * p1.Y)
      19. End Sub
      22. 'Anhand dieser Werte wird die gerade definiert
      23. Private ReadOnly dx As Double
      24. Private ReadOnly dy As Double
      25. Private ReadOnly a As Double
      26. Private ReadOnly b As Double
      27. Private ReadOnly c As Double
      29. ''' <summary>
      30. ''' Vergleicht ob es sich um zwei gleiche Geraden handelt
      31. ''' </summary>
      32. ''' <param name="G1">Erste Gerade</param>
      33. ''' <param name="G2">Zweite Gerade</param>
      34. ''' <returns>Gibt "True" zurück wenn beide Geraden gleich sind</returns>
      35. ''' <remarks></remarks>
      36. Public Shared Operator =(ByVal G1 As Gerade, ByVal G2 As Gerade) As Boolean
      37. Return Abs((G1.a * G2.b) - (G1.b * G2.a)) <= Double.Epsilon AndAlso Abs((G1.b * G2.c) - (G1.c * G2.b)) <= Double.Epsilon AndAlso Abs((G1.a * G2.c) - (G1.c * G2.a)) <= Double.Epsilon
      38. End Operator
      40. ''' <summary>
      41. ''' Vergleicht ob es sich nicht um zwei gleiche Geraden handelt
      42. ''' </summary>
      43. ''' <param name="G1">Erste Gerade</param>
      44. ''' <param name="G2">Zweite Gerade</param>
      45. ''' <returns>Gibt "True" zurück wenn beide Geraden nicht gleich sind</returns>
      46. ''' <remarks></remarks>
      47. Public Shared Operator <>(ByVal G1 As Gerade, ByVal G2 As Gerade) As Boolean
      48. Return Not Abs((G1.a * G2.b) - (G1.b * G2.a)) <= Double.Epsilon AndAlso Abs((G1.b * G2.c) - (G1.c * G2.b)) <= Double.Epsilon AndAlso Abs((G1.a * G2.c) - (G1.c * G2.a)) <= Double.Epsilon
      49. End Operator
      51. ''' <summary>
      52. ''' Prüft ob eine Gerade parallel zu der aktuellen Gerade ist
      53. ''' </summary>
      54. ''' <param name="G">Die zweite Gerade</param>
      55. ''' <returns>Gibt "True" zurück wenn die Geraden parallel sind</returns>
      56. ''' <remarks></remarks>
      57. Public Function parallel_zu(ByRef G As Gerade) As Boolean
      58. return Abs((Me.a * G.b) - (G.a * Me.b)) <= Double.Epsilon andalso ((G.a * Me.b) <= -Double.Epsilon andalso (G.a * Me.b) >= double.Epsilon)
      59. End Function
      61. ''' <summary>
      62. ''' Errechnet den Schnittpunkt einer Gerade mit der aktuellen Gerade
      63. ''' </summary>
      64. ''' <param name="G">Die zweite Gerade</param>
      65. ''' <returns>Gibt die Koordinaten des Schnittpunkts zurück</returns>
      66. ''' <remarks></remarks>
      67. Public Function schnittpunkt_mit(ByRef G As Gerade) As Point2d
      68. If Me.parallel_zu(G) Then Throw New Exception("Geraden verlaufen Parallel!")
      69. If Me = G Then Throw New Exception("Beide Geraden sind gleich!")
      70. If Me.a <> 0 Then
      71. Dim y As Double = (G.a / Me.a * Me.c - G.c) / (G.b - G.a / Me.a * Me.b)
      72. Dim x As Double = (Me.b * y + Me.c) / (-Me.a)
      73. Return New Point2d With {.X = x, .Y = y}
      74. Else
      75. Return G.schnittpunkt_mit(Me)
      76. End If
      77. End Function
      78. End Class


      Ein kurzes Anwendungsbeispiel:

      Spoiler anzeigen

      VB.NET-Quellcode

      1. Sub test()
      2. Dim Startpunkt1 As New Point2d With {.X = 1, .Y = 5}
      3. Dim Endpunkt1 As New Point2d With {.X = 9, .Y = 4.2}
      4. Dim G1 As New Gerade(Startpunkt1, Endpunkt1)
      6. Dim Startpunkt2 As New Point2d With {.X = 81, .Y = 12}
      7. Dim Endpunkt2 As New Point2d With {.X = 6, .Y = 32}
      8. Dim G2 As New Gerade(Startpunkt2, Endpunkt2)
      10. Dim Schnittpunkt As Point2d
      12. If Not G1.parallel_zu(G2) Then
      13. Schnittpunkt = G1.schnittpunkt_mit(G2)
      14. End If
      16. MsgBox("X = " & Schnittpunkt.X & vbCrLf & "Y = " & Schnittpunkt.Y)
      17. End Sub


      Mit freundlichen Grüßen
      Steve
      SWYgeW91IGNhbiByZWFkIHRoaXMsIHlvdSdyZSBhIGdlZWsgOkQ=

      Weil einfach, einfach zu einfach ist! :D

      Dieser Beitrag wurde bereits 4 mal editiert, zuletzt von „BiedermannS“ ()

      Ich geb mal meine Senf dazu:

      1. Mathematik

      In der Mathematik gibt es eine einfache Methode Geraden darzustellen: y-Achsenabschnitt (b) und Steigung (a):
      y(x) = a*x + b
      Leider kann man hiermit keine senkrechten Geraden darstellen. ( a = unendlich)

      Sehe ich das richtig, dass du 5 Double Variablen verwendest???

      2. Umsetzung:
      Ich würde in der Klasse nur a und b speichern. Eine Gerade aus 2 Punkten kannst du ja weiterhin mit dem entsprechenden Konstruktor erstellen.
      - Konstruktor New(Point,point)
      - Konstruktor New(Steigung as double, Abschnitt as double)

      2 Geraden sind gleich, wenn sie den gleichen y-Abschnitt und die gleiche Steigung haben.

      WICHTIG: Das Überprüfen auf Gleichheit macht bei Geraden praktisch keinen Sinn, da du Double Variablen auf Gleichheit überprüfem musst. Da kommt es sehr sehr schnell zu Rundungsfehlern. Mathematisch gleiche Geraden werden folglich fast immer als ungleich dargestellt. Beim Überprüfen auf Parallelität hat man das gleiche Problem.

      3. Programmiertechnisch:
      Die If Abfrage ist 100% unnötig:

      VB.NET-Quellcode

      1. Public Shared Operator <>(ByVal G1 As Gerade, ByVal G2 As Gerade) As Boolean
      2. If G1.a * G2.b = G1.b * G2.a AndAlso G1.b * G2.c = G1.c * G2.b AndAlso G1.a * G2.c = G1.c * G2.a Then
      3. Return False
      4. Else
      5. Return True
      6. End If
      7. End Operator

      besser so (Not macht true->false und false-> true):

      VB.NET-Quellcode

      1. Public Shared Operator <>(ByVal G1 As Gerade, ByVal G2 As Gerade) As Boolean
      2. Return Not (G1.a * G2.b = G1.b * G2.a AndAlso G1.b * G2.c = G1.c * G2.b AndAlso G1.a * G2.c = G1.c * G2.a)
      3. End Operator

      Hier mal meine Antworten: :)

      1)
      Wie du selbst richtig erkannt hast, Kann man keine Geraden damit darstellen, darum verwende ich auch die komplexere Formel ;)
      Ja ich verwende 5 Double Variablen, diese definieren die Gerade.


      2)
      Ich speichere nicht nur a und b, da ich sonst bei jeder Berechnung die Parameter der Geraden erneut ausrechnen muss. Was meines Erachtens unnötige Prozessorzeit beansprucht.
      Zwei Geraden auch gleich wenn sie den, definierten Regeln entsprechen. D.H.: Je nach dem in welcher Form du die Gerade definiert hast (Formel) gibt es verschiedene Methoden die Gleichheit zu überprüfen.

      Das Überprüfen ob es sich bei zwei Geraden um zwei gleiche Geraden handelt macht sehr wohl Sinn, da man nicht immer schon im vorhinein weis wo die Geraden liegen. Und bei zwei gleichen Geraden würden sich unendlich viele Schnittpunkte ergeben. Wenn sie nicht zu 100% gleich sind, dann gibts auch nur einen Schnittpunkt und somit kein Problem mehr.

      Wie genau die Daten eingegeben werden ist nicht zwingend vorgeschrieben. (Es können auch ganze Werte verwendet werden :))

      Da in meinem Code nicht gerundet wird, kommt es erst bei den Kommastellen zu Rundungsfehlern, die für Normalsterbliche (Also Leute die nicht in der Feinmechanik o.Ä. arbeiten) im tragbaren Bereich liegen (Kommt ja doch wieder auf die Eingabe der Daten an ^^)

      Zu den Zwei Konstruktoren kann ich nur sagen: Wer es umbedingt braucht, kann es sich nach-implementieren. Der Code ist nicht für Mathematiker gedacht, sonder für Leute die schnell einen Schnittpunkt zweier geraden brauchen. In diesem Fall, ausgehend von zwei Linien.

      3) Das ist wohl eher ein kleiner Schönheitsfehler der mir hier passiert ist, werd es gerne ausbessern.


      Alles in allem ist der Code eine Grundlage, die man gerne verbessern/verändern kann.

      Der Code kann:
      Eine Gerade anhand von 2 Punkten definieren und das in jedem Winkel.
      Die Gleichheit zweier Geraden prüfen.
      Die Parallelität zweier Geraden prüfen.
      Den Schnittpunkt zweier Geraden prüfen.

      Alles weitere liegt nun an den Programmierern die den Code verwenden wollen. (Ist übrigens OpenSource :))
      SWYgeW91IGNhbiByZWFkIHRoaXMsIHlvdSdyZSBhIGdlZWsgOkQ=

      Weil einfach, einfach zu einfach ist! :D

      BiedermannS schrieb:

      Da in meinem Code nicht gerundet wird

      Es macht nix, ob DU rundest. Das Problem ist das Darstellungsformat des Double-Datentyps (IEEE-754). Das ist halt dummerweise per se schon ungenau (wegen der Darstellung des Decimalsystems über das Binärsystem). Und wenn du VERGLEICHST, werden auch ALLE Nachkommastellen berücksichtig, egal wie irrelevant sie sein mögen.

      bsp:

      VB.NET-Quellcode

      1. Debug.Print((0.1# / 0.3#).ToString)
      2. Debug.Print((1.0# / 3.0#).ToString)
      4. If 0.1# / 0.3# <> 1.0# / 3.0# Then
      5. MessageBox.Show("WTF!")
      6. End If


      Und nu? Die Steigung (zb) wäre EIGENTLICH identisch, aber de facto ist sie es nicht, weil halt automatisch Rundungsfehler auftreten.
      Entweder baust du also ein Epsilon ein, oder du rechnest tatsächlich mit Brüchen.

      BiedermannS schrieb:

      Alles weitere liegt nun an den Programmierern die den Code verwenden wollen.
      Du bietest den Code hier an.
      Ich denke, Du bist auch zumindest für den Anfang für die Pflege Deines Codes verantwortlich.

      Zum Thema senkrechte Geraden:
      Dieser Punkt ist für die Bildverarbeitung unabdingbar, da solltest Du Dich klar positionieren.
      Ein Ansatzpunkt wäre, bei Geraden mit einem Anstieg größer 1 / kleiner -1 die Mathematik von y = ax + b nach x = Ay + B umzudrehen und dies entsprechend zu berücksichtigen.
      Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
      Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
      Ein guter .NET-Snippetkonverter (der ist verfügbar).
      Programmierfragen über PN / Konversation werden ignoriert!

      Ich bin mir dessen bewusst das ich für meinen Code verantwortlich bin, aber hauptsächlich für das beheben von Fehlern.
      Der Code macht was er soll, auch mit senkrechten Geraden. Und überhaupt habe ich auch keine Library vorgestellt, sondern ein Snippet zum berechen von Schnittpunkten von Geraden.

      Das Double So ungenau arbeitet war mir nicht (in diesem Ausmaß) bewusst, ich werd hier noch etwas ändern.

      Nur was du mit dem Epsilon meins, ist mir momentan nicht klar. (Steh wohl gerade neben mir :S)
      SWYgeW91IGNhbiByZWFkIHRoaXMsIHlvdSdyZSBhIGdlZWsgOkQ=

      Weil einfach, einfach zu einfach ist! :D

      BiedermannS schrieb:

      Und überhaupt habe ich auch keine Library vorgestellt, sondern ein Snippet zum berechen von Schnittpunkten von Geraden.

      Wer sollte denn diesen Deinen Code benutzen oder besser gebrauchen können?
      Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
      Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
      Ein guter .NET-Snippetkonverter (der ist verfügbar).
      Programmierfragen über PN / Konversation werden ignoriert!

      Ich brauche diesen Code in einem meiner Programme und wollte Ihn mit der Öffentlichkeit teilen.

      Wer den Code nun benutzt oder nicht, kann ich dir nicht sagen. Aber ich bin mir sicher, das es noch mehr Leute gibt die nicht wissen wie sie so eine Schnittpunktrechnung in vb.net implementieren.

      Ausserdem glaube ich nicht das dies hier zur Debatte steht, da es hier um den Code geht und nicht darum wer diesen verwendet.
      SWYgeW91IGNhbiByZWFkIHRoaXMsIHlvdSdyZSBhIGdlZWsgOkQ=

      Weil einfach, einfach zu einfach ist! :D

      Bin heut hierüber gestolpert, und erinnerte mich, dass Fließkommazahlen in .Net auch für +-Unendlich definiert sind, ja sogar einen Wert "not defined" gibt es!

      Das hat natürlich eklatante Auswirkung auf eine Gerade-Klasse, denn da kann man fröhlich die Steigungsgleichung nutzen, und eine Gerade ist mit nur 2 Fließkomma-Feldern definiert: C (=Schnittpunkt Y-Achse) und M (Steigung).

      VB.NET-Quellcode

      1. <Diagnostics.DebuggerDisplay("{c} {Grade}")> _
      2. Public Structure Straight
      4. Public Grade As Single '(dt: Steigung)
      6. ''' <remarks>if Grade IsInfinite then C equals the only existing X-Value. Otherwise C equals Y at X=0 </remarks>
      7. Private C As Single
      9. Public Sub New(ByVal p1 As PointF, ByVal p2 As PointF)
      10. Me.New(p1.X, p1.Y, p2.X, p2.Y)
      11. End Sub
      12. Public Sub New(ByVal X1 As Single, ByVal Y1 As Single, ByVal X2 As Single, ByVal Y2 As Single)
      13. Grade = (Y2 - Y1) / (X2 - X1)
      14. If Single.IsNegativeInfinity(Grade) Then Grade = Single.PositiveInfinity
      15. C = If(Single.IsInfinity(Grade), X1, Y1 - (X1 * Grade))
      16. End Sub
      18. Public Shared Operator =(ByVal G1 As Straight, ByVal G2 As Straight) As Boolean
      19. Return G1.Grade = G2.Grade AndAlso G1.C = G2.C
      20. End Operator
      21. Public Shared Operator <>(ByVal G1 As Straight, ByVal G2 As Straight) As Boolean
      22. Return Not G1 = G2
      23. End Operator
      25. Public Function ParallelTo(ByVal g2 As Straight) As Boolean
      26. Return Math.Round(Grade, 4) = Math.Round(g2.Grade, 4)
      27. End Function
      29. Public Overrides Function ToString() As String
      30. Return String.Format("c: {0,-11:.####} m: {1}", C, Grade)
      31. End Function
      33. End Structure
      ein Trick:
      Bei Vertikalen wird nach Geradengleichung die Steigung +unendlich, und der Schnittpunkt Y-Achse wird -unendlich.
      Für den Zahlentyp Single kein Problem, aber wenn man zwei parallele Vertikalen auf dieser Basis vergleicht, erscheinen sie als identisch, denn beide haben dieselbe Steigung (+Unendlich), und hätten als y-Schnittpunkt ja auch das gleiche eingetragen: (-Unendlich).
      Daher belege ich C im Falle unendlicher Steigung mit was annerem, nämlich ich nehm den X-Wert, weil für eine Vertikale ist ja nur ein einziger X-Wert ühaupt definiert.
      Bilder

      • Shots00.Png

        14,26 kB, 457×335, 207 mal angesehen
      Dateien

      Dieser Beitrag wurde bereits 4 mal editiert, zuletzt von „ErfinderDesRades“ ()

      ErfinderDesRades schrieb:

      Bin heut hierüber gestolpert
      und muss da noch mal mit meinem letzten Einwand intervenieren:

      RodFromGermany schrieb:

      Zum Thema senkrechte Geraden:
      Dieser Punkt ist für die Bildverarbeitung unabdingbar, da solltest Du Dich klar positionieren.
      Ein Ansatzpunkt wäre, bei Geraden mit einem Anstieg größer 1 / kleiner -1 die Mathematik von y = ax + b nach x = Ay + B umzudrehen und dies entsprechend zu berücksichtigen.
      Da kann kein Anstieg mit Unendlich vorkommen.
      Der Zustand, dass die x-Achse gegenüber der y-Achse was besonderes oder zumindest was anderes ist, ist eben ein Spezialfall in dieser speziellen Art der Darstellung, die sich zwar einfach und schnell behandeln lässt, dafür aber ein paar Nebenbedingungen hat, die behandelt werden wollen.
      Allein durch Verdrehung des Koordinatensystems lässt sich der Zustand "senkrecht" eliminieren, was leider bei der Bildverarbeitung nur in 90°-Schritten geht, da wir hier die Pixel als Vorzugsrichtung haben.
      Allerdings plädiere ich doch dafür, das Problem allgemein zu lösen und bei Vorgabe irgend zweier Geraden (bzw. 4er Punkte) eine ordentliche Vektor-Gleichung aufstellen und dann die Determinante bestimmen, die dann und nur dann Null ist, wenn beide Geraden parallel sind.
      Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
      Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
      Ein guter .NET-Snippetkonverter (der ist verfügbar).
      Programmierfragen über PN / Konversation werden ignoriert!

    Facebook
    Telefonspende