最近做了一个算法题【盒马配货】：
（题目大意）盒马店的配送范围由一些点组成的多边形确定，给定一个点判断其是否在配送范围内，若在，则此点不需要挪动，打印"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
（完）
网友评论