calculating perpendicular and angular distance between line segments in 3d

I am working on implementing a clustering algorithm in C++. Specifically, this algorithm: http://www.cs.uiuc.edu/~开发者_StackOverflow中文版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: p1 to p2, p1 to p3.

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?

To get the perpendicular distance of a point Q to a line defined by two points P_1 and P_2 calculate this:

d = DOT(Q, CROSS(P_1, P_2) )/MAG(P_2 - P_1)

where DOT is the dot product, CROSS is the vector cross product, and MAG is the magnitude (sqrt(X*X+Y*Y+..))

Using Fig 5. You calculate d_1 the distance from sj to line (si->ei) and d_2 the distance from ej to the same line.

I would establish a coordinate system based on three points, two (P_1, P_2) for a line and the third Q for either the start or the end of the other line segment. The three axis of the coordinate system can be defined as such:

e = UNIT(P_2 - P_1)      // axis along the line from P_1 to P_2
k = UNIT( CROSS(e, Q) )  // axis normal to plane defined by  P_1, P_2, Q
n = UNIT( CROSS(k, e) )  // axis normal to line towards Q

where UNIT() is function to return a unit vector (with magnitude=1).

Then you can establish all your projected lengths with simple dot products. So considering the line si-ei and the point sj in Fig 5, the lengths are:

(l || 1) = DOT(e, sj-si);
(l |_ 1) = DOT(n, sj-si);
ps = si + e * (l || 1)      //projected point

And with the end of the second segment ej, new coordinate axes (e,k,n) need to be computed

(l || 2) = DOT(e, ei-ej);
(l |_ 1) = DOT(n, ej-ei);
pe = ei - e * (l || 1)      //projected point

Eventually the angle distance is

(d th)  = ATAN( ((l |_ 2)-(L |_ 1))/MAG(pe-ps) )

PS. You might want to post this at Math.SO where you can get better answers.

Look at figure 5 on page 3. It draws out what d┴ and dθ are.

EDIT: The "Lehmer mean" is defined using Lp-space conventions. So in 3 dimensions, you would use p = 3. Let's say that the (Euclidean) distance between the two start points is d1, and between the ends is d2. Then d┴(L1, L2) = (d1^3 + d2^3) / (d1^2 + d2^2).

To find the angle between two vectors, you can use their dot product. The norm (denoted ||x||) is computed like this.