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
    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)2011-03-07
  • 0
    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.2011-03-07
  • 0
    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 http://en.wikipedia.org/wiki/Spherical_coordinate_system2011-03-07
  • 0
    would the change in coordinate system effect both distance calculations or just the angular distance calculation?2011-03-08
  • 0
    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.2011-03-08
  • 0
    ok, i think i understand you here so i would calculate the vectors and then convert them over to spherical coordinates and go on from there just to clarify, the perpendicular distance wouldnt change at all?2011-03-08
  • 0
    so i read over again and you are saying, that i take the lat/lon/altitude and convert it to cartesian coordinates via the cartesian frame you mentioned above and then derive my work from there???2011-03-09
  • 0
    @basil:That's right2011-03-09
  • 0
    and i would do that when i calculate the distances for the lehmer mean and when finding the angular distance?2011-03-09
  • 0
    I don't know where the Lehmer mean came from. I looked it up on Wikipedia, but don't see where it comes into this problem.2011-03-09
  • 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
    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?2011-03-09
  • 0
    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.2011-03-09
  • 0
    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.2011-03-10
  • 0
    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)?2011-03-10
  • 0
    $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.2011-03-10
  • 0
    Okay, that was me not paying close enough attention, I apologize. Iam going to try to work this out on paper with some semi live data. I'll get back here shortly with my results and hopefully they'll be correct. Coordinates in (Latitude, Longitude, Latitude): $S_i$ = (40.23, -106.82, 358.0) $E_i$ = (40.29, -106.18, 295.0) $S_j$ = (40.26, -106.52, 339.0) $E_j$ = (40.27, -106.44, 332.0) just using lat for x, lon for y, alt for z, i get $P_s$=(40.248,-106.627,338.974) $P_e$=(40.055,-106.556,331.981) 2011-03-11
  • 0
    From that, I get $l_{||1}$ roughly equal to 6.172, $l_{||2}$ roughly equal to 26.021, and $d_{||}$ = $l_{||1}$. $l_{\bot1}$ roughly equal to .111, $l_{\bot2}$ roughly equal to 36.99, and $d{\bot}$ roughly equal to 36.99. $d_\theta = l_{\bot2} - l_{\bot1} = 36.879$ Sorry about the formatting, I am new at this. But does the above look somewhat correct?2011-03-11
  • 0
    @basil: Missed your last post when it came in. Note that by using lat,lon,alt you have very different scales in the three axes. 1 deg lat is 69 miles, 1 deg lon (at 40 deg lat) is 52.9 mi, 1 unit is alt is whatever (1 foot?) This makes the altitude dominate everything.2011-03-17
  • 0
    I get the same first two coordinates for $P_s$, but for the third I get 338.9989. This comes from t=0.301605, but for $P_e$ I get (40.25476,-106.556,332.0039) using t=0.412637. For $l_{||1}$ I get 19.002, while for $l_{||2}$ I get 37.0058. Your numbers look suspect to me because the length of segment 2 is only 7 units long, so the two $t$ values should be close. Certainly $l_{\bot1}$ and $l_{\bot2}$ should be much smaller-I get 0.10764 and 0.38441.2011-03-17
  • 0
    I apologize for missing these comments. How do I go about normalizing the lat, lon, alt?2011-03-29
  • 0
    @basil: for small differences in coordinates, you can just use the scale factors I gave: 1 degree of latitude is 69 statute miles, 1 degree of longitude is $69 \cos$ latitude statute miles, and measure altitude in miles, or convert to your favorite length units2011-03-29
  • 0
    Theoretically, I understand what you are saying. But I don't understand algorithmically how and when to implement this normalization. As this is a c++ program, would it make sense to do the calculations as soon as I read in the coordinates i.e. save the coordinates as [lat,lon,alt]=>[lat*69,69*cos(lat),alt] ?2011-03-30
  • 0
    Yes, I would do it immediately.2011-03-30