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.

Answer 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;
  ...
}

Answer 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".

Answer 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!

Answer 4

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

Answer 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.

Answer 6

Say, x[] is the array of x points and y[] is the array of y points.
You are meant to return 1 if the point exists in the polygon and 2 if not. where (planeX,planeY) is the point you need to check.

//check like this
return new Polygon(x,y,x.length).contains(planeX, planeY)?1:2;

Answer 7

Check to see if it's on the same side of the 4 half-planes defined by the lines that contain the line segments that make up the sides of the quad.

Here is a good explanation.

Answer 8

Polygon's abscissas x_array: Array[Integer]

Polygon's ordinates: y_array: Array[Integer]

Point: x: Integer, y: Integer

import java.awt.Polygon
import java.awt.Point
...

final boolean isInPolygon = 
    new Polygon(x_array,y_array,x_array.length).contains(new Point(x, y));

In this example we create an object java.awt.Polygon and use the method contains to check if your coordinates are in the shape you designed.

I use the object java.awt.Point to represent the coordinates to make the code elegant but that is optional, you can directly use .contains(x, y)

Answer 9

Many answers are based on intersections. Here is a simple algorithm not based on intersections but only using vector products. This method is less complex that methods based on intersections, but only works for convex polygons. Since the question is about convex polygons, this less complex method should be preferred.

Imagine that your convex polygon (P0, P1, ..., Pn), with (Pi-1, Pi) being its segments, is a needle clock and that the point C you want to check is inside the clock. The points (Pi) will either turn clockwise, or counterclockwise. Imagine a needle attached to C, that gives hours when turning clockwise. The vectors CP0→, CP1→, CP2→, CP...→, CPn→ all turn either clockwise, or counterclockwise. This means that the vector products CP0→⨯CP1→, CP1→⨯CP2→, CP2→⨯CP...→, CPn-1→⨯CPn→ and CPn→⨯CP0→ all have the same orientation. Since they are also colinear, their orientation is defined by the sign of their scalar product taken two by two. This property only occurs when C is inside the polygon. Therefore, iif the signs of the scalar products of the vector products are constant, C is inside the polygon.