4

我正在尝试确定测试两个细胞\体素是否连接的最有效方法。为简单起见，我将在二维中讨论这个问题，并考虑图中的单元格......

典型单元格排列示意图
现在我将问题限制在垂直轴上，称之为 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
4

4 回答 4

0

假设连接的意思是“共享一个重要的边界”，我会这样想：如果这些字段中的两个共享两个不同的点，则它们是连接的。如果您坚持使用矩形字段，您只需检查每个单元格的角并查看八个角中的至少两个是否在两组中。要使用这种方法将平面的分区解析为表示连接字段的图形，您还可以使用它来检查是否应该插入一条边（假设这是您的最终目标），但您可能应该考虑某种排序方式它们，这样您就不会在单元格数量上进行二次比较。

于 2013-05-19T17:30:27.937 回答
0

仅通过几何检查，您就接近最佳状态。

您需要 4 次比较（在 2d 中）来确定哪些边对（如果有）是相邻的。如果发现邻接，则需要检测是否存在 2d 重叠。您正在通过使用 <= 和 >= 的两个包含检查来执行此操作。你不会做得更好。如果正确答案比错误答案更有可能，那么首先检查一个端点是否被固定包含在另一边中可能是值得的。如果所有这些测试都失败，则逻辑必须通过最终检查相同的边。（如果错误答案很常见，这种额外的检查会使方法更加昂贵。）

如果您为每个节点添加一个“深度”数字，则可以使用效率。这将快速告诉您哪个单元格更大或者它们是否大小相等，从而允许您仅进行两项包含检查中的一项。单一深度比较将避免多次边缘坐标比较。

最后，如果您将父指针放在节点中，那么您可以通过查找到最不常见的祖先的路径来进行此比较。可以测试这些路径以获得答案。但是，由于查找和测试它们不太可能比您已经拥有的数值比较更快，因此我不会进一步讨论。

于 2013-05-19T19:47:16.583 回答
0

您可以分析框在轴上的投影如何相互交叉（类似于@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 个值需要考虑，所以可能还不错。

于 2013-05-19T22:27:49.930 回答
0

在我看来，你的代码是最好的。

它最多需要 6 次比较。

恐怕，找到半径/距离/重叠涉及更多的计算。

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

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

于 2013-05-20T04:27:31.400 回答