Datensatzerstellung für die spätere Integration in MySQL & Google Maps API für eine Website? (ein Punkt-in-Polygon, Kollisionssatz, usw.)
Ich habe es in den letzten Monaten geschafft, PHP, PDO & amp; SQL, und haben eine grundlegende dynamische Website mit Benutzerregistrierung / E-Mail-Aktivierung / und Log-in-Logout-Funktionalität erstellt, die den Best Practices von PHP / SQL folgt. Jetzt bin ich bei der nächsten Aufgabe fest ...
Ich habe einen riesigen Datensatz von Quadraten / Polygonen (3 Millionen +) erstellt, jede 1 Minute Breite & amp; Länge in der Größe, in einem PHP-Array mit einem einzigen Satz von Koordinaten (die obere linke Ecke) gespeichert. Um eine quadratische Form zu extrapolieren, addiere ich einfach 0,016 Grad (~ 1 Minute) in jede Richtung und erzeuge die anderen 3 Koordinaten.
Ich muss nun überprüfen, dass jedes Polygon in diesem Array über mindestens einem Teil des Landes in den Vereinigten Staaten ist .... dh wenn ich eine grafische Ausgabe meines fertigen Datensatzes erstellen und einen Blick auf die San Fransisco Küste, sie würden etwas wie dieses sehen.
Es ähnelt dem Punkt-in-Polygon-Problem, es handelt sich jedoch um ein anderes Polygon anstelle eines Punktes, das andere Polygon ist eine Ländergrenze, und ich betrachte nicht nur Schnittpunkte. Ich möchte überprüfen, ob:
- Ein Polygon / Quadrat schneidet das Polygon. (Denken Sie Küstenlinie / Grenze).
- Ein Polygon / Quadrat befindet sich innerhalb des Polygons. (Denken Sie kontinental U.S.).
- Ein Polygon / Quadrat enthält einen Teil des Polygons. (Denke kleine Insel).
Dies ist mit meinem grob gezeichneten Bild illustriert:
Wenn es eine dieser drei Bedingungen erfüllt, möchte ich das Quadrat behalten. Wenn es nicht mit dem großen Polygon zusammenwirkt (d. H. Es ist über Wasser), verwerfen Sie es.
Ich dachte, das große Polygon wäre ein Shapefile der USA, oder eine KML-Datei, aus der ich die Koordinaten entfernen könnte, um daraus ein sehr komplexes Polygon zu erzeugen.
Dann dachte ich, ich würde diese passenden Quadrate und Quadrat-IDs über an eine CSV-Datei zur Integration in eine MySQL-Tabelle übergeben, die eine Menge von Koordinaten jedes Quadrats enthält (tatsächlich bin ich nicht einmal über die Best Practices für die Handhabung von Tabellen dieser Größe in MySQL Bescheid, aber ich werde dazu kommen, wenn es nötig ist). Das letztendliche Ziel wäre dann, eine Karte mit Google Maps API über Javascript zu entwickeln, um diese Quadrate über einer Karte auf der Website anzuzeigen, die ich kodiere (offensichtlich nur Quadrate innerhalb des Aussichtspunkts, um sicherzustellen, dass ich meine db nicht zu Tode besteuere) ). Ich bin mir ziemlich sicher, dass ich diese Informationen zuerst auch über PHP weitergeben muss. Aber all das scheint relativ einfach zu sein, verglichen mit der eigentlichen Erstellung des Datensatzes.
Dies ist offensichtlich etwas, das nicht von Hand gemacht werden kann, also muss es automatisiert werden. Ich kenne ein bisschen Python, also würde das helfen? Irgendwelche anderen Tipps, wo man anfangen soll? Jemand, der bereit ist, einen Teil des Codes für mich zu schreiben?
2 Antworten
Hier ist eine Lösung, die effizient und so einfach wie möglich zu implementieren ist. Beachten Sie, dass ich nicht einfach, aber so einfach wie möglich sage. Dies ist ein schwieriges Problem, wie sich herausstellt.
1) Erhalte US-Polygondaten mit Shapefiles oder KFL, die eine Menge von Polygonformen (Landmassen) ergeben, die jeweils durch eine Liste von Scheitelpunkten definiert sind.
2) Erstellen Sie eine Reihe von AABB-Rechtecken für die Vereinigten Staaten: eine für Alaska und jede Alaska-Insel, eine für jede Hawaii-Insel, eine für die kontinentalen Vereinigten Staaten und eine für jede kleine Insel die Küste der kontinentalen USA (z. B. Bald Head Island in NC, Catalina vor der Küste von Kalifornien). Jeder Begrenzungsrahmen ist als ein Rechteck mit den Ecken definiert, die die minimale und maximale Breite und Länge für die Form darstellen. Ich vermute, dass es ein paar hundert davon geben wird. Zum Beispiel, für Hawaiis große Insel, verläuft die Breite 18 ° 55'N bis 28 ° 27'N, und die Länge verläuft 154 ° 48'W bis 178 ° 22'W. Die meisten Ihrer globalen lat / long Paare werden bei diesem Schritt rausgeworfen, da sie sich nicht in einem dieser wenigen hundert Bounding Boxes befinden. Zum Beispiel, Ihre Bounding Box bei 10 ° 20'W, 30 ° 40'N (ein Ort im Atlantischen Ozean in der Nähe von Las Palmas, Afrika) überlappt Hawaii nicht, weil 10 ° 20'W weniger als 154 ° 48'W ist . Dieses Bit wäre in Python einfach zu programmieren.
3) Wenn das lat / long-Paar eines der mehreren hundert AABB-Rechtecke überlappt, müssen Sie es dann mit dem einzelnen Polygon innerhalb des AABB-Rechtecks testen. Es wird dringend empfohlen, den Minkowski-Unterschied (MD) zu verwenden. Bitte überprüfen Sie diese Website zuerst gründlich:
Sehen Sie sich insbesondere die Demo "Poly versus Poly" auf halber Seite an und spielen Sie ein wenig mit ihr. Wenn Sie das tun, werden Sie sehen, dass, wenn Sie die MD der 2 Formen verwenden, wenn diese MD den Ursprung enthält, die beiden Formen sich überschneiden. Sie müssen also nur den Minkowski-Unterschied der 2 Polygone nehmen, was wiederum zu einem neuen Polygon (B - A, in der Demo) führt und dann sehen, ob das Polygon den Ursprung enthält.
4) Es gibt viele Online-Arbeiten über Algorithmen zur Implementierung von MD, aber ich weiß nicht, ob Sie die Möglichkeit haben werden, das Papier zu lesen und es in Code zu übersetzen. Da es schwierige Vektormathematik ist, die MD der zwei Polygone zu nehmen (das lat / long Rechteck, das du testest, und das Polygon, das in der Boundingbox enthalten ist, die das lat / long Rechteck überlappt), hast du uns deine Erfahrung erzählt Level ist noch nicht hoch, ich würde vorschlagen, eine Bibliothek zu verwenden, die bereits MD implementiert, oder noch besser, Kollisionserkennung implementiert.
Zum Beispiel:
Hier sehen Sie den relevanten Pseudocode, den Sie in Python portieren könnten:
%Vor%Wenn Sie dies nicht selbst portieren können, könnten Sie sich vielleicht an einen der Autoren der beiden Links wenden, die ich hier aufgenommen habe - beide haben den MD-Algorithmus in Flash implementiert, vielleicht könnten Sie den Quellcode lizenzieren.
5) Angenommen, Sie haben die Kollisionserkennung übernommen, können Sie einfach in der Datenbank einen booleschen Wert speichern, ob das lat / long-Paar Teil der Vereinigten Staaten ist. Sobald dies erledigt ist, habe ich keine Zweifel mehr, dass Sie mit Ihrem Google Maps-Artikel nach Belieben arbeiten können.
Also, um es zusammenzufassen, das einzige schwierige Stück hier ist, entweder 1) den Kollisionserkennungs-GJK-Algorithmus zu implementieren, oder alternativ 2) schreibe einen Algorithmus, der zuerst die Minkowski-Differenz zwischen Ihrem lat / langen Paar und dem Land berechnet Polygon in Ihrem AABB enthalten und dann sehen Sie, ob das MD-Polygon den Ursprung enthält. Wenn Sie diesen Ansatz verwenden, würde Ray Casting (typische Punkt-in-einem-Polygon-Lösung) mit dem zweiten Teil den Trick machen.
Ich hoffe, das gibt Ihnen einen Start in die richtige Richtung!
Ich denke, diese andere Frage beantwortet einen guten Teil dessen, was Sie versuchen zu tun
Wie ermittle ich, ob sich zwei konvexe Polygone schneiden?
Der andere Teil besteht darin, dass wenn Sie eine Datenbank verwenden, ich alle Polygone in der Nähe Ihres Ansichtspunkts aus beiden Mengen laden würde (die Menge der Kartenpolygone und die Menge anderer generierter Polygone) und dann den obigen Algorithmus ausführen Auf dieser kleineren Menge von Polygonen können Sie eine Liste aller Polygone in Ihrer Menge erstellen, die auf der Karte überlagert werden sollen.
Tags und Links google-maps php mysql dataset point-in-polygon