algorithm - 圆内两点之间的距离

Question

我在一个圆圈内得到 2 分。我必须在圆上找到一个点（不是在里面，不是在外面），这样给定的 2 个点和我找到的点之间的距离之和是最小的。我只需要找到最小距离，而不是点的位置。

Answer 1

这是一个最小化问题：

minimize sqrt((x1-x0)^2 + (y1-y0)^2) +  sqrt((x2-x0)^2 + (y2-y0)^2)
             ^                                         ^
     (distance from point1)                (distance from point 2)

subject to constraints:
x1 = C1
y1 = C2
x2 = C3
x4 = C4
x0^2 + y0^2 = r^2 
(assuming the coordinates are already aligned to the center of the circle as (0,0)).
(C1,C2,C3,C4,r) are given constants, just need to assign them.

分配 x1,y1,x2,y2 后 - 您会遇到一个包含 2 个变量 (x0,y0) 和一个约束的最小化问题。最小化问题可以使用拉格朗日乘数来解决。

Answer 2

令 (x1, y1) 和 (x2, y2) 为圆内的点，(x, y) 为圆上的点，r 为圆的半径。您的问题简化为拉格朗日条件极值问题，即：

极值函数：

f(x, y) = sqrt((x-x1)^2 + (y-y1)^2) + sqrt((x-x2)^2 + (y-y2)^2)

条件：

g(x, y) = x^2 + y^2 = r^2  (1)

引入一个辅助功能（参考）：

Λ(x, y, λ) = f(x, y) + λ(g(x, y) - r^2)

令∂Λ / ∂x = 0，我们有：

(x-x1)/sqrt((x-x1)^2 + (y-y1)^2) + (x-x2)/sqrt((x-x2)^2 + (y-y2)^2) + 2λx = 0 (2)

令∂Λ / ∂y = 0，我们有：

(y-y1)/sqrt((x-x1)^2 + (y-y1)^2) + (y-y2)/sqrt((x-x2)^2 + (y-y2)^2) + 2λy = 0 (3)

现在我们有 3 个变量（即 x、y 和 λ）和 3 个方程（即 (1)、(2) 和 (3)），所以它是可解的。

请注意，应该有两个解决方案（除非两个内点恰好是圆的中心）。一个是最小值（这是您需要的），另一个是最大值（将被忽略）。

Answer 3

只是另一种方法（更直接）：

为简单起见，假设圆在 (0,0) 处，半径为 r，并假设两个点是 P1(x1,y1) 和 P2(x2,y2)

我们可以计算这两个点的极角，假设它们显然是alpha1和alpha2，那么在圆上并且到P1和P2的距离之和最小的点在alpha1和alpha2组成的圆扇区内

同时，该扇区内圆上的点与P1和P2之间的距离之和是二次函数。因此，可以使用三分法找到最小距离。