2D and 3D Object Reconstruction with the gamma-Neighborhood Graph

摘要

A method for the (re)construction of a simple polygon (two dimensional) orpolyhedron (three dimensional) passing through all the points of a given set is presented. The points are assumed to lie on the boundary of a closed object without holes, but no assumptions on the relative order of the boundary points are made. The reconstruction technique is based on a parameterized geometric graph, the gamma neighborhood graph. This graph unifies a range of geometrical graphs of which the convex hull, the Delaunay triangulation, and the Gabriel graph are well known instances. The hull of the gamma neighborhood graph is constricted, exploiting geometric information incorporated in the graph. Constriction on the basis of the gamma neighborhood graph succeeds in cases where constricting the Delaunay triangulation or growing the Voronoi skeleton fails, either because the constriction process gets locked, or because the Delaunay triangulation does not contain a Hamilton, polygon/polyhedron. Object reconstruction from the gamma neighborhood graph gives correct and smooth boundaries when compared to other methods, as is shown by several examples.