Representing shapes of 2D point sets by straight outlines

The problem of faithfully matching the outlines of objects that are represented by finite point sets in 2D by simple polygons is challenging if the actual shape is non-convex and features long, straight edges and only few, distinct angles. A common application for this task is the geometric reconstruction of man-made structures like buildings from LIDAR data. Using algorithms for computing hulls to outline such point sets frequently yields polygons that consist of too many short line segments joining at unexpected angles with respect to the original object. Furthermore, if the outline polygons contain large regions that correspond to holes within the underlying object, it is desirable to represent such structures by polygons as well, but increases the complexity. We present two methods for creating outline polygons that account for the characteristics of the aforementioned kind of objects given as finite 2D point sets, and that are also suited for bordering holes. The resulting polygons have fewer vertices and angles than those obtained from hulls and are able to depict long, straight edges of the underlying objects more accurately.