obtenir plus proche point à la ligne

Voici Ruby déguisé en Pseudo-Code, en supposant Point objets ont chacun un x et y champ.

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

---

Sinon:

De Ligne de Ligne de Intersection, sur Wikipédia. Tout d'abord, trouver Q, qui est un deuxième point qui est d'un pas de P dans la "bonne direction". Cela nous donne quatre points.

def getClosestPointFromLine(A, B, P)
a_to_b = [B.x - A.x, B.y - A.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

La mise en cache, de Sauter des étapes, etc. est possible, pour des raisons de performances.

Votre pointX) sera une combinaison linéaire de points A et B:

X = k A + (1-k) B

Pour X être fait sur le segment de ligne, le paramètre k doit être comprise entre 0 et 1 inclus. Vous pouvez calculer k comme suit:

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

(où la période dénote le produit scalaire)

Ensuite, assurez-vous que le point est fait sur le segment de ligne:

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

J'ai écrit cela il y a longtemps, il n'est pas très différent de ce que les autres ont dit, mais c'est un copier/coller de la solution en C# si vous avez une classe (ou structure) nommé PointF avec les membres X et Y:

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 = P.X - A.X;
a_to_p.Y = P.Y - A.Y; //    # Storing vector A->P  
a_to_b.X = B.X - A.X;
a_to_b.Y = B.Y - A.Y; //    # 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(A.X + a_to_b.X * t, A.Y + a_to_b.Y * t);
}

Mise à jour: en Regardant les commentaires on dirait que j'ai adapté à C# à partir du même code source mentionnée dans la accepté de répondre.

Cette réponse est fondée sur les idées de la géométrie projective.

Calculer le produit vectoriel (Ax,Ay,1)×(Bx,By,1)=(u,v,w). Le vecteur résultant décrit la ligne reliant A et B: on a l'équation ux+vy+w=0. Mais vous pouvez aussi l'interpréter (u,v,0) comme un point infiniment loin de là, dans une direction perpendiculaire à cette ligne. Faire une autre croix produit, vous obtenez la ligne joignant hat point de P: (u,v,0)×(Px,Py,1). Et à l'intersection de cette ligne avec la ligne AB, vous faites un autre produit vectoriel: ((u,v,0)×(Px,Py,1))×(u,v,w). Le résultat sera un vecteur de coordonnées homogènes (x,y,z) à partir de laquelle vous pouvez lire les coordonnées de ce point le plus proche de (x/z,y/z).

Prendre le tout et vous obtenez la formule suivante:

À l'aide d'un système de calcul formel, vous pouvez obtenir les coordonnées suivantes:

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

Comme vous le remarquez, il y a beaucoup de termes qui reviennent. Inventer (assez bien arbitraire) de noms de ces, vous pouvez profiter du résultat final, écrit en pseudo-code:

dx = A.x - B.x
dy = A.y - B.y
det = A.y*B.x - A.x*B.y
dot = dx*P.x + dy*P.y
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)

Avantages de cette approche:

• Aucun cas distinctions
• Pas de racines carrées
• Une seule division

Ici sont des méthodes d'extension qui devrait faire l'affaire:

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));
}

Puis il suffit d'appeler:

P.DistanceTo(A, B);

Pour obtenir la distance du point "P" de la ligne |AB|. Il devrait être facile de modifier cela pour PointF.

Trouver le point le plus proche puis c'est juste une question de recherche de la distance minimale. LINQ a des méthodes pour cela.

De l'algorithme serait assez facile:

vous avez 3 points - triangle. De là, vous devriez être en mesure de trouver AB, AC, BC.

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