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. // The following statement was changed. See the comments. //return (Math.Abs(total_angle) > 0.000001); return (Math.Abs(total_angle) > 1); }

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

Thanks a Ton…

It was exactly what I needed.

Congratulations, very good job! I’ve used it with double data type

The PointInPolygon method fails for the below polygon:

https://imgur.com/QkXxkMM

Otherwise it is a great method and i am using it in my project where there are no such polygons!

I think this is a rounding error. When I step through an example where it incorrectly thinks a point is inside the polygon, the total of the angles is 0.000001013279, which is slightly larger than the value 0.000001 that it uses for comparison.

There’s really no need to use such a small comparison value because the total should be either 2π, -2π, or 0.

I think it should work if you change the test in the

PointInPolygonmethod to the following.I have made that change to the code.

Thank you!!!

Hi!

Checked that latest version and works perfectly!

Also all the other polygon related operations!

If I were you, I would create a class library of polygon operations and also publish a nuget package…

Cheers,

Ladislav

Should this algorithm work also on spherical polygons? Especially near sphere poles?

If you mean should it work in three-dimensional polygons, the answer is “sort of.” This code only works in two-dimensions, so you would need to project the three-dimensional points into two-dimensional space before using the method.

That’s one way a three-dimensional drawing tool can perform hit testing. They convert the points that make up the objects into the viewing projection and then do something similar to what’s shown here to see if the point lies inside the resulting transformed polygons. They also need to find the points of intersection so they can tell which intersection is closest to the camera.

If you’re trying to perform hit testing, then you might be better off just allowing the 3D tool to find the point of intersection for you.

If you’re asking whether it will work with a “polygon” that has points that lie on a sphere, then the answer is “not quite.” A triangle is still a triangle if its points lie on a sphere, but in general more complex polygons won’t actually be polygons because they won’t be flat. You can still project them with the viewing transformation to make them flat and then the previous discussion applies.

And if I’m completely missing your question, post a follow-up. 😉