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;
}
Ist das an mich gerichtet?^^ Wenn ja, dann nein.AnGaiNoR hat geschrieben:Ist wohl ziemlich lange her mit der Vektorrechnung was? ^^
Ähm...ein Trapez in einem n-dimensionalem Raum?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.
Das ist ja die oben genannte Linearkombination.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
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)AnGaiNoR hat geschrieben: r = (xvp * yvc - yvp * xvc) / (xvb * yvc - xvc * yvb)
s = (yvp * xvb - xvp * yvb) / (xvb * yvc - xvc * yvb)
Das war eher an den Fragesteller gerichtet.Dirty Oerti hat geschrieben:Ist das an mich gerichtet?^^ Wenn ja, dann nein.AnGaiNoR hat geschrieben:Ist wohl ziemlich lange her mit der Vektorrechnung was? ^^
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:Ähm...ein Trapez in einem n-dimensionalem Raum?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.
Dazu ist es doch ausreichend, den n-dimensionalen Raum auf eine 2 dimensionale Ebene abzubilden (in der dann das Trapez liegt) ...
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.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.
Das ist also eine Art "Skalarfaktor", welcher in gewisser Weise angibt, wo sich der Punkt p im Endeffekt befindet?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.
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.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?
Was nun?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 einem if prüfen ob a das auch machtWas nun?
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);
}
}/// <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;
}
cloidnerux hat geschrieben:In einem if prüfen ob a das auch machtWas nun?
Ich meine, dass der Satz ...
... in sich einen Widerspruch trägt.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.