algorithm - 円の 2 点間の距離

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

ちょうど別のアプローチ（より直接的です）：

簡単にするために、円が半径 r の (0,0) にあり、2 つの点が P1(x1,y1) と P2(x2,y2) であると仮定します。

これらの 2 点の極角を計算できます。それらが alpha1 と alpha2 であると仮定すると、明らかに、円上にあり、P1 と P2 までの距離の合計が最小である点は、alpha1 と alpha2 で構成される円形セクター内にあります。

一方、その扇形内の円上の点と P1 および P2 との間の距離の合計は 2 次関数です。したがって、最小距離は三分法を使用して見つけることができます。