Schnittpunkt zweier Linen berechnen mit Delphi

[TOC]

Hi!

Einige von Euch haben doch viel Ahnung von Mathe, genauer: Geometrie.
Ich hab da ein blödes Problem und komm einfach nicht weiter...
Ich brauche für mein neuestes Programm unbedingt eine Formel mit der ich den Schnittpunkt zweier Geraden berechnen kann. Fest steht, das die eine Linie mehr oder weniger schräg von oben nach unten verläuft und die zweite Linie mehr oder weniger schräg von links nach rechts. Ebenfalls steht fest das sich beide Linien im Schnittpunkt P kreuzen.
Die eine Linie nennen wir jetzt einfach mal Linie A, und die zweite Linie B. Die Start- und Endpunkte beider Linien sind gegeben, damit kommen wir auf die Punkte:

AX1,AY1 , AX2,AY2 und BX1,BY1 , BX2,BY2

Gesucht sind die X- und Y-Koordinaten vom Schnittpunkt P, also PX,PY.

Dazu eine Grafik:

http://www.badongo.com/pic/219243

Was ich jetzt noch weiss ist das jeder Punkt auf der Linie der Gleichung :

Delphi-Quellcode:

  Y=A+m*X

folgt, wobei "m" die Steigung der Geraden ist.

Die Steigung berechnet sich aus:

Delphi-Quellcode:

  m=a/b

und a und b berechnet man aus Delta X und Delta Y, also:

Delphi-Quellcode:

  m=(Y2-Y1)/(X2-X1)

Hmm. Und da an der Stelle komm ich einfach nit weiter... Sowas haben wir auf der Hauptschule damals leider nie gelernt :cry: .

Viele von Euch sind ja auf dem Gymnasium oder studieren sogar an der Uni. Wenn Du zufälligerweise weist wie man den Schnittpunkt der Geraden berechnen kann dann gib mir bitte einen Typ. Ich brauche dringend so eine Formel für mein neuestes Programm. Wenn das Programm fertig ist werde ich es Euch hier in DP kostenlos zur Verfügung stellen, wie immer, aber ich möchte jetzt noch nit verraten was das Programm macht. Es hat was mit Mustererkennung zu tun...

Uuups, dat mit der Grafik klappt nit ??? Dann häng ich sie halt an zum runterladen!

[Edit]================================================== ==========================================

Problem gelösst! Danke an DFried!

Im Anhang jetzt Delphi 3.0 und 7.0 Demo-Programm mit dem ihr zwei Linien zeichnen und deren
Schnittpunkt berechnen lassen könnt!

Die Programme sind FreeWare und natürlich OpenSource und schreiben NIX in die System-Registrierung!

Ihr könnt sie Euch ja mal anschauen!

Grüsse von TOC!

[dfried]

Die Suche ist dein Freund!

Kuckst du hier oder hier

[TOC]

Hi!

Zitat:

Zitat von dfried

Die Suche ist dein Freund!

Hey, cool! Vielen Dank für die Links :thumb: ! Hab´s mir grad alles runtergeladen und werds mir zuhause in Ruhe ansehen...

Grüsse von TOC :stupid: !

[TOC]

Hi!

Hey, vielen vielen Dank nochmal an dfried für die beiden Links :thumb: . Ich hab so diese Seite gefunden : Schnittpunk berechnen. Ein Freund hat mir geholfen die für mich völlig unverständlichen Matrizen-Funktion zu übersetzen. Mein neuestes Programm das ich am schreiben bin ist dadurch wahnsinnig viel schneller geworden und braucht endlich keinen virtuellen Speicher mehr!

Herausgekommen ist dabei diese kompakte Funktion:

Delphi-Quellcode:

{
  Diese Funktion berechnet den Schnittpunkt von Line A
  und Linie B. Haben beide Linien keinen Schnittpunkt
  dann ist das Ergebnis 'false', sonst werden die
  Koordinaten des Schnittpunktes in den Var-Paramtern X
  und Y zurückgegeben und das Ergebnis ist 'true'
}
Function CrossingPoint(AX1,AY1,AX2,AY2, BX1,BY1,BX2,BY2:Integer; Var X,Y:Integer):Boolean;
Var
  T,S,N:Extended;
Begin
  Result:=false;
  // Nenner berechnen (Matrize)
  N:=AX1*BY2 + BX2*AY2 + AX2*BY1 + BX1*AY1 - BX2*AY1 - AX1*BY1 - BX1*AY2 - AX2*BY2;
  // Möglicherweise Abruch wegen Divison durch Null
  If N=0 then Exit;
  // T berechnen (Matrize)
  T:=(AX1*AY2 + AX2*BY1 + BX1*AY1 - AX2*AY1 - BX1*AY2 - AX1*BY1) / N;
  // Wenn T nicht im Intervall [0,1] liegt dann haben
  // beide Linien keinen Schnittpunkt
  If (T<0) or (T>1) then Exit;
  // S berechnen (Matrize)
  S:=(AX1*BY2 + BX2*BY1 + BX1*AY1 - BX2*AY1 - BX1*BY2 - AX1*BY1) / N;
  // Wenn S nicht im Intervall [0,1] liegt dann haben
  // beide Linien keinen Schnittpunkt
  If (S<0) or (S>1) then Exit;
  // Berechnung mit T
  X:=Round(BX1+T*(BX2-BX1));
  Y:=Round(BY1+T*(BY2-BY1));
  // Berechnung mit S
  // X:=Round(AX1+S*(AX2-AX1));
  // Y:=Round(AY1+S*(AY2-AY1));
  Result:=true;
End;

Wenn, wie in meinem Programm, definitiv fest steht das sich beide Linien kreuzen dann gehts noch einfacher und schneller:

Delphi-Quellcode:

{
  Diese Prozedur berechnet den Schnittpunkt von Line A
  und Linie B. Haben beide Linien keinen Schnittpunkt
  dann ergeben X und Y den Punkt an dem sich
  beide Linien überschneiden würden, wenn man sie
  entsprechend verlängert!
}
Procedure CrossingPointQuick(AX1,AY1,AX2,AY2, BX1,BY1,BX2,BY2:Integer; Var X,Y:Integer);
Var
  T,N:Extended;
Begin
  // Nenner berechnen (Matrize)
  N:=AX1*BY2 + BX2*AY2 + AX2*BY1 + BX1*AY1 - BX2*AY1 - AX1*BY1 - BX1*AY2 - AX2*BY2;
  // T berechnen (Matrize)
  T:=(AX1*AY2 + AX2*BY1 + BX1*AY1 - AX2*AY1 - BX1*AY2 - AX1*BY1) / N;
  // Berechnung mit T
  X:=Round(BX1+T*(BX2-BX1));
  Y:=Round(BY1+T*(BY2-BY1));
End;

Das war´s schon!

Im Anhang findest Du jetzt zwei Demoprogramme, jeweils für Delphi 3.0 oder 7.0 .
Du kannst im Programm zwei Linien zeichnen und den Schnittpunkt berechnen lassen.

Die Programme sind FreeWare + OpenSource!

[Edit] Du findest sie jetzt ganz oben im Beitrag!

Vielen Dank nochmal!

Grüsse von TOC :stupid: !

[DP-Maintenance]

Dieses Thema wurde von "Daniel" von "Programmieren allgemein" nach "Open-Source" verschoben.
Auf Wunsch des Autors nach Opensource verschoben, da jetzt eine ausführliche Lösung existiert.

[TOC]

Hi!

Es gibt ein UpDate!

Grüsse von TOC :stupid: !