Seite 3 von 4

Re: Liegt Punkt in einem 2D-Dreieck

Verfasst: Fr Jan 22, 2010 6:58 pm
von AnGaiNoR
Dirty Oerti hat geschrieben: Der Punkt P kann ja schlecht auf C liegen, wenn a = 0 ist ODER wenn a = 1 ist. (Könnte er schon, macht aber so keinen Sinn.)
Mich interessiert, welches der beiden "C" s eigentlich ein "B" hätte sein sollen.
Sry, Schreibfehler ^^
Bei a=1 auf C, bei a=0 auf B; so müsste es stimmen.
Am besten du skizzierst dir ein Dreieck in der Ebene und zeichnest alles ein, dann wird es ziemlich schlüssig.

@cloidnerux:
In deinem Code müsste es natürlich so heißen:

Code: Alles auswählen

if (r >= 0 && r <= 1 && s >= 0 && s <= 1)
Außerdem solltest du prüfen, ob die Punkte A, B und C überhaupt ein Dreieck bilden, sonst kann es zu einer Division durch null kommen. Den Fakt kannst du aber auch ausnutzen, indem du den Divisor (der ja in beiden Fällen gleich ist) in einer extra Variable speicherst und testest ober er null ist.


EDIT:
Dirty Oerti hat geschrieben: Das Themengebiet nennt man ja Analytische Geometrie (zumindest soweit ich weiß).
Müssen wir also nur noch ins Englische übersetzen, um einen neuen Bereichstitel zu erhalten.
Ich würde es einfach lineare Algebra (linear algebra) nennen ^^

EDIT2:
Ich habe grad festgestellt, das "linear algebra" sich auch großteilig mit "systems of linear equations" und "matrices" beschäftigt. Deshalb taufe ich um auf "vector analysis".

Re: Liegt Punkt in einem 2D-Dreieck

Verfasst: So Jan 24, 2010 6:51 pm
von cloidnerux
So, habe jezt beide Funktionen getestet, beide Funktionieren aber nur Teilweise.
Die erste Funktion die die Winkel ausrechnet, gibt nur an bestimten Punkten true zurück.
Die 2 mit dem Mathematischen Beweis nutzt schon ein größen Bereich, deckt aber nicht das ganze Dreieck ab.

Re: Liegt Punkt in einem 2D-Dreieck

Verfasst: So Jan 24, 2010 7:00 pm
von AnGaiNoR
cloidnerux hat geschrieben: Die 2 mit dem Mathematischen Beweis nutzt schon ein größen Bereich, deckt aber nicht das ganze Dreieck ab.
Echt? Wo soll denn der Punkt dann liegen, so dass es nicht funktioniert?

Re: Liegt Punkt in einem 2D-Dreieck

Verfasst: So Jan 24, 2010 7:12 pm
von cloidnerux
Bild
Die Roten Punkte stellen in etwa die Cursorposition dar.
Blau bedeuted das die Funktion "true" zurückgegeben hat, Grün steht für "false".
Hier die Funkiton, geschrieben in C#:

Code: Alles auswählen

/// <summary>
        /// Errechnet ob ein Punkt P innerhalb des Dreiecks ABC liegt
        /// </summary>
        /// <param name="p">Der zu Prüfende Punkt</param>
        /// <param name="A">Der Eckpunkt A des Dreiecks</param>
        /// <param name="B">Der Eckpunkt B des Dreiecks</param>
        /// <param name="C">Der Eckpunkt C des Dreiecks</param>
        /// <returns>true wenn der Punkt innerhalb des Dreieck liegt</returns>
        public static bool IsPointInTriangle2(Point p, Point A, Point B, Point C)
        {
            VectorF vc = new VectorF(B.X - A.X, C.Y - A.Y);
            VectorF vb = new VectorF(C.X - A.X, C.Y - A.Y);
            VectorF vp = new VectorF(p.X - A.X, p.Y - A.Y);
            float r, s;
            r = ((vp.X * vc.Y) - (vp.Y * vc.X)) / ((vb.X * vc.Y) - (vc.X * vb.Y));
            s = ((vp.Y * vb.X) - (vp.X * vb.Y)) / ((vb.X * vc.Y) - (vc.X * vb.Y));
            if (r >= 0 && r <= 1 && s >= 0 && s <= 1)
            {
                return true;
            }
            return false;
        }
"Vector" ist eine Klasse von mir, die zusätzlich zu den X- und Y-längen noch Vektoroperationen und ausgabe des Winkels und Länge des Vektors beherscht.
VectorF steht für ein Vektor mit float-Werten.

Re: Liegt Punkt in einem 2D-Dreieck

Verfasst: So Jan 24, 2010 7:20 pm
von AnGaiNoR
cloidnerux hat geschrieben:

Code: Alles auswählen

VectorF vc = new VectorF(B.X - A.X, C.Y - A.Y);
VectorF vb = new VectorF(C.X - A.X, C.Y - A.Y);
Die Definitionen für Vektor vc und vb sehen irgendwie komisch aus...

So würde ich das machen:

Code: Alles auswählen

VectorF vc = new VectorF(C.X - A.X, C.Y - A.Y);
VectorF vb = new VectorF(B.X - A.X, B.Y - A.Y);

Re: Liegt Punkt in einem 2D-Dreieck

Verfasst: So Jan 24, 2010 7:25 pm
von cloidnerux
Die Definitionen für Vektor vc und vb sehen irgendwie komisch aus...
So würde ich das machen:

Code: Alles auswählen

    VectorF vc = new VectorF(C.X - A.X, C.Y - A.Y);
    VectorF vb = new VectorF(B.X - A.X, B.Y - A.Y);
Du hast bei deinem Beweis folgendes geschrieben:
Dabei seien die Vektoren va = CB, vb = AC und vc = AB.
Das sah für mich so aus, als sei va Parallel zur Strecke a, vb Parallel zur Strecke b und vc Parallel zur Strecke c, damit würde es stimmen, aber ich werde deine Änderung gleich mal Testen.
Edit:
Habe es geändert und getest mit dem Dreick aus dem Bild.
Der Algorithmus gibt mir jezt für das Komplette Dreieck true zurück, leider aber auch für die komplette Rechte Seite.

Re: Liegt Punkt in einem 2D-Dreieck

Verfasst: So Jan 24, 2010 7:28 pm
von AnGaiNoR
Klar, hab ich vergessen ^^ Du müsstest eben noch C und B tauschen.
Aber das, was vorher dastand war auf jeden Fall eigenartig.

Re: Liegt Punkt in einem 2D-Dreieck

Verfasst: So Jan 24, 2010 7:47 pm
von cloidnerux
Aber das, was vorher dastand war auf jeden Fall eigenartig.
Habe ich auch gerade bemerkt, war warscheinlich ein Copy&Paste Fehler, habe einfach nur vergessen das C mit einem B zu Tauschen.
Klar, hab ich vergessen ^^ Du müsstest eben noch C und B tauschen.
Das habe ich auch gerade gemacht, hat das gleiche resultat, die komplette Rechte seite außerhalb des Dreiecks wird noch als Gültig erklärt.
Gerade ein wenig Dubuging betrieben, mit folgendem resultat:

Code: Alles auswählen

r = ((vp.X * vc.Y) - (vp.Y * vc.X)) / ((vb.X * vc.Y) - (vc.X * vb.Y));
s = ((vp.Y * vb.X) - (vp.X * vb.Y)) / ((vb.X * vc.Y) - (vc.X * vb.Y));
Diese Zeilen sind nicht ganz korrekt, ich verstehe nur noch nicht wieso.

Re: Liegt Punkt in einem 2D-Dreieck

Verfasst: So Jan 24, 2010 7:51 pm
von AnGaiNoR
cloidnerux hat geschrieben:

Code: Alles auswählen

r = ((vp.X * vc.Y) - (vp.Y * vc.X)) / ((vb.X * vc.Y) - (vc.X * vb.Y));
s = ((vp.Y * vb.X) - (vp.X * vb.Y)) / ((vb.X * vc.Y) - (vc.X * vb.Y));
Diese Zeilen sind nicht ganz korrekt, ich verstehe nur noch nicht wieso.
Hmm, da soll die Lösungsformel für lineare Gleichungssysteme mit 2 Unbekannten und 2 Gleichungen hin...

Re: Liegt Punkt in einem 2D-Dreieck

Verfasst: So Jan 24, 2010 7:55 pm
von cloidnerux
Fehler gefunden:
http://www.zum.de/Foren/mathematik/archiv/a24.html
Der Punkt liegt im Dreieck, wenn 0 <= r, s <= 1 und r+s <= 1.
Das hat das Problem gelöst. Ich danke für die Hilfe.