平面几何算法：求点到直线和圆的最近点

前端西瓜哥

发布于 2024-03-04 11:46:02

1630

发布于 2024-03-04 11:46:02

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

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

今天我们来学习平面几何算法，求点到直线和圆的最近点。

这个方法还挺常用的。

比如精细的图形拾取（尤其是一些没有填充只有描边的图形）。如果光标点到最近点的距离小于某个阈值，计算图形就算被选中。

还比如图形编辑器的实体吸附、极轴还有正交，当点靠近某条直线时，绘制点会吸附到这条直线的最近点上。

求最近点，起名通常为 getClosestPoint（最近点），或者 project（投影）。

在介绍投影算法之前，我们先学习一个前置知识点：线性插值。

线性插值

我们只用两个点就表示一段线段，这是因为可以基于这两个点，通过不断插值的方式得到所有中间点，将这些点绘制出来，线段也就绘制出来了。

你可以联想一下 flash 动画的补间动画。

假设有两个点 p0 和 p1，求在 p0 和 p1 线段上的点 p。

这个 p 在 p0 到 p1 方向，比例为 t 的位置（即 t = 距离(p0, p) / 距离(p0, p1)），t 的范围在 0 到 1 之间。

则有公式：

// p 位置的计算过程
const x = x0 + (x1 - x0) * t
const y = y0 + (y1 - y0) * t

这个可以从向量的角度来理解。

向量等于其对应的（1）单位方向向量，乘以（2）向量的模（向量的长度）。

乘以 t 等价于：p0 到 p1 向量先除以 距离(p0, p1) 得到一个单位方向向量，然后乘以 距离(p0, p)，得 p0 到 p 的向量，这个向量就是 偏移值，和点 p0 相加就能得到插值点 p 了。

线性插值在数学、计算机图形学领域被广泛使用，比如贝塞尔曲线，线性贝塞尔曲线就是线性插值，还有就是本文后面会讲的最近点算法。

如果让多个线段依次相连，并同时插值，产生的点继续相连，再插值，直到点只有一个。这样套娃就能变成 N 阶贝塞尔曲线，如下图：

在上面的讨论，我限定了 t 的范围：0 到 1。

这个其实只在两点之间补全线条会限制，实际上 t 可以是任意值（包括负值）。

当然在平面几何上就会表现为超出线段的范围，但它仍然符合它是在一条直线上的特征，如下图：

点到直线的最近点

已知直线的两点 p0、p1 组成的直线上，距离点 p 最近的最近点。

解法是使用线性插值，为此需要计算出 t。

t 是什么？p0 到最近点的长度，除以 p0 到 p1 的长度。

这里 p0 到最近点的长度是不知道的，我们可以使用 点积公式 求p0 到 p 向量，到 p0 到 p1 向量上的投影。

点积公式为：

A·B = |A| |B| cos(θ)

|A| 表示向量 A 的长度，可以用勾股定理计算：

const distance = (p1, p2) => {
  const dx = p2.x - p1.x;
  const dy = p2.y - p1.y;
  return Math.sqrt(dx * dx + dy * dy);
};

A·B 为两个向量的 x 和 y 各自相乘，然后相加。

|A| cos(θ)是 A 到 B 的投影，即：

|A| cos(θ) = A·B / |B|

前面我们说了，p0 到最近点的长度，除以 p0 到 p1 的长度。所以 t 为：

 t 
= |A| cos(θ) / |B|
= A·B / (|B| |B|)

投影是有方向的，所以 t 可能是负值。

注意直线两端的点相同的情况，此时会退化为一个点。两个不同点才能确定一条唯一直线。

代码实现

const closestPointOnLine = (
  p1: Point,
  p2: Point,
  p: Point,
  /** 是否可以在线段之外 */
  canOutside = false,
) => {
  // p1 和 p2 相同退化为一个点的特殊情况
  if (p1.x === p2.x && p1.y === p2.y) {
    return {
      t: 0,
      d: distance(p1, p),
      point: { x: p1.x, y: p1.y },
    };
  }
  
  // A 就是 (dx, dy)
  const dx = p2.x - p1.x;
  const dy = p2.y - p1.y;

  // t = A·B / (|B| |B|)
  let t = ((p.x - p1.x) * dx + (p.y - p1.y) * dy) / (dx * dx + dy * dy);
  
 // t 是否只能在 0 到 1 的范围
  if (!canOutside) {
    t = Math.max(0, Math.min(1, t));
  }
  // 线性插值
  const closestPt = {
    x: p1.x + t * dx,
    y: p1.y + t * dy,
  };
  return {
    t,
    d: distance(p, closestPt),
    point: closestPt,
  };
};

返回值除了最近点的坐标，还额外返回了 t，以及最短距离 d。

顺带返回 t，是因为有时候我们要保存比例值，或用作复杂算法的后续运算。

最短距离 d 可不返回，在外面需要时再算。d 可用于实现高精度拾取算法，当 d 小于某个阈值时，认为线条被选中。

可视化交互

我做了可视化交互。

demo 地址为：

https://codepen.io/F-star/pen/RwdzMwz

点到圆上的最近点

圆和求直线最近点一样，需要求 t。

对于圆，t 为 radius / distance(center, p)。

这里要注意除数不能为 0，如果 distance(center, p) 为 0，t 直接赋值为 0。

在这里 t 是不会为负数的，因为是从圆心往外辐射，没法取一个负值。

算法实现

const closestPointOnCircle = (
  center,
  radius,
  p,
) => {
  const dx = p.x - center.x;
  const dy = p.y - center.y;
  const dist = Math.sqrt(dx * dx + dy * dy);
  const t = dist === 0 ? 0 : radius / dist;
  const closestPt = {
    x: center.x + dx * t,
    y: center.y + dy * t,
  };
  return {
    d: Math.abs(dist - radius),
    point: closestPt,
  };
};