3-DIMENSIONAL ALPHA-SHAPES
3-DIMENSIONAL ALPHA-SHAPES
复制标题
DOI：
10.1145/174462.156635
复制
发表时间：
1994-01-01
影响因子：
6.2
通讯作者：
MUCKE, EP
中科院分区：
文献类型：
--
作者：
EDELSBRUNNER, H;MUCKE, EP
通常，科学计算中的数据以其抽象的形式是空间中的一个有限点集，它有时是有用的或需要计算一个人可能称之为该集合的‘’形状‘’。为此，本文引入了R3中有限点集的Alpha形式族的形式概念。每个形状都是一个定义明确的多面体，派生自点集的Delaunay三角剖分，参数α是一个元素，R控制所需的细节级别。给出了一个算法，该算法在最坏的情况下，在O(N2)时间内构造出给定大小为n的集合的整个形状族。讨论了该算法的健壮性实现，并提到了该算法在科学计算领域的几个应用。
Frequently, data in scientific computing is in its abstract form a finite point set in space, and it is sometimes useful or required to compute what one might call the ''shape'' of the set. For that purpose, this article introduces the formal notion of the family of alpha-shapes of a finite point set in R3. Each shape is a well-defined polytope, derived from the Delaunay triangulation of the point set, with a parameter alpha is-an-element-of R controlling the desired level of detail. An algorithm is presented that constructs the entire family of shapes for a given set of size n in time O(n2), worst case. A robust implementation of the algorithm is discussed, and several applications in the area of scientific computing are mentioned.