7

I have three points: p1(x1,y1) p2(x2,y2) and p3(x3,y3).

I am connecting p1 to p2 to p3. how can I tell if the triangle was drawn clockwise or counter-clockwise?

How can I generalize this for n points? (you pass through a point exactly once, and no lines can cross).

Thanks all!

Ben West
  • 12,366
Michael Seltenreich
  • 222
  • 1
  • 2
  • 14

4 Answers4

6

If the points
$(x_1\mid y_1); (x_2\mid y_2); (x_3\mid y_3)$
are in anticlockwise order, then
$\begin{vmatrix} x_1&y_1&1\\ x_2&y_2&1\\ x_3&y_3&1\\ \end{vmatrix}\gt 0$ . If clockwise, then $\lt 0$ .

If in a line, then $=0$ .

As for your second question, select one of the points and call it $P_1$. For $n$ points, you will conduct the same test on $n-2$ triangles, as follows:

Triangle #1: $P_1,P_2,P_3$
Triangle #2: $P_1,P_3,P_4$
Triangle #3: $P_1,P_4,P_5$
.............................
Triangle #n-4: $P_1,P_{n-3},P_{n-2}$
Triangle #n-3: $P_1,P_{n-2},P_{n-1}$
Triangle #n-2: $P_1,P_{n-1},P_{n}$

Senex Ægypti Parvi
  • 2,419
  • Your test for $n$ vertices is incorrect. –  Jun 13 '15 at 21:04
  • @Yves Daoust \ My conception of the problem is that the polygon is to be broken up into triangles. The first vertex of each is $P_1$. The sequence of triangles progresses according to the order of points desired by the OP. The failure of the clockwise test by one of the triangles would be the criterion for failing the entire sequence of points. Have I missed something? Should only the hull of the given points be considered? – Senex Ægypti Parvi Jun 13 '15 at 21:52
  • Take a polygon that starts from $P_1$ and makes two clockwise turns around it. It will pass your sign tests though it crosses itself. –  Jun 14 '15 at 07:06
  • why clockwise if it is negative? any intuition behind this? – SRIDHARAN Dec 19 '17 at 14:10
  • @Sridharan it's just convention. On tutorials point the algorithm has it the other way around. And if you switch the ordering of that formula, anticlockwise then becomes negative. It's useful to visualise each compositional vector and how when multiplied it gives an indication of turning direction.

    https://www.tutorialspoint.com/Check-if-two-line-segments-intersect

     – AER Jan 23 '19 at 02:42
3

My geometry is a little rusty, but I think this works:

Compare the quantities $A = x_2y_1+x_3y_2+x_1y_3$ and $B = x_1y_2+x_2y_3+x_3y_1$.

If $A > B$ then the triangle was drawn clockwise. If $A < B$ then the triangle was drawn counterclockwise. If $A = B$ then the triangle is degenerate.

This should generalize to $n$ points by letting $A = \displaystyle\sum_{k = 1}^{n}x_{k+1}y_k$ and $B = \displaystyle\sum_{k = 1}^{n}x_ky_{k+1}$ (where $x_{n+1} = x_1$ and $y_{n+1} = y_1$).

JimmyK4542
  • 54,331
  • This isn't quite right. Example failures (in radians, for unit vectors): 1, 1, 1 and 2, 1, 6 The determinant-based answer from Senex Aegypti Parvi above I think is correct. – ZachB May 05 '23 at 21:37
1

use a linear transformation such that the first point goes to 0, the second goes to 1 and the third goes to infinity. See where the center goes to a point in the upper half plane or in the lower half plane. See Ahlfors: Complex analysis p. 83 on orientation of circles.

Adelafif
  • 1,275
1

Checking the polygon has no self intersection is called the Simplicity test, and it is related to the problem of polygon triangulation.

The easiest approach is by just testing every pair of edges for intersection, but this is an $O(N^2)$ process, only acceptable for small $N$. Chazelle has shown that it can be performed in optimal time $O(N)$ but implementing his algorithm is daunting. An acceptable compromise is to use an efficient lines segment intersection test like that of Bentley and Ottman, which will run in time $O(N \log(N))$.