Find lines segment portions close together

Question

I have two lines segment in 3D space. Lines segment are defined by 2 points each: $A_1$, $B_1$ and $A_2$, $B_2$ (see left part in the below schema).

I would a like to find an algorithm to detect which portion of the line segment 1 has a distance less than or equal to $x$ to the line segment 2 (and the opposite). The expected result of the algorithm is represented by the red lines in the schema:

Could you please provide me some tips & tricks? I do not know where to start. Thank you.

Answer 1

Here is a derivation that shows how to solve this problem, using a bit of vector arithmetic.

You can project a point $P$ onto the line $A_1B_1$ using vector arithmetic; in particular, the projection of $P$ is $${(B_1-A_1)^\top (P-A_1) \over \|B_1-A_1\|_2} (B_1-A_1) + A_1,$$ so the vector measuring the orthogonal distance from $A_1B_1$ to $P$ is

$$D=P-{(B_1-A_1)^\top (P-A_1) \over \|B_1-A_1\|_2} (B_1-A_1) - A_1.$$

Every point $P$ on the line segment $A_2B_2$ has the form $P=\alpha A_2 + (1-\alpha)B_2$, for some $\alpha \in [0,1]$. So, we can write $D$ in the form

$$ \begin{align*} D=\;&\alpha A_2 + (1-\alpha)B_2 - A_1\\ &- {(B_1-A_1)^\top (\alpha A_2 + (1-\alpha)B_2-A_1) \over \|B_1-A_1\|_2} (B_1-A_1). \end{align*} $$

Notice that this is a linear function of $\alpha$, when $A_1,B_1,A_2,B_2$ are fixed.

Let the $x,y$-coordinates of $D$ be $x_D,y_D$, i.e., $D=(x_D,y_D)$. The above equation implies that there are constants $a_0,a_1,a_2,a_3$ such that

$$x_D=a_0 \alpha + a_1, y_D = a_2 \alpha + a_3.$$

The $a_0,\dots,a_3$ depend only on $A_1,A_2,B_1,B_2$ (but not on $\alpha$) and can be readily computed using the formula above.

Now we want this vector $D$ to be of length at most $\tau$, i.e., $\|D\|_2 \le \tau$. In other words, we want

$$x_D^2 + y_D^2 \le \tau.$$

This is equivalent to

$$(a_0 \alpha + a_1)^2 + (a_2 \alpha + a_3)^2 \le \tau.$$

That is a quadratic in the unknown $\alpha$, so we can readily find the range of $\alpha$ where this inequality holds by using the quadratic formula (basically, find the roots of the quadratic equation $(a_0 \alpha + a_1)^2 + (a_2 \alpha + a_3)^2 = \tau$, and these are the endpoints of that range, except that you should clamp to the range $[0,1]$). Say that the inequality holds for $\alpha$ in the range $[\alpha_\ell,\alpha_u]$. Then it follows that the points on the line segment $A_3B_3$ are all of distance at most $\tau$ to the line $A_1B_1$, where $A_3 = \alpha_\ell A_2 + (1-\alpha_\ell) B_2$ and $B_3 = \alpha_u A_2 + (1-\alpha_u) B_2$.

This solves your question of how to find all points on the line segment $A_2B_2$ that are distance at most $\tau$ from $A_1B_1$. You can repeat the same procedure a second time to find all points on the line segment $A_1B_1$ that are distance at most $\tau$ from $A_2B_2$.

Answer 2

Here's a way to think of the 2D problem:

I'm focusing on the part of $\overline{AB}$ that is distance $\leq x$ from $\overline{CD}$. First draw a right triangle on $\overline{CD}$ whose leg has length $x$. As a comment pointed out, the shortest distance from a point to a line is given by the perpendicular. Then everything shaded in red has distance $\leq x$. By rotating the triangle $180^\circ$ you get the same red portion on the other side.

How can you express your answer? One way is to say "everything on line $\overline{AB}$ distance $d$ from the intersection, where $d = \|EF\|$ in the picture. Here is where coordinates enter: distance $d = \frac{x}{\sin \theta}$ and you can express the angle $\theta$ in terms of $A,B,C,D$ using the vectors $\vec{AB}$ and $\vec{CD}$.

As a comment: if you want to locate the relevant portion of $\overline{CD}$ that is distance $\leq x$ from $\overline{AB}$, you could repeat the analysis with the roles of $\overline{AB}, \overline{CD}$ switched, or better yet, observe that the reflection about the angle bisector takes one line to the other, and preserves distances. This means that the red portions you would draw on both lines have the same length.

Extending to 3D: if the two lines are intersecting then the above analysis goes through unchanged. If the lines are skew, well, first you may have the empty set if $x$ is too small. Here it helps to know that skew lines belong to parallel planes. The answer, if it is nonempty, is going to be some part of the line equidistant from the intersection of the projection. This can be expressed in terms of the relevant angles without much extra difficulty.