CODEWITHSUNDEEP
c++arraysmultithreadingrecursionmultidimensional-array
Tradition
Tradition

Reputation: 80

C++ Mark for contiguous sections in a 3D array of objects

If we have a 3x3x3 array of objects, which contain two members: a boolean, and an integer; can anyone suggest an efficient way of marking this array in to contiguous chunks, based on the boolean value. For example, if we picture it as a Rubix cube, and a middle slice was missing (everything on 1,x,x == false), could we mark the two outer slices as separate groups, by way of a unique group identifier on the int member.

The same needs to apply if the "slice" goes through 90 degrees, leaving an L shape and a strip.

Could it be done with very large 3D arrays using recursion? Could it be threaded.

I've hit the ground typing a few times so far but have ended up in a few dead ends and stack overflows.

Very grateful for any help, thanks.

Upvotes: 2

Views: 138

Answers (2)

Baltram
Baltram

Reputation: 681

It could be done that way:

struct A {int m_i; bool m_b;};
enum {ELimit = 3};
int neighbour_offsets_positive[3] = {1, ELimit, ELimit*ELimit};

A cube[ELimit][ELimit][ELimit];
A * first = &cube[0][0][0];
A * last = &cube[ELimit-1][ELimit-1][ELimit-1];

// Init 'cube'.
for(A * it = first; it <= last; ++it)
    it->m_i = 0, it->m_b = true;

// Slice.
for(int i = 0; i != ELimit; ++i)
    for(int j = 0; j != ELimit; ++j)
        cube[1][i][j].m_b = false;

// Assign unique ids to coherent parts.
int id = 0;
for(A * it = first; it <= last; ++it)
{
    if (it->m_b == false)
        continue;
    if (it->m_i == 0)
        it->m_i = ++id;
    for (int k = 0; k != 3; ++k)
    {
        A * neighbour = it + neighbour_offsets_positive[k];
        if (neighbour <= last)
            if (neighbour->m_b == true)
                neighbour->m_i = it->m_i;
    }
}

Upvotes: 1

Armen Tsirunyan
Armen Tsirunyan

Reputation: 132974

If I understand the term "contiguous chunk" correctly, i.e the maximal set of all those array elements for which there is a path from each vertex to all other vertices and they all share the same boolean value, then this is a problem of finding connected components in a graph which can be done with a simple DFS. Imagine that each array element is a vertex, and two vertices are connected if and only if 1) they share the same boolean value 2) they differ only by one coordinate and that difference is 1 by absolute value (i.e. they are adjacent)

Upvotes: 0

Related Questions