4. Feststellen ob ein Punkt innerhalb eines Dreiecks liegt.

Feststellen ob ein Punkt innerhalb eines Dreiecks liegt.

  • S

    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? 😃

    0
  • S

    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... 👎 😡

    0
  • T

    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;
    0
  • A

    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;
}
    0

  • Hui, Nukem kann den Kopf behalten.

    Bye, TGGC (Dem beste BdT)

    0
  • A

    "Hui, Nukem kann den Kopf behalten."

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

    0
  • S

    Aua...?!? 😕 😞

    0

  • 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)

    0
  • A

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

    0
  • A

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

    0
  • A

    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).

    0
  • A

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

    0
  • T

    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).

    0

  • 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)

    0
  • A

    Das ist eigentlich ganz simpel (gleich kommt der aha Effekt).
    Man errechnet die drei Flächennormalen der Dreiecke, die entstehen wenn man jeweils die Eckpunkte einer Seite mit dem Testpunkt verbindet.
    Wenn der Testpunkt außerhalb des Dreieckes liegt, kehrt sich der Drehsinn des Dreieckes um (und damit auch die Flächennormale). Man muss also nur herausfinden ob alle Flächennormalen das gleiche Vorzeichen haben.
    Das Ganze muss man aber nicht in 3D rechnen die 2d Projektion reicht aus.

    bool STLCAM::Pointtest(Facet P1,Facet P2,Facet P3, Facet Ptest)
{
PXY 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; 
/*            Kreuzprodukt
  Test1.x=((temp1.y * temp2.z)-(temp1.z*temp2.y));
  Test1.y=((temp1.x * temp2.z)-(temp1.z*temp2.x));
  Test1.z=((temp1.x * temp2.y)-(temp1.y*temp2.x));

   das Ganze in 2D ---den Z-Wert auf Null setzen

  Test1.x=((temp1.y * 0.0)-(0.0*temp2.y));
  Test1.y=((temp1.x * 0.0)-(0.0*temp2.x));
  Test1.z=((temp1.x * temp2.y)-(temp1.y*temp2.x));

                  ergibt
  Test1.x=0.0
  Test1.y=0.0
  Test1.z=((temp1.x * temp2.y)-(temp1.y*temp2.x));

                    also
  Test1=((temp1.x * temp2.y)-(temp1.y*temp2.x));

  simpel oder?

*/
Test2=temp2.x * temp3.y-temp2.y*temp3.x;       

if((Test1>0 && Test2>0)||(Test1<0 && Test2<0))  
//haben die ersten zwei Normalen gleiches Vorzeichen 
//wird die Dritte auch noch erechnet
{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;
// sind die ersten zwei Normalen schon unterschiedlich  
// liegt der Punkt schon auserhalb(Funktion kann abgebrochen werden)
}

    Ist doch einfach oder?

    Wo wir gerade dabei sind ich suche noch eine Funktion um den Schnittpunkt einer Geraden bzw. Linie mit einem Kreis zu errechnen (2D).Vielleicht hat Jemand eine zur Hand (Danke im Voraus)
    Gruß ABC++

    0

  • Deine 3D-Deutung ist Humbug. Überprüft wird so lediglich, ob sich der Punkt bezüglich der gewählten Projektion im Dreieck befindet. Projeziert man anders, kann das Ergebnis auch anders sein. In der Bildebene läuft nur das ab, was hier von Anfang an gesagt wurde.

    Kreis-Gerade suchst du erst den Lotpunkt P vom Mittelpunkt M auf die Gerade g. Nennen wir den Abstand von P nach M a, so existieren 0-2 Punkte On auf der Geraden g, wobei für den Abstand d von P nach gilt: r² = a² + d². (nach Satz des Pythagoras)

    Code gibts sicher bei google.

    Bye, TGGC (Dem beste BdT)

    0
  • A

    "Deine 3D-Deutung ist Humbug"??? 😕
    "Projeziert man anders, kann das Ergebnis auch anders sein."

    Na denn Projeziere doch mal anders.
    Also beim mir funktioniert das alles wunderbar, das kann aber auch an meiner Festplatte liegen oder so.:D

    Gruß ABC++

    0
  • T

    ABC++ schrieb:

    Na denn Projeziere doch mal anders.
    Also beim mir funktioniert das alles wunderbar, das kann aber auch an meiner Festplatte liegen oder so.:D

    solang deine projektion nicht grade zum strich mutiert ist das kein problem ,-) ergo: einfach stur z wegwerfen wird dir sauber schiefgehen, sobald dein dreieck auf der x-z oder y-z ebene liegt (oder allgemein der normalenvektor senkrecht zur z-achse steht). deswegen die koordinate wegwerfen, die bei der dreiecksnormalen am größten ist (oder wenigstens eine, die nicht 0 oder fast 0 ist).

    in 2d brauchts auch kein kreuzprodukt (gibts sowieso nicht), da werden x und y vertauscht, eins der vorzeichen geändert und fertig. und wenn du dabei grundsätzlich das vorzeichen für die neue x-koordinate änderst (und die punkte des dreiecks brav gegen den uhrzeigersinn laufen), dann wird die normale auch immer nach "links" (vom vektor aus) zeigen.

    wenn der winkel zwischen temp1 und temp2 < 180 ist, dann liegt die spitze von temp2 auf der linken seite und das skalarprodukt ist positiv, bei 0 ist der winkel genau 180 und der punkt liegt genau auf der kante (dummerweise unbekannt, ob er nicht trotzdem außerhalb des dreieckes liegt). ist der punkt außerhalb, dann ist irgendein winkel automatisch größer als 180, die spitze liegt auf der falschen seite, das ding wird negativ.

    also sollte das hier genau das gleiche ergebnis liefern:

    if (temp1.x * -temp2.y + temp1.y * temp2.x <= 0) return false;
    if (temp2.x * -temp3.y + temp2.y * temp3.x <= 0) return false;
    if (temp3.x * -temp1.y + temp3.y * temp1.x <= 0) return false;
    return true;

    letztlich die gleiche mathe, nur getrickst, um keine seitennormalen berechnen zu müssen. spart 3 subtraktionen, aber dafür sind punkte, die genau auf einer der drei geraden liegen ungünstig.

    0

  • Ein Dreieck, drei Ergebnisse:

    Projektion auf y-z Ebene => daneben
    Projektion auf x-z Ebene => Treffer
    Projektion auf y-x Ebene => WTF?

    ^y                ^y
I                 I   _____
I       /         I   \   I
I      /          I    \  I
I     /           I     \ I
I    /            I      \I
I                 I
I     X...........I.....X
I     :           I
+------------> x  +------------> z  
      :    
^z    :
I     /I
I    /:I
I   / XI
I  /___I
I
+------------> x

    Es sind immer Projektionen möglich, die zu einem Treffer führen, z.b. auf die Tangentialebene des Vektors vom Testpunkt zum Mittelpunkt des Innkreises. Die korrekte 3D-Deutung ist ein 3-seitiges Prisma unendlicher Höhe, senkrecht zur Projektionsebene stehend, und kein einfaches Dreieck.

    Bye, TGGC (Dem beste BdT)

    0
  • T

    und jetzt trauen wir doch einfach zur abwechslung mal einem fragesteller zu, daß er kein totaler dummbeutel ist und den schnitt zwischen gerade und ebene schon längst berechnet hat und für eben diesen den test braucht.

    0
Anmelden zum Antworten