高效识别连通单元格/体素

Question

我正在尝试确定测试两个单元格/体素是否连接的最有效方法。为了简单起见，我将讨论二维空间中的问题，并考虑图表中的单元格/体素。现在，我只想把问题限制在垂直轴上，并称其为y轴。

每个单元格的左下角是它的坐标，并且它始终是正整数（如果这有帮助的话）。A和B的y轴边界可以写成：

A.y1 = 4 A.y2 = 8 B.y1 = 7 B.y2 = 8

那么，检查A和B在y轴上是否相连/重叠的最有效方法是什么呢？请注意，如果你在图表中切换A和B标签，它也应该能正常工作。

以下是我的天真尝试...

IF B.x2 == A.x1
    IF (A.y1 <= B.y1) AND (A.y2 >= B.y2) THEN
        connected = true
    ELSE 
    IF (A.y1 >= B.y1) AND (A.y2 <= B.y2) THEN
        connected = true
    ELSE 
        connected = false
    END
END

- AlexS

---

你正在进行近8-9次比较和6次内存访问。如果你能够计算出每个正方形中心之间的距离，那么你只需要（r=sqrt(dxdx+dydy+dz*dz)）<=连接长度，就可以完成6次内存访问、3次乘法、1个特殊函数和1次比较。如果你使用重量级算法，则速度更快，但如果你使用轻量级算法，则速度更快且比较次数更少。 - huseyin tugrul buyukisik

@Svalorzen 我可以假设每个体素的坐标都是中心，没问题。单元格/体素始终是正方形/立方体。单元格/体素永远不会部分重叠。 - AlexS

也许k-d树会有用。 - masoud

@huseyintugrulbuyukisik，我不明白你的话怎么能成为一个解决方案，请详细说明一下？ - AlexS

两个正方形之间的最大距离为r1+r2，其中r1为第一个正方形的对角线的一半，r2为第二个正方形的对角线的一半。因此，距离必须小于r1+r2，因为两个正方形之间不能有空隙，因为它们被放置在其他矩形区域中，所以您不需要使用O(NN)进行搜索，只需使用O(Nlog(N))进行搜索。 - huseyin tugrul buyukisik

Answer 1

你可以分析盒子在轴上的投影如何相互交叉（类似于@coproc的答案）。但是这次要计算每个交点的“向量”大小，然后检查是否全部为非负数。然后，要检查仅角接触，您可以要求至少有一个这样的长度为正数。例如，使用类似于以下结构的内容（我已经重新排列了边界框结构以获得清晰度）：

typedef int axis_t; // some signed type
struct range { axis_t low, high; };
struct box { range x, y; }

axis_t overlap(const range &a, const range &b)
{
  return min(a.high, b.high) - max(a.low, b.low);
}

bool overlap(const box &a, const box &b)
{
  axis_t x_overlap = overlap(a.x, b.x);
  axis_t y_overlap = overlap(a.y, b.y);
  return x_overlap >= 0 && y_overlap >= 0 && x_overlap + y_overlap > 0;
}

这里涉及到7次比较和3次加减运算，但是需要考虑8个值，所以情况可能并不糟糕。

- NonNumeric

Answer 2

假设您所说的“连接”是指“共享非平凡边界”，那么我会这样考虑：如果两个字段共享两个不同的点，则它们之间存在连接。如果您坚持使用矩形字段，则只需检查每个单元格的角落，看看是否至少有两个八个角落在两个集合中都存在。为了使用这种方法解析平面划分成表示连接字段的图形，您还可以使用此方法来检查是否应插入边缘（假设这是您的最终目标），但您可能应该考虑一些排序方式，以便在单元格数量上不会得到二次方数量的比较。

- G. Bach

Answer 3

仅通过几何检查，您就接近最优。

在二维空间中，您需要进行4次比较才能确定哪些边缘对是相邻的（如果有的话）。如果找到相邻性，则需要检测2D重叠的存在或不存在。您正在使用<=和>=进行两个包含检查来完成此操作。您不会做得更好。如果真实答案比错误答案更可能出现，则首先检查一个端点是否严格包含在另一条边缘中可能是值得的。如果所有这些测试都失败了，逻辑必须落入到一个最终检查相同边缘的检查中。（如果错误答案很常见，则此额外检查会使方法更加昂贵。）

如果您为每个节点添加“深度”编号，则可以提高效率。这将快速告诉您哪个单元格更大，或者它们是否大小相等，从而使您只需进行两个包含检查之一。单个深度比较将避免进行多个边缘坐标比较。

最后，如果您在节点中放置父指针，则可以通过查找到达最近公共祖先的路径来进行此比较。这些路径可以进行测试以获得答案。但是，由于找到并测试它们不太可能比您已经拥有的数值比较更快，因此我不会进一步介绍。

- Gene

Answer 4

依据我的看法，你的代码是最好的。

它最多需要6次比较。

很抱歉，查找半径/距离/重叠需要更多的计算。

一个替代方案是缓存。 如果在存储每个框坐标时缓存相邻节点， 以后您只需查找B是否在A的相邻列表中，比较次数更少。建立初始缓存是开销，但以后的性能可能会更好。

否则，我没有看到更好的方法。

- bjskishore123