together: Find's Blog

标题的意思不是说计算几何是basic but most useful, 是说我学到的几个算法是这样的. 每一次这样的标题下MS都是对CLRS的一次复述. 说句良心话, CLRS实在是一本好书, 一本大好书. 切入正题.

先说凸组合, 设点 p1, p2, p3. 若 p3 = x * p1 + ( 1 – x ) * p2 ( x, y 坐标对就相乘, 0<= x <= 1 ), 则称p3是p1-p2的凸组合. p1-p2 ( 包括p1和p2 ) 是全体p3. 矢量就不说了, 我自己也没完全弄懂它呢. 暂且理解为有向线段, 即有长度限制的射线.

叉积, 我完全是用一次函数推出来的, 它所算的有向面积, 我不明白原理, 或者它只是一个很本质的东西? 就像矩形的面积是长乘高般原始? 不知道, 这些以后再扩充吧. 我的主要目的是弄懂凸包. 三维空间中的一个向量, 这就更不用说了, 不知道.

相对原点p0, p1 和 p2 的叉积公式: p1 * p2 = ( x1 * y2 ) – ( x2 * y1 ) . 当叉积大于零,p1 在 p2 的顺时针方向, 当叉积小于零, p1 在 p2 的逆时针方向. 当它等于零, p0, p1, p2共线. 共线时, 可以用判断p2是否在p0-p1为对角线的矩形中的方法, 判断点是否在一条线段上.

确定连续线段是向左转还是向右转, 即判断角p0p1p2的转向, 可以通过相对p0计算差积获得, 画个图就好明白了. 这个方法在求凸包时很关键.

判断两条线段是否相交是用一种跨立的方法, 即用叉积分别计算p1-p2是否”跨过”p3-p4, 再判断 p3-p4 是否”跨过”p1-p2, 若两次都成立, 则它们相交. 至于一条线段的端点在另一条线段的情况, 加点特判就可以了. CLRS p578 上的那张图把这些情况画得非常具体.

确定一组线段中是否有任意一对线段是否相交有一个 O( nlogn ) 的算法. 它先根据x轴将这些线段离散化, 然后再根据两条相交线段必定在某两个”扫除线”之间是相邻的这个显而易见的事实, 在每一个扫除线上做一次这些线段y 轴上的排序, 并对每一对新成为相邻线段的线段做一次是否相交的判断. 利用BST做优化, 就可以达到O( nlogn )的时间界. BST中的比较就是比较在此”扫除线”上, 两条线段的相对位置. 这可以分为两条线段相交和不相交两种情况讨论. 当然, 我们也可以在出现第一种情况时直接结束. 至于求出全部线段中所有相交的线段, 我也根据习题想了一个算法, 但太麻烦了, 用了两个BST, 所以就先不写了.

寻找凸包书上讲了两个方法. 一个是Graham扫描法. 另一个是 Jarvis 步进法.

Graham扫描法: 先找一个点p0, 它的y坐标最小, 在同样的点中, 它的x坐标又最小, 显然它是一定在凸包中的. 然后对其余点按其极角排序. 接着就是维护一个堆栈, 使得它是目前为止所迭代到的点的一个凸包. 对每一个点pi, 我们读出堆栈出最顶和次顶元素p1, p2. 再判断p2p1pi 是不是向左转的, 若不是, p1出栈, 若是, pi 进栈. 排序算法如果是快排堆排什么的, 复杂度就是 O ( nlogn ).

Jarvis步进法: 它就比较直接了, 它直接就每次找到一次凸包上的点. 因为对每一个在凸包中的点p 来说,下一个点q 必定是相对它极角最小的一个点. 这样它的复杂度显然就是 O( nh ), 其中h是凸包中点的数目. 我们可以用一个记录上一线段极角的方法去找凸包, 也可以先找右链, 再找左链的方法. 我感觉第一种方法在记录极角这个步骤上有点麻烦, 不如就用第二种方法.

找到凸包后可以找最远点对, 因为最远点对必定在凸包上. maigo对此的证明:

距离最远的两个点一定都在输入的点的凸包上。简证如下：设距离最远的两个点为A和B，旋转图形使B点位于A点正上方。如果还有比B点更高的点C，那么AC一定大于AB，这与AB距离最远矛盾。所以B点一定是最高点，也就一定在凸包上。同理可证A点也一定在凸包上。

最高的点一定在凸包上, 看来在这类问题上这个条件总是很有用的. maigo的TJU题解上这个题解. 一个细节我还没有完全清楚, 但有点晕了, 过几天再想这个问题. 我觉得maigo所说的指针都应指向线段. 有点乱反正.

寻找最近点对也有一个O ( nlogn )的算法, 这个就很容易理解了. 不停地在x轴上二分点集, 求出左右点集中最小距离m, 然后合并时对二分线左右各m个单位距离内的点做单独处理, 检查每个点其后y坐标值大于它的七个点即可. 七, 难道真是这么一个神秘的数字?　七的推出是根据一个极限情况,　在这个极限情况中,　在二分线四周m * 2m的范围内, 最多有八个点. 而最近点对若存在, 也必定在这八个点中选两个. 具体的证明比较长, 还有个图. 但真的很容易理解.

目前为止学到的就这么多. 现在比较关键的遗留问题就是寻找最远点对问题的具体实现. 这个我再看看资料吧.