在 3D-space 中找到所有相邻的 cells/cubes

Question

我将 3D space 的一部分分成一系列 1x1x1 立方体，该部分的体积可能为 100^3 到 1000^3，但是，cubes/cells我真的对他们的数量很少超过 5000-20000 感兴趣。

我想要做的是找到所有满足我的标准的 cells/cubes，与所选的相邻。但是，我不确定哪种算法最适合这样的任务。我想到的第一件事是使用常规的洪水填充算法，但出现了以下问题：我必须存储有关工作区域中所有单元格的信息，正如我所说，它可能有多达 1000^3 个元素，但是我需要的只有5000-20000。

所以说我的问题是：

如果我应该使用flood fill，是否有任何数据结构可以用于我的情况？
如果我不应该使用洪水填充，我应该怎么办？

Answer 1

我认为这应该可以说明我对如何解决您的问题的想法。完成初始处理后，您还可以考虑将 set 转移到 vector（尽管严格来说这两种结构在完全迭代分摊速度方面是相似的）

set<pair<int, int> > getAllPointsToProcess(const pair<int, int>& initialCell) {
    set<pair<int, int> > activatedCells; // these will be returned
    queue<pair<int, int> > toProcess;
    toProcess.push(initialCell);
    activatedCells.insert(initialCell);
    int adjacentOffsets[][] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    pair<int, int> currentlyProcessed;
    int neighbourCell;
    while (!toProcess.empty()) {
        currentlyProcessed = toProcess.front();
        toProcess.pop();
        for (int i = 0; i < 4; i++) {
             neighbourCell.first = currentlyProcessed.first + adjacentOffsets[i][0];
             neighbourCell.second = currentlyProcessed.second + adjacentOffsets[i][1];
             if (isActive(neighbourCell) && activatedCells.find(neighbourCell) == activatedCells.end()) {
                 toProcess.push(neighbourCell);
                 activatedCells.insert(neighbourCell);
             }
        }
    return activatedCells;
}

Answer 2

正如您所指出的，Flood-Fill 算法 似乎与此相关problem.The 您面临的问题是存储信息关于所有立方体，无论它们是否被访问过与否。

您有两个选择：

为每个立方体保留哈希，Space： O(1000^3) 时间 : O(1) : 你不想要的
维护已访问多维数据集的列表，Space : O(10000) Time : O( 10000²) : 每次你需要检查这个立方体是否被访问时，只需遍历访问过的立方体的完整列表。

这只是space时间权衡。

P.S：希望我能正确解决您的问题！

Answer 3

我将尝试重新表述需求：您想为每个单元格存储一些数据（bool visited），并且对于大多数单元格来说，它是相同的（也没有被访问过），因此您想节省一些内存。

最近听说了 OpenVDB：http://www.openvdb.org/documentation/doxygen/

我没用过，但它看起来符合要求 - 它存储稀疏的体积数据，并声称内存和时间效率很高。

在 3D-space 中找到所有相邻的 cells/cubes

Find all of adjacent cells/cubes in 3D-space

c++

algorithm

search

flood-fill