Re: Distance point <=> straight line in space

• From: Daniel Kraft <d@xxxxxxxx>
• Date: Thu, 31 Jul 2008 17:57:56 +0200

Bartc wrote:
"Daniel Kraft" <d@xxxxxxxx> wrote in message news:g6qck5\$evf\$1@xxxxxxxxxxxxxxxxxxxxxxxx
Hi,

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))

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?

Doing this 10,000 times shouldn't take any time at all. So you must be repeating the whole thing, presumably with a different set of points and/or a different line to measure to.

You're perfectly right, in fact those are some millions, I realise (it takes about 2 seconds right now)... 10000 was just a number I chose without much thinking to emphasize the fact that some precalculation can reasonably help.

And, you might want to take a closer look at the generated code (only because I don't trust optimisers myself).

Yes, I've looked at gcc's optimized tree-dump and the code really looks good; I'm using C++ expression templates to get the vector-operations inlined.

Daniel

--
Done: Arc-Bar-Sam-Val-Wiz, Dwa-Elf-Gno-Hum-Orc, Law-Neu-Cha, Fem-Mal
Underway: Cav-Dwa-Law-Fem
To go: Cav-Hea-Kni-Mon-Pri-Ran-Rog-Tou
.