# 得到最接近的一条线

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

` `def GetClosestPoint(A, B, P) a_to_p = [Px - Ax, Py - Ay] # Storing vector A->P a_to_b = [Bx - Ax, By - Ay] # 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 => Ax + a_to_b[0]*t, :y => Ay + a_to_b[1]*t ) # Add the distance to A, moving # towards B end` `

` `def getClosestPointFromLine(A, B, P) a_to_b = [Bx - Ax, By - Ay] # 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 => Px + perpendicular[0], :y => Py + 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 => ((Ax*By - Ay*Bx)*(Px - Qx) - (Ax-Bx)*(Px*Qy - Py*Qx)) / ((Ax - Bx)*(Py-Qy) - (Ay - By)*(Py-Qy)), :y => ((Ax*By - Ay*Bx)*(Py - Qy) - (Ay-By)*(Px*Qy - Py*Qx)) / ((Ax - Bx)*(Py-Qy) - (Ay - By)*(Py-Qy)) ) end` `

` ` public static Vector2 GetClosestPointOnLineSegment(Vector2 A, Vector2 B, Vector2 P) { Vector2 AP = P - A; //Vector from A to P Vector2 AB = B - A; //Vector from A to B float magnitudeAB = AB.LengthSquared(); //Magnitude of AB vector (it's length squared) float ABAPproduct = Vector2.Dot(AP, AB); //The DOT product of a_to_p and a_to_b float distance = ABAPproduct / magnitudeAB; //The normalized "distance" from a to your closest point if (distance < 0) //Check if P projection is over vectorAB { return A; } else if (distance > 1) { return B; } else { return A + AB * distance; } }` `

` `X = k A + (1-k) B` `

` `k_raw = (PB).(AB) / (AB).(AB)` `

（其中周期表示点积）

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

Justin L.的答案几乎没有问题，但它并不检查标准化距离是否小于0，或者高于ABvector幅度。 那么当Pvector超出范围（来自线段AB）时，它将无法正常工作。 这里是更正的伪代码：

` ` function GetClosestPoint(A, B, P) { vectorAP = (px - ax, py - ay) //Vector from A to P vectorAB = (bx - ax, by - ay) //Vector from A to B magnitudeAB = vectorAB[0]^2 + vectorAB[1]^2 //Magnitude of AB vector (it's length) ABAPproduct = vectorAB[0]*vectorAP[0] + vectorAB[1]*vectorAP[1] //The product of a_to_p and a_to_b distance = ABAPproduct / magnitudeAB //The normalized "distance" from a to your closest point if ( distance < 0) //Check if P projection is over vectorAB { returnPoint.x = ax returnPoint.y = ay } else if (distance > magnitudeAB) { returnPoint.x = bx returnPoint.y = by } else { returnPoint.x = ax + vectorAB[0]*distance returnPoint.y = ay + vectorAB[1]*distance } }` `

` `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 <--` `

` `x = ((Ax - Bx)*Px + (Ay - By)*Py)*(Ax - Bx) + (Ay*Bx - Ax*By)*(Ay - By) y = -(Ay*Bx - Ax*By)*(Ax - Bx) + ((Ax - Bx)*Px + (Ay - By)*Py)*(Ay - By) z = (Ax - Bx)^2 + (Ay - By)^2` `

` `dx = Ax - Bx dy = Ay - By det = Ay*Bx - Ax*By dot = dx*Px + dy*Py x = dot*dx + det*dy y = dot*dy - det*dx z = dx*dx + dy*dy zinv = 1/z return new Point(x*zinv, y*zinv)` `

• 没有区别
• 没有平方根
• 只有一个部门

• 只能有一条这样的路线。

• 这是一个两线方程的系统。 只需解决`x``y`

• `A``B`之间绘制一条线段; 称这个`L` `L`的等式是`y = mx + b` ，其中`m`是y坐标与x坐标的比率。 在expression式中使用`A``B`来求解`b`

• 像上面那样做，但对于`CP` 。 现在求解联立线性方程组。

• 谷歌search会给你一个可供select的例子

` `private static PointF ClosestPointToSegment(PointF P, PointF A, PointF B) { PointF a_to_p = new PointF(), a_to_b = new PointF(); a_to_p.X = PX - AX; a_to_p.Y = PY - AY; // # Storing vector A->P a_to_b.X = BX - AX; a_to_b.Y = BY - AY; // # Storing vector A->B float atb2 = a_to_b.X * a_to_b.X + a_to_b.Y * a_to_b.Y; float atp_dot_atb = a_to_p.X * a_to_b.X + a_to_p.Y * a_to_b.Y; // The dot product of a_to_p and a_to_b float t = atp_dot_atb / atb2; // # The normalized "distance" from a to the closest point return new PointF(AX + a_to_b.X * t, AY + a_to_b.Y * t); }` `

` `public static double DistanceTo(this Point from, Point to) { return Math.Sqrt(Math.Pow(from.X - to.X, 2) + Math.Pow(from.Y - to.Y, 2)); } public static double DistanceTo(this Point point, Point lineStart, Point lineEnd) { double tI = ((lineEnd.X - lineStart.X) * (point.X - lineStart.X) + (lineEnd.Y - lineStart.Y) * (point.Y - lineStart.Y)) / Math.Pow(lineStart.DistanceTo(lineEnd), 2); double dP = ((lineEnd.X - lineStart.X) * (point.Y - lineStart.Y) - (lineEnd.Y - lineStart.Y) * (point.X - lineStart.X)) / lineStart.DistanceTo(lineEnd); if (tI >= 0d && tI <= 1d) return Math.Abs(dP); else return Math.Min(point.DistanceTo(lineStart), point.DistanceTo(lineEnd)); }` `

` `P.DistanceTo(A, B);` `

find最接近的点就是search最小距离的问题。 `LINQ`有这方面的方法。

` `Intersector.nearestSegmentPoint` `