2011算法第十六十七讲几何

ECNUYinpingLiu几何扫描柳银萍ECNUYinpingLiu几何算法中，考虑的主要对象通常是二维、三维和更高维空间中的点、线段、多边形和其他几何体。有时候一个问题的解法要求“扫描”给出的输入对象来收集信息以找到可行解。这种技术在二维平面称为平面扫描，在三维空间称为空间扫描。在它的简单形式中，一条垂直的直线在平面中从左到右扫描，在每个对象(比如说一点)处逗留，从最左的对象开始直到最右的对象。我们结合计算几何中的一个简单问题来阐明这种方法。ECNUYinpingLiu定义18-1设P1=(x1，y1，)和P2=(x2，y2)是平面中的两点，如果x1≤x2并且y1≤y2,，则称P2支配P1，记为PlP2。定义18-2设S是平面中的一个点集，点p∈S是极大点或最大点，如果不存在点q∈S，使得p≠q并且pq。求极大点的问题有一个简单的算法，它是几何扫描算法的一个很好的例子。MAXIMALPOINTS：在平面上给定一个n个点的集合S，确定S中的极大点。ECNUYinpingLiu求解这个问题很容易，方法如下:首先，我们把S中的所有点按照它们x坐标的非升序排列，最右点(有最大x值的那点)无疑是个极大点。算法从右到左扫描这些点，同时确定它是否在y坐标上被先前扫描过的任何点所支配。这个算法在下面的算法MAXIMA中给出。ECNUYinpingLiu算法18.1MAXIMA输入：平面上n个点的集合S。输出：S中极大点集合M。1．设A为S中按x坐标非升序排列的点的集合。如果两个点有相同的x坐标，则有较大y坐标值的点出现在集合的前面2．M←{A[1]}3．maxy←A[1]的y坐标值ECNUYinpingLiu4．forj←2ton5．(x，y)←A[j]6．ifymaxythen7．M=MU{A[j]}8．maxy←y9．endif10endforECNUYinpingLiu图18.1展示了算法在一个点集上的状态。如图所示，极大点集合{a,b,c,d}形成一个阶梯。作为一个例子，请注意e仅由a支配，而f由a和b支配，g仅由c支配。很容易看出算法MAXIMA的运行时间主要由排序步骤决定，因此是O(nlogn)。上述的例子展示了平面扫描算法的两个基本组成部分。首先，有一个事件点进度表，它是一个x坐标自右向左排序的序列，这些点定义了扫描线将会“逗留”的位置，在这里扫描线是垂直线。ECNUYinpingLiu在某些平面扫描算法中情况可能与前面的例子不同，它们的事件点进度表可能需要动态更新.并且,为了得到高效的实现,可能需要比简单的数组和队列更复杂的数据结构.平面扫描方法中的其他部分是扫描线状态，这是扫描线上几何对象的适当描述。在上述例子中，扫描线状态由最新探测到的极大点的“描述”组成。这个描述仅仅是它的y坐标的值。在其他的几何算法中，扫描线状态可能需要以栈、队列或堆等形式存储所需要的相关信息。ECNUYinpingLiu2.几何预备知识在本节中，我们介绍本章中将要用到的计算几何中一些基本概念的定义。这些定义大多是在二维空间的框架之内，它们可以很容易地推广到更高维空间中。一个点p由一对坐标(x，y)表示，一条线段由它的两个端点表示。如果p和q是两个不同点，我们用记端点为p和q的线段。一条折线路径∏是点p1，p2，…，pn的一个序列，使得是线段，1≤i≤n-1，如果p1=pn，我们称∏(包括以∏为界的封闭区域)是一个多边形。在这种情况下,点pi,1≤i≤n，称为多边形的顶点，而线段,,…，:称为边。pq1iipp21pp32ppnnpp1ECNUYinpingLiu我们可以很方便地用一个存储了各个顶点的环形链表来表示一个多边形。在一些算法中，它用环形双向链表表示。如果一个多边形P的任意两条边除了在顶点处外均不相交，那么称P是简单的；否则它是非简单的。图18.2显示了两个多边形，一个是简单的，另一个不是。图18.2(a)简单多边形(b)非简单多边形图18.3(a)凸多边形(b)非凸多边形ECNUYinpingLiu从现在开始，除非特别加以说明，否则我们始终假设多边形是简单的。对于一个多边形P，如果连接P中任意两点的线段全部在P中，我们说P是凸的。图18.3显示两个多边形，一个是凸的，另一个不是。设S是平面上的一个点集，我们定义包含了S中所有顶点的最小凸多边形为S的凸包，记做CH(S)。CH(S)的顶点称为包顶点，有时也称为S的极点。设u=(x1，y1)，v=(x2，y2)和w=(x3,y3)，由这三点形成的三角形带符号面积是下面行列式的一半。ECNUYinpingLiu1yx1yx1y332211xD如果“u,v,w,u”构成一个逆时针回路，则D是正的。在这种情况下，我们说路径u,v,w构成一个左旋。如果u,v,w,u形成顺时针回路,则它是负的，在这种情况下，我们说路径u,v,w构成一个右旋(见图18.4)。D=0当且仅当三点共线，即三点在同一直线上。ECNUYinpingLiu图18.4(a)左旋(b)右旋ECNUYinpingLiu3.计算线段的交点在这一节，我们考虑以下问题。给出平面上n条线段的集合L={l1,l2,…ln}，找出交点的集合。我们将假设没有垂直线段，没有三条线段交于同一点。如果没有这些假设，则只会使算法变得更复杂。设li和lj是L中的任意两条线段，如果li与lj分别和横坐标为x的垂直线交于点pi和pj那么，倘若在横坐标为x的垂线上点pi在pj的上方，我们就说li在lj的上方，表示为lixlj，关系x定义了所有与具有横坐标为x的垂线相交的线段集的全序。于是，在图18.5中，我们有:l2xll，l2xl3，l3yl2和l4zl3ECNUYinpingLiu图18.5关系x的说明算法首先将n条线段的2n个端点按它们横坐标的非降序进行排列。在算法执行过程中，一条垂直线从左到右扫描所有线段的端点和它们间的交点。它从空的关系开始，每遇到一个端点或一个交点，就改变序关系。具体地说，当线从左到右扫描时，只要出现如下事件之一，序关系就改变。ECNUYinpingLiu(1)遇到线段的左端点时；(2)遇到线段的右端点时；(3)遇到两条线段的交点时。扫描线的状态完全由序关系x描绘，至于事件点的进度表E，它包括这些线段已排序的端点加上它们的交点，这些交点是在线从左到右扫描时动态地添加进去的。算法在每种事件上所做的动作如下:(1)当遇到线段l的左端点时，l被加到序关系中。如果有一条线段l1，紧接在l上面同时l1和l相交，则它们的交点将被插入到事件点进度表E中去。类似地，如果存在线段l2紧接在l下面同时l2和l相交则它们的交点也将被插入到E中去。ECNUYinpingLiu(2)当遇到线段l的右端点p时，算法把l从序关系中移去。在这种情况中，算法会测试紧接在l上下的线段l1和l2，看它们是否可能1在p的右侧一点q处相交。如果出现种情况，口会被插人到E中去.(3)当遇到两条线段的交点时，它们在关系中的相对次序被翻转。这样，如果在它们的交点左边有l1xl2，那么序关系要修改为l2xl1。设l3和l4是紧接在交点p的上面和下面的两条线段(见图18.6)，换句话说，对于交点右面l3在l2上面而l4在l1的下面(见图18.6)。在这种情况下，我们检查l2与l3和l1与l4相交的可能性。像前面一样，如果存在交点，就把它们插入E中。ECNUYinpingLiu图18.6在交点处翻转两条线段的次序事件点进度表和扫描线的状态所需的数据结构:为了实现事件点进度表E，我们需要一个支持以下运算的数据结构:·insert(p，E)：把点p插入到E中；·delete-min(E)：返回具有最小z坐标的点并把它从E中删除.ECNUYinpingLiu堆这种数据结构显然能够在时间O(1ogn)内支持这两种运算。于是，E由堆实现，初始时它包含2n个已排序的点。每次扫描线向右移动，横坐标最小的点被取出，像上面说明的那样，当算法探测到一个交点p时，把p插入E。扫描线的状态S必须支持以下的运算:·insert(l，S)：把线段l插入到S中；·delete(l，S)：从S中删除线段l；·above(l，S)：返回紧接在l上方的线段；·below(l，S)：返回紧接在l下方的线段。ECNUYinpingLiu一种通常称为字典的数据结构在O(logn)时间内支持上面的每个运算。注意阿above(l,s)或below(l,s)可能不存在，我们需要一个简单的测试(它没包含在算法中)来处理这两种情况。关于这一算法，一个更精确的描述在算法INTERSECTIONSLS中给出。在算法中，过程process(p)把p插入E中并输出p。算法18.2:INTERSECTIONLS输入：平面上n个线段集L={l1,l2,···,ln}。输出：L中线段的交点。ECNUYinpingLiu1.按横坐标的非降序排列端点，将它们插入堆E中(事件点进度表)2.whileE非空3.p←delete-min(E)4.ifp是左端点then5.设l是左端点为p的线段6.insert(l，S)7.l1above(l，S)8.l2below(l，S)9.ifl与l1在点q1相交thenprocess(q1)10.ifl与l2在点q2相交thenprocess(q2)ECNUYinpingLiu11.elseifp是右端点then12.设l是右端点为p的线段13.l1←above(l,S)14.l2←below(l,S)15.delete(l,S)16.ifl1与l2在p的右边点q相交thenprocess(q)17.else{p是相交点}18.设在p点相交的线段为l1和l219.其中l1在p的左边位于l2上方20.l3←above(l1,S){在p的左边}21.l4←below(l2,S){在p的左边}ECNUYinpingLiu22.ifl2与l3在q1相交thenprocess(q1)23.ifl1与l4在q2相交thenprocess(q2)24.在S中交换l1和l2的秩序25.endif26.endwhileECNUYinpingLiu排序步骤要耗费O(nlogn)时间，设交点数是m，那么有2n+m个事件点要处理，每一点需要O(1og(2n+m))处理时间，因此，算法处理所有交点的总时间是O((2n+m)log(2n+m))。因为m≤n(n-1)/2=O(n2)，阶就变成O((n+m)1ogn)。由于找出全部交点用朴素的方法要运行O(n2时间，因此这算法不适合于处理交点数目预计为O(n2/logn)线段集合。另一方面，如果m=O(n)，则算法需要O(n1ogn)时间。算法的时间复杂度：ECNUYinpingLiu4.凸包问题本节我们考察也许是计算几何中最基本的问题：在平面中给出n个点的集合S，寻找S的凸包CH(S)。我们在这里叙述一个著名的被称为“Graham扫描”的几何扫描算法。在它的简单形式中，Graham扫描使用以某一点为中心的扫描线，它旋转扫描线使之扫过整个平面，并在每一点逗留以决定这一点是否将被包括到凸包中。首先,算法在点表上做一次扫描，找出具有最小y坐标的点，记做p0,如果有两个或更多的点具有最小y坐标，就选最右的一个为p0。很明显，p0属于凸包。ECNUYinpingLiu接着，所有点的坐标被转换为以p0为原点的坐标，于是在S-{p0}中的点按照原点p0的极角排序，如果两点pi和pj与p0形成同样的极角，则更靠近p0的那一点排在前面。注意，在此我们无需计算从原点起的真实距离，因为包括开方计算，计算它是耗费很大的；这里我们只需要比较距离平方。设排序之后的表是T={p0，p1，…，pn-1}，其中p1和pn-1分别与p0形成了最小和最大的极角。图18.7显示了一个按照关于p0的极角排序的13个点集合的例子。ECNUYinpingLiu现在，对事件点的进度表，即排序表T开始扫描，扫描线的状态用一个栈St实现。栈初始时包含(pn-1，p0)，p0在栈顶。