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 am a programmer without really good knowledge in math. :/ So I have to write an algorithm that changes the color of pixel(dot) P to opposite if it's on left side of the straigt line in coordinate system (and the line is not vertical, with that I mean, x2-x1 can't be 0). The values of x1, y1 and x2, y2 dots are known (and they can also be negative).

Does anyone have an idea how could this be solved?

share|improve this question
    
Previously: On which side of vector the point is –  Rahul Jan 9 '13 at 20:14

2 Answers 2

up vote 1 down vote accepted

To determine which side of the line from $A=(x_1,y_1)$ to $B=(x_2,y_2)$ a point $P=(x,y)$ falls on you need to compute the value:- $$d=(x-x_1)(y_2-y_1)-(y-y_1)(x_2-x_1)$$ If $d<0$ then the point lies on one side of the line, and if $d>0$ then it lies on the other side. If $d=0$ then the point lies exactly line.

To see whether points on the left side of the line are those with positive or negative values compute the value for $d$ for a point you know is to the left of the line, such as $(x_1-1,y_1)$ and then compare the sign with the point you are interested in.

share|improve this answer
    
Omg, thank You so much! Is there a name for this method? –  Ritvars Jan 9 '13 at 21:02
    
I'm not sure, but this method is often used to calculate the winding order of triangles in computer graphics to ascertain if a triangle is facing towards or away from you. –  Shard Jan 9 '13 at 21:41

If the point is given by the 2D vector $\vec{P}$ and the line end point by $\vec{A}$ and $\vec{B}$, then calculate the cross product: $$\vec{AB}\times\vec{AP} = x_{AB}\cdot y_{AP} - x_{AP}\cdot y_{AB}$$ $$x_{AB} = x_B - x_A,\ x_{AP} = x_P - x_A\ ...$$ The sign of the above will determine what side of the line your pixel is on.

share|improve this answer

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.