1
$\begingroup$

I'm looking for a way to compute the coordinates of the intersection of two lines.

Each lines are defined with a point and a normal vector.

Graphic representation

We can assume than the normal vectors are not zero and that the lines are not parallel (this has been easily checked by computing the scaral product of u and v), so this intersection exists.

The coordinates of A and B are known (lets call them $(A_x,A_y)$ and $(B_x,B_y)$) as well as the vectors : $(u_x,u_y)$ and $(v_x,v_y)$.

Could you point me to a simple computer algorithm that could give me $(M_x,M_y)$ ?

I know that by hand I could do this by resolving a simple equation system, but I wonder if there is some direct way to do it on a computer.

$\endgroup$
5
$\begingroup$

I might as well add this since you haven't gotten an answer that deals with the format you have for the lines (i.e. point and normal vector). In your case, you can write the equation of each line as $$ (\vec{x}_0-\vec{x})\cdot\vec{n}=0 $$ where $\vec{x}_0$ is a point on the line. This gives $$ (A_x-x)u_x+(A_y-y)u_y=0 $$ $$ (B_x-x)v_x+(B_y-y)v_y=0 $$

The linear system can then be written in matrix form as $$ \left[ \begin{array}{cc} u_x & u_y \\ v_x & v_y \end{array} \right] \left[ \begin{array}{c} x \\ y \end{array} \right] = \left[ \begin{array}{c} A_x u_x + A_y u_y \\ B_x v_x + B_y v_y \end{array} \right] $$

This linear system can be solved easily via Gaussian elimination with pivoting for any case where the lines are not parallel (i.e. $u_x v_y - u_y v_x \ne 0$). As mentioned in the other solutions, if the lines are very nearly parallel there may be some issues with accuracy due to rounding errors in the computer.

$\endgroup$
  • $\begingroup$ Thanks for the detailled solution. Google and Wikipedia helped me to find out how to write the Gaussian elimination algorithm. $\endgroup$ – Orabîg Jan 23 '15 at 14:01
  • $\begingroup$ @Orabîg Depending on the programming language you're using there are very likely either built-in tools for solving the linear system or simple libraries for doing so. Matlab and Python would be well suited to this and you could use Matlab's \ operator or Python's Numpy.linalg.solve, reducing you entire code to just a few lines. $\endgroup$ – Doug Lipinski Jan 23 '15 at 14:22
3
$\begingroup$

To elaborate a bit, start with the ray/parametric form of the first line (0):

$\vec r_0(t) = \vec p_0 + t \cdot \vec q_0$

.. where $\vec p_0$ is some origin point known to be on the line (like your point $\vec A$), and $\vec q_0$ is the known unit vector along the line (the tangent, orthogonal to your normal $\vec u$). You can write a similar statement for the other line (1).

$\vec r_1(t) = \vec p_1 + s \cdot \vec q_1$

The intersection point is where $\vec r_0(t) = \vec r_1(s)$, write that statement down:

$\vec p_0 + t \cdot \vec q_0 = \vec p_1 + s \cdot \vec q_1$

Dot that equation with $\vec q_0$, and dot it again with $\vec q_1$ to get two scalar equations in terms of the two unknowns t and s:

$\left<\vec q_0,\vec p_0\right> + t \cdot \left<\vec q_0,\vec q_0\right> = \left<\vec q_0,\vec p_1\right> + s\cdot\left<\vec q_0,\vec q_1\right>$ $\left<\vec q_1,\vec p_0\right> + t \cdot \left<\vec q_1,\vec q_0\right> = \left<\vec q_1,\vec p_1\right> + s\cdot\left<\vec q_1,\vec q_1\right>$

Note that $\left<\vec q_0,\vec q_0\right>$ = $\left<\vec q_1,\vec q_1\right>$ = 1, since these are unit vectors. Denote $c = \left<\vec q_0,\vec q_1\right>$, it's the cosine of the angle between the two lines. Then rearrange into a 2x2 matrix equation:

[  1  -c ] [ t ] = [ <q0,p1-p0> ]
[ -c   1 ] [ s ]   [ <q1,p0-p1> ]

This matrix is nonsingular (symmetric positive definite, in fact) as long as $|c|$ is bounded away from 1, which is the parallel/antiparallel case (where there is either no intersection or infinitely many). Solve for s and t, then evaluate either $\vec r_0(t)$ or $\vec r_1(s)$ to find the intersection point explicitly.

$\endgroup$
0
$\begingroup$

Hi Orabig and welcome to scicomp! The answer to your question seems pretty straightforward... You could setup the matrix system $Ax=b$ from the equations defining the lines and solve the matrix system on a computer directly (e.g. gaussian elimination). There's nothing really tricky about it.. As long as the slopes of the two lines are not too close to each other (i.e. an ill-conditioned system), it's really that simple.

$\endgroup$
  • $\begingroup$ Thanks for your answer. I agree with you except that resolving this kind of equation doesn't seem very straightforward for me. But I guess I should take a look at the method you mentionned. $\endgroup$ – Orabîg Jan 21 '15 at 20:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.