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?


4 Answers 4


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.


For completeness an explanation as to how this works is as follows:

The direction of the line $AB$ can be defined as $<x_2, y_2> - <x_1, y_1> = <x_2 - x_1, y_2 - y_1>$

The orthogonal (perpendicular) direction to that line will be $\vec n=<y_2-y_1, -(x_2 - x_1)>$ (we flip the x's and the y's and negate one component i.e (y's, -x's)). You can verify this is orthogonal by taking the dot product with the original value and check it's 0).

One possible vector going from the line to the Point $P$ is $D = P-A = <x-x_1,y-y_1> $

This vector $D$ is made of 2 components, a component $D^{\parallel}$ that is parallel to the line $AB$ and a component $D^{\bot}$ that is perpendicular to the line $AB$. By definition $D^{\parallel} \cdot \vec n = 0$. Since a direction parallel to the line will be perpendicular to the normal of that line.

We are interested in knowing whether the point is on the side the normal points to, or the side the normal points opposite to. In other words, we want to know if $D^{\bot}$ is in the same direction as $\vec n$ or not.

This is essentially the sign of the dot product of $D$ and $\vec n$ since $D \cdot \vec n = (D^{\bot} + D^{\parallel}) \cdot \vec n = D^{\bot} \cdot \vec n$

Arithmetically: $$<x-x_1, y-y_1> \cdot <y_2 - y_1, -(x_2 - x_1)>$$ $$=(x-x_1)(y_2 - y_1) - (y-y_1)(x_2 - x_1)$$

In short, we are calculating the signed shortest distance from the line $AB$ to the point $P$ then evaluating the sign of that distance.

Diagram for clarity: enter image description here

  • 1
    $\begingroup$ Omg, thank You so much! Is there a name for this method? $\endgroup$
    – Ritvars
    Jan 9, 2013 at 21:02
  • 2
    $\begingroup$ 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. $\endgroup$
    – Shard
    Jan 9, 2013 at 21:41
  • 5
    $\begingroup$ This is the outer product of AB and AP. $\endgroup$
    – Joop Eggen
    Sep 6, 2017 at 21:36
  • 1
    $\begingroup$ @JoopEggen Shouldn't the outer product of 2 vectors be a matrix? At least according to wikipedia (en.wikipedia.org/wiki/Outer_product). $\endgroup$ Sep 16, 2019 at 13:15
  • 2
    $\begingroup$ @EricDuminil indeed! I could not find the correct notion. Usage:vector calc, 90° rotation, to find on which side of the line a point resides. Should be cross product. $\endgroup$
    – Joop Eggen
    Sep 16, 2019 at 13:47

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.

  • $\begingroup$ But the article you linked says that the product is only defined in three-dimensional space, and would be $a×b = ||a|| ||b|| sin(θ)n$. Could you please elaborate how does it relate to your formula? $\endgroup$
    – Hi-Angel
    Jan 4, 2018 at 15:02
  • 1
    $\begingroup$ @Hi-Angel - That formula is equivalent, but it's faster to compute multiplications. Look down on that page to see how it's calculated via the determinant, in our 2D case, just take all $z$ components of $u,v$ to be zero. $\endgroup$
    – nbubis
    Jan 5, 2018 at 13:11

An alternative derivation for the same formula is the dot product of $\vec{AP}$ and a vector perpendicular to $\vec{AB}$. Given $A=(x_1,y_1)$ and $B=(x_2,y_2)$, define vector $V$ perpendicular to $\vec{AB}$ as $V=[y_2-y_1, x_1-x_2]$. Then $$ V \cdotp \vec{AP} = (y_2-y_1)(x-x_1)+(x_1-x_2)(y-y_1)$$ Since dot product is negative iff the angle $\alpha$ between vectors satisfies $ \frac \pi 2 < \alpha < \frac 3 2 \pi$, the sign of the dot product determines which side of $\vec{AB}$ $P$ lies on.


Since people are struggling with terminology here, with outer product, dot product and cross product, I want to introduce another term: The perp dot product.

All we are calculating here is the dot product of one vector with another vector, that is rotated by 90°:

$$\mathbf{a}\perp\mathbf{b}=\mathbf{a}^\perp\cdot\mathbf{b} = a_xb_y-a_yb_x = \left|\begin{array}{rl}a_x&a_y\\b_x&b_y\end{array}\right|$$

It can be shown that this is the cross product with z-components equal zero:

$$\mathbf{a}\times\mathbf{b} = \left|\begin{array}{ccc}\hat{\mathbf{x}} & \hat{\mathbf{y}} & \hat{\mathbf{z}}\\a_x & a_y & 0\\b_x & b_y & 0\end{array}\right|= \left|\begin{array}{cc}a_x & a_y\\b_x & b_y\end{array}\right|\hat{\mathbf{z}} = (a_xb_y - a_yb_x)\hat{\mathbf{z}} = (\mathbf{a}\perp\mathbf{b})\hat{\mathbf{z}}$$

And now with $\mathbf{a}=P_2 - P_1$ and $\mathbf{b}=P_3 - P_1$, we can say

$$\begin{array}{rl}\mathbf{a}\perp\mathbf{b}=0 & \Leftrightarrow\mathbf{a}\text{ and }\mathbf{b}\text{ are collinear, i.e } |\theta|=\text{0° or 180°}\\\mathbf{a}\perp\mathbf{b} > 0 & \Leftrightarrow P_3\text{ is on left of } P_1P_2\text{, i.e. }0 < \theta < 180^\circ\\\mathbf{a}\perp\mathbf{b} < 0 & \Leftrightarrow P_3\text{ is on right of } P_1P_2\text{, i.e. }-180^\circ < \theta < 0\\\end{array}$$


You must log in to answer this question.

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