Identifying rectangles in laser range data for urban scene reconstruction

In urban scenes, many of the surfaces are planar and bounded by simple shapes. In a laser scan of such a scene, these simple shapes can still be identified. We present a one-parameter algorithm that can identify point sets on a plane for which a rectangle is a fitting boundary. These rectangles have a guaranteed density: no large part of the rectangle is empty of points. We prove that our algorithm identifies all angles for which a rectangle fits the point set of size n   in O(nlogn)O(nlogn) time. We evaluate our method experimentally on 13 urban data sets and we compare the rectangles found by our algorithm to the α‐shapeα‐shape as a surface boundary.

Graphical abstractFigure optionsDownload full-size imageDownload high-quality image (458 K)Download as PowerPoint slideHighlights► We automatically reconstruct a geometric model consisting of simple surfaces fitting urban LiDAR. ► Our geometry is more concise than meshes; our paradigm is more general than building fitting. ► The algorithm has one parameter and a time efficiency of O(NlogN)O(NlogN), in the size of the point set. ► We empirically analyze the parameter settings at which the algorithm works best.