Points Inside a Polygon

The following describes an algorithm which is used to test if a point is within a polygon or not. The original algorithm is from the forum post here by Daniel Kuppitz. The following is intended to provide an explanation of this algorithm. For completeness this algorithm is given below (taken from the aformentioned forum post).

static bool PointInPolygon(Point p, Point[] poly)
{
    Point p1, p2;
    bool inside = false;

    if (poly.Length < 3)
    {
        return inside;
    }

    Point oldPoint = new Point(poly[poly.Length - 1].X, poly[poly.Length - 1].Y);

    for (int i = 0; i < poly.Length; i++)
    {
        Point newPoint = new Point(poly[i].X, poly[i].Y);

        if (newPoint.X > oldPoint.X)
        {
            p1 = oldPoint;
            p2 = newPoint;
        }
        else
        {
            p1 = newPoint;
            p2 = oldPoint;
        }

        if ((newPoint.X < p.X) == (p.X <= oldPoint.X) && 
           ((long)p.Y - (long)p1.Y) * (long)(p2.X - p1.X) < ((long)p2.Y - (long)p1.Y) * (long)(p.X - p1.X))
        {
            inside = !inside;
        }

        oldPoint = newPoint;
    }

    return inside;
}

How does this algorithm work?

This algorithm is formed around three contraints, all in the following excerpt taken from the original code:

if ((newPoint.X < p.X) == (p.X <= oldPoint.X) && 
           ((long)p.Y - (long)p1.Y) * (long)(p2.X - p1.X) < ((long)p2.Y - (long)p1.Y) * (long)(p.X - p1.X))

For a given point tested by the algorithm and a given line of the polygon (the algorithm iterates through each of the lines, testing them), the first two contraints are true only if the x-coordinates of the test point are within the bounds of the x-coordinates of the end of the line segment currently under consideration. The third constraint is only true if the point is on the side of the current line (extending past the delimited end points) 'facing' the origin x-axis of the image frame coordinate space. If all three constraints are true for a given line, the value held by a Boolean flag is toggled. Since this flag is given an initial value of False, a point is therefore inside a polygon for a an odd number of toggles (when all lines have been considered).

The following diagram is intended to better explain why the third constraint mentioned above works.

p1 and p2 are points at either end of a line forming one of the polygon edges, p is the current point under observation. The third constraint compares two areas to determine which side of the line p1->p2 p is on. In the above diagram, these are denoted 'Area 1' (red) and 'Area 2' (blue). If p sits on the line p1->p2, Area 1 will always be equal to Area 2. If p moves to the right or up, Area 1 is always less than Area 2. If p moves to the left or down, Area 1 is always greater than Area 2. Therefore, comparison of Areas 1 and 2 provides information regarding which side of the line p resides.

Example

To better demonstrate this algorithm, consider the following polygon:

The following images show the pixels (white) for which the first, second and third constraints are true for each line of the polygon.

Considering each of the images above sequentially (from left to right) the following series of images show the accumulative 'toggle' of the flags for each image. Here, the white pixels represent those which are currently considered to be part of the polygon (i.e. true). As can be seen, when all of the lines have been included (the far right image) only the pixels within the original polygon are white.

App

To help better understand how this point-inside-polygon algorithm works. I have developed an application, which demonstrates each of the stages represented in the previous example. The MSI installer for this application can be downloaded from here.

After installing and launching the app, you should be presented with a form that looks like the following:

The form is divided into three key areas. The left-hand area is were you can define your own polygon. The central area shows intermediate images created for each line of the polygon, i.e. all of the pixels which are considered to be part of the polygon with respect to a certain line are shown are white. The final, right-hand area, allows you to add each of the intermediate images to create the final combined image of all pixels with the polygon.

The following demonstrates example use of this app.

First, (left) click a point in the 'create polygon area' in the left-hand side area of the form. This should create the first vertice of the polygon, shown as the green square. The white circle's use is explained in a bit. You should now have something that looks like the screenshot below.

Select more polygon vertices by left clicking in the 'create a polygon' area. But make sure you do not select a vertex in the area highlighted by the white circle.

Now, complete the polygon. This can be achieved in one of two ways. Either, left click within the white circle, or right click anywhere within the 'create a polygon' area. Once the polygon has been completed, it will change from green to red. Once the polygon has been completed, if you wish to start again and create a new polygon, click the 'Clear' button.

When you are happy with a polygon to use, click the 'Process' button to create the intermediate processed images for each line of the polygon.

Each of the intermediate images can be added to (or removed) from the combined image at the right-hand side of the form using the check box entitled 'Add to combined image' below the corresponding image. All of the intermediate images can be added to or removed from the combined image using the 'Add All' or 'Clear All' buttons respectively.