Was ist der beste Weg, um eine Höhenkarte zu finden, die aus Lat / Lon / Elevation-Paaren besteht, um alle Punkte oberhalb einer gegebenen Höhenniveau (oder besser gesagt, nur der konkaven 2D-Hülle) zu finden?
Ich arbeite an einer GIS-App, bei der ich ein Overlay über einer Karte rendern muss, um Regionen mit höherer Höhe anzuzeigen. es bestimmt dieses Polygon / Gebiet, das mich (vorerst) ratlos macht. Ich habe ein einfaches Array von Lat / Lon / Elevation-Paaren (genauer gesagt die GTOPO30 DEM-Dateien), aber ich bin frei, das in irgendeine Datenstruktur umzuwandeln, die Sie vorschlagen würden.
Wir wurden auf "Triangulated Irregular Networks" (TINs) hingewiesen, aber ich bin nicht sicher, wie diese Daten effizient abgefragt werden können, sobald wir die TIN erstellt haben. Ich wäre nicht überrascht, wenn unser Problem ähnlich gelöst werden könnte, wie man eine Konturkarte erzeugen würde, aber ich habe keine Erfahrung damit. Irgendwelche Vorschläge wären großartig.
Es klingt, als ob Sie versuchen, eine polygonale Darstellung der Grenze des Hochlandes zu erstellen.
Wenn Sie mit Rasterdaten arbeiten (in einem rechteckigen Raster), versuchen Sie dies.
Stellen Sie sich Ihr Gitter als eine Ansammlung von rechtwinkligen Dreiecken vor.
Nehmen wir an, Sie haben ein 3x3 Raster mit Punkten
Ihre Dreiecke sind:
Ihr Algorithmus hat diese Schritte.
Erstellen Sie eine Liste von Dreiecken, die über dem Elevationsschwellenwert liegen.
Nehmen Sie die Vereinigung dieser Dreiecke zu einem polygonalen Bereich.
Bestimmen Sie die Grenze des Polygons.
Glätten Sie gegebenenfalls die Polygongrenze, damit Ihre Ebene bei der Anzeige in Ordnung aussieht.
Wenn Sie versuchen, gut aussehende Konturlinien zu erzeugen, ist Schritt 4 sehr schwer zu korrigieren.
Schritt 1 ist der Schlüssel zu diesem Problem.
Wenn für jedes Dreieck alle drei Eckpunkte über dem Schwellenwert liegen, schließen Sie das gesamte Dreieck in Ihre Liste ein. Wenn alle unten sind, vergessen Sie das Dreieck. Wenn einige Scheitelpunkte über und andere darunter sind, teilen Sie Ihr Dreieck in drei, indem Sie neue Scheitelpunkte hinzufügen, die genau auf der Höhenlinie liegen (durch Interpolation der Höhe). Fügen Sie das eine oder zwei dieser neuen Dreiecke in Ihre Highland-Liste ein.
Für den Rest der Schritte benötigen Sie eine ordentliche 2D-Geometrie-Verarbeitungsbibliothek.
Wenn Ihre Punkte nicht auf einem regelmäßigen Gitter liegen, beginnen Sie mit dem Delaunay-Algorithmus (den Sie nachschlagen können), um Ihre Punkte in Dreiecke zu organisieren. Dann folge dem oben erwähnten Algorithmus. Warnung. Dies wird irgendwie skizzenhaft aussehen, wenn Sie nicht viele Punkte haben.
Wenn Sie die lat / lon / Höhendaten in einem Array (oder drei separaten Arrays) gespeichert haben, sollten Sie Array-Abfragetechniken verwenden können, um alle Punkte auszuwählen, an denen die Höhe über einem bestimmten Schwellenwert liegt. Zum Beispiel, in Python mit numpy können Sie tun:
Und die Variable indices enthält die Indizes aller Elemente von array größer als der Schwellenwert value . Ähnliche Befehle sind in verschiedenen anderen Sprachen verfügbar (zum Beispiel hat IDL den Befehl WHERE() , und ähnliche Dinge können in Matlab gemacht werden).
Sobald Sie diese Liste von Indizes erhalten haben, können Sie ein neues binäres Array erstellen, wobei jede Stelle, an der der Schwellenwert erfüllt war, auf 1 gesetzt ist:
%Vor% (Angenommen, Sie haben ein leeres Array mit der gleichen Größe wie Ihre ursprüngliche Breite / Länge / Höhe erstellt und es als binary_array bezeichnet.
Wenn Sie mit Raster-Daten arbeiten (was ich für diese Art von Arbeit empfehlen würde), werden Sie vielleicht feststellen, dass Sie dieses Array einfach auf einer Karte überlagern können und einen schönen Satz von Regionen sehen können. Wenn Sie jedoch die Bereiche über dem Höhenschwellenwert in Vektorpolygone konvertieren müssen, können Sie eine der vielen eingebauten GIS-Methoden verwenden, um Raster- & gt; Vektor zu konvertieren.
Ich würde eine geschachtelte C-Quadrate Anordnung verwenden, wobei jedes Quadrat eine vorberechnete maximale Bodenhöhe hat . Dies würde mir erlauben, auf einer hohen Ebene zu scannen, irgendwelche Quadrate zu verwerfen, wo die maximale Höhe nicht über der Suchhöhe liegt, und weiter in jene Quadrate zu bohren, wo Teile des Bodens über der Suchhöhe lagen.
Wenn Sie auf verschiedenen Ebenen der Suchhöhe arbeiten, können Sie die konvexe Hülle für die verschiedenen vordefinierten Ebenen für die kleinsten Quadrate, die Sie verwenden möchten, vorberechnen (oder für alle Quadrate.)
Ich bin mir nicht sicher, ob deine Lat / Lon / Alt-Punkte auf einem regulären Gitter liegen oder nicht, aber wenn nicht, könnten sie vielleicht interpoliert werden, um sogar 100 Fuß Höheninkremente und Uniform darzustellen lat / lon Divisionen (unter Berücksichtigung, dass dies keine einheitlichen Distanzteilungen ergibt). Aber wenn das funktionieren würde, warum nicht ein dreidimensionales Array vorberechnen, wobei die Indizes Höhe, Breite und Länge darstellen. Wenn das Flugzeug dann Daten über Punkte in oder über einer Höhe für ein bestimmtes Terrain benötigt, muss der Code nur einen kleinen Teil der Daten in diesem Array auslesen, der indiziert ist, um angrenzende "Voxel" zusammenhängend zu machen Indexierungsschema.
Natürlich müssen die Längenzuwächse nicht einheitlich sein: Wenn gleichmäßige Abstände benötigt werden, würde das gleiche Schema funktionieren, aber die Indizes für den Längengrad würden auf eine nicht gleichmäßig beabstandete Menge von Längen hinweisen.
Ich glaube nicht, dass es eine schnellere Möglichkeit geben würde, diese Daten zu durchsuchen.
Aus Ihrer Frage geht nicht klar hervor, ob die Menge der Punkte statisch ist und Sie oft herausfinden müssen, welche Punkte über einer bestimmten Höhe liegen oder ob Sie die Abfrage nur einmal durchführen müssen.
Die einfachste Lösung besteht darin, die Punkte in einem Array zu speichern, sortiert nach Höhe. Das Finden aller Punkte in einem bestimmten Höhenbereich ist nur eine binäre Suche, und Sie müssen nur einmal sortieren.
Wenn Sie die Abfrage nur einmal ausführen müssen, führen Sie einfach eine lineare Suche durch das Array in der Reihenfolge durch, in der Sie sie erhalten haben. Der Aufbau einer schickeren Datenstruktur aus dem Array wird sowieso O (n) sein, so dass Sie keine besseren Ergebnisse erzielen werden, wenn Sie Dinge komplizieren.
Wenn Sie andere Anforderungen haben, wie beispielsweise, dass Sie alle Punkte in einem Rechteck, das der Benutzer gerade anzeigt, effizient auflisten müssen oder dass Punkte zur Laufzeit hinzugefügt oder gelöscht werden können, dann ist möglicherweise eine andere Datenstruktur besser. Vermutlich eine Art Baum oder Gitter.
Wenn Sie nur Rendering durchführen möchten, können Sie dies sehr effizient mit Grafikhardware durchführen, und es ist nicht notwendig, eine ausgefallene Datenstruktur zu verwenden. Sie können einfach Dreiecke an die GPU senden und Fragmente über oder abtöten lassen unterhalb einer bestimmten Höhe.
Tags und Links c# map gis terrain cartography