大家好,我是前端西瓜哥。
今天我们来实现判断点是否在凸多边形内的算法。
提供一个凸多边形(用点数组表示),以及一个点,判断这个点是否在多边形内。
凸多边形,指的边不存在自我相交,且内角小于 180 度的多边形。
我们需要这个算法实现图形拾取,判断鼠标是否落在图形上。
在之前的 求两向量的夹角的文章 中我提到过,对于两个向量,我们可以利用叉积的符合右手定则,判断两个向量的位置关系。
在屏幕坐标系(x 轴向右,y 轴向下)下,对于向量 a 和 b 的叉积,若结果为正,则 b 在 a 的右侧;若结果为负,则 b 在 a 的左侧。
特殊的,如果结果为 0,表示两向量在同一方向上,属于边缘场景。你可以认为属于左边,或者属于右边。
我们计算凸多边形的所有边向量,和边向量起点到起点的叉乘,记为点相对边的方向。
如果方向都是左边,或都是右边,则点在凸多边形内,否则点不在凸出变形内。
特殊的,对于点在某条边上,它介于在和不在凸多边形上的中间态,属于边缘情况,读者可自行定义。
代码基于 TypeScript 实现。
const isPointInConvexPolygon = (polygon: IPoint[], point: IPoint) => {
let dir: number | undefined = undefined;
for (let i = 0; i < polygon.length; i++) {
const start = polygon[i];
const end = polygon[(i + 1) % polygon.length];
const a = {
x: end.x - start.x,
y: end.y - start.y,
};
const b = {
x: point.x - start.x,
y: point.y - start.y,
};
// 通过叉积公式得到点在边的方向
const currDir = Math.sign(a.x * b.y - a.y * b.x);
// 点在边上,跳过
if (currDir === 0) {
continue;
}
if (dir === undefined) {
dir = currDir;
}
// 发现有方向不一样了,点不在凸多边形上
else if (dir !== currDir) {
return false;
}
}
// 点都在边的同一方向上
return true;
};
这里我认为点在边上,也算在凸多边形上,所以当叉积计算出了 0,会在遍历时跳过它。
如果你认为这种情况属于不在凸多边形上,直接结束循环并返回一个 false 即可。
我是前端西瓜哥,关注我,学习更多平面几何知识。