Quadtree-based polynomial polygon fitting

In this paper, we present a novel method for surface reconstruction with a low execution time for segmenting and representing scattered scenes accurately. The surfaces are described in a memory-efficient fashion as polynomial functions and polygons. Segmentation and parameter determination is done in one pass by using a quadtree on ordered point clouds, which results in a complexity of O(log n). This paper includes an evaluation with respect to reconstruction accuracy, segmentation precision, execution time and compression ratio of everyday indoor scenes. Our surface reconstruction algorithm outperforms comparable approaches with respect to execution time and accuracy. More importantly, the new technique handles curved shapes accurately and enables complex tasks like 3D mapping for mobile robots in an unknown environment