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

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

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

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

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

点到边的距离

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

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

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

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

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

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

Java实现代码如下:

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
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)表示配送点的坐标,先贴代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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。

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

接下来是核心算法部分:

1
2
3
4
5
6
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,

则有:

Java代码实现:

1
2
3
4
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

(完)