Three-dimensional alpha shapes

DOI10.1145/174462.156635MaRDI QIDQ4296530zbMATH OpenOpenAlexWikidataFDO

Authors E. P. Mücke, Herbert Edelsbrunner

Publication date 19 June 1994

Published in ACM Transactions on Graphics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/9410208

zbMATH Keywords

Delaunay triangulationgeometric algorithmsrobust implementation\(\alpha\)-shapescomputational graphics

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

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 paper introduces the formal notion of the family of $alpha$-shapes of a finite point set in $Rea{l}^3$. Each shape is a well-defined polytope, derived from the Delaunay triangulation of the point set, with a parameter $alphainReal$ 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(n^2)$, worst case. A robust implementation of the algorithm is discussed and several applications in the area of scientific computing are mentioned.

Recommendations

• scientific article; zbMATH DE number 3854464
• scientific article; zbMATH DE number 1189236
• 3D kinetic alpha complexes and their implementation
• Efficient generation of simple polygons for characterizing the shape of a set of points in the plane
• Combinatorial Image Analysis

Cited in

(only showing first 100 items - show all)

• A prediction method based on the voxel model and the finite cell method for cutting force-induced deformation in the five-axis milling process
• The meshless finite element method
• A unified Lagrangian formulation for solid and fluid dynamics and its possibility for modelling submarine landslides and their consequences
• Surface reconstruction via cooperative evolutions
• A fully partitioned Lagrangian framework for FSI problems characterized by free surfaces, large solid deformations and displacements, and strong added-mass effects
• Modeling continuous grain crushing in granular media: a hybrid peridynamics and physics engine approach
• Continuation of point clouds via persistence diagrams
• An enhanced semi-explicit particle finite element method for incompressible flows
• A semi-implicit stabilized particle Galerkin method for incompressible free surface flow simulations
• An efficient runtime mesh smoothing technique for 3D explicit Lagrangian free-surface fluid flow simulations
• Free-slip boundary conditions for simulating free-surface incompressible flows through the particle finite element method
• A partitioned fully explicit Lagrangian finite element method for highly nonlinear fluid-structure interaction problems
• Lagrangian modelling of large deformation induced by progressive failure of sensitive clays with elastoviscoplasticity
• Uniform boundary conditions on models of spherical particles through alpha shape surface tracking and Laguerre-Voronoi diagrams
• Approximate Delaunay mesh reconstruction and quality estimation from point samples
• On the scaling of the instability of a flat sediment bed with respect to ripple-like patterns
• Second-order consensus protocols based on transformed \(d\)-path Laplacians
• SURFACE RECONSTRUCTION OF FREEFORM OBJECTS BASED ON HIERARCHICAL SPACE DECOMPOSITION
• Generation of segmental chips in metal cutting modeled with the PFEM
• Surface reconstruction by offset surface filtering
• Geometric algorithm visualization, current status and future
• The β-Shape and β-Complex for Analysis of Molecular Structures
• The particle finite element method (PFEM) in thermo-mechanical problems
• Surface reconstruction using umbrella filters
• Design and analysis of planar shape deformation
• Refinements to the boundary transformation vector representation of attractor shape deformation to enhance system parameter identification
• A hybrid Lagrangian-Eulerian particle finite element method for free-surface and fluid-structure interaction problems
• A SIMPLE ALGORITHM FOR HOMEOMORPHIC SURFACE RECONSTRUCTION
• The weighted mean curvature derivative of a space-filling diagram
• The weighted Gaussian curvature derivative of a space-filling diagram
• 3D regularized \(\mu(I)\)-rheology for granular flows simulation
• Level set and density estimation on manifolds
• Persistent Homology: A Topological Tool for Higher-Interaction Systems
• Advances in stabilized finite element and particle methods for bulk forming processes
• Cohomological learning of periodic motion
• Accelerating smooth molecular surface calculation
• Preserving geometric properties in reconstructing regions from internal and nearby points
• A particle finite element method for analysis of industrial forming processes
• Atom simplification and quality T-mesh generation for multi-resolution biomolecular surfaces
• Unified Lagrangian formulation for solid and fluid mechanics and FSI problems
• Denoising point sets via \(L_0\) minimization
• General framework for testing Poisson-Voronoi assumption for real microstructures
• The extended Delaunay tessellation
• On the imposition of essential boundary conditions in natural neighbour Galerkin methods
• Finding the homology of submanifolds with high confidence from random samples
• Volume-optimal cycle: tightest representative cycle of a generator in persistent homology
• Possibilities of the particle finite element method for fluid-soil-structure interaction problems
• Triangulating the surface of a molecule
• Holes and dependences in an ordered complex
• Representing implicit surfaces satisfying Lipschitz conditions by 4-dimensional point sets
• Defective point data reconstruction based on improved process of morphological operations
• Parallel and adaptive surface reconstruction based on implicit PHT-splines
• Principal component analysis of persistent homology rank functions with case studies of spatial point patterns, sphere packing and colloids
• A model reduction method for the post-buckling analysis of cellular microstructures
• Regularization of discrete contour by Willmore energy
• Reconstruction of surfaces of revolution with partial sampling.
• Efficient generation of simple polygons for characterizing the shape of a set of points in the plane
• Measuring shape with topology
• Polyhedral perturbations that preserve topological form
• Provably correct reconstruction of surfaces from sparse noisy samples
• Some improvements on free surface simulation by the particle finite element method
• A mixed u-p edge-based smoothed particle finite element formulation for viscous flow simulations
• Implicit reconstructions of thin leaf surfaces from large, noisy point clouds
• Local Delaunay-based high fidelity surface reconstruction from 3D point sets
• The neural particle method - an updated Lagrangian physics informed neural network for computational fluid dynamics
• Mathematical optimization problems for particle finite element analysis applied to 2D landslide modeling
• THE PARTICLE FINITE ELEMENT METHOD — AN OVERVIEW
• The power crust, unions of balls, and the medial axis transform
• Simulation of wave overtopping of maritime structures in a numerical wave flume
• A weak characterisation of the Delaunay triangulation
• Field choice problem in persistent homology
• Fluid-structure interaction using the particle finite element method
• Parallel Delaunay triangulation for particle finite element methods
• Point-cloud method for image-based biomechanical stress analysis
• A topological sampling theorem for robust boundary reconstruction and image segmentation
• Modelling three-dimensional piece-wise homogeneous domains using theα-shape-based natural element method
• TIGHTENING: MORPHOLOGICAL SIMPLIFICATION
• \(N\)-body gravitational and contact dynamics for asteroid aggregation
• Using the medial axis to represent flow features for feature-aligned unstructured quad-dominant mesh generation
• Statistics for data with geometric structure. Abstracts from the workshop held January 21--27, 2018
• On Poincaré cone property
• Topologically Correct Image Segmentation Using Alpha Shapes
• Delaunay conforming iso-surface, skeleton extraction and noise removal
• A particle finite element method based on level-set functions
• A topological data analysis study on murine pulmonary arterial trees with pulmonary hypertension
• Boundary estimation from point clouds: algorithms, guarantees and applications
• From empirical data to inter-individual interactions: unveiling the rules of collective animal behavior
• \(r\)-regular shape reconstruction from unorganized points
• Level set and density estimation on manifolds
• Zigzag persistence
• Incremental topological flipping works for regular triangulations
• Approximating the pathway axis and the persistence diagrams for a collection of balls in 3-space
• Order-\(k\) \(\alpha\)-hulls and \(\alpha\)-shapes
• Imposing essential boundary conditions in the natural element method by means of density-scaled?-shapes
• Computational topology: Ambient isotopic approximation of 2-manifolds.
• Radius functions on Poisson-Delaunay mosaics and related complexes experimentally
• Shape space from deformation
• The maximum opposite angulation for mesh construction
• Smooth surface reconstruction via natural neighbour interpolation of distance functions
• Dynamic maintenance and visualization of molecular surfaces.

This page was built for publication: Three-dimensional alpha shapes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4296530)