Shape Reconstruction from Unorganized Set of Points

This paper deals with the problem of reconstructing shapes from an unorganized set of sample points (called S). First, we give an intuitive notion for gathering sample points in order to reconstruct a shape. Then, we introduce a variant of alpha-shape [1] which takes into account that the density of the sample points varies from place to place, depending on the required amount of details. The Locally-Density-Adaptive-alpha-hull (LDA-alpha-hull) is formally defined and some nice properties are proven. It generates a monotone family of hulls for alpha ranging from 0 to 1. Afterwards, from LDA-alpha-hull, we formally define the LDA-alpha-shape, describing the boundaries of the reconstrcted shape, and the LDA-alpha-complex, describing the shape and its interior. Both describe a monotone family of subgraphs of the Delaunay triangulation of S (called Del(S)). That is, for alpha varying from 0 to 1, LDA-alpha-shape (resp. LDA-alpha-complex) goes from the convex hull of S (resp. Del(S)) to S. These definitions lead to a very simple and efficient algorithm to compute LDA-alpha-shape and LDA-alpha-complex in O(n log(n)). Finally, a few meaningful examples show how a shape is reconstructed and underline the stability of the reconstruction in a wide range of a even if the density of the sample points varies from place to place.