Liegt Punkt in einem 2D-Dreieck

Fragen zu mathematischen Problemen
Benutzeravatar
Dirty Oerti
Beiträge: 2229
Registriert: Di Jul 08, 2008 5:05 pm
Wohnort: Thurndorf / Würzburg

Re: Liegt Punkt in einem 2D-Dreieck

Beitrag von Dirty Oerti » Do Jan 21, 2010 6:47 pm

Ok, so passt es doch nicht.
Es reicht nicht, 2 Punkte als "Startpunkte" zu nehmen, man muss alle überprüfen.
Die letzte Funktion würde also so aussehen:

Code: Alles auswählen

bool IsInTriangle(Vektor A, Vektor B, Vektor C, Vektor P)
{
	if (CouldBeInTriangle(A,B,C,P)) {
		if (CouldBeInTriangle(B,A,C,P)) {
			if (CouldBeInTriangle(C,A,B,P)) {
				return true;
			}
		}
	}
	return false;
}
Bei Fragen einfach an daniel[ät]proggen[Punkt]org
Ich helfe gerne! :)
----------
Wenn du ein Licht am Ende des Tunnels siehst, freu dich nicht zu früh! Es könnte ein Zug sein, der auf dich zukommt!
----
It said: "Install Win95 or better ..." So I installed Linux.

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

Re: Liegt Punkt in einem 2D-Dreieck

Beitrag von AnGaiNoR » Do Jan 21, 2010 7:10 pm

Ist wohl ziemlich lange her mit der Vektorrechnung was? ^^
Ich hätte eine allgemeine Lösung für n-dimensionale Räume (n>1); dadu das Trapez ja aufteilst beschränke ich mich allerdings auf den Beweis, dass ein Punkt in einem Dreieck liegt.

Zuerst betrachte ich das Dreieck ABC. Dabei seien die Vektoren va = CB, vb = AC und vc = AB. (Am besten du skizzierst dir alles).

Nun möchte ich Vielfache des Vektors va durch vb und vc ausdrücken: (a, b und c sind Parameter)
a * va + vb = b * vb + c * vc

Vektor va lässt sich so darstellen: va = vc - vb
Daraus folgt aber: a * vc - a * vb + vb = b * vb + c * vc
Zusammengefasst ergibt das: (1 - a) * vb + a * vc = b * vb + c * vc
Daraus kann man b = (1 - a) und c = a folgern, oder eben b + c = 1-a + a = 1

Damit habe ich bewiesen, dass für b + c = 1 gilt: b * vb + c * vc = a * va ist.
Möchte man nun, dass a zwischen 0 und eins liegen, dann müssen auch b und c zwischen 0 und 1 liegen.

Heißt in deutscher Sprache: Wenn man einen Vektor mit b multipliziere und einen mit c und diese dann addiere, dann endet der Ergebnisvektor genau auf dem letzten verbleibenden Vektor, wenn b und c zwischen 0 und 1 und b + c = 1.

Daraus folgt aber, dass für b + c < 1 der Vektor im Dreieck endet.
Nimmt man nun einen Punkt P hinzu, dann liegt dieser genau dann im Dreieck, wenn der Vektor AP (im folgenden kurz vp) sich durch b * vb + c * vc darstellen lässt.
Das führt zu folgender Gleichung (die einer Ebene verdammt ähnlich sieht und auch etwas damit zu tun hat ^^): vp = r * vb + s * vc
Lassen sich r und s so bestimmen, dass r + s < 1 und zwischen 0 und 1, dann liegt der Punkt im Dreieck. Das führt letztlich zu einem Gleichungssystem mit 2 Unbekannten (r und s) und n Gleichungen (n ist die Anzahl der Dimensionen), wobei ich nur die beiden Gleichungen für die X- und die Y-Koordinate notiere:
xvp = r * xvb + s * xvc
yvp = r * yvb + s * yvc

Auf das Gleichungssystem kann man die allgemeine Lösungsstrategie anwenden. xvp zum Beispiel ist die X-Koordinate des Vektors AP, also im Endeffekt die Differenz aus X-Koordinate des Punktes P und X-Koordinate des Punktes A. Hier kann mir durchaus ein Fehler unterlaufen, also bitte kontrollieren:
r = (xvp * yvc - yvp * xvc) / (xvb * yvc - xvc * yvb)
s = (yvp * xvb - xvp * yvb) / (xvb * yvc - xvc * yvb)
Gilt nun oben gesagtes, dann liegt der Punkt in dem Dreieck, sonst nicht. Bei mehr Dimensionen müsstest du die Lösung in jede Folgegleichung einsetzen und kontrollieren. Meine Lösung hat den Vorteil, dass sie kurz, mathematisch exakt und allgemein ist und ohne Winkelberechnungen auskommt.
Physics is like sex: sure, it may give some practical result, but that's not why we do it.
(Richard P. Feynman)

Benutzeravatar
Dirty Oerti
Beiträge: 2229
Registriert: Di Jul 08, 2008 5:05 pm
Wohnort: Thurndorf / Würzburg

Re: Liegt Punkt in einem 2D-Dreieck

Beitrag von Dirty Oerti » Do Jan 21, 2010 8:00 pm

AnGaiNoR hat geschrieben:Ist wohl ziemlich lange her mit der Vektorrechnung was? ^^
Ist das an mich gerichtet?^^ Wenn ja, dann nein.
AnGaiNoR hat geschrieben:Ich hätte eine allgemeine Lösung für n-dimensionale Räume (n>1); dadu das Trapez ja aufteilst beschränke ich mich allerdings auf den Beweis, dass ein Punkt in einem Dreieck liegt.
Ähm...ein Trapez in einem n-dimensionalem Raum?
Dazu ist es doch ausreichend, den n-dimensionalen Raum auf eine 2 dimensionale Ebene abzubilden (in der dann das Trapez liegt) ...
AnGaiNoR hat geschrieben:Damit habe ich bewiesen, dass für b + c = 1 gilt: b * vb + c * vc = a * va ist.
Möchte man nun, dass a zwischen 0 und eins liegen, dann müssen auch b und c zwischen 0 und 1 liegen.

Heißt in deutscher Sprache: Wenn man einen Vektor mit b multipliziere und einen mit c und diese dann addiere, dann endet der Ergebnisvektor genau auf dem letzten verbleibenden Vektor, wenn b und c zwischen 0 und 1 und b + c = 1.

Daraus folgt aber, dass für b + c < 1 der Vektor im Dreieck endet.
Nimmt man nun einen Punkt P hinzu, dann liegt dieser genau dann im Dreieck, wenn der Vektor AP (im folgenden kurz vp) sich durch b * vb + c * vc darstellen lässt.
Das führt zu folgender Gleichung (die einer Ebene verdammt ähnlich sieht und auch etwas damit zu tun hat ^^): vp = r * vb + s * vc
Das ist ja die oben genannte Linearkombination.
Warum du sicher sein kannst, dass der Vektor innerhalb des Dreiecks liegt wenn die Parameter zwischen 0 und 1 liegen müsstest du bitte noch einmal genauer erklären..?
Ich bin bisher nur darauf gekommen, dass ich ausschließen kann, dass der Vektor im Dreieck liegt, wenn die Parameter unter 0 liegen.
AnGaiNoR hat geschrieben: r = (xvp * yvc - yvp * xvc) / (xvb * yvc - xvc * yvb)
s = (yvp * xvb - xvp * yvb) / (xvb * yvc - xvc * yvb)
Müsste stimmen, man kann deine Gleichungen zumindest in meine obigen umformen, und die obigen stimmen mit ziemlicher Sicherheit (ich hab sie gerade nochmal nachgerechnet)
:)
Bei Fragen einfach an daniel[ät]proggen[Punkt]org
Ich helfe gerne! :)
----------
Wenn du ein Licht am Ende des Tunnels siehst, freu dich nicht zu früh! Es könnte ein Zug sein, der auf dich zukommt!
----
It said: "Install Win95 or better ..." So I installed Linux.

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

Re: Liegt Punkt in einem 2D-Dreieck

Beitrag von AnGaiNoR » Do Jan 21, 2010 8:45 pm

Dirty Oerti hat geschrieben:
AnGaiNoR hat geschrieben:Ist wohl ziemlich lange her mit der Vektorrechnung was? ^^
Ist das an mich gerichtet?^^ Wenn ja, dann nein.
Das war eher an den Fragesteller gerichtet.
Dirty Oerti hat geschrieben:
AnGaiNoR hat geschrieben:Ich hätte eine allgemeine Lösung für n-dimensionale Räume (n>1); dadu das Trapez ja aufteilst beschränke ich mich allerdings auf den Beweis, dass ein Punkt in einem Dreieck liegt.
Ähm...ein Trapez in einem n-dimensionalem Raum?
Dazu ist es doch ausreichend, den n-dimensionalen Raum auf eine 2 dimensionale Ebene abzubilden (in der dann das Trapez liegt) ...
Ich wollte nur betonen, dass meine Lösung für alle Räume mit mehr als einer Dimension gelten, also auch für den 2-dimensionalen; allerdings haben nur die 2- bis 4-dimensionalen wirklich praktische Relevanz.
Dirty Oerti hat geschrieben: Warum du sicher sein kannst, dass der Vektor innerhalb des Dreiecks liegt wenn die Parameter zwischen 0 und 1 liegen müsstest du bitte noch einmal genauer erklären..?
Ich bin bisher nur darauf gekommen, dass ich ausschließen kann, dass der Vektor im Dreieck liegt, wenn die Parameter unter 0 liegen.
Aus (1 - a) * vb + a * vc = b * vb + c * vc folgt b = 1-a und c = a. Deshalb muss b + c = 1-a + a = 1 sein, damit der die Linearkombination einen Vektor darstellt, der auf der Gerade BC (also mit anderen Worten dem von mir va genannten Vektor) liegt. Da ich aber sicherstellen muss, dass der Punkt in diesem Schritt auf der Seite BC liegt und nicht irgendwo davor oder dahinter auf der Gerade, dürfen a und 1-a niemals größer als eins oder kleiner als 0 werden, was letztlich bedeutet 0 <= a <= 1.
Physics is like sex: sure, it may give some practical result, but that's not why we do it.
(Richard P. Feynman)

Benutzeravatar
Dirty Oerti
Beiträge: 2229
Registriert: Di Jul 08, 2008 5:05 pm
Wohnort: Thurndorf / Würzburg

Re: Liegt Punkt in einem 2D-Dreieck

Beitrag von Dirty Oerti » Do Jan 21, 2010 8:51 pm

AnGaiNoR hat geschrieben:Aus (1 - a) * vb + a * vc = b * vb + c * vc folgt b = 1-a und c = a. Deshalb muss b + c = 1-a + a = 1 sein, damit der die Linearkombination einen Vektor darstellt, der auf der Gerade BC (also mit anderen Worten dem von mir va genannten Vektor) liegt. Da ich aber sicherstellen muss, dass der Punkt in diesem Schritt auf der Seite BC liegt und nicht irgendwo davor oder dahinter auf der Gerade, dürfen a und 1-a niemals größer als eins oder kleiner als 0 werden, was letztlich bedeutet 0 <= a <= 1.
Das ist also eine Art "Skalarfaktor", welcher in gewisser Weise angibt, wo sich der Punkt p im Endeffekt befindet?
Sprich a = 0 bedeutet P befindet sich auf Punkt A und a = 1 bedeutet, dass sich der Punkt P auf der Verbindungsstrecke zwischen B und C befindet?
Bei Fragen einfach an daniel[ät]proggen[Punkt]org
Ich helfe gerne! :)
----------
Wenn du ein Licht am Ende des Tunnels siehst, freu dich nicht zu früh! Es könnte ein Zug sein, der auf dich zukommt!
----
It said: "Install Win95 or better ..." So I installed Linux.

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

Re: Liegt Punkt in einem 2D-Dreieck

Beitrag von AnGaiNoR » Do Jan 21, 2010 9:16 pm

Dirty Oerti hat geschrieben: Das ist also eine Art "Skalarfaktor", welcher in gewisser Weise angibt, wo sich der Punkt p im Endeffekt befindet?
Sprich a = 0 bedeutet P befindet sich auf Punkt A und a = 1 bedeutet, dass sich der Punkt P auf der Verbindungsstrecke zwischen B und C befindet?
a=0 bedeutet, dass der Punkt mit dem Punkt C übereinstimmt, bei a=1 stimmt der Punkt mit C überein, bei a=0.5 liegt er genau zwischen B und C.
Physics is like sex: sure, it may give some practical result, but that's not why we do it.
(Richard P. Feynman)

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

Re: Liegt Punkt in einem 2D-Dreieck

Beitrag von AnGaiNoR » Do Jan 21, 2010 10:01 pm

Mir fällt grad auf, dass man dieses und weitere algebraische Probleme getrost auch ins Wiki setzen könnte; da werd ich mich morgen evtl. mal ransetzen.
Physics is like sex: sure, it may give some practical result, but that's not why we do it.
(Richard P. Feynman)

Benutzeravatar
Dirty Oerti
Beiträge: 2229
Registriert: Di Jul 08, 2008 5:05 pm
Wohnort: Thurndorf / Würzburg

Re: Liegt Punkt in einem 2D-Dreieck

Beitrag von Dirty Oerti » Do Jan 21, 2010 10:05 pm

Gute Idee. Am besten in den Mathbereich...
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.
Mit Eintragungen schließe ich mich dann an, wenn meine Facharbeit fertig ist^^
a=0 bedeutet, dass der Punkt mit dem Punkt C übereinstimmt, bei a=1 stimmt der Punkt mit C überein, bei a=0.5 liegt er genau zwischen B und C.
Was nun?
Bei Fragen einfach an daniel[ät]proggen[Punkt]org
Ich helfe gerne! :)
----------
Wenn du ein Licht am Ende des Tunnels siehst, freu dich nicht zu früh! Es könnte ein Zug sein, der auf dich zukommt!
----
It said: "Install Win95 or better ..." So I installed Linux.

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

Re: Liegt Punkt in einem 2D-Dreieck

Beitrag von cloidnerux » Fr Jan 22, 2010 3:10 pm

Was nun?
In einem if prüfen ob a das auch macht ;)
Ich habe die Frage egstellt, und werde zusheen das in Code zu Bannen.
Ich habe die erste Methode mit den Winkeln schon implementiert, aber in C#, ich Poste Trotzdem mal den Code:

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 IsPointInTriangle(Point p, Point A, Point B, Point C)
        {
            Vector AB = new Vector(B.X - A.X, B.Y - A.Y);
            Vector AC = new Vector(C.X - A.X, C.Y - A.Y);
            Vector AP = new Vector(p.X - A.X, p.Y - A.Y);
            if (System.Math.Max(AB.GetAngel(), AC.GetAngel()) < AP.GetAngel()
                && System.Math.Min(AB.GetAngel(), AC.GetAngel()) > AP.GetAngel())
            {
                return false;
            }
            Vector BA = new Vector(A.X - B.X, A.Y - B.Y);
            Vector BC = new Vector(C.X - B.X, C.Y - B.Y);
            Vector BP = new Vector(p.X - B.X, p.Y - B.Y);
            if (System.Math.Max(BA.GetAngel(), BC.GetAngel()) < BP.GetAngel()
                && System.Math.Min(BA.GetAngel(), BC.GetAngel()) > BP.GetAngel())
            {
                return false;
            }
            Vector CA = new Vector(A.X - C.X, A.Y - C.Y);
            Vector CB = new Vector(B.X - C.X, B.Y - C.Y);
            Vector CP = new Vector(p.X - C.X, p.Y - C.Y);
            if (System.Math.Max(CA.GetAngel(), CB.GetAngel()) < CP.GetAngel()
                && System.Math.Min(CA.GetAngel(), CB.GetAngel()) > CP.GetAngel())
            {
                return false;
            }
            return true;
        }
        public static bool IsPointOnTrapez(Point p, Point A, Point B, Point C, Point D)
        {
            if (!IsPointInTriangle(p, A, B, C) || !IsPointInTriangle(p, B, C, D))
            {
                return false;
            }
            return true;
        }
    }

    class Vector
    {
        /// <summary>
        /// Die Vectorangaben
        /// </summary>
        int x, y;
        /// <summary>
        /// Die X-Länge des Vectors
        /// </summary>
        public int X
        {
            get
            {
                return x;
            }
            set
            {
                x = value;
            }
        }
        /// <summary>
        /// Die Y-Länge des Vectors
        /// </summary>
        public int Y
        {
            get
            {
                return y;
            }
            set
            {
                y = value;
            }
        }

        public Vector()
        {
            X = 0;
            Y = 0;
        }

        public Vector(int vX, int vY)
        {
            X = vX;
            Y = vY;
        }

        /// <summary>
        /// Gibt den Winkel des Vectors zurück
        /// </summary>
        /// <returns></returns>
        public double GetAngel()
        {
            return System.Math.Asin(y / this.GetLength());
        }

        /// <summary>
        /// Gibt die Länge des Vectors zurück
        /// </summary>
        /// <returns></returns>
        public double GetLength()
        {
            return System.Math.Sqrt(y * y + x * x);
        }
    }
Edit: 2 Möglichkeit schnell in den Computer gehackt, hoffe das ich es richitg verstanden habe:
/// <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 IsPointOnTrinagle2(Point p, Point A, Point B, Point C)
{
VectorF vc = new VectorF(A.X - B.X, A.Y - C.Y);
VectorF vb = new VectorF(A.X - C.X, A.Y - C.Y);
VectorF vp = new VectorF(A.X - p.X, A.Y - p.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 <= 0)
{
return true;
}
return false;
}
Redundanz macht wiederholen unnötig.
quod erat expectandum

Benutzeravatar
Dirty Oerti
Beiträge: 2229
Registriert: Di Jul 08, 2008 5:05 pm
Wohnort: Thurndorf / Würzburg

Re: Liegt Punkt in einem 2D-Dreieck

Beitrag von Dirty Oerti » Fr Jan 22, 2010 3:45 pm

cloidnerux hat geschrieben:
Was nun?
In einem if prüfen ob a das auch macht ;)
:roll: Ich meine, dass der Satz ...
a=0 bedeutet, dass der Punkt mit dem Punkt C übereinstimmt, bei a=1 stimmt der Punkt mit C überein, bei a=0.5 liegt er genau zwischen B und C.
... in sich einen Widerspruch trägt.
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.
Bei Fragen einfach an daniel[ät]proggen[Punkt]org
Ich helfe gerne! :)
----------
Wenn du ein Licht am Ende des Tunnels siehst, freu dich nicht zu früh! Es könnte ein Zug sein, der auf dich zukommt!
----
It said: "Install Win95 or better ..." So I installed Linux.

Antworten