I have a set of points (with unknow coordinates) and the distance matrix. I need to find the coordinates of these points in order to plot them and show the solution of my algorithm.
我有一组点(不知道坐标)和距离矩阵。我需要找到这些点的坐标以便绘制它们并显示算法的解。
I can set one of these points in the coordinate (0,0) to simpify, and find the others. Can anyone tell me if it's possible to find the coordinates of the other points, and if yes, how?
我可以在坐标(0,0)中将这些点中的一个设为simpify，然后找到其他点。谁能告诉我是否有可能找到其他点的坐标，如果有，怎么找到?
Thanks in advance!
提前谢谢!
EDIT Forgot to say that I need the coordinates on x-y only
编辑忘了说我只需要x-y上的坐标
4 个解决方案
#1
4
Step 1, arbitrarily assign one point P1 as (0,0).
步骤1，任意指定一个点P1(0,0)。
Step 2, arbitrarily assign one point P2 along the positive x axis. (0, Dp1p2)
步骤2，沿正x轴任意分配一点P2。(0,Dp1p2)
Step 3, find a point P3 such that
第三步，找一个点P3
Dp1p2 ~= Dp1p3+Dp2p3
Dp1p3 ~= Dp1p2+Dp2p3
Dp2p3 ~= Dp1p3+Dp1p2
and set that point in the "positive" y domain (if it meets any of these criteria, the point should be placed on the P1P2 axis).
Use the cosine law to determine the distance:
在“正”y域中设置这个点(如果它满足这些条件中的任何一个，那么点应该放在P1P2轴上)。利用余弦定律确定距离:
cos (A) = (Dp1p2^2 + Dp1p3^2 - Dp2p3^2)/(2*Dp1p2* Dp1p3)
P3 = (Dp1p3 * cos (A), Dp1p3 * sin(A))
You have now successfully built an orthonormal space and placed three points in that space.
你现在已经成功地建立了一个标准正交空间并在这个空间中放置了三个点。
Step 4: To determine all the other points, repeat step 3, to give you a tentative y coordinate. (Xn, Yn).
Compare the distance {(Xn, Yn), (X3, Y3)} to Dp3pn in your matrix. If it is identical, you have successfully identified the coordinate for point n. Otherwise, the point n is at (Xn, -Yn).
步骤4:确定所有其他的点，重复第三步，给你一个临时的y坐标。(Xn Yn)。比较矩阵中{Xn, Yn)， (X3, Y3)}到Dp3pn的距离。如果它是相同的，你已经成功地识别了点n的坐标，否则，点n在(Xn， -Yn)
Note there is an alternative to step 4, but it is too much math for a Saturday afternoon
注意，除了第4步，还有另外一种选择，但对于周六下午来说，这实在是太难了
#2
12
The answers based on angles are cumbersome to implement and can't be easily generalized to data in higher dimensions. A better approach is that mentioned in my and WimC's answers here: given the distance matrix D(i, j), define
基于角度的答案很难实现，很难推广到更高维度的数据。我和WimC在这里的答案中提到了一种更好的方法:给定距离矩阵D(i, j)，定义
M(i, j) = 0.5*(D(1, j)^2 + D(i, 1)^2 - D(i, j)^2)
which should be a positive semi-definite matrix with rank equal to the minimal Euclidean dimension k in which the points can be embedded. The coordinates of the points can then be obtained from the k eigenvectors v(i) of M corresponding to non-zero eigenvalues q(i): place the vectors sqrt(q(i))*v(i) as columns in an n x k matrix X; then each row of X is a point. In other words, sqrt(q(i))*v(i) gives the ith component of all of the points.
它应该是一个正的半定矩阵它的秩等于最小欧几里得维k点可以被嵌入其中。这些点的坐标可以从M对应于非零特征值q(i)的k特征向量v(i)得到:将向量sqrt(q(i))*v(i)作为n×k矩阵x中的列;那么每一行X都是一个点。换句话说，sqrt(q(i))*v(i)给出了所有点的第i个分量。
The eigenvalues and eigenvectors of a matrix can be obtained easily in most programming languages (e.g., using GSL in C/C++, using the built-in function eig in Matlab, using Numpy in Python, etc.)
矩阵的特征值和特征向量在大多数编程语言中都很容易得到(例如在C/ c++中使用GSL，在Matlab中使用内置函数eig，在Python中使用Numpy等)。
Note that this particular method always places the first point at the origin, but any rotation, reflection, or translation of the points will also satisfy the original distance matrix.
注意，这个特殊的方法总是在原点处放置第一个点，但是任何旋转、反射或点的平移也会满足原距离矩阵。
#3
1
If for points p, q, and r you have pq, qr, and rp in your matrix, you have a triangle.
如果对于点pq和r你的矩阵中有pq qr和rp，你有一个三角形。
Wherever you have a triangle in your matrix you can compute one of two solutions for that triangle (independent of a euclidean transform of the triangle on the plane). That is, for each triangle you compute, it's mirror image is also a triangle that satisfies the distance constraints on p, q, and r. The fact that there are two solutions even for a triangle leads to the chirality problem: You have to choose the chirality (orientation) of each triangle, and not all choices may lead to a feasible solution to the problem.
只要矩阵中有一个三角形你就可以计算出这个三角形的两个解中的一个(与平面上的三角形的欧几里得变换无关)。每个三角形计算,镜像是一个三角形,满足距离限制p,q,r。事实上,有两个解决方案甚至一个三角形导致手性问题:你必须选择每个三角形的手性(方向),并不是所有的选择可能会导致一个可行的解决问题的办法。
Nevertheless, I have some suggestions. If the number entries is small, consider using simulated annealing. You could incorporate chirality into the annealing step. This will be slow for large systems, and it may not converge to a perfect solution, but for some problems it's the best you and do.
不过，我有一些建议。如果数量项很小，考虑使用模拟退火。你可以在退火步骤中加入手性。这对于大型系统来说是很慢的，而且它可能不会收敛到一个完美的解决方案，但是对于某些问题，这是最好的办法。
The second suggestion will not give you a perfect solution, but it will distribute the error: the method of least squares. In your case the objective function will be the error between the distances in your matrix, and actual distances between your points.
第二个建议不会给你一个完美的解决方案，但是它会分配误差:最小二乘法。在这种情况下，目标函数将是矩阵中距离之间的误差，以及点之间的实际距离。
#4
0
This is a math problem. To derive coordinate matrix X only given by its distance matrix.
这是一道数学题。导出仅由距离矩阵给出的坐标矩阵X。
However there is an efficient solution to this -- Multidimensional Scaling, that do some linear algebra. Simply put, it requires a pairwise Euclidean distance matrix D, and the output is the estimated coordinate Y (perhaps rotated), which is a proximation to X. For programming reason, just use SciKit.manifold.MDS in Python.
然而，对于这个问题有一个有效的解决方法——多维尺度变换，它可以做一些线性代数运算。简单地说，它需要一个成对的欧氏距离矩阵D，输出是估计的坐标Y(可能是旋转的)，这是x的近似值，因为编程的原因，只是使用scikit.。MDS Python。
#1
4
Step 1, arbitrarily assign one point P1 as (0,0).
步骤1，任意指定一个点P1(0,0)。
Step 2, arbitrarily assign one point P2 along the positive x axis. (0, Dp1p2)
步骤2，沿正x轴任意分配一点P2。(0,Dp1p2)
Step 3, find a point P3 such that
第三步，找一个点P3
Dp1p2 ~= Dp1p3+Dp2p3
Dp1p3 ~= Dp1p2+Dp2p3
Dp2p3 ~= Dp1p3+Dp1p2
and set that point in the "positive" y domain (if it meets any of these criteria, the point should be placed on the P1P2 axis).
Use the cosine law to determine the distance:
在“正”y域中设置这个点(如果它满足这些条件中的任何一个，那么点应该放在P1P2轴上)。利用余弦定律确定距离:
cos (A) = (Dp1p2^2 + Dp1p3^2 - Dp2p3^2)/(2*Dp1p2* Dp1p3)
P3 = (Dp1p3 * cos (A), Dp1p3 * sin(A))
You have now successfully built an orthonormal space and placed three points in that space.
你现在已经成功地建立了一个标准正交空间并在这个空间中放置了三个点。
Step 4: To determine all the other points, repeat step 3, to give you a tentative y coordinate. (Xn, Yn).
Compare the distance {(Xn, Yn), (X3, Y3)} to Dp3pn in your matrix. If it is identical, you have successfully identified the coordinate for point n. Otherwise, the point n is at (Xn, -Yn).
步骤4:确定所有其他的点，重复第三步，给你一个临时的y坐标。(Xn Yn)。比较矩阵中{Xn, Yn)， (X3, Y3)}到Dp3pn的距离。如果它是相同的，你已经成功地识别了点n的坐标，否则，点n在(Xn， -Yn)
Note there is an alternative to step 4, but it is too much math for a Saturday afternoon
注意，除了第4步，还有另外一种选择，但对于周六下午来说，这实在是太难了
#2
12
The answers based on angles are cumbersome to implement and can't be easily generalized to data in higher dimensions. A better approach is that mentioned in my and WimC's answers here: given the distance matrix D(i, j), define
基于角度的答案很难实现，很难推广到更高维度的数据。我和WimC在这里的答案中提到了一种更好的方法:给定距离矩阵D(i, j)，定义
M(i, j) = 0.5*(D(1, j)^2 + D(i, 1)^2 - D(i, j)^2)
which should be a positive semi-definite matrix with rank equal to the minimal Euclidean dimension k in which the points can be embedded. The coordinates of the points can then be obtained from the k eigenvectors v(i) of M corresponding to non-zero eigenvalues q(i): place the vectors sqrt(q(i))*v(i) as columns in an n x k matrix X; then each row of X is a point. In other words, sqrt(q(i))*v(i) gives the ith component of all of the points.
它应该是一个正的半定矩阵它的秩等于最小欧几里得维k点可以被嵌入其中。这些点的坐标可以从M对应于非零特征值q(i)的k特征向量v(i)得到:将向量sqrt(q(i))*v(i)作为n×k矩阵x中的列;那么每一行X都是一个点。换句话说，sqrt(q(i))*v(i)给出了所有点的第i个分量。
The eigenvalues and eigenvectors of a matrix can be obtained easily in most programming languages (e.g., using GSL in C/C++, using the built-in function eig in Matlab, using Numpy in Python, etc.)
矩阵的特征值和特征向量在大多数编程语言中都很容易得到(例如在C/ c++中使用GSL，在Matlab中使用内置函数eig，在Python中使用Numpy等)。
Note that this particular method always places the first point at the origin, but any rotation, reflection, or translation of the points will also satisfy the original distance matrix.
注意，这个特殊的方法总是在原点处放置第一个点，但是任何旋转、反射或点的平移也会满足原距离矩阵。
#3
1
If for points p, q, and r you have pq, qr, and rp in your matrix, you have a triangle.
如果对于点pq和r你的矩阵中有pq qr和rp，你有一个三角形。
Wherever you have a triangle in your matrix you can compute one of two solutions for that triangle (independent of a euclidean transform of the triangle on the plane). That is, for each triangle you compute, it's mirror image is also a triangle that satisfies the distance constraints on p, q, and r. The fact that there are two solutions even for a triangle leads to the chirality problem: You have to choose the chirality (orientation) of each triangle, and not all choices may lead to a feasible solution to the problem.
只要矩阵中有一个三角形你就可以计算出这个三角形的两个解中的一个(与平面上的三角形的欧几里得变换无关)。每个三角形计算,镜像是一个三角形,满足距离限制p,q,r。事实上,有两个解决方案甚至一个三角形导致手性问题:你必须选择每个三角形的手性(方向),并不是所有的选择可能会导致一个可行的解决问题的办法。
Nevertheless, I have some suggestions. If the number entries is small, consider using simulated annealing. You could incorporate chirality into the annealing step. This will be slow for large systems, and it may not converge to a perfect solution, but for some problems it's the best you and do.
不过，我有一些建议。如果数量项很小，考虑使用模拟退火。你可以在退火步骤中加入手性。这对于大型系统来说是很慢的，而且它可能不会收敛到一个完美的解决方案，但是对于某些问题，这是最好的办法。
The second suggestion will not give you a perfect solution, but it will distribute the error: the method of least squares. In your case the objective function will be the error between the distances in your matrix, and actual distances between your points.
第二个建议不会给你一个完美的解决方案，但是它会分配误差:最小二乘法。在这种情况下，目标函数将是矩阵中距离之间的误差，以及点之间的实际距离。
#4
0
This is a math problem. To derive coordinate matrix X only given by its distance matrix.
这是一道数学题。导出仅由距离矩阵给出的坐标矩阵X。
However there is an efficient solution to this -- Multidimensional Scaling, that do some linear algebra. Simply put, it requires a pairwise Euclidean distance matrix D, and the output is the estimated coordinate Y (perhaps rotated), which is a proximation to X. For programming reason, just use SciKit.manifold.MDS in Python.
然而，对于这个问题有一个有效的解决方法——多维尺度变换，它可以做一些线性代数运算。简单地说，它需要一个成对的欧氏距离矩阵D，输出是估计的坐标Y(可能是旋转的)，这是x的近似值，因为编程的原因，只是使用scikit.。MDS Python。