Three-dimensional alpha shapes

TLDR

Scientific computing often deals with finite point sets, and the shape of such a set can be defined as a polytope derived from its Delaunay triangulation, with a parameter α controlling the level of detail. This article introduces the formal notion of the family of α‑shapes for a finite point set in ℝ³. An algorithm is presented that constructs the entire family of α‑shapes in O(n²) time, and a robust implementation is discussed. The implementation is shown to be robust and is applied to several scientific computing problems.

Abstract

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 α-shapes of a finite point set in R 3 . Each shape is a well-defined polytope, derived from the Delaunay triangulation of the point set, with a parameter α ε 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 0(n 2 ) , worst case. A robust implementation of the algorithm is discussed, and several applications in the area of scientific computing are mentioned.