Liegt Punkt in einem 2D-Dreieck

Fragen zu mathematischen Problemen
Benutzeravatar
cloidnerux
Moderator
Beiträge: 3123
Registriert: Fr Sep 26, 2008 4:37 pm
Wohnort: Ram (Gibts wirklich)

Liegt Punkt in einem 2D-Dreieck

Beitrag von cloidnerux » Mi Jan 20, 2010 9:11 pm

Also, ich habe für eine kleines GUI-Element abgeschrägte Seiten. Da ich jezt nciht will, das man quasi außerhalb des Trapezes das GUI-Element aktivieren kann, wollte ich Prüfen, ob der Punkt in diesem Trapez liegt.
Da ich keine gescheiten Ergebnise für den Beweis, das ein Punkt innerhalb eiens Trapezes liegt, gefunden habe, teile ich das Trapez jetzt in 2 Dreiecke auf.
Dazu habe ich etwas gefunden. Aber dort wird nur ungenau beschrieben, wie man mit sonst wie vielen Umformungen und TEchniken nicht gegebene Eckpunkte errechnet und Beweise aufstellt, was mir eindeutig zu kompliziert war, denn ich habe ja die Koordinaten der Eckpunkte.
Ich habe bisher so viel verstanden, das man aus den Koordinaten und Streckenlängen des Dreiecks Vectoren Bilden muss, mit denen men Prüft ob der Punkt Links oder Rechts einer Seite des Dreiecks befindet. Ihc habe nur noch nicht verstanden, wie.
Kann mir jemand helfen oder hat erfahrung damit?

MfG cloidnerux.
Redundanz macht wiederholen unnötig.
quod erat expectandum

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8858
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Re: Liegt Punkt in einem 2D-Dreieck

Beitrag von Xin » Do Jan 21, 2010 12:21 am

cloidnerux hat geschrieben:Ich habe bisher so viel verstanden, das man aus den Koordinaten und Streckenlängen des Dreiecks Vectoren Bilden muss, mit denen men Prüft ob der Punkt Links oder Rechts einer Seite des Dreiecks befindet. Ihc habe nur noch nicht verstanden, wie.
Kann mir jemand helfen oder hat erfahrung damit?
Mal freies Raten... ;)

Nehmen wir ein Beispiel: das Dreieck A(-1,1), B(1,3), C(0,-2) und den Punkt P(0,0). Dann gehen wir das Dreieck im Kreis ab, also von A nach B, dann nach C und weiter nach A. Wir haben damit die Strecken AB, BC und CA. Wenn wir rechtrum gehen, dann muss der Punkt bei allen Strecken rechts liegen, dann liegt er innenliegend. Gehen wir nach links, so muss der Punkt bei allen Strecken auf der linken Seite liegen.

Nehmen wir die erste Grade AB. Die Gerade ist dann definiert durch AB( v ) = A + (B-A)*v. (B-A) ist (1,3)-(-1,1), also ( 2,2 ). Jetzt drehen wir die Richtung von (2,2) um 90 Grad und zwar so: (x,y) => ( y, -x ). Wir erhalten also ( 2, -2 ). Nun bilden wir von P einen Grade, die 90 Grad durch AB durch den Schnittpunkt S verläuft: PS( w ) = P + w ( 2, -1 ). An der Stelle, wo die beiden Gleichungen gleich werden, ist der Schnittpunkt S. Also v und w bestimmen:

AB( v ) = PS( w )
A + (B-A)*v = P + (90GradVon(B-A)) * w
( -1, 1 ) + ( 2,2 ) * v = ( 0,0 ) + ( 2, -2 ) * w

-1 + 2v = 0+2*w
1 + 2v = 0+-2*w
-------
-1 + 2v = 0+2*w
2 = -4w
--------
-1 + 2v = 0+2*w
w = -1/2 // Hier kann man Schluss machen
--------
v = (-1 +1) / 2 = 0
w = -1/2
------------
S = AB( v ) = ( -1, 1 ) + ( 2,2 ) * v
S = AB( 0 ) = (-1,1) + ( 2,2) * 0
S = AB( 0 ) = (-1,1)
-------------
w sollte nun angeben, ob man sich nach links oder rechts bewegt.


Das Ganze für jede Linie des Polygons (dein Dreieck) und go. Um zu entscheiden, ob Du links oder rechtsrum gehst, musst Du wohl gucken, ob C links oder rechts von AB liegt.
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

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 12:25 am

Also das Aufteilen in 2 Dreiecke halte ich ehrlich gesagt auf den ersten Blick für stark sinnlos.
Dadurch machst du aus 2 schrägen Seiten (was das eigntl Problem ist) 3 schräge Seiten. Es macht es also nur komplizierter.

Ich würde es folgendermaßen machen:

Das Trapez enthält ja erstmal ein Rechteck. Ob sich ein Punkt in einem Rechteck befindet lässt sich einfach überprüfen.
Bleiben dir 2 Dreiecke.

Fangen wir mit dem linken an:

.......X
.......|
.......|
.......|
X.....A

Nach rechts haben wir die x-Achse, nach oben die y-Achse.

Du berechnest nun den Vektor zwischen dem oberen X und dem unteren X.
( Das bedeutet Koordinaten des oberen X minus Koordinaten des unteren X )
Den nennen wir nun Vektor 1.

Deinen zu überprüfenden Punkt nimmst du nun, und ziehst von dessen Koordinaten die Koordinaten des unteren X ab.
Dadurch erhältst du einen Vektor vom X zum Punkt. Genannt Vektor 2.

Jetzt kannst du die Winkel der beiden Vektoren zur x-Achse berechnen.

Ist der Winkel von Vektor 2 größer als von Vektor 1 ist der Punkt nicht im Dreieck.
Ist der Winkel kleiner, dann musst du nur gucken, ob seine x-Koordinate größer ist als die des Punktes A.

Überleg dir das ganze am besten graphisch...also nimm dir einen Block, mal ein ordentliches Koordinatensystem drauf und überleg dir, wo Punkte überall liegen könnten.
--------------------------------------------------------

Achja: Wie du einen Winkel zwischen zwei Vektoren (Vektor 1/2 und x-Achse) berechnest:

cosinus WINKEL = ( SKALARPRODUKT der Vektoren ) / ( Produkte der Vektorenlängen )

SKALARPRODUKT von Vektor (a1 | a2) und Vektor (b1 | b2) = a1*b1 + a2*b2
Länge eines Vektors (a1 | a2) = sqrt ( a1^2 + a2^2 )

Der Vektor der X-Achse ist ( 1 | 0)



... ist das verständlich? :)
Wenn nicht, dann kann ich das noch genauer ausführen.
Eine effizientere Möglichkeit könnte es auch noch geben..
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: 3123
Registriert: Fr Sep 26, 2008 4:37 pm
Wohnort: Ram (Gibts wirklich)

Re: Liegt Punkt in einem 2D-Dreieck

Beitrag von cloidnerux » Do Jan 21, 2010 3:26 pm

Also das Aufteilen in 2 Dreiecke halte ich ehrlich gesagt auf den ersten Blick für stark sinnlos.
Mir geht es eher darum, zu Lernen, als so eine schrecklich komplizierte Methode anzuwenden, denn ich schreibe ein kleines CAD-Program, es könnte daher mal nützlich zu sein solche Sachen zu bestimmen.
Das Trapez enthält ja erstmal ein Rechteck. Ob sich ein Punkt in einem Rechteck befindet lässt sich einfach überprüfen.
Bleiben dir 2 Dreiecke.
In diesem fall, kann ich über Sinus/Cosinus und den Satz des Pytagoras das viel einfacher bestimmen, denn ich habe ja 2 Seiten die Parallel zur X-, bzw Y-Achse liegen, das grenzt das ganze Stark ein.
Dann errechne ich mir cos(Alpha)/*Unten Links*/ und Teile damit die Distanz von P->X zu A->X/*Unten Links*/. Damit hätte ich die Hypotenuse des Dreiecks, das die höchstmögliche Gegenkathete hat, dann nur noch sin(Alpha) und mit der Hypothenuse Multiplizieren, und Prüfen ob P->Y den Wert einhält.
Aber wie gesagt, Interessiere ich mich für die Mathematische Lösung, die es mit erlaubt ein belibig gedrehtes Dreieck zu Prüfen.
Zudem kann ich aus vielen Dreiecken jedes beliebige Polygon erstelen, umgekehrt aber nicht.
Redundanz macht wiederholen unnötig.
quod erat expectandum

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8858
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Re: Liegt Punkt in einem 2D-Dreieck

Beitrag von Xin » Do Jan 21, 2010 3:27 pm

cloidnerux hat geschrieben:
Also das Aufteilen in 2 Dreiecke halte ich ehrlich gesagt auf den ersten Blick für stark sinnlos.
Mir geht es eher darum, zu Lernen, als so eine schrecklich komplizierte Methode anzuwenden, denn ich schreibe ein kleines CAD-Program, es könnte daher mal nützlich zu sein solche Sachen zu bestimmen.
Dein Trapez ist ein Polygon... genau, wie ein Dreieck.. s.o.

Bei einem Polygon mit mehr als drei Punkten musst Du nur sicherstellen, dass Du ein konvexes Polygon hast, oder Dir durch Tesselation konvexe Polygone erstellen - also wieder Dreiecke.
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

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 4:11 pm

cloidnerux hat geschrieben:Mir geht es eher darum, zu Lernen, als so eine schrecklich komplizierte Methode anzuwenden, denn ich schreibe ein kleines CAD-Program, es könnte daher mal nützlich zu sein solche Sachen zu bestimmen.
^^ Schrecklich komplizierte Methode ... du bist lustig ;)
myself hat geschrieben:das Aufteilen in 2 Dreiecke
Wenn du meinen Beitrag oben genau durchliest, wirst du feststellen, dass ich dir den Ansatz dafür gegeben habe, beliebig gedrehte (und auch förmige) Dreiecke zu überprüfen. Das kannst du mit deinem Satz des Pythagoras nicht :-P

Mal auf ein beliebiges Dreieck angewandt:

Das Dreieck besteht aus den Punkten ABC.
Der Winkel an Punkt A heißt ALPHA, an B BETA und an C GAMMA.
Benannt wird in folgender Richtung:
C
|...\
|......\
A-------B

Nun willst du prüfen, ob ein beliebiger Punkt P in diesem Dreieck ist.

Erster Schritt:

Du berechnest den Vektor (das ist nun WIRKLICH nicht kompliziert) von Punkt A zu Punkt P.
Du berechnest die Vektoren von Punkt A nach C und von A nach B.

Nun berechnest du den Winkel w1 zwischen Vektor A->C und Vektor A->B
Und du berechnest den Winkel w2 zwischen Vektor A->P und Vektor A->B

Ist w2 größer als w1 dann kannst du abbrechen, der Punkt liegt NICHT im Dreieck.
Ansonsten:

Zweiter Schritt:

Du berechnest den Vektor von B nach P.
Dann nimmst du noch den Vektor von B nach A (das ist der Vektor von A nach B, nur das jede Koordinate mal -1 genommen wurde)
AUßerdem noch den Vektor von B nach C.

Du berechnest den Winkel w3 zwischen Vektor B->A und Vektor B->C
Außerdem den Winkel w4 zwischen Vektor B->P und Vektor B->C
(Die Winkel müssen spitze Winkel sein. Sind sie es nicht, dann einfach 180°-Winkel nehmen)


Ist w4 kleiner als w3, dann ist der Punkt im Dreieck.
Wenn nicht, dann liegt der Punkt außerhalb des Dreiecks.

----

So. Das sollte nun mit JEDER möglichen Art von Dreieck funktionieren, egal wie gedreht und so weiter es ist.
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: 3123
Registriert: Fr Sep 26, 2008 4:37 pm
Wohnort: Ram (Gibts wirklich)

Re: Liegt Punkt in einem 2D-Dreieck

Beitrag von cloidnerux » Do Jan 21, 2010 4:18 pm

Verdammt, gerade erst Dirty Oertis Beitrag verstanden.
Ich bin selbst auf die gleiche Lösung gekommen, nur nicht so schnell.
Wäre ja mal was fürs Wiki. Ich Implemntiere das gleich mal und sehe zu daraus was fürs Wiki zu machen.
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 » Do Jan 21, 2010 4:26 pm

MIr ist gerade eingefallen, dass man das auch auf Vierecke erweitern kann.
Und zwar auf eine beliebige Variante (also auch ein Trapez).

Das Verfahren geht analog zu oben erwähnten.
Nur müssen nun nicht benachbarte Punkte zur Überprüfung herangezogen werden, sondern entegengesetzte:


D_______C
|..........|
|..........|
A_______B

Nun nimmst du als erstes z.B. Punkt A.
Bilde die Vektoren A->B und A->D. sowie den Vektor A->P
Winkel zwischen A->B und A->D sowie A->B und A->P bilden.
Ist der Winkel zwischen A->B und A->P größer als der andere, dann liegt der Punkt außerhalb.

Ansonsten gehts weiter mit dem gegenüberliegendem Punkt C:
Vektoren C->B und C->D sowie Vektor C->P bilden.
Winkel zwischen C->B und C->D sowie Winkel zwischen C->B und C->P bilden.
Ist der Winkel zwischen C->B und C->P größer als der andere, dann liegt der Punkt außerhalb.

Ansonsten ist der Punkt im Viereck.
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: 3123
Registriert: Fr Sep 26, 2008 4:37 pm
Wohnort: Ram (Gibts wirklich)

Re: Liegt Punkt in einem 2D-Dreieck

Beitrag von cloidnerux » Do Jan 21, 2010 4:42 pm

MIr ist gerade eingefallen, dass man das auch auf Vierecke erweitern kann.
Und zwar auf eine beliebige Variante (also auch ein Trapez).
Und damit auf jedes Konvexe Polygon.
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 » Do Jan 21, 2010 6:34 pm

Haha :)
Ich sitze (saß, jetzt bin ich daheim) gerade in Informatikunterricht und meinem Lehrer ist noch eine (deutlich bessere und schnellere) Variante eingefallen.

Diese bezieht sich jetzt aber NUR auf Dreiecke.
Ist aber deutlich schneller, da keine Winkel berechnet werden müssen.

Und zwar:

C
|..\
|....\
|......\
A_____B

Punkt P wird überprüft.

1. Schritt:

Du berechnest die Vektoren A->C und A->B
Ersteren nennen wir mal a und den anderen b;

Dann berechnest du den Vektor A->P
Den nennen wir mal p

Jetzt ist (da es sich im 2 dimensionalem "Raum" abspielt) der Vektor p automatisch eine sog. Linearkombination aus den Vektoren a und b.
Das bedeutet konkret:

p = r * a + s * b;

Nun musst du die Parameter r und s berechnen.
Mal ausgeschrieben auf die einzelnen Koordinaten erhältst du folgendes Gleichungssystem:

p1 = r * a1 + s * b1;
p2 = r * a2 + s * b2;

r = (p2 - s*b2) / a2;

s = (p1 - r*a1) / b1;

Einsetzen:

s = { p1 - a1* [ (p2 - s*b2) / a2 ] } / b1;

Auflösen:

s = [ p1 - (a1*p2)/a2 ] / [ b1 - (a1*b2)/a2 ]

Daraus kannst du nun s berechnen, und daraus dann mittels obiger Formel auch r.

Nun schaust du, ob r >= 0 und s >= 0.
Wenn ja, dann KANN der Punkt im Dreieck liegen, wenn nein, dann liegt er SICHER NICHT im Dreieck.

Wenn der Punkt im Dreieck liegen KANN, dann muss das noch weiter überprüft werden.
Das geht genauso wie oben, nur dass du nicht von Punkt A ausgehst, sondern z.B. von Punkt B

Dann erhältst du als Vektor a eben : Punkt A minus Punkt B
Und als Vektor b: Punkt C minus Punkt B



Da mir gerade so danach war, hab ich das mal in (ungetesteten) Code geprügelt.
Funktionieren müsste es :)
Testet, ob der Punkt P im Dreieck aus den Punkten A,B und C ist.

Code: Alles auswählen


typedef struct
{
	int x;
	int y;
} Vektor;


bool CouldBeInTriangle(Vektor PUNKTA, Vektor PUNKTB, Vektor PUNKTC, Vektor PUNKTP)
{
	Vektor a,b,p;
	a.x = PUNKTC.x - PUNKTA.x;
	a.y = PUNKTC.y - PUNKTA.y;
	b.x = PUNKTB.x - PUNKTA.x;
	b.y = PUNKTB.y - PUNKTA.y;
	p.x = PUNKTP.x - PUNKTA.x;
	p.y = PUNKTP.y - PUNKTA.y;

	double s,r;
	s = ( p.x - ((a.x*p.y)/a.y) ) / ( b.x - ((a.x*b.y)/a.y) );
	r = ( p.x - (s*b.y)) / a.y;
	if ( s >= 0 && r >= 0) {
		return true;
	} else {
		return false;
	}
}


bool IsInTriangle(Vektor A, Vektor B, Vektor C, Vektor P)
{
	if (CouldBeInTriangle(A,B,C,P)) {
		if (CouldBeInTriangle(B,A,C,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.

Antworten