算法设计与分析(十)

算法设计与分析2010.9(ACM创新实验班)王多强[e-mail]十、计算几何学什么是计算几何学？计算几何学是计算机科学的一个分支，专门研究解决几何问题的算法。这一类问题中，输入一般是关于一组几何对象的描述，如点、线段、多边形等。输入则是对有关这些对象的问题的解答，如直线是否相交？是否为一个新的几何对象，如顶点集合的凸包等。p1p2p4p2计算几何学常见问题折线段的拐向判断判断点与线、矩形、多边形、圆之间的相对位置关系计算点到线段、折线、矩形、多边形的最近点计算线段、直线与线、矩形、多边形、圆的交点判断形状间的包含，如一个矩形是否在另一个矩形之中凸包问题等在现代工程和数学领域，计算几何在图形学、机器人技术、超大规模集成电路设计和统计学等诸多领域，都有着十分重要的应用。10.1线段的性质1.点的表示n个点输入对象记为：{p1,p2,...,pn}，其中每个pi=(xi,yi),xi∈R,yi∈R。形状一般用点的序列来表示，如多边形用顶点集{p1,p2,...,pn}表示。2.点的凸组合(convexcombination)两个不同的点p1=(x1,y1)和p2=(x2,y2)的凸组合是满足下列条件的任意点p3=(x3,y3)：对于a，(0≤a≤1)，有：x3=ax1+(1-a)x2,y3=ay1+(1-a)y2。也可写作p3=ap1+(1-a)p2。p1,p2,p3的相对位置关系如图：亦即，p3位于穿过p1和p2的直线上、并处于p1和p2之间（包括p1和p2两点）的任意点。而线段p1p2可以看作是p1和p2的凸组合的集合p1p3p2这里，称p1、p2是线段的p1p2的端点。如果考虑有向性，可以记有向线段为p1p2。如果p1是原点(0,0)，则有向线段p1p2简称为向量p2。向量p1和p2的叉积可以看作是由点(0,0)，p1，p2和p1+p2=(x1+x2,y1+y2)所形成的平行四边形的面积。如图所示：叉积也被定义为下面的行列式形式：叉积p2p1p1+p2(0,0)121221212121ppyxyxyyxxpp分析：如果p1×p2为正数，则相对于原点(0,0)来说，p1在p2的顺时针方向上；如果p1×p2为负数，则p1在p2的逆时针方向上；下图示出向量p的顺时针区域和逆时针区域。如果叉积为0的话，则p1、p2共线，p1、p2指向同一个方向或相反的方向。p(0,0)xyp1p2(0,0)p1p2(0,0)p的逆时针方向p的顺时针方向p1、p2同向共线p1、p2逆向共线如何判断线段之间的相对方向？已知两个有公共端点p0的有向线段p0p1、p0p2，计算叉积：(p1-p0)×(p2-p0)=(x1-x0)(y2-y0)-(x2-x0)(y1-y0)若＞0，则p0p1在p0p2的顺时针方向上若＜0，则p0p1在p0p2的逆时针方向上若＝0，则p0p1和p0p2共线确定连续线段是向左转还是向右转？已知两条连续的线段p0p1、p1p2，在p1点是向左转还是向右转？方法一：运用三角公式求出∠p0p1p2，判断其转向；方法二：运用叉积，无需对角进行计算即可判断线段的转向。亦即如图所示，检查有向线段p0p2是在有向线段p0p1的顺时针方向还是在其逆时针方向？p0p1p2逆时针p0p2顺时针p1计算叉积：(p2-p0)×(p1-p0)若叉积＜0,则p0p2在p0p1逆时针方向，在点p1就是左转。若叉积＞0,则p0p2在p0p1顺时针方向，在点p1就是右转。若叉积＝0,则p0、p1、p2三点共线。p0p1p2逆时针p0p2顺时针p1确定两个线段是否相交跨域：给定一个线段p0p2线，如果点p1位于某一直线的一边，而点p2位于该直线的另一边，则称线段p0p2跨越了该直线。如果p1和p2落在直线上，则出线共线情况。相交：当且仅当下面两个条件中至少一条成立时，两个线段相交：1）每个线段都跨越了另一线段的直线；2）一个线段的某一端点位于另一线段上。p1p2程序描述1）定义过程DIRECTION(pi,pj,pk)：使用叉积计算线段pipk相对于线段pipj的方位，返回叉积的值。如图所示，令d1=DIRECTION(p1,p2,p3)，d2=DIRECTION(p1,p2,p4)，若d1≠0，d2≠0，且两者的符号不同，则线段p3p4跨越线段p1p2的直线，如图a)和b)。若d1＝0，则线段p3在线段p1p2的直线上,如图c)或d)。p1p2p3p4p1p2p3p4p1p2p3p4a)b)c)p1p2p3p4d)2）定义过程ON-SEGMENT(pi,pj,pk)：当dk＝0时，ON-SEGMENT(pi,pj,pk)判断pk是否位于线段pipj上：点pk位于pipj上的充分必要条件是pk落在端点pi和pj之间，包括与端点pi或pj重叠。如图：图c)是线段相交的情形，而图d)中的两个线段并不相交。p1p2p3p4c)p1p2p3p4d)3）定义过程SEGMENTS-INTERSECT(p1,p2,p3,p4)：布尔函数，判断线段p1p2和p3p4是否相交，相交，则返回TRUE，否则返回FALSE。4）过程的描述如下：SEGMENTS-INTERSECT(p1,p2,p3,p4)d1←DIRECTION(p3,p4,p1)d2←DIRECTION(p3,p4,p2)d3←DIRECTION(p1,p2,p3)d4←DIRECTION(p1,p2,p4)if((d1＞0andd2＜0)or(d1＜0andd2＞0))and((d3＞0andd4＜0)or(d3＜0andd4＞0))thenreturnTRUEelseifd1＝0andON-SEGMENT(p3,p4,p1)thenreturnTRUEelseifd2＝0andON-SEGMENT(p3,p4,p2)thenreturnTRUEelseifd3＝0andON-SEGMENT(p1,p2,p3)thenreturnTRUEelseifd4＝0andON-SEGMENT(p1,p2,p4)thenreturnTRUEelsereturnFALSEENDSEGMENTS-INTERSECTDIRECTION(pi,pj,pk)return(pk-pi)×(pj-pi)ENDDIRECTIONON-SEGMENT(pi,pj,pk)ifmin(xi,xj)≤xk≤max(xi,xj)andmin(yi,yj)≤yk≤max(yi,yj)thenreturnTRUEelsereturnFALSEENDON-SEGMENT例：p1p2p3p4p1p2p3p4a)b)0)()(3431pppp0)()(1213pppp0)()(1214pppp0)()(3432pppp0)()(3431pppp0)()(1213pppp0)()(3432pppp0)()(3432pppp分析：上述问题也可以按照通常的解析几何的方法求解，如计算出形如y=kx+b的直线方程，然后求直线交点，然后检查交点是否落在线段的端点之间，判定线段的相交性。我们的算法仅使用加、减、乘和比较运算就完成了计算，没有使用除法，不需要三角函数计算。优点：除法、三角函数的计算代价都很高除法的舍入误差问题近似平行线时，求斜率k对计算机除法运算的精度非常敏感，很容易产生溢出问题等。10.2确定任意一对线段是否相交对给定的一组线段，确定其中任意两个线段是否相交？这里假设：1）所有的线段不垂直的（水平的可以）。2）相交于同一点的线段数≤2。（假设的目的是为了在算法设计中简化对边界条件的处理。可以证明假设的合理性，对于假设外的情况也可以进行有效处理）扫除技术（Sweeping）：在几何空间中，假想存在一条垂直直线，称为扫除线。从左到右移动扫除线。扫除线移动时会穿过一组已知的几何物体，而扫除线移动的空间方向可以看作是一种次序（时间顺序或空间位置次序）。利用穿过几何体时扫除线的这种次序对几何物体进行空间排序、筛选或其它处理。这种技术称为扫除技术abcdrut线段排序根据假设，不存在垂直线段，所以任何线段与垂直扫除线至多有一个交点。因此，在某x处，可以根据线段与扫除线交点的y坐标对线段进行排序。考察两条线段s1和s2。如果横坐标为x时，垂直扫除线与这两条线段都相交，则称这两条线段在x处是可比的。如果s1和s2在x处可比，并且在x处，扫除线的交点与s1的交点比与s2的交点高，则说在x处，s1位于s2之上，记为s1＞xs2。如图，有1）a＞rc2）a＞tb、a＞tc、b＞tc3）b＞uc4）线段d与其它任何线段都不可比abcdrut对任意给定的x，关系＞x是定义在那些在x出与扫除线相交的线段上的全序关系，即任何两条这样的线段都是可比的。当线段的左端点遇到扫描线时，线段进入排序，而当其右端点遇到扫除线时，就离开排序。随着x的不同，扫除线与扫除线的交点是不断变化的，线段间的次序会随之而改变。如图，线段e和f相交与o点。在o的左方，e＞vf，而在o的右方，f＞we交点o：存在线段次序变换的现象efghiwzvo当扫除线穿过两条线段的交点时，它们在全序中的位置将被颠倒，如图所示，线段e、f在交点o处的次序发生了颠倒。由于假定没有三条线段相交于同一点，所以必有某条垂直线扫除线x，使得相交线段e和f在全序＞x中是连续的。如图，任何穿过阴影区域的扫描线（如z）都是的e和f在其全序中连续。efghiwzvo扫除线的数据结构定义扫除线一般要维护下列两组数据：1）扫除线状态（sweep-linestatus）：即与扫除线相交的物体之间的关系；2）事件点（event-pointschedule）：是一个从左向右的x坐标的排列，这些x坐标记录了扫除线状态发生变化的位置。efghiwzvo在本问题中，每条线段的端点都是事件点，因为当扫除线进入（离开）任何端点处，都将引起扫除线状态的改变。而这，通过增加x坐标，从左向右对线段的端点进行排序即可得线段问题的所有事件点。如果两个或多个端点位于同一条垂直线上，若y坐标不同，则有坐标小的排在前面，若y坐标也相同（即相交于同一点），则看另一端点的x坐标，小的放在前面。abcdefababdbcdcdceehfhf基于上述定义，根据事件点调度序列检查线段。当扫除线遇到线段的左端点时，就把该线段插入到扫除线状态中；当扫除线遇到线段的右端点时，就把它从扫除线状态中删去；当两条线段在全序中第一次变为连续（连续排列在一起）时，就检查它们是否相交（注：非连续排列在一起的线段是不会相交的）。扫除线状态是一个全序T，定义T上的操作如下：INSERT(T,s)：把线段s插入T中；DELETE(T,s)：把线段s从T中删除；ABOVE(T,s)：返回T中紧靠线段s上面的线段；BELOW(T,s)：返回T中紧靠线段s下面的线段。输入n条线段，运用红黑树，可以在O(logn)的时间内执行上述操作。判断线段集合中线段相交的过程ANY-SEGMENTS-INTERSECT(S)//S为n个线段的集合，如果找到S中任一对线段相交就返回TRUE；否则，若S中没有任何线段相交，则返回FALSE。全序T由一棵红黑树实现。//T←ΦsorttheendpointsofthesegmentsinSfromlefttoright,breakingtiesbyputingleftendpointbeforerightendpointsandbreakingfurthertiesbyputtingpointswithlowery-coordinatesfirstforeachpointpinthesortedlistofendpointsdoifpistheleftendpointofasegmentsthenINSERT(T,s)if(ABOVE(T,s)existsandintersectss)or(BELOW(T,s)existsandin