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

Question

Hi everyone,

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.

Answer 3

Well, if analysis fails, reach for a computer and do a silly amount of calculation until you get a feel for the numbers ...

I too have a copy of Mathematica. To keep things simple, since a triangle must lie in a plane, I've worked the following in 2D space. To keep things extra simple, I specify a point at {0,0} and a line segment from {1,0} to {0,1}. The average distance from point to line must be, if it is meaningful, the average length of all the lines which could be drawn from {0.0} to anywhere on the line segment. Of course, there are an awful lot of such lines, so let's start with, say, 10. In Mathematica this might be computed as

Mean[Table[EuclideanDistance[{0, 0}, {1 - k, 0 + k}], {k, 0, 1, 10.0^-1}]]]

which gives 0.830255. The next step is obvious, make the number of lines I measure larger. In fact, let's make a table of averages as the exponent of 10.0 gets smaller (they're negative !). In Mathematica:

Table[Mean[Table[EuclideanDistance[{0, 0}, {1 - k, 0 + k}], {k, 0, 1, 
10.0^-i}]], {i, 0, 6}]

which produces:

{1, 0.830255, 0.813494, 0.811801, 0.811631, 0.811615, 0.811613}

Following this approach I re-worked @Dave's example (forget the third dimension):

Table[Mean[Table[EuclideanDistance[{0, 0}, {4, 0 + 3 k}], {k, 0, 1, 
10.0^-i}]], {i, 0, 6}]

which gives:

{9/2, 4.36354, 4.34991, 4.34854, 4.34841, 4.34839, 4.34839}

This does not agree with what @dreeves says @Dave's algorithm computes.

EDIT: OK, so I've wasted some more time on this. For the simple example I used in the first place, that is with a point at {0,0} and a line segment extending from {0,1} to {1,0} I define a function in Mathematica (as ever), like this:

fun2[k_] := EuclideanDistance[{0, 0}, {0 + k, 1 - k}]

Now, this is integratable. Mathematica gives:

   In[13]:= Integrate[fun2[k], {k, 0, 1}]

   Out[13]= 1/4 (2 + Sqrt[2] ArcSinh[1])

Or, if you'd rather have numbers, this:

In[14]:= NIntegrate[fun2[k], {k, 0, 1}]
Out[14]= 0.811613

which is what the purely numerical approach I took earlier gives.

I'm now going to get back to work, and leave it to you all to generalise this to an arbitrary triangle defined by a point and the end-points of a line segment.