Intersection of two vector-CodePudding

I have 2 point in 3D space and one vector for each. I need to know whether that 2 vectors intersect each other. And also intersection point if it exist.

I tried to search but my english knowledge is not enough for this knd of search. If someone have a link or explanation I would really appreciate it.

CodePudding user response：

I believe you mean line, not vector. A vector is like an individual point in space, a line is an continuous set of points.

First, consider how you want to represent your lines. The way you might have tried first is using y = mx b. But this might not be the easiest thing for you to do programmatically, and it doesn't extend well to 3D.

Instead, you should use the vector representation of a line as shown.

[x, y] = [m_x, m_y]*t [b_x, b_y]

Basically what this equation is saying is that points x and y are defined as a base point that I have written as [b_x, b_y], plus some scalar multiple of some vector [m_x, m_y]. You can think of this as your slope vector, and it's being scaled by some number t. By plugging in different values of t you can get every point on the line.

We can convert from y = mx b by noting that:

b is the y-intercept. it is a point [0, b] which is our [b_x, b_y] term.
m is the slope, it's the ratio of m_y/m_x. If you have an equation where m=3 then you know that y increases 3 times faster than x. This can give us [m_x, m_y] to be [1, 3], [4, 12], or anything else just so long as m_y/m_x = m.

Now we are going to have two equations, one for each line.

(1) [x, y] = [m_x_1, m_y_1]*t   [b_x_1, b_y_1]
(2) [x, y] = [m_x_2, m_y_2]*s   [b_x_2, b_y_2]

If we set these two equations equal to each other then we can solve for s and t to figure out where the intersection is, or if one exists at all.

[m_x_1, m_y_1]*t   [b_x_1, b_y_1] = [m_x_2, m_y_2]*s   [b_x_2, b_y_2]

Next, we can represent the m*s and m*t terms as a matrix multiplication. At this stage I'm going to start drawing our vectors vertically, instead of horizontally.

|m_x_1, -m_x_2| * |s| = |b_x_2 - b_x_1|
|m_y_1, -m_y_2|   |t|   |b_y_2 - b_y_1|

Now that we have a linear equations represented by the following matrix equation. In this case, [s, t] is our x, we are trying to solve for this. The equation is telling us that we can solve for x by multiplying the Matrix Inverse of A by b.

Ax=b
x=A^-1b

You can read about the Matrix Inverse Here. Just know that a 2x2 Matrix can have it's inverse calculated as follows:

|a, b|^-1 = 1/(ad - bc) * |d,  -b|
|c, d|                    |-c,  a|

Now pay attention to the (ad-bc) term. It is a denominator, if it is zero the answer to the Matrix inverse is undefined. This would mean there is no intersection, for our line equation no intersection would look like this:

0 = m_x_1 * -m_y_2   m_x_2 * m_y_1

If it is not zero, then we can arrive at our s, t terms as follows:

[s, t] = 1/(m_x_1 * -m_y_2   m_x_2 * m_y_1) * [(b_x_1 - b_x_2), (b_y_1, b_y_2)]

Now these s and t terms will be real numbers from (-Infinity, Infinity). If you only care about Ray intersections, then you can just throw one away and keep one, I'll take s. This s gives us a point on line (1) where intersection occurs. We can plug this into our equation and get the intersection. [x, y] here is your intersection.

[x, y] = [m_x_1, m_y_1]*t   [b_x_1, b_y_1]

I don't believe I made any errors, but try extending this to 3D for yourself, the steps are the same!.

CodePudding user response：

Vectorially, you want to solve for the parameters r and s the system

P   r.U = Q   s.V

equivalent to

Px   r.Ux = Q.x   s.Vx
Py   r.Uy = Q.y   s.Vy
Pz   r.Uz = Q.z   s.Vz

(points P and Q, vectors U and V).

This is a system of 3 equations in 2 unknowns, which generally has no solution. The compatibility condition can be written

|Ux Vx Px-Qx|
|Uy Vy Py-Qy| = 0
|Uz Vz Pz-Qz|

If that condition holds*, you can solve the 2x2 system obtained by dropping one of the equations. If you want to restrict the solutions to the line segments defined by the points and vectors, check that r and s belong to [0, 1]. From r or s you can compute the position of the intersection.

*Because of floating-point issues, the condition might not hold exactly. It is out of the scope of this answer to discuss how close to 0 it should be.