如何编写代码计算一个点与一条抛物线之间的距离？

Question

我正在尝试找到二维平面中一条抛物线上距离任意点最近的点，用于DirectX像素着色器。

经过大量搜索，我发现这是一个常见的预备数学作业问题。不幸的是，数百个相关答案都说“一旦你有了这个方程，使用你的图形计算器的最小值函数，它会告诉你答案是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);
} 

- Greg Bahm

---

对于抛物线来说，有无限多个最近的点，即所有距离为零的在抛物线上的点，你不能再更接近了。如果你对数学和数学思维的基础不满意，我猜你会发现计算几何令人沮丧，因为这构成了编程中这种类型的（不）惊人大部分。 - Kerrek SB

请编辑一些代码以展示抛物线数据的表示方式。 - SimpleVar

Kerrek SB，我为我的帖子可能不够清晰而道歉。我正在尝试找到一条抛物线上距离不在该抛物线上的点最近的点。我确信只有一个这样的点，并且它是垂直于曲线切线和任意点之间形成的直线的点。 - Greg Bahm

@Greg：请注意，抛物线有两个支架：如果A位于抛物线的对称轴上，则“最接近点”不一定是唯一的。我认为，除了这种边缘情况外，最多可能有三个同样接近的点：每侧各一个加上抛物线的拐点。但是除此之外，你没问题。 - Steve Jessop

@GregBahm 我有类似的问题。对我来说，求导有些复杂。你找到答案了吗？ - Sirish

Answer 1

您可以使用以下内容：

您可以利用此功能：

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

就是这样。

- Michal B.

---

好的，现在更接近真相了。首先，我认为你不应该将TS导数化，因为他需要程序，并且可以将所有符号导数并得到以a，b，c，px，py为项的答案。然后，“将P'（x）置为零以找到它穿过X轴的位置”--为什么要关注穿过X轴呢？ - Lol4t0

为了找到局部极值，您需要找到导数的根。 - Ivaylo Strandjev

根据我的计算，你需要解决以下三次方程式：(2*a^2)*x^3 + (3*a*b)*x^2 + (2*a*c - 2*a*py + b^2 + 1)*x + (b*c - b*py - px) = 0。 - rodrigo

Answer 2

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

希望这可以帮助到您。

- Ivaylo Strandjev

---

你可以在这种简单情况下找到确切的表达式。请查看@Michal B.的答案。 - Lol4t0

但是a、b和c是参数，因此在计算导数之后，您仍然需要教计算机计算三次多项式的根。您可以使用卡尔达诺公式来实现这一点，但我认为由于其复杂性，答案的准确性将大大降低。 - Ivaylo Strandjev

@IvayloStrandjev GSL - GNU Scientific Library有一个用于解三次方程的C语言求解器 https://www.gnu.org/software/gsl/manual/html_node/Cubic-Equations.html - Alessandro Jacopson