Feststellen ob ein Punkt innerhalb eines Dreiecks liegt.

ABC++ 0

"Mit einer der beiden Methoden, die ich beschrieb." - Ach so.

Sgt. Nukem

over'load schrieb:

Anders gehts auch so:
$0 \leq \lambda + \mu \leq 1$
Dreieck spannst du mit zwei Vektoren auf:

$\vec{x} = \vec{p} + \lambda\cdot \vec{a} + \mu\cdot \vec{b}$

Aha.

ABC++ 0

So ich habe ne gute Lösung.
Neugierig ???

randa

auf jeden...spann uns nicht auf die Folter

Ahvolon*F-Bytes*

ABC++ schrieb:

So ich habe ne gute Lösung.
Neugierig ???

Klar, sowas tolles kann ja nicht jeder. Da gehört echt viel dazu.

TGGC

Ich wette Nukem's Kopf, es basiert auf schon erwähnten Ideen.

Bye, TGGC (Der Held lebt!)

spl*t

Ich finde schon das ein schneller Algo dafür nicht soo leicht ist. Hatte vor ein paar Tagen erst selbst das Problem. Ich komme jetzt mit 6 Vektorsubtraktionen, 3 Crossproducts und ziemlich vielen if´s aus. Wer ist besser?

Sgt. Nukem

TGGC schrieb:

Ich wette Nukem's Kopf, es basiert auf schon erwähnten Ideen.

Wie rücksichtsvoll von Dir, mich auch in eure kleine Diskussion zu integrieren...

P.S.: Fix doch einer mal die LaTeX-Pics hier...

Trienco

spl@t schrieb:

...und ziemlich vielen if´s aus. Wer ist besser?

hmmm... testen. aus dem bauch raus würde ich vermutlich jederzeit ein if gegen ein bis zwei z.b. skalarprodukte tauschen. profilen, sofern der code überhaupt zentral genug ist.

aber wer mal eine besonders ungewöhnliche (naja, vermutlich auch nicht mehr) lösung machen will, kann sich ja mal plücker koordinaten ansehen. das bequeme daran war, daß man schnell am skalarprodukt rausfinden konnte, ob sie im raum im oder gegen den uhrzeiger aneinander vorbeilaufen. auf die art muß man nur prüfen, ob die vorzeichen für alle seiten des dreiecks gleich sein.

falls es hier nur um 2d geht würde ich das ganze aber wieder vergessen, außerdem würde das hin und her konvertieren wahrscheinlich jeden vorteil zunichte machen, ergo müßte man die darstellung in plücker-koordinaten nochmal zusätzlich speichern. die operation selbst wäre dann natürlich auch nochmal einen tick komplexer als ein normales 3d skalarprodukt (aber schön parallelisierbar).

sehr schön, die artikel dazu bei flipcode gibts immer noch *g*
http://www.flipcode.com/articles/dpcolumn_issue02.shtml

edit: ich denk mal wieder einen schritt zu weit. wir sind ja erst bei punkten in dreiecken.

mit a,b,c die drei eckpunkte und p der fragliche punkt

vec2 A(a.x-b.y, b.x-a.x);
vec2 B(b.x-c.y, c.x-b.x);
vec2 C(c.x-a.y, a.x-c.x);
vec2 d1=p-a, d2=p-b, d3=p-c;
return (A*d1<0 || B*d2<0 || C*d3<0) 0 : 1;

oder als häßlicher einzeiler, dafür ohne variablen

return (((a.y-b.y)*(p.x-a.x) + (b.x-a.x)*(p.y-a.y)) <0 ||
        ((b.y-c.y)*(p.x-b.x) + (c.x-b.x)*(p.y-b.y)) <0 ||
        ((c.y-a.y)*(p.x-c.x) + (a.x-c.x)*(p.y-c.y)) <0) ? 0 : 1;

ABC++ 0

Ist bestimmt noch Verbesserungsfähig

/*
struct Point2D{
float x,y;
};

struct Point3D{
float x,y,z;
};

Ptest der zu überprüfende Punkt (ein errechneter Schnittpunkt von einer Geraden mit einem Dreieck)
P1,P2,P3 sind die Eckpunkt vom Dreieck. 
Die Rechnung benutz nur die 2D Projektion der Eckpunkte deswegen werden die Z-Werte vernachlässigt.

if(Pointtest(P1,P2,P3,Ptest))
printf("der Punkt liegt im Dreieck");
else
printf("der Punkt liegt nicht im Dreieck");

*/

bool Pointtest(Point3D P1,Point3D P2,Point3D P3,Point3D Ptest)
{
Point2D temp1,temp2,temp3;
float Test1,Test2;

 temp1.x=P1.x-Ptest.x,
 temp1.y=P1.y-Ptest.y,
 temp2.x=P3.x-Ptest.x,
 temp2.y=P3.y-Ptest.y, 
 temp3.x=P2.x-Ptest.x,
 temp3.y=P2.y-Ptest.y;

Test1=temp1.x * temp2.y-temp1.y*temp2.x;
Test2=temp2.x * temp3.y-temp2.y*temp3.x;

if((Test1>0 && Test2>0)||(Test1<0 && Test2<0))
{Test2=temp3.x * temp1.y-temp3.y*temp1.x;
  if((Test1>0 && Test2>0)||(Test1<0 && Test2<0))
     return true;
     else
      return false ;
}
else
return false;
}

TGGC

Hui, Nukem kann den Kopf behalten.

Bye, TGGC (Dem beste BdT)

ABC++ 0

"Hui, Nukem kann den Kopf behalten."

Nö Nö Nukem muss sein Kopf abgeben.
Das beruht nicht auf deinen Ideen.
Her damit !!

Sgt. Nukem

Aua...?!?

TGGC

ABC++ schrieb:

Nö Nö Nukem muss sein Kopf abgeben.
Das beruht nicht auf deinen Ideen.

a) Ich sprach nicht von "_meinen_ Ideen"
b) Es wird überprüft, ob der Punkt auf der Innenseite aller Dreiecksseiten liegt.

Bye, TGGC (Dem beste BdT)

ABC++ 0

"Punkt auf der Innenseite aller Dreiecksseiten liegt"
Nö das passiert da nicht.

Ahvolon*F-Bytes*

ABC++: Alles nochmal genau lesen und mal darüber nachdenken wie eine Dreiecksseite denn eine Innen- und Aussenseite haben kann.

ABC++ 0

Ich denke ich werde wohl wissen wie ich das hergeleitet habe und nach welcher Methode das funktioniert. Mit ein bisschen Verstand erkennt das Jeder(vielleicht fast Jeder).

Ahvolon*F-Bytes*

Schade dass dus nicht verstanden hast. ist im Grunde ein gutes Wortspiel. Mit ein bisschen Verstand erkennt das Jeder(vielleicht fast Jeder).

Trienco

ABC++ schrieb:

Ich denke ich werde wohl wissen wie ich das hergeleitet habe und nach welcher Methode das funktioniert.

erklärs mir trotzdem.
-du berechnest drei vektoren temp vom punkt zu den drei ecken (hier siehts verdächtig nach der winkel addieren methode aus)

-dann verdächtige skalarprodukte von einem der vektoren mit einem anderen (der um 90° gedreht ist)

-dann ein vergleich auf gleiches vorzeichen, aber weder die deutung als skalierter cos noch als projektion von einem vektor auf den anderen will mir dabei in den kopf gehen

nachvollziehen würde ich die lösung höchstens, wenn du die temp vektoren mit der jeweiligen seitennormalen verwursten würdest, aber untereinander? entgeht mir eine grundlegende beobachtung über das verhalten von dreiecken? *verwirrt*

wenn ich jetzt berücksichtige, daß genau ein winkel größer als 180° sein muß, wenn der punkt außerhalb liegt.. hm, stimmt, dann müßte die "normale" und der andere vektor in verschiedene halbräume zeigen, das vorzeichen von dem skalarprodukt wäre negativ ("strenge" ausrichtung der "normalen" vorausgesetzt, dann könntest du dir auch den test sparen, ob beide negativ sind, weil es nicht vorkommen sollte)

also wenn ich das richtig nachvollziehe, dann ist das ein ziemlich wilder zwitter aus winkel messen und seite prüfen.

*rechne* falls die methode wirklich funktioniert und es keine sonderfälle gibt, die einen in den hintern beißen, dann wär sie noch 3 subtraktionen kürzer. allerdings könntest du dann wie gesagt auch einfach sicherstellen, daß die punkte in der reihenfolge gegen den uhrzeiger laufen, die "normale" immer 90° nach links gedrecht wird und jedes skalarprodukt für sich allein auf negativ prüfen (und in dem fall abbrechen).

TGGC

Die beiden Tests sind jeweils die Frage, ob zwei Eckpunkte des Dreiecks auf verschiedenen Seiten einer Gerade durch den dritten und den Testpunkt liegen. Oder anders gesagt: liegt der Testpunkt im Doppelkegel zweier Dreiecksseiten? Nun, dieser Doppelkegel ist nichts weiter als der Schnitt zweier Halbräume die ich als Innenseite einer Dreieckseite bezeichnen würde.

Bye, TGGC (Dem beste BdT)