198 lines
9.5 KiB
TeX
198 lines
9.5 KiB
TeX
\section{问题一：有界误差交会定位与覆盖圆}\aigcA
|
||
\subsection{从示向度到前向角域的半平面模型}
|
||
交会定位的第一个困难在于，带误差的示向度只限制方向而不唯一确定位置。
|
||
由题设可知，示向度误差不超过 $\pm1^\circ$，故给定检测点 $s_i=(s_{ix},s_{iy})$ 与读数 $\theta_i$ 后，
|
||
真实方位必然落在 $[\theta_i-\delta,\theta_i+\delta]$ 内。据此，
|
||
真实位置属于以前向方向 $u(\theta_i)$ 为中轴的角域
|
||
\begin{equation}
|
||
W_i=\left\{g:
|
||
\begin{aligned}\relax
|
||
[u(\theta_i-\delta),g-s_i]&\ge0,\\
|
||
[u(\theta_i+\delta),g-s_i]&\le0,\\
|
||
u(\theta_i)\cdot(g-s_i)&\ge0
|
||
\end{aligned}\right\}.
|
||
\label{eq:wedge}
|
||
\end{equation}
|
||
三条不等式的意义并不相同。前两条把位置限制在左右边界之间，
|
||
第三条显式保留"只在前方"这一方向性，
|
||
从而使零误差的退化情形对应一条射线而不是整条直线。
|
||
为便于统一求解，将其改写为 $a x+b y\le c$ 的形式，法向依次为
|
||
\begin{equation}
|
||
\begin{aligned}
|
||
&(\sin(\theta_i-\delta),-\cos(\theta_i-\delta)),\\
|
||
&(-\sin(\theta_i+\delta),\cos(\theta_i+\delta)),\\
|
||
&(-\cos\theta_i,-\sin\theta_i),
|
||
\end{aligned}
|
||
\end{equation}
|
||
右端为相应法向与 $s_i$ 的内积。采用正弦、余弦表示还有一个工程上的好处：
|
||
$0^\circ$ 与 $360^\circ$ 的跨界无需特判即可自动处理。
|
||
|
||
由于所有角域都是凸的半平面交，多个测点的信息可以直接合并。
|
||
问题一的多边形定位区域因此定义为
|
||
\begin{equation}
|
||
P=\bigcap_{i=1}^{n}W_i=\{g:Ag\le b\}.
|
||
\label{eq:q1set}
|
||
\end{equation}
|
||
式~\eqref{eq:q1set} 根据各次测向角域确定问题一的定位区域；
|
||
后续问题将在此基础上加入圆域 $\Omega$ 与接收距离约束。
|
||
值得先说明的是，半平面交是闭凸集，可能为空集、单点、线段、有界多边形或无界集，
|
||
这些情形必须分别处理，否则"直径"与"覆盖圆"都没有定义。
|
||
|
||
\subsection{区域构造、空集及无界情形}
|
||
要求解式~\eqref{eq:q1set}，只需枚举约束边界之间的交点再筛除不可行者。
|
||
令约束数 $k=3n$，对任意两条不平行边界
|
||
$a x+b y=c$、$d x+e y=f$，候选交点为
|
||
\begin{equation}
|
||
x=\frac{ce-bf}{ae-bd},\qquad y=\frac{af-cd}{ae-bd}.
|
||
\end{equation}
|
||
仅保留满足全部不等式的交点，再经去重和单调链凸包构造即得顶点集合。
|
||
数值上，实现先平移与缩放坐标，以降低千米尺度坐标带来的误差；
|
||
同时保留近平行边界的求交，因为其远端交点可能决定细长区域的直径。
|
||
|
||
顶点集确定之后，还需判断区域是否无界。为此对非空集合定义衰退锥
|
||
\begin{equation}
|
||
\mathcal R=\{d:Ad\le0\}.
|
||
\end{equation}
|
||
若 $\mathcal R$ 含非零向量，则 $g+td\in P$ 对所有 $t\ge0$ 成立，
|
||
区域无界、直径为 $+\infty$。二维多面锥只需检查约束边界的两个切向
|
||
$(b,-a)$ 与 $(-b,a)$ 是否满足全部齐次不等式。
|
||
由于本题至少一个前向窄角域会排除直线性，非空交集必存在极点，
|
||
故在该输入族中不存在可行边界交点却判为空集的情况；无观测输入单独返回整个平面，
|
||
不按空集处理。
|
||
|
||
有界非空区域中，一个顶点对应单点，两个顶点对应线段，其余为凸多边形。
|
||
空集没有本文定义的有效直径与覆盖圆，程序以显式状态报告观测不相容，
|
||
便于检查频道、误差界或输入数据。
|
||
|
||
\subsection{直径与直径圆的判定}
|
||
题目要求计算定位区域直径，并判断以该直径为直径的圆能否覆盖整个区域。
|
||
对前者，可以证明无需在区域内部搜索。
|
||
|
||
\begin{proposition}[顶点直径]
|
||
设 $P=\operatorname{conv}\{v_1,\ldots,v_m\}$ 非空有界，则
|
||
\begin{equation}
|
||
D(P)=\max_{i,j}\norm{v_i-v_j}.
|
||
\label{eq:diameter}
|
||
\end{equation}
|
||
\end{proposition}
|
||
\begin{proof}
|
||
任意 $x,y\in P$ 可表示为凸组合
|
||
$x=\sum_i\lambda_i v_i$、$y=\sum_j\mu_jv_j$。
|
||
由于系数非负且各自和为 $1$，
|
||
\[
|
||
\norm{x-y}
|
||
=\left\|\sum_{i,j}\lambda_i\mu_j(v_i-v_j)\right\|
|
||
\le\sum_{i,j}\lambda_i\mu_j\norm{v_i-v_j}
|
||
\le\max_{i,j}\norm{v_i-v_j}.
|
||
\]
|
||
最远顶点对本身属于 $P$，故上界可达。
|
||
\end{proof}
|
||
|
||
由命题可知，只需枚举顶点对即可，计算量为 $O(m^2)$。
|
||
至于第二个问题，结论比直觉更严格：最远顶点对的中点未必能覆盖整个区域。
|
||
|
||
\begin{proposition}[直径圆覆盖的充要条件]
|
||
取最远顶点对 $a,b$，令 $D=\norm{a-b}$、$o=(a+b)/2$。
|
||
存在直径等于 $D$ 的圆盘覆盖 $P$，当且仅当
|
||
\begin{equation}
|
||
\max_{v\in V(P)}\norm{v-o}\le D/2.
|
||
\label{eq:diametercircle}
|
||
\end{equation}
|
||
\end{proposition}
|
||
\begin{proof}
|
||
若半径 $D/2$ 的圆盘中心为 $z$ 且包含 $a,b$，则
|
||
$D\le\norm{a-z}+\norm{z-b}\le D$。
|
||
等号迫使 $z=o$。反之，圆盘为凸集，包含全部顶点即包含它们的凸包。
|
||
\end{proof}
|
||
|
||
证明过程同时说明：圆心被 $a,b$ 唯一确定，因此只需逐一检查其余顶点到该中点的距离。
|
||
若条件不成立，输出圆外顶点及超出量 $e=\max_v\norm{v-o}-D/2$，
|
||
即得到可独立检查的否定证据。换言之，不能仅以直径端点在圆周上判断整个区域被覆盖。
|
||
|
||
图~\ref{fig:q1geometry}(a)(b) 给出一组三点交会算例及其实例区域的放大，
|
||
(b) 中虚线为直径圆、实线为最小包围圆。
|
||
该算例的定位区域由 $\ExOneVertices$ 个顶点确定，直径为 $\ExOneDiameter$ m，
|
||
以该直径为直径的圆半径为 $\ExOneRadius$ m，
|
||
而最远顶点到圆心的距离超出该圆 $\ExOneExceed$ m，故直径圆并不覆盖定位区域；
|
||
其最小包围圆半径为 $\ExOneMec$ m，满足 $20$ m 的清除判据。
|
||
这说明直径不超过 $40$ m 与能否清除是两个不同的判据，覆盖判定必须逐顶点检查。
|
||
|
||
\subsection{反例与可清除半径}
|
||
上述差别并非数值巧合，而是几何上的必然。为说明这一点，
|
||
构造等边三角形
|
||
\begin{equation}
|
||
A=(0,0),\qquad B=(40,0),\qquad C=(20,20\sqrt3).
|
||
\end{equation}
|
||
其直径为 $40$ m。以 $AB$ 为直径的圆心为 $(20,0)$，半径为 $20$ m，
|
||
但 $C$ 到圆心的距离为 $20\sqrt3$ m，位于圆外。
|
||
其最小包围圆圆心为 $(20,20/\sqrt3)$，半径
|
||
$40/\sqrt3\approx23.094$ m，同样大于清除半径。
|
||
图~\ref{fig:q1geometry}(c) 展示两类圆的差别。
|
||
|
||
\begin{figure}[htbp]
|
||
\centering
|
||
\includegraphics[width=\linewidth]{geo-q1-geometry.png}
|
||
\caption{问题一的几何算例。(a) 三点交会：三条浅色示向度的角域边界与它们的交集（定位区域），
|
||
观测取自自建模拟器演练局 \texttt{8VRC-ADW4-XDXM-F62L} 的频道 $\ExOneChannel$；
|
||
(b) 该定位区域的放大：虚线为直径圆、实线为最小包围圆，
|
||
几何量由生产求解器 \texttt{mcm26b.geometry.solve} 现算；
|
||
(c) 等边三角形解析反例：虚线直径圆 $r=20$ m 不覆盖顶点 $C$，
|
||
实线最小包围圆 $\rho=40/\sqrt3\approx23.094$ m 覆盖全部顶点，该图不是模拟器观测。}
|
||
\label{fig:q1geometry}
|
||
\end{figure}
|
||
|
||
该三角形并非人为设定的特例，它可以由题设的 $\pm1^\circ$ 角域构造出来。例如检测点
|
||
$(-1000,0)$、$(540,-500\sqrt3)$、$(520,520\sqrt3)$，
|
||
对应示向度为 $1^\circ$、$121^\circ$、$241^\circ$。
|
||
各角域的一侧边界给出三角形的三条支撑线，另一侧边界包含整个三角形，
|
||
故交集恰为上述三角形。
|
||
|
||
既然覆盖判据不足以保证清除，就需要一个与清除动作直接对应的指标。
|
||
为此对一般候选区域定义最小包围圆
|
||
\begin{equation}
|
||
\rho(P)=\min_{z\in\mathbb R^2}\max_{g\in P}\norm{g-z},\qquad
|
||
m\in\arg\min_z\max_{g\in P}\norm{g-z}.
|
||
\label{eq:mec}
|
||
\end{equation}
|
||
其边界由至多三个支撑点确定，可用 Welzl 随机增量算法计算\cite{welzl}。
|
||
实现采用固定随机种子及显式栈，并在输出前检查全部顶点的包含关系。
|
||
在精确模型中，若 $\rho(P)\le20$，于 $m$ 清除即可覆盖所有可能真源；
|
||
考虑浮点计算后采用 $\rho(P)+\eta_{\mathrm{num}}\le20$ 的充分判据。
|
||
由此可见，$D(P)\le40$ 只是必要条件，并非充分条件。
|
||
|
||
\subsection{算法一与复杂度}
|
||
将上述判定串成流程，即得问题一的求解算法。
|
||
|
||
\begin{algorithm}[htbp]
|
||
\caption{有界测向角域交会与覆盖圆判定}
|
||
\label{alg:q1}
|
||
\begin{algorithmic}[1]
|
||
\Require 同一频道的检测点、示向度和误差半角
|
||
\Ensure 区域状态、顶点、直径、直径圆判定与最小包围圆
|
||
\If{观测为空}
|
||
\State \Return 无界
|
||
\EndIf
|
||
\State 归一化坐标，生成 $3n$ 条半平面约束
|
||
\State 枚举非平行边界交点，仅保留满足全部约束的点
|
||
\If{无可行点}
|
||
\State \Return 空集
|
||
\EndIf
|
||
\State 检查衰退锥；若存在非零方向，\Return 无界及无穷直径
|
||
\State 对可行交点去重并求凸包，区分单点、线段和二维多边形
|
||
\State 枚举最远顶点对，计算 $D$ 与中点 $o$，检查全部顶点是否在 $\B(o,D/2)$ 内
|
||
\State 计算最小包围圆 $\B(m,\rho)$，复核包含关系与数值余量
|
||
\State \Return $\rho+\eta_{\mathrm{num}}\le20$ 是否成立
|
||
\end{algorithmic}
|
||
\end{algorithm}
|
||
|
||
边界交点枚举需 $O(k^2)$ 次，每点校验 $k$ 条约束，主计算量为 $O(k^3)$；
|
||
凸包最坏需 $O(k^2\log k)$，直径枚举需 $O(m^2)$。
|
||
Welzl 算法在随机排列下具有期望线性时间。该求解流程适合少量观测，
|
||
当前入口限制最多 $100$ 个检测点；更大规模可替换半平面交算法。
|
||
|
||
综上，问题一给出两点结论：1. 带误差交会定位的直径可由顶点对枚举精确得到，
|
||
覆盖判定则必须逐顶点检查；2. 与清除动作真正对应的判据是最小包围圆半径不超过 $20$ m，
|
||
直径约束只是它的必要条件。
|
||
|
||
|