Zeichnen einer topographischen Karte

Question

Ich habe für 2-dimensionale kontinuierliche Daten auf einem Visualisierungsprojekt gearbeitet. Es ist die Art von Sache, die Sie Höhendaten oder Temperaturmuster zu studieren auf einer 2D-Karte verwenden könnten. In seinem Kern ist es wirklich eine Art und Weise der Abflachung 3-Dimensionen in zwei Dimensionen-plus-Farbe. In meinem speziellen Bereich der Studie, arbeite ich nicht wirklich mit geographischen Höhendaten, aber es ist eine gute Metapher, also wird mich in diesem Beitrag dabei bleiben.

Wie auch immer, an diesem Punkt, ich habe eine „kontinuierliche Farb“ Renderer, ich bin sehr zufrieden mit:

Der Gradient wird das Standard-Farbrad, wo rote Pixel-Koordinaten mit hohen Werten zeigen, und violette Pixel angeben niedrige Werte.

Die zugrundeliegende Datenstruktur verwendet einige sehr klug (wenn ich so selbst sage) Interpolation Algorithmen beliebig tief zu ermöglichen, in die Details der Karte zoomen.

An dieser Stelle mag ich einige topographischen Höhenlinien zeichnen (mit quadratischen Bezier-Kurven), aber ich habe nicht in der Lage gewesen zu finden, diese Kurven jede gute Literatur beschreibt effiziente Algorithmen zu finden.

Um Ihnen eine Idee für, was ich denke, hier ist ein Arme-Leute-Implementierung (wo der Renderer nur einen schwarzen RGB-Wert verwendet, wenn es um ein Pixel trifft, die eine Konturlinie schneidet):

Es gibt mehrere Probleme mit diesem Ansatz, aber:

• Bereiche des Graphen mit einem steileren Neigung Ergebnis in dünner (und oft gebrochen) Topo Linien. Idealerweise sollten alle Topo Linien kontinuierlich sein.

• Bereiche des Graphen mit einem flacheren Steigung Ergebnis in breiteren Linien Topo (und oft ganze Regionen von Schwärze, insbesondere am Außenumfang der Renderingregion).

Also habe ich mich auf einen Vektor-Zeichen Ansatz für diese schöne, perfekte 1-Pixel-dicken Kurven zu bekommen. Die Grundstruktur des Algorithmus werden diese Schritte umfassen müssen:

1. bei jeder diskreten Höhen wo ich möchte ein Topo Linie zeichnen, einen Satz von Koordinaten finden, wo die Erhebung an dieser Koordinate extrem nahe ist (da ein willkürlicher epsilon-Wert) auf die gewünschte Höhe.

2. Vermeiden redundante Punkte. Wenn zum Beispiel drei Punkte in einer perfekt geraden Linie sind, dann ist der Mittelpunkt überflüssig wird, da es ohne Änderung der Form der Kurve beseitigt werden. Ebenso mit Bezier-Kurven ist es oft möglich cetain Ankerpunkte zu beseitigen, indem die Position der benachbarten Kontrollpunkte eingestellt werden.

3. Montieren der verbleibenden Punkte in einer Folge, derart, dass jedes Segment zwischen zwei Punkten annähert eine Erhebung neutralen Trajektorie, und derart, dass keine zwei Liniensegmente je kreuzen. Jede Punkt-Sequenz muss entweder ein geschlossenes Polygon erstellen, oder muß die Begrenzungsrahmen der Renderingregion schneiden.

4. Für jeden Scheitelpunkt, der ein Paar von Kontrollpunkten finden, so dass die sich ergebende Kurve, die einen minimalen Fehler aufweist, in Bezug auf die redundante Punkte in Schritt # 2 eliminiert.

5. Stellen Sie sicher, dass alle Merkmale der Topographie sichtbar an der aktuellen Rendering-Skala werden durch entsprechende Topo Linien dargestellt. Wenn zum Beispiel enthalten die Daten, die eine Spitze mit großer Höhe, aber mit extrem kleinem Durchmesser, sollten die Topo Linien noch gezogen werden. Vertikale Merkmale sollten nur ignoriert werden, wenn ihre Funktion Durchmesser kleiner ist als die gesamte Rendering Körnigkeit des Bildes.

Aber auch unter diesen Randbedingungen, kann ich immer noch der Meinung von mehreren verschiedenen Heuristiken zum Auffinden der Zeilen:

• Finden Sie den Höhepunkt in der Rendering-Begrenzungs-Box. Von diesem Höhepunkt, fahren bergab auf mehrere verschiedene Bahnen. Jedesmal, wenn die Traversierung Linie crossest einen Höhenschwelle, fügen diesen Punkt zu einer Höhe spezifischer bucket. Wenn der Traversierungspfads ein lokales Minimum erreicht hat, den Kurs ändern und bergauf fahren.

• Durchführen einer hochauflösenden Traversierung entlang der rechteckigen Bounding-Box des Renderingregion. An jeder Elevationsschwelle (und bei Wendepunkten, wo auch immer die Neigungsrichtung umkehrt), fügt diese Punkte auf eine Höhe spezifische Eimer. Nach der Grenzüberquerung Finishing, beginnen nach innen von den Randpunkten in den Eimer zu verfolgen.

• Scannen des gesamten Wiedergabebereich, eine Höhenmessung an einem regelmäßigen Intervall sparse nehmen. Für jede Messung nutzt die Nähe zu einer Höhe Schwelle als ein Mechanismus, um zu entscheiden, ob eine interpolierte Messung seiner Nachbarn zu nehmen. Mit dieser Technik würde eine bessere Garantien für die Berichterstattung über die gesamte Rendering-Region zur Verfügung stellen, aber es wäre schwierig, die resultierenden Punkte in einer sinnvollen Reihenfolge für den Bau von Wegen zu montieren.

Also, das sind einige meiner Gedanken ...

Vor dem Tauchen tief in eine Implementierung, wollte ich sehen, ob jemand auf Stackoverflow Erfahrung mit dieser Art von Problem hat und Zeiger für eine genaue und effiziente Umsetzung bieten könnte.

Edit:

Ich bin besonders interessiert an dem „Gradient“ Vorschlag von ellisbben. Und meine Kerndatenstruktur (ein Teil der Optimierung der Interpolation Verknüpfungen ignoriert wird) kann als die Summe eines Satzes von 2D-Gauß-Funktionen dargestellt werden, die total differenzierbar ist.

Ich glaube, ich werde eine Datenstruktur benötigen eine dreidimensionale Neigung darzustellen, und eine Funktion für an beliebigem Punkt, dass die Steigung Vektor für die Berechnung. Aus der Spitze von meinem Kopf, ich weiß nicht, wie das zu tun (obwohl es, wie es scheint, sollte einfach sein), aber wenn Sie einen Link zu erklären, die Mathematik, würde ich sehr dankbar!

UPDATE:

Dank der hervorragenden Beiträge von ellisbben und Azim, kann ich nun die Konturwinkel für jeden beliebigen Punkt auf dem Gebiet berechnen. die wirklichen Topo Linien Zeichnung folgt in Kürze!

Hier sind aktualisiert Renderings, mit und ohne Ghetto rasterbasierte Topo-Renderer, die ich verwendet habe. Jedes Bild enthält tausend Stichprobenpunkte, durch rote Punkte dargestellt. Die Winkel-of-Kontur an diesem Punkt wird durch eine weiße Linie dargestellt. In bestimmten Fällen konnte keine Neigung an dem gegebenen Punkt gemessen werden (basierend auf der Granularität der Interpolation), so tritt der rote Punkt ohne eine entsprechende Winkel-of-Umrißlinie.

Genießen Sie!

(Hinweis: Verwenden Sie diese Renderings eine andere Oberflächentopographie als die bisherigen Renderings - da ich die Datenstrukturen auf jeder Iteration zufällig generiert, während ich Prototyping bin - aber die Kern-Rendering-Methode ist das gleiche, so ich bin sicher, Sie bekommen die Idee.)

Hier ist ein Spaß Tatsache: über auf der rechten Handseite dieser Renderings, werden Sie eine Reihe von seltsamen Konturlinien bei perfekten horizontalen und vertikalen Winkel sehen. Dies sind Artefakte des Interpolations-Prozesses, der ein Gitter von Interpolatoren verwendet die Anzahl von Berechnungen zu verringern (um etwa 500%) erforderlich, um die Kern-Rendering-Operationen durchzuführen. All diese seltsamen Konturlinien treten auf der Grenze zwischen zwei Interpolator Gitterzellen.

Glücklicherweise haben diese Artefakte nicht wirklich wichtig sind. Obwohl die Artefakte nachweisbar während Steigungsberechnung sind, wird der endgültige Renderer sie nicht bemerkt, da es an einer anderen Bittiefe arbeitet.

---

UPDATE WIEDER:

Aaaaaaaand, als eine letzte Nachsicht, bevor ich schlafen gehen, hier ist ein anderes Paar von Renderings, ein in der alten Schule „continuous Farbe“ -Stil, und eines mit 20.000 Gradienten Proben. In diesem Satz von Renderings, habe ich den roten Punkt für Punkt-Proben eliminiert, da es unnötig unübersichtlich das Bild.

Ersind, können Sie wirklich diese Interpolationsartefakte sehen, die ich vorher erwähnt, dank der Gitterstruktur der Interpolators Sammlung. Ich möchte betonen, dass diese Artefakte auf die endgültige Kontur Rendering völlig unsichtbar sein wird (da der Unterschied in der Größe zwischen zwei beliebigen benachbarten Interpolator Zellen kleiner als die Bit-Tiefe des gerenderten Bildes).

Guten Appetit !!

Answer 1

Die Gradienten ein mathematischer Operator ist, dass Sie helfen können.

Wenn Sie Ihre Interpolation in eine differenzierbare Funktion drehen kann, wird der Gradient der Höhe immer in die Richtung des steilsten Aufstieg. Alle Kurven gleicher Höhe senkrecht zum Gradienten der Höhe an diesem Punkt bewertet.

Ihre Idee vom höchsten Punkt zum Starten ist sinnvoll, aber vielleicht Features vermissen, wenn es mehr als ein lokales Maximum ist.

Ich würde vorschlagen,

1. Pick Höhe Werte, bei denen Sie Linien zeichnen werden
2. eine Reihe von Punkten auf einem feinen, regelmäßigem Abstand Raster erstellen, dann jeden Punkt in kleinen Schritten in der Gradientenrichtung zu Fuß in Richtung der nächsten Höhe, in der Sie eine Linie zeichnen möchten
3. erstellen Kurven, die durch jeden Punkt senkrecht zum Gradienten Schritt; überschüssige Punkte beseitigen, indem Sie einen Punkt zu töten, wenn eine andere Kurve zu nahe kommt, aber es-- wie Figuren zerstören das Zentrum der Sanduhr zu vermeiden, müssen Sie möglicherweise den Winkel zwischen dem orientierten Vektor senkrecht zum Gradienten für beide der Punkte überprüfen. (Wenn ich orientierte sage, meine ich sicher, dass der Winkel zwischen dem Gradienten und der Senkrechten Wert, den Sie berechnen, ist immer um 90 Grad in die gleiche Richtung.)

Answer 2

Alternativ gibt es die Quadrate marschieren Algorithmus, der für Ihr Problem angemessen erscheint, obwohl Sie sollte die Ergebnisse glätten, wenn Sie ein grobes Raster verwendet werden.

Die Topo Kurven Sie zeichnen möchten sind Isoflächen eines skalaren Feldes mehr als 2 Dimensionen. Für Isoflächen in 3 Dimensionen gibt es die Marching Cubes rel="nofollow Algorithmus.

Answer 3

Als Antwort auf Ihren Kommentar zu @erickson und den Punkt über die Berechnung des Gradienten Ihrer Funktion zu beantworten. Anstatt die Derivate des 300 Zeitfunktion Berechnen Sie könnten eine numerische Differenzierung wie folgt tun.

ein Punkt gegeben [x, y] in Ihrem Bild, das Sie die Steigung (Richtung der steilsten anständigen) berechnen könnten

g={  ( f(x+dx,y)-f(x-dx,y) )/(2*dx), 
  {  ( f(x,y+dy)-f(x,y-dy) )/(2*dy) 

wobei dx und dy könnte der Abstand im Raster sein. Die Konturlinie wird senkrecht zum Gradienten laufen. Also, um die Konturrichtung zu bekommen, c können wir multiplizieren g = [v, w] durch Matrix A = [0 -1, 1 0] geben

c = [-w,v]

Answer 4

Ich habe so etwas wie dies selbst wollte, aber nicht eine Vektor-basierte Lösung.

gefunden

Eine rasterbasierte Lösung ist nicht so schlecht, obwohl, vor allem, wenn Ihre Daten rasterbasierte. Wenn Ihre Daten zu vektorbasierten (in anderen Worten, Sie haben ein 3D-Modell Ihrer Oberfläche), sollten Sie in der Lage sein, einige echte Mathematik zu tun, um die Schnittkurven mit horizontalen Ebenen in unterschiedlichen Höhen zu finden.

Für einen rasterbasierten Ansatz, sehe ich an jedem Paar von benachbarten Pixeln. Wenn man über eine Konturebene ist, und man ist unten, offensichtlich eine Konturlinie verläuft zwischen ihnen. Der Trick, den ich verwenden, um anti-alias die Konturlinie ist die Konturlinie Farbe in beide Pixel, proportional zu ihrer Nähe zu der idealisierten Konturlinie zu mischen.

Vielleicht wird dazu beitragen, einige Beispiele. . Nehmen wir an, daß das aktuelle Pixel auf einem „Elevation“ von 12 ft, ein Nachbar in einer Höhe von 8 ft ist, und Konturlinien werden alle 10 ft Dann gibt es eine Konturlinie auf halbem Weg zwischen; malt das aktuelle Pixel mit dem Konturlinienfarbe bei 50% Opazität. Ein weiteres Pixel ist 11 Meter und hat einen Nachbarn zu 6 Metern. Farbe der aktuellen Pixel bei 80% Opazität.

alpha = (contour - neighbor) / (current - neighbor)

Leider habe ich nicht den Code handlich, und es könnte ein bisschen mehr zu bieten haben (ich vage an diagonalen Nachbarn erinnern suchen, und das Einstellen von sqrt(2) / 2). Ich hoffe, das genug, um Ihnen den Kern zu geben.

Answer 5

Es fiel mir ein, dass das, was Sie versuchen zu tun wäre ziemlich einfach, in MATLAB zu tun, um die Kontur-Funktion. Dinge zu tun, wie die Herstellung von geringer Dichte Annäherungen an Ihre Konturen können wahrscheinlich mit einiger ziemlich einfachen Nachbearbeitung der Konturen erfolgen.

Zum Glück GNU Octave, ein MATLAB-Klon, hat Implementierungen der verschiedenen Kontur Plotfunktionen. Sie könnten für einen Algorithmus zu diesem Code suchen und Implementierung, die mit ziemlicher Sicherheit mathematisch-Sound ist. Oder könnten Sie nur in der Lage sein, um die Verarbeitung zu Octave abzuladen. Schauen Sie sich die Seite auf mit anderen Sprachen Schnittstelle zu sehen, ob das wäre einfacher.

Disclosure: Ich habe Octave nicht verwendet sehr viel, und ich habe nicht wirklich getestet Kontur Plotten ist. Aber aus meiner Erfahrung mit MATLAB, kann ich sagen, dass es Sie gibt fast alles, was man in nur wenigen Zeilen Code sind gefragt, vorausgesetzt, Sie erhalten Ihre Daten in MATLAB.

Auch Gratulation zu machen ein sehr VanGough-esque Slopefield Grundstück.

Answer 6

Ich überprüfe Orte immer wie http://mathworld.wolfram.com , bevor sie auf eigene Faust zu tief gehen :)

Vielleicht rel="nofollow ihre Kurven Abschnitt helfen würde? Oder vielleicht der Eintrag auf Karten .

Answer 7

vergleichen, was Sie mit einer realen Topo-Karte verdient gemacht haben - sie mir gleich aussehen! Ich würde nichts ändern ...

Answer 8

Schreiben Sie die Daten aus als HGT Datei (sehr einfach digitale Höhendatenformat verwendet USGS) und verwenden die freie und Open-Source gdal_contour Werkzeug zu schaffen, Konturen. Das funktioniert sehr gut für terrestrische Karten, wobei die Einschränkung, dass die Datenpunkte werden 16-Bit-Zahlen mit Vorzeichen, die sehr gut den irdischen Bereich von Höhen in Metern passen, kann aber für Ihre Daten nicht ausreicht, die ich davon ausgehen, keine sein Karte der tatsächlichen Gelände -. Sie können sie aber Geländekarten erwähnen tun

Answer 9

Ich empfehle den CONREC Ansatz:

• Erstellen Sie eine leere Zeile Segmentliste
• Teilen Sie Ihre Daten in regelmäßigen Gitterquadrate
• für jeden Gitterplatz teilen das Quadrat in 4 -Komponente Dreiecke:
  • Für jedes Dreieck, behandeln die Fälle (a bis j):
    • Wenn ein Liniensegment kreuzt einer der Fälle:
      • Berechnen seine Endpunkte
      • Speichern Sie das Liniensegment in der Liste
• Zeichnen jedes Liniensegment in der Liniensegment-Liste

Wenn die Linien zu gezackt sind, verwenden Sie einen kleineren Raster. Wenn die Linien glatt genug sind und der Algorithmus zu lange dauert, verwenden Sie ein größeres Netz.