4. Feststellen ob ein Punkt innerhalb eines Dreiecks liegt.

Feststellen ob ein Punkt innerhalb eines Dreiecks liegt.

  • A

    Ich suche einen schnellen Algo um festzustellen ob ein Punkt innerhalb eines Dreiecks liegt.
    Hat Jemand eine Idee?

    Gruß ABC++

    0

  • Entweder:
    Überprüfen ob der Punkt auf der Innenseite aller Dreiecksseiten liegt.

    Oder:
    Überprüfen wie oft die Strecke zu einem Punkt außerhalb des Dreiecks, die Dreiecksseiten schneidet.

    Bye, TGGC (Der Held lebt!)

    0
  • D

    TGGC schrieb:

    Entweder:
    Überprüfen ob der Punkt auf der Innenseite aller Dreiecksseiten liegt.

    Oder:
    Überprüfen wie oft die Strecke zu einem Punkt außerhalb des Dreiecks, die Dreiecksseiten schneidet.

    Bye, TGGC (Der Held lebt!)

    lol, Dir muss aber ganz schön langweilig sein.

    0
  • A

    Jo danke erstmal TGGC,

    Wie überprüft man den ob ein Punkt auf der Innenseite eines Dreieckes liegt?
    Gruß ABC++

    0
  • O

    Anders gehts auch so:
    0≤λ+μ≤10 \leq \lambda + \mu \leq 1
    Dreieck spannst du mit zwei Vektoren auf:

    x⃗=p⃗+λ⋅a⃗+μ⋅b⃗\vec{x} = \vec{p} + \lambda\cdot \vec{a} + \mu\cdot \vec{b}

    MfG

    0

  • ABC++ schrieb:

    Wie überprüft man den ob ein Punkt auf der Innenseite eines Dreieckes liegt?

    Mit einer der beiden Methoden, die ich beschrieb.

    Bye, TGGC (Der Held lebt!)

    0
  • A

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

    0
  • S

    over'load schrieb:

    Anders gehts auch so:
    0≤λ+μ≤10 \leq \lambda + \mu \leq 1
    Dreieck spannst du mit zwei Vektoren auf:

    x⃗=p⃗+λ⋅a⃗+μ⋅b⃗\vec{x} = \vec{p} + \lambda\cdot \vec{a} + \mu\cdot \vec{b}

    Aha. 🕶

    0
  • A

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

    0
  • R

    auf jeden...spann uns nicht auf die Folter 🕶

    0
  • A

    ABC++ schrieb:

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

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

    0

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

    Bye, TGGC (Der Held lebt!)

    0
  • 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
Anmelden zum Antworten