不断缩放 3 个圆圈直到它们相交

Question

我在Python中实现了trilateration定位算法，到目前为止，结果看起来很不一样，因为计算的距离受到信号干扰的影响，所以它看起来像这样：

什么时候应该看起来像这样：

所以我在考虑使用常数因子同时缩放圆圈，直到它们都在一个点相交（这将是最佳的）或直到它们相互距离的总和最小。给定 2D-space 中三个圆的 XY 坐标，以及它们与参考点（其中一个圆的中心）的计算距离 FSPL，函数应该 return 最小化误差的最佳比例因子。它应该是这样的：

def find_best_scaling_constant(p1, p2, p3, r1, r2, r3):
  # some magic here
  return scalingConstant

find_best_scaling_constant((0.00, 0.00), (3.15, -0.47), (4.90, 7.00), 1.12, 1.77, 0.18)

我不是数学家，所以我不知道这个逻辑是否合理，但如果有人有意见或更好的想法，请分享。会有很大帮助！

Answer 1

让圆心的坐标为：

并让您计算出的相应半径为：

分别。所以看起来您正在寻找点和具有以下属性:

的比例因子

等价地，我们需要在平面中找到一个点，它是三个圆的公共交点，由re-scaling原圆的半径乘公因数得到k，或者用数学符号表示，我们需要求解系统

显然上面的系统和之前写的属性系统是等价的

为了简化事情，对系统中每个等式的两边进行平方：

根据毕达哥拉斯定理，写

这就是为什么在显式公式中，上面的三元方程组实际上是二次方程组：

将每个等式的 right-hand 边移动到 left-hand 边后，变为：

展开每个方程中的所有平方差并对项重新排序：

为了简化这个系统，从第一个方程减去第二个方程，然后从第二个方程减去第三个方程并保留一个二次方程，假设保留第一个二次方程：

寻找这个系统的解决方案的思路如下：

为了简化符号和表达式，我们可以使用一些线性代数的符号。定义如下二乘二矩阵和二乘一column-vectors:

当我们将后一个矩阵方程乘以M的逆矩阵时：

我们也用矩阵记法来写

最后，找到三个圆的交点的算法，在用适当的缩放因子缩放后，可以表述如下：

观察二次方程 z 有两个解。我选择的带负号的是第一个交点，只要三个圆都在每个圆的外部并且初始半径为 non-intersecting。还有第二个交点，对应z的正解。如果您有来自第四座塔的可用信息，那么您将能够选择正确的点，甚至可能能够将问题完全线性化。但是只有这些可用数据，你有两个解决方案。

我使用以下 hand-made 示例测试了该算法：

x1 = 0;  y1 = 0;  r1 = sqrt(13)/3;
x2 = 5;  y2 = 1;  r2 = sqrt(13)/3;
x3 = 3;  y3 = 7;  r3 = sqrt(17)/3;

它会输出正确的位置

x = 2;  y = 3;

和比例因子 k = 3.

我在 Matlab/Octave 实现了它，因为我对那里的线性代数很满意：

function [xy, k] = location_scaled(x1, y1, r1, x2, y2, r2, x3, y3, r3)
        
        M = 2*[x2 - x1  y2 - y1; 
               x3 - x2  y3 - y2];
        A = [r1^2 - r2^2; 
             r2^2 - r3^2];
        B = [x2^2 + y2^2 - x1^2 - y1^2; 
             x3^2 + y3^2 - x2^2 - y2^2];
        A = M\A;
        B = M\B;
        
        a = A'*A;
        b = 2*B'*A - 2*[x1  y1]*A - r1^2;
        c = [x1 y1]*[x1; y1] - 2*[x1  y1]*B + B'*B;
        
        k = (- b - sqrt(b^2 - 4*a*c)) / (2*a);
        
        xy = k*A + B;
        k = sqrt(k);
        
end

这里是 python 版本：

import numpy as np

def location_scaled(x1, y1, r1, x2, y2, r2, x3, y3, r3):

        M = 2*np.array([[x2 - x1,  y2 - y1], 
                        [x3 - x2,  y3 - y2]])
        A = np.array([r1**2 - r2**2, 
                      r2**2 - r3**2])
        B = np.array([x2**2 + y2**2 - x1**2 - y1**2, 
                      x3**2 + y3**2 - x2**2 - y2**2])

        M = np.linalg.inv(M)
        A = M.dot(A)
        B = M.dot(B)
        x1_y1 = np.array([x1, y1])

        a = A.dot(A)
        b = 2*B.dot(A) - 2*x1_y1.dot(A) - r1**2
        c = x1*x1 + y1*y1 - 2*x1_y1.dot(B) + B.dot(B)

        k = (- b - np.sqrt(b*b - 4*a*c)) / (2*a);

        return k*A + B, np.sqrt(k)

不断缩放 3 个圆圈直到它们相交

Scaling 3 circles constantly until they intersect

python

geometry

geolocation

trilateration