1
$\begingroup$

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:

enter image description here

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

$\endgroup$
  • $\begingroup$ Can you define what you are looking for a bit better? Are you asking for segments $S1$ and $S2$ such that every point of $S1$ is at distance $\leq x$ to the closest point on $S2$ (and reciprocally)? Or are you looking for segments such that the endpoints are at distance $\leq x$? depending on how exactly you define your problem there might also not be a unique maximal solution (one solution might have a longer segment on one line while another might have a longer segment on the other line for example). $\endgroup$ – Tassle Nov 20 '19 at 20:58
  • $\begingroup$ Two lines in the same plane intersect or are parallel. $\endgroup$ – greybeard Nov 20 '19 at 21:06
1
$\begingroup$

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^2} (B_1-A_1) + A_1,$$ where $v^\top$ denotes the transpose of vector $v$, 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^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^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 would describe how to find all points on the line segment $A_2B_2$ that are distance at most $\tau$ from the line connecting $A_1$ and $B_1$. However, we really want to find all points that are distance at most $\tau$ from the line segment $A_1B_1$. So, we want to constrain the projection of $P$ to be between $A_1$ and $B_1$, i.e., we want to constrain $D$ to be between $0$ and $B_1-A_1$. By solving systems of linear equations, you can find $\alpha_0$ such that $(a_0 \alpha_0+a_1,b_0 \alpha_0+b_1)=(0,0)$ and $(a_0 \alpha_1+a_1,b_0 \alpha_1+b_1)=B_1-A_1$. Then, we replace $[\alpha_\ell,\alpha_u]$ (obtained above by the quadratic formula) with the intersection of ranges $[\alpha_\ell,\alpha_u] \cap [\alpha_0,\alpha_1]$. This gives us all points on the line segment $A_2B_2$ that are distance at most $\tau$ from the line segment $A_1B_1$.

This solves your question of how to find all points on the line segment $A_2B_2$ that are distance at most $\tau$ from the line segment $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$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I just tried these formulas in pratice and I realized they don't work well. Indeed, the projection formula from a line segment to another line segment is not correct. Indeed, this constraint must be added to the projection formula: $${(B_1-A_1)^\top (P-A_1) \over \|B_1-A_1\|_2} \in [0, 1]$$. If I'm not wrong, that complicated everything as $a_1$ and $a_3$ will now depends of $\alpha$. Is there a simple way to easily incorporate this constraint into the above formulas? $\endgroup$ – Saelhenen Nov 30 '19 at 9:19
  • $\begingroup$ @Saelhenen, good point, you are right. See edited answer (specifically, the next-to-last paragraph). Also, I had the formula for projection wrong (I forgot to square the denominator), so I've corrected that as well. Does it work now? Thank you for your patience with all of these mistakes! Sorry that I had so many errors. $\endgroup$ – D.W. Nov 30 '19 at 20:18
  • $\begingroup$ First at all: thanks to you for your help. What is the purpose of $_2$ in projection denominator ? I thought it was the square... I also try to figure out why $D$ should be between $(0, 0, 0)$ and $B_1-A_1$ to constraint the projection to line segment $A_1B_1$. I don't understand the logic. I tried in pratice and that doesn't seem to work. $\endgroup$ – Saelhenen Dec 1 '19 at 21:58
  • $\begingroup$ @Saelhenen, the notation $\|U\|_2$ refers to the $L_2$ norm of $U$, and $\|U-V\|_2$ is the $L_2 $ distance (Euclidean distance) between $U$ and $V$. In other words, if $U=(u_1,u_2)$, then $\|U\|_2 = \sqrt{u_1^2+u_2^2}$, and $\|U\|_2^2 = u_1^2 + u_2^2$. $\endgroup$ – D.W. Dec 1 '19 at 22:51
  • $\begingroup$ We want the projection onto the line segment to be between $A_1$ and $B_1$. If the projection falls on $A_1$, then $D=0$. If the projection falls on $B_1$, then $D=B_1-A_1$. If we want the projection to fall in between these two extremes, then we want $D$ to be between $0$ and $B_1-A_1$. $\endgroup$ – D.W. Dec 1 '19 at 22:53
1
$\begingroup$

Here's a way to think of the 2D problem: enter image description here

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.