提问人：alextgordon 提问时间：2/23/2022 最后编辑：alextgordon 更新时间：2/23/2022 访问量：284
测试二维网格上的两条线段是否相邻的算法
Algorithm to test if two line segments on a 2d grid are adjacent
问：
给定 2D 网格上的两条线段（水平或垂直），如何确定它们是否相邻？
如果 A 和 B 中至少存在一对相邻的点，则两条线段 A、B 相邻。(ax, ay)(bx, by)
如果两个点在水平或垂直方向上相邻，则它们相邻。对角线不计算在内。
可以假设线段不相交，长度为 >= 1。
显然，一个幼稚的解决方案是遍历这些点并检查邻接关系，但我正在寻找一个恒定时间的封闭式解决方案。
例如，这些线段是相邻的：
B
AB
AB
AB
B
就像这些一样
A
ABBB
A
但这些都不是（注意空格）
BBB
A
A
A
二维网格上的水平或垂直线段可以表示为元组，其中是指示线长度的布尔值。或者，这样的线段可以表示为 其中 x0 = x1 或 y0 = y1。(x, y, length, vertical)vertical(x0, y0, x1, y1)
答：
0赞
Aconcagua
2/23/2022
#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
只要数一数这些方程中有多少个适用，如果正好有两个等式适用（不可能更多......），那么矩形只在一对角相交，因此线条只是对角线相邻。
3赞
David Eisenstat
2/23/2022
#2
我们可以将这个问题简化为计算两个轴对齐矩形之间的曼哈顿距离。
关键的观察结果是维度是可分离的，具体来说，曼哈顿距离是 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。
上一个：查找最长相邻重复非重叠子字符串
下一个：矩形范围内的点
评论