GitHub Account Google Scholar Account LinkedIn Account Twitter Account flickr Account vialab Research Group Profile Page

Checking if a Point Lies Within a Polygon

Date: May 10, 2016
To determine if a point lies within a polygon (point-in-polygon problem), one can employ the crossing number algorithm, also known as the even-odd rule algorithm. Starting at the point, cast an infinite ray in any fixed direction and count the number of times that the ray intersects with the polygon. If the number of intersections is odd, then the point is inside the polygon. If the number of intersections is even, then the point is outside of the polygon. A few caveats: the algorithm does not work if the point resides on an edge of the polygon, nor does it always work for self-intersecting polygons (complex polygons).

To determine if two lines intersect, one can employ the equation of the line:

Equation Equation Equation Equation
If the denominator of Scalar1 and Scalar2 (they are identical) is 0, then the two lines are parallel. If the denominator and numerator for the equations for Scalar1 and Scalar2 are 0, then the two lines are coincident. For two line segments, an intersection only occurs when Scalar1 and Scalar2 are between 0 and 1 inclusive.

To determine if a ray (infinite line) intersects a line segment, set Point3 as the start of the ray and Point4 as its direction. Then an intersection occurs when Scalar1 is between 0 and 1 inclusive and Scalar2 is bigger or equal to 0.

References: 1, 2, 3, 4
import java.util.Scanner;

public class PointInPolygon {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int testX = in.nextInt();
        int testY = in.nextInt();
        Point testPoint = new Point (testX, testY);

        int numPoints = 6;
        Point[] points = new Point[numPoints];

        points[0] = new Point(2, 1);
        points[1] = new Point(5, 5);
        points[2] = new Point(10, 3);
        points[3] = new Point(9, 10);
        points[4] = new Point(3, 10);
        points[5] = new Point(1, 5);

        Polygon poly = new Polygon(points);
        Point rayDir = new Point(10, 7);

        boolean pInside = poly.pointInside(testPoint, rayDir);

        if (pInside) {
            System.out.println("Point is inside the polygon!");
        } else {
            System.out.println(
                "Point is NOT inside the polygon!");
        }
    }

    public static class Polygon {

        Point[] points;

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

        public boolean intersects(Point testPoint,
          Point rayDir, Point edgePoint1, Point edgePoint2) {

            float denom = (rayDir.y - testPoint.y)
                * (edgePoint2.x - edgePoint1.x)
                - (rayDir.x - testPoint.x)
                * (edgePoint2.y - edgePoint1.y);

            float edgeScalar = (rayDir.x - testPoint.x)
                * (edgePoint1.y - testPoint.y)
                - (rayDir.y - testPoint.y)
                * (edgePoint1.x - testPoint.x);

            float testScalar = (edgePoint2.x - edgePoint1.x)
                * (edgePoint1.y - testPoint.y)
                - (edgePoint2.y - edgePoint1.y)
                * (edgePoint1.x - testPoint.x);

            if (denom != 0) {

                edgeScalar /= denom;
                testScalar /= denom;

                if (edgeScalar >= 0 && edgeScalar <= 1
                    && testScalar >= 0 ) {

                    Point p2p1 =
                            subtract(edgePoint2, edgePoint1);

                    Point multScalar =
                            mult(p2p1, edgeScalar);

                    Point interPoint =
                            add(edgePoint1, multScalar);

                    System.out.println("Intersection at : "
                          + interPoint.x + " " + interPoint.y);

                    return true;
                }
            }

            return false;
        }

        public boolean pointInside(Point testPoint,
        Point rayDir) {

            int length = points.length;
            Point edgePoint1 = null;
            Point edgePoint2 = null;
            int count = 0;
            boolean doesIntersect = false;


            for (int i = 0; i < length; i++) {

                edgePoint1 = points[i];

                if (i == length - 1) {
                    edgePoint2 = points[0];

                } else {
                    edgePoint2 = points[i + 1];
                }

                doesIntersect = intersects(testPoint, rayDir,
                                     edgePoint1, edgePoint2);

                if (doesIntersect) {
                    count++;
                }
            }

            if (count % 2 == 0) {
                return false;
            }

            return true;
        }
    }

    public static Point mult(Point a, float b) {
        return new Point(a.x * b, a.y * b);
    }

    public static float crossProduct(Point a, Point b) {
        return (a.x * b.y) - (b.x * a.y);
    }

    public static Point subtract(Point a, Point b) {
        return new Point(a.x - b.x, a.y - b.y);
    }

    public static Point add(Point a, Point b) {
        return new Point(a.x + b.x, a.y + b.y);
    }

    public static class Point {

        float x = -1;
        float y = -1;

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