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.

CodePudding user response：

as you already know #1,#2 then lets focus on #3 I would start with:

1. mark border voxels

   so any voxel equal to 1 set to 2 if its neigbors any voxel with 0. After this 0 is empty space, 1 is interior, 2 is surface.

2. find any surface voxel (2) and use it as start position

3. use A* to fill the surface from start position

   so set all direct neighbors equal to 2 of start position to 3, then their neigbors to 4 and so on until whole surface is filled with surface distance from start position.

4. find all local maximums on surface

   so find all surface voxels that are bigger than all of its neighbors and count them into some variable for example n

Now if the object is just some blob without holes there should be single local maximum n=1 somewhere opposite to start position. However if there are holes The A* filling should produce more local maximums n>1 as going around hole has bigger length so its filling will hit already filled parts more than once.

I did not test this, so in order to make this work you might be probably have to adjust the algo a bit, like add smoothing filter before processing, or consider also "lines" as local maximum instead of just singular voxels.

CodePudding user response：

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):

CodePudding user response：

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.