3

对于 DirectX 像素着色器，我正在尝试在抛物线上找到与 2d 中任意点最近的点。

大量的谷歌搜索向我揭示了这是一个常见的微积分前作业问题。不幸的是，数百个相关答案都说“一旦你有了这个方程，使用你的图形计算器的最小函数，它会告诉你答案是 6”。

我承认我对微积分一无所知。我认识到我寻求的方程式可能就在维基百科上，但我不知道如何将这些希腊符号转换为 HLSL 函数。C、C++、C# 或任何其他语言的解决方案也将不胜感激。

编辑：根据请求查看输入曲线的格式：

//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);
}
4

2 回答 2

3

你可以利用这个：

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

而已。

于 2012-03-21T07:55:54.233 回答
0

我假设您想要的是抛物线上最接近平面中另一个点的点。假设抛物线由下式给出，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）。在这些情况下，您需要使用不同的初始点启动该函数两次。

希望这可以帮助。

于 2012-03-21T08:09:58.673 回答