c++ - 有效地识别连接的细胞\体素

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

Answer 1

您可以分析框在轴上的投影如何相互交叉(类似于@coproc 的回答)。但是这次计算每个交叉点的“vector ”大小，然后检查是否所有交叉点都是非负的。然后检查角落只接触你可以要求至少有一个这样的长度是积极的。例如，像这样(为了清楚起见，我重新排列了边界框结构):

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 个值需要考虑，所以可能还不错。