What is the algorithm to determine whether a cluster of 3D voxels is a donut shape?

Question

I will start off with some background for this problem. It is an extension of several easier problems. Strangely the final extension leads to it being almost impossible to solve.

1. Given a matrix of integers with 1s, and 0s. 1s representing land and 0s representing ocean count the amount of islands in the matrix which is clusters of 1s separated from each other.

2. Extend the above problem to donuts. Given the same thing as above only count donuts. That means clusters of 1s with one or more holes of "water" or 0s in it. There can be donuts within donuts.

3. Extend the above problem to 3D. When you extend the problem above to 3D it becomes hard enough that I will move the question away from "counting donuts" and more towards "is donut?" So in other words, instead of counting clusters of 1s, now you are told that in this 3D grid space there is one and only one cluster of voxels. That cluster is either a donut or it is not a donut. Which means it has a hole (or several holes) going through it or it does not. Write an algorithm to identify this.

Each question is a more challenging extension of the other. With (1.) being the simplest and (3.) being the hardest.

The first 2 questions are quite straight forward. 1. is a classic interview question. (2.) is an extension of that; simply color all separate bodies of water via flood fill with a separate "color" (aka number) and all "islands" touching 2 or more colors is a donut (the hole touches one body of water, and the outside touches a different body of water).

However the 3rd question is challenging. I cannot come up with a way. My coworkers at 2 jobs... nobody could find a way. So I post it here. The isDonut algorithm question.

from typing import List
#3D_space is gaunteed to have one and only one cluster of pixels in it. 
def isDonut(3d_space: List[List[List[int]]]) -> bool:
    #implement this code

There are many solutions that seem correct but actually fail under specific circumstances. Be careful if you decide to answer.

Edit: For clarity I will define what a voxel donut is:

The above is a voxel donut. A cluster of voxels with a hole going through it. I can only define it in high level english terms. You know it when you see it.

A formal definition of what this is in terms of voxels is the solution to this problem and is described in terms of a programming algorithm. I therefore am unable to describe it, as it's basically my question. Essentially you can think of this question as isomorphic to this one: "what is the formal definition of a voxel donut"?

Edit 2: I'm getting some vague answers and people using advanced math that are hard to understand. Let me put it this way. If you have a straightforward answer you should be able to finish off that python function signature above. You do that the answer is correct, whether or not anyone fully understands your reasoning.

Answer 1

Consider the boundary of your shape: that is, all faces that lie between a filled voxel and an empty one.

Let V be the number of vertices on the boundary, E the number of edges on the boundary, and F the number of faces on the boundary. These are easy to compute; just be careful not to count edges & vertices that belong to multiple boundary faces more than once.

A shape is a donut if and only if (1) the boundary faces are connected, and (2) V-E+F=0.

For more information on this strange and magical second condition, see Euler characteristic.

Answer 2

Edit: This definition does not work. See Rawling's comment below.

Here is an attempt to define a donut, first in a continuous world, through a few observations:

A convex set cannot be a donut. Let S be potential donut, and let conv(S) be the convex hull of S. We define the hole to be H := S \ conv(S). Then S is a donut if H has exactly two disjoint contact surfaces with R^3 \ conv(S). (See below for definitions of "conv()" and "".)

Now, in a discrete voxel world. We can do pretty much the same, except that there are some ambiguities. However, since "donut" is rather informal, they can be resolved according to your personal preferences.

We first need to compute conv(S). There are multiple valid answers here. For example, voxels that partially intersect the continuous conv(S) could be considered part or not part of the discrete convex hull. The construction of H is straightforward, and so are the contact surfaces. The second ambiguity concerns the two disjoint surfaces, specifically what constitutes contiguous voxel faces. A restrictive definition would count 12 neighbors for each voxel face (must have a cube edge in common). But this can be extended to many more if adjacent cube vertices are considered enough.

Note that here I considered that if H is shaped like a Y, then S is not a donut. But this could be up for discussion too.

Disclaimer: not a topologist, my vocabulary may be off. Links to definitions:

Convex hull conv(S): https://en.wikipedia.org/wiki/Convex_hull

S \ conv(S): "set complement" / "Boolean subtraction": https://en.wikipedia.org/wiki/Complement_(set_theory)#Relative_complement / https://en.wikipedia.org/wiki/Constructive_solid_geometry

Edit: Here is an illustration. Yellow: donut. Blue: convex hull. Green: hole. Red: surfaces. Generated with https://evanw.github.io/csg.js/