无标记三角测量/三边测量：未知距离对应关系的定位问题

嘿，这个问题是常规三角测量的有趣变体对吧？平时我们都是明确知道哪个距离对应哪个参考点，现在配对完全打乱了，得换个思路来定位测试点$x$。我给你梳理下具体的解决步骤：

核心思路 #

本质上，我们要做的是枚举所有可能的距离-参考点配对组合，对每个组合用常规三角测量求解，再筛选出符合所有条件的有效解。因为三个距离对应三个点，总共有6种可能的配对方式，这个枚举量很小，完全可行。

具体步骤 #

1. 列出所有配对组合 #

假设我们拿到的三个距离值是$r_1, r_2, r_3$，参考点是$A、B、C$，那么所有可能的配对有6种：

• 组合1：$d(A,x)=r_1$，$d(B,x)=r_2$，$d(C,x)=r_3$
• 组合2：$d(A,x)=r_1$，$d(B,x)=r_3$，$d(C,x)=r_2$
• 组合3：$d(A,x)=r_2$，$d(B,x)=r_1$，$d(C,x)=r_3$
• 组合4：$d(A,x)=r_2$，$d(B,x)=r_3$，$d(C,x)=r_1$
• 组合5：$d(A,x)=r_3$，$d(B,x)=r_1$，$d(C,x)=r_2$
• 组合6：$d(A,x)=r_3$，$d(B,x)=r_2$，$d(C,x)=r_1$

2. 对每个组合求解$x$的位置 #

针对每一种组合，用常规三角测量的方法解方程组。举个例子，拿组合1来说：
设$A=(a_x,a_y)$，$B=(b_x,b_y)$，$C=(c_x,c_y)$，$x=(x,y)$，可以列出以下方程组：
$$
\begin{cases}
(x - a_x)^2 + (y - a_y)^2 = r_1^2 \
(x - b_x)^2 + (y - b_y)^2 = r_2^2 \
(x - c_x)^2 + (y - c_y)^2 = r_3^2
\end{cases}
$$
求解的时候，先把前两个方程相减，消去$x^2$和$y2$项，得到一条线性方程；再把第一个和第三个方程相减，得到另一条线性方程，联立这两条直线就能算出$x$的候选坐标。

注意：这里可能出现两种情况——要么方程组无解（三个圆没有公共交点），要么有两个解（三个圆交于两点）。

3. 验证候选解的有效性 #

对每个组合得到的候选解，一定要代入三个距离方程验证是否全部满足（毕竟联立线性方程可能引入增根）。另外，如果是实际应用场景，还可以结合$x$的预期区域来筛选（比如不可能在某个障碍物后面）。

4. 处理多解情况 #

如果有多个组合都得到了有效解，那你可能需要额外的信息来区分——比如增加第四个参考点，或者已知$x$的大致范围。不过在大多数实际场景中，不合理的解很容易被排除，最终只会剩下一个正确的位置。

举个直观的例子 #

假设参考点是等边三角形：$A=(0,0)$，$B=(2,0)$，$C=(1,\sqrt{3})$，拿到的三个距离是$1,1,\sqrt{3}$。

• 当配对是$d(A,x)=1$，$d(B,x)=1$，$d(C,x)=\sqrt{3}$时，解是$(1,0)$，代入验证完全符合；
• 其他配对要么无解，要么得到的坐标代入后不满足所有距离条件，最终只有$(1,0)$是有效解。

内容的提问来源于stack exchange，提问作者Elchanan Solomon