Berechnen von 2D-Konturen aus der Punktwolke

Question

Ich habe eine 2D-Punktwolke, die jeweils einen skalaren Wert enthält. Angenommen, dieser Wert kann an jedem beliebigen Punkt auf der Ebene interpoliert werden, und ich habe einen Freiheitsgrad, um die genaue Interpolationsformel zu wählen, solange sie glatt ist und konvergiert zu den gegebenen Punkten, wenn sie in ihrer Nähe berechnet werden. Mein Ziel ist es, geschlossene Konturen zu konstruieren, die einem konstanten Skalarwert entsprechen.

Mein spezieller Fall ist etwas komplexer, aber der Einfachheit halber nehmen wir an, dass wir eine Geländehöhe (Höhe) an einigen Punkten haben, und wir müssen Konturen konstanter Höhe für einige gegebene Werte davon konstruieren. Konturen sollten durch Polylinien approximiert werden.

Zuvor erhielt ich die Punkte in Form eines regelmäßigen Gitters, und ich löste es, indem ich die Kontursegmente in jeder Gitterzelle separat untersuchte und (wenn nötig) baute. Das heißt, für jede Gitterzelle habe ich die Werte in den Ecken geprüft, um zu erkennen, ob die Kontur Zellengrenzen überschreiten sollte (einige Ecken sollten höher und einige niedriger sein), und jeweils die Schnittpunkte berechnet.

Jetzt muss ich dies aus beliebigen Punktwolke rekonstruieren.

Natürlich kann ich aus der Punktwolke (da wir interpolieren) ein regelmäßiges Gitter bauen, dicht genug, aus dem die Konturen berechnet werden können, aber ich hätte gerne einen effizienteren Algorithmus. Meine Idee ist es, die Punkte in der Wolke so zu verbinden, dass die Ebene von Dreiecken (oder komplexeren konvexen Polygonen) bedeckt wird, die jeweils eine Gitterzelle bilden. Dann kann ich Konturen so wie früher konstruieren.

Gibt es einen bekannten Algorithmus, um speziell dieses Problem zu lösen?

Update:

Dank @coproc. Ich kenne Delaunay Triangulation, und das ist wahrscheinlich der Weg zu gehen. Es gibt jedoch immer noch Fragen darüber, wie man in beliebigen Punkten auf einer Ebene interpoliert: Wäre es ausreichend, nur die Dreiecksspitzen oder auch andere nahegelegene Punkte zu betrachten. In einem unbalanzierten Fall kann es eine Situation geben, in der ein Punkt in extremer Nähe zu dem Dreieck ist. Zum Beispiel hier:

Als Alternative kann ich denken, nur von einem beliebigen Punkt in einer Ebene ausgehend und dann senkrecht auf den Gradienten, um die Konturen zu erstellen.

Answer 1

Dies scheint wie ein GIS-Interpolation/Extrapolationsproblem. Es gibt mehrere Techniken, um "intelligenter" zu interpolieren, und ich würde vorschlagen, dass Sie zuerst die inverse Distanzgewichtung (IDW) und dann Kriging versuchen, wenn Sie Zeit haben, darauf zu achten.

IDW kurz gesagt basiert auf dem "ersten Gesetz der Geographie": Dinge nahe beieinander korrelieren. Sie geben engeren Punkten höhere Gewichte und interpolieren das Gitter.

Kriging versucht, die Ausrichtung der betreffenden Phänomene zu berücksichtigen und passt die Gewichte entsprechend an. Stellen Sie sich eine Hauptkomponentenanalyse für die Nachbarschafts- und Skalierungspunktabstände gemäß der Varianz in verschiedenen Richtungen vor.

Dies ist ein kurzer Blick auf einige der bestehenden Methoden. http://www.bisolutions.us/A-Brief-Introduction-to-Spatial-Interpolation.php