get closest point to a line

Question

I'd like to have a straight forward C# function to get a closest point (from a point P) to a line-segment, AB. An abstract function may look like this. I've search through SO but not found a usable (by me) solution.

public Point getClosestPointFromLine(Point A, Point B, Point P);

Answer 1

The algorithm would be quite easy:

you have 3 points - triangle. From there you should be able to find AB, AC, BC.

Theck this out: http://www.topcoder.com/tc?d1=tutorials&d2=geometry1&module=Static#line_point_distance

Answer 2

Find the slope a1 of AB by dividing the y-difference with the x-difference; then draw a perpendicular line (with slope a2 = -1/a1, you need to solve for the offset (b2) by putting P's coordinates into y = a2*x + b2); then you have two lines (i.e. two linear equations), and you need to solve the intersection. That will be your closest point.

Do the math right, and the function will be pretty trivial to write.

To elaborate a bit:

Original line:
y = a1 * x + b1
a1 = (By - Ay) / (Bx - Ax)   <--
b1 = Ay - a1 * Ax            <--

Perpendicular line:
y = a2 * x + b2
a2 = -1/a1                   <--
b2 = Py - a2 * Px            <--

Now you have P which lies on both lines:
y = a1 * x + b1
y = a2 * x + b2
--------------- subtract:
0 = (a1 - a2) * Px + (b1 - b2)
x = - (b1 - b2) / (a1 - a2)  <--
y = a1 * x + b1              <--

Hope I didn't mess up somewhere :) UPDATE Of course I did. Serve me right for not working things out on paper first. I deserved every downvote, but I'd've expected someone to correct me. Fixed (I hope).

Arrows point the way.

UPDATE Ah, the corner cases. Yeah, some languages don't handle infinities well. I did say the solution was language-free...

You can check the special cases, they're quite easy. The first one is when the x difference is 0. That means the line is vertical, and the closest point is on a horizontal perpendicular. Thus, x = Ax, y = Px.

The second one is when y difference is 0, and the opposite is true. Thus, x = Px, y = Ay

Answer 3

The closest point C will be on a line whose slope is the reciprocal of AB and which intersects with P. This sounds like it might be homework, but I'll give some pretty strong hints, in order of increasing spoiler-alert level:

• There can be only one such line.

• This is a system of two line equations. Just solve for x and y.

• Draw a line segment between A and B; call this L. The equation for L is y = mx + b, where m is the ratio of the y-coordinates to the x-coordinates. Solve for b using either A or B in the expression.

• Do the same as above, but for CP. Now solve the simultaneous linear system of equations.

• A Google search will give you a bevy of examples to choose from.

Answer 4

Your point (X) will be a linear combination of points A and B:

X = k A + (1-k) B

For X to be actually on the line segment, the parameter k must be between 0 and 1, inclusive. You can compute k as follows:

k_raw = (P-B).(A-B)  /  (A-B).(A-B)

(where the period denotes the dot product)

Then, to make sure the point is actually on the line segment:

if k_raw < 0:
    k= 0
elif k_raw > 1:
    k= 1
else:
    k= k_raw

Answer 5

Here's Ruby disguised as Psuedo-Code, assuming Point objects each have a x and y field.

def GetClosestPoint(A, B, P)

  a_to_p = [P.x - A.x, P.y - A.y]     # Storing vector A->P
  a_to_b = [B.x - A.x, B.y - A.y]     # Storing vector A->B

  atb2 = a_to_b[0]**2 + a_to_b[1]**2  # **2 means "squared"
                                      #   Basically finding the squared magnitude
                                      #   of a_to_b

  atp_dot_atb = a_to_p[0]*a_to_b[0] + a_to_p[1]*a_to_b[1]
                                      # The dot product of a_to_p and a_to_b

  t = atp_dot_atb / atb2              # The normalized "distance" from a to
                                      #   your closest point

  return Point.new( :x => A.x + a_to_b[0]*t,
                    :y => A.y + a_to_b[1]*t )
                                      # Add the distance to A, moving
                                      #   towards B

end

---

Alternatively:

From Line-Line Intersection, at Wikipedia. First, find Q, which is a second point that is to be had from taking a step from P in the "right direction". This gives us four points.

def getClosestPointFromLine(A, B, P)

  a_to_b = [B.x - A.x, B.y - B.y]   # Finding the vector from A to B
                                        This step can be combined with the next
  perpendicular = [ -a_to_b[1], a_to_b[0] ]
                                    # The vector perpendicular to a_to_b;
                                        This step can also be combined with the next

  Q = Point.new(:x => P.x + perpendicular[0], :y => P.y + perpendicular[1])
                                    # Finding Q, the point "in the right direction"
                                        If you want a mess, you can also combine this
                                        with the next step.

  return Point.new (:x => ((A.x*B.y - A.y*B.x)*(P.x - Q.x) - (A.x-B.x)*(P.x*Q.y - P.y*Q.x)) / ((A.x - B.x)*(P.y-Q.y) - (A.y - B.y)*(P.y-Q.y)),
                    :y => ((A.x*B.y - A.y*B.x)*(P.y - Q.y) - (A.y-B.y)*(P.x*Q.y - P.y*Q.x)) / ((A.x - B.x)*(P.y-Q.y) - (A.y - B.y)*(P.y-Q.y)) )

end

Caching, Skipping steps, etc. is possible, for performance reasons.