Abstand eines Punkts zu einem Dreieck

[Nikolas]

Hallo Delphianer

Ich habe ein kleines Problem bei meinem aktuellen Projekt, dass auf den ersten Blick nicht allzu schwer aussieht.
Es geht darum, dass ich ein Dreieck im R3 durch seine Eckpunkte gegeben habe und nun den Abstand zu einem weiteren Punkt berechnen soll. Mit Abstand meine ich hier den kleinstmöglichen, also zwischen dem Punkt und einem der Eckpunkt, oder einem Punkt auf einer der drei Strecken, oder innerhalb des Dreiecks.

Mein Ansatz sieht so aus:
Berechne den Punkt in der Ebene, in der das Dreieck liegt, der den kleinsten Abstand zum gegebenen Punkt hat. Wenn dieser Punkt innerhalb des Dreiecks liegt, ist man fertig. Ansonsten betrachtet man die drei Strecken und macht eine Gerade-Punkt-Abstands berechnung und kommt so auch ans Ziel.

Der Punkt an dem ich gerade hänge, ist die Entscheidung, ob der Punkt innerhalb des Dreiecks liegt. Zur Zeit gehe ich von einer Darstellung des Dreiecks in Parameterdarstellung aus, wobei ich alle Punkte so verschiebe, dass einer der Eckpunkt des Dreiecks im Ursprung liegt. (dann: alpha*r_1+beta*r_2 ) Wenn ich aber alpha*r_1+beta*r_2 = P auflösen will, um dan später zu untersuchen, ob alpha und beta im richtigen Intervall liegen, komme ich auf Nenner, bei denen ich nicht genau sagen kann, ob sie nicht Null sind.

Hat da vielleicht jemand eine bessere Idee? Als zusätzliche Schwierigkeit kommt hinzu, dass diese Abfrage später in meiner Anwendung SEHR häufig ausgeführt werden muss, so dass die Laufzeit wichtig ist. Da die betrachteten Dreiecke sich nicht verändern, sondern nur die Punkte, können Hilfswerte wie Normalenvektoren schon im Vorraus berechnet werden.

Nikolas

[jfheins]

Um zu prüfen ob ein Punkt in der Ebene in dem Dreieck liegt könntest du folgendes machen:

Kleine "Skizze":

Code:

*   A
   x

                             x P
x
B

          x
           C

Das Dreieck besteht jetzt mal aus A. b und C und der Punkt ist P

1. Ermittle den Winkel ABC und den Winkel PBC mittels Skalarprodukt. Bildlich gesprochen: Liegt der Punkt P aus Sicht von B zwischen den Punkten A und C?
2. Wenn das passt (PBC > 0 && PBC < ABC), musst du das noch für eine andere Ecke machen.

Du brauchst wahrscheinlich nichtmal den Winkel errechnen und kannst dir so den arccos sparen um noch etwas rechenzeit herauszuholen.

[Nikolas]

Für die Winkelberechnung bräuchte ich doch einen Aufruf von acos, was leider zu teuer ist. Der Vergleich wird ein Tausend Mal pro sekunde ausgeführt werden, da ist Trigonometrie verboten. Aber Danke für die Idee.

[himitsu]

Gab es nicht mal vor einer Weile zu einem der 3D-Spiel-Projekte hier soein Thema?

Also bezüglich Kollisionsabfrage.
Da muß es ja auch recht schnell gehen.

[jfheins]

Zitat:

Zitat von Nikolas

Für die Winkelberechnung bräuchte ich doch einen Aufruf von acos, was leider zu teuer ist. Der Vergleich wird ein Tausend Mal pro sekunde ausgeführt werden, da ist Trigonometrie verboten. Aber Danke für die Idee.

Ich weis nicht ob du mein Edit gesehen hast, deshalb nochmal genauer:

Der arccos ist streng monoton fallend - da du ja nur eine qualitative Aussage brauchst kannst du ihn ja sogar duch eine Gerade annähern! (Wenn man das noch annähern nennen kann)

[Apollonius]

Eine recht einfache Variante wäre auch, die Summe der Flächen der Dreiecke ABP, BCP und CAP zu berechnen. Wenn sie größer ist als die Fläche von ABC, liegt P außerhalb des Dreiecks.

[himitsu]

Man könnte auch erstmal nur schauen, ob P über, unter, rechts oder links der entsprechenden äußersten Punkte liegt ... wenn ja, dann liegt P auf jeden Fall außerhalb und wenn nein, dann genauer rechnen.

[brechi]

Ist ein relativ einfaches Problem: Punkt in Polygon ->
Man suche sich einen weiteren Punkt im unendlichen (Boundingbox.X des Polygons + 1)

Dann schneidet man die Gerade zwischen den Punkten (der zu überprüfende und der im unedlichen) mit allen Geraden des Polygons und zähl die Schnittpunkte.
Ungerade Anzahl = im Polygon
Gerade Anzahl = außerhalb des Polygons

[Nikolas]

Wunderbar, ihr seid echt gut : )

Das mit dem Winkel werde ich mir mal anschauen, da bräuchte ich nur 2-4 Skalarprodukte, bei der Methode über die Flächen (die ich fast noch anschaulicher finde) bräuchte ich 4 Kreuzprodukte, die schon etwas teurer sind (grob Faktor 2 gegen Skalarprodukte).
Manchmal hilft es wirklich, ein bischen geometrie zu nutzen und nicht gleich groß loszurechnen.

@himitsu: stimmt. So eine Boundingbox wäre auch vorher berechenbar, so dass ich mir mit schlappen 6 Vergleichen die Rechnung ganz sparen kann. Da die Dreiecke auch tendenziell klein sind, wird der Fall, dass der Punkt im Dreieck liegt, eher selten auftreten, so dass deine Idee noch mal gut Zeit rausholen wird.

@brechi: Auch was schönes. Nur könnte ich da Probleme mit den degenerierten Fällen haben. (Punkt auf Strecke, oder einem Endpunkt.) Ich schau mal, ob solche Fälle mir Probleme machen könnten, und wie er sich zeitlich zu den anderen Fällen verhällt.

Je nach dem wie motiviert ich heute bin, werde ich mehrere Versuche implementieren und dann sagen, wie sie zeitlich abschneiden...


Beim nächsten Problem werde ich gleich herkommen. :mrgreen:

[Apollonius]

Für die Flächenmethode brauchst du nur drei Kreuzprodukte - die Fläche von ABC kannst du vorher berechnen. Wenn der Punkt außerdem weit außerhalb des Dreiecks liegt, kannst du häufig schon früher abbrechen.

[Nikolas]

Da hast du auch recht. Und da es die einfachste ist, werde ich sie auch als erste implementieren. Da gibt es keine Spezialfälle und Vorzeichen muss ich auch nicht beachten :mrgreen:

[SimStar001]

Stichwort: ANALYTISCHE GEOMETRIE!!!


einfach drei Gerade bilden (A-B) (B-C) und (C-A) und jeweils den Normalenvektor zu P von jeder Gerade bilden und den Abstand berechen.

wenns nur im 2D ist noch einfacher:

z.b. A = 0,0
B = 1,5
C = 3,1

nun die gerade (a-b) x*(1,5) --> sekrechter Winkelvektor dazu v(5,1) und nun haste ne neue Gerade mit Punkt p als punkt und dem senkrechten vektor zu (a-b). nun nur noch den Schnittpunkt der beiden geraden bilden und du hast den Punkt auf der geraden (a-b) der Punkt P am nächsten ist.


Das ganze musste für alle geraden machen und dann gucken welcer wert am kleinsten ist!

[Nikolas]

So, die ersten Ergebnisse sind da.

Ich habe erstmal die Methode mit der Fläche implementiert und kam auf 400Berechnungen/ms (10.000.000 in 25,600s).
Gerade eben habe ich noch den Vorschlag mit der Boundingbox implementiert und habe dadurch nochmal auf 19,800s beschleunigen können, was dann grob 500Berechnungen pro ms entspricht.
Vielleicht werde ich in den nächsten Tagen noch die anderen Optionen ausprobieren, spätestens wenn das Programm, das auf der Berechnung hier beruht zu langsam läuft, werde ich mir die Operation noch mal genauer anschauen.

Auf jeden Fall vielen Dank für die vielen guten Ideen : )