16

我有一组点（坐标未知）和距离矩阵。我需要找到这些点的坐标以便绘制它们并显示我的算法的解决方案。

我可以在坐标 (0,0) 中设置这些点之一以简化，并找到其他点。谁能告诉我是否可以找到其他点的坐标，如果可以，如何？

提前致谢！

编辑忘了说我只需要 xy 上的坐标

4

4 回答 4

20

基于角度的答案实施起来很麻烦，并且不能轻易推广到更高维度的数据。更好的方法是我和 WimC 的答案中提到的：给定距离矩阵D(i, j)，定义

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

它应该是一个正半定矩阵，其秩等于k可以嵌入点的最小欧几里得维数。然后可以从对应于非零特征值的k特征向量v(i)中获得点的坐标：将向量作为列放在矩阵中；那么每一行都是一个点。换句话说，给出所有点的第 th 个分量。Mq(i)sqrt(q(i))*v(i)n x kXXsqrt(q(i))*v(i)i

矩阵的特征值和特征向量可以在大多数编程语言中轻松获得（例如，在 C/C++ 中使用 GSL，在 Matlab 中使用内置函数eig，在 Python 中使用 Numpy 等）

请注意，此特定方法始终将第一个点放在原点，但点的任何旋转、反射或平移也将满足原始距离矩阵。

于 2013-06-18T20:01:41.490 回答
5

第一步，任意指定一个点P1为(0,0)。

第二步，沿x轴正方向任意指定一个点P2。(0, Dp1p2)

步骤 3，找到一个点 P3 使得

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

并将该点设置在“正”y 域中（如果它满足这些标准中的任何一个，则该点应放置在 P1P2 轴上）。
使用余弦定律确定距离：

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

您现在已经成功地构建了一个正交空间并在该空间中放置了三个点。

第 4 步：要确定所有其他点，请重复第 3 步，给您一个暂定的 y 坐标。(Xn, Yn)。
比较矩阵中的距离 {(Xn, Yn), (X3, Y3)} 到 Dp3pn。如果相同，则您已成功识别点 n 的坐标。否则，点 n 在 (Xn, -Yn) 处。

请注意，第 4 步还有一个替代方法，但对于周六下午来说，这太数学了

于 2012-06-09T18:11:02.300 回答
1

如果对于点 p、q 和 r，您的矩阵中有 pq、qr 和 rp，则您有一个三角形。

无论您的矩阵中有一个三角形，您都可以计算该三角形的两个解之一（独立于平面上三角形的欧几里德变换）。也就是说，对于您计算的每个三角形，它的镜像也是一个满足对 p、q 和 r 的距离约束的三角形。即使对于三角形也有两种解决方案这一事实导致了手性问题：您必须选择每个三角形的手性（方向），并且并非所有选择都可能导致问题的可行解决方案。

不过，我有一些建议。如果条目数很少，请考虑使用模拟退火。您可以将手性纳入退火步骤。这对于大型系统来说会很慢，并且可能不会收敛到完美的解决方案，但对于某些问题，这是最好的选择。

第二个建议不会给你一个完美的解决方案，但它会分布错误：最小二乘法。在您的情况下，目标函数将是矩阵中的距离与点之间的实际距离之间的误差。

于 2012-06-09T18:20:02.890 回答
1

这是一道数学题。导出坐标矩阵 X 仅由其距离矩阵给出。

然而，有一个有效的解决方案——多维缩放，它可以做一些线性代数。简单地说，它需要一个成对的欧几里得距离矩阵 D，输出是估计的坐标 Y（可能是旋转的），它是 X 的近似值。出于编程原因，在 Python 中使用 SciKit.manifold.MDS 即可。

于 2015-09-15T23:02:39.763 回答