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.

Improve this question
$\endgroup$
2
$\begingroup$

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.

Improve this answer
$\endgroup$
11
  • $\begingroup$ well, thats the thing: they dont ALWAYS share an endpoint, just sometimes. at least, that is what i gather from the reading. i am just defining the distance between endpoints as sqrt(deltaLatitude^2 + deltaLongitude^2 + deltaAltitude^2) $\endgroup$ – basil Mar 7 '11 at 20:22
  • $\begingroup$ Normally then, you would define the distance between the segments as the smallest distance between any point on one segment and any point on the other. This is not necessarily at the endpoints. Imagine (0,-1) to (0,1) as one segment and (1,0) to (2,0) as the other. $\endgroup$ – Ross Millikan Mar 7 '11 at 20:27
  • $\begingroup$ If you are using spherical earth coordinates (as it appears) you need a different formula. Your formula doesn't even have matching units. There is some discussion at en.wikipedia.org/wiki/Spherical_coordinate_system $\endgroup$ – Ross Millikan Mar 7 '11 at 20:32
  • $\begingroup$ would the change in coordinate system effect both distance calculations or just the angular distance calculation? $\endgroup$ – basil Mar 8 '11 at 16:05
  • $\begingroup$ The angle calculation does not change, but you need to get the dot product right in your coordinates. If distances are small, a local Cartesian frame is $(h, R d\theta, R \cos(\theta) d\phi)$, where $h$ is height, $\theta$ is latitude, $\phi$ is longitude, and $R$ is the earth radius. $\endgroup$ – Ross Millikan Mar 8 '11 at 16:43
1
$\begingroup$

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.

Improve this answer
$\endgroup$
13
  • $\begingroup$ First off: apologies again for any ignorance I am showing here. I am trying my best to understand this conceptually. What are the bounds for the sigma summations above i.e. (for $p_s$) $t=\frac{\sum(s_j-s_i)(e_i-s_i)}{\sum(e_i-s_i)^2}$ and (for $p_e$) $t=\frac{\sum(e_j-s_i)(e_i-s_i)}{\sum(e_i-s_i)^2}$ ? Also, if I were to do things this way, it wouldn't matter whether I was dealing in cartesian or spherical coordinates; I should be able to get the angular distance AND perpendicular distance via sum of squares? $\endgroup$ – basil Mar 9 '11 at 20:48
  • $\begingroup$ The bounds are the number of dimensions in your space. The paper is written in great generality, so there could be 2, 3, or more. $\endgroup$ – Ross Millikan Mar 9 '11 at 22:02
  • $\begingroup$ Note that this "distance" fails one of the usual criteria for a distance function-the distance from segment a to segment b may be different than the distance from segment b to segment a. This is alleviated by always taking the longer as the reference segment, but I don't think it is even symmetric if they are the same length. $\endgroup$ – Ross Millikan Mar 10 '11 at 17:30
  • $\begingroup$ Just a quick question on your math. I am assuming you found $L_j$ by the pythagorean theorem: $(L_j)^2 = (d_\theta)^2 + (L_i)^2$ with $L_i$ being the distance from $P_s$ to $P_e$, or $\sqrt{((P_e)_x - (P_s)_x)^2 + ((P_e)_y - (P_s)_y)^2}$? In that case, shouldn't $L_j$ = 2 ($sqrt(4)$)? Or, if I am wrong, how did you find $L_j$? Would the above method work in 3 dimension (cartesian, spherical)? $\endgroup$ – basil Mar 10 '11 at 18:45
  • $\begingroup$ $L_j$ is just the distance from $s_j$ to $e_j$, so (2,1) to (2,5) is 4. I think the square root you show is $L_i$, so it would be $\sqrt{(1.4-3)^2+(2.2-3)^2}=1.789$ Yes, all this works in 3 (or more) dimensions. That is why I parameterized the line and took the derivative instead of just finding the slope and using the negative reciprocal. When we use the Pythagorean square roots to find lengths, we are selecting Cartesian coordinates. $\endgroup$ – Ross Millikan Mar 10 '11 at 19:04

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.