Überprüfen, ob sich ein Punkt innerhalb eines Vierecks befindet

Question

Hallo, ich habe einen Punkt P und das Viereck ABCD und möchte überprüfen, ob sich P innerhalb des Vierecks oder außerhalb befindet. Das Ganze ist im zweidimensionalen Raum.

Comments

Um was für ein Viereck handelt es sich?

---

Ein beliebiges Viereck, keine bestimmte geometrische Form.

Answer 1

Hallo,

teile das Viereck zunächst in zwei Dreiecke und prüfe anschließend, ob sich der Punkt \(P\) in einem der beiden Dreiecke befindet. Für die Prüfung im Dreieck \(\triangle ABC\) bestimme die Richtungsvektoren \(u=\vec{AB}\) und \(v=\vec{AC}\). Diese spannen zusammen mit \(A\) ein (nicht kartesisches) Koordinatensystem auf:$$k: \quad x = A + r \cdot u + s \cdot u $$mit den freien Parametern \(r\) und \(s\). Löse das Gleichungssystem $$\begin{aligned} A + r \cdot u + s \cdot u &= P \\ r \cdot u + s \cdot u &= P-A\end{aligned}$$nach \(r\) und \(s\). Wenn \(r \ge 0 \land s \ge 0 \land r+s \le 1\), dann befindet sich \(P\) innerhalb von \(\triangle ABC\).

Gruß Werner

Comments

Beachte das es eventuell auch konkave und überschlagene Vierecke geben kann.

Sowas sollte eventuell vorher abgefangen werden.

Ich hatte mal ein Geometrieprogramm für den C64 geschrieben habe das aber Aufgrund der etwas trägen Geschwindigkeit (von BASIC) nicht weiter verfolgt :)

---

Beachte das es eventuell auch konkave und überschlagene Vierecke geben kann.

ein Grund mehr, eine Datenbasis auf Dreiecke zu definieren, statt auf beliebige Vierecke.

Answer 2

Hm,

von einem Punkt innerhalb ABCD gibt es in EINER Richtung genau 2 Schnittpunkte mit den Rand bildenden Geraden z.B. x+Richtung