186 lines
18 KiB
Markdown
186 lines
18 KiB
Markdown
# 问题一：有界测向误差下定位区域的直径与圆覆盖
|
||
|
||
## 摘要
|
||
|
||
针对同一干扰源在多个检测点处的带误差方位观测，建立前向角域交集模型，将定位区域表示为二维线性不等式组的可行域。首先推导角域的半平面表达，给出兼顾空集、点、线段和无界区域的几何构造算法；随后证明，有界定位区域的直径必由一对顶点取得，且判断是否存在直径等于区域直径的覆盖圆，只需检验任意一组最远顶点的中点。通过符合题设测向条件的等边三角形反例，说明直径圆一般不能覆盖定位区域。进一步以最小包围圆连接定位精度和后续清除条件，并给出算法复杂度、数值处理原则及既有演练观测的复算结果。全部结论以有界误差模型为前提，不引入误差独立、正态或均匀分布假设。
|
||
|
||
**关键词：** 交会定位；有界误差；半平面交；凸多边形直径；最小包围圆。
|
||
|
||
## 1. 问题界定与思路来源
|
||
|
||
题目要求由若干检测点坐标及同一干扰源的示向度，求交会定位多边形的直径，并判断以该直径为直径的圆能否覆盖定位区域。题面规定测向误差在 $[-1^\circ,1^\circ]$ 内，同一地点重复测量的误差不变；示向度从正东沿逆时针方向计量。[题面第1页、附录2第(1)、(3)项](C:/Users/HelixCopex/code/MATH/issue/B题.pdf)
|
||
|
||
由此得到三步建模思路。第一，单次观测不能确定一条精确射线，却可以确定一个包含真实方向的角域，因此采用集合相交而非直线最小二乘。第二，角域可以写成半平面交，问题随之转化为凸几何问题。第三，“两点最远距离”和“覆盖全部位置所需半径”是不同的优化量，应分别计算直径和最小包围圆。
|
||
|
||
半平面、凸组合和凸集交运算属于标准凸分析工具，其背景见 Boyd 与 Vandenberghe 的《Convex Optimization》第2章；本文针对测向模型给出独立推导，不将一般理论本身视为新的研究贡献。[文献2](https://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf)
|
||
|
||
本文严格区分两个集合：问题一的 $P$ 仅表示测向角域之交；第二问及在线搜索中的 $K$ 可进一步结合源位置圆域和接收距离先验。向 $P$ 加入圆盘后，边界可能出现圆弧，不能继续把它当成原问题中的纯多边形。
|
||
|
||
## 2. 符号及基本假设
|
||
|
||
| 符号 | 含义 |
|
||
| --- | --- |
|
||
| $s_i=(s_{ix},s_{iy})$ | 第 $i$ 个检测点，坐标单位为米 |
|
||
| $\theta_i$ | 第 $i$ 次有效示向度 |
|
||
| $\delta_i$ | 误差半角，题设取 $1^\circ$ |
|
||
| $g=(x,y)$ | 未知干扰源位置 |
|
||
| $W_i$ | 第 $i$ 次测向对应的闭前向角域 |
|
||
| $P$ | 所有角域的交集 |
|
||
| $V=\{v_1,\ldots,v_m\}$ | 非空有界 $P$ 的顶点集 |
|
||
| $D(P)$ | 区域内任意两点距离的上确界 |
|
||
| $B(c,r)$ | 中心为 $c$、半径为 $r$ 的闭圆盘 |
|
||
| $\rho(P)$ | 覆盖 $P$ 的最小圆盘半径 |
|
||
|
||
假设各次有效示向度对应同一频道的同一个静止源。仅把 `direction` 观测代入角域模型，不能给 `near` 或 `no_signal` 人为赋予角度。理论推导允许 $0\le\delta_i<90^\circ$，用于讨论退化情况，题目主模型始终采用 $\delta_i=1^\circ$。
|
||
|
||
程序可额外计入两位小数舍入对应的 $0.005^\circ$ 裕量，但必须显式声明。题设的 $1^\circ$ 误差界与实现中的浮点容差是两个概念，均不能在结果解释时省略。
|
||
|
||
## 3. 由角域推导半平面约束
|
||
|
||
定义方向向量 $u(\alpha)=(\cos\alpha,\sin\alpha)$，二维叉积为 $[a,b]=a_xb_y-a_yb_x$。三角函数计算前将角度换成弧度。
|
||
|
||
令 $u_i^-=u(\theta_i-\delta_i)$、$u_i^+=u(\theta_i+\delta_i)$。当 $0<\delta_i<90^\circ$ 时，真实位置位于两条边界射线之间，等价于 $[u_i^-,g-s_i]\ge0$ 和 $[u_i^+,g-s_i]\le0$。第一条要求 $g-s_i$ 在下边界的左侧，第二条要求其在上边界的右侧。
|
||
|
||
将第一条展开，得到 $\sin(\theta_i-\delta_i)x-\cos(\theta_i-\delta_i)y\le\sin(\theta_i-\delta_i)s_{ix}-\cos(\theta_i-\delta_i)s_{iy}$。
|
||
|
||
将第二条展开，得到 $-\sin(\theta_i+\delta_i)x+\cos(\theta_i+\delta_i)y\le-\sin(\theta_i+\delta_i)s_{ix}+\cos(\theta_i+\delta_i)s_{iy}$。
|
||
|
||
同时保留前向约束 $u(\theta_i)\cdot(g-s_i)\ge0$。该约束在正半角情形下冗余，但当 $\delta_i=0$ 时，前两条只限定一条直线，加入它才得到正确的射线。角域顶点本身也包含在闭集合内，这是保守几何处理，并不表示该点仍能获得示向度。
|
||
|
||
因此，$P=\bigcap_{i=1}^{n}W_i=\{g:Ag\le b\}$。采用向量不等式后，$359^\circ$ 与 $0^\circ$ 跨界无需分段比较角度。每个 $W_i$ 是闭凸集，故 $P$ 也是闭凸集；它可能为空、为单点、为线段、为有界凸多边形，也可能无界。
|
||
|
||
## 4. 定位区域的构造与分类
|
||
|
||
### 4.1 边界交点与可行性
|
||
|
||
把约束统一写成 $a_jx+b_jy\le c_j$。两条边界的行列式为 $\Delta_{jk}=a_jb_k-a_kb_j$。当 $\Delta_{jk}\ne0$ 时，交点坐标为 $x=(c_jb_k-c_kb_j)/\Delta_{jk}$、$y=(a_jc_k-a_kc_j)/\Delta_{jk}$。保留满足全部约束的交点，再去重并构造凸包。
|
||
|
||
**命题1：** 至少有一次观测时，非空的角域交集一定存在极点，因此可通过可行边界交点枚举判空。
|
||
|
||
**证明：** 取第一个角域的轴向量 $u_1$，其中任意 $g$ 满足 $u_1\cdot(g-s_1)\ge\cos\delta_1\,\lVert g-s_1\rVert$，且 $\cos\delta_1>0$。在非空 $P$ 上最小化线性函数 $u_1\cdot(g-s_1)$；以任一可行点的函数值截取下水平集，得到非空紧集，故最小值能够取得。最小化点集位于一条支撑直线上，且有界，所以为点或线段。取该点或线段端点即得到 $P$ 的极点。二维线性约束的极点至少有两条法向量线性无关的有效边界，否则沿所有有效边界的公共切向可作双向小扰动，与极点定义矛盾。因此极点包含在上述交点枚举中。证毕。
|
||
|
||
无观测时，$P=\mathbb R^2$，应直接判为无界，不能用“没有交点”判断为空集。
|
||
|
||
### 4.2 无界性判定
|
||
|
||
对非空 $P$ 定义衰退锥 $\mathcal R=\{d:Ad\le0\}$。若存在 $d\ne0$，则任意 $g_0\in P$ 与 $t\ge0$ 都满足 $g_0+td\in P$，所以 $P$ 无界。
|
||
|
||
反之，若 $P$ 无界，可取 $g_k\in P$ 使 $\lVert g_k-g_0\rVert\to\infty$。单位向量 $(g_k-g_0)/\lVert g_k-g_0\rVert$ 存在收敛子列，极限 $d$ 满足 $\lVert d\rVert=1$。将 $Ag_k\le b$ 减去 $Ag_0$，再除以距离并取极限，得到 $Ad\le0$。因此 $P$ 有界当且仅当 $\mathcal R=\{0\}$。
|
||
|
||
本模型的衰退锥被一个小于 $180^\circ$ 的闭角域约束，若包含非零向量，必含一条极射线，该射线平行于某条有效约束边界。故只需检查每个法向量 $(a_j,b_j)$ 的两个切向方向 $(b_j,-a_j)$、$(-b_j,a_j)$ 是否满足所有齐次不等式。
|
||
|
||
### 4.3 分类约定
|
||
|
||
可行交点为空时返回空集；存在非零衰退方向时返回无界。否则求可行交点的凸包，按顶点数和仿射维数区分单点、线段和二维多边形。空集的直径在本文约定为未定义；无界集合的直径为 $+\infty$。程序使用空值及单独的无穷标志表示二者，避免写入非标准 JSON 数值。
|
||
|
||
显示窗口只用于绘图裁剪。任意大矩形都不能取代衰退锥判定，更不能把截断图形的直径称为原无界区域的直径。
|
||
|
||
## 5. 直径的顶点定理
|
||
|
||
**定理1：** 若 $P=\operatorname{conv}(V)$ 非空且有界，则 $D(P)=\max_{i,j}\lVert v_i-v_j\rVert$。
|
||
|
||
**证明：** 任取 $x,y\in P$，可写成 $x=\sum_i\lambda_i v_i$、$y=\sum_j\mu_jv_j$，其中权重非负且分别求和为1。于是 $x-y=\sum_{i,j}\lambda_i\mu_j(v_i-v_j)$。由三角不等式，$\lVert x-y\rVert\le\sum_{i,j}\lambda_i\mu_j\lVert v_i-v_j\rVert\le\max_{i,j}\lVert v_i-v_j\rVert$。最远顶点对又属于 $P$，上界可以达到，结论成立。证毕。
|
||
|
||
因此，小规模问题中直接枚举所有顶点对即可，计算复杂度为 $O(m^2)$。单点的直径为0，线段的直径为端点距离。这里的直接枚举不是近似算法；其缺点仅在于大规模时计算量较高。
|
||
|
||
## 6. 直径圆覆盖的充要条件
|
||
|
||
**定理2：** 取任意一组最远顶点 $a,b$，令 $D=\lVert a-b\rVert$、$o=(a+b)/2$。存在直径为 $D$ 的覆盖圆，当且仅当所有顶点均满足 $\lVert v_i-o\rVert\le D/2$。
|
||
|
||
**证明：** 若半径为 $D/2$、中心为 $z$ 的圆同时包含 $a,b$，则 $D\le\lVert a-z\rVert+\lVert z-b\rVert\le D$。两个不等式必须同时取等号，所以 $z$ 在两点连线上，且到两点距离相等，只能是中点 $o$。当 $D=0$ 时结论直接成立。另一方面，圆盘是凸集，包含全部顶点等价于包含它们的凸包。因此只需在这个唯一可能的圆心处检查全部顶点。证毕。
|
||
|
||
该定理不仅回答“以某条直径线段为直径的圆是否覆盖”，也回答“能否移动一个同样大小的圆使其覆盖”。若检查失败，移动圆心或更换最远顶点对均不能解决。
|
||
|
||
定义最大超出量 $E=\max_i\lVert v_i-o\rVert-D/2$。在精确算术下，$E=0$ 表示覆盖成立，$E>0$ 表示失败；不会出现严格负值，因为最远点对就在圆周上。取达到最大值的顶点，即得到一份可以独立复核的覆盖失败证据。
|
||
|
||
## 7. 符合测向条件的反例
|
||
|
||
取误差半角均为 $1^\circ$，三个检测点及读数如下。
|
||
|
||
| 检测点 | 坐标（米） | 示向度 |
|
||
| --- | --- | --- |
|
||
| $s_1$ | $(-1000,0)$ | $1^\circ$ |
|
||
| $s_2$ | $(540,-500\sqrt3)$ | $121^\circ$ |
|
||
| $s_3$ | $(520,520\sqrt3)$ | $241^\circ$ |
|
||
|
||
每个角域的下边界方向分别为 $0^\circ,120^\circ,240^\circ$。对应的三个左半平面是 $y\ge0$、$\sqrt3x+y\le40\sqrt3$、$y\le\sqrt3x$，交集为顶点 $A=(0,0)$、$B=(40,0)$、$C=(20,20\sqrt3)$ 的等边三角形。
|
||
|
||
还需验证每个角域的另一条边不会切去这个三角形。以 $s_1$ 为例，到三个顶点的方向分别为 $0^\circ,0^\circ,\arctan(20\sqrt3/1020)$，最后一项约为 $1.945^\circ<2^\circ$，均在 $[0^\circ,2^\circ]$ 内。其余两站由绕三角形中心旋转 $120^\circ$ 的对称性成立。因此三个完整前向角域之交恰为上述三角形。
|
||
|
||
将真实源取为三角形中心 $g_*=(20,20\sqrt3/3)$。以第一站为例，真实方向约为 $0.649^\circ$，与 $1^\circ$ 的读数偏差小于 $1^\circ$；检测距离约为1020米，小于1500米。另两站同理。该反例符合题设方位误差和可能的有效接收半径。
|
||
|
||
此时 $D=40$ 米，而以 $AB$ 为直径的圆中心为 $(20,0)$，到 $C$ 的距离为 $20\sqrt3>20$ 米，不能覆盖。三角形外接圆即最小包围圆，其中心为 $(20,20\sqrt3/3)$，半径为 $40/\sqrt3\approx23.094011$ 米。这也证明了“直径不超过40米”不足以保证一次清除。
|
||
|
||
## 8. 最小包围圆及其清除含义
|
||
|
||
### 8.1 存在性、唯一性与支撑点
|
||
|
||
定义 $f(z)=\max_{v\in V}\lVert v-z\rVert$，则 $\rho(P)=\min_z f(z)$。由于 $V$ 有限，$f$ 连续且随 $\lVert z\rVert\to\infty$ 而趋于无穷，最小值存在。
|
||
|
||
若两个不同中心 $c_1,c_2$ 都以半径 $r$ 覆盖 $V$，中点 $c$ 对每个顶点满足 $\lVert v-c\rVert^2=(\lVert v-c_1\rVert^2+\lVert v-c_2\rVert^2)/2-\lVert c_1-c_2\rVert^2/4<r^2$，与最小性矛盾。因此最小包围圆唯一。
|
||
|
||
在最优中心 $c$ 处，令 $T$ 为圆周上的顶点集。若 $c$ 不在 $T$ 的凸包中，可沿严格分离方向小幅移动中心，使所有圆周点的距离同时减小；其余有限个点有严格余量，仍被稍小圆覆盖，产生矛盾。故 $c\in\operatorname{conv}(T)$。二维凸组合经仿射相关权重消元，最多保留3个点。因此最小包围圆由至多3个圆周顶点支撑。
|
||
|
||
更具体地，若支撑点 $p_j$ 的权重满足 $c=\sum_j\lambda_jp_j$，则对任意 $z$ 有 $\sum_j\lambda_j\lVert p_j-z\rVert^2=r^2+\lVert c-z\rVert^2\ge r^2$。这给出了任何覆盖圆半径不能小于 $r$ 的直接证据。
|
||
|
||
### 8.2 求解方法与来源
|
||
|
||
由支撑点性质，可以枚举单点零半径圆、两点直径圆和三点外接圆，再检查全体顶点。这是便于核查的基准方法，最坏复杂度为 $O(m^4)$。
|
||
|
||
当前实现采用 Welzl 的随机增量算法：打乱点序，若当前圆不包含新点，则在该点成为边界点的约束下递归求解较小问题；边界点至多3个。程序用显式栈避免递归深度限制，并固定随机种子以复现结果。理论期望线性依赖随机排列分析，不等于任意固定排列的最坏时间保证。3个强制边界点应使用外接圆，不能替换成其无约束最小圆。算法来源为 Welzl 的原论文，CGAL 文档提供了定义与实现背景。[文献3](https://people.inf.ethz.ch/emo/PublFiles/SmallEnclDisk_LNCS555_91.pdf)、[文献4](https://doc.cgal.org/latest/Bounding_volumes/classCGAL_1_1Min__circle__2.html)
|
||
|
||
### 8.3 与一次清除的关系
|
||
|
||
所有能够保证一次清除的位置构成 $C_{20}(P)=\bigcap_{g\in P}B(g,20)=\bigcap_{v\in V}B(v,20)$。第二个等号来自圆盘凸性。该集合非空当且仅当 $\rho(P)\le20$。
|
||
|
||
因此，最小包围圆中心是保证清除的充分选择，但不一定是移动距离最短的选择。若后续需要优化路径，可以在 $C_{20}(P)$ 内寻找距离机器狗最近的位置。相比之下，$D(P)\le40$ 只是必要条件。
|
||
|
||
## 9. 算法流程与计算量
|
||
|
||
**算法1：角域交、直径及覆盖证据。**
|
||
|
||
1. 校验观测并进行坐标平移、尺度归一化，保留原误差半角。
|
||
2. 生成每次观测的三条半平面约束。
|
||
3. 枚举非平行边界交点，保留满足全部约束的点；无观测和空集分别处理。
|
||
4. 检验非零衰退方向；存在时报告无界并停止有限圆计算。
|
||
5. 对可行点去重并求凸包，识别点、线段或多边形。
|
||
6. 枚举顶点对求直径及任意一组最远点。
|
||
7. 检查其中点到全部顶点的距离，输出最大超出量与失败顶点。
|
||
8. 求最小包围圆，换回原坐标，重新检查顶点包含性，输出清除半径余量。
|
||
|
||
令半平面数 $k=3n$，顶点数为 $m$。边界交点枚举及全约束检查为 $O(k^3)$，衰退方向检查为 $O(k^2)$，交点排序上界为 $O(k^2\log k)$，直径计算为 $O(m^2)$，覆盖证据检查为 $O(m)$。随机增量最小圆在随机排列下期望为 $O(m)$；整个算法仍由半平面交点枚举主导，不能因此称为总体线性算法。
|
||
|
||
## 10. 数值实现与已有观测复核
|
||
|
||
数学结论使用精确不等式。浮点实现先平移、归一化，再用位置容差、平行判定阈值和衰退方向容差分别处理不同问题。接近平行或退化输入应进行精度与容差敏感性检查；任意追加一个固定小数裕量都不能替代严格的误差传播上界。
|
||
|
||
当前程序输出 `diameter_circle` 中的圆心、半径、最大超出量和反例顶点，以及 `minimum_enclosing_circle`。清除判断采用 $\rho+\varepsilon_m\le20$，其中 $\varepsilon_m$ 是工程数值裕量。它是观测及几何计算可靠这一前提下的决策条件，不是一次真实清除成功记录。
|
||
|
||
既有官方演练案例 `U5ZW-P9KN-TCAG-R7ST` 的三次不同位置观测如下。
|
||
|
||
| 检测点 | $x$ / 米 | $y$ / 米 | 示向度 / 度 |
|
||
| --- | ---: | ---: | ---: |
|
||
| 1 | 0 | 0 | 131.52 |
|
||
| 2 | -613.7618853216 | 391.5307754525 | 34.92 |
|
||
| 3 | -314.2721344680 | 656.6833525352 | 227.19 |
|
||
|
||
| 误差半角 | 直径 / 米 | 最小包围半径 / 米 | 直径圆最大超出 / 米 |
|
||
| --- | ---: | ---: | ---: |
|
||
| $1^\circ$ | 23.996723 | 12.068583 | 0.604002 |
|
||
| $1.005^\circ$ | 24.119088 | 12.130377 | 0.608486 |
|
||
|
||
两种口径下直径圆均不覆盖区域，最小包围半径均小于20米。该演练未公开源坐标，且没有执行清除，故只用于观测交会和计算一致性复核，不能据此声称实测定位误差或全清成功率。数据见[原始三点观测](C:/Users/HelixCopex/code/MATH/output/q1/practice/U5ZW-P9KN-TCAG-R7ST_observations.json)，敏感性数值见[已有复算报告](C:/Users/HelixCopex/code/MATH/output/q1/optimization_report.json)。
|
||
|
||
## 11. 结论与实现对应
|
||
|
||
问题一的准确答案为：将测向角域表示为半平面交，先判断非空性及有界性，再由最远顶点对得到直径；以该直径为直径的圆一般不能覆盖定位区域，覆盖的充要条件是任意一组最远顶点的中点到全部顶点的距离均不超过半径。最小包围圆提供独立且适合后续清除的精度指标。
|
||
|
||
对应实现为 [localization.py](C:/Users/HelixCopex/code/MATH/geometry/localization.py)。在项目根目录可运行 `python -m geometry examples/q1/triangle.json`；追加 `--rounding-margin-deg 0.005` 可复算额外舍入裕量。本文整理理论与已有计算结果，不改变原始观测或既有程序。
|
||
|
||
## 参考文献
|
||
|
||
1. 全国大学生数学建模竞赛组委会. 2026年高教社杯全国大学生数学建模竞赛B题：无线电干扰源的快速自动定位与清除[Z]. 2026. [本地题面](C:/Users/HelixCopex/code/MATH/issue/B题.pdf)，第1页、附录2。
|
||
2. BOYD S, VANDENBERGHE L. Convex Optimization[M]. Cambridge: Cambridge University Press, 2004. [作者公开版本](https://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf)，第2章。用于凸几何背景，本文的题目化证明在正文给出。
|
||
3. WELZL E. Smallest enclosing disks (balls and ellipsoids)[C]//MAURER H. New Results and New Trends in Computer Science. Lecture Notes in Computer Science, vol. 555. Berlin: Springer, 1991: 359–370. [作者公开论文](https://people.inf.ethz.ch/emo/PublFiles/SmallEnclDisk_LNCS555_91.pdf)。用于随机增量最小包围圆算法来源。
|
||
4. CGAL Project. CGAL::Min_circle_2: Bounding Volumes[EB/OL]. [在线文档](https://doc.cgal.org/latest/Bounding_volumes/classCGAL_1_1Min__circle__2.html)，访问日期：2026-09-10。用于最小圆及支撑点定义的交叉核对。
|