2
$\begingroup$

I'm trying to check if a line hits a rectangle, and for that, I found this nice solution:

Line triangle intersection

The problem is that, having forgot almost all I ever knew about math, I don't know how to obtain that equation of a line which they use there: $4x − 3y + 2 = 0$

I know a line's equation is $y = mx + b$. But the above form and how can I obtain it is a mystery to me. Can somebody please bring a flashlight? ::- D.

$\endgroup$
4
  • $\begingroup$ What information do you already have about the line? $\endgroup$
    – Isaac
    Mar 5, 2011 at 19:28
  • $\begingroup$ Are you asking how we can get $ax+by+c=0$ from $y=mx+d$? In that case: Subtract $mx + d$ on both sides and get $-mx+y-d = 0$, which is the same as $ax+by+c=0$ when $a=-m,b=1,c=-d$. $\endgroup$
    – Eivind
    Mar 5, 2011 at 19:44
  • $\begingroup$ Hi Isaac ::- D. I have 2 points on the line. $\endgroup$
    – Axonn
    Mar 5, 2011 at 20:07
  • $\begingroup$ Oh, good, then I guessed right. :) $\endgroup$
    – Isaac
    Mar 5, 2011 at 20:11

3 Answers 3

4
$\begingroup$

If you know two points on the line, $(x_1,y_1)$ and $(x_2,y_2)$, then the vector $\langle x_2-x_1,y_2-y_1\rangle$ is in the direction of the line and the vector $\vec{n}=\langle y_1-y_2, x_2-x_1\rangle$ (swap the components, take the opposite of one component) is orthogonal (perpendicular) to the line. For any point $(\pmb{x},\pmb{y})$ on the line, the vector $\langle \pmb{x}-x_1,\pmb{y}-y_1\rangle=\langle \pmb{x},\pmb{y}\rangle-\langle x_1,y_1\rangle$ is in the direction of the line, so it is also orthogonal to $\vec{n}$, so its dot product with $\vec{n}$ is $0$: $$\begin{align} \vec{n}\cdot\langle \pmb{x}-x_1,\pmb{y}-y_2\rangle&=0 \\ \vec{n}\cdot\left(\langle \pmb{x},\pmb{y}\rangle-\langle x_1,y_1\rangle\right)&=0 \\ \vec{n}\cdot\langle \pmb{x},\pmb{y}\rangle-\vec{n}\cdot\langle x_1,y_1\rangle&=0 \\ \langle y_1-y_2, x_2-x_1\rangle\cdot\langle \pmb{x},\pmb{y}\rangle-\langle y_1-y_2, x_2-x_1\rangle\cdot\langle x_1,y_1\rangle&=0 \\ (y_1-y_2)\pmb{x}+(x_2-x_1)\pmb{y}-\left((y_1-y_2)x_1+(x_2-x_1)y_1\right)&=0 \\ (y_1-y_2)\pmb{x}+(x_2-x_1)\pmb{y}+\left(-(y_1-y_2)x_1-(x_2-x_1)y_1\right)&=0 \\ (y_1-y_2)\pmb{x}+(x_2-x_1)\pmb{y}+\left((y_2-y_1)x_1-(x_2-x_1)y_1\right)&=0 \end{align}$$

$\endgroup$
5
  • $\begingroup$ Hi Isaac ::- D. Thank you for your answer! I am a bit unsure about how to use the last form that you written though. It seems to have 2 points, and X / Y and no 'c' factor (4x -3y +2 ). $\endgroup$
    – Axonn
    Mar 5, 2011 at 20:14
  • 1
    $\begingroup$ The $a=y_1-y_2$ is a single number (based on the $y$-coordinates of your two known points), $b=x_2-x_1$ is a single number (based on the $x$-coordinates of your two known points, and $c=(y_1-y_2)x_1+(x_2-x_1)y_1$ is a single number using both coordinates of both known points... oh, I see, I tend to use $Ax+By=C$ rather than $Ax+By+C=0$. I'll edit my answer accordingly. In the revised form, $c=(y_2-y_1)x_1-(x_2-x_1)y_1$. $\endgroup$
    – Isaac
    Mar 5, 2011 at 20:19
  • $\begingroup$ Oh, no problem! I just got confused to who is C ::- ). Now I understood that the right hand side is C. $\endgroup$
    – Axonn
    Mar 5, 2011 at 20:23
  • $\begingroup$ Thank you again Isaac! ::- D. BTW, is this direction-independent? I suppose not, since you're talking about the vector. $\endgroup$
    – Axonn
    Mar 5, 2011 at 20:28
  • 1
    $\begingroup$ @Axonn: If by direction-independent, you mean that swapping the two known points doesn't matter, yes—the coefficients will probably all change sign, but that's equivalent to multiplying the whole equation by $-1$. $\endgroup$
    – Isaac
    Mar 5, 2011 at 20:36
2
$\begingroup$

You can transform the given equation to make it explicit in $y$ to obtain the form that you are familiar with: $$ \begin{align} 4x - 3y + 2 =& 0 \\ 4 x + 2 =& 3y \\ \frac{4}{3}x + \frac{2}{3} =& y \\ y =& \frac{4}{3}x + \frac{2}{3} \end{align} $$

From this you can tell that the line crosses the $y$-axis at $\frac{2}{3}$ and that the slope of the line is $\frac{4}{3}$: when $x$ increases by 1, $y$ increases by $\frac{4}{3}$.

$\endgroup$
2
  • $\begingroup$ I was just giving an example, my equations will be different, because all this is done at the run-time of a program. How can I do what you said if I only have 2 points on the line? So I can calculate the slope (y = mx + b). $\endgroup$
    – Axonn
    Mar 5, 2011 at 20:17
  • $\begingroup$ @Axonn, given two points $(x_1,y_1)$ and $(x_2, y_2)$, the slope is $m = \frac{y_2 - y_1}{x_2 - x_1}$ $\endgroup$ Jun 7, 2011 at 15:36
0
$\begingroup$

Borrowing from Homogeneous coordinates I set $A=y_2-y_1$, $B=x_1-x_2$ and $C=x_2 y_1-x_1 y_2$ such that $[A,B,C]\cdot[x,y,1]=A x + B y + C = 0$ is the equation of the line.

The distance of a vertex $P=(x_P, y_P)$ from the line is $$ d = \frac{A x_P+B y_P + C}{\sqrt{A^2+B^2}} $$

and the closest point $Q$ on the line from point $P$ lies in $$ \begin{bmatrix} x_Q \\ y_Q \end{bmatrix} = \frac{1}{A^2+B^2} \begin{bmatrix} B^2 \,x_P - A B \;y_P \\ A^2 \,y_P - A B \;x_P \end{bmatrix} $$

Edit: Homogeneous coordinates (HC) are a way to represent points, planes and lines for computer graphics methods. A point $(x,y)$ is represented by three coordinates $[x,y,1]$ and every scalar multiple of it, such as $[2x,2y,2]$. To get the point back from the 3 coordinates $[a,b,c]$ divide by the last value $(x,y)=(a/c,b/c)$.

The equation of the line through two points is derived from the line coordinates $$ L = [y_2-y_1, x_1-x_2, x_2 y_1-x_1 y_2] $$ in a way that when the dot-product with a point is zero that point falls on the line. So any point with coordinates $[x,y,1]$ that lies on the line has $$ [x,y,1]\cdot[y_2-y_1, x_1-x_2, x_2 y_1-x_1 y_2]=0 $$ $$ x(y_2-y_1)-y(x_2-x_1)+( x_2 y_1-x_1 y_2)=0 $$ which is the equation of the line in $Ax+By+C=0$ form. As a function the line is $y =-(A/B) x-(C/B)$

$\endgroup$
2
  • $\begingroup$ Not to be too critical, but I don't see how this answer would help anyone in the OP's position. For example, what is this "Homogenous coordinates" of which you speak? What does the notation [,,,].[,,,] mean? Where does your formula for $d$ come from? How do you get from the last equation to $Ax + By + C = 0$? $\endgroup$ Oct 4, 2011 at 16:39
  • $\begingroup$ @3Sphere - If interested in the subject look it up. Focus on planar system like Part 7 of cs.iastate.edu/~cs577/handouts/homogeneous-coords.pdf $\endgroup$ Oct 5, 2011 at 14:04

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.