symbolics net mathnet c# math geometry

c# - net - obtener el punto más cercano a una línea



mathnet c# (11)

Me gustaría tener una función directa de C # para obtener un punto más cercano (desde un punto P) a un segmento de línea, AB. Una función abstracta puede verse así. He buscado a través de SO pero no he encontrado una solución utilizable (por mí).

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

Aquí está Ruby disfrazado de Pseudo-Code, asumiendo que los objetos Point tienen cada uno un campo y .

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

Alternativamente:

Desde Line-Line Intersection , en Wikipedia. Primero, encuentre Q, que es un segundo punto que se debe tener al dar un paso desde P en la "dirección correcta". Esto nos da cuatro puntos.

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

El almacenamiento en caché, omitir pasos, etc. es posible por motivos de rendimiento.

Aquí hay métodos de extensión que deberían hacer el truco:

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

Entonces solo llame:

P.DistanceTo(A, B);

Para obtener la distancia del punto "P" de la línea | AB |. Debería ser fácil modificar esto para PointF .

Encontrar el punto más cercano es solo cuestión de buscar una distancia mínima. LINQ tiene métodos para esto.

El punto C más cercano estará en una línea cuya pendiente es recíproca de AB y que se cruza con P Parece que podría ser tarea, pero voy a dar algunas pistas bastante fuertes, para aumentar el nivel de alerta del spoiler:

  • Solo puede haber una línea.

  • Este es un sistema de ecuaciones de dos líneas. Solo solucione x e y .

  • Dibuja un segmento de línea entre A y B ; llama esto L La ecuación para L es y = mx + b , donde m es la relación de las coordenadas y a las coordenadas x. Resuelve para b usando A o B en la expresión.

  • Haz lo mismo que arriba, pero para CP . Ahora resuelve el sistema lineal simultáneo de ecuaciones.

  • Una búsqueda en Google le dará una gran cantidad de ejemplos para elegir.

En caso de que alguien esté buscando la forma de hacerlo con Java + LibGdx:

Intersector.nearestSegmentPoint

Encuentre la pendiente a1 de AB dividiendo la diferencia y con la diferencia x; luego dibuja una línea perpendicular (con pendiente a2 = -1 / a1, necesitas resolver el desplazamiento (b2) colocando las coordenadas de P en y = a2 * x + b2); entonces tienes dos líneas (es decir, dos ecuaciones lineales), y necesitas resolver la intersección. Ese será tu punto más cercano.

Haga las matemáticas bien, y la función será bastante trivial para escribir.

Para elaborar un poco:

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

Espero que no haya cometido ningún error :) ACTUALIZACIÓN Por supuesto que sí. Servirme bien para no resolver las cosas en papel primero. Me merecía cada voto negativo, pero esperaba que alguien me corrigiera. Reparado (espero).

Las flechas señalan el camino.

ACTUALIZACIÓN Ah, los casos de esquina. Sí, algunos lenguajes no manejan bien los infinitos. Dije que la solución no tenía lenguaje ...

Puede verificar los casos especiales, son bastante fáciles. El primero es cuando la diferencia x es 0. Eso significa que la línea es vertical, y el punto más cercano está en una perpendicular horizontal. Por lo tanto, x = Ax, y = Px .

El segundo es cuando y la diferencia es 0, y lo opuesto es verdad. Por lo tanto, x = Px, y = Ay

Escribí esto hace mucho tiempo, no es muy diferente a lo que otros han dicho, pero es una solución de copiar / pegar en C # si tienes una clase (o estructura) llamada PointF con miembros X e 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); }

Actualización : Mirando los comentarios, parece que lo adapté a C # del mismo código fuente mencionado en la respuesta aceptada.

Esta respuesta se basa en ideas de geometría proyectiva.

Calcule el producto cruzado (Ax, Ay, 1) × (Bx, By, 1) = (u, v, w). El vector resultante describe la línea que conecta A y B: tiene la ecuación ux + vy + w = ​​0. Pero también puede interpretar (u, v, 0) como un punto infinitamente lejano en una dirección perpendicular a esa línea. Al hacer otro producto cruzado, obtiene la línea que une el punto del sombrero con P: (u, v, 0) × (Px, Py, 1). Y para cruzar esa línea con la línea AB, haces otro producto cruzado: ((u, v, 0) × (Px, Py, 1)) × (u, v, w). El resultado será un vector de coordenadas homogéneo (x, y, z) a partir del cual puede leer las coordenadas de este punto más cercano como (x / z, y / z).

Tome todo junto y obtendrá la siguiente fórmula:

Utilizando un sistema de álgebra computacional, puede encontrar las coordenadas resultantes para ser las siguientes:

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

Como nota, hay muchos términos recurrentes. Al inventar nombres (bastante arbitrarios) para estos, puede obtener el siguiente resultado final, escrito en pseudocódigo:

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)

Beneficios de este enfoque:

  • Sin distinciones de casos
  • Sin raíces cuadradas
  • Solo una sola división

La respuesta de Justin L. es casi correcta, pero no verifica si la distancia normalizada es menor que 0, o mayor que la magnitud del vector AB. Entonces no funcionará bien cuando la proyección del vector P esté fuera de límites (del segmento de línea AB). Aquí está el pseudocódigo corregido:

function GetClosestPoint(A, B, P) { vectorAP = (p.x - a.x, p.y - a.y) //Vector from A to P vectorAB = (b.x - a.x, b.y - a.y) //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 = a.x returnPoint.y = a.y } else if (distance > magnitudeAB) { returnPoint.x = b.x returnPoint.y = b.y } else { returnPoint.x = a.x + vectorAB[0]*distance returnPoint.y = a.y + vectorAB[1]*distance } }

Su punto ( X ) será una combinación lineal de los puntos A y B :

X = k A + (1-k) B

Para que X esté realmente en el segmento de línea, el parámetro k debe estar entre 0 y 1, inclusive. Puede calcular k de la siguiente manera:

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

(donde el período denota el producto punto)

Luego, para asegurarse de que el punto está realmente en el segmento de línea:

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

si alguien está interesado en una función C # XNA basada en lo anterior:

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