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!
$\endgroup$ 24 Answers
$\begingroup$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}$
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.
$\endgroup$ $\begingroup$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$).
$\endgroup$ $\begingroup$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))$.
$\endgroup$
