线段的直角凸包计算解析

### 线段的直角凸包计算解析 #### 1. 直角凸包相关概念与已有研究 在计算几何领域，直角凸包的计算是一个重要问题。以往对于直角凸包的研究，多集中在坐标轴固定的情况。例如，Nicholl 等人研究了计算多边形直角凸包的问题，针对一组正交多边形，提出了一个时间复杂度为 $O(n \log n)$、空间复杂度为 $O(n)$ 的算法，这里的 $n$ 是所有多边形边的数量。而 Rawlins 则针对不一定正交的多边形，给出了一个在顶点数为 $n$ 时，时间和空间复杂度均为最优的 $\Theta(n)$ 的算法。 值得注意的是，即使引入坐标轴旋转，相关算法仍能达到上述提到的时间复杂度，并且与计算一组线段标准凸包的算法时间复杂度相匹配：若线段不一定不相交，时间复杂度为 $\Theta(n \log n)$；若线段构成简单多边形链，时间复杂度为 $\Theta(n)$。 #### 2. 直角凸包的定义与性质 - **基本定义** - **直线方向**：直线的方向是其与 $X+$ 正半轴所成两个可能角度中的较小者。一组方向是指通过某一固定点且方向不同的一组直线。本文考虑由两条正交直线组成的方向集，记为 $O$，为简便起见，假设这两条直线都过原点且平行于坐标轴。 - **$O$-凸区域**：若一个区域与平行于 $O$ 中某条直线的直线的交集为空集、一个点或一条线段，则称该区域为 $O$-凸区域。 - **楔形与象限**：设 $\rho_1$ 和 $\rho_2$ 是从点 $x \in R^2$ 出发的两条射线，将 $\rho_1$ 绕点 $x$ 旋转角度 $\theta \in [0, 2\pi)$ 得到 $\rho_2$，则 $R^2 \setminus (\rho_1 \cup \rho_2)$ 中的两个开放区域称为楔形，它们的顶点均为 $x$，大小分别为 $\theta$ 和 $2\pi - \theta$。对于角度 $\omega$，大小为 $\omega$ 的楔形称为 $\omega$-楔形。象限是指射线平行于 $O$ 中直线的 $\frac{\pi}{2}$-楔形。 - **$P$-自由区域**：若一个区域与集合 $P$ 的交集为空，则称该区域为 $P$-自由区域。集合 $P$ 的直角凸包 $RCH(P)$ 是一个封闭的 $O$-凸集，定义为 $RCH(P) = R^2 \setminus \bigcup_{q \in Q} q$，其中 $Q$ 表示平面上所有（开放的）$P$-自由象限的集合。 - **重要性质** - **与标准凸包的关系**：$RCH(P) \subseteq CH(P)$。特别地，若 $CH(P)$ 是一个边平行于 $O$ 中直线的矩形，则 $RCH(P) = CH(P)$；否则，$RCH(P)$ 不是凸集。 - **连通性**：若 $P$ 中的线段构成多边形链，则 $RCH(P)$ 是连通的；若 $RCH(P)$ 不连通，则其连通分量要么是 $P$ 中的线段，要么是 $O$-凸的封闭多边形，该多边形不一定正交，甚至可能不简单。 - **方向依赖性**：除了某些特殊情况（如将 $O$ 中的直线同时逆时针旋转 $\frac{\pi}{2}$），同一集合在 $O$ 中直线不同方向下的两个直角凸包彼此不全等。 我们用 $O_{\theta}$ 表示将 $O$ 中的直线同时逆时针旋转角度 $\theta$ 后得到的集合，用 $RCH_{\theta}(P)$ 表示相对于 $O_{\theta}$ 计算的 $P$ 的直角凸包。 #### 3. 线段直角凸包的计算 设 $P = \{s_1, s_2, \cdots, s_n\}$ 是平面上的一组 $n$ 条线段，这些线段不一定不相交。下面介绍一个在 $\theta$ 从 $0$ 增加到 $2\pi$ 时，计算并维护 $RCH_{\theta}(P)$ 的最优算法，其时间复杂度为 $\Theta(n \log n)$，空间复杂度为 $\Theta(n\alpha(n))$，其中 $\alpha(n)$ 是阿克曼函数的反函数。 - **四个方向与楔形定义** 我们将北、南、东、西四个方向分别记为 $N$-方向、$S$-方向、$E$-方向和 $W$-方向。对于 $N$-方向，若存在一个以点 $x \in R^2$ 为顶点的 $\omega$-楔形，满足（i）该楔形包含通过 $x$ 的 $N$-方向；（ii）其内部不包含 $P$ 中线段的任何点，则称点 $x$ 相对于 $N$-方向是 $\omega$-楔形 $P$-自由的。同理可定义其他三个方向的情况。为计算 $RCH_{\theta}(P)$，我们关注以 $R^2$ 中的点或 $P$ 中线段上的点为顶点的 $P$-自由 $\frac{\pi}{2}$-楔形，且这些楔形包含 $N$、$S$、$E$ 或 $W$ 方向之一。 - **四个包络的计算** 对于 $N$-方向，一个线段 $s$ 上的点 $x$ 要成为相对于 $N$-方向的 $P$-自由 $\omega$-楔形（$\omega > 0$），必要条件是 $x$ 从无穷远北方可见