Re: [Algorithms] 3d Lines Intersection

[<ro...@do...>]

Steve Wood  wrote:

>> -----Original Message-----
>> From: ro...@do... [mailto:ro...@do...]
>> 
>[snip]
>> 
>
>What if we test by projecting against the yz plane? Using your example:
>
>The projection of line1 on the yz plane is the point (0,0,0)
>The projection of line 2 on the yz plane is the line z = y+1
>There is no intersection.
>

Exactly.  I constructed the counterexample that way so that it would
be plain as the nose on your face that there is no intersection.  It
doesn't change the fact that it is a counterexample to the algorithm
as stated. 

Another counter example in which the non-intersection is not quite as
plain.

Line 1 :
Parametric (s, s, 0)
Implicit    y = x, z=0

Line2 :  (same as before)
Parametric (0,t, t+1)
Implicit   z = y+1, x=0

Projections on xy plane:
Line 1  y= x , z=0
Line 2 x=0, z = 0, i.e, the y axis
Intersection (0,0,0)

Projections on xz plane
Line 1 z=0, y=0  i.e. the x axis
Line 2  x=0 y=0 i.e the z axis,
Intersection (0,0,0)

So the putative algorithm says that the lines intersect at (0,0,0)
when in fact they still don't intersect anywhere (an exercise for the
reader),

In this counterexample the projections onto the yz plane do intersect
at  (0,-1, 0), so it is a little harder for you to show
non-intersection.  

This suggests that  maybe one could try modify the suggested algorithm
to involve comparing the x coordinates of the intersections of the xy
and xz projections AND comparing the y coordinates of the
intersections of the xy and yz projections AND comparing the z
coordinates of the intersections of the xz and yz projections. I do
think you'd have to do all three projection directions to unravel all
the special cases, as when two lines project onto the same line (which
can happen when they intersect and also when they don't intersect).  

And then of course, you will never get exact equality in ANY of the
tests due to rounding errors and the fact that lines in space hardly
ever intersect anyway, but  the algorithm does not give a clue how to
estimate the distance of closest approach of the lines in space  from
the differences in the respective x, y, and z coordinates of the
intersections of the various projections.    For example, for the
algorithm as originally stated, I can construct a counter example
where x1 and x2 are pretty damned close but the lines in space miss by
a mile.  

No, the whole project would be a pretty big and expensive mess
compared to just solving the simple 2x2 system that I showed how to
derive in two different ways based on elementary mathematics, and
which is based directly on measuring the distance of closest approach.
(Of course it, too, has special cases to deal with as well. I think
that the only case where the 2x2 system fails to have a unique
solution is the case that it has infinitely many solutions, which is
the case that the two lines are parallel and so have infinitely many
mutual perpendiculars, so infinitely many pairs of nearest points, all
at the same distance, and this special case is immediately detectable
in the solution of the simple 2x2 system).