Vektoriales Rechnen

[Maurooon]

Okay, also ich habe mir jetzt eine Funktion gebaut, die jede Millisekunde die Geradengleichung durch die Punkte Figur1 und Figur2 berechnet. Durch meine Hindernisse hab ich nun auch geraden gelegt. Jetzt muss ich nur noch die Schnittpunkte berechnen und dann überprüfen ob die Schnittpunkte innerhalb der Hindernisse liegen (weil diese ja eigentlich nur Strecken sind) und falls ja, siehen die Figuren sich nicht und falls nein sehen sie sich.

Ich habe mir den Link einmal angeschaut, nur verstehe ich die Funktion nicht ganz und verwende sehr ungern Code den ich nicht versthe... Könntest du mir erklären, was dort jeweils passiert? Hier nochmal die Funktion:

Zitat:

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;

Was bedeutet Matrize, was für einen Nenner berechnet man da? Und sind dann AX1 und AY1 die Koordinaten von Figur 1 z.B. und AX2 und AY2 die von Figur 2 und BX1, BY1, BX2 und BY2 Punkte auf dem Hindernis?

Ich hoffe mir kann jemand helfen.

LG

[Namenloser]

Zitat von Maurooon:

nur verstehe ich die Funktion nicht ganz und verwende sehr ungern Code den ich nicht versthe... Könntest du mir erklären, was dort jeweils passiert?

Das ist löblich. Ich versuche mal den groben Ansatz zu erklären, weil ich mich noch daran erinnern kann, dass ich damals in der Mittelstufe auch ziemlich daran hing, da wir noch keine Vektorrechnung hatten.

Man kann die Lösung in zwei Teile untergliedern
(1) Tu so als wären die Strecken Geraden (also unendlich lang). Berechne die Schnittpunkte der Geraden.
(2) Prüfe, ob der Schnittpunkt tatsächlich auf den Strecken liegt.

(1) Zuerst betrachten wir mal nur die Schnittpunkte von Geraden (also unendlich langen Strecken), weil der Fall einfacher ist. Man kann eine Gerade durch zwei Punkte und einen Parameter darstellen:

Gerade g: g(t) = g0*(1-t) + g1*t
Gerade h: h(s) = h0*(1-s) + h1*s

g0, g1: Stützpunkte von Gerade g (Vektoren)
h0, h1: Stützpunkte von Gerade h (Vektoren)
t, s: Parameter (Skalare)

Du kannst dir vorstellen, dass man, wenn man für t und s beliebige Werte einsetzt, alle Punkte auf den jeweiligen Geraden bekommt.

Den Schnittpunkt erhält man jetzt einfach, indem man g = h setzt. Da bekommt man ein Gleichungssystem heraus, das man dann auflösen muss. Wie man sich denken kann, gibt es einen Fall, in dem das Gleichungssystem nicht bzw. nicht eindeutig lösbar ist, nämlich wenn g und h parallel sind (führt in der Praxis zu einer Division durch 0). Diesen Fall muss man abfangen.

Andernfalls erhält man die Lösung in Form einer Formel für t bzw. s. Wenn man den Wert in die oben gegebene Definition für g bzw. h einsetzt, erhält man den Schnittpunkt.

(2) Wie prüfen wir jetzt, ob der Schnittpunkt tatsächlich auf den Strecken liegt? Nun, schauen wir uns mal an, was passiert, wenn wir für t den Wert 0 oder den Wert 1 einsetzen.

g(0) = g0*(1-0) + g1*0 = g0
g(1) = g0*(1-1) + g1*1 = g1

Aha! Das heißt, 0 und 1 ergeben genau die Endpunkte der Strecke. Und nicht nur das, alle Werte zwischen 0 und 1 ergeben genau die Punkte zwischen den Endpunkten.

D.h. man muss nur prüfen, ob t im Bereich [0,1] liegt, und ob s im Bereich [0,1] liegt. Wenn beides wahr ist, dann schneiden sich die Strecken im berechneten Punkt. Andernfalls schneiden sie sich nicht.

---

Ich hoffe, der grobe Ansatz ist so verständlich. Ich hatte jetzt keine Lust, das hier alles im Detail aufzulösen. Du kannst ja mal versuchen, das nachzurechnen. Wenn du dabei Fragen hast, kannst du sie hier stellen.

Zitat von Maurooon:

Was bedeutet Matrize

Der Singular ist eigentlich "Matrix". Ist hier einfach nur eine kompakte Schreibweise für ein lineares Gleichungssystem.

[hanvas]

Zitat:

Function CrossingPoint(AX1,AY1,AX2,AY2, BX1,BY1,BX2,BY2:Integer; Var X,Y:Integer):Boolean; Was bedeutet Matrize, was für einen Nenner berechnet man da? Und sind dann AX1 und AY1 die Koordinaten von Figur 1 z.B. und AX2 und AY2 die von Figur 2 und BX1, BY1, BX2 und BY2 Punkte auf dem Hindernis?
LG

Normalerweise kann man den Schnittpunkt zweier Geraden berechnen in dem man die allgemeine Form der Geradengleichung für jede Gerade aufstellt und aus beiden Gleichungen ein Gleichungsystem aufstellt. Das wurde aber schon im Post vor mir beantwortet, weshalb ich mir das spare und stattdessen etwas zur konrekten Verwendung sage.

Genau das Beschriebene macht die Funktion. AX1,AY1 und AX2,AY2 sind die Koordinaten des Anfangs.- und Endpunktes einer Strecke, BX1,BY1 und BX2 und BY2 sind die Koordinaten des Anfangs.- und Endpunktes der zweiten Strecke. Die Funktion liefert wahr zurück wenn sich die beiden Strecken schneiden und false wenn nicht. X und Y sind die Koordinaten des Schnittpunktes falls sich die Strecken schneiden, ansonsten undefiniert.


cu Ha-Jö

[Maurooon]

Okay, vielen Dank.

Was bringt das

Code:

Result := false;

in der ersten Zeile und könnte man statt dem

Code:

Exit

nicht auch

Code:

result := false;

nehmen?

[BrightAngel]

Hey

Das Exit "unterbricht" den Kontrollfluss in der Funktion und kehrt zum "Aufrufer" zurück. Result ist der Rückgabewert und fasst erstmal den Kontrollfluss nicht an, sondern setzt nur den Rückgabewert.

Der Gedanke ist der: Diese Funktion ist so aufgebaut, dass man viele Kriterien überprüfen muss, bevor ein positives Ergebnis herauskommt. Man kann in jedem Zwischenschritt abbrechen und verkürzt damit die Ausführungszeit.

Warum kein if-else-Baum? Ja, man kann das auch mit verschachtelten if-else Statements ausdrücken. Aber optisch ist das eventuell nicht so schön, da man in jeder Verschachtelung optisch einmal mehr "einrückt". Klar, das ist Stil. Der Autor dieses Codes hat sich entschieden, dass das optisch für ihn schöner ist, wenn das alles optisch in einer Ebene liegt. Diese Entscheidung hat zum Beispiel zur Folge, dass die Symmetrie der Berechnung von S und T direkt allein schon durch den selben Zeilenbeginn und die interne Struktur der Zeile sichtbar ist.

Brighty

[Michael II]

Hallo Mauroon

die Funktion ZweiObjekte( ) überprüft, ob sich zwei Objekte a und b, welche sich mit gleichmässiger Geschwindigkeit je entlang einer Gerade bewegen jetzt gerade oder in der Zukunft treffen werden.

IN:
a1 : Momentaner Standort von a
a2 : a ist unterwegs von a1 in Richtung a2
ppsa: Geschwindigkeit von a in Pixel Pro Sekunden
radiusa : Zur Vereinfachung wird für die Form der Objekte ein Kreis mit Radius radiusa angenommen. [Man könnte hier natürlich auch ein Rechteck oder die wirkliche Form annehmen.]

OUT:
treffpunkt_a : Ortsvektor von a beim Zusammentreffen mit b.
kontakt: TRUE, wenn sich die beiden Objekte momentan überlappen.
zeit_bis_a2: Zeit, welche a von a1 nach a2 benötigt
Result: TRUE, wenn sich die beiden Objekte jetzt treffen oder sich in Zukunft treffen werden.
Falls Result=TRUE: sekundenbiszumteffen: Nach dieser Zeit treffen a und b aufeinander.

Delphi-Quellcode:

function ZweiObjekte( a1, a2 : TRPoint; radiusa : extended; ppsa : extended;
                      b1, b2 : TRPoint; radiusb : extended; ppsb : extended;
                      var treffpunkt_a, treffpunkt_b : TRPoint;
                      var zeit_bis_a2 : extended; var sekundenbiszumteffen : extended; var kontakt : boolean ):boolean;

var speeddelta, startdelta, speeda, speedb : TVektor;
    Radius : extended;
    quadres : TQuadResultat;
    res : boolean;

    function getVektor( a, b : TRPoint ): TVektor;
    begin
        Result.x := b.x - a.x;
        Result.y := b.y - a.y;
    end;

    function speedvektor( v : TVektor; pps : extended ) : TVektor;
    var len : extended;
    // IN v in Bewegungsrichtung pps=Speed des Objekts Pixel pro Sekunden
    // OUT Vektor - nach einer Sekunde hat sich das Objekt um diesen Vektor verschoben
    begin
        len := sqrt( sqr(v.x) + sqr(v.y) );
        if ( len > 0 ) then
        begin
          Result.x := v.x/len*pps;
          Result.y := v.y/len*pps;
        end
        else
        begin
          v.x := 0;
          v.y := 0;
        end;
    end;

    function OrtNachTSekunden( start, speedvektor : TVektor; sec : extended ) : TVektor;
    begin
        Result.x := start.x + sec*speedvektor.x;
        Result.y := start.y + sec*speedvektor.y;
    end;

    function hkontakt( pos1, pos2 : TRPoint; radius1, radius2 : extended ):boolean;
    begin
        Result := sqrt(sqr(pos2.x-pos1.x) + sqr(pos2.y-pos1.y)) < (radius1 + radius2);
    end;


begin
  Radius := radiusa + radiusb;
  res := false;
  kontakt := false;

  // Objekt a bewegt pro Sekunde "speeda" vorwärts - Objekt b bewegt pro Sekunde "speeda" vorwärts
  speeda := speedvektor( getVektor( a1, a2 ), ppsa );
  speedb := speedvektor( getVektor( b1, b2 ), ppsb );

  // Solange benötigt a von a1 nach a2:
  if abs(speeda.x) > abs(speeda.y) then
    zeit_bis_a2 := ( a2.x - a1.x )/speeda.x else
    zeit_bis_a2 := ( a2.y - a1.y )/speeda.y;

  // nach t Sekunden befindet sich Objekt a an der Stelle a1 + t*speeda,
  // nach t Sekunden befindet sich Objekt b an der Stelle b1 + t*speedb
  // Treffen die Objekte aufeinander? D.g. gibt es ein t: a1 + t*speeda = b1 + t*speedb?
  speeddelta := getVektor( speedb, speeda );
  startdelta := getVektor( b1, a1 );

  if ( speeddelta.x = 0 ) and ( speeddelta.y = 0 ) then
  begin // die relative geschwindigkeit zwischen a und b ist 0 =>
        // prüfen, ob sich a und b am momentanen ort berühren:
      res := hkontakt( a1, b1, radiusa, radiusb );
      treffpunkt_a := a1;
      treffpunkt_b := b1;
      kontakt := res;
      sekundenbiszumteffen := 0;
  end
  else
  begin
       // sonst muss für ein Zusammentreffen nach t gelten:
       // ¦a1+t*speeda - (b1+t*speedb)¦ < Radius =>
       // Dies führt auf eine quadratische Gleichung in t, welche wir lösen müssen:
      if Quadratische_Gleichung_Reell( (sqr(speeddelta.x) + sqr(speeddelta.y)),
        2*( speeddelta.x * startdelta.x + speeddelta.y * startdelta.y),
        sqr(startdelta.x) + sqr(startdelta.y)- sqr(Radius),
        quadres ) then
      begin
          // quadres.x2 ist immer <= quadres.x1 (da in dieser quadratischen Gleichung (at^2+bt+c=0) a immer positiv ist)
          if ( quadres.x1 <> quadres.x2 ) then // wir werden nur Überschneidungen der Kreise als Treffer
          begin
              kontakt := ( quadres.x2 < 0 ) and ( quadres.x1 > 0 );
              if kontakt then
              begin
                 // a und b haben momentan einen gemeinsamen Schnitt
                 treffpunkt_a := a1;
                 treffpunkt_b := b1;
                 res := true;
                 sekundenbiszumteffen := 0;
              end
              else
              begin
                 // a und b werden in quadres.x2 Sekunden einen gemeinsamen Schnitt haben
                 if ( quadres.x2 > 0 ) then
                 begin
                    treffpunkt_a := OrtNachTSekunden( a1, speeda, quadres.x2 );
                    treffpunkt_b := OrtNachTSekunden( b1, speedb, quadres.x2 );
                    res := true;
                    sekundenbiszumteffen := quadres.x2;
                 end;
              end;
          end;
      end;
  end;
  Result := res;
end;

Anwendungsbeispiel:
Dein Spielobjekt a befindet sich an Position a1, das Zielobjekt an Position a2. a (dein Projektil) bewegt sich mit ppsa in Richtung a2.
b ist ein Hindernis, welches sich auch bewegt oder auch still steht ( dann ppsb = 0 wählen ).
Die Funktion überprüft, ob und wann (var sekundenbiszumteffen) a auf b treffen wird.
Die Funktion berechnet ebenfalls, wie lange a von a1 nach a2 benötigt.


Code unten:
a bewegt sich entlang der x Achse von x=1000 nach -1000. speed 500
b bewegt sich entlang der y Achse von y=500 nach 0. speed 250

Die Funktion gibt TRUE zurück, weil sich die Objekte natürlich nach ca. 2 Sekunden in der Region (0,0) treffen werden.
a und b treffen nach treffer_in_sec=1.989266873708 aufeinander.
a benötigt von a1 nach a2 bisa=4 Sekunden.
=> a trifft aufs Hindernis b, bevor a beim Punkt a2 angekommen ist.

Delphi-Quellcode:

procedure TForm92.Button1Click(Sender: TObject);
var a1, a2, b1, b2, tpa, tpb : TRPoint;
    ppsa, ppsb, radiusa, radiusb, bisa2, treffer_in_sec : extended;
    kontakt : boolean;

begin
  a1 := RPoint( 0,1000);
  a2 := RPoint( 0,-1000 );
  b1 := RPoint( 500,0 );
  b2 := RPoint( 0,0 );

  radiusa := 3;
  radiusb := 3;
  ppsa := 500;
  ppsb := 250;

  if ZweiObjekte( a1, a2, radiusa, ppsa,
                  b1, b2, radiusb, ppsb, tpa, tpb, bisa2, treffer_in_sec, kontakt ) then
  begin
      showmessage( 'treffer' );
  end
  else showmessage( 'kein treffer' );
end;