Publication

Fast 3-D Euclidean connected components

W. Randolph Franklin, Salles Viana Gomes de Magalhães, and Eric N Landis. Fast 3-D Euclidean connected components. In John Krumm, editor, 3rd ACM SIGSPATIAL International Workshop on Spatial Gems (SpatialGems 2021). ACM, 2 Nov 2021. URL: https://www.spatialgems.net/.
[full text]
BibTeX
@incollection{connect-gem-2021,
    author = "Franklin, W. Randolph and de Magalhães, Salles Viana Gomes and Landis, Eric N",
    editor = "Krumm, John",
    title = "Fast {3-D} {Euclidean} connected components",
    booktitle = "3rd {ACM SIGSPATIAL} International Workshop on Spatial Gems (SpatialGems 2021)",
    publisher = "ACM",
    year = "2021",
    month = "2 Nov",
    location = "Beijing, China (virtual)",
    mykey = "recent salles landis connect topology 2021",
    url = "https://www.spatialgems.net/",
    href = "\bibhref{240-connect-gem-2021}"
}

Abstract

We present an efficient algorithm, with implementations, 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. On key to efficiency is representing voxels by 1-D \emphruns of adjacent voxels. As a special case, 2-D connected components of images may easily be computed.

Full text

Read the paper

The full text opens at its existing location.

Preview the full text on this page

Open or download the paper

Citation

Download BibTeX ↓

@incollection{connect-gem-2021,
    author = "Franklin, W. Randolph and de Magalhães, Salles Viana Gomes and Landis, Eric N",
    editor = "Krumm, John",
    title = "Fast {3-D} {Euclidean} connected components",
    booktitle = "3rd {ACM SIGSPATIAL} International Workshop on Spatial Gems (SpatialGems 2021)",
    publisher = "ACM",
    year = "2021",
    month = "2 Nov",
    location = "Beijing, China (virtual)",
    mykey = "recent salles landis connect topology 2021",
    url = "https://www.spatialgems.net/",
    href = "\bibhref{240-connect-gem-2021}"
}
← PublicationsBack to top ↑