定位设备(相交圆)

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.

其中circle (P,q)指定center P和radius q.

如果不存在这样的点,那么给定的数据是不正确的.

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

请注意,RobH指出,可以有无限多的解决方案.由于您只需要虚拟表示,我猜任何有效的解决方案都足够了.

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

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

编辑:在任何阶段,如果有一个点的两个有效图,我们可以选择其中任何一个,但我们到达一个有效的解决方案.