算法 - PNPoly解决点到多边形的距离问题

最近做了一个算法题【盒马配货】：

（题目大意）盒马店的配送范围由一些点组成的多边形确定，给定一个点判断其是否在配送范围内，若在，则此点不需要挪动，打印"no 0"；若不在，则给出此点需要挪动到配送范围的最短距离，打印"yes 距离"。

如何求解点到多边形的距离

此题求解需要解决两个问题：

点到多边形的边的最短距离。
点是否包含在多边形内。

点到边的距离

计算点到多边形最短距离的基本原理是：依次计算点到多边形每条边的距离，然后筛选出最短距离。

image

如下图，假设AB为多边形的一条边，现在求点P到AB的距离。

image

根据向量内积公式(\vec a \cdot \vec b=|a||b|\cos\theta)，我们可以推出：

image

根据以上公式，我们可以求出t，进而求出点D的坐标，最终PD的长度就很容易求得了。

但是还有一些边界条件需要注意，即最终D点不是落在AB上，有以下三种情况：

t < 0，D在BA延长线上，此时最短距离取PA；
0 <= t <= 1，D在AB上，此时最短距离取PD；
t > 1，D在AB延长线上，此时最短距离取PB；

image

Java实现代码如下：

private static double pointToSegmentDist(double px, double py, double ax, double ay, double bx, double by) {
    double ABx = bx - ax;
    double ABy = by - ay;
    double APx = px - ax;
    double APy = py - ay;

    double AB_AP = ABx * APx + ABy * APy;
    double distAB2 = ABx * ABx + ABy * ABy;

    double Dx = ax, Dy = ay;
    if (distAB2 != 0) {
        double t = AB_AP / distAB2;
        if (t >= 1) {
            Dx = bx;
            Dy = by;
        } else if (t > 0) {
            Dx = ax + ABx * t;
            Dy = ay + ABy * t;
        } else {
            Dx = ax;
            Dy = ay;
        }
    }

    double PDx = Dx - px, PDy = Dy - py;

    return Math.sqrt(PDx * PDx + PDy * PDy);
}

点是否包含在多边形内

根据W. Randolph Franklin 提出的PNPoly算法，只需区区几行代码就解决了这个问题。

假设配送范围多边形的点横纵坐标分别存放在两个数组xs、ys里，(x,y)表示配送点的坐标，先贴代码：

private static void polygon(double[] xs, double[] ys, double x, double y) {
    boolean contained = false; // 点是否包含在多边形内

    double xMin = Arrays.stream(xs).min().getAsDouble();
    double xMax = Arrays.stream(xs).max().getAsDouble();
    double yMin = Arrays.stream(ys).min().getAsDouble();
    double yMax = Arrays.stream(ys).max().getAsDouble();

    if (x > xMax || x < xMin || y > yMax || y < yMin) {
        contained = false;
    }
    // 核心算法部分
    int N = xs.length;
    double dist = Double.MAX_VALUE;
    for (int i = 0, j = N - 1; i < N; j = i++) {
        if (((ys[j] > y) != (ys[i] > y))
            && (x < (xs[j] - xs[i]) * (y - ys[i]) / (ys[j] - ys[i]) + xs[i])) {
            contained = !contained;
        }
        dist = Math.min(dist, pointToSegmentDist(x, y, xs[i], ys[i], xs[j], ys[j]));
    }
    System.out.println(contained ? "no 0" : "yes" + " " + dist);
}

首先，我们需要取得该数组在横坐标和纵坐标的最大值和最小值，根据这四个点算出一个四边型，判断目标坐标点是否在这个四边型之内，如果在这个四边型之外，那可以跳过后面较为复杂的计算，直接返回false。

if (x > xMax || x < xMin || y > yMax || y < yMin) {
    contained = false;
}

接下来是核心算法部分：

for (int i = 0, j = N - 1; i < N; j = i++) {
    if (((ys[j] > y) != (ys[i] > y))
        && (x < (xs[j] - xs[i]) * (y - ys[i]) / (ys[j] - ys[i]) + xs[i])) {
        contained = !contained;
    }
}

每次计算都涉及到相邻的两个点和待测试点，然后考虑两个问题：

被测试点的纵坐标testy是否在本次循环所测试的两个相邻点纵坐标范围之内，即

ys[i] <y < ys[j]

或者

ys[j] <y < ys[i]。
待测点test是否在i,j两点之间的连线之下（相交判断）。

每次这两个条件同时满足的时候我们把返回的布尔量取反。

这个表达式的意思是说，随便画个多边形，随便定一个点，然后通过这个点水平划一条线，先数数看这条横线和多边形的边相交几次（可先排除那些不相交的边，即第一个判断条件），然后再数这条横线穿越多边形的次数是否为奇数，如果是奇数，那么该点在多边形内，如果是偶数，则在多边形外（射线法）。

点在直线下 - 相交判断

如下图，ab与过p点的水平线相交于c，

image

则有：

image

Java代码实现：

if (((ys[j] > y) != (ys[i] > y))
    && (x < (xs[j] - xs[i]) * (y - ys[i]) / (ys[j] - ys[i]) + xs[i])) {
    contained = !contained;
}

点在多边形内部 - 射线法

判断点是否在多边形内，可以从这个点做一条射线，计算它跟多边形边界的交点个数，如果交点个数为奇数，那么点在多边形内部，否则点在多边形外。参考https://www.cnblogs.com/anningwang/p/7581545.html

参考

https://wrf.ecse.rpi.edu//Research/Short_Notes/pnpoly.html

https://www.cnblogs.com/anningwang/p/7581545.html

https://jingsam.github.io/2016/09/26/polydist.html

（完）