Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
What information do you already have about the line? –  Isaac Mar 5 '11 at 19:28
    
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$. –  please delete me Mar 5 '11 at 19:44
    
Hi Isaac ::- D. I have 2 points on the line. –  Axonn Mar 5 '11 at 20:07
    
Oh, good, then I guessed right. :) –  Isaac Mar 5 '11 at 20:11

3 Answers 3

up vote 4 down vote accepted

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}$$

share|improve this answer
    
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 ). –  Axonn Mar 5 '11 at 20:14
1  
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$. –  Isaac Mar 5 '11 at 20:19
    
Oh, no problem! I just got confused to who is C ::- ). Now I understood that the right hand side is C. –  Axonn Mar 5 '11 at 20:23
    
Thank you again Isaac! ::- D. BTW, is this direction-independent? I suppose not, since you're talking about the vector. –  Axonn Mar 5 '11 at 20:28
1  
@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$. –  Isaac Mar 5 '11 at 20:36

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}$.

share|improve this answer
    
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). –  Axonn Mar 5 '11 at 20:17
    
@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}$ –  The Chaz 2.0 Jun 7 '11 at 15:36

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)$

share|improve this answer
    
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$? –  ItsNotObvious Oct 4 '11 at 16:39
    
@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 –  ja72 Oct 5 '11 at 14:04

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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