One way to determine whether a point lies inside a polygon is to add up the angles that it makes with the polygon's vertices. If the test point is P and A and B are two adjacent polygon points, then you look at the angle ∠APB.

If you add up all of the angles between the test point and each of the polygon's edges, the result will be either 0, 2π, or –2π. If the total is 2π or –2π, then the point is inside the polygon. If the total is 0, then the point lies outside of the polygon. You can probably convince yourself that this works if you draw a few examples. For example, try placing points inside and outside of a square, draw the angles, and estimate their values.

The idea is straightforward. The hard part is calculating the angles. One way to do that is to use dot products and cross products.

The dot product of two vectors, v0 and v1, which is written v0 ∙ v1, equals |v0| × |v1| cos(θ), where |v0| and |v1| mean the lengths of the vectors v0 and v1, and θ is the angle between the two vectors.

One nice thing about dot products is that they are easy to calculate. If the vectors have the components v0 = <v0x, v0y> and v1 = <v1x, v1y>, then their dot product is simply v0x * v1x + v0y * v1y. If you calculate a dot product and then divide by the lengths of the two vectors, then the result is the cosine of the angle between the vectors.

Unfortunately, the cosine isn't quite enough to determine the angle because cos(θ) = cos(-θ). Even after you find the cosine, you still don't know which angle to use.

That's where the cross product comes in. The cross product of two vectors, v0 and v1, which is written v0 × v1, gives you a new vector that is perpendicular to both v0 and v1. For example, if v0 and v1 lie in the plane of your table, then v0 × v1 pokes straight up out of (or down into) the table. The length of the new vector is |v0| × |v1| sin(θ).

If you write the vectors in three dimensions as <v0x, v0y, v0z> and <v1x, v1y, v1z>, then the cross product of the vectors is <rx, ry, rz>, where:

If you assume that the vectors v0 and v1 lie in the X-Y plane, then their Z coordinates are zero, so the rx and ry values are also zero. That makes sense because the result of the cross product is a vector that is perpendicular to the plane containing v0 and v1, so it's X and Y components should be zero. Because this vector has only one non-zero component, rz, its length is simply rz = v0x * v1y – v0y * v1x.

After you calculate the cross product, you simply divide by the lengths of the two original vectors and you know sin(θ).

Finally, after you know cos(θ) and sin(θ), you can use the arctangent function to find θ.

Now that you know how to find the angle θ, it's time to look at some code. The following methods calculate the dot and cross products:

// Return the cross product AB x BC.
// Note that |AB x BC| = |AB| * |BC| * Sin(theta).
public static float CrossProductLength(Point A, Point B, Point C)
{
    // Get the vectors' components.
    float ABx = A.X - B.X;
    float ABy = A.Y - B.Y;
    float BCx = C.X - B.X;
    float BCy = C.Y - B.Y;

    // Calculate the Z coordinate of the cross product.
    return (ABx * BCy - ABy * BCx);
}

// Return the dot product AB · BC.
// Note that AB · BC = |AB| * |BC| * Cos(theta).
private static float DotProduct(Point A, Point B, Point C)
{
    // Get the vectors' components.
    float ABx = A.X - B.X;
    float ABy = A.Y - B.Y;
    float BCx = C.X - B.X;
    float BCy = C.Y - B.Y;

    // Calculate the dot product.
    return (ABx * BCx + ABy * BCy);
}

These methods take as parameters three points A, B, and C, and calculate AB ∙ BC and AB × BC, respectively.

The following GetAngle method uses the DotProduct and CrossProduct methods to find the angle ∠ABC:

// Return angle ABC between PI and -PI.
// Note that the value is the opposite of what you might
// expect because Y coordinates increase downward.
public static float GetAngle(Point A, Point B, Point C)
{
    // Get the dot product.
    float dotProduct = DotProduct(A, B, C);

    // Get the cross product.
    float crossProduct = CrossProductLength(A, B, C);

    // Calculate the angle.
    return (float)Math.Atan2(crossProduct, dotProduct);
}

The method calls the DotProduct and CrossProduct methods to get the dot and cross products. It then uses the Math.Atan2 method to find the corresponding angle.

Finally, the following code shows the PointIsInPolygon method:

// Return true if testPoint lies inside the polygon.
private bool PointIsInPolygon(List<Point> points, Point testPoint)
{
    int numPoints = points.Count;
    if (numPoints < 3)
        throw new Exception(
            "The polygon must have at least three vertices");

    // Repeat the first point at the end for convenience.
    points.Add(points[0]);

    // Loop over the polygon's segments.
    float total = 0;
    for (int i = 0; i < numPoints; i++)
        total += GetAngle(points[i], testPoint, points[i + 1]);

    // Remove the repeated first point.
    points.RemoveAt(numPoints);

    // See if total is +/-2*pi.
    const float tiny = 0.0001f;
    return (Math.Abs(total) > tiny);
}

This method first verifies that the polygon contains at least three points and throws an exception if it doesn't. It then adds a copy of the first point to the end of the polygon's point list to make looping through the polygon's edges easier.

Next, the code loops through the polygon's edges. For each edge, it calls the GetAngle method to get the corresponding angle and adds it to the total.

After it has processed all of the edges, the method removes the copy of the first point from the end of the point list. It finishes by returning true if the total angle is not close to 0, which means it is either 2π, or –2π.

Download the PointInPolygon example solution to see additional details.