Urban areas are of increasing importance in most of the countries since they have been changing rapidly over time. Buildings are the main objects of these areas, and building boundaries are one of the key factors for urban mapping and city modelling. Accurate building extraction using lidar data has been a prevalent topic that many research efforts have been contributed to. However, the complexity of building shapes and irregularity of lidar point distribution make the task difficult to achieve. Although there are plenty of algorithms trying to solve the difficulties, it is not feasible for a single method to fit for all. Each can perform well under a certain situation and requirement only.
In this paper, several building boundary extraction algorithms including an alpha-shape algorithm, a grid-based algorithm, and a concave hull algorithm are assessed. The strengths and limitations of each algorithm are identified and addressed. The point cloud used in this research is derived from the airborne lidar data acquired over the main campus of the University of New South Wales (UNSW) Australia in 2005.
Typically, the boundary extraction algorithms are applied to the clusters of building points when lidar data is segmented and classified. Many approaches have been attempted to improve the extraction algorithms. The simplest way to extract a rough boundary is using the convex hull method which has been implemented by several researchers including Qihong et al. . However, this algorithm only fits for buildings with regular convex shapes. In order to overcome the limitation of this method many researchers have modified and improved the algorithm and obtained more reliable boundaries [2, 3]. Another prevalent and recent method is using an alpha-shape algorithm based on two-dimensional Delaunay Triangulation [4, 5]. This method works for both concave and convex shapes, and even for some complicated shapes. Another approximation-based algorithm was introduced by Zhou and Neumann  using watertight grids.
Although it is observed that aforementioned algorithms work well in different scenarios, a quantitative comparison analysis on each algorithm’s performance on an identical dataset is rarely reported. Aiming at evaluating and improving these algorithms, we implemented a mathematical framework to compare the algorithms in an object-by-object basis. This study compares the boundary points selected by different algorithms and the impact of the selection on the accuracy.
In this paper, three algorithms for building boundary extraction are assessed in an object-by-object basis. The alpha-shape algorithm generates reliable boundaries for most of sample buildings, while the grid-based algorithm shows a little inconsistency in some cases. The concave hull algorithm performs moderately with a few limitations. The alpha-shape algorithm is suggested for general building boundary extraction for its consistency and reliability.