how to know if two lines are intersected ?

my input is (a,b,c,d,e,f,g,h,i,j,k,l)

(a,b,c) are first point ,( d,e,f )are second point

(g,,h,i)first vector , (j,k,l) second vector

how can i check if they are intersected

[John D'Errico]

Are you saying you have two lines in three dimensions? (If so, first, NEVER do this sort of thing by defining a dozen different variables. LEARN TO USE VECTORS AND MATRICES.)

Anyway, with probability measure 1, they do not intersect. Do you have one of the rare cases, where almost by construction, you have two intersecting lines, and you want to know if that is the case? Note that here, you will still need to understand how to use linear algebra/ computational geometry and how to work with tolerances. Because all you can say is they two lines intersect to within some tolerance.

But is that your question?

[mariem elkholy]

yes it is

+it is a function whose 1 output + if i want to vectorize it, will it be for example : function x=intersect(a,b,c,d) ?

Answer 1

[John D'Errico]

Just find the point where the lines are at their closest approach. If the point of closest approach is zero, they intersect.

Given two lines, defined by a point in R^3 and a vector that points in some direction. So we have a line defined as the locus of points

f(t) = a + va*t

and a second line defined as

g(s) = b + vb*s

Here ta and tb are parameters that allow you to define both lines parametrically. I'll createe some random vectors as an example.

a = rand(3,1)
b = rand(3,1)
va = rand(3,1)
vb = rand(3,1)

a =
      0.20949
      0.23808
      0.37665
b =
      0.83398
      0.82809
      0.80802
va =
      0.43283
      0.60998
      0.36585
vb =
      0.96745
      0.79764
      0.33452

What is the minimum distance between the lines? The easiest way to do this is using a linear regression. That is, solve for the parameters t and s, that minimizes the sum of squares of the residuals to the problem

va*t - vb*s = a - b

In MATLAB, we can solve that as:

ts = [va,-vb] \ (b - a)
ts =
      0.66662
      -0.3171

Can I convince you this does minimize the distance between the lines? Effectively you are solving for the pair of line parameters that results in the point of closest approach. t and s enter into the problem linearly, so we can use a linear regression to solve this, and that is what the backslash usage there does in MATLAB. So next, I'll show that fminsearch does compute the same result. That does not mean I want or recommend you should use fminsearch to do this! I am just showing you that what I wrote does work.

f = @(t) a + va*t;
g = @(s) b + vb*s;

D = @(ts) norm(f(ts(1)) - g(ts(2)));

D(ts)
ans =
     0.11097
     
[tsmin,fval] = fminsearch(D,[1 1])
tsmin =
      0.66665     -0.31708
fval =
     0.11097

So the optimizer gives the same result. The point is, the simple solution is to use

ts = [va,-vb] \ (b - a);

to solve for the closest point of approach. If that point of closest approach has a distance of zero, to within some tolerance of your choice, then they intersect, at least as far as you are concerned.

If the distance between the lines is non-zero, then they NEVER intersect, since we have found the point of closest approach. Here, we can see the two points where the lines lie at their points of closest approach. As I said, they are not the same, or even close.

f(ts(1))
ans =
      0.49803
       0.6447
      0.62053
      
g(ts(2))
ans =
       0.5272
      0.57517
      0.70194

Having said all that, are there cases where this code will fail? Under what circumstances is there a problem? The most obvious is the case when the lines are parallel. Do two parallel lines ever intersect? Never so, UNLESS the lines are coincident.

I'll leave a and b as the same random vectors they were before, but now set va and vb equal. What happens?

vb = va;
      
ts = [va,-vb] \ (b - a)
Warning: Rank deficient, rank = 1, tol =  5.546402e-16. 
 
ts =
       1.1367
            0

MATLAB gets upset. It gave a warning. telling us there is a problem.

f = @(t) a + va*t;
>> g = @(s) b + vb*s;
>> f(ts(1))
ans =
      0.70148
      0.93142
       0.7925
>> g(ts(2))
ans =
      0.83398
      0.82809
      0.80802

There are infinitely many pairs of points along those two lines that have the SAME distance. So even though we got a solution with a warning attached, the warning just told the lines were numerically parallel. MATLAB was unhappy because the solution is not unique. So understanding the problem we are solving allows us to understand the source of the warning message, to diagnose if this is an issue or not.

[David Goodmanson]

The algorithm in the answer is good the vast majority of the time, but it's interesting to take a look at what happens when the two lines are almost exactly parallel.

format long                       % case 1
a = [0 0 0]';
b = [1 1 0]';
va = [0 0 1]';
vb = [1e-15 0 1]';

ts = [va,-vb] \ (b - a)
f = @(t) a + va*t;
g = @(s) b + vb*s;
D1 = norm(f(ts(1)) - g(ts(2)))

The answer here should be 1, but

   D1 = 1.004916182175344      (method 1)

Looking at the solution coefficents,

  ts = 1.0e+14 *
        -9.007199254740993
        -9.007199254740993

so this situation, as is often the case, arises from subtracting two very large numbers to get a small result.

A second method utilizes the vector that is perpendicular to va and vb:

nab = null([va vb]'); 
D2 = norm((a-b)'*nab)
   D2 = 1                       (method 2)

That's good, but it's not like method 2 is immune to problems either.

a = [0 0 0]';                 % case 2
b = [1 0 0]';
va = [0 0 1]';
vb = [8e-12 -6e-12 1]';
  D1 = 0.600000000001327      (method 1)
  D2 = 0.599997836605097      (method 2)

Here the answer should be 0.6. Neither method is perfect, but method 1 is certainly a lot better than method 2.

All this suggests using an improved set of basis vectors in place of va and vb.

va = va/norm(va);
vb = vb/norm(vb);
u1 = va+vb;
u1 = u1/norm(u1);
u2 = va-vb;
u2 = u2/norm(u2);

u1 and u2 are perpendicular and provide a very efficient basis. The near-singular issue goes away.

  D1 = 1
  D2 = 1
  D1 =  0.600000000000000
  D2 =  0.600000000000000

And this basis is good for pretty much every set of nonparallel lines that can be described in double precision. I believe it is the best basis for this problem.