Abstract FR:

Cette étude consiste à élaborer des algorithmes, bases sur des critères géométriques, permettant de reconstruire une courbe ou une surface, à partir d'une représentation sous forme ponctuelle. Il s'agit, connaissant uniquement les coordonnées d'un ensemble de n points, de déterminer soit une ligne polygonale, soit une surface polyedrale a faces triangulaires, ayant pour sommets ces points, et qui converge uniformément vers la courbe ou la surface initiale, lorsque le nombre de points n tend vers l'infini. L’originalité de cette étude réside à la fois dans le fait qu'aucune structure sur les données n'est connue initialement, et dans l'approche théorique développée pour valider les méthodes proposées. De nombreuses applications pratiques en reconnaissant de forme, en vision par ordinateur, en imagerie médicale, ont suscité de l'intérêt pour ce type d'étude, qui peut également constituer une étape préliminaire à des problèmes d'interpolation de données. Dans le cas où les points sont situés sur une courbe, ce problème revient à déterminer un ordre sur ces données. Nous présentons deux critères qui nous permettent d'obtenir les résultats de convergence souhaites, pour une grande variété de courbes. Nous démontrons également que ces deux algorithmes, dont la complexité temporelle moyenne est en o(n log n), permettent de séparer les points selon chaque composante connexe de la courbe sur laquelle ils se trouvent et de déterminer ses éventuelles extrémités. Ces deux algorithmes sont illustres par de nombreux exemples et diverses applications pratiques, dont deux ont été réalisées en collaboration avec l’aérospatiale et le centre d'étude et de recherche de Toulouse. Dans une seconde partie, nous étendons cette étude au cas où les points initiaux sont situés sur une surface connexe. Nous présentons un premier algorithme, qui consiste a maximiser l'angle dièdre situe entre deux faces adjacentes de la surface polyedrale, et qui permet de traiter le cas de surfaces fermées convexes. Puis nous adaptons ce critère au cas de surfaces fermées non convexes et nous présentons une heuristique permettant de traiter le cas de surfaces a bord. La complexité temporelle moyenne de ces algorithmes, qui ont été illustres par divers exemples numériques, est en o(n log n)