平面几何：判断点是否在多边形内（射线法）
平面几何：判断点是否在多边形内（射线法）
大家好，我是前端西瓜哥。
之前我们讲解了如何利用叉乘 判断点是否在凸多边形内。但该算法限制较大，多边形必须为凸多变形。
最近我的图形编辑器又新增了星形图形，然而这个星形又不是凸多边形。
于是我再基于射线法，实现一个较通用的算法，支持判断点是否在任意多边形内。
实现后的图形拾取效果如下。
射线法原理
这里我们用射线法来实现。
原理很简单，从点引出一条射线，计算射线和多边形的交点数量。
交点数如果是奇数，说明点在多边形内；如果是偶数，则点不在多边形内。
背后的原因是，交点刚好把这条射线切割为 “...内-外-内-外” 这样交替的子区域。奇数的时候，目标点刚好在 “内” 的子区域中；而偶数的时候则是在 “外”。
这里我们讨论的是非自交的多边形。但该算法在特定的自交多边形也是适用的。
自交会将多边形切割为多个区域，所以我们通常需要指定 填充规则，确定哪些区域需要填充，哪些区域不需要填充。
基于射线法的实现只适用其中使用了 奇偶规则 的自交多边形。
实现思路
这里假设坐标系为 y 轴向下，x 轴向右。
首先我们要找一个方向做射线。
射线方向没有要求，通常选择水平或垂直方向的射线，能够有效减少计算量。
这里我们选择 向右的射线。
然后就是遍历多边形的所有边，判断边线段和射线是否有交点，有交点就给相交数 count 加 1。
for (let i = 0; i < polygon.length; i++) {
let a = polygon[i];
let b = polygon[(i + 1) % polygon.length];
// 拿到边的两个端点 a 和 b，接着会判断是否和射线相交。
}
拿到边的两个端点 a 和 b。我们调整一下 a 和 b 的位置，确保 a 是上方的点，b 是下方的点。
if (a.y > b.y) {
[a, b] = [b, a]; // 交换位置
}
这样做是避免多余的分类讨论。
然后我们判断射线是否在边的 y 范围内：a.y 是否小于等于目标点的 y 值，且 b 大于目标点的 y 值。
if (a.y <= pt.y && b.y > pt.y) {
// ...
}
这里 b.y > pt.y 不是大于等于，而是大于，剔除了等于的情况。
这是因为我们要处理一些特殊情况，就是 射线刚好穿过多边形的顶点的情况。
如果等于也算的话，会导致穿过一个点变成了穿过两个点的效果，最后结果错误。
如果 y 在线段范围内，我们再判断 目标点是否在边的左侧。
判断左右？是不是觉得这个问题很熟悉呢。没错，又是你，叉积。之前判断 点在凸多边形内 也用到。
关于叉积，这里就不再展开讲了，说太多了。
我们求 a 到 b，和 a 到 目标点这两个向量的叉积。
如果叉积为 0，说明是特殊情况：点在边上。此时不用继续遍历，直接返回 true（或 false）。
如果叉积是正数，说明目标点在边的左侧，交点数 count 加 1。
if (a.y <= pt.y && b.y > pt.y) {
// 求 a 到 b，和 a 到 目标点这两个向量的叉积
const crossProduct =
(pt.x - a.x) * (b.y - a.y) - (b.x - a.x) * (pt.y - a.y);
// 点在边上，直接返回 true
if (crossProduct === 0) {
return true;
}
// 点在边的左侧，交点数+1
if (crossProduct > 0) {
count++;
}
}
遍历结束后，判断 count 的是否奇数。
return count % 2 === 1;
完整代码实现
const isPointInPolygon = (polygon, pt) => {
let count = 0;
for (let i = 0; i < polygon.length; i++) {
let a = polygon[i];
let b = polygon[(i + 1) % polygon.length];
if (a.y > b.y) {
[a, b] = [b, a];
}
if (a.y <= pt.y && b.y > pt.y) {
const crossProduct =
(pt.x - a.x) * (b.y - a.y) - (b.x - a.x) * (pt.y - a.y);
if (crossProduct === 0) {
return true;
}
if (crossProduct > 0) {
count++;
}
}
}
return count % 2 === 1;
};
其它
对于该算法，有一些可以调整的点：
- 可以将交点数变量 count 换成一个默认为 false 的布尔值变量，每当找到一个交点做一个取反；
- 可以不交换线段两点的位置，但对应的判断会变成
(a.y > y) != (b.y > y)和crossProduct > 0) != (b.y < a.y)这些，但可读性较差。
如果进行上述调整，我们会得到另一种风格的写法：
const isPointInPolygon = (polygon, pt) => {
let isIn = false;
for (let i = 0; i < polygon.length; i++) {
const a = polygon[i];
const b = polygon[(i + 1) % polygon.length];
if (a.x === pt.x && a.y === pt.y) {
return true;
}
if (a.y > pt.y !== b.y > pt.y) {
const crossProduct =
(pt.x - a.x) * (b.y - a.y) - (b.x - a.x) * (pt.y - a.y);
if (crossProduct === 0) {
return true;
}
if (crossProduct < 0 != b.y < a.y) {
isIn = !isIn;
}
}
}
return isIn;
};
结尾
我是前端西瓜哥，关注我，学习更多平面几何知识。