Punkt-in-Polygon

Ein Punkt-in-Polygon-Test beantwortet eine grundlegende Frage der algorithmischen Geometrie: liegt ein Abfrageort bei einer geschlossenen Form aus einem geordneten Eckpunkt-Ring im Inneren der Form? Vermessung, Kartenprodukte, Spiel-Kollisionsmasken, Logistik-Geofences und Geometrie-Labore im Unterricht brauchen dieselbe deterministische Antwort statt einer Handskizze. Dieser Prüfer implementiert den klassischen Gerade-ungerade-Raycasting-Algorithmus auf planaren Koordinaten: ein horizontaler Halbstrahl wird vom Testpunkt zur positiven Unendlichkeit geworfen, jede Polygonkante wird auf eine echte Kreuzung geprüft, und die Parität der Kreuzungszahl entscheidet innen versus außen. Punkte genau auf einer Kante oder einem Eckpunkt gelten als innen und erhalten ein Rand-Flag, damit Closed-Set-Nutzer keinen zweiten Durchlauf brauchen. Das Polygon wird implizit geschlossen — Sie müssen den ersten Eckpunkt am Ende nicht wiederholen — und Eckpunkte können als Objekte mit x- und y-Feldern oder als Zwei-Element-Arrays geliefert werden. Bei weniger als drei Eckpunkten schlägt die Anfrage mit einem klaren Validierungsfehler fehl, weil ein Polygon mindestens ein Dreieck braucht.

Wie der Gerade-ungerade-Raycasting-Test funktioniert

Starten Sie mit einem endlichen Abfragepunkt mit Koordinaten x und y und einer geordneten Liste von mindestens drei planaren Eckpunkten, die ein einfaches geschlossenes Polygon bilden, wenn aufeinanderfolgende Eckpunkte verbunden werden und der letzte zum ersten zurückführt. Der Algorithmus verlangt keine Uhrzeiger- oder Gegen-Uhrzeiger-Reihenfolge; beide Orientierungen sind unter der Gerade-ungerade-Regel gültig. Vom Abfragepunkt aus stellen Sie sich einen horizontalen Strahl vor, der nur nach rechts läuft, nie nach links.

Gehen Sie jede Kante des Polygons ab und entscheiden Sie, ob diese Kante den Strahl kreuzt. Horizontale Kanten werden ignoriert, damit keine mehrdeutigen Doppelzählungen entstehen. Wenn eine Kante die Strahlhöhe überspannt — ein Endpunkt streng oberhalb des Abfrage-y und der andere nicht — wird das exakte x des Schnittpunkts mit einem linearen Parameter entlang der Kante berechnet.

Liegt das Abfrage-x streng links von diesem Schnitt, trägt die Kante eine Kreuzung bei; fällt der Schnitt mit der Abfrage innerhalb einer winzigen numerischen Toleranz zusammen, wird der Punkt als auf dem Rand klassifiziert. Nach Verarbeitung aller Kanten bedeutet eine ungerade Kreuzungszahl innen und eine gerade außen — das klassische Jordan-Kurven-Paritätsargument spezialisiert auf einen horizontalen Strahl. Koordinaten müssen endlich sein; NaN und Infinity werden abgelehnt.

Wo Punkt-in-Polygon-Prüfungen in der Praxis vorkommen

Logistik- und Lieferprodukte fragen, ob ein Kurier-GPS-Fix in einem Nachbarschaftspolygon liegt, bevor ein zonenspezifischer Tarif angeboten wird, und brauchen eine deterministische Antwort, die zwischen Browser-Kartenvorschau und Server nicht driftet. Spiele und interaktive Medien nutzen achsenausgerichtete oder freiformige Kollisionsmasken als Eckpunkt-Ringe und prüfen Spieler- oder Projektilpositionen jedes Frame ohne einen schweren GIS-Stack. Unterrichtsmodule zur algorithmischen Geometrie lehren Raycasting, Jordan-Kurven-Intuition und Gleitkomma-Grenzfälle; ein einziges vertrauenswürdiges Orakel, das sowohl das Inside-Flag als auch die rohe Kreuzungszahl liefert, hilft Studierenden, Hausaufgaben schrittweise zu prüfen.

Stadtplanung und Katasterwerkzeuge klassifizieren Stichprobenpunkte gegen Gebäudegrundrisse oder Zonierungspolygone in frühen Entwurfsreviews, wenn volle Topologie-Datenbanken noch nicht angebunden sind. Wenn Sie später Polygonumfang, Polygonfläche, Großkreis-Geodäsie, Multipolygon-Löcher mit der Nonzero-Winding-Regel oder sphärische Containment auf dem WGS84-Ellipsoid brauchen, behandeln Sie diese als getrennte Suchabsichten und Landings statt diese planare Punkt-in-Polygon-Prüferseite zu überladen.