Punkt im Dreieck?

Christoph Redl

Hallo!

Wie kann man berechnen, ob ein Punkt innerhalb oder außerhalb eines Dreiecks liegt (im 2D-Raum)?
Ich suche eine Methode, die das Ergebnis möglichst schnell ermittelt, da das ganze an einer performace-kritischen Stelle eingebaut werden soll.

Danke!

mfg

Hallo,

schau dir den Beitrag Rechteckt mal an !

Sonst für beliebiges Polygon gilt es :
1. n Geradegleichungen (Drehsinn beachten !)
2. Abstand des Punktes zu allen Geraden berechnen mit Hilfe und Kreuzprodukt
3. Vorzeichen der Abstände müssen entweder positiv bzw. negativ sein abhängig vom Drehsinn.

Performance :
Für ein Dreieck braucht man 6 Multis + 3 Addis + 2 ANDs zum Ergebnis.

Viel Spass bei der Herleitung !

WebFritzi

OK, sagen wir mal, du hast ein Dreieck.

/\
 /  \
/__*_\__________________x-Achse_____\
 .    \                             /
   .   \
     .  \
       . \
         .\

Der *-Punkt ist zu testen. Erstmal nimmst du dir den "linkesten" Punkt des Dreiecks. Wenn dies 2 sind, dann nimmst du einfach den untersten von beiden. Das ist hier der, wo die x-Achse beginnt. Das soll unser Angelpunkt sein. Von ihm gehen 2 Geraden aus zu den anderen beiden Punkten des Dreiecks. Diese beiden Geraden bilden je einen Winkel mit der x-Achse. Nennen wir diese $\alpha_1$ und $\alpha_2$ und den Winkel unseres Punktes (der mit der x-Achse $\alpha$ , dann muss $\alpha = t\alpha\_1 + (1-t)\alpha\_2$ sein mit einem $t\in (0,1)$ , damit der Punkt im Dreieck liegt. Das ist äquivalent dazu, dass es ein $t\in (0,1)$ gibt, so dass

$t = \frac{\alpha - \alpha\_2}{\alpha\_1 - \alpha_2}$

Also muss der rechte Ausdruck zwischen 0 und 1 liegen. Damit haben wir schon einmal ein Kriterium, dass dein Punkt zwischen den beiden Geraden liegt. Nun soll er aber auch noch "links" von der verbleibenden Geraden sein. Du kennst zwei Punkte auf der Geraden. D.h., du kannst per 2-Punkte-Form eine Geradengleichung $y = mx + c$ aufstellen. Ist dein Punkt (*) $(x\_0, y\_0)$ , dann muss $y\_0 < mx\_0 + c$ gelten. Das war's. Also, erstmal hast du das Winkelkriterium von oben und dann noch das Geradenkriterium. Ergeben beide ein positives Ergebnis, so liegt der Punkt im Dreieck.

P.S.: Ich habe die ganze Zeit angenommen, "im Dreieck" bedeutet, dass er nicht auf dem Rand liegen darf. Soll der dazugenommen werden, dann kann der Winkelbruch (das t) von oben auch 0 oder 1 werden und $y_0$ kann auch $= mx_0 + c$ sein.

Mis2com

Zur Optimierung kann man auch erst überprüfen, ob sich der Punkt im Rechteck um das Dreieck befindet.

Jester

Ich fürchte, damit wirst Du nicht viel rausholen können. Dann lieber zum Dreieck den Mittelpunkt mitspeichern und schaun, wie weit der Testpunkt vom Mittelpunkt entfernt ist, ist es weiter, als der Radius des Umkreises, so kann der Punkt nicht drin sein. Dabei sollte man sich aber genau überlegen, wie oft der Punkt wohl drin liegen wird und wie oft nicht. Denn für jeden Punkt für den wir nachher den Originaltest laufen lassen müssen machen wir Laufzeitverluste, nur für die Ausschlüsse machen wir Gewinn.

Der vorherige Ausschlußtest lohnt sich nur dann, wenn

Ausschlußrate*Auschlußaufwand+(1-Auschlußrate)*(Ausschlußaufwand+normaler Aufwand) <= normaler Aufwand.

Und die Rate hängt wohl erheblich von der Andwendung ab.

MfG Jester