Construction d'une courbe régulière d'approximation d'un ensemble de points

Claisse, Alexandra; Frey, Pascal

Comptes Rendus. Mathématique, Tome 346 (2008) no. 17-18, pp. 1017-1022.

Dans cette Note, on s'intéresse au problème de la construction d'une courbe régulière Γ telle que $\forall x\in \Gamma$, $d(x,V)⩽\epsilon$, où $d(x,V)={\min }_{\overline{x}\in V}\Vert x-\overline{x}\Vert$ pour un ensemble de points donné V supposé appartenir à la frontière d'un ouvert de ${\mathbb{R}}^2$, et pour ε, petit fixé. Pour approcher cette courbe, on résout un problème de minimisation basé sur une formulation de type ligne de niveau. La particularité du schéma numérique utilisé est qu'il s'appuie sur une triangulation anisotrope d'un domaine convexe Ω contenant V. Un exemple de construction est proposé pour illustrer cette approche.

In this Note, we deal with the problem of constructing a regular (smooth) curve Γ such that $\forall x\in \Gamma$, $d(x,V)⩽\epsilon$, where $d(x,V)={\min }_{\overline{x}\in V}\Vert x-\overline{x}\Vert$ for a given point cloud V assumed to belong to the boundary of an open subset of ${\mathbb{R}}^2$ and for ε small. To approximate this curve, we solve a minimization problem based on a levelset formulation. The particularity of the corresponding numerical scheme is to solve on an anisotropic triangulation of a convex domain Ω enclosing V. A numerical example is provided to show the efficiency of the proposed approach.

[1] Abgrall, R. Numerical discretisation of boundary conditions for first order Hamilton–Jacobi equation n triangular meshes, Comm. Pure Appl. Math., Volume 49 (1996), pp. 1339-1373

[2] D. Cohen-Steiner, F. Da, A greedy Delaunay based surface reconstruction algorithm, preprint INRIA RR-4564, 2002

[3] Crandall, M.; Lions, P.L. Two approximations of solutions of Hamilton–Jacobi equations, Math. Comp., Volume 43 (1984), pp. 1-19

[4] T.K. Dey, J. Giesen, J. Hudson, Delaunay based shape reconstruction from large data, in: Proc. IEEE Symposium in Parallel and Large Data Visualization and Graphics, 2001, pp. 19–27

[5] Ducrot, V.; Frey, P. Contrôle de l'approximaion géométrique d'une interface par une métrique anisotrope, C. R. Acad. Sci. Paris, Ser. I, Volume 345 (2007), pp. 537-542

[6] Gout, C.; Le Guyader, C.; Vese, L. Segmentation under geometrical conditions using geodesic active contours and interpolation using level set methods, Numer. Algorithms, Volume 39 (2005) no. 1–3, pp. 155-173

[7] Jiang, G.; Peng, D. Weighted ENO schemes for Hamilton–Jacobi equations, SIAM J. Sci. Comput., Volume 21 (2000), pp. 2126-2143

[8] Osher, S.; Sethian, J.A. Fronts propagating with curvature-dependent speed: Algorithms based on Hamilton–Jacobi formulations, J. Comput. Phys., Volume 79 (1988), pp. 12-49

[9] Sethian, J.A. Fast marching methods, SIAM Rev., Volume 41 (1999) no. 2, pp. 199-235

[10] Sussman, M.; Smereka, P.; Osher, S. A level set approach for computing solutions to incompressible two-phase flow, J. Comput. Phys., Volume 114 (1994), pp. 146-159

[11] Zhao, H.K.; Osher, S.; Merriman, B.; Kang, M. Implicit and nonparametric shape reconstruction from unorganized data using a variational level set method, Comput. Vision and Image Understanding, Volume 80 (2000), pp. 295-314

[12] Zhao, H.K.; Osher, S. Visualization, analysis and shape reconstruction of unorganised datasets (Osher, S.; Paragios, N., eds.), Geometric Level Set Methods in Imaging, Vision and Graphics, Springer, 2002