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

.

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

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

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