Interpolation par voisins naturels

L'interpolation par voisins naturels est une méthode d'interpolation multivariée, développée par Robin Sibson (en). La méthode est basée sur le diagramme de Voronoi d'un ensemble discret de points dans l'espace. Elle présente des avantages sur des méthodes plus simples d'interpolation, comme l'interpolation au plus proche voisin, en donnant une approximation plus lisse de la fonction interpolée.

Interpolation par voisins naturels avec poids de Sibson en 2D. La surface des disques verts correspondant au poids (w_i). La région en violet correspond à la nouvelle cellule de Voronoi après avoir inséré un point d'interpolation (point noir). Les poids représentent l'intersection de la surface violette avec chacune des cellules voisines

L'estimation se calcule par :

$G(\mathbf {x} )=\sum _{i=1}^{n}w_{i}(\mathbf {x} )f(\mathbf {x} _{i})$

avec G(x) l'approximation au point x, w_i les poids et f(x_i) les valeurs connues de la fonction de référence aux points (x_i).

Poids de Sibson

La méthode de Sibson pour définir les poids w_i consiste à calculer la part du volume de la cellule de Voronoi liée à x prise aux autres cellules. Pour la calculer, il faut considérer le diagramme de Voronoi de référence (lié aux points (x_i)) et un second, lié aux points (x_i) et au point x. Ainsi, une nouvelle cellule apparait, liée à x. Ainsi, en désignant par A(x) le volume de cette nouvelle cellule et A(x_i) le volume de l’intersection entre la nouvelle cellule liée à x et l’ancienne cellule liée à x_i, le poids est défini par :

$w_{i}(\mathbf {x} )={\frac {A(\mathbf {x} _{i})}{A(\mathbf {x} )}}$

Interpolation par voisins naturels avec poids de Laplace en 2D. L'interface l(x_i) entre les cellules liées a x et x_i est en bleu, et la distance d(x_i) entre x et x_i en rouge.

Poids de Laplace

On peut définir les poids par

$w_{i}(\mathbf {x} )={\frac {\frac {l(\mathbf {x} _{i})}{d(\mathbf {x} _{i})}}{\sum _{k=1}^{n}{\frac {l(\mathbf {x} _{k})}{d(\mathbf {x} _{k})}}}}$

où l(x_i) désigne la mesure de l'interface entre les cellules liées à x et x_i dans le nouveau diagramme de Voronoi (longueur d'arête en 2D, surface en 3D) et d(x_i), la distance entre x et (x_i).

Voir aussi

• Pondération inverse à la distance
• Interpolation multivariée