Re: Distance point <=> straight line in space

"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.

Have you looked globally at your code to see if all these calculations are necessary? Is every result of the 10000 used? (Perhaps you can calculate the distance on demand). If the line is constant, do any of the points repeat (so you can remember the distance)?

Are you calculating some sort of minimum or maximum distance? (Then there might be some quick way of rejecting many of the points.)

Where do the points come from? Would it be feasible to create them as vectors from the line endpoint anyway? Would it be feasible to reorientate the line and points so that the line is along the X,Y or Z axis? Then the calculation is simpler.

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

.

Relevant Pages

  • Re: Distance point <=> straight line in space
    ... Bartc wrote: ... need to calculate for each of those points the distance to the straight. ... 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: 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: My New Website
    ... I merely used the distance between adjacent atoms. ... And I explained my calculation in great detail, ... I.e. you simply choose the angles with which the arms ... If two tetrahedrons touch at one corner, i.e. one arm of each is connected ...
    (sci.physics)
  • Re: What c.l.pys opinions about Soft Exception?
    ... Which might be a useful place to use SoftExceptions ... def calculateforce: ... The problem happens when the distance is small enough and we want to ... obfuscate the code since we have to separate distance calculation from ...
    (comp.lang.python)
  • Re: A twin contraction paradox
    ... talk about two events on A's prongs and another part talks ... I will repeat a part and add a new calculation at the end. ... A measures his own prongs to be a distance L apart. ... We translate this physical statement into coordinates language now: ...
    (sci.physics.relativity)