计算机算法基础 第2版 课件 第12章 计算几何基础.pptx

1第12章计算几何基础计算几何简介 2平面线段及相互关系 3平扫线技术和线段相交的确定 17平面点集的凸包 27Graham扫描法 29Jarvis行进法 38最近点对问题 44

1.计算几何简介 2计算几何(ComputationalGeometry)是计算机算法的一个重要分支，它要解决的是如何有效地完成与几何问题有关的算法问题。例如，在X-Y平面中求两点间距离是个简单的几何问题，但是如何快速地在n个点中找出距离最近的两个点就是个算法问题。计算几何在许多领域有广泛的应用，例如计算机图形学、机器人、电子游戏、大规模积成电路设计，生物信息科学等。这一学科的研究需要一些几何知识，但大部分情况下，不需要高深的几何知识，这要视具体问题而定。

3?2.平面线段及其相互关系

4?

5?显然， p1?p2=p2?p1，但是p1?p2=-p2?p1。下图(图12-1)解释这两个乘积的几何意义。

6点积和叉积的几何含义?O=(0,0)p1p2???XY(x1,y1)(x2,y2)点积

7O=(0,0)p1p2???XY(x1,y1)(x2,y2)p1叉积?u

8平面线段的相互关系我们回答前面所提的三个问题(p4)。定理12.1给定X-Y平面上两个向量，p1和p2，如果p1?p20那么p1是在p2的顺时针方向上，否则是在其逆时针方向上。如果p1?p2=0，则表明两个向量共线。证明：由上面的分析可知，p1?p2=|Op1||Op2|sin?。如果p1?p20，那么就有sin?0。sin?0说明?=(?-?)0，即p1是在p2的顺时针方向上。否则，(?-?)0，即p1是在p2的逆时针方向上。如果p1?p2=0，sin?=0，必有?=0或?=180?，显然表明二个向量共线。?

9P1P2???OP1P2???O(a)p1?p20,在p1处向左拐(b)p1?p20,在p1处向右拐?

10注：推论12.2中，如果起点不是原点O，而是p0，那么我们在p1点应该向左拐呢，还是向右拐呢？我们可以先把原点O平移到p0再考虑这个问题。这等价于考虑向量(p1-p0)和(p2-p0)的叉乗。所以，如果(p1-p0)?(p2-p0)0，那么在p1点向左拐；如果(p1-p0)?(p2-p0)0，则是向右拐；如果(p1-p0)?(p2-p0)=0，那么在p1点要么不改变方向，要么转180?逆向行走。这就回答了第二个问题。?

11?

12?

13?p1p3p2p4p4p1p2p3??判断方法: d1=(p2–p1)?(p3–p1)， d2=(p2–p1)?(p4–p1) d3?(p4–p3)?(p1–p3)， d4?(p4–p3)?(p2–p3)。不共线，不相交的充要条件是d1d20或d3d40。两个线段不共线而且相交。充要条件是情形(1)(2)的条件不满足。(伪码见下页)

14?

15?

16OP1P2P3P4p1=(-3,4)，p2=(2,6)，p3=(-1,7)和p4=(4,-5)

173.平扫线技术和线段相交的确定 平扫线技术(Sweepingline)是解决许多应用问题的一个重要技巧。我们通过下面这一问题来解释这个技术： 问题：假设X-Y平面上有n个线段，如何设计一个快速有效算法来确定是否有两个线段相交？如果用程序Segment-Intersect为每一对线段作判断，复杂度是?(n2)。如果用平扫线技术，则只需O(nlgn)时间就可以判断。做法：用一根垂直于X轴的直线l，称为平扫线，从左向右扫描。我们只需检查2n个位置上l的状态即可给出答案，每次只需O(lgn)时间。为简单起见，假定没有垂直于X轴的线段，也没有三个线段交于一点。所以，每个线段的左、右端点有不同的X坐标。（下面会详细讨论）

18平扫线的状态定义12.4当平扫线l停留在横坐标为x的位置时，所有与l相交的线段按交点的纵坐标从大到小排序。这个序列称为l在点x时的状态，而点x称为平扫线l的一个状态点。序列中任两个线段，u和v，称为在点x可比较，并且，如果u在v之上，则记为uxv。例(图12-5)udcabtr(a)平扫线在3个点的状态: r点:a,ct点:a,b,cu点:b,ceifhgyxwz(b)平扫线