Interpolating an unorganized 2D point cloud with a single closed shape

Given an unorganized two-dimensional point cloud, we address the problem of efficiently constructing a single aesthetically pleasing closed interpolating shape, without requiring dense or uniform spacing. Using Gestalt’s laws of proximity, closure and good continuity   as guidance for visual aesthetics, we require that our constructed shape be a minimal perimeter, non-self intersecting manifold. We find that this yields visually pleasing results. Our algorithm is distinct from earlier shape reconstruction approaches, in that it exploits the overlap between the desired shape and a related minimal graph, the Euclidean Minimum Spanning Tree (EMSTEMST). Our algorithm segments the EMSTEMST to retain as much of it as required and then locally partitions and solves the problem efficiently. Comparison with some of the best currently known solutions shows that our algorithm yields better results.

► An efficient algorithm for 2D shape reconstruction from unorganized point clouds.
► Our algorithm can handle sparse and non-uniformly sampled 2D point sets.
► Gestalt laws translated to minimum length closed manifolds yield pleasing shapes.
► Ingeniously exploits relationship between EMST graph and minimum length polygon.
► Quality of resulting shapes excels that of best known 2D reconstruction solutions.