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

user_1165750 0
Viewed 114

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.

language-agnostic geometry algorithm
2 Answers

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.

user_21446690

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.

user_13123820
Related