Punkt in Dreieck

luki91

hallo
ich habe ein programm das ein dreieck zeichnet. wie kann ch abfragen, ob ein bestimmter punkt im dreieck liegt oder nicht?
mfg
luki

interpreter

z.B. durch 3 Tests die prüfen, auf welcher Seite der 3 Kanten der Punkt liegt. Wenn er jedesmal auf der "richtigen" Seite liegt, dann ist er im Dreieck.

Wenn p0,p1,p2 die Eckpunkte des Dreiecks sind, p der zu prüfende Punkt und n die Normale des Dreiecks, dann sieht der Test so aus:
(p1-p0) x (p-p0) * n >= 0
(p2-p1) x (p-p1) * n >= 0
(p0-p2) x (p-p2) * n >= 0
// x = Kreuzprodukt, * = Skalarprodukt

In der 1. Zeile schaust du z.B., ob der Kosinus zwischen n und dem Vektor, der Senkrecht auf die von p1-p0 und p-p0 aufgespannte Ebene senkrecht steht >= 0, sprich der Winkel in [-pi/2, +pi/2] liegt. Wenn das der Fall ist, dann liegt der Punkt auf der "richtigen Seite im Raum".

oder fast noch einfacher, wenn das dreieck durch A,B,C gegeben ist und du den punkt P hast:

Vektoren AP, BP, CP aufstellen
danach die winkel zwischen AP-BP; AP-CP; und BP-CP ausrechnen, wenn die winkel miteinander addiert 360 ergeben, ist der punkt im dreieck (dh. wenn das eintritt, oder P=A oder P=B oder P=C ist)

stefan

bin zwar mathenoob, aber wenn man Vektor p1 zu p2 und p1 zu p3 nimmt und dann sowas macht (px ist der punkt von dem ich wissen will, ob er im Dreieck liegt):

px = p1 + r*(p2 - p1) + s *(p3-p1).
Ist r + s <= 1 liegt es im Dreieck.

Kann aber auch müll sein.

... und r > 0 und s > 0 ^^

ach mist, also du willst ja im Dreieck und nicht im Dreieck und auf dem Dreieck.
dann muss s + t < 1, s > 0, t > 0.

luki91

was ist r und s ?
ich bin nemlich auch ein noob

luki91 schrieb:

was ist r und s ?
ich bin nemlich auch ein noob

du setzt oben die punkte ein, erhälst ein LGS und löst es nach r und s.
(s. auch Parameterform einer Ebenengleichung)

interpreter

PS: Es ginge auch über baryzentrische Koordinaten:
p = x*p0 + y*p1 + z*p1
mit x+y+z=1
so erhältst du ein LGS mit 3 Gleichungen, dass du nach x,y,z auflösen kannst. Wenn 0<=x,y,z<=1 gilt, liegt p im Dreieck.

luki91

danke für die hilfe,aber das:

px = p1 + r*(p2 - p1) + s *(p3-p1).
Ist r + s <= 1 liegt es im Dreieck.

stimmt bei mir leider überhaupt nicht

interpreter

luki91 schrieb:

danke für die hilfe,aber das:

px = p1 + r*(p2 - p1) + s *(p3-p1).
Ist r + s <= 1 liegt es im Dreieck.

stimmt bei mir leider überhaupt nicht

Vermutlich deshalb, weil die Formel quatsch ist.

luki91 schrieb:

danke für die hilfe,aber das:

px = p1 + r*(p2 - p1) + s *(p3-p1).
Ist r + s <= 1 liegt es im Dreieck.

stimmt bei mir leider überhaupt nicht

hm ich mach mal n beispiel.
p1(0|0)
p2(4|0)
p3(0|4]
-> p2-p1 = (4|0)
-> p3-p1 = (0|4)
px sei mal (1|1)
->
(1|1) = 0|0 + r*(4|0) + s*(0|4)
->
1 = r*4 + s*0 -> r = 1/4
1 = r*0 + s*4 -> s = 1/4
-> r > 0, s > 0, r + s = 0.5 -> px ist in Dreieck

px sei mal (3|2)
->
3 = r*4 + s*0 -> r = 3/4
2 = r*0 + s*4 -> s = 1/2
da 3/4 + 1/2 > 1 ist (3|2) nicht in Dreieck.

interpreter schrieb:

luki91 schrieb:

danke für die hilfe,aber das:

px = p1 + r*(p2 - p1) + s *(p3-p1).
Ist r + s <= 1 liegt es im Dreieck.

stimmt bei mir leider überhaupt nicht

Vermutlich deshalb, weil die Formel quatsch ist.

warum?
Also bei 3-dimensionalen Vektoren funktioniert sie prima.
wüsste nicht, warum das bei 2d nicht gehen sollte.

interpreter, ich würde mich sehr freuen, wenn du mich aufklären würdest, warum meine Formel quatsch sein sollte. Einfach so ne Aussage unbegründet in den Raum zu werfen halte ich für wenig sinnvoll und nicht sonderlich produktiv.
Es ist ja auch nicht so dass du die ganze Zeit offline warst - denn bereits in anderen Mathematik-Threads hast du seither dein Unwesen getrieben.
Außerdem ist es mir schleierhaft, wie folgende Formel von dir funktionieren soll:

interpreter schrieb:

PS: Es ginge auch über baryzentrische Koordinaten:
p = x*p0 + y*p1 + z*p1
mit x+y+z=1

Wo ist die Bedingung p2?!?!
Oder hast du hier einen Fehler gemacht und p1 statt p2 geschrieben?
Mit bitte um Aufklärung,
MfG

luki91

ich weiß wieso es nicht funktioniert!!!
diese berechnung funktioniert nämlich nur bei einem kartesischen koordinatesystem!
das hab ich aber nicht,kannt jemand eine andere lösung ?

mfg
luki

interpreter

Black Shadow_ schrieb:

interpreter, ich würde mich sehr freuen, wenn du mich aufklären würdest, warum meine Formel quatsch sein sollte. Einfach so ne Aussage unbegründet in den Raum zu werfen halte ich für wenig sinnvoll und nicht sonderlich produktiv.
Es ist ja auch nicht so dass du die ganze Zeit offline warst - denn bereits in anderen Mathematik-Threads hast du seither dein Unwesen getrieben.
Außerdem ist es mir schleierhaft, wie folgende Formel von dir funktionieren soll:

interpreter schrieb:

PS: Es ginge auch über baryzentrische Koordinaten:
p = x*p0 + y*p1 + z*p1
mit x+y+z=1

Wo ist die Bedingung p2?!?!
Oder hast du hier einen Fehler gemacht und p1 statt p2 geschrieben?
Mit bitte um Aufklärung,
MfG

wie's aussieht hat wohl doch luki nen fehler gemacht und die formel scheint zu stimmen, sorry.
das 2. p1 meiner formel soll natürlich p2 heißen.

luki91

die formel stimmt da habt ihr recht !
aber nur im kartesischen koordinaten system
hat jemand eine idee wie ich das allgemein rechnen kann ?

mfg
luki

luki91 schrieb:

die formel stimmt da habt ihr recht !
aber nur im kartesischen koordinaten system
hat jemand eine idee wie ich das allgemein rechnen kann ?

mfg
luki

was hast du denn für ein koordinatensystem?

@interpreter: alles klar, deine formel kannte ich auch noch net, thx!
Und ich entschuldige mich für meinen unfreundliche Ton .
MfG,
Black Shadow

luki91

ich weiß nicht wie das system heist aber ich kanns erklären:
limks oben ist 0/0 . x nimmt nach rechts zu, und y nimmt nach unten zu

oggs_the_progger

du kannst annehmen dass wenn der punkt im dreieck liegt die vektoren vom zu prüfenden Punkt P zu den Eckpunkten A,B,C die Summe der Winkel == 360° ist

a ist der Vektor A,P
b B,P

ax = Ax - Px
ay = Ay - Py
bx = Bx - Px
by = By - Py

den Winkel kannst du mit

winkel = 180/PI * arccos((ax*bx+ay*by)/sqrt((ax*ax+ay*ay)*(bx*bx+by*by))