Prudent carving: a progressively refining algorithm for shape reconstruction from dot patterns

Given a set of dot pattern point set P with the size n in the plane, we propose a Delaunay triangulation-based shape reconstruction algorithm, entitled prudent carving, that can reconstruct the inner boundaries (holes) and outer boundaries of P with the same approach. Our prudent carving algorithm is a parameter-free algorithm that has the ability to detect multiple components, sharp corners, and nested holes independent from the number of them in the total \(O(n \log n)\) $O(nlogn)$ time. The qualitative and quantitative comparison of the results with the state-of-the-art algorithms shows that the prudent carving algorithm provides an enhancement over the previously best-known algorithms for reconstructing the boundaries of points.