How to determine if a point is inside a 2D convex polygon?

Question

I have a convex polygon (typically just a rotated square), and I know all of 4 points. How do I determine if a given point (yellow/green) is inside the polygon?

EDIT: For this particular project, I don't have access to all of the libraries of the JDK, such as AWT.

Solution 1

This page: http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html shows how to do this for any polygon.

I have a Java implementation of this, but it is too big to post here in its entirety. However, you should be able to work it out:

class Boundary {
    private final Point[] points; // Points making up the boundary
    ...


    /**
     * Return true if the given point is contained inside the boundary.
     * See: http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html
     * @param test The point to check
     * @return true if the point is inside the boundary, false otherwise
     *
     */
    public boolean contains(Point test) {
      int i;
      int j;
      boolean result = false;
      for (i = 0, j = points.length - 1; i < points.length; j = i++) {
        if ((points[i].y > test.y) != (points[j].y > test.y) &&
            (test.x < (points[j].x - points[i].x) * (test.y - points[i].y) / (points[j].y-points[i].y) + points[i].x)) {
          result = !result;
         }
      }
      return result;
    }
}

And here is a sketch of the Point class

/**
 * Two dimensional cartesian point.
 */
public class Point {
  public final double x;
  public final double y;
  ...
}

Solution 2

For those who would like to understand how the method written by Dean Povey above works, here is the explanation:

The method looks at a "ray" that starts at the tested spot and extends to infinity to the right side of the X axis. For each polygon segment, it checks if the ray crosses it. If the total number of segment crossing is odd then the tested point is considered inside the polygon, otherwise - it is outside.

To understand the way the crossing is calculated, consider the following figure:

            v2
            o
           /
          / c (intersection)
o--------x----------------------> to infinity
t       /
       /   
      /
     o
     v1

For the intersection to occur, tested.y must be between the y values of the segment's vertices (v1 and v2). This is the first condition of the if statement in the method. If this is what happens, then the horizontal line must intersect the segment. It only remains to establish whether the intersection happens to the right of the tested point or to the left of it. This requires finding the x coordinate of the intersection point, which is:

              t.y - v1.y
c.x = v1.x + ----------- * (v2.x - v1.x)
             v2.y - v1.y

All that remains to be done is examining the subtleties:

• If v1.y == v2.y then the ray goes along the segment and therefore the segment has no influence on the outcome. Indeed, the first part of the if statement returns false in that case.
• The code first multiplies and only then divides. This is done to support very small differences between v1.x and v2.x, which might lead to a zero after the division, due to rounding.
• Finally, the problem of crossing exactly on a vertex should be addressed. Consider the following two cases:

         o                    o
         |                     \     o
         | A1                C1 \   /
         |                       \ / C2  
o--------x-----------x------------x--------> to infinity
        /           / \
    A2 /        B1 /   \ B2
      /           /     \ 
     o           /       o
                o

Now, to verify if it works, check for yourself what is returned for each of the 4 segments by the if condition in the method body. You should find that the segments above the ray (A1, C1, C2) receive a positive result, while those below it (A2, B1, B2) receive a negative one. This means that the A vertex contributes an odd number (1) to the crossing count, while B and C contribute an even number (0 and 2, respectively), which is exactly what is desired. A is indeed a real crossing of the polygon, while B and C are just two cases of "fly-by".

Solution 3

Assuming that your point is at Y coordinate y, simply calculate the x positions where each of the polygon's (non-horizontal) lines cross y. Count the number of x positions that are less than the x position of your point. If the number of x positions is odd, your point is inside the polygon. Note: this works for all polygons, not just convex. Think of it this way: draw a line from infinitely far away straight in to your point. When that line crosses a polygon line, it is now inside the polygon. Cross the line again, outside. Cross again, inside (and so forth). Hope this helps!

Solution 4

The java.awt.Polygon class has a number of contains(...) methods if you use Polygon objects to represent your polygon.

Solution 5

Just to add a (simple) Java implementation of the original code in C from code suggested by @Dean Povey (I don't know why @Dean Povey is referring to a large implementation):

static boolean pnpoly(double[] vertx, double[] verty, double testx, double testy)
{
    int nvert = vertx.length;
    int i, j;
    boolean c = false;
    for (i = 0, j = nvert-1; i < nvert; j = i++) {
        if ( ((verty[i]>testy) != (verty[j]>testy)) &&
                (testx < (vertx[j]-vertx[i]) * (testy-verty[i]) / (verty[j]-verty[i]) + vertx[i]) )
            c = !c;
    }
    return c;
}   

I did not change the case to comply with Java rule to show the minimal changes required. I have also tested it in simple cases and it works fine.

View more solutions