在三维空间中找到所有相邻的单元格/立方体

Question

我把一个3D空间的一部分分割成一系列的1x1x1立方体，这个部分的体积可能是100^3到1000^3，然而，我真正感兴趣的立方体/细胞的数量很少超过5000到20000。

我要做的是找到所有符合我的标准的单元格/立方体，与选择的单元/立方体相邻。然而，我不知道哪种算法最适合这样的任务。我想到的第一件事是使用常规的洪水填充算法，但是出现了以下问题:我必须存储工作区域中所有单元的信息，正如我所说的，这些单元可能有1000^3个元素，但我只需要5000-20000个元素。

所以我的问题是：

1. 如果我应该使用洪水填埋场，是否有任何数据结构可以用于我的情况？
2. 如果我不应该使用洪水填充物，我应该怎么做？

Answer 1

我将尝试重新定义需要:您希望为每个单元存储一些数据(bool访问)，而对于大多数单元格，它将是相同的(也不会访问)，因此您希望节省一些内存。

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

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

Answer 2

我认为这应该能说明我对你如何解决问题的想法。您还可以考虑在完成初始处理后将set传输到vector (尽管严格地说，这两种结构在resepct方面与完全迭代分期速度相似)。

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;
}