Multi-region Delaunay complex segmentation

摘要

We focus on the problem of segmenting scattered point data into multiple regions in a single segmentation pass. To solve this problem, we begin with a set of potential boundary points and use a Delaunay triangulation to complete the boundaries. We then use information from the triangulation and its dual Voronoi complex to determine for each face whether it resembles a boundary or interior face, allowing a user to choose a specific segmentation by keeping only faces where our parameter is above a threshold. The resulting algorithm has time complexity in O(nd), where n is the number of Delaunay simplices.