-3

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]
}
LioM
  • 139
  • 1
  • 2
  • 5

3 Answers3

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)
}
La pieuvre
  • 438
  • 2
  • 9
  • 1
    beware of divide by 0 if the line is vertical or horizontal – vacawama Aug 08 '20 at 13:49
  • You are right! I will correct the answer when I’m on my computer – La pieuvre Aug 08 '20 at 13:50
  • I was writing a similar answer. I just checked for the vertical and horizontal line up front and then returned the trivial solution. – vacawama Aug 08 '20 at 13:58
  • 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 ? – LioM Aug 09 '20 at 07:14
  • 1
    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) – LioM Aug 09 '20 at 07:59
  • 1
    I spotted some error in my code, I’ll fixed them in few hours when I’ll be available. – La pieuvre Aug 09 '20 at 09:00
  • huge thanks to you, already looking forward to trying out your solution :) – LioM Aug 09 '20 at 14:04
  • That should be it now :) – La pieuvre Aug 09 '20 at 16:48
  • There only seems to be a problem with vertical lines, do you know how i could fix it ? – LioM Aug 09 '20 at 17:26
  • For vertical line it’s very simple, it’s the absolute value of the x of the line - the x of the point. – La pieuvre Aug 09 '20 at 17:34
  • ah yes indeed ... thank you so much for your help :) – LioM Aug 09 '20 at 17:37
1

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
0

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.

Blindman67
  • 51,134
  • 11
  • 73
  • 136