第十一章 计算几何问题

11.1 引言

一、二维平面中的点、线段和多边形

1、点：

用数偶(x,y)表示点p的坐标。 2、线段：

由它的两个端点表示。

如果p(x1,y1)，q(x2,y2)是两个离散的点，端点为p和q的线段，表示为pq。 3、多边形：

多边形路径是点p1,p2,,pn的一个序列，其中，pipi1是线段，1in1。 如果p1pn，则由所封闭起来的区域称为多边形。

pi称为多边形的顶点；线段pipi1称为多边形的边。

通常用“多边形”来表示多边形的边界。 4、简单多边形和非简单的多边形：

除了顶点之外，任何两条边都不会交叉的多边形称为简单多边形； 有交叉边的多边形称为非简单的多边形。

例：图11.1(a)是简单的多边形，图11.1(b)是非简单的多边形。

（a） （b）

图11.1 简单的多边形(a)和非简单的多边形(b)

5、凸多边形和非凸多边形

凸多边形：连接多边形任意两个顶点的线段，完全处于多边形内部， 非凸多边形：连接多边形任意两个顶点的线段，不完全处于多边形内部 例：图11.2(a)表示一个凸多边形，图11.2(b)表示一个非凸多边形。

1

（a） （b）

图11.2 凸多边形(a)和非凸多边形(b)

二、有向面积

1、以源点作为始点的两个向量的有向面积

点p(x1,y1)，q(x2,y2)是以源点o(0,0)作为始点的两个向量op及oq的端点，则向量op及oq的有向面积为：

opoqx1y1x2 y2x1y2x2y1 oqop

2、两向量有向面积的平行四边形表示

若过点p平行于oq的直线与过点q平行于op的直线相交于s， p,q,s的垂线与X轴分别相交于a,b,c，

平行四边形opsq的面积S为：

obq的面积加上梯形qbcs的面积，减去opa的面积，再减去梯形pacs的面积。

显然，acobx2，bcoax1，csbqapy1y2。

S1111x2y2(y2y2y1)x1x1y1(y1y1y2)x2 2222 x1y2x2y1

y s q(x2,y2) p(x1,y1) o b a c x

图11.3 由两个向量所构成的平行四边形

3、结论

1）opoq的有向面积的绝对值，等于平行四边形opsq的面积。

2

2）当opoq值为正时，向量op可沿着平行四边形内部逆时针旋转到达oq； 3）当opoq值为负时，向量op可沿着平行四边形内部顺时针旋转到达oq。 4、左转的三角区和右转的三角区

o,p,q三点的坐标分别为(x1,y1),(x2,y2),(x3,y3)， op(x2x1,y2y1)，oq(x3x1,y3y1)。

opoq(x2x1)(y3y1)(x3x1)(y2y1)

x1y2x2y3x3y1y1x2y2x3y3x1

上述opoq的有向面积，也可用下面的行列式的值来确定：

x1Dx2x3y1y2y311x1y2x2y3x3y1y1x2y2x3y3x1 1（11.1.1）

当D为正时，o,p,q,o构成一个反时针方向的回路，就说路径o,p,q是左转的， 当D为负时，o,p,q,o构成一个顺时针方向的回路，就说路径o,p,q是右转的， 当D0时，这三点在同一直线上。

例：图11.4表示左转的三角区和右转的三角区。

q q p p o o （a） （b）

图11.4 左转的三角区域(a)和右转的三角区域(b)

二、几何扫描

1、几何扫描

对物体进行扫描，以便确定物体的几何形状、识别物体中各个部件的几何特征及部件之间的联系。 2、平面几何扫描

在二维平面上，对某一个对象从左到右用垂直线进行扫描。

三、平面扫描算法的基本组成部分：

1、事件调度点p_schedule

按X坐标排序的点序，由这些点定义了扫描线的“站点”位置。 2、扫描线状态，

扫描线的“站点”状态，表示在“站点”位置时，所处理几何对象的状态。 扫描线状态的描述，取决于所处理的几何对象。

3

11.2 平面线段的交点问题

一、问题

给定平面上n条线段的集合L{l1,l2,,ln}，寻找它们的交点集合。 二、平面上线段的关系描述

定义11.1 令li和lj是平面上任意两条线段，它们与X坐标为x的垂线分别相交于点pi与pj。若pi的Y坐标值大于pj的Y坐标值，就说li在x高于lj，记为lixlj。

如果线段li和lj，其中有一条、或者两条都不与X坐标为x的垂线相交，就说这两条线段不存在x关系。

例：图11.5中，有如下关系成立：

l1al3al4，l3bl1bl4，l2cl3

在“站点”a，扫描线状态为l1al3al4； 在“站点”b，扫描线状态为l3bl1bl4； 在“站点”c，扫描线状态为l2cl3。

l1 l2 l3 l4 a b c x

图11.5 线段之间的x关系

11.2.1 寻找平面线段交点的思想方法

一、寻找平面线段交点的两种方法

1、计算所有的线段的交点，需O(n2)时间。

2、从左到右扫描所有线段，根据线段的x关系，对扫描到的线段进行定序，排除不可能相交的线段，只对有可能相交的线段确定它们的交点位置，可以有效减少计算交点的时间。 二、算法的思想方法：假定不会出现三条线段相交于一点的情况

对n条线段的2n个端点以X坐标的非降顺序排序； 用垂线从左到右扫描所有的线段；

用线段的端点和交点构成事件调度点序列E； 把扫描线所扫描到的线段按x关系定序， 在扫描线上线段的x关系，构成了扫描线的状态， 开始时，扫描线的初始状态为空，

扫描线从左到右扫描时，遇到三种事件调度点：线段的左端点、右端点、两线段交点。

4

每遇到一个事件调度点，就执行下面的一种相应的动作，并刷新扫描线的状态： 1. 扫描到线段l的左端点的处理：

把线段l按照x关系的顺序，插入到当前扫描线状态集S中， 若S中存在与l紧邻的线段l1以及（或者）l2，使得l1xl，lxl2， 且若l与l1，以及（或者）l与l2有交点，把交点保存到交点集T中， 把交点按X坐标的非降顺序，插入事件调度点序列E中； 2. 扫描到线段l的右端点的处理：

若S中存在与l紧邻的线段l1及l2，使得l1xl，lxl2，

并且，如果l1与l2有交点且未处理，就把它们的交点保存到交点集T中， 并把它们的交点按X坐标的非降顺序，插入事件调度点序列E中， 把线段l从S中删去；

3. 扫描到线段l1及l2的交点的处理：

把扫描线状态集S中l1与l2的x关系颠倒过来，

在交点的右边，如果S中存在着l1与l2的紧邻l3及l4，使得l3xl2，l1xl4， 并且l3与l2、l1与l4有交点，且交点尚未保存到T中，就保存它们的交点， 把交点按X坐标的非降顺序，插入事件调度点序列E中。 例11.1 寻找图11.6中五条线段的交点。

10个端点按X坐标的非降顺序，事件调度点序列E{1,2,3,4,5,6,7,8,9,10}。 用垂线从左到右扫描事件调度点，过程如下：

2 1 4 a b 9 c 7 e 10 3 d f 5 6 8 图11.6 寻找线段交点的过程

1. 端点1： S{l1}；T；E{2,3,4,5,6,7,8,9,10}； 2. 端点2： S{l2,l1}； T{a}；E{3,4,5,a,6,7,8,9,10}； 3. 端点3： S{l2,l1,l3}；T{a}；E{4,5,a,6,7,8,9,10} 4. 端点4： S{l2,l4,l1,l3}；T{a,b}，E{b,5,a,6,7,8,9,10}； 5. 交点b： S{l2,l1,l4,l3}；T{a,b,c}；E{5,c,a,6,7,8,9,10}； 6. 端点5： S{l2,l1,l4,l3,l5}；T{a,b,c}；E{c,a,6,7,8,9,10}： 7. 交点c： S{l2,l1,l3,l4,l5}，T{a,b,c,d}；E{a,d,6,7,8,9,10}； 8. 交点a： S{l1,l2,l3,l4,l5}；T{a,b,c,d,e}；E{d,6,e,7,8,9,10}； 9. 交点d： S{l1,l2,l3,l5,l4}，T{a,b,c,d,e}；E{6,e,7,8,9,10}； 10. 端点6： S{l1,l2,l3,l5}；T{a,b,c,d,e}；E{e,7,8,9,10}；

5

11. 交点e： S{l1,l3,l2,l5}；T{a,b,c,d,e,f}；E{7,f,8,9,10}； 12. 端点7： S{l1,l2,l5}；T{a,b,c,d,e,f}；E{f,8,9,10}； 13. 交点f： S{l1,l5,l2}；T{a,b,c,d,e,f}；E{8,9,10}； 14. 端点8： S{l1,l5}；T{a,b,c,d,e,f}；E{9,10}； 15. 端点9： S{l5}；T{a,b,c,d,e,f}；E{10}； 16. 端点10：S；T{a,b,c,d,e,f}；E；

11.2.2 寻找平面线段交点的实现

一、数据结构

1、有关线段的数据结构：

typedef struct {

float x; float y; } POINT;

typedef struct {

POINT lp; POINT rp; } LINE; LINE BOOL

line[n]; b[n][n];

/* n条线段 */

/* n条线段的相交标志 */

/* 线段的左端点 */ /* 线段的右端点 */

/* 点的X坐标 */ /* 点的Y坐标 */

2、有关事件调度点的数据结构：

typedef struct {

float x; float y; int int int } HEAP; HEAP HEAP

p;

/* 事件调度点 */

/* 存放事件调度点的堆存储空间 */

tag;

/* 事件调度点的X坐标 */ /* 事件调度点的Y坐标 */

/* 事件调度点标志：=0 左端点,=1 右端点,=2 线段交点 */

line1; /* tag=0,1时的线段序号,tag=2时,交点左边高顺序线段序号*/ line2; /* tag=2时,交点左边低顺序线段序号*/

heap[3*n];

3、有关扫描线状态的数据结构：假定，线段按照序号顺序存放在数组line

struct tree {

int

line;

/* 线段序号 */

6

int high; /* 结点子树的高度 */ /* 左儿子结点 */ /* 右儿子结点 */

struct tree *lchild; struct tree *rchild; };

typedef struct tree TREE; TREE

*s;

/* 平衡二叉树的根结点指针 */

二、数据结构的有关操作

1、用最小堆存放事件调度点序列，使用下面两个堆的操作：

 void insert(HEAP heap,int &n,HEAP p)； 把事件调度点p插入堆中

 HEAP delete_min(HEAP heap,int &n)； 返回X坐标最小的点，并从堆中删去 很清楚，这两个操作以O(logn)时间维护堆的数据。

2、用平衡二叉树存放扫描线状态，使用下面维护树的衣服操作，及线段交点的计算：  TREE *insert_t(int line,TREE *s,float x)； 把序号为line的线段插入S中，返回指向 void delete_t(TREE *line,TREE *s)；  int above_t(TREE *line,TREE *s)；  int below_t(TREE *line,TREE *s)；

S中line的指针

从S中删去指针line所指向的线段

 TREE *search_t(int line,TREE *s,float x)； 在X坐标上检索序号为line的线段

返回当前X坐标上高于line的线段序号 返回当前X坐标上低于line的线段序号

判断并计算两条线段的交点

 BOOL inter_sec(int line1,int line2,POINT &p)； 三、有关计算式

1、确定线段在S中的插入位置

已知：欲插入S的线段左端点坐标(x0,y0)，x0x

S中被检索线段的两端点坐标(x1,y1)及(x2,y2) 求：S中的线段在x处的Y坐标值y

目的：y0与y比较，以确定被插入线段与S中的线段的x关系 由平面解析几何知，有直线方程：

yy1y2y1(xx1) x2x1 （11.2.1）

S中被检索线段的Y坐标值y为：

yy2y1(xx1)y1 x2x1 （11.2.2）

2、线段交点的计算 已知：线段两端点 求：线段交点

7

（11.2.1）式改写为

(y2y1)x(x2x1)y(x2x1)y1(y2y1)x10

令：

Ay2y1，B(x2x1) ，CAx1By1 （11.2.3）

则上述直线方程可写成：

AxByC0

（11.2.4）

若已知直线l1及l2的联立方程为：

A1xB1yC10 AxByC0222 （11.2.5）

解此联立方程，得：

xB1C2B2C1

A1B2A2B1yC1A2C2A1

A1B2A2B1（11.2.6）

由（11.2.6）式，可得两直线的交点坐标。

当交点坐标位于其中一条线段的两个端点坐标之外，则这两条线段没有交点。 当A1B2A2B10时，这两条线段平行，也没有交点。

四、求取平面上n条线段的交点集合步骤：

1. 按X坐标的非降顺序把线段两端点，放入最小堆heap中；T{}，L{}，S{}； 2. 如果heap为空，算法结束；否则转3；

3. 取下heap的最小元素于p，如果p是线段l的左端点，转4；否则，转6； 4. 按（11.2.2）式调用insert_t(l,S,x)操作，把线段l插入扫描线状态S中； 5. 令l1above_t(l,S)，l2below_t(l,S)； 若l与l1有交点，计算该交点q1， 若l与l2有交点，计算该交点q2，

把q1与q2插入heap；TT{q1,q2}；LL{{l,l1},{l,l2}}；转2； 6. 如果p是线段l的右端点，转7；否则，转8；

7. 令l1above_t(l,S)，l2below_t(l,S)，从S中删去l，

若l1与l2有交点，计算该交点q，把q插入heap；TT{q}；LL{{l1,l2}}；转2；

8. p是线段l1和l2的交点，l1在p的左边高于l2； 令l3above_t(l1,S)，l4below_t(l2,S)； 交换S中l1和l2的位置；

若l2与l3有交点，计算该交点q1， 若l1与l4有交点，计算该交点q2，

把q1与q2插入heap；TT{q1,q2}；LL{{l2,l3},{l1,l4}}；转2；

8

五、算法描述：

算法11.1 求取平面上n条线段的交点集合 输入：线段line[],线段数目n

输出：交点集合T[],相交的线段L[]个数k

1. void intersections(LINE line[],int n,POINT T[],KINE_PAIR L[],int &k) 2. {

3. int i,j,k,m,temp; 4. HEAP p,p1,heap[3*n]; 5. TREE *s,*snode; 6. LINE line_1,line_2; 7. BOOL b[n][n] = {FALSE}; 8. m = 0; k = 0; 9. s = new TREE;

10. s->lchild = s->rchild = NULL; /* 扫描线状态置为空*/ 11. for (i=0;i/* 线段的左右两端点插入堆中 */

12. p.x = line[i].lp.x; p.y = line[i].lp.y; 13. p.tag = 0; p.line1 = i; p.line2 = -1; 14. insert(heap,m,p);

/* 插入左端点,m在insert操作中递增 */

15. p.x = line[i].rp.x; p.y = line[i].rp.y; 16. p.tag = 1; p.line1 = i; p.line2 = -1; 17. insert(heap,m,p); 18. }

19. while (m>0) {

/* 插入右端点,m在insert操作中递增 */

/* m:最小堆元素计数器,k:线段交点计数器 */

20. p = delete_min(heap,m);/* 取事件调度点,m在delete_min中递减*/ 21. if (p.tag==0) {

/* 左端点处理 */

22. snode = insert_t(p.line1,s,p.x); 23. line_1 = above_t(snode,s); 24. line_2 = below_t(snode,s);

25. process(line_1,p.line1,T,L,k,heap,m,b); 26. process(p.line1,line_2,T,L,k,heap,m,b); 27. }

28. else if (p.tag ==1) {

/* 右端点处理 */

29. snode = search_t(p.line1,s,p.x); 30. line_1 = above_t(snode,s); 31. line_2 = below_t(snode,s); 32. delete_t(snode,s);

33. process(line_1,line_2,T,L,k,heap,m,b); 34. }

9

35. else { /* 交点处理 */

36. snode = search_t(p.line1,s,p.x); 37. line_1 = above(snode,s);

48. snode1 = search_t(p.line2,s,p,x); 39. line_2 = below(snode1,s);

40. process(line_1,p.line2,T,L,k,heap,m,b); 41. process(line_2,p.line1,T,L,k,heap,m,b);

42. temp = snode->line; snode->line = snode1->line; 43. snode1->line = temp; 44. } 45. } 46. }

1. void process(int line_h,int line_l,POINT T[],LINE_PAIR L[],int &k,

HEAP heap[],int &m,BOOL b[][])

2. {

3. POINT point; 4. HEAP p;

5. if (!(b[line_h][line_l])) { 6. b[line_h][line_l] = TRUE; 7. b[line_l][line_h] = TRUE; 9. p.x = point.x; 10. p.y = point.y; 11 p.tag = 2;

12. p.line1 = line_h; 13. p.line2 = line_l; 14. insert(heap,m,p); 15. T[k] = point;

/* 保存交点 */

/* 保存相交的线段编号 */

/* 置交点计算标志 */ /* 把交点插入堆中 */

/* 交点已计算?*/

8. if (inter_sec(line_h,line_l,point)) { /* 判断并计算交点 */

16. L[k].line1 = line_h; 17. L[k++].line2 = line_l; 18. } 19. } 20. }

六、复杂性分析

1、数据复杂性：

把n条线段的端点插入最小堆，需O(nlogn)时间。

10

如果交点个数为m，则要处理的事件调度点的数目为2nm。 对堆的每一个insert操作和delete_min操作，需O(log(2nm))。 对二叉树s的每一个操作，需O(logn)时间。 process中的inter_sec操作，需O(1)时间。

因此，每处理一个事件调度点，最多需O(log(2nm))时间。 所以总时间最多为O((2nm)log(2nm))。 2、空间复杂性：

存放事件调度点的空间，最多有2nm个事件调度点，需O(2nm)空间； 存放扫描线状态，最多有n条线段，需O(n)空间；

最后，有一个二维数组b来存放交点的处理标志，需O(n2)空间。 因此，算法所需要的工作单元所需要的空间为O(n2)。

11.3 凸壳问题

定义11.2 令S是平面上的一个点集，封闭S中所有顶点的最小凸多边形，称为S的凸壳，表示为CH(S)。CH(S)上的顶点，有时也叫做S的极点。

凸壳问题是计算几何中最重要的问题之一。它的提法是：给定平面上n个点的集合S，求S的凸壳CH(S)。凸壳问题也可以用几何扫描方法来求取。

11.3.1 凸壳问题的格雷厄姆（Graham）扫描法

一、凸壳问题

1、凸壳的定义

定义11.2 令S是平面上的一个点集，封闭S中所有顶点的最小凸多边形，称为S的凸壳，表示为CH(S)。CH(S)上的顶点，有时也叫做S的极点。

2、凸壳问题

给定平面上n个点的集合S，求S的凸壳CH(S)。 1、在平面点集S中，寻找Y坐标最小的点。把它称为p0。 2、以p0为源点，对所有点的坐标进行变换。

3、对变换后的所有点，以p0为源点，计算它们的极坐标幅角。

4、以幅角的非降顺序来排序S{p0}中的点，令排序过的点为T{p1,p2,,pn1}，其中，p1和pn1分别与p0构成最小与最大的幅角。 5、把点集T中的元素，作为事件调度点进行扫描。

6、用堆栈CS作为扫描过程中局部构成的半封闭凸多边形，把它作为扫描线状态维护。7、堆栈初始化为CS{pn1,p0}，其中，p0为栈顶元素。 8、按极坐标的幅角，从p1开始，到pn1为止进行扫描。

11

二、思想方法

9、扫描处理：

假定，在某一个时刻，堆栈内容为：

CS{pn1,p0,,pi,pj,pk}

其中，pk为栈顶元素，则栈中元素按顺序构成半封闭的凸多边形。 令pl是正在扫描的点，如果由pj、pk、pl所构成的路径是左转的，

则由pj、pk、pl形成的边是凸边，把pkpl作为凸多边形中的边加入进来，把pl 压入栈顶，把扫描线移到下一点；

如果由pj、pk、pl所构成的路径是右转的，

则由pj、pk、pl形成的边是凹边，pk不是凸壳的极点。把pk弹出栈顶，扫描线仍然停留在pl上。

在下一轮处理中，将由pi、pj、pl进行判断和作出处理。 例11.2 求图11.7所示点集的凸壳。

y p8 p6 p9 p10 p7 p4 p3 p11 p5 p1 p2 p12 p0 x

图11.7 以p0为源点、按极坐标幅角排序的点集

y p8 p6 p9 p10 p7 扫描线 p4 p3 p11 p5 p1 p2 p12 p0 x

图11.8 处理p5之后产生的凸壳

12

y p8 p6 p9 p10 p7 p4 p3 p11 p5 p1 p2 p12 p0 x

图11.9 处理p6之后产生的凸壳

y p8 p6 p9 p10 p7 p4 p3 p11 p5 p2 p1 p12 p0 x

图11.10 最后得到的凸壳

11.3.2 格雷厄姆扫描法的实现

一、算法步骤：

1. 求平面点集S中Y坐标最小的点p0； 2. 以p0为源点，变换S{p0}中所有点的坐标； 3. 以p0为源点，计算S{p0}中所有点的幅角；

4. 以幅角的非降顺序排序S{p0}中所有的点，令事件调度点T{p1,p2,,pn1}是排序过的数组；

5. 初始化堆栈：令CS[0]pn1，CS[1]p0；令堆栈指针sp1，事件调度点数组T的下标k0；

6. 如果kn1，转7；否则，算法结束；

7. 按（11.1.7）式计算CS[sp1]，CS[sp]，T[k]所构成的三角区符号D，若D0，

spsp1，CS[sp]T[k]，kk1；转6；否则，spsp1；转6；

二、数据结构：

typedef struct {

float

x;

/* X坐标 */

13

float float } SPOINT; POINT SPOINT POINT

y; ang; S[n]; T[n];

/* Y坐标 */ /* 极坐标的幅角 */ /* 平面点集 */

/* 按幅角的非降顺序排序的平面点集 */ /* 构成凸壳的点集 */

CS[n];

三。算法的实现：

算法11.2 求平面点集的凸壳 输入：平面点集S[],顶点个数n

输出：构成凸壳的极点CS[];极点个数sp

1. void convex_hull(POINT S[],POINT CS[],int n,int &sp) 2. {

3. int i,k; 4. float D; 5. SPOINT T[n]; 6. for (i=1;i/* S中Y坐标最小的点于S[0]*/

7. if ((S[i].y/* 以S[0] 为源点,变换S[i]的坐标于T[i] */

/* 求T[i]的幅角 */

10. T[i－1].x = S[i].x – S[0].x; T[i].y = S[i].y – S[0].y; 11. T[i－1].ang = atan(T[i－1].y,T[i－1].x); 12. }

13. sort(T,n－1);

/* 按T[i]幅角的非降顺序排序T[i] */

14. CS[0].x = T[n-2].x; CS[0].y = T[n-2].y; 15. CS[1].x = 0; CS[1].y = 0; sp = 1; k = 0; 16. while (k/* 求栈顶两点及扫描线上一点所构成的三角区符号 */

17. D = CS[sp-1].x*CS[sp].y + CS[sp].x*T[k].y + T[k].x*CS[sp-1].y 18. - CS[sp-1].y*CS[sp].x - CS[sp].y*T[k].x - T[k].y*CS[sp-1].x; 19. if (D>=0)

20. CS[++sp] = T[k++]; /* 若D0,T[k]压入栈顶，扫描线前移一点 */ 21. else sp--; 22. } 23. }

/* 否则,弹出栈顶元素 */

四、复杂性分析

1、数据复杂性：

14

第6～8行及9~12行，各需(n)时间； 第13行的排序操作，需O(nlogn)时间； 第16~22行的while循环，需(n)时间。 因此，算法的时间复杂性是O(nlogn)。 2、空间复杂性：

用于输入的平面点集、用于输出的凸壳极点需要(n)空间 事件调度点数组，需要(n)空间。

11.4 平面点集的直径问题

11.4.1 求取平面点集直径的思想方法

一、基本概念

1、平面点集的直径

令S是平面上的点集，S的直径定义为S中两点之间的最大距离，记为Diam(S) 2、平面点集的直径与凸壳的关系

凸壳是封闭S中所有顶点的最小凸多边形，点集S的直径等于它的凸壳上顶点的直径，即Diam(S)Diam(CH(S))，也即凸壳上任何两点之间的最大距离。 3、凸多边形的支撑线

定义11.3 P是凸多边形，P的支撑线是通过P的一个顶点的直线l，使得P完全位于l的一侧。

例：图11.11表示了凸多边形的一些支撑线。

l1 p2 l2 l3 p1 p3 l4 p6 p4 p5 l6 l5

图11.11 凸多边形的支撑线

4、凸多边形支撑线与凸多边形直径的关系：

定理11.1 凸多边形P的直径等于P的任何一对平行支撑线之间的最大距离。 例：图11.11中，l1与l6是任何一对平行支撑线中，距离最大的一对。它就是顶点对p1与p6之间的距离，也是凸多边形P的距离。

5、对跖对（antipodal pair）

定义11.4 通过两条平行支撑线的凸多边形P上的任何两顶点，叫做对跖对 例：在图11.11中，对应于平行支撑线l1与l6的对跖对是(p1,p6)，

对应于平行支撑线l2与l5的对跖对是(p2,p5)。

15

二、求平面点集直径的思想方法

1、思想方法

把计算平面点集凸壳的直径，转化为在凸壳上寻找所有的对跖对，然后，选择最大距离的对跖对。

2、顶点与边之间距离的确定 线段qr是凸多边形上的一条边，

点p是凸多边形上的一个顶点。

延伸线段qr的两个端点，使之成为直线l，

点p到线段qr的距离，定义为点p到直线l的距离，记为dist(q,r,p)。 假定，q,r,p三点的坐标分别为：(x1,y1)，(x2,y2)，(x0,y0)， 线段qr的直线方程为

AxByC0

点p到线段qr的距离，可由下式确定：

dist(q,r,p)|Ax0By0C|AB22 （11.1.8）

3、对跖对的求取

对某个mn，令点集p1,p2,,pm是凸壳上反时针顺序的所有顶点。

在以反时针顺序遍历凸壳上的顶点时，令pk是第一个距离线段pmp1最远的顶点，

pl是第一个距离线段p1p2最远的顶点，ps是第一个距离线段p2p3最远的顶点。 pk和pl之间（包括pk和pl）的所有顶点，都可以与p1构成对跖对。 pl和ps之间的顶点，lsm，都可以与p2构成对跖对

p 7 p 6 p 8 p 5 p 9 p 4 p 10 p 11 p 3 p 2 p 12 p 1

图11.12 寻找对跖对

4、平面点集直径的求取：

1）从p2开始，以反时针顺序遍历凸壳的顶点，寻找距离pmp1最远的顶点pk， 2）把顶点对(p1,pk)放入初始化为空的对跖对集合A中。

3）从pk开始，以反时针顺序遍历凸壳的顶点，寻找与p1p2的距离递增的顶点pj，一直到与p1p2的距离最远的顶点pl为止。

16

4）把所有这些顶点对(p1,pj)及(p1,pl)放入A中。

5）继续从pl开始，以反时针顺序遍历凸壳的顶点，寻找与p2p3的距离递增的顶点pt，一直到与p2p3的距离最远的顶点ps为止。并把(p2,pl)到(p2,ps)的所有顶点对放入A中。

6）这个过程一直继续，直到反时针遍历完凸壳的所有顶点，或者遇到线段pkpk1为止。 7）扫描A中的所有对跖对，找出距离最大的一对对跖对，它的距离就是凸壳的直径。

11.4.2 平面点集直径的求取

一、求平面点集直径问题的步骤：

1. 求点集S的凸壳CH(S){p1,p2,,pm}； 2. 令A{}，k2；

3. 寻找pk：如果dist(pm,p1,pk1)dist(pm,p1,pk)，则kk1，并继续第3步； 否则，转4； 4. 令i1，jk；

5. 如果ik并且jm，则AA{(pi,pj)}，转6；否则，转8；

6. 如果dist(pi,pi1,pj1)dist(pi,pi1,pj)，并且jm，转7；否则，ii1，转5； 7. AA{(pi,pj1)}，jj1，转6；

8. 求取A中距离最远的对跖对(pr,ps)，则(pr,ps)的距离就是平面点集S的直径。

二、数据结构：

typedef struct {

POINT POINT } ANTIPODAL; ANTIPODAL POINT POINT

A[n]; S[n];

/* 对跖对集合 */ /* 平面点集 */ /* 构成凸壳的点集 */

p1; p2;

/* 对跖对数据结构 */

CS[n];

三、算法的实现：

算法11.3 求平面点集S的直径 输入：平面点集S[],顶点个数n

输出：距离最远的对跖对a及其距离d,即点集S的直径

1. void diameter(POINT S[],int n,ANTIPODAL &a,float &d) 2. {

3. int i,j,k,m,s;

17

4. float x,y; 4. POINT CS[n]; 5. ANTIPODAL A[n];

6. convex_hull(S[],CS[],n,&m); 7. k = 2;

8. while (dist(CS[m],CS[1],CS[k+1])>(dist(CS[m],CS[1],CS[k])) 9. k = k + 1;

/* 寻找距离线段CS[m],CS[1]最远的顶点CS[k] */

/* i从1扫描到k,j从k扫描到m*/

10. i = 1; j = k; s = 0; 11. while ((i<=k)&&(j<=m)) {

12. A[s].p1 = CS[i]; A[s++].p2 = CS[j]; 13. while ((dist(CS[i],CS[i+1],CS[j+1])>=

(dist(CS[i],CS[i+1],CS[j])) && (j14. A[s].p1 = CS[i]; A[s++].p2 = CS[j+1]; j++; 15. } 16. i++; 17. }

18. x = A[0].p1.x – A[0].p2.x; y = A[0].p1.y – A[0].p2.y; 19. d = x * x + y * y; i = 0; 20. for (j=1;j/* 寻找距离最远的对跖对 */

21. x = A[j].p1.x – A[j].p2.x; y = A[j].p1.y – A[j].p2.y; 22. x = x * x + y * y; 23. if (d24. d = x; i = j; 25. } 26. }

27. a = CS[i]; d = sqrt(d); 28. }

/* 寻找对跖对CS[i],CS[j] */

四、复杂性分析

1、时间复杂性

第6行调用convex_hull函数计算点集S的凸壳，需O(nlogn)时间。 第8~17行寻找构成对跖对的CS[i]和CS[j]， 如果凸壳的顶点个数为m，没有包含平行边， 则判断两个顶点是否构成对跖对的次数恰好为m次。 如果包含平行边，平行边的数目不会超过m/2， 因此，判断的总次数不会超过3m/2O(n)。 所以，寻找对跖对的时间为O(n)。 对跖对的总个数也不会超过上述数目，

18

所以，第18行开始的寻找距离最远的对跖对，所需时间也是O(n)。 因此，算法的运行时间是O(nlogn)时间。 2、空间复杂性

存放输入点集所需要的空间为(n)，

需要存放的点集S的凸壳的顶点，不会超过n个， 需要存放的对跖对不会超过n对，

因此，用于存放凸壳的顶点及对跖对的工作空间为O(n)。

19