OT: Recreational puzzle

Hi all.

Suppose we have two straight lines in 3D space. The lines
are parameterized on the form

   L = P + tV

where P is a point on the line, V is a vector parallel with the
line and t is a scalar.

Computing the intersection between those lines is a bit tedious
when using pen and paper, but not particularly difficult.

How would you find the intersection of the lines in 3D space
(not 2D, that's trivial) using a computer?

Rune

Rune Allnor schreef:
> Hi all.
> 
> Suppose we have two straight lines in 3D space. The lines
> are parameterized on the form
> 
>    L = P + tV
> 
> where P is a point on the line, V is a vector parallel with the
> line and t is a scalar.
> 
> Computing the intersection between those lines is a bit tedious
> when using pen and paper, but not particularly difficult.
> 
> How would you find the intersection of the lines in 3D space
> (not 2D, that's trivial) using a computer?
> 
> Rune
> 

line 1: L1 = P1 + t1*V1
line 2: L2 = P2 + t2*V2

At the intersection we have
P1 + t1*V1 = P2 + t2*V2
t1*V1 - t2*V2 = P2 - P1

This is an overdetermined system of equations, and thus does not 
necessarily have a solution (2 lines in 3D space do not always intersect).
Solving this system of equations applies to M-D linear structures in N-D 
space (M<N):
- solve the system of the first min( 2*M,N ) equations (2 equations in 
this case)
- check the solution for the possibly remaining max( 0,N-2*M ) equations 
(1 equation in this case); if the solution is not correct for all these 
equations, there is no intersection.

-- John

Rune Allnor wrote:
> Hi all.
> 
> Suppose we have two straight lines in 3D space. The lines
> are parameterized on the form
> 
>    L = P + tV
> 
> where P is a point on the line, V is a vector parallel with the
> line and t is a scalar.
> 
> Computing the intersection between those lines is a bit tedious
> when using pen and paper, but not particularly difficult.
> 
> How would you find the intersection of the lines in 3D space
> (not 2D, that's trivial) using a computer?

It's a rare pair of lines in space that intersect, as rare as those that 
are parallel. If you enumerate intersecting lines isomorphically with 
the rational numbers, then the skew lines are isomorphic to the reals.

Pick a pair of lines; any pair. What do you bet that they intersect? If 
the lines are chosen at random, that's a sucker bet at any odds.

Jerry
-- 
Engineering is the art of making what you want from things you can get.
�����������������������������������������������������������������������

Jerry Avins wrote:
> Rune Allnor wrote:
> > Hi all.
> >
> > Suppose we have two straight lines in 3D space. The lines
> > are parameterized on the form
> >
> >    L = P + tV
> >
> > where P is a point on the line, V is a vector parallel with the
> > line and t is a scalar.
> >
> > Computing the intersection between those lines is a bit tedious
> > when using pen and paper, but not particularly difficult.
> >
> > How would you find the intersection of the lines in 3D space
> > (not 2D, that's trivial) using a computer?
>
> It's a rare pair of lines in space that intersect, as rare as those that
> are parallel.

Maybe rare, but useful. I faced this problem when I tried to visualize
and process triangulated bathymetry maps. My thoughts went along
the lines of Linear Programming. John's explanation is a lot simpler
to understand. I am not sure if what he describes indeed is LP, though.


Rune

Rune Allnor wrote:
> Hi all.
>
> Suppose we have two straight lines in 3D space. The lines
> are parameterized on the form
>
>    L = P + tV
>
> where P is a point on the line, V is a vector parallel with the
> line and t is a scalar.
>
> Computing the intersection between those lines is a bit tedious
> when using pen and paper, but not particularly difficult.
>
> How would you find the intersection of the lines in 3D space
> (not 2D, that's trivial) using a computer?
>
> Rune

How about this...

Let

Line 1: L1 = P1 + t1*V1
Line 2: L2 = P2 + t2*V2

The problem can be formulated by finding the nearest distance between
the two lines. If the two lines intersect, this distance would be zero.
Defining the objective as

J = | L1 - L2 |^2

the solution is obtained by minimizing J. Rearranging the objective, we
have

J = | (P1 + t1*V1) - (P2 + t2*V2) |^2
J = | (P1 - P2) + (t1*V1 - t2*V2) |^2
J = | A + Bu |^2

where A = P1-P2 is a N-dim vector, B = [V1 -V2] is a Nx2 matrix and u =
[t1 t2]^T is a 2-dim vector with the unknowns.

Then, setting the gradient dJ/du to zero, we have

B^T (A + Bu) = 0
u = (B^T B)^-1 B^T A

(B^T B)^-1 denotes an inverse of a 2x2 matrix which should not be too
difficult to achieve computationally.

Alan

Rune Allnor wrote:

(snip)

> How would you find the intersection of the lines in 3D space
> (not 2D, that's trivial) using a computer?

This reminds me of a problem being discussed in a class I visited
while deciding which college to go to.  (one I didn't go to.)

It had to do with computing the derivative at a point, given
a curve in parametric form.  That is, x(t) and y(t), find
dy/dx given x and y.  The problem is easy to answer, but it
seems that the curve didn't go through the given x and y!

-- glen

glen herrmannsfeldt wrote:
> Rune Allnor wrote:
>
> (snip)
>
> > How would you find the intersection of the lines in 3D space
> > (not 2D, that's trivial) using a computer?
>
> This reminds me of a problem being discussed in a class I visited
> while deciding which college to go to.  (one I didn't go to.)
>
> It had to do with computing the derivative at a point, given
> a curve in parametric form.  That is, x(t) and y(t), find
> dy/dx given x and y.  The problem is easy to answer, but it
> seems that the curve didn't go through the given x and y!

With a couple of experiences like that, a person can make that
check before he even attempts to invoke the full machinery
of whatever solution method he chooses to use.

I was a bit surprised to find out what a computational problem
this "trivial" exercise posed, from a computer programmer's
point of view. The lines can intersect, or they can cross. They
can be colinear, that is, every point on L1 also belongs to L2,
or they can be parallel.

All of these situations show up differently in the equations,
which the computer has to handle robustly.

A very interesting excersise. 

Rune

Alan Tan wrote:
>
> How about this...
>
> Let
>
> Line 1: L1 = P1 + t1*V1
> Line 2: L2 = P2 + t2*V2
>
> The problem can be formulated by finding the nearest distance between
> the two lines. ...

which always exists.

> ... If the two lines intersect, this distance would be zero.
...

i'm putting my vote behind Alan's solution.  there could conceivably be
a numerical problem that the minimum distance is calculated to be of
the order of 10^(-20) or some teeny number and you might have to put in
a threshold to declare that as zero and where the lines intersect.

we did something like this in 3rd semester Calculus class, some 30
years ago.  The book was Robert Seeley.  it's pretty straight forward
if you express P1, P2, V1, and V2 in terms of their 3 vector components
and then express the (possible) intersection, L1=L2, as 3 real
equations with 2 unknowns (t1, t2).

r b-j

On 13 Aug 2006 12:03:13 -0700, "robert bristow-johnson"
<rbj@audioimagination.com> wrote:

>
>Alan Tan wrote:
>>
>> How about this...
>>
>> Let
>>
>> Line 1: L1 = P1 + t1*V1
>> Line 2: L2 = P2 + t2*V2
>>
>> The problem can be formulated by finding the nearest distance between
>> the two lines. ...
>
>which always exists.
>
>> ... If the two lines intersect, this distance would be zero.
>...
>
>i'm putting my vote behind Alan's solution.  there could conceivably be
>a numerical problem that the minimum distance is calculated to be of
>the order of 10^(-20) or some teeny number and you might have to put in
>a threshold to declare that as zero and where the lines intersect.
>
>we did something like this in 3rd semester Calculus class, some 30
>years ago.  The book was Robert Seeley.  it's pretty straight forward
>if you express P1, P2, V1, and V2 in terms of their 3 vector components
>and then express the (possible) intersection, L1=L2, as 3 real
>equations with 2 unknowns (t1, t2).
>
>r b-j

I like Alan's solution as well.

I was going to suggest the brute force method, which is easy to code
on a computer, i.e., just test every point in space to see whether it
is occupied by both lines.   If so, that's the coordinate of the
intersection.

It's just a few nested loops with a simple test.   Easy to code. What
could go wrong?

;)

Eric Jacobsen
Minister of Algorithms, Intel Corp.
My opinions may not be Intel's opinions.
http://www.ericjacobsen.org

Rune Allnor wrote:

> I was a bit surprised to find out what a computational problem
> this "trivial" exercise posed, from a computer programmer's
> point of view. The lines can intersect, or they can cross. They
> can be colinear, that is, every point on L1 also belongs to L2,
> or they can be parallel.
> 
> All of these situations show up differently in the equations,
> which the computer has to handle robustly.
> 
> A very interesting excersise. 

Dave Eberly has done it for intersection or distance of various 3D 
objects in his articles at
http://www.geometrictools.com/Documentation/


Martin

-- 
Quidquid latine scriptum sit, altum viditur.