Encontrar las coordenadas de los puntos de la matriz de distancia

Question

Tengo un conjunto de puntos (con coordenadas desconocidas) y la matriz de distancia. Necesito encontrar las coordenadas de estos puntos para trazarlos y mostrar la solución de mi algoritmo.

Puedo establecer uno de estos puntos en la coordenada (0,0) para simplificar, y encontrar los demás. ¿Alguien puede decirme si es posible encontrar las coordenadas de los otros puntos, y si es así, cómo?

¡Gracias de antemano!

EDITAR olvidaba decir que tengo las coordenadas en x-y solamente

Answer 1

Paso 1, arbitrariamente asignar un punto P1 como (0,0).

Paso 2, asignar arbitrariamente un punto P2 a lo largo del eje x positivo. (0, Dp1p2)

Paso 3, encontrar un punto P3 de tal manera que

Dp1p2 ~= Dp1p3+Dp2p3 
Dp1p3 ~= Dp1p2+Dp2p3 
Dp2p3 ~= Dp1p3+Dp1p2 

y establece ese punto de la y de dominio "positivo" (si cumple cualquiera de estos criterios, el punto debe ser colocado en el eje P1P2).
utilizar la ley del coseno para determinar la distancia:

cos (A) = (Dp1p2^2 + Dp1p3^2 - Dp2p3^2)/(2*Dp1p2* Dp1p3) 
P3 = (Dp1p3 * cos (A), Dp1p3 * sin(A)) 

Ahora han construido con éxito un espacio ortonormal y se coloca a tres puntos en ese espacio.

Paso 4: Para determinar todos los otros puntos, repita el paso 3, para darle una coordenada y tentativa. (Xn, Yn).
Compara la distancia {(Xn, Yn), (X3, Y3)} a Dp3pn en tu matriz. Si es idéntico, ha identificado con éxito la coordenada para el punto n. De lo contrario, el punto n está en (Xn, -Yn).

en cuenta que es una alternativa al paso 4, pero es demasiado matemática para un sábado por la tarde

Answer 2

Si por puntos p, q, y r tiene PQ, QR, y RP en su matriz, que tiene un triángulo.

Dondequiera que tenga un triángulo en su matriz, puede calcular una de las dos soluciones para ese triángulo (independientemente de una transformación euclidiana del triángulo en el plano). Es decir, para cada triángulo que calcula, su imagen especular también es un triángulo que satisface las restricciones de distancia en p, qy r. El hecho de que haya dos soluciones, incluso para un triángulo, conduce al problema de quiralidad: debe elegir la quiralidad (orientación) de cada triángulo, y no todas las opciones pueden conducir a una solución factible al problema.

Sin embargo, tengo algunas sugerencias. Si las entradas de números son pequeñas, considere usar simulated annealing. Podría incorporar la quiralidad en el paso de recocido. Esto será lento para sistemas grandes, y puede no converger a una solución perfecta, pero para algunos problemas es lo mejor que puedes hacer.

La segunda sugerencia no le dará una solución perfecta, pero distribuirá el error: el method of least squares. En su caso, la función objetivo será el error entre las distancias en su matriz y las distancias reales entre sus puntos.

Answer 3

Las respuestas basadas en ángulos son difíciles de implementar y no se pueden generalizar fácilmente a datos en dimensiones superiores.Un mejor enfoque es que se menciona en mis y WimC de respuestas here: dada la matriz de distancia D(i, j), definir

M(i, j) = 0.5*(D(1, j)^2 + D(i, 1)^2 - D(i, j)^2) 

que debe ser una matriz semi-definida positiva con rango igual a la dimensión euclidiana mínima k en el que los puntos pueden estar incrustado. Las coordenadas de los puntos pueden ser obtenidos a partir de los vectores propios kv(i) de M correspondientes a valores propios distintos de cero q(i): lugar los vectores sqrt(q(i))*v(i) como columnas en una matriz de Xn x k; entonces cada fila de X es un punto. En otras palabras, sqrt(q(i))*v(i) proporciona el i componente th de todos los puntos.

Los valores propios y los vectores propios de una matriz se pueden obtener fácilmente en la mayoría de los lenguajes de programación (por ejemplo, el uso de GSL en C/C++, utilizando la función incorporada eig en Matlab, utilizando Numpy en Python, etc.)

Tenga en cuenta que este método particular siempre coloca el primer punto en el origen, pero cualquier rotación, reflexión o traducción de los puntos también satisfará la matriz de distancia original.

Answer 4

Esto es un problema de matemáticas. Para derivar la matriz de coordenadas X solo dada por su matriz de distancia.

Sin embargo, hay una solución eficiente para esto - Escalamiento multidimensional, que hace un poco de álgebra lineal. En pocas palabras, requiere una matriz de distancia Euclidiana por pares D, y la salida es la coordenada Y estimada (tal vez rotada), que es una aproximación a X. Por razones de programación, simplemente use SciKit.manifold.MDS en Python.