How to determine whether a vertex of a simple polygon is convex

Question

I'm trying to understand the ear clipping algorithm for triangulation of a simple polygon G on the Euclidian plane.

It checks whether a vertex of G is convex; Let p, q, r be consecutive 3 vertices of G. q is said to be convex if the internal angle between the edges (p, q) and (q,r) is less than 180 degrees.

My question is: How do you determine computationally if q is convex?

Answer 1

Let $a\in G$ (in the interior) and $L$ the line by $p$ and $r$. If $q$ and $a$ are in the same semiplane respect to $L$, $q$ are not convex.

To check this, see (if exist or not) the intersection of $L$ with the segment $aq$

Answer 2

Your question is for arbitrary consecutive vertices, in which case you do need to know that the polygon has an interior and an exterior to make the question of whether it is a convex angle a meaningful one. Once you have that, the following method can be easily shown to give you the answer.

Begin at the bottommost vertex and walk along the polygon starting with the rightmost incident edge. The interior is always on the left of the walk, so you can identify which angles along the way are convex (interior angle less than $180$ degrees) and which are concave simply by seeing which are left-turns and which are right-turns.

It is easy to prove that this works. At the start, there is a straight path from the vertex to infinity on the right, so the interior is on the left. Take any consecutive vertices $A,B,C,D$ in order along the walk such that the interior is on the left of the subpath $ABC$. Let $B',C'$ respectively be points that are sufficiently close to $B,C$ on the left of the subpaths $ABC,BCD$. Then $B',C'$ are connected by a straight path not intersecting the polygon. How close is sufficient? Less than the minimum distance from a vertex to a non-incident edge, which would mean that $B',C'$ are close enough to $BC$ that $B'C'$ cannot cut any edge of the polygon since no vertex besides $B,C$ is so close to $BC$.