Как найти расстояние между точкой и параболой в коде - PullRequest
Новая
       8

Как найти расстояние между точкой и параболой в коде

3 голосов
/ 21 марта 2012

Я пытаюсь найти ближайшую точку на параболе к произвольной точке в 2d для пиксельного шейдера DirectX.

Большое количество поисков в Google показало мне, что это общее предварительное исчислениедомашнее заданиеК сожалению, сотни релевантных ответов все говорят, например, «Как только вы получите это уравнение, используйте функцию минимума вашего графического калькулятора, и он скажет вам, что ответ равен 6».исчисление.Я понимаю, что уравнение, которое я ищу, вероятно, находится прямо там, в Википедии, но я не могу понять, как преобразовать эти греческие символы в функцию HLSL.Решение на C, C ++, C # или любом другом языке также будет высоко ценится.

edit: По запросу для просмотра формата входной кривой: 

//Equation of parabola being y = ax^2 + bx + c
//p is the arbitrary point we're trying to find the closest point on the parabola for.
float2 GetClosestPointOnParabola(float a, float b, float c, float2 p)
{
    //Something involving the distance formula...
    //Something involving "minimization"...
    return float2(x, y);
}

Ответы [ 2 ]

3 голосов
/ 21 марта 2012

Вы можете использовать это: 

Pmin = (xmin, ymin) ~ point on a parabola
P = (px, py) ~ point in 2d    
y = a*x^2 + bx + c ~ parabola

P(x) = (x-px)^2 + (y-py)^2 = (x-px)^2 + (a*x^2 + bx + c - py)^2

Вам нужно вычислить производную P (x), это не так сложно. Например. Если вы получите: P(x) = x^4 + 4x^2 - 3x + 10, то производная будет: 

P'(x) = 4x^3 + 8x - 3

Я думаю, вы понимаете, как рассчитать это. Затем сравните P '(x) с нулем, чтобы найти, где он пересекает ось X. Вы находите xmin из этого, а затем у вас есть ymin из: 

y = a*x^2 + bx + c

Вот и все.

0 голосов
/ 21 марта 2012

Я предполагаю, что вам нужна точка на параболе, ближайшая к другой точке на плоскости. Предположим, парабола задана как y = a * x^2 + b * x + c, и вы хотите найти точку на ней, ближайшую к точке A (x a , y a ).

Я бы предложил вам использовать восхождение на гору . Он находит локальный минимум в функции с логарифмической сложностью. Я напишу пример кода c ++, предполагая, что есть функция h (x), которая вычисляет расстояние от A до точки с точкой с координатой x, равной x на параболе. 

double minDist() {
  const double epsylon = 1e-9; // used to avoid double prescision errors
  double current = 0.0;
  double step = 1e+6;
  while (step > 1e-5) { // change this with the accuracy you need
    double left_neighbour = current - step;
    double right_neighbour = current + step;
    double cval = h(current);
    double lval = h(left_neighbour);
    double rval = h(right_neighbour);
    if (cval < rval + epsylon && cval < lval + epsylon) {
      step *= 0.5;
      continue;
    }
    if (lval < rval) {
      current = left_neighbour;
    } else {
      current = right_neighbour;
    }
  }
  return current;
}

В большинстве случаев у вас будет один локальный минимум, который является тем ответом, который вам нужен, но, возможно, в некоторых случаях у вас их два (я думаю, их не может быть больше 2). В этих случаях вам нужно запустить функцию дважды с разными начальными точками.

Надеюсь, это поможет.

...