测试二维网格上的两条线段是否相邻的算法

Question

给定二维网格上的两条线段（水平或垂直），如何确定它们是否相邻？

如果A中至少有一对点(ax, ay)和B中的点(bx, by)相邻，则两条线段A、B相邻

如果两个点在水平或垂直方向上相邻，则它们是相邻的。对角线不算数。

可以假设线段不相交且长度>=1。

显然，一个天真的解决方案是遍历这些点并检查邻接性，但我正在寻找恒定时间内的封闭形式解决方案。

例如这些线段是相邻的：

 B
AB
AB
AB
 B

这些也是

A
ABBB
A

但这些不是（注意space）

 BBB
A
A
A

二维网格上的水平或垂直线段可以表示为元组 (x, y, length, vertical)，其中 vertical 是表示线长的布尔值。或者，这样的线段可以表示为 (x0, y0, x1, y1)，其中 x0 = x1 或 y0 = y1.

Answer 1

对于任何一条线，该线本身及其相邻（包括对角线）点形成一个矩形，例如：

++++++    +++
+----+    +|+
++++++    +|+
          +++

对于一条线 (x0, y0, x1, y1)，此矩形由坐标 (x0 - 1, y0 - 1, x1 + 1, y1 + 1) 定义，我们将它们命名为 (X0, Y0, X1, Y1)。您现在只需要检查这些矩形是否相交：

      A:X0 <= B:X1   and   B:X0 <= A:X1
and   A:Y0 <= B:Y1   and   B:Y0 <= A:Y1

不过，这还包括对角邻接，因此您需要明确检查这种情况：

A:X0 == B:X1
A:X1 == B:X0
A:Y0 == B:Y1
A:Y1 == B:Y0

数一数这些等式中有多少个适用，如果恰好有两个（不可能更多...），则矩形仅在一对角处相交，因此这些线仅在对角线上相邻。

Answer 2

我们可以将这个问题简化为计算两个 axis-aligned 矩形之间的曼哈顿距离。

关键观察是维度是可分离的，具体来说，曼哈顿距离是x区间的曼哈顿距离（一维）加上y区间的曼哈顿距离。

一维区间 [a, b] 和 [c, d] 之间的曼哈顿距离为 max(max(a, c) − min(b, d), 0)。

整体测试为max(max(x0, x0′) − min(x1, x1′), 0) + max(max(y0, y0′) − min(y1, y1′), 0) = 1.

Algorithm to test if two line segments on a 2d grid are adjacent