Wie kann man berechnen in einem Java Programm, ob ein Punkt im Dreieck ist, wenn man nur den Punkt(Point) und die Eckpunkte(X-Y-Wert) des Dreiecks hat?

Dies ist eine der Standardaufgaben im Bereich der Computergrafik. Wenn du im Internet danach suchst, findest du bestimmt eine Vielzahl von Kriterien und Algorithmen für einen solchen Test.

Das einfachste, was mir in den Sinn kommt: die baryzentrischen Koordinaten des Punktes bzgl. der Eckpunkte des Dreiecks berechnen. Wenn diese alle zwischen 0 und 1 liegen, liegt der Punkt innerhalb des Dreiecks.

Gegeben: Strecke AB mit A=(xa, ya) und B=(xb, yb).

So prüfst Du, wie ein Punkt P=(xp, yp) zur Geraden AB liegt:

Wenn (xp–xa)(yb–ya) – (yp–ya)(xb–xa)

• < 0: P liegt links von AB
• = 0: P liegt auf der Geraden AB
• > 0: P liegt rechts von AB

In einem positiv orientierten Dreieck ABC liegt P ...

• im Inneren, wenn er links von allen drei Seiten AB, BC und CA liegt.
• außerhalb, wenn er rechts von (mindestens) einer Seite liegt.
• auf dem Rand, wenn er weder innerhalb noch außerhalb liegt.

Je nachdem, ob Du Randpunkte mit zählst, reicht Dir also eine boolesche Funktion, die den obigen Ausdruck auf <0 (links von) bzw. ≤0 (nicht rechts von) prüft.

Caveats:

1. Bei einem negativ orientierten Dreieck muss man überall links und rechts vertauschen. Diesen Fall erkennst Du daran, dass C rechts von AB liegt. Am einfachsten wird es dann sein, A und B zu vertauschen.
2. Für Randpunkte eines entarteten Dreiecks (A, B und C liegen auf einer Geraden) scheitert das Verfahren. Diesen Fall erkennst Du daran, dass C weder links noch rechts von AB liegt. Hier muss man prüfen, ob min(xa,xb,xc)≤xp≤max(xa,xb,xc) ∧ min(ya,yb,yc)≤yp≤max(ya,yb,yc).

Stelle Vektor AP als Linearkombination von AB und AC dar.

Sind beide Koeffizienten vor AB und AC zwischen 0 und 1 ist der Punkt im Parallelogramm ABCD. Dann dasselbe nochmal vom Punkt B aus testen.