java中求点到边距离的函数

Question

有没有人在java中有一个函数来找到点和线段/边之间的最短距离？我找到的每个例子都是用另一种语言编写的，并使用了一堆子函数。它不能基于它们是垂直的假设。

更新

我将python函数移植到java。如果有人擅长数学并且可以验证，我将不胜感激。x 和 y 是点，其他参数是线段。

public float pDistance(float x, float y, float x1, float y1, float x2, float y2) {

          float A = x - x1;
          float B = y - y1;
          float C = x2 - x1;
          float D = y2 - y1;

          float dot = A * C + B * D;
          float len_sq = C * C + D * D;
          float param = -1;
          if (len_sq != 0) //in case of 0 length line
              param = dot / len_sq;

          float xx, yy;

          if (param < 0) {
            xx = x1;
            yy = y1;
          }
          else if (param > 1) {
            xx = x2;
            yy = y2;
          }
          else {
            xx = x1 + param * C;
            yy = y1 + param * D;
          }

          float dx = x - xx;
          float dy = y - yy;
          return (float) Math.sqrt(dx * dx + dy * dy);
        }

Answer 1

我们可以稍微简化一下。您不需要计算参数。您可以做的是找到与该线成直角的向量v。取向量 (A,B) 的点积。在 2D 中很容易找到与（C，D）正交的向量，它只是（-D，C）。

public float pDistance(float x, float y, float x1, float y1, float x2, float y2) {

      float A = x - x1; // position of point rel one end of line
      float B = y - y1;
      float C = x2 - x1; // vector along line
      float D = y2 - y1;
      float E = -D; // orthogonal vector
      float F = C;

      float dot = A * E + B * F;
      float len_sq = E * E + F * F;

      return (float) Math.abs(dot) / Math.sqrt(len_sq);
    }

如果您担心性能可以更容易地使用平方距离，那么最后一行将是

      return (float) dot * dot / len_sq;

这省去了计算平方根的麻烦。所以如果你想计算最近的边，找到到每条边的平方距离并选择最小的。

此函数查找到无限线而不是线段的距离。这可能不是您想要的。题中的解与点超出线段两端的情况不同。在那里它找到到最近端点的距离。

Answer 2

来自http://en.wikipedia.org/wiki/Distance_from_a_point_to_a_line

点到线的距离（或垂直距离）是欧几里得几何中点到线的最短距离。它是连接点和线并垂直于线的线段的长度。

你说“不能基于它们垂直的假设”，但是点和线段之间的最短距离代表另一条与原始线垂直的线。因此，它是由 AB 和 C 形成的三角形的高度，其中 A - 点，B 和 C 是线段的端点。

我们知道所有三个点的坐标，因此我们可以获得三角形的边长。使用 Heron 公式： https: //www.mathsisfun.com/geometry/herons-formula.html我们可以从以下位置获得也等于 0.5 * b * h 的面积：https: //www.mathsisfun.com/algebra/ trig-area-triangle-without-right-angle.html

private static float distBetweenPointAndLine(float x, float y, float x1, float y1, float x2, float y2) {
    // A - the standalone point (x, y)
    // B - start point of the line segment (x1, y1)
    // C - end point of the line segment (x2, y2)
    // D - the crossing point between line from A to BC

    float AB = distBetween(x, y, x1, y1);
    float BC = distBetween(x1, y1, x2, y2);
    float AC = distBetween(x, y, x2, y2);

    // Heron's formula
    float s = (AB + BC + AC) / 2;
    float area = (float) Math.sqrt(s * (s - AB) * (s - BC) * (s - AC));

    // but also area == (BC * AD) / 2
    // BC * AD == 2 * area
    // AD == (2 * area) / BC
    // TODO: check if BC == 0
    float AD = (2 * area) / BC;
    return AD;
}

private static float distBetween(float x, float y, float x1, float y1) {
    float xx = x1 - x;
    float yy = y1 - y;

    return (float) Math.sqrt(xx * xx + yy * yy);
}

我不知道它有多正确，希望真正的数学家能够纠正或支持这个解决方案