Re: Distance point <=> straight line in space

Daniel Kraft <d@xxxxxxxx> writes:

Ben Bacarisse wrote:
Daniel Kraft <d@xxxxxxxx> writes:

in a program, I've got a straight line in space defined by two points
(p1 and p2) on it, and a set (~ 10000) points q_i in space. Then I
need to calculate for each of those points the distance to the
straight. At the moment I'm doing it like this:

vector g = normalized (p2 - p1) // Find normalized direction
for i = 1 to n
distance_i = norm (cross_product (p2 - q_i, g))

So this costs (I think):

* +- sqrt 3 [from p2 -
q_i]
6 5 [cross product]
3 2 1 [norm]

or 9 multiplies, 10 add/subtracts and 1 square root.

I believe this formula is fairly straight-forward (a single
cross-product and a norm); unfortunatelly, my program spents a large
amount of time (~ 95% of total runtime) in this routine and the
current duration is unacceptable.

Is there a better approach I could take to do this calculation that
requires less operations?

The uglier formula[1] involves pre-computing

V = (p2 - p1)/norm_squared(p2 - p1);

According to the formula on MathWorld and to my tests, this should in
fact be a normalized vector, so not norm_squared here.

Do check again... I am highly fallible in such matters, but I've gone
back and can't see it myself. My suggestion is formula (6) from that
page and everything there is either a vector difference or involves
|...|^2. I divided out by |x2-x1|^2 and I can't see any actual
normalisation.

Thanks for this suggestion, it works and gives around 20% speed-up,
quite nice :)

Excellent. 20% is what one would expect from saving 20% of the
operations, but it is good when practise follows theory.

--
Ben.
.