Re: Distance point <=> straight line in space

Ben Bacarisse wrote:
Daniel Kraft <d@xxxxxxxx> writes:

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

So this costs (I think):

* +- sqrt 3 [from p2 - q_i]
6 5 [cross product]
3 2 1 [norm]

or 9 multiplies, 10 add/subtracts and 1 square root.

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 uglier formula[1] involves pre-computing

V = (p2 - p1)/norm_squared(p2 - p1);

According to the formula on MathWorld and to my tests, this should in fact be a normalized vector, so not norm_squared here.

where norm_squared (x, y, z) is x^2 + y^2 + z^2. Then, for each
point, the distance is:

sqrt(norm_squared(Q) - (Q.V)^2) where Q = p1 - q_i;

* +- sqrt 3 [from p1 - q_i]
3 2 [norm_squared(Q)]
3 2 [dot product]
1 1 [square and subtract]
1 [sqrt]

which I make to be 7 multiplies, 8 add/subtracts and a square root.
Of course, I may have messed up the algebra.

Thanks for this suggestion, it works and gives around 20% speed-up, quite nice :)

I think I'm going to combine this with some high-level algorithmic changes (but I'll still rely heavily on this calculation to be efficient) to get the desired runtime performance.

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

If there is any reason to transform your co-ordinate system, you might
want to shift and rotate the world so that p1 and p2 are on the z-axis
(say). Then all you distances are 2D from the origin. This feels
more expensive unless there is some other payoff to changing the
co-ordinate system.

This is a nice suggestion, too; unfortunatelly in my particular case this coordinate-transformation would only be useful for the one calculation. This would be 8 multiplies, 7 add/subtracts and a square root (including not calculating the z coordinate), and thus I don't think it is worth in my case the additional complexity as compared to your formula above or may well be even worse.

Thanks again,
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: questions about the perspective projection matrix ???
    ... You *could* use Euclidean distance to sort out depth layering. ... subtract, a dot product of the result with itself, and a square root - ... monotonic distance calculated by the perspective calculation, ...
    (comp.graphics.algorithms)
  • 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)
  • Re: Elevation Calculator for Distant Object?
    ... >>ground distance from the observer to a point directly below the object. ... >>That is, as an example, suppose that I know I'm 400 miles from Los ... >>see a more general calculation. ... > earth, you could simplify this calculation enough that you might not ...
    (sci.astro.amateur)