Liegt Punkt in einem 2D-Dreieck

Fragen zu mathematischen Problemen
AnGaiNoR
Beiträge: 212
Registriert: Sa Jul 19, 2008 7:07 pm
Wohnort: Dresden

Re: Liegt Punkt in einem 2D-Dreieck

Beitrag von AnGaiNoR » Fr Jan 22, 2010 6:58 pm

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".
Physics is like sex: sure, it may give some practical result, but that's not why we do it.
(Richard P. Feynman)

Benutzeravatar
cloidnerux
Moderator
Beiträge: 3079
Registriert: Fr Sep 26, 2008 4:37 pm
Wohnort: Ram (Gibts wirklich)

Re: Liegt Punkt in einem 2D-Dreieck

Beitrag von cloidnerux » So Jan 24, 2010 6:51 pm

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.
Redundanz macht wiederholen unnötig.
quod erat expectandum

AnGaiNoR
Beiträge: 212
Registriert: Sa Jul 19, 2008 7:07 pm
Wohnort: Dresden

Re: Liegt Punkt in einem 2D-Dreieck

Beitrag von AnGaiNoR » So Jan 24, 2010 7:00 pm

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?
Physics is like sex: sure, it may give some practical result, but that's not why we do it.
(Richard P. Feynman)

Benutzeravatar
cloidnerux
Moderator
Beiträge: 3079
Registriert: Fr Sep 26, 2008 4:37 pm
Wohnort: Ram (Gibts wirklich)

Re: Liegt Punkt in einem 2D-Dreieck

Beitrag von cloidnerux » So Jan 24, 2010 7:12 pm

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.
Redundanz macht wiederholen unnötig.
quod erat expectandum

AnGaiNoR
Beiträge: 212
Registriert: Sa Jul 19, 2008 7:07 pm
Wohnort: Dresden

Re: Liegt Punkt in einem 2D-Dreieck

Beitrag von AnGaiNoR » So Jan 24, 2010 7:20 pm

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);
Physics is like sex: sure, it may give some practical result, but that's not why we do it.
(Richard P. Feynman)

Benutzeravatar
cloidnerux
Moderator
Beiträge: 3079
Registriert: Fr Sep 26, 2008 4:37 pm
Wohnort: Ram (Gibts wirklich)

Re: Liegt Punkt in einem 2D-Dreieck

Beitrag von cloidnerux » So Jan 24, 2010 7:25 pm

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.
Redundanz macht wiederholen unnötig.
quod erat expectandum

AnGaiNoR
Beiträge: 212
Registriert: Sa Jul 19, 2008 7:07 pm
Wohnort: Dresden

Re: Liegt Punkt in einem 2D-Dreieck

Beitrag von AnGaiNoR » So Jan 24, 2010 7:28 pm

Klar, hab ich vergessen ^^ Du müsstest eben noch C und B tauschen.
Aber das, was vorher dastand war auf jeden Fall eigenartig.
Physics is like sex: sure, it may give some practical result, but that's not why we do it.
(Richard P. Feynman)

Benutzeravatar
cloidnerux
Moderator
Beiträge: 3079
Registriert: Fr Sep 26, 2008 4:37 pm
Wohnort: Ram (Gibts wirklich)

Re: Liegt Punkt in einem 2D-Dreieck

Beitrag von cloidnerux » So Jan 24, 2010 7:47 pm

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.
Redundanz macht wiederholen unnötig.
quod erat expectandum

AnGaiNoR
Beiträge: 212
Registriert: Sa Jul 19, 2008 7:07 pm
Wohnort: Dresden

Re: Liegt Punkt in einem 2D-Dreieck

Beitrag von AnGaiNoR » So Jan 24, 2010 7:51 pm

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...
Physics is like sex: sure, it may give some practical result, but that's not why we do it.
(Richard P. Feynman)

Benutzeravatar
cloidnerux
Moderator
Beiträge: 3079
Registriert: Fr Sep 26, 2008 4:37 pm
Wohnort: Ram (Gibts wirklich)

Re: Liegt Punkt in einem 2D-Dreieck

Beitrag von cloidnerux » So Jan 24, 2010 7:55 pm

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.
Redundanz macht wiederholen unnötig.
quod erat expectandum

Antworten