算法 - PNPoly解决点和多边形问题
算法 - PNPoly解决点和多边形问题
最近做了一个算法题【盒马配货】：
（题目大意）盒马店的配送范围由一些点组成的多边形确定，给定一个点判断其是否在配送范围内，若在，则此点不需要挪动，打印"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实现代码如下：
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]<="" p="" style="box-sizing: border-box;"> 或者 ys[j]<y <="" ys[i]。<="" p="" style="box-sizing: border-box;">
- 待测点test是否在i,j两点之间的连线之下（相交判断）。
每次这两个条件同时满足的时候我们把返回的布尔量取反。
这个表达式的意思是说，随便画个多边形，随便定一个点，然后通过这个点水平划一条线，先数数看这条横线和多边形的边相交几次（可先排除那些不相交的边，即第一个判断条件），然后再数这条横线穿越多边形的次数是否为奇数，如果是奇数，那么该点在多边形内，如果是偶数，则在多边形外（射线法）。
点在直线下 - 相交判断
如下图，ab与过p点的水平线相交于c，
则有：
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
腾讯云开发者
