计算几何（五）

从今天开始主要说说平面上点集的凸包。

先用一个例子来说明怎么求凸包。如图3-1所示。假定我们能确定凸包内一点x，

把点集中的n个点，按照其对x的角度，反时针从小到大排序。

如图中排序后的点按顺序记为a, b, c, ..., j，按排序后的顺序处理这n个点。

当前已处理过的点记在堆栈S中。算法开始时S中只有排在最前的两个点，S=(b, a)。

这里规定列出堆栈元素的时候，栈顶在前，栈底在后。

按顺序检查下一个点c。角abc在b点左转，因此c入栈，得到S=(c, b, a)。

注意此时abc是一个凸链。“栈中所有元素构成一个凸链”是算法要维护的一个不变式。

接下来处理d。bcd在c点右转，因此栈顶元素c出栈。

现在再检查abd。abd在b点左转，因此d入栈。此时的堆栈S=(d, b, a)

继续这个过程，e、f入栈，堆栈为S=(f, e, d, b, a)

之后，因为角efg和deg都是右转的，所以点g导致f, e出栈，

然后g入栈，堆栈内容变为S=(g, d, b, a)，如此等等不细说。

最后S内的点形成一个闭合折线段S=(j, i, g, d, b, a)即凸包的所有顶点。

这个算法里有几点细节需要处理：

第一，如果起始点a不在凸包上，算法的结束条件就会出问题。

第二，如果算法开始时堆栈中的第二个点b不在凸包上，万一abc是右转的，

导致点b出栈，这时候栈的内容S=(a)。可是栈内至少要有两个点，

才能判断下一个点和栈内元素一起是否构成一个凸链。

第三，如何确定点x的位置，以最大地简化排序和避免浮点误差。

先看看问题（三）。我们选给定的点集中y坐标最小的一个点为x。

若这样的点有多个，选择其中x坐标最大的一个。

这个点明显是肯定在凸包上的。图3-1中的j就是这样的点。

如果以j为参考点（记为p0），假定排序用的坐标系原点在p0，x轴即

经过p0的水平直线，排序的结果就变成了图3-2所示：

在这种情形下，p1是肯定在凸包上的（但不一定是凸包的顶点，

而是可能位于凸包的边上）。那么如果p1不是凸包的顶点怎么办？

先看排序时如果出现共线的情况怎么办？

排序时两个点共线，也就是他们和p0点所成的直线角度相等。

这时候哪个点到参考点p0的距离小，哪个点就排在前面。

这样排序的一个例子参见图3-3。

注意图中的小圆圈。很容易看出来，这些点都不可能是凸包的顶点。

可以在算法开始前先把这些点删除，就不会出现上面说的p1不是凸包顶点的问题了。

到此为止问题（一）（二）也解决了。

再看看凸包边界上的的共线如何处理。

首先，我们期待的结果是，输出的仅是凸包的顶点，不包含那些在凸包边界上的点。

举例来说，如果给定的点集中的所有点，都分布在一个正方形的边界上，

且恰好正方形的四个顶点都在这个点集内。

那么我们希望的输出只包含这个正方形的四个顶点，此外的点都不要。

记栈顶元素为pt和p[t-1]，考虑下一个点pi是否为凸包顶点时，

只要要求(p[t-1], pt, pi)是严格左转的就可以，即此内角须严格小于180度。

这样，在凸包上而非凸包顶点的pt就会被删除，从而不出现在最后的结果里。