Identifying rectangles in laser range data for urban scene reconstruction |
| |
Authors: | Thijs van Lankveld Marc van Kreveld Remco Veltkamp |
| |
Affiliation: | Utrecht University, Department of Information and Computing Sciences, Princetonplein 5, 3584CC Utrecht, The Netherlands |
| |
Abstract: | 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) time. We evaluate our method experimentally on 13 urban data sets and we compare the rectangles found by our algorithm to the α‐shape as a surface boundary. |
| |
Keywords: | Boundary representations Computational geometry Object modeling Geometric algorithms |
本文献已被 ScienceDirect 等数据库收录! |