计算点是否在多边形内

发表于 更新于 分类于

现有一个多边形，和一个点，需要判断点是否在多边形内。
几种情况：

  • 点在边上
  • 点在多边形顶点上
  • 点在多边形内

方法通过射线法，从点发出一条射线，如果穿过多边形，偶数个交点表示在多边形外；奇数个交点在多边形内。
特殊情况：

  • 点的射线和多边形边重合
  • 点的射线刚刚好经过多边形的点 代码实现如下：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    public static boolean pointInPolygon(double[][] polygon, double[] point) {
        if (polygon.length < 3) {
            return false;
        }
        double x = point[0];
        double y = point[1];
        boolean in = false;

        for (int i = 0, j = polygon.length - 1; i < polygon.length; j = i++) {
            double x1 = polygon[i][0];
            double y1 = polygon[i][1];
            double x2 = polygon[j][0];
            double y2 = polygon[j][1];
            //点位重合
            if ((x == x1 && y == y1) || (x == x2 && y == y2)) {
                return true;
            }
            //斜率为0，点在线段上
            if (y == y1 && y == y2 && x >= Math.min(x1, x2) && x <= Math.max(x1, x2)) {
                return true;
            }
            //判断y坐标是否在范围内，该判断解决了点射线刚刚好经过多边形的点情况  TODO后面需要补充原理
            if ((y > y1 && y <= y2) || (y > y2 && y <= y1)) {
                //点x轴方向射线与线段的交集
                double tmpX = x1 + (x2 - x1) * (y - y1) / (y2 - y1);
                //如果需要忽略浮点数计算导致精度丢失的问题，可以通过添加容差后判断值是否在容差范围
                if (x == tmpX) {
                    return true;
                }
                if (x < tmpX) {
                    in = !in;
                }
            }
        }
        return in;
    }

参考：

  • 原代码实现应该有bug https://www.cnblogs.com/sunsky303/p/16468234.html