Heightmap Erzeugungsalgorithmus?

https://stackoverflow.com/questions/557496

05-09-2019
|

Frage

Ich war auf der Suche rund um das Internet und kann nicht einen perfekten Algorithmus für dieses spezielle Problem finden:

Unsere Kunden eine Reihe von Punkten und Gewichtsdaten zusammen mit jedem Punkt wie dieses Bild gezeigt werden:

gewichtete Punkte http://chakrit.net/files/stackoverflow/so_heightmap_points.png

Davon haben wir ein GIS-Programm, das eine „heightmap“ oder eine Art von Geländedaten von diesen Punkten und deren Gewichtswerte erzeugen können, aber als wir in der Nähe haben tausend Datenpunkte, und dass diese im Laufe der Zeit ändern, werden wir möchte unsere eigenen Werkzeuge erstellen, um diese zu height~~POS=TRUNC automatisch generieren.

Bisher habe ich versucht, das Gewicht für jedes Pixel von seiner Entfernung zum nächsten Datenpunkt mit Sqrt((x1 - x2) ^ 2 + (y1 - y2) ^ 2) und Anwendung von Gewicht und Entfernung Faktor auf den Datenpunktes der Farbe zur Berechnung der resultierenden Gradienten Farbe für den jeweiligen Pixel zu erzeugen:

heightmap führen http://chakrit.net/files/stackoverflow/so_heightmap_result.png

Sie sehen, dass es immer noch Probleme mit bestimmten Konfiguration von Datenpunkten sind und der Algorithmus manchmal ein eher polygonal Bild erzeugen, wenn es eine Menge von Datenpunkten ist. Das ideale Ergebnis sollte sieht eher aus wie eine Ellipse und weniger wie ein Polygon.

Hier ist ein Beispiel Bild von Wikipedia-Artikel auf abgestufter Aufstieg, die das Ergebnis zeigt, ich will:

Berge http://chakrit.net/files/stackoverflow/so_gradient_descent.png

Der Gradient Aufstieg Algorithmus ist nicht mein Interesse. Was interessiert mich; ist der Algorithmus, um die ursprüngliche Funktion in diesem Bild in erster Linie zu berechnen, vorausgesetzt, Datenpunkte mit Gewichten.

Ich habe keine Klasse in topologischen Mathematik genommen, aber ich kann etwas Kalkül tun. Ich glaube, ich etwas fehlen kann und bin ziemlich verloren, was soll ich geben, dass Google-Suchfeld.

Ich brauche einige Hinweise.

Danke!

Lösung

Was Sie suchen ist Oberflächeninterpolation.

Einige Produkte existieren, dies zu tun (hier ein )

Die resultierende Funktion / Spline / anderes mathematisches Konstrukt kann dann in der erforderlichen Auflösung abgefragt werden, um die Höhenkarte zu liefern.

Ihre Interpolationsfunktion

Sqrt((x1 - x2) ^ 2 + (y1 - y2) ^ 2)

Ist ähnlich wie Inverse Distance Die gewichteten Methoden außer Sie einen beliebigen Filter anwenden und viele der anderen Datenpunkte zu verwerfen.

Die meisten dieser Techniken beruhen auf einer angemessenen Anzahl von Proben und "Geländeähnliche Verhalten der zugrundeliegenden Werte.

ich das Gewicht, wie die Höhe Probe empfehlen die Verwendung und zu versuchen, dem einfachen Shepard-Methode in der zweiten Verbindung (filtere keine Pixel mit zu beginnen), indem der Anteil eines Abtastpunkte Beitrag zur Gesamthöhe Wert an einem Interpolationspunkt unter Sie können die Farben der Proben in diesen Verhältnissen mischen, um auch den Punkt zu färben. Verwenden der Intensität (in etwa die Graustufen in einfachen RGB-Raum zu sprechen), um die Höhe anzuzeigen oder Konturlinien in schwarz wie das Beispiel Bild hinzufügt.

Andere Tipps

Dieses Problem ist nicht so einfach, wie es auf der Oberfläche aussieht. Ihr Problem ist, dass beide Seiten der Grenze zwischen den Regionen müssen die gleiche Höhe haben, was zu sagen ist, die Höhe bei einem gegebenen Pixel wird von mehr als nur eine nächsten Nachbarn bestimmt.

Wenn ich es richtig verstehe, müssen Sie mindestens zwei Algorithmen (und ein drittes Stück Jargon).

dies richtig zu tun, müssen Sie die Ebene in eine Voronoi Tesselation .

Sie gehen zu wollen, wahrscheinlich eine kd-Baum zu helfen finden die nächsten Nachbarn. Statt unter O (n ^ 2), das wird es zu O bringen (n log (n)) (der Vorteil ist, dass Ihre Voronoi Region Generation Phase schnell genug in Entwicklung sein wird, auf der Höhe Berechnungsphase zu arbeiten).

Nun, da Sie haben eine 2-D-Karten Indizieren jeder Punkt auf seinen nächsten Nachbarn i, Sie über alle x zu gehen brauchen, y Punkt auf der Karte, und seine Höhe zu berechnen.

Um das zu tun, für einen gegebenen Punkt x, y, zuerst i seinen nächsten Nachbarn greifen und halten, dass in eine Liste, sammeln dann alle angrenzenden Regionen auf dem Voronoidiagramm. Eine einfache Möglichkeit ist Flußfüllen zu verwenden, um alle Punkte in der Region zu finden, dann schauen Sie sich um die Grenze und sammelt die anderen Identitäten auf.

Mit dieser Liste aller nächsten Nachbarn, haben Sie jetzt eine Chance auf Interpolations-richtig! (Siehe andere Antworten für Interpolationsverfahren).

Sie haben für 2-D-Interpolation der irregulären Daten für Informationen über Algorithmen gefragt, die ganz ein komplexes Gebiet ist. Da Sie sagen, Sie ArcGIS haben, I raten dringend Sie automatisch in ArcGIS seiner integrierten sich mit der bietet für automatische Berechnungen. Ich bin sicher, dass seine viel einfacher als Ihren eigenen Interpolations-Algorithmus zu schreiben. Ich habe einige Automatisierung von ArcGIS getan, es ist ziemlich einfach.

Wenn Sie eine eigene Interpolation Code schreiben - Ich rate Ihnen nicht zu - das erste, was ist es, den entsprechenden Algorithmus zu wählen, da es mehrere sind jeweils mit ihren eigenen Vor- und Nachteile. Hier einige Ratschläge von Hilfe für die ausgezeichnete Interpolation Tool cribbed Surfer (die BTW kann auch ganz leicht automatisiert werden). Es gibt mehrere Algorithmen, das sind nur die, die ich ausprobiert habe.

Kriging ist eine der flexiblere Methoden und ist für Rasterung fast jede Art von Datensatzes nützlich. Bei den meisten Datensatz, Kriging mit der Standard-linearen Variogramms ist sehr effektiv. Im Allgemeinen würden wir am häufigsten empfehlen diese Methode. Kriging ist die Standard-Rasterung Methode, weil es eine gute Karte für die meisten Datensätze erzeugt. Für größere Datenmengen können Kriging eher langsam sein. Kriging können Rasterwerte über Ihre Daten des Z-Bereich extrapolieren.
Inverse Distanzgewichtung ist schnell, aber die Tendenz hat, „Bullauge“ Muster von konzentrischen Konturen um die Datenpunkte zu erzeugen. Inverse Entfernung zu einem Power extrapoliert nicht Z-Werte über den Bereich von Daten. Eine einfache inverse Distanzgewichtung Algorithmus ist einfach zu implementieren, aber wird slowish sein.
Triangulation mit linearer Interpolation ist schnell. Wenn Sie kleine Datenmengen verwenden, erzeugt Triangulation mit Linear Interpolation verschiedene Dreiecksflächen zwischen den Datenpunkten. Triangulation mit Linear Interpolation nicht extrapoliert Z-Werte über den Bereich von Daten.
Shephard-Methode ist ähnlich Entfernung zu einer Leistung Inverse aber nicht dazu neigt, „Bullauge“ Muster zu erzeugen, vor allem, wenn ein Glättungsfaktor verwendet wird. Shepards Methode können Werte extrapolieren über Ihre Daten des Z-Bereich.

, um die Algorithmen zu implementieren: Sie können googeln versuchen, oder die Links in einigen der anderen Antworten folgen. Es gibt einige Open-Source-GIS-Pakete, die Interpolation umfassen, vielleicht können Sie die Algorithmen aus ihnen extrahieren, wenn Sie durch C ++ Höhlenforschung mag. Oder dieses Buch von David Watson ist offenbar ein klassisches betrachtet, obwohl es eine schwierige Lese ist und der Beispielcode ist Spaghetti Grund !! Aber von dem, was ich höre, ist es die beste zur Verfügung. Wenn jemand anderes auf Stack-Überlauf besser weiß, bitte mich nicht korrigieren, wie ich es auch nicht glauben kann.

Kriging ist einer der Schwergewichts-Methoden, dies zu tun, vor allem im Bereich der GIS . Es hat einige nette mathematische Eigenschaften - der Nachteil ist, dass es Ihre Variogramms langsam sein kann.

Wenn Sie etwas wollen, einfacher, es gibt viele Interpolationsroutinen, die diese sehr gut vertragen. Wenn Sie ahold einer Kopie von Numerical Recipes , Kapitel 3 widmet sich erklären viele Varianten für die Interpolation und enthält Codebeispiele und Beschreibungen ihrer funktionellen Eigenschaften.

ist der Algorithmus zur Berechnung der ursprüngliche Funktion in diesem Bild in der erste Platz, sofern Datenpunkte mit freien Gewichten.

Es ist möglich. Wenn Sie mit einzelnen Punkten starten, werden Sie immer mit Kreisen am Ende, aber wenn man die Datenpunkte gewichtet und berücksichtigen können Sie die Kreise in Ovalen wie im Bild zerquetschen ..

Der Grund, warum Sie mit Polygonen sind zu enden ist, dass Sie eine diskrete Funktion in Ihrer Berechnung verwenden -. Sie zuerst die nächste Farbe finden, dann bestimmen Sie die Farbe

Sie sollten stattdessen in Gradienten-Algorithmen suchen, die eine Farbe für einen Punkt weisen basierend auf dem Abstand und Gewicht von den drei Datenpunkten, die diesen Punkt in einem Dreieck umschließen.

Gradient Algorithmus

Es hängt davon ab, was Sie angezeigt werden versuchen. Ein verein Algorithmus wäre:

Für jedes Pixel:

Die drei Punkte, die das kleinste Dreieck bilden, das dieses Pixel umgeben
Stellen Sie diesen Punkt auf die Farbe (HSV-Farbsystem), die sowohl durch das Gewicht und Entfernung zu jedem Datenpunkt betroffen ist:

pixel.color = datapoint[1].weight * distance(pixel, datapoint[1]) * datapoint[1].color + datapoint[2].weight * distance(pixel, datapoint[2]) * datapoint[2].color + datapoint[3].weight * distance(pixel, datapoint[3]) * datapoint[3].color

Ich verwende + hier, aber Sie müssen den ‚durchschnittlich‘ Algorithmus für Ihre Anwendung geeignet bestimmen.

-Adam

Surface Interpolation scheint ein hartes und mathematisches Problem zu sein. Eine andere, billigere Art und Weise, es zu tun:

For each pixel:
For each point:
pixel.addWeight(weight(point, pixel))

def addWeight(w):
totalweight += w
numberofweights += 1
weight = totalweight / numberofweights

Beispiel Gewichtsfunktion:

def weight(point, pixel):
return point.weight * 1/(1 + sqrt((point.x - pixel.x)^2 + (point.y - pixel.y)^2))

Es ist ein ziemlich brutale Gewalt Ansatz, aber es ist einfach.

implementiert ich so etwas wie dies in Winamp vor einer Weile AVS. Es verwendet einen „metaballs“ type Ansatz des inversen quadrierte Abstand Berechnung von jedem Datenpunkt (die sqrt für die Geschwindigkeit zu vermeiden), Capping es (z.B. 1,0), und eine Summe dieser Abstände für jeden Punkt auf dem 2D-Gitter nehmen. Dadurch wird eine gleichmäßig variierende Farbe / Höhenkarte geben.

Wenn Sie auf den Code aussehen soll, seine in der "Glowy" Preset aus meinem J10 AVS packen .

EDIT: Nur es bei der Suche ich eine andere Jazz hinzugefügt, um es schöner aussehen zu lassen, dass das Teil ist am wichtigsten ist:

d1=s/(sqr(px1-rx)+sqr(py1-ry));
d2=s/(sqr(px2-rx)+sqr(py2-ry));
d3=s/(sqr(px3-rx)+sqr(py3-ry));
d4=s/(sqr(px4-rx)+sqr(py4-ry));
d5=s/(sqr(px5-rx)+sqr(py5-ry));
d6=s/(sqr(px6-rx)+sqr(py6-ry));
d=d1+d2+d3+d4+d5+d6;

, die die Summe für die 6 Punkte nehmen. Alles anderes getan zu den roten, grünen und blauen Ausgangswerten ist es schönere aussehen. Ich habe versucht, diesen Lauf in Echtzeit zu machen auf einem 320x200 Gitter auf einer 400 MHz-Maschine 6 Punkte sind nicht viel zu tragen, aber im Sinne, als sie neu war (was es tut bei ~ 20 fps). :)

Ersetzen Sie die rot = grün = und blau = ... Linien mit rot = d; etc ... um zu sehen, was ich meine. Alle prettiness geht weg, und Sie sind links mit einem Graustufen-Bild von sanft variierende Blobs um die Datenpunkte.

Ein weiterer edit: Ich habe vergessen, „s“ zu sagen, ist das gemeinsame Gewicht für alle Punkte, ändert es für jeden gibt Gewichte individuell für jeden Punkt, z.B. d1 = 2 / (...) und d2 = 1 / (...) würde d1 doppelt so viel Höhe in seiner Mitte als d2 geben. Vielleicht wollen Sie auch mit so etwas wie d1 = 2 / max (..., 1,0), um den Ausdruck an der Unterseite der Kappe der Spitzen der Punkte zu glätten, so dass sie im Unendlichen nicht in der Mitte Peak. :)

Sorry für die Unübersichtlichkeit der Antwort ... dachte ich, das Codebeispiel Posting gut genug sein würde, aber bei der Inspektion meines Code ist verwirrend und schwer zu lesen. : (

Ich weiß, das ist eine ganz alte Frage, aber ich über ihn gestolpert bei dem Versuch, ein ähnliches Problem zu lösen.

Es ist ein Open-Source-Projekt namens Surfit , die implementiert genau diese Art von Funktionalität.

Sie suchen nach etwas, das Blender Anrufe " metaballs " ( Wikipedia Artikel mit Links , Beispiel ). Denken Sie daran, auf diese Weise:

Ihre Objekte sind Zapfen, die aus dem Boden bleiben. Sie sind alle Parabeln und das Gewicht sagt, wie weit sie aus dem Boden bleiben. Alternativ machen sie alle die gleiche Höhe und stellen Sie die „Flachheit“ der Parabel entsprechend, so ein großes Gewicht macht den Kegel sehr breit, während ein geringes Gewicht sie scharf macht. Vielleicht sogar beide zu einem gewissen Grad.

Ich schlage vor, dass Sie diese implementieren und sehen, wie es aussieht.

Als nächstes müssen Sie ein Tuch oder Gummifolie über das Ergebnis hängen. Das Tuch wird um einen bestimmten Betrag dehnt und es wird in der Regel aufgrund der Schwerkraft nach unten hängen. Die Kegel halten ihn auf.

Solange Sie in die Mitte eines Kegels nahe sind, die Z-Koordinate ist nur die Position auf der Oberfläche des Kegels. Wie Sie das Kegelzentrum verlassen, Schwerkraft nach unten zu ziehen beginnt, und der Einfluss anderer Kegel wächst.

Lizenziert unter: CC-BY-SA mit Zuschreibung

Nicht verbunden mit StackOverflow