FAST 3-D EUCLIDEAN CONNECTED COMPONENTS

Published: 2022

Author(s):
Landis, E. N.
Franklin, R.
Magalhães, S.

Publication Name:

Publication URL: https://wrfranklin.org/p/240-connect-gem-2021.pdf

Research Area:
Keywords:
,

Abstract:

We present an efficient algorithm and implementation for computing the connected components within a 3-D cube of voxels, also known as the Euclidean union-find problem. There may be over 10ˆ9 voxels. The components may be 8-connected or 26-connected. Computing connected components has applications ranging from material failure in concrete under increasing stress to electrical conductivity in complex metal objects to elasticity in 3D printed parts. One key to efficiency is representing voxels by 1-D runs of adjacent voxels. We also compute each component’s surface area. As a special case, 2-D connected components of images may easily be computed.