7.9 凸多边形的极值点
(Extreme Point of Convex Polygon)

我们经常需要找到凸多边形在某个方向上的极值点。例如，寻找一个包围多边形的最小矩形框，其边与坐标轴平行，可以由四个方向(上下左右)的极值点来构建。通常这种计算都是通过对所有顶点进行简单的 $O(n)$ 扫描来完成的，尽管如此，我们还是可以稍微修改一下通过二分查找在 $O(\log n)$ 的时间内完成同样的目标。在本节中，我们将概述一种查找最高点的搜索算法，然后将其推广到查找特定任意方向上的极值点。

设 $n$ 个多边形顶点为 $P[0], \ldots, P[n-1]$，并按逆时针方向标记。假设在搜索过程中，我们已知最高顶点位于索引 $a$ 和 $b$ 之间的逆时针路径上。我们将这些索引的集合表示为 $[a, b]$，即我们的搜索区间。因此，如果 $a < b$，那么 $P[a], P[a+1], \ldots, P[b-1], P[b]$ 中有一个是最高顶点。刚开始考虑这个问题，我们暂不考虑索引 0 的回绕，也不考虑两个顶点可能同为最高点的情况，这两个问题都会使实现变得复杂。

主要思想是利用多边形的有向边来确定如何二分搜索区间。设 $c$ 为严格介于 $a$ 和 $b$ 之间的一个索引。如果 $P[a]$ 之后的边 $A$ 向上，那么 $a$ 位于 $P$ 的右链上。如果 $P[c]$ 之后的边 $C$ 向下，那么 $c$ 位于左链上，如图 7.19(a) 所示，最高点位于两者之间。在这种情况下，我们可以将原始搜索区间 $[a, b]$ 缩短为 $[a, c]$。如图(b)所示，$A$ 向下 $C$ 向上，或者 $A$ 和 $C$ 都向上，如图(c)(d)所示，或者 $A$ 和 $C$ 都向下(未显示)，也会发生类似的缩短。不断重复此二分过程，直到 $c$ 之后的边向下且其之前边向上，表明 $c$ 是最高点。算法 7.3 中的伪代码展示了这些决策的细节。

有三点需要进一步澄清一下：

中间索引 $c$ 该如何计算?
循环的终止条件应该是啥?
若两个顶点都是最高点，对算法有何影响?

让我们来解决第一个问题: 如何找到 $a, b$ 之间的中间索引。如果 $a < b$，那么 $(a + b)/2$ 就是中间位置。注意，如果 $b = a + 1$，那么 $(a + b)/2 = a$，这是由于截断造成的。如果 $a \ge b$，区间 $[a, b]$ 包含 0，公式 $(a + b)/2$ 就不再生效了。例如，$n = 10, a = 7, b = 3$。这里 $[7, 3] = (7, 8, 9, 0, 1, 2, 3)$，中点是 0。这可以通过将 $b$ 平移 $n$ 使其再次大于 $a$，然后对结果模 $n$ 来计算 $((a + b + n)/2) \bmod n$。刚才的例子中，$((7 + 3 + 10)/2) \bmod 10 = 0$。注意，如果 $a \ge b$ 且 $b = (a + 1) \bmod n$，那么计算结果再次为 $a$，这与 $a < b$ 时的行为相同。当 $a, b$ 相邻时，中点是 $a$。

这为我们提供了一个中点函数，可以按照 Code7.23 所示的方式实现。注意对于代表 $P$ 的整个边界的 $[a, a]$ 的中点，该函数输出 $(a + n/2) \bmod n$，即从 $a$ 出发绕半圈的位置，完全符合预期。

展开 Code 7.23. Midway.>>>

        int Midway( int a, int b, int n )
        {
            if ( a < b ) return ( a + b ) / 2;
            else         return ( ( a + b + n ) / 2 ) % n;
        }

如果最高顶点唯一，那么循环终止条件很简单。此时与 $c$ 相邻的顶点都严格低于 $c$。如果一条水平边是最高的(若输入允许，或许有多条共线的水平边)，要捕获的情况也并不那么困难，因为与 $c$ 相邻的顶点都不是更高的点。

遗憾的是，由于 Midway 在 $b = a + 1$ 时截断，我们无法保证 $c$ 最终会命中极值点。这总截断总是顺时针方向的，可能会阻碍最后一步所需的逆时针移动。可以通过专门处理 $c = a$ 的情况来确保终止。完整的实现留给练习 7.9.2[2]，现在我们转向推广和应用。

简单修改算法，就可以找到任意方向 $u$ 上的极值。将测试向量 $V$ 是否向下的测试替换为，测试 $u \cdot V < 0$，将测试 $P[a]$ 是否在 $P[c]$ 上方的测试替换为，测试 $u \cdot (P[a] - P[c]) > 0$，依此类推。这使得极值查找算法不仅可以用于包围盒子计算，还可以有很多其它用途。

7.9.1. 穿刺凸多边形 (Stabbing a Convex Polygon)

寻找几何对象与一条直线的交集的问题通常被称为"穿刺(stabbing)"问题。这里，我们将展示如何利用极值查找算法在 $O(\log n)$ 的时间内刺穿一个凸多边形。

给定多边形 $P$ 和直线 $L$，设 $u$ 为垂直于 $L$ 的向量。找到 $P$ 在 $+u$ 和 $-u$ 方向上的两个极值顶点，分别记为 $a, b$。参见图 7.20。如果 $a$ 和 $b$ 都在 $L$ 的同一侧，则 $L \cap P = \emptyset$。否则，$a,b$ 将边界 $\partial P$ 分割成两条链，它们与 $L$ 的交点可以通过简单的二分查找找到。链 $P[a, b]$ 将产生图中的交点 $x$，而 $P[b, a]$ 将产生 $y$。

7.9.2. 练习

共线点 Collinear points。假设输入多边形包含三个或更多连续的共线顶点，对算法 7.3 来说是否有问题?
[Programming] 实现极值算法 Implement extremes algorithm。实现算法 7.3，并将其推广到任意方向 $u$。在包含极值边的示例上进行测试。
直线与多边形的距离 Line-polygon distance。设计一个算法来确定 $n$ 个顶点的任意多边形 $P$ 和一条直线 $L$ 之间的距离。距离的定义为 $$ \min_{x, y} \{ |x - y| : x \in P, y \in L \} $$ 其中 $x$ 和 $y$ 是点。尝试预处理之后，实现每次查询的时间复杂度为 $O(\log n)$。

7.9 凸多边形的极值点(Extreme Point of Convex Polygon)

7.9.1. 穿刺凸多边形 (Stabbing a Convex Polygon)

7.9.2. 练习

7.9 凸多边形的极值点
(Extreme Point of Convex Polygon)