Distance de chanfrein

Cet article est une ébauche concernant les mathématiques. Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

Les distances de chanfrein sont des distances discrètes utilisant des masques dont les poids sont des entiers. Les distances de chanfrein sont rapides à calculer sur une machine. Bien qu'elles soient plus précises que les distances discrètes d4 et d8, elles ne fournissent qu'une approximation de la distance euclidienne.

Définition

Une pondération est un couple $(\mathbf{x},w)$ où $\mathbf{x}$ est un point (le déplacement) et $w$ un entier. Un masque $\mathcal{M}$ est un ensemble fini de pondérations : $\mathcal{M} = \left\{(\mathbf{x}_i,w_i)\right\}$. Un masque de chanfrein est un masque possédant une symétrie centrale, dont les poids sont strictement positifs et les déplacements non nuls.

Il est possible de trouver un chemin entre deux points $p$ et $q$ en utilisant les déplacements d'un masque de chanfrein. Soit $\mathcal{M} = \left\{(\mathbf{x}_i,w_i)\right\}$ un masque de chanfrein, alors

$q = p + \sum \lambda_i \mathbf{x}_i$,

où $\lambda_i$ est un entier qui correspond au nombre de fois que le déplacement $\mathbf{x}_i$.

Distance de chanfrein

Une distance de chanfrein $d_{\mathcal{M}}$ entre deux points $p$ et $q$ d'un espace discret est le coût minimal $\sum \lambda_i w_i$ de tous les chemins de longueur finie $\sum \lambda_i \mathbf{x}_i$ entre $p$ et $q$ et utilisant les déplacements $\mathbf{x}_i$ du masque $\mathcal{M}$ :

$d_{\mathcal{M}} = \min \left\{ \sum \lambda_i w_i \left| q = p + \sum \lambda_i \mathbf{x}_i \right. \right\}$.