平面几何：判断点是否在凸多边形内

前端西瓜哥

发布于 2024-05-15 18:20:42

730

发布于 2024-05-15 18:20:42

文章被收录于专栏：前端西瓜哥的前端文章前端西瓜哥的前端文章

大家好，我是前端西瓜哥。

今天我们来实现判断点是否在凸多边形内的算法。

需求

提供一个凸多边形（用点数组表示），以及一个点，判断这个点是否在多边形内。

凸多边形，指的边不存在自我相交，且内角小于 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 即可。