Compute average distance from point to line segment and line segment to line segment

Question

I'm searching for an algorithm to calculate the average distance between a point and a line segment in 3D. So given two points A(x1, y1, z1) and B(x2, y2, z2) that represent line segment AB, and a third point C(x3, y3, z3), what is the average distance between each point on AB to point C?

I'm also interested in the average distance between two line segments. So given segment AB and CD, what is the average distance from each point on AB to the closest point on CD?

I haven't had any luck with the web searches I've tried, so any suggestions would be appreciated.

Thanks.

Answer 1

First, the distance between two points is the square root of the sum of the squares of the pairwise differences of the coordinates. (For example, the distance from (0,0,0) to (1,1,1) is sqrt(3) but this works for arbitrary points in any number of dimensions.) This distance is known as the l2-norm (lower-case L) or Euclidean norm. Write norm(A,B) for the distance between points A and B.

On to the interesting problem of average distances... (Note that finding the minimum distance from a point to a line or between line segments is a much more common problem. There was an answer here with good pointers for that problem but it seems it was deleted in the meantime.)

To find the average distance from a point C to a line segment AB, consider the distance to an arbitrary point between A and B, namely (1-k)A+kB where k ranges from 0 to 1. That's norm(C, (1-k)A+kB). So the average distance is the integral from k = 0 to 1 of norm(C, (1-k)A+kB).

Mathematica can do that integral for any specific A, B, and C.

Here's a Mathematica implementation:

avgd[A_,B_,C_] :=  Integrate[Sqrt@Dot[(1-k)*A+k*B-C, (1-k)*A+k*B-C], {k, 0, 1}]

The integrand can also be written Norm[(1-k)*A+k*B-C]. Either way, Mathematica can do it for specific points but can't integrate it symbolically, though apparently David got it to do so somehow. Here's David's example from the comments:

> avgd[{0, 0, 0}, {4, 0, 0}, {4, 3, 0}] // N

3.73594

For the problem of the average distance between two line segments, in theory I think this should work:

avgd[A_,B_,C_,D_] := Integrate[Norm[(1-k)A+k*B - (1-j)C - j*D], {k,0,1}, {j,0,1}]

But Mathematica seems to choke on that even for specific points, let alone symbolically.

Answer 2

If you mean what I think you mean by "average" (and "distance," i.e. the L2 norm mentioned by dreeves), here's a procedure that I think should work for finding the average distance between a point and a line segment. You'll need a function dot(A,B) which takes the dot product of two vectors.

// given vectors (points) A, B, C
K1 = dot(A-C,A-C)
K2 = 2*dot(B-A,A-C)
K3 = dot(B-A,B-A)
L1 = sqrt(K3*(K1+K2+K3))
L2 = sqrt(K3*K1)
N = 4*K3*L1 + 2*K2*(L1-L2) + (K2*K2-4*K1*K3)*log((K2+2*L2)/(2*K3+K2+2*L1))
D = N / (8*K3^1.5)

Assuming I've transcribed everything correctly, D will then be the average distance.

This is basically just pseudocode for evaluating the result of an integral that I did in Mathematica. There may be some neat computational shortcut for this but if there is, I don't know it. (And unless there is one, I'd question how much you really need to do this computation)

If you want to find the average distance from the closest point on a line segment CD to all points on AB, in most cases the closest point will be either C or D so you can just check both of those to see which is closer (probably using some minimum-distance calculation as referenced in other answers). The only exception is when CD and AB are parallel and you could run a perpendicular from one to the other, in which case you'd have to define your requirements more precisely.

If you wanted to find the average distance between all points on CD and all points on AB... it could be done with a double integral, though I shudder to think how complicated the resulting formula would be.