Shape Reconstruction from Unorganized Set of Points
Shape Reconstruction from Unorganized Set of Points
复制标题
DOI：
10.1007/978-3-642-13772-3_28
复制
发表时间：
2010-06
期刊：
影响因子：
--
通讯作者：
Yvan Maillot;Bruno Adam;Mahmoud Melkemi
中科院分区：
文献类型：
--
作者：
Yvan Maillot;Bruno Adam;Mahmoud Melkemi
本文讨论从一组无组织的样本点（称为 S）重建形状的问题。首先，我们给出了收集样本点以重建形状的直观概念。然后，我们引入了α-形状的变体[1]，它考虑到样本点的密度因地点而异，具体取决于所需的细节量。局部密度自适应α-船体（LDA-α-船体）被正式定义，并证明了一些良好的特性。它生成一个单调的 α 范围从 0 到 1 的外壳族。之后，从 LDA-α-外壳，我们正式定义 LDA-α-形状，描述重建形状的边界，以及 LDA-α-复合体，描述形状及其内部。两者都描述了 S 的 Delaunay 三角剖分的单调子图族（称为 Del(S)）。也就是说，对于从 0 到 1 变化的 α，LDA-α 形状（分别为 LDA-α-复合体）从 S(resp.Del(S)) 的凸包变为 S。这些定义导致了一种非常简单且有效的算法来计算 O(nlog(n)) 中的 LDA-α-shape 和 LDA-α-complex。最后，一些有意义的例子展示了形状是如何重建的，并强调了即使样本点的密度因地而异，重建在广泛的α范围内的稳定性。
This paper deals with the problem of reconstructing shapes from an unorganized set of sample points (calledS). First, we give an intuitive notion for gathering sample points in order to reconstruct a shape. Then, we introduce a variant ofα-shape [1] which takes into account that the density of the sample points varies from place to place, depending on the required amount of details. The Locally-Density-Adaptive-α-hull (LDA-α-hull) is formally defined and some nice properties are proven. It generates a monotone family of hulls forαranging from 0 to 1. Afterwards, from LDA-α-hull, we formally define the LDA-α-shape, describing the boundaries of the reconstructed shape, and the LDA-α-complex, describing the shape and its interior. Both describe a monotone family of subgraphs of the Delaunay triangulation ofS(calledDel(S)). That is, forαvarying from 0 to 1, LDA-α-shape (resp. LDA-α-complex) goes from the convex hull ofS(resp.Del(S)) toS. These definitions lead to a very simple and efficient algorithm to compute LDA-α-shape and LDA-α-complex inO(nlog(n)). Finally, a few meaningful examples show how a shape is reconstructed and underline the stability of the reconstruction in a wide range ofαeven if the density of the sample points varies from place to place.