Determine whether a point is inside a polygon in C#

example

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.


Download Example   Follow me on Twitter   RSS feed


This entry was posted in algorithms, geometry, graphics, mathematics and tagged , , , , , , , , , , , , . Bookmark the permalink.

7 Responses to Determine whether a point is inside a polygon in C#

  1. Felipe Vaz says:

    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.

  2. Anonymous says:

    Thank you!

    Great applicaton :))

  3. murat says:

    great application thank you!

  4. Pingback: Perform geometric operations on polygons in C# |

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

  6. TFO says:

    There are some great graphics tools in .NET

    Regions

    Region region1 = new Region(new Rectangle(50, 0, 50, 150));
    Point point = new Point(60, 10);
    if (region1.IsVisible(point)
    {
        //Point is within region
    }

    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.

  7. Mike says:

    THANKKKKK YOUUUU!!!! GREAT Solution

Leave a Reply

Your email address will not be published. Required fields are marked *