Determinante 3 Punkte Kreis

[bahu]

Hallo,

ich habe aus dem Internet folgendes Copy&Pasted / aus VB.NET übetragen:

Delphi-Quellcode:

function isLeft(a, b, c: TPoint) : boolean;
begin
  Result := ((c.y - a.y)*(b.x - a.x) - (b.y - a.y)*(c.x - a.x)) < 0;
end;

Hier wird geprüft ob bei 3 Punkten der Punkt C links von AB liegt.

Ich verstehe aber nicht warum das so ist, kann mir das einer erklären?


Viele Dank.

[Sherlock]

Das ist Vektorrechnung

http://www.mikrocontroller.net/topic/105993#931021

Sherlock

[SMO]

Zitat:

Zitat von bahu (Beitrag 1321794)

Ich verstehe aber nicht warum das so ist, kann mir das einer erklären?

Das ist auch auf den ersten Blick nicht leicht zu verstehen, besonders wenn man noch keine Vektorrechnung hatte.
Die von Sherlock verlinkte Erklärung ist gut, aber nicht besonders anschaulich, finde ich.

Deine "isLeft"-Funktion sollte wohl eher "isRight" heißen, denn sie liefert False für den kleinen Test A(1|1), B(3|2), C(2|3), obwohl dieser Punkt C links von AB liegt. Es kommt darauf an, welche "Richtung" man der Geraden gibt. Interpretiert man sie als "von A nach B", dann liefert die Formel positive Werte wenn C links liegt, interpretiert man die Gerade aber als "von B nach A", dann liefert sie negative wenn C links liegt.

Die Formel ist im Prinzip nichts anderes als ein zweidimensionals Kreuzprodukt (Kreuzprodukt in R²).
Falls du das Kreuzprodukt nicht kennst und auch von Vektoren keine Ahnung hast, müsste ich viel zu weit ausholen... Aber wenn du Grundkenntnisse hast, lass es mich wissen und ich werde es erklären.

Ansonsten hier eine Zerlegung des Codes von mir, die helfen könnte:

Delphi-Quellcode:

function Kreuzprodukt2D(x0, y0, x1, y1: Single): Single; inline;
begin
  Result := x0 * y1 - x1 * y0;
end;

// PunktAufSeite: Bestimmt, auf welcher Seite einer Gerade ein Punkt ist.
// Der zu testende Punkt P ist (px,py), die Gerade geht durch die Punkte A (ax,ay) und B (bx,by)
// Rückgabewert:  < 0 Punkt ist rechts, > 0 Punkt ist links, = 0 Punkt ist auf der Geraden
function PunktAufSeite(ax, ay, bx, by, px, py: Single): Single;
begin
  // 2D Kreuzprodukt der Vektoren von A nach B und von A nach P
  // = Kreuzprodukt(B-A, P-A)
  // = (bx-ax) * (py-ay) - (px-ax) * (by-ay)
  Result := Kreuzprodukt2D(bx - ax, by - ay, px - ax, py - ay);
end;

Und hier kannst du interaktiv mit dem 3D-Kreuzprodukt herumspielen.
Da das aber etwas unübersichtlich ist und dein Problem nur 2D ist, habe ich schnell ein kleines GeoGebra-Projekt zusammengeklickt, siehe Anhang. Einfach die Zip-Datei entpacken, Web-App starten, und im Menü rechts oben die .ggb-Datei öffnen (Drag & Drop der Datei ins Browserfenster geht auch). "uxv" ist dabei das Kreuzprodukt, d.h. der Wert der Formel, bevor auf Vorzeichen getestet wird (<0, >0).

[Lyan]

Also in dem Fall ist Determinante und Kreuzprodukt das gleiche. Man bildet aus 3 Vektoren 2 und nach Ausrechnung erhält man quasi:

Länge Vektor 1 * Länge Vektor 2 * sin vom Winkel zwischen denen.

Ergebnis > 0 heißt: Winkel zwischen 0 und 180 (oder 0 und PI wenn man so will)
Ergebnis < 0 heißt: Winkel zwischen 180 und 360 (oder PI und 2PI)

Also wenn das Vorzeichen des Kreuzproduktes negativ ist, befindet sich C links von AB und wenn positiv rechts von AB.