13

Sorry about formatting, this is my first question here, and I have no idea how to do it properly.

Assuming I have two lines

$\displaystyle l_1 = \binom{x_1}{y_1} + a\binom{u_1}{v_1}$

$\displaystyle l_2 = \binom{x_2}{y_2} + b\binom{u_2}{v_2}$

Thus the intersection holds

$\displaystyle \binom{x_1}{y_1} + a\binom{u_1}{v_1} = \binom{x_2}{y_2} + b\binom{u_2}{v_2}$

and have made sure those two lines will intercept (so $u_1,v_1$ and $u_2,v_2$ aren't parallel), how do I find the intersection point elegantly?

Currently (I am using this in a C++ code), I need to do a lot of if() cases, since I cannot divide by 0, but in order to find the point, I need to substitute b in the formula

I get

$a = \dfrac{x_2-x_1+bu_2}{u_1}$

so here I have to check for $u_1\neq0$, and then substitute in the second line, where I then need to check for $v_2\neq0$, and this creates one hell a lot of code.

Is there a better way, am I just missing something easy?

Jerry
  • 884
  • 8
  • 18
SinisterMJ
  • 344

2 Answers2

19

The most elegant formulation (IMO) uses Cramer's Rule. You can reformulate your two equations into $$\begin{bmatrix} u_1 & -u_2\\ v_1 & -v_2 \end{bmatrix} \cdot \begin{bmatrix} a \\ b\end{bmatrix} = \begin{bmatrix} x_2-x_1 \\ y_2 -y_1 \end{bmatrix}$$ and use determinants to solve for $a$.

Another nice way to think about it is areas: For segments AB and CD, the fraction along AB at which the intersection occurs is equal to the area of the triangle ACD divided by the area of the quadrilateral ACBD.

Sneftel
  • 760
  • 1
    That works absolutely beautifully, and is a 3 line code!! Love this answer! – SinisterMJ May 30 '13 at 17:40
  • @SinisterMJ Could you share the three lines, as it's many years since I solved matrix equations? – fadedbee Jul 26 '22 at 20:08
  • 1
    @fadedbee do the area method, if you’re not a determinants sort of person. Code for finding the area of a triangle is readily available, and a quadrilateral is just two triangles. – Sneftel Jul 26 '22 at 20:11
  • I put in the effort to re-learn determinants and arrived at ((x1-x0)*v1 - u1*(y1-y0)) / (u0*v1 - u1*v0) after cancelling out some negatives. The subscripts are now zero-based as it's code, not maths. – fadedbee Jul 28 '22 at 18:05
  • 1
    @fadedbee what does your code do? What value does it calculate? How do you convert that value into the vector that represents the intersection point? – Alex Spurling Aug 21 '22 at 15:22
  • 1
    @AlexSpurling The formula gives you the scalar value of how far along along the line segment (x0,y0)->(x0+u0, y0+v0) the intersection happens. (I assume that this is in units of the segment length, but I haven't confirmed it as I'm using unit segments.) If the denominator is zero, there is no intersection. – fadedbee Aug 29 '22 at 10:38
1

You could use the elimination method to solve the simultaneous equations rather than the substitution method. If the two lines aren't parallel then there should be no cases when you could accidentally divide by $0$.

john
  • 5,633