Title: Determine whether a point is inside a polygon in C#

One way to determine whether a point lies within a polygon is to add up the angles between the point and adjacent points on the polygon taken in order. For example, if the point in question is P and points A and B are adjacent on the polygon, then you look at the angle APB.

If the total of all the angles is 2π or -2π, then the point is inside the polygon. If the total is zero, the point is outside. You can verify this intuitively with some simple examples using squares or triangles.

To use the example program, draw a polygon and position the mouse over the point you want to check. Then press F3 to invoke the Point in Polygon test. Alternatively you can use the Alt key to open the program's menu, use the arrow keys to select the test, and press Enter to perform the test. The program draws the point in green if it lies inside the polygon and red if it lies outside of the polygon.

The following code shows how the program's Polygon class determines whether a point lies inside the polygon.

// Return True if the point is in the polygon. public bool PointInPolygon(float X, float Y) { // Get the angle between the point and the // first and last vertices. int max_point = Points.Length - 1; float total_angle = GetAngle( Points[max_point].X, Points[max_point].Y, X, Y, Points[0].X, Points[0].Y); // Add the angles from the point // to each other pair of vertices. for (int i = 0; i < max_point; i++) { total_angle += GetAngle( Points[i].X, Points[i].Y, X, Y, Points[i + 1].X, Points[i + 1].Y); } // The total angle should be 2 * PI or -2 * PI if // the point is in the polygon and close to zero // if the point is outside the polygon. return (Math.Abs(total_angle) > 0.000001); }

This code first gets the angle made by the polygon's first and last points, plus the target point. It then loops through the polygon's other points calculating their angles and adding them up. When it finishes, the method returns true if the sum of the angles is close to 2π or -2π.

The following code shows the GetAngle method that the PointInPolygon method uses to find angles.

// Return the angle ABC. // Return a value 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(float Ax, float Ay, float Bx, float By, float Cx, float Cy) { // Get the dot product. float dot_product = DotProduct(Ax, Ay, Bx, By, Cx, Cy); // Get the cross product. float cross_product = CrossProductLength(Ax, Ay, Bx, By, Cx, Cy); // Calculate the angle. return (float)Math.Atan2(cross_product, dot_product); }

This code uses the DotProduct and CrossProductLength methods to get the angle's dot product and length of the cross product. (If the two vectors are AB and BC, then the dot product is given by |AB| * |BC| * Cos(theta) and the length of the cross product is given by |AB| * |BC| * Sin(theta), where theta is the angle between the two vectors.)

If you divide the length of the cross product by the length of the dot product, you get:

(|AB| * |BC| * Sin(theta)) / (|AB| * |BC| * Cos(theta)) =
Sin(theta)) / Cos(theta)) =
Tan(theta)

The Math.ATan2 method takes opposite and adjacent side lengths for a right triangle and returns an angle with the corresponding tangent. That fact plus the previous equations means Math.Atan2(cross_product, dot_product) returns the angle between the two vectors.

To see the CrossProductLength method, download the example or see the post Determine whether a polygon is convex in C#. The following code shows the DotProduct method.

// Return the dot product AB . BC. // Note that AB x BC = |AB| * |BC| * Cos(theta). private static float DotProduct(float Ax, float Ay, float Bx, float By, float Cx, float Cy) { // Get the vectors' coordinates. float BAx = Ax - Bx; float BAy = Ay - By; float BCx = Cx - Bx; float BCy = Cy - By; // Calculate the dot product. return (BAx * BCx + BAy * BCy); }

If two vectors A and B have X and Y components <Ax, Ay> and <Bx, By>, then their dot product is simply:

Ax * Bx + Ay * By

The DotProduct method simply calculates and returns that value. For more information on dot products, see Wikipedia and Wolfram MathWorld.

Download the example to experiment with it and to see additional details.