本文共 2732 字，大约阅读时间需要 9 分钟。

判断点是否在多边形内

代码逻辑说明

此算法基于“叉积判断”方法，即通过计算点与多边形边的交叉点数来确定点的位置关系。具体来说：

代码实现

public static boolean IsPtInPoly(Point2D point, List
   
     pts) {      int N = pts.size();      boolean boundOrVertex = true;      int intersectCount = 0;      double precision = 2e-10;      Point2D p1 = pts.get(0);      Point2D p = new Point2D(testX, testY);      for (int i = 1; i <= N; ++i) {          if (p.equals(p1)) {              return boundOrVertex;          }          Point2D p2 = pts.get(i % N);          if (p.x < Math.min(p1.x, p2.x) || p.x > Math.max(p1.x, p2.x)) {              p1 = p2;              continue;          }          if (p.x > Math.min(p1.x, p2.x) && p.x < Math.max(p1.x, p2.x)) {              if (p.y <= Math.max(p1.y, p2.y)) {                  if (p1.x == p2.x && p.y >= Math.min(p1.y, p2.y)) {                      return boundOrVertex;                  }                  if (p1.y == p2.y) {                      if (p1.y == p.y) {                          return boundOrVertex;                      } else {                          ++intersectCount;                      }                  } else {                      double xinters = (p.x - p1.x) * (p2.y - p1.y) / (p2.x - p1.x) + p1.y;                      if (Math.abs(p.y - xinters) < precision) {                          return boundOrVertex;                      }                      if (p.y < xinters) {                          ++intersectCount;                      }                  }              } else {                  if (p.x == p2.x && p.y <= p2.y) {                      Point2D p3 = pts.get((i+1) % N);                      if (p.x >= Math.min(p1.x, p3.x) && p.x <= Math.max(p1.x, p3.x)) {                          ++intersectCount;                      } else {                          intersectCount += 2;                      }                  }              }          }          p1 = p2;      }      return intersectCount % 2 == 0 ? false : true;  }  ### 测试案例  为了验证该算法的准确性，可以编写以下测试用例：  ```java  public static void main(String[] args) {      Point2D point = new Point2D(116.404072, 39.916605);      List
    
      pts = new ArrayList<>();    pts.add(new Point2D(116.395, 39.910));      pts.add(new Point2D(116.394, 39.914));      pts.add(new Point2D(116.403, 39.920));      pts.add(new Point2D(116.402, 39.914));      pts.add(new Point2D(116.410, 39.913));      if (IsPtInPoly(point, pts)) {          System.out.println("点在多边形内");      } else {          System.out.println("点在多边形外");      }  }
    
   

总结

通过上述代码及测试案例，可以方便地判断任意给定点是否位于多边形内。该算法在保持简洁的同时，具备较高的准确性和效率，是解决实际问题的有效方法。

转载地址：http://vjryk.baihongyu.com/