Voronoi-Interpolation

Die Voronoi-Interpolation (engl. natural neighbor interpolation „Interpolation durch natürliche Nachbarn“), auch Sibson-Interpolation genannt, ist ein Interpolationsverfahren, das mit Voronoi-Diagrammen arbeitet.

Prinzip

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

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

Abb. 1. Voronoi-Diagramm. Die Kanten liegen jeweils exakt auf halbem Weg zwischen zwei Punkten.		Abb. 2. Die neue Zelle (rot) wird eingefügt. Die Überlappungsbereiche mit den alten Zellen (orange) dienen als Gewichtungsfaktoren.

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:

$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$

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

Anwendung

Die Voronoi-Interpolation kann prinzipiell überall angewandt werden, wo in einem metrischen Raum Werte interpoliert werden sollen.

Ein Dreiecksnetz bildet die Oberfläche eines dreidimensionalen Objekts nach. Die Delaunay-Triangulation erzeugt Dreiecksnetze mit für die Computergrafik besonders günstigen Eigenschaften.

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.