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
    Commented 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
    Commented Mar 5, 2011 at 19:44
  • $\begingroup$ Hi Isaac ::- D. I have 2 points on the line. $\endgroup$
    – Axonn
    Commented Mar 5, 2011 at 20:07
  • $\begingroup$ Oh, good, then I guessed right. :) $\endgroup$
    – Isaac
    Commented 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
    Commented 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
    Commented 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
    Commented 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
    Commented 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
    Commented 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
    Commented 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$ Commented 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$ Commented 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$ Commented Oct 5, 2011 at 14:04

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .