给定二维网格上的两条线段(水平或垂直),如何确定它们是否相邻?
如果 A 中至少存在一对点 (ax, ay)
和 B 中的 (bx, by)
,则两条线段 A、B 相邻相邻。
如果两个点在水平或垂直方向上相邻,则它们相邻。对角线不算数。
可以假设线段不相交且长度 >= 1。
显然,一个简单的解决方案是循环遍历这些点并检查邻接性,但我正在寻找恒定时间内的封闭形式解决方案。
例如,这些线段是相邻的:
B
AB
AB
AB
B
这些也是
A
ABBB
A
但这些不是(注意空格)
BBB
A
A
A
二维网格上的水平或垂直线段可以表示为元组(x,y,长度,垂直)
,其中vertical
是指示长度的 bool 值的线。或者,这样的线段可以表示为 (x0, y0, x1, y1)
,其中 x0 = x1 或 y0 = y1。
最佳答案
我们可以将这个问题简化为计算两个轴对齐矩形之间的曼哈顿距离。
关键的观察结果是维度是可分离的,具体来说,曼哈顿距离是 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 .
关于测试二维网格上的两条线段是否相邻的算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/71238906/