大家好,我是前端西瓜哥。
之前我们讲解了如何利用叉乘 判断点是否在凸多边形内。但该算法限制较大,多边形必须为凸多变形。
最近我的图形编辑器又新增了星形图形,然而这个星形又不是凸多边形。
于是我再基于射线法,实现一个较通用的算法,支持判断点是否在任意多边形内。
实现后的图形拾取效果如下。
这里我们用射线法来实现。
原理很简单,从点引出一条射线,计算射线和多边形的交点数量。
交点数如果是奇数,说明点在多边形内;如果是偶数,则点不在多边形内。
背后的原因是,交点刚好把这条射线切割为 “...内-外-内-外” 这样交替的子区域。奇数的时候,目标点刚好在 “内” 的子区域中;而偶数的时候则是在 “外”。
这里我们讨论的是非自交的多边形。但该算法在特定的自交多边形也是适用的。
自交会将多边形切割为多个区域,所以我们通常需要指定 填充规则,确定哪些区域需要填充,哪些区域不需要填充。
基于射线法的实现只适用其中使用了 奇偶规则 的自交多边形。
这里假设坐标系为 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;
};
对于该算法,有一些可以调整的点:
(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;
};
我是前端西瓜哥,关注我,学习更多平面几何知识。