Open Mobile Map

This note describes the technique and gives the solution to finding the shortest distance from a point to a line or line segment. The equation of a line defined through two points P1 (x1,y1) and P2 (x2,y2) is

P = P1 + u (P2 - P1)

The point P3 (x3,y3) is closest to the line at the tangent to the line which passes through P3, that is, the dot product of the tangent and line is 0, thus

(P3 - P) dot (P2 - P1) = 0Substituting the equation of the line gives

[P3 - P1 - u(P2 - P1)] dot (P2 - P1) = 0Solving this gives the value of u

Substituting this into the equation of the line gives the point of intersection (x,y) of the tangent as

x = x1 + u (x2 - x1)
y = y1 + u (y2 - y1)

The distance therefore between the point P3 and the line is the distance between (x,y) above and P3.

Notes

• The only special testing for a software implementation is to ensure that P1 and P2 are not coincident (denominator in the equation for u is 0)
• If the distance of the point to a line segment is required then it is only necessary to test that u lies between 0 and 1.
• The solution is similar in higher dimensions.

Sample java source code

/*
* DistancePointSegmentExample, calculate distance to line
* This program is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program.  If not, see <http://www.gnu.org/licenses/>.
*
* Example implementation of “Minimum Distance between a Point and a Line”
import java.awt.geom.Point2D;

public class DistancePointSegmentExample {

/**
* Wrapper function to accept the same arguments as the other examples
*
* @param x3
* @param y3
* @param x1
* @param y1
* @param x2
* @param y2
* @return
*/
public static double distanceToSegment(double x3, double y3, double x1, double y1, double x2, double y2) {
final Point2D p3 = new Point2D.Double(x3, y3);
final Point2D p1 = new Point2D.Double(x1, y1);
final Point2D p2 = new Point2D.Double(x2, y2);
return distanceToSegment(p1, p2, p3);
}

/**
* Returns the distance of p3 to the segment defined by p1,p2;
*
* @param p1
*                First point of the segment
* @param p2
*                Second point of the segment
* @param p3
*                Point to which we want to know the distance of the segment
*                defined by p1,p2
* @return The distance of p3 to the segment defined by p1,p2
*/
public static double distanceToSegment(Point2D p1, Point2D p2, Point2D p3) {

final double xDelta = p2.getX() - p1.getX();
final double yDelta = p2.getY() - p1.getY();

if ((xDelta == 0) && (yDelta == 0)) {
throw new IllegalArgumentException(”p1 and p2 cannot be the same point”);
}

final double u = ((p3.getX() - p1.getX()) * xDelta + (p3.getY() - p1.getY()) * yDelta) / (xDelta * xDelta + yDelta * yDelta);

final Point2D closestPoint;
if (u < 0) {
closestPoint = p1;
} else if (u > 1) {
closestPoint = p2;
} else {
closestPoint = new Point2D.Double(p1.getX() + u * xDelta, p1.getY() + u * yDelta);
}

return closestPoint.distance(p3);
}

/**
* @param args
*/
public static void main(String[] args) {
// Test example
System.out.println(String.format(”Distance from 5,5 to (10,10)-(20,20): %f”, distanceToSegment(5, 5, 10, 10, 20, 20)));
System.out.println(String.format(”Distance from 15,15 to (10,10)-(20,20): %f”, distanceToSegment(15, 15, 10, 10, 20, 20)));
System.out.println(String.format(”Distance from 15,15 to (20,10)-(20,20): %f”, distanceToSegment(15, 15, 20, 10, 20, 20)));
System.out.println(String.format(”Distance from 0,15 to (20,10)-(20,20): %f”, distanceToSegment(0, 15, 20, 10, 20, 20)));
System.out.println(String.format(”Distance from 0,25 to (20,10)-(20,20): %f”, distanceToSegment(0, 25, 20, 10, 20, 20)));
System.out.println(String.format(”Distance from -13,-25 to (-50,10)-(20,20): %f”, distanceToSegment(-13, -25, -50, 10, 20, 20)));

// Should give:
// Distance from 5,5 to (10,10)-(20,20): 7.071068
// Distance from 15,15 to (10,10)-(20,20): 0.000000
// Distance from 15,15 to (20,10)-(20,20): 5.000000
// Distance from 0,15 to (20,10)-(20,20): 20.000000
// Distance from 0,25 to (20,10)-(20,20): 20.615528
// Distance from -13,-25 to (-50,10)-(20,20): 39.880822
}

}