Find missing points in N dimensional grid

Question

I've got an N dimensional (regular) grid with data, which doesn't fill it's volume completely, but should be convex. So, for example, in 2D this is okay (1=exists, 0=missing):

0011111100
0111111110
1111111111
0011111100
0000011100

But this is not:

0011111100
0111101110
1111111111
0011111000
0000011100

I want to find the additional zeros in this second example (marked in bold). And I want to do this in more than 2 dimensions.

The only way I can think of now is to get all possible coordinates in N-1 dimensions and check in the Nth dimension, whether it's convex, which just means finding the first and last data points in that dimension and check, whether any point is missing in between. But I'd have to do that in every dimension and for every slice in that dimension.

There must be an easier solution, right?

Answer 1

You would need to figure out and understand the algorithms that help to get a "multidimensional convex hull" for a given multidimensional grid. This is bit complex and I can't explain a full blown solution in the post but can give the below pointers.

• CONVEX HULL IN 3 DIMENSIONS
• Scipy: Convex hulls in N dimensions.
• CGAL: The Computational Geometry Algorithms Library
• Newton Apple Wrapper

I doubt if an easier solution would exist for this as you are talking about multiple dimensions.

Answer 2

To easily solve this problem, consider an opposite problem: "How can one find the space surrounding a shape?"

If you know how to fill in all the space surrounding a shape, then all pixels or voxels which are not part of that empty space must be part of the convex hull. In the following example, we:

1. fill all the surrounding 0 space with -
2. replace - with 0 and 0 with 1 (results in the convex hull)
3. XOR with the original model

01110        -111-        01110        00000
11010   ->   1101-   ->   11110   ->   00100
11111        11111        11111        00000

In the final result, a 1 now represents enclosed empty space. Note that - could be represented as a 2 or 3 for this to work and we would temporarily need two bits per voxel, not just one.

To implement the first step, we simply flood-fill all 0 voxels with - for all voxels that are on the edge of the model. For each of those boundary voxels we start a separate flood-fill run. The empty space inside of the model stays unchanged, because the flood-fill doesn't reach it.

Implementing the second and third step should be trivial.

Avoiding "Troolean" Logic

It's also possible to do all of this with only boolean logic, so no third - value. To do this, we would have to:

• flood-fill zeros in the input array with 1 instead of -
• for every voxel we fill, write a 1 into a separate output buffer

The first step would then give us a result of:

10001
00001
00000

We now just need to bit-flip this buffer to get the convex hull.