1
$\begingroup$

I originally posted this over at stackoverflow and they suggested asking it over here.

link to original: https://stackoverflow.com/questions/5222781/calculating-perpendicular-and-angular-distance-between-line-segments-in-3d

Text of original:

I am working on implementing a clustering algorithm in C++. Specifically, this algorithm: http://www.cs.uiuc.edu/~hanj/pdf/sigmod07_jglee.pdf

At one point in the algorithm (sec 3.2 p4-5), I am to calculate perpendicular and angular distance (d┴ and dθ) between two line segments: $p_1$ to $p_2$, $p_1$ to $p_3$.

It has been a while since I had a math class, I am kinda shaky on what these actually are conceptually and how to calculate them. Can anyone help?


It looks like I can calculate the perpendicular distance by the following $\left(\frac{d_1^3 + d_2^3}{d1^2 + d2^2}\right)$, where d1 is the euclidean distance between the starting points and d2 is the euclidean distance between the ending points. How would I calculate euclidean distances though?

The angular distance looks to be calculated by the dot product of the vectors. It has been about $10$ years since linear algebra so I am very rusty on this but I think I can get a handle on this one hopefully. Just a bit unsure of how to conceptually transfer line segments to vectors.

Anyway, any help you all could offer would be greatly appreciated.

2 Answers 2

2

How are you defining the distance between two segments? It appears the two segments share an endpoint, so the distance would normally be zero. Then if you take the two vectors $\vec {v_1}= \overrightarrow{p_2-p_1}$ and $\vec {v_2}= \overrightarrow{p_3-p_1}$, you have $\cos(\theta)=\frac{\vec {v_1}\cdot \vec {v_2}}{|\vec {v_1}||\vec {v_2}|}$ where $\theta$ is the angle between them.

  • 0
    for the perpendicular distance, d_|_ . e.g. (d1^3+d2^3)/(d1^2+d2^2) also, when you say RdTheta and Rcos(theta)dPhi, what is d here?2011-03-09
1

I finally clicked through to the paper and found the definitions of distances you are referring to. The hard part is finding the points $p_s$ and $p_e$ in figure 5. If you parameterize segment 1 as $s_i+t(e_i-s_i)$ we can find the distance from $s_j$ to a point and minimize over $t$. The distance squared is $d^2=\sum(s_j-s_i-t(e_i-s_i))^2$ note: sign before $t$ changed to -, does not affect the following. where the sum is over the various components. If we take the derivative with respect to $t$ and set to zero we find $t=\frac{\sum(s_j-s_i)(e_i-s_i)}{\sum(e_i-s_i)^2}$. Plugging this $t$ into $s_i+t(e_i-s_i)$ gives the point $p_s$. A similar expression using $e_j$ instead of $s_j$ gives the value of $t$ for $p_e$. Now you can calculate all the distances using the usual sum of squares technique.

Added: so imagine $s_i=(1,2), e_i=(5,4), s_j=(2,1)$ If you plot them, you will see that $p_s=(1.4,2.2)$. The calculation would be $t=\frac{(2-1)(5-1)+(4-2)(1-2)}{(5-1)^2+(4-2)^2}=0.1$, so $p_s$ lies 0.1 of the way from $s_i$ to $e_i$ and is at $(1.4,2.2)$. Similarly, if $e_j$ is at $(2,5)$, $t=\frac{(2-1)(5-1)+(5-2)(1-2)}{(5-1)^2+(4-2)^2}=0.5$ and $e_j=(3,3)$.

Then we can say $l_{||1}=\sqrt{(1.4-1)^2+(2.2-2)^2}=.447$

$l_{||2}=\sqrt{(3-1)^2+(3-2)^2}=2.236$

$l_{\bot1}=\sqrt{(2-1.4)^2+(1-2.2)^2}=1.34$

$l_{\bot2}=\sqrt{(3-5)^2+(3-4)^2}=2.236$

$L_j=4, d_\theta=l_{\bot2}-l_{\bot1}=0.896$

If you have three coordinates all these sums of two things become three. From here you should be able to follow the equations in the article.

  • 0
    Yes, I would do it immediately.2011-03-30