Punkt-in-Polygon-Test
Der Punkt-in-Polygon-Test bestimmt, ob ein gegebener Punkt innerhalb, außerhalb oder auf dem Rand eines Polygons liegt. Er zählt zu den grundlegendsten Operationen der algorithmischen Geometrie und bildet die Basis für räumliche Abfragen, räumliche Verknüpfungen und Geokodierung in GIS-Anwendungen.
Überblick
Der Punkt-in-Polygon-Test (englisch point-in-polygon, kurz PIP) ist ein Algorithmus der algorithmischen Geometrie, der die räumliche Beziehung zwischen einem Punkt und einem Polygon bestimmt und den Punkt als innen, außen oder auf dem Rand liegend klassifiziert. Diese scheinbar einfache Operation gehört zu den am häufigsten ausgeführten räumlichen Abfragen im GISGISGeographic Information Systems (GIS) enable users to analyze and visualize spatial data to uncover patterns, relation... und bildet die Grundlage für räumliche Verknüpfungen (Spatial Joins), die Zuordnung von Adressen zu Gebietsgrenzen und die Prüfung, ob ein Objekt in einer Fläche enthalten ist.
Algorithmen
Das Ray-Casting-Verfahren ist die gebräuchlichste Methode für den Punkt-in-Polygon-Test. Dabei wird von dem zu prüfenden Punkt aus ein halbunendlicher Strahl in eine beliebige Richtung ausgesendet und gezählt, wie oft er den Polygonrand kreuzt. Eine ungerade Anzahl Kreuzungen bedeutet, dass der Punkt innerhalb liegt, eine gerade Anzahl, dass er außerhalb liegt. Der Winding-Number-Algorithmus verfolgt einen alternativen Ansatz: Er berechnet, wie oft sich der Polygonrand um den zu prüfenden Punkt windet. Eine von null verschiedene Windungszahl zeigt an, dass der Punkt innerhalb liegt. Beide Algorithmen kommen auch mit komplexen Polygonen mit Löchern zurecht, wobei Grenzfälle, etwa Punkte exakt auf Randsegmenten oder Eckpunkten, eine sorgfältige gesonderte Behandlung erfordern.
Anwendungsbereiche
Räumliche Verknüpfungen im GISGISGeographic Information Systems (GIS) enable users to analyze and visualize spatial data to uncover patterns, relation... nutzen den Punkt-in-Polygon-Test, um Punktobjekte wie Adressen, GPSGPSThe Global Positioning System (GPS) is a satellite-based navigation system operated by the U.S. Space Force that prov...-Tracks oder Vorfälle den umschließenden Flächenobjekten zuzuordnen, etwa Volkszählungsbezirken, Postleitzahlengebieten oder Verwaltungseinheiten. GeofencingGeofencingGeofencing creates virtual boundaries around real-world geographic areas, triggering automated actions when mobile de...-Systeme prüfen fortlaufend Gerätestandorte gegen virtuelle Grenzpolygone, um Benachrichtigungen oder Aktionen auszulösen. Wahlsysteme ordnen Wähleradressen den zuständigen Wahlbezirken zu. Im Umweltmonitoring werden Sensormesswerte den jeweiligen Überwachungszonen zugewiesen. E-Commerce-Plattformen ermitteln damit die zuständige Steuerjurisdiktion für Lieferadressen.
Performance
Bei großen Datenmengen beschleunigen räumliche Indexstrukturen wie R-Bäume und Quadtrees den Punkt-in-Polygon-Test erheblich, indem sie Polygone, die einen gegebenen Punkt unmöglich enthalten können, frühzeitig ausschließen. So reduziert sich die Berechnung von einem Test gegen alle Polygone auf einen Test gegen nur wenige naheliegende Kandidaten.
Bereit?
Sehen Sie Mapular
in Aktion.
Buchen Sie eine kostenlose 30-minütige Demo. Wir zeigen Ihnen genau, wie die Plattform für Ihren Anwendungsfall funktioniert. Kein generisches Foliendeck, keine Verpflichtung.