Re: Distance point <=> straight line in space
- From: Daniel Kraft <d@xxxxxxxx>
- Date: Thu, 31 Jul 2008 17:57:56 +0200
"Daniel Kraft" <d@xxxxxxxx> wrote in message news:g6qck5$evf$1@xxxxxxxxxxxxxxxxxxxxxxxxHi,
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.
Done: Arc-Bar-Sam-Val-Wiz, Dwa-Elf-Gno-Hum-Orc, Law-Neu-Cha, Fem-Mal
To go: Cav-Hea-Kni-Mon-Pri-Ran-Rog-Tou