Re: Punkt in Polygon

Punkt in Polygon (6 Beiträge, 222 Mal gelesen)

Du bist nicht angemeldet. [ Login/Registrieren ]

Hi!

Ich habe eine Vielzahl an Polygonen in der Datebank (definiert über n Ecken mit jeweils einem Koordinaten-Paar).

Meine Aufgabe ist es jetzt, herauszufinden, ob sich ein Punkt (definiert über ein Koordinaten-Paar) innerhalb einer der Polygone befindet. Diese Abfrage muss in "Echtzeit" passieren, d.h. ich kann nicht jedes Polygon mit einem komplizierten Algorithmus einzeln behandeln.

Da es schnell gehen aber nicht unbedingt absolut exakt berechnet werden muss, ist mein Denkansatz, die Fläche, in der sich die Polygone befinden, schon im Vorfeld in eine Vielzahl von Quadraten zu teilen (also ein Raster drüberzulegen) und zu ermitteln, welche Quadrate in welche Polygone fallen. Ich muss dann nur noch in Echtzeit ermitteln, in welchem Quadrat sich mein Punkt befindet und mir dann nur noch die zuvor ermittelten Polygone holen, in denen das Quadrat liegt.

Habt ihr eine bessere Idee? Und wenn nein, wie ermittle ich am besten, ob sich ein Quadrat innerhalb eines Polygons befindet?

Re: Punkt in Polygon (Ardjan am 02.02.2014, 13:16:34)

Re: Punkt in Polygon (mossess am 02.02.2014, 13:29:38)

Re: Punkt in Polygon

(LFMoe18 am 02.02.2014, 18:59:15)

Re: Punkt in Polygon (ZombyKillah am 02.02.2014, 20:43:00)

Die Algorithmen für diese Aufgabenstellung sind seit Jahrzehnten bekannt und sollten in jedem besseren Buch zur Einführung in Computergraphik zu finden sein.

Dabei gibt es noch 2 Fälle zu unterscheiden: sind die Polygone konvex (einfach zu testen, grob gesagt: befindet sich eine Koordinate zw. je 2 Punkten eines Polygons) oder konkav (schwieriger, da Fallunterscheidungen und Schnitte von Linien)

--------------------------------------------------------
Falls sowohl Auflösung und die Anzahl der Polygone "überschaubar" sind, wäre folgender Ansatz eine Option:

du "zeichnest" die Polygone, so, wie es jede Graphik-API vorsieht, in einen Framebuffer (=Array in der Auflösung und gewisser Bittiefe) und füllst sie mit einer individuellen Farbe. Wobei wiederum gilt:

Falls die Polygone überlappen (dürfen), müsstest du die "Farbe" bitweise vergeben + per OR-Verknüpfung füllen. Das würde natürlich bedeuten, daß du einen 16bit-Array brauchst, um 15 überlappende Polygone zu unterscheiden, ohne Überlappung hingegen gehen 2^16 (-1 ... Hintergrund / kein Polygon).

In beiden Fällen besteht dann der Test einfach darin, die Koordinaten abzufragen - ein Wert > 0 ("Hintergrund") bedeutet Polygon "getroffen", durch herauspfriemeln der Bits bei überlappenden sogar alle auf einmal -> Aufwand praktisch konstant.

Dieses Forum ist eine frei zugängliche Diskussionsplattform.
Der Betreiber übernimmt keine Verantwortung für den Inhalt der Beiträge und behält sich das Recht vor, Beiträge mit rechtswidrigem oder anstößigem Inhalt zu löschen.
Datenschutzerklärung