algorithm - 仅使用距离矩阵放置点

Question

我想可视化一些点，但只给出了它们的距离矩阵。有什么好的方法可以找到一种可能的方式将它们放置在二维空间上。

输入:一个距离矩阵

输出:这些点的坐标

Answer 1

对于给定的矩阵，如果你想出一个可能的位置，那么点的任何平移也将满足矩阵，任何旋转和镜像也是如此。

对于一种可能的展示位置:

选择 3 个点 A B C(即矩阵中的 3 行)，它们形成一个三角形，距离为 AB、AC 和 BC，取自矩阵。这些点不可能都在一条线上，所以 AB != AC + BC，AC != AB + BC 和 BC != AB + AC。

将 A 置于原点，将 B 置于 (AB, 0)。然后使用余弦法则推导出直线 AB 和 AC 之间的角度:

角度 = arccos((AB² + AC² - BC²)/(2 * AB * AC))

现在你有了角度，你可以计算 C 的位置:

C = (cos(角度) * AC, sin(角度) * AC);

你现在有了 A B 和 C 的位置。你可以遍历矩阵中与其他点对应的其他每一行，并找到每个点与 A B 和 C 之间的距离。然后你可以使用这个公式来工作根据你假设的 A B C 位置和点到每个点的距离得出点的位置:

Finding location of a point on 2D plane, given the distances to three other know points

因此，您实际上只需要矩阵每一行的 3 个值。对于一个大矩阵，大部分都是完全多余的。如果您正在尝试最小化存储空间，这可能对您有所帮助。

请记住，任何平移、旋转和镜像也是有效的。