7. How to tell when a point is inside an arbitrary polygon.

Again, label the polygon $P _ 0,\dots, P _ {n-1}$ with $P _ n = P _ 0$, and consider a point $Q$.

Method #1: Choose a point $S$ that you know is outside the polygon. Find how many times the line segment $\overline{QS}$ crosses the edges of the polygon. If this count is odd, then $Q$ is inside the polygon; if it is even, then $Q$ is outside.

Details: For the $x$ coordinate of $S$, you could, say, take the max of the $x$ coordinates of the points $P _ i$ and add 1. Then $S$ is definitely outside. For the $y$ coordinate of $S$, use a random number between 0 and 1; that way, there is essentially no possibility that $\overline{QS}$ will go through one of the $P _ i$, an undesirable case. If $Q$ is on the boundary, you'll discover that fact as part of looking for the crossings.

Method #2 (the winding number method): Add up the angles subtended at $P$ by the edges of the polygon, with appropriate signs, and divide the total by $2 \pi$. The result is called the winding number (the number of times that the polygon winds around $P$). If the winding number is 1 or -1, $P$ is inside; if it is $0$, $P$ is outside.

In Method #2, for each $i$ you will need to find the signed angle between the vector $P _ {i-1} - Q$ and the vector $P _ i - Q$, using the method of Handout C, §5, (vi). It is a good idea to check separately that $Q$ is not equal to any of the points $P _ i$, so that the difference vectors are both nonzero. You can check that $Q$ is not on the boundary when you are finding the angles.