Using Recursion for 3D Array Manipulation — Causin

问题:

I recently posted a question yesterday about a similar issue, but I have coded up something a little different and now have a different problem. Here is my code that is causing a StackOverflow.

** Note that the 3D grid array is upwards of 1 million elements and can reach up to around 64 million elements (stores enums).

** Also note that this is not going into infinity. On small data sets, this algorithm works fine.

Is this likely caused by the extreme recursion? How do I handle this (this is an essential part of my algorithm!)? I've done some research and have heard using a queue, for even just massive for-loops.

What will reduce the likelihood of causing a stackoverflow?

Thank you!

/**
 * Fills all void cells in the 3D grid of Atom.
 *
 * @param x
 *            The starting x coordinate
 * @param y
 *            The starting y coordinate
 * @param z
 *            The starting z coordinate
 */
private void fillAllVoidCells(int x, int y, int z)
{
    // Base case -- If not BLOATED_ATOM, BOUNDING_BOX,
    // or VOID then must be a cavity (only 4 CellType
    // enum types.
    if ((grid[x][y][z] == CellType.BLOATED_ATOM)
        || grid[x][y][z] == CellType.BOUNDING_BOX
        || grid[x][y][z] == CellType.VOID)
    {
        // Pop off runtime stack
        return;
    }
    else
    {
        // Set to void then check all surrounding cells.
        grid[x][y][z] = CellType.VOID;

        fillAllVoidCells(x + 1, y, z); // right
        fillAllVoidCells(x - 1, y, z); // left
        fillAllVoidCells(x, y + 1, z); // in front
        fillAllVoidCells(x, y - 1, z); // behind
        fillAllVoidCells(x, y, z + 1); // above
        fillAllVoidCells(x, y, z - 1); // below
    }
}

===== EDIT ====== New Method Implemented Using a Stack (per Roee Gavirel help) Would this be a correct implementation?

   // ----------------------------------------------------------
    /**
     * Fills all void cells in the 3D grid of Atom.
     *
     * @param x
     *            The starting x coordinate
     * @param y
     *            The starting y coordinate
     * @param z
     *            The starting z coordinate
     */
    private void fillAllVoidCells(int x, int y, int z)
    {
        Point p = new Point(x, y, z);

        stack.push(p);

        while (!stack.isEmpty())
            p = stack.top();
        stack.pop();

        // Base case -- If not BLOATED_ATOM, BOUNDING_BOX,
        // or VOID then must be a cavity (only 4 CellType
        // enum types.
        CellType state = grid[p.x][p.y][p.z];

        if ((state == CellType.BLOATED_ATOM) || state == CellType.BOUNDING_BOX
            || state == CellType.VOID)
        {
            return;
        }
        else
        {
            // Set to void then check all surrounding cells.
            grid[p.x][p.y][p.z] = CellType.VOID;
            Point tempP = p;

            tempP.x = p.x - 1;
            stack.push(tempP);
            tempP.x = p.x + 1;
            stack.push(tempP);
            tempP.x = p.x; // return to original x coordinate

            tempP.y = p.y - 1;
            stack.push(tempP);
            tempP.y = p.y + 1;
            stack.push(tempP);
            tempP.y = p.y; // return to original y coordiante

            tempP.z = p.z - 1;
            stack.push(tempP);
            tempP.z = p.z + 1;
            stack.push(tempP);
            tempP.z = p.z; // return to original z coordinate
        }
    }

回答1:

This is most likely to cause an overflow. what you can (and should) do to avoid it is to use your own stack for the data and avoid recursion.

In you case:
1. have a stack of relevant points (x,y,z) which have the point you initially called fillAllVoidCells with.
2. while the stack is not empty you should do your checks
3. If it's cavity add the surrounding points to the stack.

==EDIT== something like that:

struct point {
    int x,y,z;
}

private void fillAllVoidCells(int x, int y, int z)
{
    std::list<point> Ps;
    point p;
    p.x = x;
    p.y = y;
    p.z = z;
    Ps.push_back(p);

    while (!Ps.empty())
        p = Ps.back();
        Ps.pop_back();

        // Base case -- If not BLOATED_ATOM, BOUNDING_BOX,
        // or VOID then must be a cavity (only 4 CellType
        // enum types.
        auto state = grid[p.x][p.y][p.z];
        if ((state == CellType.BLOATED_ATOM)
            || state == CellType.BOUNDING_BOX
            || state == CellType.VOID)
        {
            continue;
        }
        else
        {
            // Set to void then check all surrounding cells.
            grid[p.x][p.y][p.z] = CellType.VOID;

            point tempP = p;
            tempP.x = P.x - 1;    
            Ps.push_back(tempP);
            tempP.x = P.x + 1;    
            Ps.push_back(tempP);
            tempP.y = P.y - 1;    
            Ps.push_back(tempP);
            tempP.y = P.y + 1;    
            Ps.push_back(tempP);
            tempP.z = P.z - 1;    
            Ps.push_back(tempP);
            tempP.z = P.z + 1;    
            Ps.push_back(tempP);
        }
    }
}