從點到橢圓弧的最短距離的算法

Question

我想找到一個計算任意點和圓弧之間的最短距離的一般方法，其中圓弧是橢圓邊界的90度部分，橢圓的軸線都對準笛卡爾座標軸。我在2D中工作，所以點和橢圓都是共面的。如果這個點與圓弧在同一象限內，相對於橢圓的中心，那麼我相信問題與計算從一個點到整個橢圓邊界上​​任何地方的距離是一樣的，對此，相當直接方法（例如http://www.geometrictools.com/Documentation/DistancePointEllipseEllipsoid.pdf）。

在圖中，如果點位於x1的左側或x2的右側或y1下方，則問題很簡單。

但是，我不知道如果點P如圖所示該怎麼辦。

Answer 1

我通常使用省略號這樣的：

1. 樣品由N點弧

   爲90程度塊使用N>=8那麼賈寶玉不要錯過一些

2. 找到的最近點由N點

   覆蓋面積圍繞該點

3. 樣品弧從以前到下一個點

4. 遞歸循環，＃2

   各迭代/遞歸增加準確性。如果達到所需的精度範圍（採樣面積足夠小）或精度限制可變（以避免FPU下溢），則停止。

[注意事項]

這適用於任何橢圓弧不僅僅是軸線對齊。

[EDIT1] C++示例

double x0,y0,rx,ry,a0,a1; // elliptic arc center,semi-axises,start/end angles CW 
void ellarc_closest_point(double &x_out,double &y_out,double x_in,double y_in) 
    { 
    int e,i; 
    double ll,l,aa,a,da,x,y,b0,b1; 
    while (a0>=a1) a0-=pi2;     // just make sure a0<a1 
    b0=a0; b1=a1; da=(b1-b0)/25.0;   // 25 sample points in first iteration 
    ll=-1; aa=a0;       // no best solution yet 
    for (i=0;i<3;i++)      // recursions more means more accurate result 
     { 
     // sample arc a=<b0,b1> with step da 
     for (e=1,a=b0;e;a+=da) 
      { 
      if (a>=b1) { a=b1; e=0; } 
      // elliptic arc sampled point 
      x=x0+rx*cos(a); 
      y=y0-ry*sin(a);     // mine y axis is in reverse order therefore - 
      // distance^2 to x_in,y_in 
      x-=x_in; x*=x; 
      y-=y_in; y*=y; l=x+y; 
      // remember best solution 
      if ((ll<0.0)||(ll>l)) { aa=a; ll=l; } 
      } 
     // use just area near found solution aa 
     b0=aa-da; if (b0<a0) b0=a0; 
     b1=aa+da; if (b1>a1) b1=a1; 
     // 10 points per area stop if too small area already 
     da=0.1*(b1-b0); if (da<1e-6) break; 
     } 
    x_out=x0+rx*cos(aa); 
    y_out=y0-ry*sin(aa); // mine y axis is in reverse order therefore - 
    } 

和視覺輸出：

Answer 2

所以整個弧的是一個紅色的鯡魚。這是一個線性縮放回單位圓。所以你只需要找到從一個點到單位圓的最短距離。 （https://math.stackexchange.com/questions/103453/closest-point-to-a-unit-circle-from-a-point-inside-it）然後只需撤消比例並測量距離。

[編輯] Spektre]這顯然是錯誤的！

如果您發現最接近圓的一個點（在縮放空間中），這並不意味着這個點在重新縮放後（到橢圓空間）仍然是最接近的！見例如：