Koordinate in Gebiet abfragen

[Quetschi]

Ich bräucht auch grad mal wieder einen Denkansatz.

Ich habe:
Tabelle 'Placemarks':
ID, Lat, Lon

Tabelle 'Areas':
ID, PolygonData

Das heißt... ich habe die Tabellen noch nicht auf einem Server, sondern erst in meinem Kopf. Das Feld PolygonData wäre einfach ein Textfeld, das mit 'Lat,Lon Lat,Lon Lat,Lon ....' gefüllt wäre. Alternativ könnte hierfür auch eine weitere Tabelle stehen, in dem jeder LatLon-Wert eines Polygons in einem eigenem Datensatz hinterlegt wäre - das würde dann auch noch zusätzlich eine Sortierspalte erforderlich machen. Wie die Polygone gespeichert werden hat mit meinem eigentlichen Anliegen aber erstmal nichts zu tun - glaube ich zumindest...

In PHP habe ich mir nun eine Funktion geschrieben, welche feststellt, ob eine mit Lat und Lon definierte Koordinate sich innerhalb eines Polygons (Array) befindet. Diese Funktion habe ich nicht nur in meinem Kopf, sondern die ist bereits "auf Papier" und funktioniert einwandfrei.

Nun ist es aber nicht möglich in SQL direkt abzufragen, ob sich eine Koordinate innerhalb eines Polygons befindet. Wenn ich also wissen will welche Datensätze aus 'Placemarks' sich innerhalb eines bestimmten Polygons aus "Areas" befinden, muss ich alle Datensätze aus 'Placemarks' holen und in PHP dann checken ob sich die Placemark innerhalb oder ausserhalb des Polygons befindet. Wie es euch dabei geht weiß ich jetzt nicht, aber mein Bauchgefühl sagt mir schon, dass das nicht gerade der Königsweg sein kann.

Der sinnvollste Weg, der mir im Augenblick einfällt, sieht so aus, dass ich eine Tabelle 'PlacemarkInArea' anlege:
ID, placemark_ID, area_id, is_in
Diese würde dann per Cronjob in regelmässigen Abständen auf fehlende Kombinationen aus placemark_ID und area_ID geprüft werden und das Prüfungsergebnis aus der PHP-Funktion würde dann dort eingetragen werden.

Wie seht ihr das? Alternativen?

PS:
Der Burner schlechthin wäre, diese Funktion direkt in mySql zu implementieren - aber das ist für mich eine Nummer zu hoch.

[AmicaNoctis]

Respekt. Welchen Algorithmus hast du benutzt? Ray casting? Dafür musst du doch lineare Gleichungssysteme lösen. Hab das auch mal gemacht und fand das nicht besonders lustig, wegen der Float-Ungenauigkeit.

Edit: Ich merk grad, dass das Blödsinn ist. Ich hatte im 3D-Raum Schnittpunkte errechnen müssen, aber in der Ebene ist das ja viel einfacher und ohne LGS machbar.

[Quetschi]

Das ist schon ne Weile her, aber weil ich grad wieder an der Thematik dran bin kam ich auf die Frage hier - aber du glaubst ja jetzt nicht ernsthaft, ich hätt mir den Algorhitmus selbst ausbaldowert?!

Google war mein Freund - was man da findet dann noch auf PHP umzumünzen stellt mal wirklich keinen vor besondere Herausforderungen.

Ich hab allerdings schon auch versucht zu verstehen was der Algo macht - er zählt mit, ob das Polygon den gesuchten Punkt umkreist in dem er mitzählt, wie oft eine Polygonkante eine Linie, die von dem Punkt aus weggeht von unten nach oben und von oben nach unten schneidet. Kommt was anderes als 0 raus, liegt der Punkt drin.

Ray Casting? Keine Ahnung - berechnest du da den Winkel einer Linie von den Eckpunkten des Polygons zum zu prüfenden Punkt?

[AmicaNoctis]

Nein, ray casting ist genau das, was du machst, auch wenn du es etwas vage beschreibst. Ich denke, das lässt sich ganz gut als Stored Function in MySQL umsetzen.

[Quetschi]

stored functions - ich wusste von stored procedures und dass mir die in dem Fall nicht weiterhelfen. Ich müsst meine Kenntnisse über mySql mal langsam über den Stand von vor 9 oder 10 Jahren hinausbringen

Ich dachte ich müsste direkt an den Quellcode von mySql ran um das reinzukriegen - aber so kann ich mir das mal angucken.

Vielen Dank!

[AmicaNoctis]

Ein Beispiel, wie sowas aussieht (wenn auch ein völlig anderes Thema) findest du hier.

[onemorenerd]

MySQL :: MySQL 5.0 Reference Manual :: 11.12.5.6 Functions That Test Spatial Relationships Between Geometries

[Quetschi]

@onemorenerd
Danke - wusste auch nicht, das mySql inzwischen dafür eigene Datentypen bereithält. Hab mich damit mal kurz befasst.

Dumm ist:
In kml-Dateien werden Polygone in der Form abgelegt:
13.35323242,48.523232,0 13.534232453,48.13353323,0 13.12412312,48.9897989,0

Der mySql-geometrie-Datentyp erwartet die Daten dagegen so:
13.35323242 48.523232, 13.534232453 48.13353323, 13.12412312 48.9897989, 13.35323242 48.523232

Ist zwar nicht weiter tragisch - man muss halt wieder mal hin- und herkonvertieren.

Hab jetzt mal ein wenig damit rumgespielt, eine Tabelle angelegt, Polygone drin gespeichert und dann nach Punkten darin gesucht - schaut gut aus


EDIT:
Also für GeoInfo ist das echt super und easy - einfach alle Infos (Gebiete, Punkte, Routen) in eine Spalte mit dem Datentyp 'geometrie' einpflegen, die Tabelle mit sich selbst joinen und schon kann man sich beliebig ineinander verschachtelte Gebiete, Punkte, Routen usw. rausziehen - der Tipp war mal echt Gold Wert

[Quetschi]

Hab jetzt mal ein wenig damit rumgespielt, eine Tabelle angelegt, Polygone drin gespeichert und dann nach Punkten darin gesucht - schaut gut aus


EDIT:
Also für GeoInfo ist das echt super und easy - einfach alle Infos (Gebiete, Punkte, Routen) in eine Spalte mit dem Datentyp 'geometrie' einpflegen, die Tabelle mit sich selbst joinen man kann sich beliebig ineinander verschachtelte Gebiete, Punkte, Routen usw. rausziehen - der Tipp war mal echt Gold Wert

Ich nehme alles zurück und behaupte das Gegenteil!

... naja, ganz so schlimm ist es nicht aber etwas den ich erhalte inzwischen Resultate, die so nicht stimmen können. Ein genauerer Blick ins Manual verrät dann auch warum das so kommt:

Die Funktion within scheint nur zu prüfen ob der gesuchte Punkt innerhalb eines Rechtecks (MBR) liegt, das durch die jeweiligen äußeren Eckpunkte des Polygons, in welchem gesucht wird, definiert wird.

Nun kann ich aber so schonmal mehr oder weniger auf die Datensätze eingrenzen, auf die das zutrifft und den Rest dann z.B. noch gegen meine PHP-Funktion checken.

Für heute hab ich aber keine Zeit mehr - war aber trotzdem ein guter Tipp!

[AmicaNoctis]

Und contains statt within?

[Quetschi]

Und contains statt within?

Selbiges. Verstehe den Unterschied eh nicht, kommt immer das Gleiche raus. Nur die Parameter werden in umgekehrter Reihenfolge übergeben.

EDIT:
In einem Link in den User-Notes wird beschrieben, dass within wohl ab 5.1 korrekt, also nicht nur MBR-basiert arbeitet. Hab leider momentan nur 5.0.77. Muss mal unsere Server durchforsten ob irgendwo >= 5.1 drauf ist.

[Quetschi]

Ich hab mir jetzt daheim zum Testen mal den mySql-snapshot von GIS Functions - MySQL Forge Wiki daheim aufgespielt und siehe da

Bin gespannt, wann das in die offizielle reinkommt...

Den Unterschied zwischen contains und within hab ich jetzt auch begriffen - die Namen sagen eigentlich eh alles. Dadurch, dass die Funktionen in den aktuellen offiziellen MySql-Versionen aber noch MBR-basiert, sind fielen die Probeläufe bei mir leider genau so aus, dass sich keine Unterschiede ergaben.