I've got a question about a good way to find the quickest algorithm for my problem:

problem: I've got a 3D cubical grid containing voxels that are either 1 or 0. It is stored as a flattened array. If multiple 1-voxels are neighboring each other, they form a cluster together. I want to detect clusters smaller than a given size (n).

current solution (slow):

For each 1-voxel, I'm doing a breadth first search to find how many neighbors it has, and how many neighbors the neighbors have, etc, until reaching a certain amount of neighbors (n).

this is horribly slow when setting n to my preferred amount n>50, because the total cube edge size is 64

Any different ways to do this that are not breadth first search? Everything is open: could even be something from computer vision like 3d pooling or whatever, but I'm a little stuck. Or am I better off trying to optimize my current approach? If interested, I posted my c# code in code review

Thanks a bunch in advance!

  • 1
    $\begingroup$ I know that octrees are sometimes used for this purpose but unfortunately I am not aware of any non-industrial documents about it. $\endgroup$ Commented Mar 12, 2020 at 22:09
  • $\begingroup$ @AbdullahAliSivas sounds interesting and relevant. Will do some research and post findings here if any $\endgroup$ Commented Mar 13, 2020 at 9:54


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.