4. Feststellen ob ein Punkt innerhalb eines Dreiecks liegt.

Feststellen ob ein Punkt innerhalb eines Dreiecks liegt.

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

    dann würde aber jeder vorteil durch die obere version schon im keim erstickt wereden, da der vergleich malwieder kostet-.-

    0
  • A

    TGGC
    ich habe keine Ahnung für welche merkwürdigen Vergleiche du solche Berechnungen brauchst. Bei mir Jedenfalls wird vorher der Schnittpunkt mit der Dreiecksebene berechnet. Auf deutsch der Punkt liegt in einer Ebene mit dem Dreieck und dann passt es (wie auch sonst).
    Also keine Panik!

    Trienco
    "solang deine projektion nicht grade zum strich mutiert ist das kein problem ,-) ergo: einfach stur z wegwerfen wird dir sauber schiefgehen,"

    das ist soweit richtig. Aber durch zwei if abfragen kann man festellen in welchen Quadranten die Rechnung passt und setzt dann z.B: für z den x Wert und x den z Wert .
    Aber wie gesagt ich berechne vorher einen Schnittpunkt mit der Dreieckseben und weiß daher das das Dreieck nicht senkrecht steht.

    "
    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;"

    Wenn die Eckpunkte in Unterschieden Quadranten liegen (z.B. temp2.x negativ) das passt deine Rechnung nicht mehr (meine schon).

    0
  • T

    ABC++ schrieb:

    Wenn die Eckpunkte in Unterschieden Quadranten liegen (z.B. temp2.x negativ) das passt deine Rechnung nicht mehr (meine schon).

    *rechne, mal, pinsel*
    ok, nach links zeigt es immer *weiterpinsel*
    unabhängig vom quadranten bleibt das skalarprodukt bis 180° positiv. solang meine drehrichtung stimmt sollte da nichts passieren. hat natürlich den nachteil, daß ich bei der projektion zusätzlich aufpassen muß, daß ich von "vorn" draufsehe oder die reihenfolge umkehre. klingt spontan nach mehr aufwand als es wert ist.

    muß jetzt doch mal nen stapel testfälle durch den profiler jagen *g*

    edit: so, nach ein bißchen rumspielen und ohne den overhead für rdtsc rauszuwerfen (und mit ein wenig meßungenauigkeit und zig tests, die +-3 ticks ausgefallen sind):

    mit seitennormalen und:
    if (a.x*n1.x + a.y*n1.y < 0) return 0;
    if (b.x*n2.x + b.y*n2.y < 0) return 0;
    if (c.x*n3.x + c.y*n3.y < 0) return 0;
    return 1;

    227 ticks (die variationen mit 231 und 235 minimal langsamer, einmal t1 bis t3 mit 0 vergleichen, einmal siehe unten)

    deine methode und:
    float d1=b.y*a.x - b.x*a.y;
    float d2=c.y*b.x - c.x*b.y;
    float d3=a.y*c.x - a.x*c.y;
    return (t1*t2<0 || t2*t3<0) ? 0 : 1;

    220 ticks (die andere mit 265 etwas langsamer)

    also in kurz: vollkommen uninteressante unterschiede, wenn der compiler erstmal mit dem code fertig ist.

    0
Anmelden zum Antworten