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@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 straightforward (a single crossproduct 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 treedump and the code really looks good; I'm using C++ expression templates to get the vectoroperations inlined.
Daniel

Done: ArcBarSamValWiz, DwaElfGnoHumOrc, LawNeuCha, FemMal
Underway: CavDwaLawFem
To go: CavHeaKniMonPriRanRogTou
.
 References:
 Distance point <=> straight line in space
 From: Daniel Kraft
 Re: Distance point <=> straight line in space
 From: Bartc
 Distance point <=> straight line in space
 Prev by Date: Re: Distance point <=> straight line in space
 Next by Date: Re: sort algorithm
 Previous by thread: Re: Distance point <=> straight line in space
 Next by thread: sort algorithm
 Index(es):
Relevant Pages
