Wie ermittle ich, ob ein Punkt innerhalb oder außerhalb einer Fläche liegt?

Question

ich habe 2 Objekte. Eine Fläche, die durch 4 oder mehr als 4 Punkte beschrieben wird und einen Punkt, der auch x und y-Werte hat und der innerhalb oder außerhalb der Fläche liegen kann. Wie ermittle ich das am besten?

Gruß Andreas

Comments

Hi Andreas,

hast Du mehr Details? Ich mein wenn es sich um eine 2D-Darstellung handelt, kann man es beispielsweise schnell zeichnerisch lösen. Oder sich Geradengleichungen aufstellen und schauen wo sich der Punkt bzgl der Geraden befindet.

Im 3D wirds komplizierter :).

Grüße

---

Ich hatte dies Problem auch schon einmal beim entwickeln von
Computerprogrammen.
Da ich auch keinen " mathematischen " Weg gefunden hatte habe ich
mir die EDV zunutze gemacht.
Der Algorithmus in Worten
Ermittele xmin,xmax,ymin,ymax aus allen Punkten.
Flächengröße ( x_min-1, y_min-1,x_max+1,y_max+1);
Zeichne die Figur durch Verbindung der Punkte.
Dann kann man vom Anfangspunkt x_min,y_min, der garantiert
außerhalb der Fläche liegt, den Befehl floodfill ( x_min_y_min )
( Fluten eines Bereichs in einer bestimmten Farbe ) verwenden
Das Fluten wird immer dann automatisch abgebrochen wenn
eine Linie ( der Figur ) berührt wird.
Am Ende wird nachgeschaut ob der Punkt ( x ,y ) die Hintergrundfarbe
hat. Hat der Punkt die Hintergrundfarbe liegt er außerhalb.
Das hört sich alles recht aufwendig an; funktionierte aber
einmal programmiert tadellos.

---

Ich brauche die Lösung nur für die 2D Ebene. Am Ende will ich es gerade für ein Computer-Zeichenprogramm  nutzen. Die umgrenzende Polylinie (mit 4 oder mehr als 4 Eckpunkten), die die Fläche beschreibt, liegt jedes Mal anders und der darin liegende Punkt, kann irgendwo liegen oder es gibt gar keinen Punkt. Da diese beiden Objekte auch wieder sehr häufig in der Zeichnung vorkommen können, will ich ein Programm schreiben, das nach Auswahl der Umgrenzungslinie einen Auswahlsatz bildet aller auf der Fläche befindlichen Punktobjekte ohne das sie explizit ausgewählt werden müssen. Dazu denke sollte die "Serie" der Eckpunkte der Fläche (x1,y1,x2,y2,x3,y3....) und die Koordinaten des Punktobjektes (x, y), die alle bekannt sind, irgendwie miteinander in Bezug gebracht werden, um zu ermitteln, ob dieser Punkt innerhalb der Fläche liegt oder nicht.

---

Interessant, das du eine Lösung für die EDV / Zeichenprogramm suchst.

Ich hatte auch schon einmal eine mathematische Funktion " innerhalb : boolean "
geschrieben weiß aber nicht ob ich diese noch finde.

Der Sachverhalt :

In Delphi konnte ich eine virtuelle Zeichenfläche erzeugen die lediglich im
Speicher existierte und nicht auf dem Bildschirm. Alle Grafikbefehle waren
auf dieser Zeichenfläche anwendbar

Schritte
einmaliges Erzeugen der Zeichenfläche
Zeichenfarbe black auswählen
Zeichnen des Vielecks. Es sind beliebige Vielecke möglich.
Fluten des Zeichenbereichs aus einer Ecke heraus.
( z.B. links oben. ist garantiert außerhalb des Vielecks )
Auslesen des Pixelfarbe des Punkts.
Ist die Pixelfarbe " black " liegt der Punkt außerhalb
des Vielecks.

---

Wenn es ein Zeichenprogramm sein soll, kannst du auch auf Geoknecht 3D zurückgreifen.

Hier ein Beispiel einer Ebene mit Punkten.

Answer 1

Also mit der Analytischen Geometrie ist das recht simpel.

Nimm einfach mal die Punkte A, B und C und einen Punkt P. Wir stellen die Ebene ABC auf und setzen diese gleich dem Punkt

A + r * AB + s * AC = P

Dieses Gleichungssystem kann man lösen, wenn P in der aufgespannten Ebene liegt.

Ist dann 0 <= r <= 1 und 0 <= s <= 1 und r + s <= 1 liegt der Punkt P auf dem von A, B und C festgelegtem Dreieck.

Ist dann 0 <= r <= 1 und 0 <= s <= 1 und r + s <= 2 liegt der Punkt P auf dem von AB und AC aufgespannten Parallelogramm.

Da man jedes Polygon zur Not in Dreiecke zerlegen kann, kann man das mit jedem Polygon so machen.

In guten Bilbliotheken zur Spieleprogrammierung sind solche Abfragen integriert.