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

1第12

章

计算几何基础计算几何简介

2平面线段及相互关系

3平扫线技术和线段相交的确定

17平面点集的凸包

27Graham扫描法

29Jarvis行进法 38最近点对问题

441.计算几何简介

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

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

4

5

显然，

p1

p2=p2

p1，但是

p1

p2=-p2

p1。下图(图12-1)解释这两个乘积的几何意义。6点积和叉积的几何含义

O=(0,0)p1p2

X

Y(x1,y1)(x2,y2)点积7

O=(0,0)p1p2

X

Y(x1,y1)(x2,y2)p1叉积

u8平面线段的相互关系我们回答前面所提的三个问题

(p4)。定理12.1给定X-Y平面上两个向量，p1和p2，如果p1

p2>0那么p1是在p2

的顺时针方向上，否则是在其逆时针方向上。如果p1

p2=0，则表明两个向量共线。证明：由上面的分析可知，p1

p2

=

|Op1||Op2|sin

。如果p1

p2>0，那么就有sin

>0。sin

>0说明

=(

-

)>0，即p1是在p2

的顺时针方向上。否则，(

-

)<0，即p1是在p2

的逆时针方向上。如果p1

p2=0，sin

=0，必有

=0或

=180

，显然表明二个向量共线。

9P1P2

OP1P2

O(a)p1

p2>0,在p1处向左拐(b)

p1

p2

<0,在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)。不共线，不相交的充要条件是d1d2>0或d3d4>0。两个线段不共线而且相交。充要条件是情形(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之上，则记为u>x

v。例(图12-5)udcabtr(a)平扫线在3个点的状态: r点:<a,c>t点:<a,b,c>u点:<b,c>eifhgyxwz(b)

平扫线在4个点的状态:

w点:<e,g,f>x点:<e,f>y点:<f,e>z点:<f,i,e>19平扫线的事件点我们有以下观察：如果线段u和v相交于点p，那么必有状态点x<p

和状态点y>p使得在x和y的状态序列中，u和v相邻，但它们的顺序相反。例如，在上图(b)中，e>x

f，但是f

>y

e。平扫线状态中的线段集合，在碰到下面两种情况时才会改变：到达一个位置，正好是一个新线段的左端点。到达一个位置，正好是状态中某个线段的右端点。n个线段有2n个端点。它们在X轴上的坐标称为事件点(eventpoint)。算法根据平扫线状态在这2n个事件点上的变化作出判断。20事件点调度序列把2n个事件点从小到大，即从左到右，排序后的序列称为事件点调度(Event-pointscheduling)序列。如果有多端点有共同的X-坐标，把左端点排在右端点前面。如果有多个左端点有共同的X-坐标，有较小Y-坐标的排在前面。如果有多个右端点有共同的X-坐标，有较小Y-坐标的排在前面。

21用平扫线确定线段相交的算法简介按调度序列，逐点检查。在每个事件点上，做下面两件事之一：如果这个点是某线段s的左端点。操作如下：将

s

插入到状态序列中。并检查，s插入后，它是否有相邻线段。如果有，用程序Segment-Intersect判断它们与s是否相交。如果相交，算法结束并报告一对相交的线段。否则，进入下一个事件点。如果这个点是某线段

r的右端点。操作如下：检查

r是否同时有上面的相邻线段和下面的相邻线段。如果有，用程序Segment-Intersect判断这两个相邻线段之间是否相交。如果相交，算法结束并报告一对相交的线段。否则，算法将线段r从状态序列中刪除。然后，进入下一个事件点。如果在2n个事件点都检查之后仍未发现有线段相交，则算法结束并报告没有交点。22红-黑树平扫线技术需要动态地，不断地对状态序列进行插入一个线段或刪除一个线段的操作，我们用红-黑树为数据结构来支持这些操作。红-黑树是二元搜索树的一种。它可保证在O(lgn)时间内完成一个插入或刪除操作，这里，n是当前红-黑树中顶点的个数。所以，为2n个事件点更新状态总共只需要O(nlgn)时间

(参阅附录-A)。

这里我们约定几个对红-黑树T进行操作的记号：Insert(T,s): 把线段s插入T；Delete(T,s): 把线段s从T中刪除；Above(T,s): 找出T中紧排在s上面的线段；Below(T,s): 找出T中紧排在s下面的线段。用平扫线确定线段相交的算法伪码如下。23Any-Segments-Intersect(S,n) //S是n个线段的集合T

//红黑树初始为空把2n

个端点排序，得调度序列L[1..2n]for

i

1to2n

ifL[i]

istheleftendpointofsegments //L[i]是线段s的左端点 then

Insert(T,s)

if

(Above(T,s)existsandintersectss)

//调用Segment-Intersect，如果s与上面相邻线段相交

thenreturntrue,s,Above(T,s)，endif

if(Below(T,s)existsandintersectss)//下面线段与s相交

thenreturntrue,s,Below(T,s)，endif else

L[i]istherightendpointofsegmentr

//L[i]是线段r的右端点

ifAbove(T,r)andBelow(T,r)existandintersect

//线段r上面和下面的线段存在并相交

then

returntrue,Above(T,r),Below(T,r)

endif

Delete(T,r)

endifendforreturnfalseEnd24例(图12-6)第1个事件点上只有a；第2个事件点上插入b在a之下但不相交；第3个事件点上插入c，与a和b相邻但都不相交；第4个事件点上插入d在a之上但不相交；第5个事件点上刪去a后d与c相邻但不相交；第6个事件点上插入e在d之上但不相交；第7个事件点上刪去c后发现d与b相邻并相交，算法结束。acbedcbdacbdcababeafdcbedb(1)(2)(3)(4)(5)(6)(7)25定理12.3

算法Any-Segments-Intersect能正确地确定S中是否有线段相交。证明：当算法报告有线段相交时显然是正确的，所以我们只需证明，只要有线段相交，算法一定会报告true。假设S中有线段相交，而p是所有交点中X-坐标最小的一个，并假设在p点相交的线段是a和b。我们分三种情况讨论。(a) 线段a和b的左端点均出现在点p的左边。设点q是点p左边最后一个事件点。如果a和b在q的平扫线状态中不相邻，那么如图(a)，一定有线段d在q点的状态中介于a和b之间。(a)

线段a和b的左端点都出现在交点p的左边。dpabq如果d的右端点在q的右边，则d必与a或b相交，点p就不是最左边的交点了，矛盾。如果右端正好在q点的平扫线上，那么在事件点q上把d删去后，发现a和b相邻并相交。因假设无3线段共点，

右端点不会在p点。26（接上页）(b) 线段a的左端点在点p的左边，而b的左端点与p重合。(b)

线段a的左端点在p点左边而线段b的左端点与交点p重合。pab这种情况下，p点是事件点。如在p点之前，已发现有线段相交，证明完成。否则，算法会在p点把b插入到平扫线状态中并且与a相邻。显然，算法会报告a和b相交。同理可证对称情况，即a的左端点与p重合，而b的左端点出现在p的左边。线段a和b的左端点均与点p重合。这种情况下，a和b的左端点都是事件点，并且会在p点的平扫线状态中被先后插入而且相邻，所以算法会报告a和b相交。(证毕)(c)

两个线段的左端点都与交点p重合。pab27定义12.5

一个多边形就是平面上一组首尾相连的线段组成的封闭曲线。曲线中的线段称为边(side)，而这条曲线称为多边形的边界。假设顺序有n条边，(p0,p1)，(p1,p2)，…，(pn-1,p0)，那么这个多边形称为n边形，并可表示为<p0,p1,…,pn-1>，称为顶点序列。定义12.6

一个简单n边形就是自身无交点的多边形，即它的n条边之间，除相邻两条边的一端点重合外，没有其他交点。除特别说明外，我们只讨论简单多边形，简称多边形。定义12.7被一个多边形所包围的平面上的点的集合(不含边界)称为该多边形的内部，多边形的边界和内部的点以外的平面上所有其他点的集合称为该多边形的外部。定义12.8如果一个多边形的内部或边界上任意两点间的线段不含外部的点，那么该多边形称为一个凸多边形。3.平面点集的凸包

28p0p1p4p2p3p5(a)

一个非简单多边形p5p3p2p4p0p1(b)

一个简单多边形但不是凸多边形p0p4p3p2内部外部边界p1(c)

一个凸多边形例定义

12.9

假设Q是平面上n个点的集合，它的凸包(ConvexHull)是包含Q的最小凸多边形，记为CH(Q)。例(图12-9)p1p2p3p4p5p6p7p8p0

P9下面讨论两个找凸包的算法。29

30Graham-scan(Q) //Q是有n+1

3个点的集合假设已有

1

<

2

<…<

n。Push(S,p0)；Push(S,p1)；Push(S,p2)； //初始化fori

3to

n

q

Top(S) p

Next-to-top(S) while(q–p)

(pi–q)

0 //从点p到q后，再到pi时，不左拐 Pop(S) //点q不可能是凸包的顶点

q

p

p

Next-to-top(S)

endwhile Push(S,pi)endforreturn

SEnd31例(图12-10)p10p3(c)

扫描p4后压入p4

p2

p6p4

p7p5p9

p8

p1

p0p10p3(d)

扫描p5时，弹出p4后压入p5

p2

p6p4

p7p5p9

p8

p1

p0p3(a)

初始状态

p2

p6p4

p7p5p9

p8

p10

p1

p0p3(b)

扫描到p3时，弹出p2后压入p3

p2

p6p4

p7p5p9

p8

p10

p1

p032p10p3(e)

扫描

p6后压入p6

p2

p6p4

p7p5p9

p8

p1

p0p10p3(f)

扫描

p7后压入p7

p2

p6p4

p7p5p9

p8

p1

p0p10p3(g)

扫描

p8时，弹出p7、p6后压入p8

p2

p6p4

p7p5p9

p8

p1

p0p10p3(h)

扫描

p9后压入p9

p2

p6p4

p7p5p9

p8

p1

p033p10p3(i)

扫描

p10时，弹出p9后压入p10

p2

p6p4

p7p5p9

p8

p1

p0p10p3(j)

算法产生的凸包

p2

p6p4

p7p5p9

p8

p1

p0Graham扫描法复杂度主要部分是排序。排序后的扫描只需O(n)时间，这是因为每次检查三点两线段的走向是在向堆栈内压入一个点或弹出一个点之后进行，包括第一次检查也是在初始化压入三点后进行。因每个点最多被压入和弹出各一次，而检查一次只需常数时间，所以排序后的扫描只需O(n)时间，因此，扫描法的复杂度是O(nlgn)。34Graham扫描法的正确性证明定理12.4算法Graham-scan(Q)结束时，堆栈中从底到顶的点的序列就是点集合Q的凸包顶点沿反时针方向的一个序列。证明：初始化后，其余各点扫描的顺序是p3,p4,…,pn。定义Qi

={p0,p1,p2,…,pi}，i=2,3,4,…,n。显然有Q2

Q3

…

Qn

=Q。下面，我们归纳证明：在for循环从i=3开始，对pi扫描后，堆栈中从底到顶的点的序列就是Qi的凸包顶点沿反时针方向的一个序列。这样，在i=n时，因为Qn

=Q，定理得证。我们设计一个与

i有关的命题称为不变量(invariant)。先证明这个命题在循环开始前正确(相当于归纳基础)。再证明每次循环后，这个命题都是正确的(相当于归纳步骤)。最后证明循环一定会停止。(接下页)35命题：对pi扫描后，堆栈中从底到顶的点的序列就是Qi的凸包CH(Qi)的顶点沿反时针方向的一个序列。初始化循环开始前，堆栈中从底到顶点的点序列是{p0,p1,p2}。显然它是集合Q2的凸包CH(Q2)顶点沿反时针方向的一个序列。循环维持假设在循环i=k

(k

3)，之前，堆栈中从底到顶点的点序列是集合Qk-1的凸包CH(Qk-1)的顶点沿反时针方向的一个序列。那么，当我们刚进入循环i=k时，由算法知，必有Top(S)=pi-1，假设此时，Next-to-top(S)=pa。循环i=k的操作有两部分。第一部分是while循环，把不可能成为凸包顶点的点从堆栈弹出。第二部分是把pi压入堆栈。这时有两种情况，分别讨论如下：36

pipi-1(a)

压入pi前栈顶为pi-1Qi-1p0p1pap2(a) 压入pi前栈顶为pi-1，Next-to-top(S)=pa。因此，在循环i=k结束时，堆栈中从底到顶的点的序列就是凸包CH(Qi)的顶点沿反时针方向的一个序列。（第2种情况见下页）37

(b) 压入pi前栈顶为pj，而j<i-1。pj(b)压入pi前栈顶为pj，j<i-1Qjp0p1pipap2pi-1可看出，所有被弹出的点都被包含在

p0pjpi中。因为从pj到pi是向左拐，因此CH(Qj)加上pi点后是Qj

{pi}的凸包。因为所有被弹出的点也被包含在这个凸包中，因此断言在这种情况下亦正确。循环终止因为停止弹出时堆栈中至少有两个点，所以每次循环对堆栈的操作是有限次。因为循环次数为n-2，所以算法一定会终止，定理正确。

38

39

40算法的正确性证明(继续)因此，栈外各点，pi+1,pi+2,…,pn，以及p0，除pk外的任何一点都不可能是在凸包CH(Q)的顶点沿反时针方向的序列中接在pi后面的顶点，否则，如下图(12-12)所示，pk会落在凸包的外部。因此，凸包中pi后面的顶点必定是pk。归纳成功。pkp0p1piPu堆栈中点都是凸包顶点栈外所有点，以及p0，都在pk的逆时针方向或在线段(pi,pk)上。由所证命题知，每次第(2)步压入堆栈的点都是凸包的下一个顶点，所以，当pk

=p0时，堆栈中点就必定是CH(Q)的顶点序列，算法正确。

(伪码见下页)41

42

p2p10p1p3p8(c)P5是下一个凸包顶点

p6p4

p7p5p9

p0p8

p10(d)

P8是下一个凸包顶点p2p1p3

p6p4

p7p5p9

p0p8(a)

初始化后情形

p2p10p1p3

p6p4

p7p5p9

p0(b)

P3是下一个凸包顶点

p2p10p1p3p8

p6p4

p7p5p9

p0例(图12-13)43p3(e)

P10是下一个凸包顶点

p2p10p1p8

p6p4

p7p5p9

p0

p2p10p1p3p8

p6p4

p7p5p9

p0Jarvis行进法复杂度因为从堆栈中每个点出发去找下一个凸包顶点时，Jarvis行进法需要在集合Q中找出最右边点，这需要O(n)时间，所以Jarvis行进法的复杂度是O(hn)，这里h是凸包顶点的个数，也是算法结束时堆栈中点的个数。44给定平面上n个点的集合P，最近点对问题是：找出两个点a和b使得它们的距离是所有点对中最近的，即d(a,b)=min{d(u,v)|u,v

P}。如果算出所有点对之间的距离，那么需要

(n2)时间。我们介绍一个只要O(nlgn)时间的分治法。分如下几部分讨论：预备工作和分治法的底分治法的分分治法的合分治法的伪码4.最近点对问题

45预备工作和分治法的底把P中这n个点的Y坐标从小到大排序并存放在数组Y中，使得

Y[1]≤Y[2]≤…≤Y[n]。用X[1..n]表示它们对应的X坐标，所以，这n点可表示为

pk=(X[k],Y[k])(1

k

n)。把

pk(1

k

n)

的X坐标从小到大排序并存放在数组X*中，使得X*[1]≤X*[2]≤…≤X*[n]

(1

i

n)。用函数I[k]记录原序列中X[k](1

k

n)在序列X*中的序号。如果X[k]=X*[i]，则有I[k]=i。如果n

2，分治法见底，我们可以直接地算出最近点对的距离。算法对底的处理很简单，下页给出这部分的伪码。46

47分治法的分设有Y[1]≤Y[2]≤…≤Y[n]，X*[1]≤X*[2]≤…≤X*[n]，并且已建立函数I[k](1

k

n)。如果n

3，则需要分治。下面是分治的步骤：mid

n/2；以直线x

=X*[mid]为分界线把P分为左右两个集合，L和R。它们的X-坐标是

X*L[1..mid]=X*[1..mid]

X*R[1..n-mid]=X*

[mid+1..n]它们对应的Y-坐标排序于数组YL[1..mid]和YR[1..n-mid]中。在划分时，如果PL中点有Y坐标YL[l]的话(1

l

mid)，那么，求该点的X坐标在X*L中的序号的函数IL[l]也同时产生。同样地，对PR中点(1

r

n-mid)，函数IR[r]也同时产生。以上划分集合P的工作可用下面一段程序完成

(见下页)48Distribution(X*[1..n],Y[1..n],I[1..n],mid) //

mid=

n/2

已在调用它的程序中算出l

r

1 //

分别是YL

和YR

的开始序号fork

1to

n //逐个分配和处理Y[k]

i

I[k] //Y[k]

的X坐标是X*[i]

if

i

mid //对应的点(X*[i],Y[k])属于PL

then

YL[l]

Y[k] //把Y[k]按序排入左集合

X*L[i]

X*[i] //

逐步做X*L[1..mid]

X*[1..mid]

IL[l]

i //构造函数IL，YL[l]的X坐标是X*L[i]

l

l+1

else

YR[r]

Y[k] //把Y[k]按序排入右集合

j

i–mid

X*R[j]

X*[i] //

逐步做X*R[1..n-mid]

X*[mid+1..n]

IR[r]

j

//构造函数IR，YR[r]的X坐标是X*R[j]

r

r+1

endifendfor

End

分治法的划分总共需要O(n)时间49分治法的合把P中点分为PL

和PR后，递归地分别找到PL

和PR中最近点对，其距离分别是

L

和

R。它们对应的点对为(pL，qL)和(pR，qR)。我们先找出

=min{

L

和

R}，其对应点对为(p,q)。显然

不一定是最近奌对的距离。分治法的合就是要解决子问题的解不能包含的那些情况下的解。在这个问题中，如果有更近的点对(

,

)，则其中一点

在集合PL中而另一点

在集合PR中。另外，

和

与直线x

=l(=X*[mid])的距离必须小于

。如下图(12-14(a))所示，我们只须检查以直线x

=l为中心，以

为左右距离的带状区域中点即可。我们检查是否这个区域中有两点，其距离小于

。做法如下：50x=lLR

L中的一个点和R中的一个点可能在此重迭L中一个点和R中的一个点可能在此重迭

(b)

最多8个点可出现在

2

矩形之中L

R=Y(

)

2

x=l

=Y(

)+

x=l-

x=l+

(a)点对(

,

)必须出现在2

矩形中51(1) 把带状区域中点按Y-坐标从小到大排序于数组Y*[1..m]

(m

n)中。

另外，用J[h]=k

表示Y*[h]在原序列Y[1..n]中的位置，即Y*[h]=Y[k](1

h

m)。这一步可由下面程序完成：Delta-Selection(X*[1..n],Y[1..n],I[1..n],Y*[1..m],J[1..m],

)//输出Y*，Jl

X*[mid] //mid

在划分集合P时已算好m

0fork

1to

n

i

I[k] //

Y[k]对应的X坐标是X*[i]

if

(l-

<X*[i])and(X*[i]<l+

) //带状区内，顺序放入Y*

then

m

m+1

Y*[m]

Y[k]

J[m]

k //以便从Y*[m]找到Y[k]

endifendfor //带状区域内有m个点End52逐点检查Y*[i]

(1

i

m)，看是否有Y*[j]

(i

<j

m),使得这两点间距离小于

。假设Y*[i]对应的点是

，它的Y-坐标是Y(

)=Y*[i]，如上图(12-14(a))所示，我们只需检查

2

的矩形中的点与

的距离即可。