4. Nächster Punkt zu einem Dreieck(im R³)

Nächster Punkt zu einem Dreieck(im R³)

  • J

    Google Spuckt dazu einige nützliche Sachen aus und ich bin jetzt soweit, dass ich folgendes durchführen möchte:

    Seien A, B und C die Punkte des Dreiecks im R³ und D der Punkt von dem man den Abstand zum Dreieck ausrechnen möchte.

    1. Stelle die Ebenengleichung mithilfe der 3 Punkte A, B, C auf.
    2. Stelle die Gerade g auf, die durch den Punkt D geht und senkrecht zur Ebene E ist(Normale)
    3. Berechne den Schnittpunkt S zwischen g und E.
    4. Prüfe ob S im Dreieck liegt(oder genau auf dem Rand)
    4a. Wenn ja, dann ist der gesuchte Mindestabstand d gleich dem Abstand von D und der Ebene, wir sind Fertig 🙂 .
    4b. Wenn nein, dann liegt der Punkt am nächsten zu einer Kante des Dreiecks oder einem Eckpunkt.

    Jetzt kommt der weniger ausgereifte Teil:
    5. Prüfe jeweils die 6 Entfernungen von D zu AB, AC, BC, A, B, C und wähle die kürzeste.

    Wie geht man da jetzt am besten weiter vor?
    Und wie bestimme ich ob ein Punkt im Dreieck liegt?

    Ist das allgemein gülitg?

    AD⃗=r⋅AB⃗+s⋅AC⃗\vec{AD} = r \cdot \vec{AB} + s \cdot \vec{AC}

    Wenn folgendes Gilt, dann liegt der Punkt im Dreieck.

    0\le r\le 1$, $0\le s\le 1$ und $r+s \le 1

    Ich denke der Ansatz ist richtig, jedoch hab ich Probleme das Ganze in Code zu fassen vorallem r und s benötigen ja das Lösen von Gleichungssystemen oder geht das auch anders?

    Ein Teil von dem was ich schon geschrieben habe:

    bool isInTrinagle(const SVector& A, const SVector& B, const SVector& C const SVector& D) {
	SVector AB(B-A);
	SVector AC(C-A);
	SVector AD(D-A);

	float r, s;
	//AD = r*AB +s*AC
	r= //???

	return false;
}

    Kennt vieleicht Jemand einen effizienteren Weg? (Nicht Mathematisch sondern bezogen auf Laufzeit und Programmierbarkeit)

    0
  • O

    JaykopX schrieb:

    Ist das allgemein gülitg?

    Ja, da AB und AC in einem Dreieck linear unabhängige Vektoren darstellen, ist jede linearkombination von ihnen ein Punkt auf der Dreiecksebene. Du hast da ein ganz bekanntes Verfahren entwickelt : die Baryzentrischen Koordinaten

    r und s kriegste, indem du den Punkt auf die Ebene projezierst und mit der Matrix Matrix (AB,AC)^-1 (oder ((AB,AC)T)-1, weiß grad nicht so genau) multiplizierst.Und ne 2x2 Matrix kann man noch gut per Hand invertieren, das sollte schnell gehen.

    eine Alternative ist: stell dir vor, dass das Dreieck kein Dreieck, sondern ein Prisma ist. dh es wird nicht von 3 Strecken sondern von 3 Ebenen begrenzt(deren Normalenvektoren alle nach aussen oder nach innen ins Dreieck zeigen). Was du nun machen musst ist zu schauen ob der Punkt bei allen Ebenen auf der selben Seite liegt. Aber ob das wirklich schneller ist?

    //letzter Edit: im Buch von Scherfgen sind beide Ansätze erklärt und er ist der Meinung, dass die Baryzentrischen Koordinaten schneller sind, wenn man die Mathematik einmal von Hand durchexerziert.

    0
  • J

    Das Ganze funktioniert jetzt im R², zumindest konnte ich keine Fehler beim Testen finden.

    bool isInTriangle(const SVector& A, const SVector& B, const SVector& C, const SVector& P) {	//Eigentlich keine Vektoren sondern Punkte
	SVector AB(B-A);
	SVector AC(C-A);
	SVector AP(P-A);

	float r, s, t;
	const float rsNenner= (AB.x*AC.y-AB.y*AC.x);

	s= (AP.x*AC.y-AP.y*AC.x)/rsNenner;
	t= (AP.y*AB.x-AP.x*AB.y)/rsNenner;
	r= 1-s-t;

	if((r>=0 && s>=0 && t>=0) || (r<=0 && s<=0 && t<=0)) //Vorzeichentest
		return true; //Wenn gleiche Vorzeichen=> Im Dreieck.
	return false; //Wenn gemischt=> Ausserhalb Dreieck
}

    Allerdings fehlt hier in der Berechnung die z-Koordinate vollständig und das kann ja garnicht funktionieren wenn nicht $$AB_z=AC_z=AP_z$$ ist.
    D.h. ich müsste irgendwie die z-Koordinate einbauen oder mit einer Transformation die z-Koordinate überflüssig machen. Weis Jemand vieleicht wie?

    Das ganze hab basteln können nachdem otze mir das Stichwort Baryzentrische Koordinaten gegeben hat:
    http://books.google.de/books?id=e7XUgN-Gb_YC&pg=PA138&lpg=PA138&dq=Punkt+im+Dreieck+Baryzentrisch&source=bl&ots=DrzKv0sT8B&sig=TTG4upxyFDLSpI7biFO-9xwYILU&hl=de&ei=DfqbS6yTAqHInAOLnN2eCw&sa=X&oi=book_result&ct=result&resnum=9&ved=0CCAQ6AEwCDgK#v=onepage&q=&f=false
    http://zach.in.tu-clausthal.de/teaching/cg1_0708/folien/06_barycentric_coord_4up.pdf

    0
  • J

    Hi! Ich hab das ganze jetzt fertig runtergeschrieben. Ist nicht so wenig, desshalb poste ich nur Sachen an denen Jemand Interesse hat.
    Hier ein Liste der Funktionen die sich evtl. lohnen würden anzusehen:

    //Mathematischer Vektor mit den nötigen Funktionen(Vektorprodukt etc.)
//Geschrieben für dieses Problem und unvollständig.
struct SVector {...};

//A und B definieren die Strecke. Geprüft wird ob P auf dieser Strecke liegt.
bool isInLine(const SVector& A, const SVector& B, const SVector& P){...}

//A, B und C definieren ein Dreieck. Geprüft wird ob P in diesem Dreieck liegt.
bool isInTriangle(const SVector& A, const SVector& B, const SVector& C, const SVector& P){...}

//PTri1, PTri2 und PTri3 definieren ein Dreieck. Rückgabe ist der Abstand von PCheck zum Dreieck.
float getDistance(const SVector& PTri1, const SVector& PTri2, const SVector& PTri3, const SVector& PCheck) {...}

//Flächeninhalt eines Dreicks welches durch die Vektoren PTriAB und PTriAC aufgespannt wird
float getAreaOfTriangle(const SVector& PTriAB, const SVector& PTriAC) {...}

//Löst eine Lineares Gleichungssystem mit A, B, C auf der Linken seite und P auf der Rechten.
//Gibt in einigen Fällen Probleme, wurde nicht zuende geschrieben, weil nicht mehr benötigt für Dreicksberechnungen.
bool solveLGS(const SVector& A, const SVector&B, const SVector& C, const SVector& P, SVector& Result){...}

    Gruß
    JaykopX

    0
  • O

    poste mal IsInLine. Nur aus Interesse, ob du das richtig hingekriegt hast 😉

    0
  • J

    Geht bestimmt eleganter 😉

    bool isInLine(const SVector& A, const SVector& B, const SVector& P) {
	SVector AB(B-A);
	SVector AP(P-A);
	SVector BP(P-B);

	const float fuzzyRadius=0.0001f;
	float lambda;

	if(AB.x!=0) lambda=P.x/AB.x;
	else if(AB.y!=0) lambda=P.y/AB.y;
	else if(AB.z!=0) lambda=P.z/AB.z;
	else {
		if(P.x==0 && P.y==0 && P.z==0) return true;
		else return false;
	}

	float CheckValue=lambda*AB.x-AP.x;
	if(CheckValue<0)CheckValue=-CheckValue;
	if(CheckValue>fuzzyRadius) return false;

	CheckValue=lambda*AB.y-AP.y;
	if(CheckValue<0)CheckValue=-CheckValue;
	if(CheckValue>fuzzyRadius) return false;

	CheckValue=lambda*AB.z-AP.z;
	if(CheckValue<0)CheckValue=-CheckValue;
	if(CheckValue>fuzzyRadius) return false;

	float dAB=SVector::Length(AB);

	if(SVector::Length(AP)>dAB || SVector::Length(BP)>dAB) return false;
	return true;
}

    Wenn du verbesserungsvorschläge hast dann her damit 😋

    0
  • O

    Ich kürze mal auf das, was fürs folgende Relevant ist

    JaykopX schrieb:

    bool isInLine(const SVector& A, const SVector& B, const SVector& P) {
	SVector AB(B-A);
	SVector AP(P-A);

	const float fuzzyRadius=0.0001f;
	float lambda=P.x/AB.x;

	float CheckValue=lambda*AB.x-AP.x;
	if(CheckValue<0)CheckValue=-CheckValue;
	if(CheckValue>fuzzyRadius) return false;
}

    Beispiel: A=(-2,0,0) B=(4,0,0) P=(1,0,0)
    P liegt offensichtlich auf der Strecke.
    Dann ist AB=(6,0,0) AP=(3,0,0)

    setzen wir dann mal ein was dein Code macht:
    CheckValue=abs(lambda*AB.x-AP.x)=abs(P.x/AB.x*AB.x-AP.x)=abs(P.x-AP.x)=abs(1-3)=2

    Aber: Checkvalue>0.0001 => liegt nicht auf der Strecke.
    funktioniert für alle Werte bei denen A nicht im Ursprung liegt.

    Viel Spaß beim Austüfteln 🙂

    //Edit was ich machen würde:
    1. P Auf AB Projezieren und damit den Punkt auf der Gerade erhalten.
    2. testen ob die projektion noch zwischen A und B liegt
    3.testen ob die Distanz zwischen dem Punkt und P < als fuzzyRadius ist.

    0
  • J

    Dumm, dass ich A als Ursprung gewählt habe und nur P variert habe.
    P ist in meinem Fall immer die Projektion auf der Geraden, aber wäre bestimmt besser es in die isInLine() funktion auszulagern. Ich werd mich mal dransetzen. Danke:)

    0
  • O

    JaykopX schrieb:

    P ist in meinem Fall immer die Projektion auf der Geraden

    Dann ist das ganze ja trivial. Dann musste ja nur für jede Koordinate von P testen, ob sie innerhalb des Intervalls [A,B] liegt.

    0
  • J

    Hoffe das es jetzt funktioniert.
    Ich habe die Berechnung der Projektion von ausserhalb jetzt hier reingeschrieben und gebe den Abstand von Projektion und Punkt zurück falls true rauskommt.
    Hab es nicht ausgiebig getestet und bin mir auch nicht sicher ob mein Lambda richtig ist.

    bool isProjectionInLine(const SVector& A, const SVector& B, const SVector& P, float& ProjectionLength) {
	ProjectionLength=-1; //Initializierung mit ungültigem Wert
	SVector AB(B-A);
	SVector AP(P-A);
	SVector PProjection;
	float lambda;

	lambda= SkalarProduct(AP, AB)/SkalarProduct(AB, AB);
	float dAB= Length(AB);
	PProjection=A+lambda*AB;

	SVector AProj(PProjection-A);
	SVector BProj(PProjection-B);

	if(Length(AProj)>dAB || Length(BProj)>dAB) return false;
	ProjectionLength=Length(P-PProjection);
	return true;
}
    0
Anmelden zum Antworten