optimization - 找到最小距离

Question

我需要在给定的圆（或曲线）上找到一个或多个点，以最小化 d0+d1？曲线的半径和中心分别为 (0,0) 和 'r'，并且点 A 和 B 的坐标是已知的。假设 A=(x1,y1) 和 B=(x1,-y1) 和 r> sqrt(x1^2+y1^2) 。C 是圆的未知点，应该最小化长度 d0+d1 d0 - 圆上 A 到 C 之间的距离 d1 - 圆上 B 到 C 之间的距离

C点沿圆周运动。我需要在给定的圆（或曲线）上找到一个或多个点，以最小化 d0+d1？

Answer 1

如果线 AB 与圆相交，则 C 是该交点（请注意，可以有两个交点并且都给出相等的距离d0+d1！）。

如果 AB 不与圆相交，则 C 是圆上的点，与离圆心最近的直线 AB 上的点相交的假想线。

网上有很多关于如何在一条直线上找到离另一个点最近的点，以及如何找到两条直线的交点的文章，这将解决第二种情况。对于第一种情况，您可以谷歌“线圆交叉点”

Answer 2

一般情况很复杂，但特殊情况

A=(x1,y1)并且B=(x1,-y1)和r > sqrt(x1^2+y1^2)

以圆心为原点的圆具有足够的对称性，至少在某些情况下可以使解决方案变得可访问。我假设A ≠ B, （等效地y1 ≠ 0），否则这个问题对于一个圈子来说是微不足道的。

让是点和dist(P,Q)之间的欧几里得距离。连接和的（闭合）线段是点的轨迹PQABP

dist(P,A) + dist(P,B) = dist(A,B)

对于D > dist(A,B), 点的轨迹

f(P) = dist(P,A) + dist(P,B) = D

是一个椭圆E(D)，其焦点是A和B。设P是圆上的一个点 和D = f(P)。

• 如果圆的切线和椭圆的切线E(D)在该点P不重合，P则既不是局部最小值也不是局部最大值f限于圆。
• 如果切线重合，并且圆的曲率大于E(D)in的曲率P，则P是f限制在圆内的孤立局部最大值。
• 如果切线重合，并且圆的曲率小于E(D)in的曲率P，则P是f限制在圆内的孤立局部最小值。
• 如果切线重合并且圆的曲率等于E(D)in的曲率P，则
  • P是一个孤立的局部最小值，f如果dist(P,A) = dist(P,B)，
  • P既不是局部最大值也不是局部最小值，f否则限制在圆内。

首先，如果x1 = 0，很容易看出（在几何上不明显的情况下）最小化圆f上的点是具有 x 坐标的点0，即P1 = (0,r)和P2 = (0,-r)。[如果是这样，那甚至是真的r² ≤ x1² + y1²。]

现在，假设x1 ≠ 0不失一般性x1 > 0。那么很明显，P = (x,y)最小化圆上的一个点f必须有x > x1。通过情况的对称性，该点R = (r,0)必须是局部最小值或f限制在圆内的局部最大值。

计算fnear的行为R，发现这R是一个局部最小值当且仅当

r ≥ (x1² + y1²) / x1

由于R是曲率最小的点E(f(R))（并且切线R与E(f(R))圆重合），R因此也是全局最小值。

如果r < (x1² + y1²) / x1，则R是f限制在圆内的局部最大值。然后f在圆上有两个全局最小值，具有相同的 x 坐标。不幸的是，我没有一个很好的公式来计算它们，所以我不能提供比迭代搜索更好的方法。