Function for finding the distance between a point and an edge in java

Question

Does anyone have a function in java for finding the shortest distance between a point and a line segment/edge? Every example I find is in another language and uses a bunch of sub functions. It can't be based on the assumption that they are perpendicular.

Update

I ported over a python function to java. If anyone is good at math and can verify I would appreciate it. x and y is the point, and other params are for the line segment.

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

We can simplify things a bit. You don't need to calculate param. What you can do is find a vector v at right angles to the line. The take the dot product of that with the vector (A,B). In 2D its easy enough to find the vector orthogonal to (C,D), its just (-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);
    }

If you are worried about performance is can be easier to work with the squared distances then the last line would be

      return (float) dot * dot / len_sq;

This saves having to calculate a square root. So if you want to calculate the closest edge, find the squared distances to each edge and select the smallest.

This function find the distance to the infinite line rather than the line segment. This may not be what you want. The solution in the question differs in what happens if the point is beyond the two ends of the line segment. There it find the distance to the closest end point.

Answer 2

If your line passes through two points, you can determine the equation of the line exactly.

If your line is ax + by + c = 0 and your point is (x0, y0), then the distance is given by :

This gives the shortest distance between any line and a point. (a, b, c are real constants)

Edit : In order to find the exact equation from two points on the line, the steps are :

`y − y1 = m(x − x1)` where m is the slope of the line.

Simplifying from this, a = -m, b = 1 and c = m*x1 - y1

Answer 3

From http://en.wikipedia.org/wiki/Distance_from_a_point_to_a_line

The distance (or perpendicular distance) from a point to a line is the shortest distance from a point to a line in Euclidean geometry. It is the length of the line segment which joins the point to the line and is perpendicular to the line.

You say that "It can't be based on the assumption that they are perpendicular.", but the shortest distance between a point and a line segment represents another line which is perpendicular to the original line. Hence it is the height of the triangle formed by A B and C, where A - the point, B and C are the end points of the line segment.

We know the coordinates of all three points, therefore we can obtain lengths of sides of the triangle. Using Heron's formula: https://www.mathsisfun.com/geometry/herons-formula.html we can obtain the area which is also equal to 0.5 * b * h from: 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);
}

I do not know how correct it is, hopefully a real mathematician can correct or back up this solution

Answer 4

If you do not want to implement all this by yourself I can recommend to use JTS. Use the distance method from LineSegment (for lines) or Coordinate (for points) accordingly. Given Points p1 and p2 for your Line and a Point p3 (that you want to calculate the distance) the code would look like that:

// create Line
LineSegment ls = new LineSegment(p1.getX(), p1.getY(), p2.getX(), p2.getY());
//calculate distance between Line and Point
double distanceLinePoint = ls.distance(new Coordinate(p3.getX(), p3.getY()));
// calculate distance between Points (p1 - p3)
double distanceBetweenPoints = new Coordinate(p1.getX(), p1.getY()).distance(new Coordinate(p3.getX(), p3.getY()));