Herausfinden ob ein Punkt in einem Dreieck ist?
Hallo,
ich habe mich gefragt, wie man herausfindet, ob ein Punkt in einem 2 Dimensionalen Koordinatensystem innerhalb oder außerhalb eines Dreiecks befindet.Bei einem Viereck ist das ja relativ einfach, aber wie geht das mit einem Dreieck?
Danke
6 Antworten
Bei einem Viereck ist das ja relativ einfach
Auch nur bei achsenparallelen Rechtecken.
Bei einem Dreieck ist es etwas komplizierter:
So prüfst Du, wie ein Punkt P=(xp, yp) zur Geraden AB mit A=(xa, ya) und B=(xb, yb) 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.
Ein Dreieck ABC ist übrigens positiv orientiert, wenn C links von AB liegt. Liegt C rechts davon, prüfe einfach mit dem Dreieck BAC.
nun der Punkt hat ja 2 Dimensionen
Wenn man nun die 3 Seiten betrachtet wie Grundlinie usw müssen die entweder kleiner ( Grundlinie ) oder größer sein sprich die Geraden müssen sich Außerhalb dieses Punktes befinden
Seien A B C die Eckpunkte, D der gesuchte Punkt.
Vektorgleichung X = 0A + r AB + s AC mit D gleichsetzen.
Ist die Summe aus r+s größer 0 und kleiner 1 für r und s > 0. liegt D im Dreieck.
Du kannst die seiten des dreiecks als funktionen auffassen und schauen, ob der punkt dazwischen liegt
Das ist ein Standardproblem der Computergrafik, und betrifft natürlich auch Rechtecke, sofern diese nicht parallel zum Koordinatensystem liegen. Das Problem löst man z.B. mit dem Jordanschen Kurvensatz:
https://de.wikipedia.org/wiki/Punkt-in-Polygon-Test_nach_Jordan