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

What is perpendicular? A point and a line? Anyway, you should at least try to write this function and show your code, before asking a question here. — Forketyfork, May 31 '15 at 16:41
have a look at the link, though this code is not in java in c++. But this code perform it's task in a single method - http://stackoverflow.com/questions/849211/shortest-distance-between-a-point-and-a-line-segment. — Razib, May 31 '15 at 16:48
Smallest distance from the point to the set of points comprising the line segment. If the math is hard just make a loop. — Thorbjørn Ravn Andersen, May 31 '15 at 17:35
Use https://docs.oracle.com/javase/8/docs/api/java/awt/geom/Line2D.html#ptLineDist-double-double-double-double-double-double- — Marco13, Jun 01 '15 at 08:09

score 10 · Answer 1 · answered Jun 01 '15 at 07:01

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.

I tried this code and a problem appeared: assume Point (0,0) and Line (100, 0) and (200, 0), I think the result should be 100 min distance. — wake-0, Jun 12 '17 at 08:46
My code calculates the distance between the line which extends to infinity, and you points all lie on the line y=0. You want the distance to the line segment which the initial code give. — Salix alba, Jun 12 '17 at 17:29

AlmasB · Answer 2 · 2015-05-31T18:15:56.700

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

This should work but it is not the most efficient way of doing things. Here you are calculating four different square roots. It is really the long way around. The solution in the updated question is more efficient using the dot product of vectors to find the distance. — Salix alba, Jun 01 '15 at 06:24
I tried the code and a problem appeared for the given example: Point(0,0) and Line(100, 0) to (200, 0). I think the result should be 100 but it is 0 because the area is 0. — wake-0, Jun 12 '17 at 08:47

score 2 · Answer 3 · answered May 31 '15 at 18:20

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 :

enter image description here

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

Lars · Answer 4 · 2017-03-15T15:00:44.180

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()));

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

4 Answers4

Linked