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 draw 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 · 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.

Great code man, worked like a charm for me. I was having a problem with the code from http://social.msdn.microsoft.com/forums/en-US/winforms/thread/95055cdc-60f8-4c22-8270-ab5f9870270a/ because its was saying that a point is inside when i used a very complex polygon, and with your code it worked very well, thank you so much.

Thank you!

Great applicaton :))

great application thank you!

Pingback: Perform geometric operations on polygons in C# |

Pingback: Determine whether a point lies inside a polygon in C#

There are some great graphics tools in .NET

Regions

The region also has a transform. It can be used if the region happens to be a selection box or selection shape on your screen. You can apply the inverse transform (if any) used when some objects where drawn and test if a known point falls within your selection box.

THANKKKKK YOUUUU!!!! GREAT Solution