资讯

历史

科技

环境与自然

成长

游戏

财经

文学与艺术

美食

健康

家居

文化

情感

汽车

三农

军事

旅行

运动

教育

生活

星座命理

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

创作时间:

作者:

@小白创作中心

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

引用

来源

https://cloud.tencent.com/developer/article/2393520

发布于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 之间。

则有公式：

代码语言：javascript

代码运行次数：0

复制

Cloud Studio代码运行


// 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 向量上的投影。

点积公式为：

代码语言：javascript

代码运行次数：0

复制

Cloud Studio代码运行


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

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

代码语言：javascript

代码运行次数：0

复制

Cloud Studio代码运行


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 的投影，即：

代码语言：javascript

代码运行次数：0

复制

Cloud Studio代码运行


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

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

代码语言：javascript

代码运行次数：0

复制

Cloud Studio代码运行


 t  

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

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

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

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

代码实现

代码语言：javascript

代码运行次数：0

复制

Cloud Studio代码运行


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 是不会为负数的，因为是从圆心往外辐射，没法取一个负值。

算法实现

代码语言：javascript

代码运行次数：0

复制

Cloud Studio代码运行


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,  

  };  

};