多边形内点边界包含/不包含

Question

我正在尝试解决多边形中的点问题，但我面临的问题是不包含多边形的下限，但包含上限。

我一直在遵循 inside code 的教程来确定一个点是否位于多边形的边界内，该多边形使用光线投射并计算该点是否穿过轮廓（un）甚至次数以确定该点是否位于外部或多边形内部。这是通过检查 2 个条件来实现的。一个条件是 Y 坐标，另一个条件是 X 坐标在多边形的每条边上循环。

在下面的示例中，我使用的多边形是大小为 3X3 的正方形。我正在循环所有坐标以检查它们是否在正方形内，但我面临的问题是不包括包含“0”的坐标，但包含包含“3”的坐标。理想情况下，从 x 0-3 和 y 0-3 范围内的所有坐标都应标记为在多边形内。我已将条件从 '<' to '<=' to include points on the contour instead of inside the polygon but to no avail.

更改为

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

Answer 1

我通过首先检查该点是否在多边形的边缘（线）上而不是该点是否在多边形内部来解决这个问题。这是通过检查当前点和边缘线的叉积是否为 0 来实现的，这意味着该点在线上。其次检查当前点的坐标是否在边缘两个点的范围内。请参阅 AnT 与俄罗斯站在一起的回答这里。