Dakwamine

Étiquette : vector

  • Unity3D.tips[2]: Intersection point between two lines in 2D

    The code

    The maths behind

    To get the point where two lines intersect, we will do some maths. To the mathematicians who will come across this post, I’m truly sorry for the heart attacks or strokes you may experience by reading this post.

    Ok, let’s take a look on the figure:

    Study case. We can see two lines crossing in an 2D Euclidian space.
    Figure 1

    First, sorry, I was too lazy to make a proper figure using computer tools so I just put a scan. XD

    Next, here are the definitions:

    • AA & BB: the two lines,
    • A1A_1, B1B_1: the arbitrary starting points of the two lines,
    • A2A_2, B2B_2: the arbitrary points which tells the direction of the two lines,
    • XX: the intersection point,
    • OO: the origin point.

    Kewl. Now, what we want is the intersection point XX between those two lines. In other words, we want to know the position which starts from either lines’ arbitrary starting point, added by the direction of the line multiplied by a scalar value. So in our figure 1, the XX position is:

    • the A1A_1 position added by the components of A1A2→\overrightarrow{A_1A_2} multiplied by an unknown which I named λ\lambda
    • the B1B_1 position added by the components of B1B2→\overrightarrow{B_1B_2} multiplied by an unknown which I named μ\mu

    In this case, it is clear that λ=μ=0.5\lambda = \mu = 0.5 so it will be easy to check if our final formula is correct. 🙂

    At the point of intersection, we know that:

    OX→=OA1→+λ×A1A2→andOX→=OB1→+μ×B1B2→\begin{array}{rcl} \overrightarrow{OX} = \overrightarrow{OA_1} + \lambda\times\overrightarrow{A_1A_2} & and & \overrightarrow{OX} = \overrightarrow{OB_1} + \mu\times\overrightarrow{B_1B_2} \end{array}

    … which gives us:

    OA1→+λ×A1A2→=OB1→+μ×B1B2→OA1→−OB1→=μ×B1B2→−λ×A1A2→\begin{array}{rcl} \overrightarrow{OA_1} + \lambda\times\overrightarrow{A_1A_2} & = & \overrightarrow{OB_1} + \mu\times\overrightarrow{B_1B_2} \\ \overrightarrow{OA_1} – \overrightarrow{OB_1} & = & \mu\times\overrightarrow{B_1B_2} – \lambda\times\overrightarrow{A_1A_2} \end{array}

    But we can’t use this statement exactly like this to solve our equation as we cannot multiply and divide vectors in this raw format. Also we need to reduce the unkowns count to 1. So we will separate our equation into two equations with the magic of matrices (which I don’t understand well at the moment), one for the x component and one for the y:

    {OA1→x−OB1→x=μ×B1B2→x−λ×A1A2→xOA1→y−OB1→y=μ×B1B2→y−λ×A1A2→y\left\{\begin{array}{c}\overrightarrow{OA_1}_x – \overrightarrow{OB_1}_x = \mu\times\overrightarrow{B_1B_2}_x – \lambda\times\overrightarrow{A_1A_2}_x \\ \overrightarrow{OA_1}_y – \overrightarrow{OB_1}_y = \mu\times\overrightarrow{B_1B_2}_y – \lambda\times\overrightarrow{A_1A_2}_y \end{array}\right.

    To make our equation more readable, we will use some shorthands:

    Aα=A1A2→,Bα=B1B2→,C=OA1→−OB1→\begin{array}{r}A_\alpha = \overrightarrow{A_1A_2}, & B_\alpha = \overrightarrow{B_1B_2}, & C = \overrightarrow{OA_1} – \overrightarrow{OB_1}\end{array}

    … so:

    {Cx=μBαx−λAαxCy=μBαy−λAαy\left\{\begin{array}{c} C_x = \mu B_{\alpha x} – \lambda A_{\alpha x} \\ C_y = \mu B_{\alpha y} – \lambda A_{\alpha y} \end{array}\right.

    From this point, we can reduce the unknown count. In my case, I have chosen to keep μ\mu instead of λ\lambda:

    {CxAαy=μBαxAαy−λAαxAαyCyAαx=μBαyAαx−λAαyAαx\left\{\begin{array}{c} C_x A_{\alpha y} = \mu B_{\alpha x} A_{\alpha y} – \lambda A_{\alpha x} A_{\alpha y} \\ C_y A_{\alpha x} = \mu B_{\alpha y} A_{\alpha x} – \lambda A_{\alpha y} A_{\alpha x} \end{array}\right.
    CxAαy−CyAαx=μBαxAαy−λAαxAαy−(μBαyAαx−λAαyAαx)CxAαy−CyAαx=μBαxAαy−λAαxAαy−μBαyAαx+λAαyAαxCxAαy−CyAαx=μBαxAαy−μBαyAαxCxAαy−CyAαx=μ(BαxAαy−BαyAαx)μ=CxAαy−CyAαxBαxAαy−BαyAαx\begin{array}{rcl} C_x A_{\alpha y} – C_y A_{\alpha x} & = & \mu B_{\alpha x} A_{\alpha y} – \lambda A_{\alpha x} A_{\alpha y} – (\mu B_{\alpha y} A_{\alpha x} – \lambda A_{\alpha y} A_{\alpha x}) \\ C_x A_{\alpha y} – C_y A_{\alpha x} & = & \mu B_{\alpha x} A_{\alpha y} – \lambda A_{\alpha x} A_{\alpha y} – \mu B_{\alpha y} A_{\alpha x} + \lambda A_{\alpha y} A_{\alpha x} \\ C_x A_{\alpha y} – C_y A_{\alpha x} & = & \mu B_{\alpha x} A_{\alpha y} – \mu B_{\alpha y} A_{\alpha x} \\ C_x A_{\alpha y} – C_y A_{\alpha x} & = & \mu (B_{\alpha x} A_{\alpha y} – B_{\alpha y} A_{\alpha x}) \\ \mu & = & \frac{C_x A_{\alpha y} – C_y A_{\alpha x}}{B_{\alpha x} A_{\alpha y} – B_{\alpha y} A_{\alpha x}} \end{array}

    And finally, you have to check if BαxAαy−BαyAαx=0B_{\alpha x} A_{\alpha y} – B_{\alpha y} A_{\alpha x} = 0. This will happen if your two lines are parallel or if there is one line defined as a point such as A1=A2A_1 = A_2 or B1=B2B_1 = B_2; no solution exists in those cases.

    Test 1

    Kewl! Now let’s try it with the Figure 1:

    μ=(1−1)×1−(2−4)×22×1−(−3)×2μ=48=0.5\begin{array}{rcl} \mu & = & \frac{(1 – 1) \times 1 – (2 – 4) \times 2}{2 \times 1 – (-3) \times 2} \\ \mu & = & \frac{4}{8} = 0.5 \end{array}

    We can get the XX position:

    {OX→x=OB1→x+Bαx×μ=1+2×0.5=2OX→y=OB1→y+Bαy×μ=4+(−3)×0.5=2.5\left\{\begin{array}{l} \overrightarrow{OX}_x = \overrightarrow{OB_1}_x + B_{\alpha x} \times \mu = 1 + 2 \times 0.5 = 2 \\ \overrightarrow{OX}_y = \overrightarrow{OB_1}_y + B_{\alpha y} \times \mu = 4 + (-3) \times 0.5 = 2.5 \end{array}\right.

    Test 2

    Ok done! Now let’s try with another figure:

    Study case 2. We can see two lines crossing in an 2D Euclidian space.
    Figure 2
    μ=((−2)−2)×(−1)−((−2)−(−3))×0(−1.5)×(−1)−1.5×0μ=41.5≈2.666\begin{array}{rcl} \mu & = & \frac{((-2) – 2) \times (-1) – ((-2) – (-3)) \times 0}{(-1.5) \times (-1) – 1.5 \times 0} \\ \mu & = & \frac{4}{1.5} \approx 2.666 \end{array}

    We can get the XX position:

    {OX→x=OB1→x+Bαx×μ=2+(−1.5)×2.666=−2OX→y=OB1→y+Bαy×μ=(−3)+1.5×2.666=1\left\{\begin{array}{l} \overrightarrow{OX}_x = \overrightarrow{OB_1}_x + B_{\alpha x} \times \mu = 2 + (-1.5) \times 2.666 = -2 \\ \overrightarrow{OX}_y = \overrightarrow{OB_1}_y + B_{\alpha y} \times \mu = (-3) + 1.5 \times 2.666 = 1 \end{array}\right.