math - 点到椭圆弧的最短距离算法

Question

我试图找到一种通用方法来计算任意点和圆弧之间的最短距离，其中圆弧是椭圆边界的 90 度部分，并且椭圆的轴都与笛卡尔轴对齐。我在 2D 中工作，所以点和椭圆都是共面的。如果该点与圆弧在同一个象限内，相对于椭圆的中心，那么我认为问题与计算从一个点到整个椭圆边界上​​任意位置的距离相同，其中有相当简单的方法(例如 http://www.geometrictools.com/Documentation/DistancePointEllipseEllipsoid.pdf )。

在图中，如果点在 x1 的左侧或 x2 的右侧或 y1 的下方，那么问题就很简单了。

但是，如果点P如图所示，我不知道该怎么办。

Answer 1

我通常使用省略号:

1. 用 N 点对圆弧进行采样

   对于 90 度 block 使用 N>=8 所以你不会错过任何东西

2. 找到最近的点

3. 以 N 点为中心的圆弧样本

   从上一点到下一点覆盖区域

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 -
    }

和视觉输出: