# Re: Distance point <=> straight line in space

*From*: Ben Bacarisse <ben.usenet@xxxxxxxxx>*Date*: Thu, 31 Jul 2008 12:23:14 +0100

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.

.

**Follow-Ups**:**Re: Distance point <=> straight line in space***From:*Daniel Kraft

**References**:**Distance point <=> straight line in space***From:*Daniel Kraft

**Re: Distance point <=> straight line in space***From:*Ben Bacarisse

**Re: Distance point <=> straight line in space***From:*Daniel Kraft

- Prev by Date:
**Re: Distance point <=> straight line in space** - Next by Date:
**sort algorithm** - Previous by thread:
**Re: Distance point <=> straight line in space** - Next by thread:
**Re: Distance point <=> straight line in space** - Index(es):