Punkt in 2D 3Eck

82kolu

Hey,
kann mir einer sagen ob die Formel hier richtig ist?
bzw wo der fehler ist? weil ich immer einen Punkt der klar auserhalb liegt als innen angezeigt wird....

typedef struct
{
   int x;
   int y;
} Vektor;

bool CouldBeInTriangle(Vektor PUNKTA, Vektor PUNKTB, Vektor PUNKTC, Vektor PUNKTP)
{
   Vektor a,b,p;
   a.x = PUNKTC.x - PUNKTA.x;
   a.y = PUNKTC.y - PUNKTA.y;
   b.x = PUNKTB.x - PUNKTA.x;
   b.y = PUNKTB.y - PUNKTA.y;
   p.x = PUNKTP.x - PUNKTA.x;
   p.y = PUNKTP.y - PUNKTA.y;

   double s,r;
   s = ( p.x - ((a.x*p.y)/a.y) ) / ( b.x - ((a.x*b.y)/a.y) );
   r = ( p.x - (s*b.y)) / a.y;
   if ( s >= 0 && r >= 0) {
      return true;
   } else {
      return false;
   }
}

bool IsInTriangle(Vektor A, Vektor B, Vektor C, Vektor P)
{
   if (CouldBeInTriangle(A,B,C,P)) {
      if (CouldBeInTriangle(B,A,C,P)) {
         return true;
      }
   }
   return false;
}

Und jetzt wird kein einziger punkt mehr als innen nagezeigt...

SeppJ

Na, wenn es nicht das richtige Ergebnis liefert, dann wird's wohl falsch sein.

Da ich ohne Kommentare im Code die Idee dahinter nicht erkennen mag (und sie ja ohnehin falsch ist), schlage ich dir einfach mal eine andere, sehr einfache, Methode vor:
Wenn du die Punkte A,B,C und P gegeben hast, kannst du mittels ((B-A)x(P-A)).((B-A)x(C-A)) >= 0 feststellen, ob der Punkt P und der Punkt C auf der gleichen Seite der Linie AB sind. Ein Punkt ist genau dann in einem Dreieck, wenn dies für alle drei Seiten gilt.

Dies ist sicher nicht die effizienteste Technik, aber sehr anschaulich und daher gut zu merken und auch sehr einfach zu implementieren. Falls Effizienz eine Rolle spielt, bemühe Google.

82kolu

SeppJ schrieb:

Na, wenn es nicht das richtige Ergebnis liefert, dann wird's wohl falsch sein.

Da ich ohne Kommentare im Code die Idee dahinter nicht erkennen mag (und sie ja ohnehin falsch ist), schlage ich dir einfach mal eine andere, sehr einfache, Methode vor:
Wenn du die Punkte A,B,C und P gegeben hast, kannst du mittels ((B-A)x(P-A)).((B-A)x(C-A)) >= 0 feststellen, ob der Punkt P und der Punkt C auf der gleichen Seite der Linie AB sind. Ein Punkt ist genau dann in einem Dreieck, wenn dies für alle drei Seiten gilt.

Dies ist sicher nicht die effizienteste Technik, aber sehr anschaulich und daher gut zu merken und auch sehr einfach zu implementieren. Falls Effizienz eine Rolle spielt, bemühe Google.

Danke! ich schau noch bisschen in Google sonst nehm ich die Idee

knivil

Man macht eine LeftOf-Test fuer alle 3 Seiten. Liegt der Punkt auf der linken Seite fuer alle Dreiecksseiten, so liegt er im Dreieck. LeftOf-Test ist sehr leicht mit dem Skalarprodukt zu realisiere (das Kreuzprodukt kann man wahrscheinlich auch nutzen).