Алгоритм для кратчайшего расстояния от точки до эллиптической дуги

Question

Я пытаюсь найти общий метод вычисления кратчайшего расстояния между произвольной точкой и дугой, где дуга - это 90-градусная часть границы эллипса, а Оси эллипса выровнены с декартовыми осями. Я работаю в 2D, поэтому и точка, и эллипс являются копланарными. Если точка находится в том же квадранте, что и дуга, относительно центра эллипса, то я считаю, что проблема такая же, как вычисление расстояния от точки до любой точки на всей границе эллипса, для которой существует довольно простая методов (например, http://www.geometrictools.com/Documentation/DistancePointEllipseEllipsoid.pdf).

На диаграмме, если точка находится слева от x1 или справа от x2 или ниже y1, проблема проста.

Однако я не могу понять, что делать, если точка P такова, как показано на диаграмме.

Answer 1

Я обычно использую для эллипсов этого:

1. образец дуги на N точек

   для 90 степени использовать кусок 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 - 
    } 

И визуальный выход:

Answer 2

Таким образом, вся дуга, что это отвлекающий маневр. Это линейный масштаб обратно в единичный круг. Поэтому вам нужно всего лишь найти кратчайшее расстояние от точки до единицы круга. (https://math.stackexchange.com/questions/103453/closest-point-to-a-unit-circle-from-a-point-inside-it) Затем просто отмените масштаб и измерьте расстояние.

[Edit by Spektre] Это явно неправильно!

Если вы найдете ближайшую точку к кругу (в масштабированном пространстве), это не означает, что эта точка после перераспределения назад (до эллиптического пространства) будет по-прежнему близка! Смотрите пример: