java - 定位装置(相交圆)

Question

我有一系列点，代表房间内的移动设备。以前我已经系统地从每个发出 ping 并记录它到达其他人的时间以计算距离。

这是示例网络的简单图表。

底部的 A 节点应该是 D 而不是

记录距离后，我得到了散列中的距离信息。

A = {B: 2, C: 1, D: 3}
B = {A: 2, C: 2, D: 2}
C = {A: 1, B: 2, D: 2}
D = {A: 3, B: 2, C: 2}

我的数学很生疏，但我觉得我应该能够使用这些值分别绘制圆圈，然后与圆圈相交以计算节点的相对图。

每次我尝试这样做时，我都会从围绕根节点(在本例中为 A)绘制的一系列圆圈开始，看起来像这样:

我知道其他节点必须位于我围绕 A 绘制的线上，但无法定位它们，如何绘制它们的距离以便与圆相交并创建图形？

Answer 1

从任何一个点开始，比如 A。现在取第二个点，比如 B，并将其绘制在圆上的某个位置，圆心为 A，半径为 A 和 B 之间的距离。现在取另一个点 C。让距离 (A,C)=x 和 (B,C)=y。找到圆 (A,x) 和 (B,y) 的交点。将其标记为 C。

其中圆 (P,q) 指定圆心在 P 和半径 q。

如果不存在这样的点，则给定的数据不正确。

现在取第 4 个 点，类似地找到圆心在前三个点的交点，半径分别为第 4 个和其他三个点之间的距离。应用此方法，直到绘制出所有点。

请注意，正如 RobH 指出的那样，可以有无限多的解决方案。由于您只需要一个虚拟表示，我想任何有效的解决方案都足够了。

上述算法的阶数为O(N^2)。如果点数大于 10000，则可能效率低下。

另请注意，要找到 k 个圆的交点，您首先需要找到任意两个圆的交点，并在其余圆上验证这些点。这是因为 k 圆最多可以在两点相交，假设所有圆都有不同的中心。

编辑:在任何阶段，如果一个点有两个有效图，我们可以选择其中任何一个，但我们会得出一个有效的解决方案。