La forme d’un nuage de points est naturelle pour l’œil humain mais difficile à définir précisément. Au début des années 80, Edelsbrunner, Kirkpatrack et Seidel définirent les α-shapes, une généralisation de l’enveloppe convexe, offrant ainsi le support scientifique pour raisonner sur ce que pourrait être la « forme » d’un nuage de points. Les α-shapes fournissent une définition précise et formelle de la forme d’un nuage de points pour une valeur de α. La variation de cette valeur sur ℝ engendre une famille monotone de formes de la plus grossière (le plan) à la plus fine (le nuage de points) en passant par son enveloppe convexe.
Les α-shapes furent à l’origine d’une quantité considérable de résultats de recherche notamment dans le domaine de la reconstruction de surface à partir de nuages de points. Toutefois une de leurs principales lacunes, que chacun a palliée à sa manière, réside dans l’incapacité à fournir une forme «acceptable» quand les points du nuage ne sont pas uniformément répartis. De récents papiers notamment en fouille de données (data mining) montrent l’intérêt grandissant de définir la frontière d’un ensemble de données spatiales ou même de dimensions supérieures afin d’établir des «clusters» dont les contours ne sont pas nécessairement convexes, même en présence d’un ensemble de données «désorganisé» et «bruité».
Nous proposons une variante des α-shapes qui pourrait être un outil d’aide au raisonnement sur la «forme» d’un nuage de points non nécessairement uniforme. Cette approche donne une interprétation précise et naturelle de la frontière d’un nuage de points dont la répartition varie par endroits selon, a priori, le niveau de détail requis. Il s’agit d’une filtration du complexe de Delaunay d’un ensemble de points en dimension quelconque, appelée «Locally-Density-Adaptive-α-shape» ou «LDA-α-shape», qui tient compte de la densité locale des points. Nous montrons que la variation de α de 0 à 1 engendre une famille monotone de sous-complexes de Delaunay de sa forme la plus grossière (l’enveloppe convexe) à sa forme la plus fine (le nuage de points).
This document was translated from LATEX by HEVEA.