从距离矩阵中寻找点的坐标

Question

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

我可以在坐标(0,0)中设置其中一个点来简化,并找到其他点.任何人都可以告诉我是否有可能找到其他点的坐标,如果可以,怎么样？

提前致谢!

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

Answer 1

基于角度的答案实施起来很麻烦,并且不能容易地推广到更高维度的数据.更好的方法是,在我和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)的M对应于非零特征值q(i):代替矢量sqrt(q(i))*v(i)作为在列n x k矩阵X; 然后每一行X都是一个点.换句话说,sqrt(q(i))*v(i)给出i所有点的组成部分.

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

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

Answer 2

步骤1，任意指定一个点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 有替代方法，但对于星期六下午来说数学太多了