How to check whether a given point lies inside a 2D polygon or not in java .(Common way)

Question

I have tried the code to find "whether a point lies inside a triangle or not " ,using area.I think by this way ,I can find the answer to "whether a point lies inside a polygon or not" because any polygon is made up of one or more triangles.But when polygon have more sides ,this method will be complex.I want to know Is there another simplier way to implement this in java.

This is my code to find "whether a point lies inside a triangle or not ".

class PointInTriangle {
    static double AreaofTriangle(int x1,int y1,int x2,int y2,int x3,int y3){ 
        return 0.5*(double)Math.abs(x1*(y2-y3)+x2*(y3-y1)+x3*(y1-y2));
    }
    static boolean isInTriangle(int x1,int y1,int x2,int y2,int x3,int y3,int px,int py){
        double bigArea,area1,area2,area3;
        bigArea = AreaofTriangle(x1, y1, x2, y2, x3, y3);
        area1 = AreaofTriangle(px, py, x2, y2, x3, y3);
        area2 = AreaofTriangle(x1, y1, px, py, x3, y3);
        area3 = AreaofTriangle(x1, y1, x2, y2, px, py);

        if(bigArea == (area1+area2+area3)) {
            return true;
        }
        return false;
    }
    public static void main(String[]args){
        Scanner in = new Scanner(System.in);
        System.out.println("Enter three points of triangle:");// (x1,y1) , (x2,y2) , (x3,y3)
        int x1,y1,x2,y2,x3,y3,px,py;
        x1 = in.nextInt();
        y1 = in.nextInt();
        x2 = in.nextInt();
        y2 = in.nextInt();
        x3 = in.nextInt();
        y3 = in.nextInt();

        System.out.println("\nEnter searching point:");// (px,py)
        px = in.nextInt();
        py = in.nextInt();

        if(isInTriangle(x1, y1, x2, y2, x3, y3, px, py)){
            System.out.println("\nExtra point is in the triangle");
        }
        else{
            System.out.println("\nExtra point is not in the triangle");
        }

    }
}

Answer 1

Wikipedia has a direct approach to this problem at Even–odd rule. Here's an example of an implementation in Java:

class Point {
  int x;
  int y;

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

public class Testing {
  Point[] polygon;

  Testing(Point[] polygon) {
    this.polygon = polygon;
  }

  public static void main(final String[] args) {
    Point[] polygon = {new Point(5,11), new Point(4,4), new Point(11,2), new Point(2,2)};
    Testing test = new Testing(polygon);

    Point pOutside = new Point(6,6);
    Point pInside = new Point(3,3);
    System.out.println(test.isInsideByEvenOddRule(pOutside)); // false
    System.out.println(test.isInsideByEvenOddRule(pInside));  // true
  }

  // java implementation of https://en.wikipedia.org/wiki/Even–odd_rule
  boolean isInsideByEvenOddRule(Point point){
    boolean result = false;
    int j = polygon.length - 1;
    for (int i = 0; i < polygon.length; i++) {
        if ((polygon[i].y > point.y) != (polygon[j].y > point.y) &&
                (point.x < polygon[i].x + (polygon[j].x - polygon[i].x) *
                  (point.y - polygon[i].y) / (polygon[j].y - polygon[i].y))) {
          result = !result;
        }
      j = i;
    }
    return result;
  }
}

Answer 2

Using this formula, you could implement areaOfPolygon method using an array of Point objects:

class Point {
    public double x, y;

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

    public static double areaOfPolygon(Point[] points){
        double sum = 0;
        for (int i = 0; i < points.length-1; i++){
            sum += (points[i].x * points[i+1].y -
               points[i].y * points[i+1].x);
        }

        sum += (points[points.length-1].x * points[0].y -
            points[points.length-1].y * points[0].x);

        return Math.abs(0.5 * sum);
    }
}

Now you can build isInPolygon method using the areaOfPolygon method.