yablog: memo for my low-memory brain: calculate intersection from two lines in 2-D.

2011/08/13

memo for my low-memory brain: calculate intersection from two lines in 2-D.

ラベル: math

This is my memo for basic geometry-formula.
Now, I want to calculate intersection of two lines(Line1 and Line2).

Line1: passes point (x1=0, y1=9) and (x2=2, y2=5).
Line2: passes point (x3=1, y3=1) and (x4=3, y4=0).

Firstly, we can express these lines as following:
Line1: $(y_1 - y_2)x - (x_1 - x_2)y = (x_2y_1 - x_1y_2)$
Line2: $(y_3 - y_4)x - (x_3 - x_4)y = (x_4y_3 - x_3y_4)$

Secondly, we can get intersection (x,y) by solving below linear algebra:
$A\begin{pmatrix}x \\ y\end{pmatrix} = \begin{pmatrix}l_1 \\ l_2\end{pmatrix}$

$a_{11} = y_1 - y_2$
$a_{12} = y_3 - y_4$
$a_{21} = x_2 - x_1$
$a_{22} = x_4 - x_3$
$l_1 = (x_2y_1 - x_1y_2)$
$l_2 = (x_4y_3 - x_3y_4)$
$A = \begin{pmatrix}a_{11} & a_{12} \\ a_{21} & a_{22}\end{pmatrix}$

Finally, using inverse matrix, we can easily calculate intersection:
$A^{-1} = \frac{1}{|detA|}\begin{pmatrix}a_{22} & -a_{12} \\ -a_{21} & a_{11}\end{pmatrix} = \frac{1}{a_{11}a_{22}-a_{12}a_{21}}\begin{pmatrix}a_{22} & -a_{12} \\ -a_{21} & a_{11}\end{pmatrix}$
$\begin{pmatrix}x \\ y\end{pmatrix} = \begin{pmatrix}l_1 \\ l_2\end{pmatrix}A^{-1}$

yablog

2011/08/13

memo for my low-memory brain: calculate intersection from two lines in 2-D.

No comments:

Post a Comment

label

Archives