1
$\begingroup$

I have a confusion related to an algorithm for finding the orientation given three points, i.e., determining whether one line is clockwise or counter-clockwise of another.

Let's say the points are $P_1=(x_1,y_1)$, $P_2=(x_2,y_2)$, $P_3(x_3,y_3)$. The algorithm says

  • Let the slope of line $P_1P_2$ be $m_1$ and slope of $P_2P_3$ be $m_2$.
  • If $m_2 > m_1$, the orientation is counterclockwise and if $m_1 > m_2$ it is clockwise.

However lets say the points are $(0,0)$, $(4,4)$ and $(2,4)$. This give $m_1=1$, $m_2=0$. The orientation is counter clockwise but $m_2 < m_1$. So I am wondering if there is any issue with the algorithm.

Any suggestions?

$\endgroup$
  • $\begingroup$ The slope of the line from $(4,4)$ to $(2,4)$ is $0$, not $-1$ as you wrote. I corrected the slope but did you mean to write some other point? $\endgroup$ – David Richerby May 5 '17 at 9:24
3
$\begingroup$

The orientation of three points in the plane is classically done with a determinant. In the linked article the approach is done on a polygon thus they use a 3x3 determinant. For only three points, i.e., a triangle, a 2x2 determinat is sufficient.

Let $p_1=(x_1,y_1), p_2=(x_2,y_2)$, and $p_3=(x_3,y_3)$ be three points in the plane. Then we compute the orientation vectors at $p_1$, that is $p_{1,2}=p_2-p_1$ and $p_{1,3}=p_3-p_1$. Now we use the determinant to find the orientation: $$\mathrm{det}\begin{bmatrix}x_2-x_1&y_2-y_1\\x_3-x_1&y_3-y_1\end{bmatrix}=(x_2-x_1)(y_3-y_1)-(y_2-y_1)(x_3-x_1).$$

If the result is smaller than zero then $(p_1,p_2,p_3)$ are in counter-clockwise order, if larger than zero in clockwise order, and if zero then they are collinear.

$\endgroup$

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.