在计算几何中，我们经常需要寻找一个2D多边形（Polygon）的极值点。例如通过x\y的极值点，我们可以定义一个多边形的包围盒。更一般的情况下，我们可能会需要寻找一个多边形在任意方向上的极值点。对于n个点的点集，很容易找到一个O(n)的算法，只需要依次测试每个点即可。然而对于凸多边形，可以利用二分搜索的思想在时间内找到极值点。首先，定义一个任意的方向向量u，接下来我们详细讲解该算法的思路。

平面点集和简单多边形的凸包在这两篇博文中已经介绍过了：、。因此，对于平面点集和任意简单多边形只需要先计算凸包，然后再计算凸包极值点即可。其算法复杂度由凸包算法决定。

首先，定义2D凸多边形S由n个点构成V0,V1,...,Vn-1,Vn=V0，并且沿着逆时针方向给定。

定义为第i条边（从Vi到Vi+1），为边向量。

目标：找到S中的所有点在u方向上的极值点。也就是将点投影在u说定义的直线上，极值点就是投影点的极值点，如下图所示：

可以看到，相对于u，Vi在Vj之上。也就是（Vi-Vj）与u之间形成一个锐角，相当于下面的几何条件：

这个条件可以帮助我们判断，一条边相对于u的投影是在增加还是减少。

最直接的办法就是暴力搜索每个点，每一步与当前保存的极值点比较。该算法的伪代码如下：

尽管算法是线性的，但还可以通过二分搜索加快。

对于一个凸多边形的点集，我们可以通过二分搜索，在时间内找到极值点。

首先，假设极大值点在顶点Va和Vb之间，Vc为Va和Vb的中间点，为了实现二分搜索，我们需要将下一步的搜索范围缩小到[a, c]或者[c, b]。由于多边形是凸的，我们可以通过比较A、C处的边向量、来做到这一点。下面详细说明：

如上图所示。假定u向上，A、B、C的相对位置可能有6种情况。对于每种情况，要么[a, c]，要么[c, b]包含最大值点。这是因为，多边形S在u方向上是单调的，它由两个单调链组成，从最小值点开始，到最大值点单调递增，然后再单调递减回到最小值点。而且无论u的方向如何，这个结论都是成立的。

接下来，我们就能构造二分搜索了。从开始，,在每一步，我们需要确定是将a增加到c,还是b减小到c，将包含最大值的区间缩小一半。当然，我们需要检查，是否已经找到了一个局部极大值点Vc，这只需要检查和的符号是否一致即可。如果两者的符号不一致，说明Vc是局部极大值点，同时也是多边形的全局最大值点。

于是，我们得到，寻找相对于u的最大值点的伪代码如下：

下面是二分搜索算法的一个C++实现：

下载百度知道APP，抢鲜体验

使用百度知道APP，立即抢鲜体验。你的手机镜头里或许有别人想知道的答案。