定位设备（相交圆）

Question

8

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

这是一个简单的示例网络图。 simple network

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

记录距离后，我将距离信息存储在哈希中。

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）周围绘制一系列圆，看起来像这样：

enter image description here

我知道其他节点必须位于我画在A周围的线上，但是如何定位它们以便绘制它们之间的距离，并相交这些圆以创建图形呢？

- Dan Prince

@Prince，你已经有了每对节点之间的距离。你可以用它来绘制一个图形。但是你确切想要什么呢？你想要每个点在二维平面上的笛卡尔坐标吗？ - nitish712

1

问题不在于你的数学生疏，而在于你试图解决一个困难的问题。这个问题显然不能直接使用封闭形式方程来解决。 - Marko Topolnik

1

为了让那些通过语言筛选问题流的人能看到这个问题，@GregKopff。 - Marko Topolnik

@nitish712 我希望设备能够正确地相对定位。笛卡尔坐标系会很好。 - Dan Prince

1

你可以将下一个节点放置在其圆圈上的任何位置。然后，您可以使用来自两个节点的信息开始定位其他节点。由于您可以围绕任何节点旋转360度，因此并不存在唯一的解决方案，但距离仍将保持不变。 - RobH

显示剩余9条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- nitish712 · Accepted Answer

从任意一个点 A 开始。现在取第二个点 B，并将其绘制到以 A 为中心、半径为 A 和 B 之间距离的圆上的某处。现在取另一个点 C。假设距离 (A,C)=x 和 (B,C)=y。找到圆形 (A,x) 和 (B,y) 的交点，并标记为 C。

其中，圆形(P,q) 指定了以 P 为中心和半径 q。

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

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

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

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

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

编辑：在任何阶段，如果有两个有效的坐标系，则可以选择其中任何一个，但我们仍然会到达其中一个有效的解决方案。