Given two line segments on a 2D grid (horizontal or vertical), how can I determine if they are adjacent?
Two line segments A, B are adjacent if there exists at least one pair of points (ax, ay) in A and (bx, by) in B that are adjacent.
Two points are adjacent if they are adjacent in the horizontal or vertical direction. Diagonals do not count.
It can be assumed that the line segments do not intersect and the length is >= 1.
Clearly a naive solution would be to loop through the points and check for adjacency but I'm looking for a closed form solution in constant time.
For example these line segments are adjacent:
B
AB
AB
AB
B
as are these
A
ABBB
A
but these are not (note the space)
BBB
A
A
A
A horizontal or vertical line segment on a 2d grid can be represented as a tuple (x, y, length, vertical) where vertical is a boolean indicating the length of the line. Alternatively, such a line segment could be represented as (x0, y0, x1, y1) where either x0 = x1 or y0 = y1.
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.