Re: Distance point <=> straight line in space

"Daniel Kraft" <d@xxxxxxxx> wrote in message
news:g6qck5$evf$1@xxxxxxxxxxxxxxxxxxxxxxxx

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? The output of gcc -O3 seems already reasonably
optimized, i.e., the cross-product and norm calculation is fully inlined.
I don't think hand-optimized inline-assembly could help here much, right?

You might find it useful to sketch out the problem and tackle it using
geometry. If you set aside the issue of dealing with lines that are [near]
vertical for the moment you should be able to demonstrate to yourself that
the distance you want is given by:

d = abs(C * (q_i_y - m * q_i_x - k))

Where:
m => is the slope of your line
k => the offset of the line as it crosses the y axis
C => cos(atan(m)) - you may need to make sure you get the quadrature
sign right!

As m, k and C are fixed for any given line, the bulk of the computation for
each point is 2 multiplications and 2 subtractions.

This falls down as the line approaches the vertical because m -> infinity
and C goes to zero. This can be easily sidestepped by switching to a
different view - effectively transposing the x-y axes (in the computations)
so it is handled like horizontal line:

d = abs(C' * (q_i_x - m' * q_i_y - k'))

Where:
m' => is the inverse slope of your line (effectively (x2-x1)/(y2-y1))
k' => the offset of the line as it crosses the x axis
C' => cos(atan(m')) - you may need to make sure you get the quadrature
sign right!

HTH
--
Stuart


.

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: Infinite 3d lattice
    ... distance from the nth face (measured along the x axis) to a point at x ... So the force from the nth face on x is going to ... So F is a cyclic function with period 1. ...
    (sci.math)
  • Re: High Speed 2, the next Great Central?
    ... Mark Goodge wrote: ... Stopping distance = 4 kms. ... Acceleration, not a straight line. ...
    (uk.railway)
  • 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)
  • 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)