3. Test ob eine Punkt einer Ebene in einem Dreieck in dieser Ebene liegt.

Test ob eine Punkt einer Ebene in einem Dreieck in dieser Ebene liegt.

  • W

    Necrofighter schrieb:

    ich verstehe nicht ganz was du meinst 🙂

    nehme die Vektoren cab, cbc und cca und bereche von zwei Paaren (z.B. cab*cbc und cbc*cca) das Skalarprodukt. Das Ergebnis darf nie kleiner 0 sein, sonst liegt P außerhalb des Dreiecks.

    0
  • N

    Das Problem ist ja, dass die nicht vollkommen identisch sind 😞

    Es sollsten ja vom Betrag 3 gleiche Vektoren da stehen, aber durch die Schwankung wird auch dein Test nicht gehen.

    0
  • W

    Necrofighter schrieb:

    Das Problem ist ja, dass die nicht vollkommen identisch sind 😞

    Es sollsten ja vom Betrag 3 gleiche Vektoren da stehen, aber durch die Schwankung wird auch dein Test nicht gehen.

    natürlich sind die nicht identisch; sie müssen nur in eine 'ähnliche' Richtung zeigen - unabhängig von ihrere Länge. Ist das Skalarprodukt zweier belieber Vektoren >0 so ist ihr Winkel untereinander <90°.
    Und es geht doch nur darum, ob alle Kreuzproduktvektoren zur selben Seite des Dreiecks hin zeigen, oder eben vom Betrag 0 sind. In letzteren Fall liegt P auf einer der Seiten.

    Wenn Du alle drei Paare untersuchst, so kannst Du auch die if( isZero(..) )-Kaskade einfach weglassen.

    Gruß
    Werner

    0
  • N

    Alles klar ich teste das mal.

    Danke für die gute Hilfe.

    Kannst mir ja vielleicht in meinem anderen Thread mit der map of arrays versuchen zu helfen 😉

    0
  • N

    Mal Mathematik:

    Wenn ich die Determinante von (ab,ap,111) und (bc,bp,111) und (ca,cp,111)
    ausrechne, dann ist beim Vorzeichenwechsel der Punkt ausserhalb und wenn nicht sitzt er drin.

    Als weitere Lösung für das Problem 🙂

    0
  • G

    Hallo!

    Ich mache beruflich Geometrie-Software. Geometrische Tests mit Double-
    Koordinaten sind nicht zuverlässig. Aber es gibt einige Möglichkeiten:

    1. Verwende einen exakten Zahlentyp. Das ist vermutlich am einfachsten,
      aber es ist auch sehr langsam. Also bei einer Million Tests würde ich
      es nicht mehr so machen. http://gmplib.org/

    2. Unter www.cgal.org findest Du eine hochwertige Geometrie-Library. Die
      Basiskomponenten, die Du brauchst, stehen unter der LGPL. Der Aufwand,
      das aufzusetzen und sich einzuarbeiten, ist allerdings nicht gering.

    3. Schau Dir http://www.cs.cmu.edu/~quake/robust.html an. Der Source
      Code ist in C geschrieben, aber das sollte sich verwenden lassen.

    lg

    0
  • K

    Kann jemand mal das Problem genauer definieren? Ich verstehe gar nicht, was der OP hier berechnen will.

    0
  • G

    krümelkacker schrieb:

    Kann jemand mal das Problem genauer definieren? Ich verstehe gar nicht, was der OP hier berechnen will.

    Drei Punkte im 3D spannen ein Dreieck auf. Er will testen, ob ein vierter Punkt der gleichen Ebene innerhalb liegt.

    0
  • N

    geom schrieb:

    Hallo!

    Ich mache beruflich Geometrie-Software. Geometrische Tests mit Double-
    Koordinaten sind nicht zuverlässig. Aber es gibt einige Möglichkeiten:

    1. Schau Dir http://www.cs.cmu.edu/~quake/robust.html an. Der Source
      Code ist in C geschrieben, aber das sollte sich verwenden lassen.

    lg

    Hey dann wirst du mir wohl nochmal helfen müssen 🙂

    Gibt es auch irgendwo eine Herleitung zu dieser Determinanten Methode?

    Edit: Was ist dann die Bedingung für die Det, dass der Punkt rechts oder links liegt?

    Und wie übertrage ich das auf 3d?

    Ich finde in dem C-File mich nicht wirklich zurecht 🙂

    0
  • G

    Necrofighter schrieb:

    geom schrieb:

    Hallo!

    Ich mache beruflich Geometrie-Software. Geometrische Tests mit Double-
    Koordinaten sind nicht zuverlässig. Aber es gibt einige Möglichkeiten:

    1. Schau Dir http://www.cs.cmu.edu/~quake/robust.html an. Der Source
      Code ist in C geschrieben, aber das sollte sich verwenden lassen.

    lg

    Hey dann wirst du mir wohl nochmal helfen müssen 🙂

    Gibt es auch irgendwo eine Herleitung zu dieser Determinanten Methode?

    Edit: Was ist dann die Bedingung für die Det, dass der Punkt rechts oder links liegt?

    Und wie übertrage ich das auf 3d?

    Ich finde in dem C-File mich nicht wirklich zurecht 🙂

    Seien p0,p1,p2 die Ecken des Dreiecks und pq der Anfragepunkt. Dann
    transformiere zuerst alle Punkte nach 2D. Dann nimm die orientierten
    Kanten e0(p0,p1), e1(p1,p2), e2(p2,p0) und führe drei Orientierungstests
    mit pq durch. Wenn pq für e0,e1 und e2 auf der gleichen Seite liegt, ist
    pq innen. Sonst nicht. Beachte aber bei der Implementierung den Sonderfall,
    daß pq mit einer Kante collinear sein kann. Herleitungen findest Du sicher
    in den Papers auf der verlinkten Seite.

    Was willst Du eigentlich insgesamt machen? Eine Übung fürs Studium oder
    etwas, das noch mehr Geometrie braucht und in jedem Fall funktionieren
    muß? In diesem Fall ersparst Du Dir viel Ärger, wenn Du eine Anfangs-
    investition machst und Dich in CGAL einarbeitest.

    lg

    0
  • N

    Ich will mittels einer Short Distance projection ein Gitter auf eine Triangulierung schießen.

    Es sind von 140000 Punkten halt noch 8, die ungefähr über einer Kante liegen und in beiden Dreiecken nicht landen.

    0
  • G

    Necrofighter schrieb:

    Ich will mittels einer Short Distance projection ein Gitter auf eine Triangulierung schießen.

    Es sind von 140000 Punkten halt noch 8, die ungefähr über einer Kante liegen und in beiden Dreiecken nicht landen.

    Das ist ein mittelgroßes Problem, für das alle drei Lösungen funktionieren
    werden. Schick mir eine PM, wenn Du noch Geometrie-Tipps brauchst oder an
    prof. Zusammenarbeit interessiert bist.

    lg

    0
Anmelden zum Antworten