How to check a polygon in $\mathbb{R}^2$ for convexity. Given $n$ points in $\mathbb{R}^2$, $\{p_1,p_2,\ldots,p_n\}$,
how do we test if the (interior of the) polygon formed by drawing the line segments  $[{p_{i-1},p_i}]$ for $1\le i \le n$ and also $[p_n,p_1]$ is a convex set in the plane?
Is there a simple algorithm?
 A: This is $O(n)$. First, define the deviation of a vertex $p_r$ to be the (signed) angle by which the direction of $p_rp_{r+1}$ differs from the direction of $p_{r-1}p_r$. This can be calculated as $\arcsin z$, where $z$ is the $z$-coordinate of:
$\dfrac{(p_{r+1}-p_r)}{|p_{r+1}-p_r|} \times \dfrac{(p_r - p_{r-1})}{|p_r - p_{r-1}|}$
Now, we get a convex set if and only if the following two conditions are met:


*

*Every deviation has the same sign (or is zero);

*The sum of the deviations is $\pm 2\pi$.



Note that, in practice, the deviation calculations may be ill-conditioned. This will happen if two points are very close together, or two successive edges are nearly parallel. But in these cases, the question of whether the figure is convex is also ill-conditioned.
Also, the sum of the deviations will not be exactly $\pm 2\pi$ in a real-world calculation, because of rounding errors. Instead, you could check that the nearest integer to |sum of deviations|/$2\pi$ is $1$.
A: It can all be done easily in $O(n)$ operations: for safety, first check that the given polygon can be split in two monotone chains (find the leftmost and rightmost of them and check monotonicity in between, i.e. increasing abscissas); if that fails, the polygon is not convex. Then check that all angles are convex in these chains.
This is a simplified version of Andrew's algorithm for convex hulls. It will also work with non-simple polygons.
A: Alternatively to checking oriented area as in Yves Daoust's answer, one could check that the polygon is locally convex at each vertex as follows.
Let $p_i$ be a fixed vertex.  For each other vertex $w$, show that the angles $\angle p_{i-1}p_i w$ and $\angle wp_ip_{i+1}$ are accute.  This can be done arithmetically by using the distances between the points and the law of cosines.  This is $\mathcal{O}(n^2)$ (maybe?).
