Friday, 16 February 2018

Shortest distance between a point and a line

Problem

There is a point P with co-ordinates [xp,yp] and a line with known parameters. Find the distance between P and the nearest point on the line, or equivalently, the perpendicular distance between P and the line.

Approach

Find the co-ordinates of this point O and then use Pythagoras' Theorem to determine distance.


--------------------------------------

Point of intersection: O = [xo,yo]
   Point outside line: P = [xp,yp]
     y-axis intercept: Q = [xq,yq] = [0,C]

P_ = OP, Q_ = OQ

Perpendicular vectors <=> P_.Q_ = 0

Line equation (slope-intercept form): y = M*x + C


P_ = (xp - xo)*ex_ + (yp - yo)*ey_

Q_ = (xq - xo)*ex_ + (yq - yo)*ey_
   = -xo*ex_ + (C - yo)*ey_

P_.Q_ = -xo*(xp - xo) + (C - yo)*(yp - yo) = 0


(C - yo)*(yp - yo) = xo*(xp - xo)
            C - yo = xo*(xp - xo)/(yp - yo)
                 C = xo*(xp - xo)/(yp - yo) + yo

   yo = M*xo + C
 M*xo = yo - C
    M = -(C - yo)/xo
      = -(xp - xo)/(yp - yo)
      = (xo - xp)/(yp - yo)

xo - xp = M*(yp - yo)
        = M*yp - M*(M*xo + C)
        = M*yp - M^2*xo - M*C

 xo + M^2*xo = M*(yp - C) + xp
xo*(1 + M^2) =        
          xo = (xp + M*(yp - C))/(1 + M^2)


 yo = M*(xp + M*(yp - C))/(1 + M^2)) + C

    = (M*(xp + M*(yp - C)) + C*(1 + M^2))/(1 + M^2)
    = (M*(xp + M*yp) - M^2*C + C + M^2*C)/(1 + M^2)
    = (M*(xp + M*yp) + C)/(1 + M^2)



L² = (xo - xp)² + (yo - yp)²

xo - xp = (xp + M*(yp - C))/(1 + M^2) - xp
        = (xp + M*(yp - C) - xp*(1 + M^2))/(1 + M^2)
        = (M*(yp - C) - M²*xp)/(1 + M²)
        = M*(yp - C - M*xp)/(1 + M²)

yo - yp = (M*(xp + M*yp) + C)/(1 + M^2) - yp
        = (M*(xp + M*yp) + C - yp*(1 + M²))/(1 + M^2)
        = (M*xp + C - yp)/(1 + M²)

L² = (M*(yp - C - M*xp)/(1 + M²))² + ((M*xp + C - yp)/(1 + M²))²
   = M²*(yp - C - M*xp)²/(1 + M²)² + (M*xp + C - yp)²/(1 + M²)²
   = (M²*(yp - C - M*xp)² + (M*xp + C - yp)²)/(1 + M²)²
   = (M²*(yp - C - M*xp)² + (-1)²(yp - C - M*xp))²/(1 + M²)²
   = (M²*(yp - C - M*xp)² + (yp - C - M*xp)²)/(1 + M²)²
   = (M² + 1)*(yp - C - M*xp)²/(1 + M²)²
   = (yp - C - M*xp)²/(1 + M²)

 => L = |yp - M*xp - C|/√(1 + M²)


---------------------------------------------

Distance equation using line equation in standard form

A*x + B*y + C' = 0
           B*y = -A*x - C'
             y = -(A/B)*x - C'/B

Equate coefficients -> M = -A/B, C = -C'/B

  L = |yp - M*xp - C|/√(1 + M²)
    = |yp - (-A/B)*xp - (-C'/B)|/√(1 + (-A/B)²)

√(1 + (-A/B)²) = √(1 + (-1)²*A²/B²)
               = √((B² + A²)/B²)
               = √(B² + A²)/B

=> L = |yp + (A/B)*xp + C'/B|/(√(A² + B²)/B)
     = |(B*yp + A*xp + C')/B|/(√(A² + B²)/B)
     = |A*xp + B*yp + C'|/√(A² + B²)



----------------------------------------------

Sanity Checks

xp = 0, yp = 1, C = 0, M = 0

L = |1 - 0 - (0)*(0)|/√(1 + (0)²)
  = |1|/√(1)
  = 1

xp = 1, yp = 1, C = 0, M = -1

L = |1 - 0 - (-1)(1)|/√(1 + (-1)²)
  = |1 + 1|/√(1 + 1)
  = 2/√(2)
  = √(2)

No comments:

Post a Comment