How to get the coordinates of the point on a line that has the smallest distance from another point

Question

i'm struggling with this geometry problem right now.

Let's say we have a line defined by point A(x1,y1) and point B(x2,y2) We also have a point C(x3,y3).

What function written in SWIFT could give me the coordinates (X,Y) of the point that has the smallest distance from the line ? In other words, the point on the line which is the intersection between a perpendicular segment and the other point.

func getCoordsOfPointsWithSmallestDistanceBetweenLineAndPoint(lineX1: Double, lineY1: Double, lineX2: Double, lineY2: Double, pointX3: Double, pointY3: Double) -> [Double] {
    // ???
    return [x,y]
}

Unlade

Answer 1

In a mathematical point of view you can :

• first find the equation of the line :

      y1 = a1x1+b1 
      a1 = (y2-y1) / (x2-x1)
      b1 = y1-a1*x1
  

• Then calculate the gradient of the second line knowing :

      a1 * a2 = -1 <-> 
      a2 = -1/a1
  

• with a2 you can find the value of b for the second equation :

      y3 = a2*x3 + b2 <-> 
      b2 = y3 - a2*x3
  

• Finally calculate the intersection of the 2 lines :

      xi = (b2-b1) / (a1-a2)
      y = a1*xi + b1
  

Then it's quite straightforward to bring that to swift :

typealias Line = (gradient:CGFloat, intercept:CGFloat)

func getLineEquation(point1:CGPoint, point2:CGPoint) -> Line {
    guard point1.x != point2.x else {
        if(point1.y != point2.y)
        {
            print("Vertical line : x = \(point1.x)")
        }
        return (gradient: .nan, intercept: .nan)
    }
    let gradient = (point2.y - point1.y)/(point2.x-point1.x)
    let intercept = point1.y - gradient*point1.x
    return (gradient: gradient, intercept: intercept)
}

func getPerpendicularGradient(gradient:CGFloat) -> CGFloat
{
    guard gradient != 0 else {
        print("horizontal line, the perpendicilar line is vertical")
        return .nan
    }
    return -1/gradient
}

func getIntercept(forPoint point:CGPoint, withGradient gradient:CGFloat) -> CGFloat
{
    return point.y - gradient * point.x
}

func getIntersectionPoint(line1:Line, line2:Line)-> CGPoint
{
    guard line1.gradient != line2.gradient else {return CGPoint(x: CGFloat.nan, y: CGFloat.nan)}
    let x = (line2.intercept - line1.intercept)/(line1.gradient-line2.gradient)
    return CGPoint(x:x, y: line1.gradient*x + line1.intercept)
}

func getClosestIntersectionPoint(forLine line:Line, point:CGPoint) -> CGPoint
{
    let line2Gradient = getPerpendicularGradient(gradient:line.gradient)
    let line2 = (
        gradient: line2Gradient,
        intercept: getIntercept(forPoint: point, withGradient: line2Gradient))
    
    return getIntersectionPoint(line1:line, line2:line2)
}

func getClosestIntersectionPoint(forLinePoint1 linePoint1:CGPoint, linePoint2:CGPoint, point:CGPoint) -> CGPoint
{
    return getClosestIntersectionPoint(
        forLine:getLineEquation(point1: linePoint1, point2: linePoint2),
        point:point)
}

Posture

beware of divide by 0 if the line is vertical or horizontal – Yb

You are right! I will correct the answer when I’m on my computer – Posture

I was writing a similar answer. I just checked for the vertical and horizontal line up front and then returned the trivial solution. – Yb

Thanks a lot for this answer, although while using SwiftProcessing (an open-source library for drawing on canvas,...), this doesn't seem to give me the right coordinates . I don't really get why, although it might be because of the Y axis being inverted maybe ? ( A point at 20x50 will be 20px from the left, 50px from the top) Do you think that could cause problems ? – Unlade

For example : let pointLineA = CGPoint(x: 300, y: 300) let pointLineB = CGPoint(x: 600, y: 500) let point = CGPoint(x: 500, y: 400) print(getClosestIntersectionPoint(forLinePoint1: pointLineA, linePoint2: pointLineB, point: point)) gives me -> (-407.6923076923077, -761.5384615384615) – Unlade

I spotted some error in my code, I’ll fixed them in few hours when I’ll be available. – Posture

huge thanks to you, already looking forward to trying out your solution :) – Unlade

That should be it now :) – Posture

There only seems to be a problem with vertical lines, do you know how i could fix it ? – Unlade

For vertical line it’s very simple, it’s the absolute value of the x of the line - the x of the point. – Posture

ah yes indeed ... thank you so much for your help :) – Unlade

Answer 2

You can minimize the squared distance of C to a point on the straight line AB:

(CA + t.AB)² = t²AB² + 2t AB.CA + CA²

The minimum is achieved by

t = - AB.CA / AB²

and

CP = CA + t.AB

Passage

Answer 3

To elaborate on Yves Daoust answer which if converted to a function has the form

func closestPnt(x: Double, y: Double, x1: Double, y1: Double, px: Double, py: Double)->[Double]{
    let vx = x1 - x  // vector of line
    let vy = y1 - y
    let ax = px - x  // vector from line start to point
    let ay = py - y
    let u = (ax * vx + ay * vy) / (vx * vx + vy * vy) // unit distance on line
    if u >= 0 && u <= 1 {                             // is on line segment
        return [x + vx * u, y + vy * u]               // return closest point on line
    }
    if u < 0 {
        return [x, y]      // point is before start of line segment so return start point
    }
    return [x1, y1]       // point is past end of line so return end
}

Note that the function is for line segments, if the closest points unit distance is behind the start or past the end then an end point is the closest.

If you want the point on a line (finitely long) then the following will do that.

func closestPnt(x: Double, y: Double, x1: Double, y1: Double, px: Double, py: Double)->[Double]{
    let vx = x1 - x  // vector of line
    let vy = y1 - y
    let ax = px - x  // vector from line start to point
    let ay = py - y
    let u = (ax * vx + ay * vy) / (vx * vx + vy * vy) // unit distance on line
    return [x + vx * u, y + vy * u]                 // return closest point on line
    
}

Note That both functions assume that !(x1 == x && y1 == y) is be true. IE the line segment MUST have a length > 0.

Baddie