Re: Distance point <=> straight line in space



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
.



Relevant Pages

  • Re: Gravity, space-time, and black holes?
    ... a train car that can move forward and backward along a straight railroad. ... We can draw the train's worldline by plotting the ... then why does the distance between them decrease at an increasing rate as ... What will actually happen to the infalling astronaut, ...
    (sci.physics)
  • Re: High Speed 2, the next Great Central?
    ... Mark Goodge wrote: ... Stopping distance = 4 kms. ... Acceleration, not a straight line. ...
    (uk.railway)
  • Re: Distance point <=> straight line in space
    ... Then I need to calculate for each of those points the distance to the straight. ... Is there a better approach I could take to do this calculation that requires less operations? ... So you must be repeating the whole thing, presumably with a different set of points and/or a different line to measure to. ...
    (comp.programming)
  • Re: The simplicity of relativity (for TomGee and others)
    ... >> the interior of a bowl, it still rolls in a straight line on the ... >> A boy sat next to a pigeon on a park bench in the city. ... >> east-west street if you like to mark the distance." ...
    (sci.physics.relativity)
  • Re: The simplicity of relativity (for TomGee and others)
    ... >> the interior of a bowl, it still rolls in a straight line on the ... >> A boy sat next to a pigeon on a park bench in the city. ... >> east-west street if you like to mark the distance." ...
    (sci.physics)