Point-In-Polygon边界包含异常：下界未纳入而上界已纳入

我在实现点-in-多边形的射线法（raycasting）时遇到了边界逻辑异常：多边形的下界坐标（含0的点）都没被判定为在多边形内，但上界坐标（含3的点）却被正确纳入。

我参考教程实现了射线法，通过统计射线与多边形边的交叉次数奇偶性来判断点是否在内部，遍历每条边时检查Y坐标和X坐标两个条件。用3×3的正方形做测试，遍历x∈[0,3]、y∈[0,3]的所有点后发现，理想状态下0-3范围内的所有点都应该被标记为在多边形内，但实际结果不符合预期。我尝试把条件中的<改为<=，问题依然存在。

测试代码 #

public class PIP {

    private final static int SIZE_X = 3;
    private final static int SIZE_Y = 3;

    public static void main(String[] args) {

        final Polygon polygon = new Polygon();
        polygon.addPoint(0, 0);
        polygon.addPoint(SIZE_X, 0);
        polygon.addPoint(SIZE_X, SIZE_Y);
        polygon.addPoint(0, SIZE_Y);

        for (int x = 0; x < SIZE_X + 1; x++) {
            for (int y = 0; y < SIZE_Y + 1; y++) {
                final boolean inPolygon = pointInPolygon(polygon, x, y);
                System.out.println("Point " + x + ", " + y + " Is In Polygon: " + inPolygon);
            }
        }
    }


    public static boolean pointInPolygon(Polygon polygon, int xp, int yp) {
        int numCross = 0;
        for (int i = 0, j = polygon.npoints - 1; i < polygon.npoints; i++) {

            final int x1 = polygon.xpoints[i];
            final int y1 = polygon.ypoints[i];
            final int x2 = polygon.xpoints[j];
            final int y2 = polygon.ypoints[j];

            if (((yp <= y1) != (yp <= y2)) && (xp <= x1 + ((yp - y1) / (y2 - y1)) * (x2 - x1))) {
                numCross += 1;
            }
            j = i;
        }
        return numCross % 2 == 1;
    }
}

代码输出 #

Point 0, 0 Is In Polygon: false
Point 0, 1 Is In Polygon: false
Point 0, 2 Is In Polygon: false
Point 0, 3 Is In Polygon: false
Point 1, 0 Is In Polygon: false
Point 1, 1 Is In Polygon: true
Point 1, 2 Is In Polygon: true
Point 1, 3 Is In Polygon: true
Point 2, 0 Is In Polygon: false
Point 2, 1 Is In Polygon: true
Point 2, 2 Is In Polygon: true
Point 2, 3 Is In Polygon: true
Point 3, 0 Is In Polygon: false
Point 3, 1 Is In Polygon: true
Point 3, 2 Is In Polygon: true
Point 3, 3 Is In Polygon: true

问题根源与修复 #

问题分析 #

1. 整数除法精度丢失：代码中(yp - y1)/(y2 - y1)是整数除法，非整数结果会被直接截断，导致X坐标判断出现偏差，比如垂直边的交点计算完全失效。
2. 边界点歧义：射线法本身对顶点、边上的点没有明确判定规则，原代码未单独处理这类情况，导致边界点被误判为外部。

修复方案 #

• 先单独判断点是否在多边形顶点或边上，直接返回true；
• 用交叉乘法替代除法，避免精度丢失，同时用long类型防止整数溢出；
• 调整射线法的交叉判断逻辑，统一边的坐标顺序，明确射线方向（向右水平射出）。

修正后的代码 #

import java.awt.Polygon;

public class PIP {

    private final static int SIZE_X = 3;
    private final static int SIZE_Y = 3;

    public static void main(String[] args) {

        final Polygon polygon = new Polygon();
        polygon.addPoint(0, 0);
        polygon.addPoint(SIZE_X, 0);
        polygon.addPoint(SIZE_X, SIZE_Y);
        polygon.addPoint(0, SIZE_Y);

        for (int x = 0; x < SIZE_X + 1; x++) {
            for (int y = 0; y < SIZE_Y + 1; y++) {
                final boolean inPolygon = pointInPolygon(polygon, x, y);
                System.out.println("Point " + x + ", " + y + " Is In Polygon: " + inPolygon);
            }
        }
    }

    public static boolean pointInPolygon(Polygon polygon, int xp, int yp) {
        // 判断点是否在顶点上
        for (int i = 0; i < polygon.npoints; i++) {
            if (polygon.xpoints[i] == xp && polygon.ypoints[i] == yp) {
                return true;
            }
        }

        // 判断点是否在边上
        for (int i = 0, j = polygon.npoints - 1; i < polygon.npoints; i++) {
            int x1 = polygon.xpoints[i];
            int y1 = polygon.ypoints[i];
            int x2 = polygon.xpoints[j];
            int y2 = polygon.ypoints[j];

            // 叉积为0说明点与边共线，再判断坐标是否在边的 bounding box 内
            if (crossProduct(xp - x1, yp - y1, x2 - x1, y2 - y1) == 0) {
                if (Math.min(x1, x2) <= xp && xp <= Math.max(x1, x2) &&
                    Math.min(y1, y2) <= yp && yp <= Math.max(y1, y2)) {
                    return true;
                }
            }
            j = i;
        }

        // 射线法判断内部点
        int numCross = 0;
        for (int i = 0, j = polygon.npoints - 1; i < polygon.npoints; i++) {
            int x1 = polygon.xpoints[i];
            int y1 = polygon.ypoints[i];
            int x2 = polygon.xpoints[j];
            int y2 = polygon.ypoints[j];

            // 统一边的y坐标顺序，简化判断逻辑
            if (y1 > y2) {
                int temp = y1; y1 = y2; y2 = temp;
                temp = x1; x1 = x2; x2 = temp;
            }

            // 射线向右水平射出，判断是否穿过边
            if (yp > y1 && yp <= y2) {
                // 交叉乘法计算交点位置，避免除法
                long cross = (long)(xp - x1) * (y2 - y1) - (long)(yp - y1) * (x2 - x1);
                if (cross < 0) { // 交点在点的右侧，计数加1
                    numCross++;
                }
            }
            j = i;
        }

        return numCross % 2 == 1;
    }

    // 计算二维叉积：(a.x*b.y - a.y*b.x)
    private static long crossProduct(int ax, int ay, int bx, int by) {
        return (long)ax * by - (long)ay * bx;
    }
}

关键修改说明 #

1. 顶点与边的前置判断：直接处理边界点，避免射线法的歧义；
2. 交叉乘法替代除法：用整数运算实现交点判断，既保证精度又避免浮点运算的性能损耗；
3. 统一边的坐标顺序：简化射线与边的交叉判断逻辑，减少条件分支。

内容的提问来源于stack exchange，提问作者Zenz