Point in Polygon Hit Testing

Checking to see if a point is inside a polygon is useful for 2D game development. Here's an algorithm in Java to do check if a given point is inside a polygon which only iterates through each vertex once so it's quite efficient.

Point in Polygon Java Example

The following Java source code checks to see if a given point is inside an array of counter-clockwise vertices.

The 2D polygon code:

public class Polygon {
  private Vector[] points;

  public Polygon(Vector[] points)
  {
    this.points = points;
  }

  public boolean pointInPolygon(float x, float y) {
    Vector p0 = points[points.length - 1];
    Vector p1 = points[0];

    boolean below0 = (y <= p0.y);

    boolean hit = false;

    for (int i = 1; i < points.length; i++) {
      boolean below1 = (y <= p1.y);

      if (below0 != below1) {
        if (((p1.y - y) * (p0.x - p1.x) >= (p1.x - x) * (p0.y - p1.y)) == below1) {
          hit = !hit;
        }
      }

      p0 = p1;
      p1 = points[i];
      below0 = below1;
    }

    return hit;
  }
}

The 2D vector code:

public class Vector {
  public float x;
  public float y;

  public Vector() {
  }

  public Vector(float x, float y) {
    this.x = x;
    this.y = y;
  }
}

How the Point in Polygon Algorithm Works

The algorithm cast a horizontal ray through the point under test. It checks to see if the \(y\) coordinates of each vertex switch from above the ray to below the ray. If a vertex flips, then it checks the \(x\) coordinate to see which way the point falls relative to the line. The algorithm will then determine if the point is inside or outside the polygon based on whether it was previously inside or outside and which side of the line between the two vertices the point lies.

It's very useful for 2D hit testing in games. The polygon does not need to be convex like some 2D vector algorithms - it works fine with a concave polygon.