6. When is a point inside a polygon? The convex case.

What is a good computer method for deciding whether a point $Q$ in    R$^ 2$ is in the interior of a triangle, or more generally, any convex polygon?

If the polygon has $n$ vertices, call them $P _ 0,\dots, P _ {n-1}$ and

let $P _ n = P _ 0$. Then the sides are $\overline{P _ {i-1} P _ {i}}$ for $i = 1,\dots, n$. Here is a method:

(*) $Q$ is in the interior of the polygon $\Leftrightarrow$ for each $i = 1,\dots, n$, $P _ {i-1}$ is to the right of $P _ i$ as seen from $Q$, or else for each $i = 1,\dots, n$, $P _ {i-1}$ is to the left of $P _ i$ as seen from $Q$. Computationally:

(**) $Q$ is in the interior of the polygon $\Leftrightarrow$ all determinants $\Delta(P _ {i-1}, P _ i, Q)$ have the same sign.

The reason why (*) is equivalent to (**) is contained in Proposition 1 of §4. Of course, if any determinant is zero, $Q$ is on the boundary.