java - 如何在java中检查给定点是否位于二维多边形内部。(常用方法)

Question

我尝试过使用面积来查找“点是否位于三角形内部”的代码。我认为通过这种方式，我可以找到“点是否位于多边形内部”的答案，因为任何多边形是由一个或多个三角形组成的。但是当多边形有更多边时，这个方法会很复杂。我想知道是否有另一种更简单的方法在java中实现这个。

这是我的代码，用于查找“一个点是否位于三角形内部”。

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

维基百科有一个解决这个问题的直接方法:Even–odd rule 。下面是 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;
  }
}