imported>PerfektesChaos: tk k

2021-08-23T00:49:19Z

tk k

Neue Seite

Die '''Voronoi-Interpolation''' ({{enS|'''natural neighbor interpolation'''}} „Interpolation durch natürliche Nachbarn“), auch '''Sibson-Interpolation''' genannt, ist ein [[Interpolation (Mathematik)|Interpolationsverfahren]], das mit [[Voronoi-Diagramm]]en arbeitet.

== Prinzip ==
Gegeben sind Punkte in einem [[Metrischer Raum|metrischen Raum]] und die ihnen zugewiesenen Werte. In den Raum wird ein zusätzlicher Punkt eingefügt. Sein Wert soll aus den umgebenden Punkten interpoliert werden.

Dazu wird zunächst aus den vorgegebenen Punkten das [[Voronoi-Diagramm]] erzeugt (Abb. links). Anschließend wird der zusätzliche Punkt mit seiner Voronoi-Zelle eingefügt (Abb. rechts).

{| class="center"
|-
| Voronoi-Diagramm. Die Kanten liegen jeweils exakt auf halbem Weg zwischen zwei Punkten.
|
| Die neue Zelle (rot) wird eingefügt. Die Überlappungsbereiche mit den alten Zellen (orange) dienen als Gewichtungsfaktoren.
|-
| [[Datei:Voronoi diagram.svg|310px]]
|
| [[Datei:Voronoi-Interpolation.svg|310px]]
|}

Der Wert des neuen Punktes ergibt sich nun, indem die Flächeninhalte der Überschneidungen mit den Nachbarzellen im Verhältnis zum Gesamtflächeninhalt der neuen Zelle als Gewichtungsfaktoren der Interpolation verwendet werden. Im Beispiel oben wäre das:

: <math>n = \frac{A ( A \cap N )}{A(N)} \cdot a + \frac{A( B \cap N )}{A(N)} \cdot b + \frac{A ( C \cap N )}{A(N)} \cdot c + \frac{A ( D \cap N )}{A(N)} \cdot d</math>

wobei A(N) den Flächeninhalt einer Fläche N angibt, und a,b,c und d für die gegebenen Funktionswerte stehen.

== Anwendung ==
[[Datei:Delaunay-Triangulation.svg|mini|Ein Dreiecksnetz bildet die Oberfläche eines dreidimensionalen Objekts nach. Die Delaunay-Triangulation erzeugt Dreiecksnetze mit für die Computergrafik besonders günstigen Eigenschaften.]]
Die Voronoi-Interpolation kann prinzipiell überall angewandt werden, wo in einem metrischen Raum Werte interpoliert werden sollen.

Dadurch, dass Voronoi-Diagramme eng mit der [[Delaunay-Triangulation]] verwandt sind, bietet sich die Voronoi-Interpolation insbesondere in der 3D-Computergrafik an. Sie kann dort verwendet werden, um ein bestehendes Dreiecksnetz durch Hinzufügen neuer Punkte zu verfeinern.

[[Kategorie:Numerische Mathematik]]
[[Kategorie:Algorithmische Geometrie]]

Voronoi-Interpolation - Versionsgeschichte

imported>PerfektesChaos: tk k