最近做了一个算法题【盒马配货】:
(题目大意)盒马店的配送范围由一些点组成的多边形确定,给定一个点判断其是否在配送范围内,若在,则此点不需要挪动,打印"no 0";若不在,则给出此点需要挪动到配送范围的最短距离,打印"yes 距离"。
此题求解需要解决两个问题:
计算点到多边形最短距离的基本原理是:依次计算点到多边形每条边的距离,然后筛选出最短距离。
如下图,假设AB为多边形的一条边,现在求点P到AB的距离。
根据向量内积公式(\vec a \cdot \vec b=|a||b|\cos\theta),我们可以推出:
根据以上公式,我们可以求出t,进而求出点D的坐标,最终PD的长度就很容易求得了。
但是还有一些边界条件需要注意,即最终D点不是落在AB上,有以下三种情况:
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; }}
每次计算都涉及到相邻的两个点和待测试点,然后考虑两个问题:
每次这两个条件同时满足的时候我们把返回的布尔量取反。
这个表达式的意思是说,随便画个多边形,随便定一个点,然后通过这个点水平划一条线,先数数看这条横线和多边形的边相交几次(可先排除那些不相交的边,即第一个判断条件),然后再数这条横线穿越多边形的次数是否为奇数,如果是奇数,那么该点在多边形内,如果是偶数,则在多边形外(射线法)。
如下图,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