문제 설명
2D 그리드의 두 선분이 인접하는지 테스트하는 알고리즘 (Algorithm to test if two line segments on a 2d grid are adjacent)
2D 그리드(가로 또는 세로)에 두 개의 선분이 주어졌을 때 인접해 있는지 어떻게 알 수 있나요?
두 개의 선분 A, B는 한 쌍 이상의 점이 있는 경우 인접합니다. A의 (ax,y)와 B의 (bx, by)는 인접합니다.
두 점이 인접하면 인접합니다. 수평 또는 수직 방향. 대각선은 계산하지 않습니다.
선분은 교차하지 않고 길이는 >= 1이라고 가정할 수 있습니다.
분명히 순진한 솔루션은 점을 순환하는 것입니다. 인접성을 확인하지만 일정한 시간에 닫힌 형식 솔루션을 찾고 있습니다.
예를 들어 다음 선분은 인접합니다.
B
AB
AB
AB
B
이것과 같이
A
ABBB
A
그러나 이들은 아닙니다(공백에 주의).
BBB
A
A
A
2차원 그리드의 가로 또는 세로 선 세그먼트는 튜플 (x, y, length, vertical) 여기서 vertical은 줄의 길이를 나타내는 부울입니다. 또는 이러한 선분은 x0 = x1 또는 y0 = y1인 (x0, y0, x1, y1)로 나타낼 수 있습니다.
참조 솔루션
방법 1:
We can reduce this problem to computing the Manhattan distance between two axis‑aligned rectangles.
The key observation is that the dimensions are separable, specifically, the Manhattan distance is the Manhattan distance of the x intervals (in 1D) plus the Manhattan distance of the y intervals.
The Manhattan distance between 1D intervals [a, b] and [c, d] is max(max(a, c) − min(b, d), 0).
The overall test is max(max(x0, x0′) − min(x1, x1′), 0) + max(max(y0, y0′) − min(y1, y1′), 0) = 1.
방법 2:
For any line the line itself and its adjacent (including diagonally) points form a rectangle as e.g.:
++++++ +++
+‑‑‑‑+ +|+
++++++ +|+
+++
For a line (x0, y0, x1, y1) this rectangle is defined by the coordinates (x0 ‑ 1, y0 ‑ 1, x1 + 1, y1 + 1), let's name them (X0, Y0, X1, Y1). You now just need to check if these rectangles intersect:
A:X0 <= B:X1 and B:X0 <= A:X1
and A:Y0 <= B:Y1 and B:Y0 <= A:Y1
This yet includes diagonal adjacency, though, so you need to check this case explicitly:
A:X0 == B:X1
A:X1 == B:X0
A:Y0 == B:Y1
A:Y1 == B:Y0
Just count how many of these equations apply, if exactly two of do so (more is not possible...), then the rectangles only intersect in a pair of corners, thus the lines are only diagonally adjacent.
(by alextgordon、David Eisenstat、Aconcagua)