# 平面点线集三角剖分的扫描算法

T r ansactions of Beijing Instit ute o f T echnolog y V ol.24　N o.2F eb.2004

(北京理工大学信息科学技术学院计算机科学工程系,北京　100081)

Sweeping Algorithm for Triangulation of Plane Point -Line Set

ZHOU Pei-de

(Depar tment of Co mputer Science and Engineer ing ,School o f Infor matio n Science and T echno lo gy ,Beijing Instit ut e of

T echno lo gy ,Beijing 100081,China)

Abstract :Sw eeping alg orithm is presented fo r the tr iangulation of plane point -line set .T he algor ithm m akes use of the idea of plane sw eeping .When the sw eep -line reaches it ,the event -po int w ill be dealt w ith,viz.,the event-point is connected w ith so me points sw ept and thus the sw ept regions are triang ulated.When the sw eep-line r eaches the leftmost event-point,the point w ill be dealt w ith ,and the triang ulation of the plane point -line set is accom plished .It is prov ed in detail that the time co mplex ities o f the alg orithm is O (N lb N ),w here N is the sum of the num ber of points and the num ber of line-seg ment endpoints w ithin the point-line set.

Key words :debunching point-line set;triang ulation;plane sw eep;alg orithm;tim e co mplex ity 收稿日期:20030321

1　概念与算法思想

T中s1的上、下相邻线段的概念.设s1,s2,s3是平面上的3条线段,s1上存在一点a,过点a作垂线l,l与s2,s3分别交于b,c,并且b y

Fig.2　Fault b roken line

2　算法描述

130北京理工大学学报第24卷

l,m).边为s i或者s j(i,j=l,n,i≠j)端点的连线,端点与点p j(j=l,m)的连线,点p j与p k(j,k=l,m, j≠k)的连线.边与边之间不相交(顶点处相交除外).

1,s′2)∧(s L x

i R x∨

p x

i R(NI成立),修改E和F.连接s L或p与E的顶点(NI成立),修改E 和F.转步4或步5.

1,s′

2)∧(s L x

i L x∨

p x

i L x),则连接s L与s′i L或p与s′

i L(NI成立),修改

E和F.连接s L或p与E的顶点(NI成立),修改E 和F.转步4或步5.

3　正确性与复杂性

2所界定的区域均被三角剖分.由于事件点是由点p i和线段端点(i=l,m)构成的,所以算法无一遗漏地划分相关区域,即点线集凸壳所围区域.并且由算法的执行过程,可知每个三角形的顶点都是点线集中的点或线段端点,而三角形的边不是点线集中线段就是点线集中线段端点的连线,或者端点与点、点与点的连线.因此算法正确地产生了所需要的三角剖分.

131

第2期周培德:平面点线集三角剖分的扫描算法

i =1

m i =N ,1≤m i ≤n -1.如图3所示

.

Fig .3　Illu strative diagram for a proof of complexity

2m k +m k -1+…+m 2+(m k +m k -1+…+m 1)lb N +

2[(m k -1+m k -2+…+m 1)-k ]=N -m 1+N lb N +2[N -m k -k ]≤

3N +N lb N =O (N lb N ).

4　应用举例

[1]　L o S H.Delaunay t riang ulat ion o f non-co nvex pla nar

do mains [J ].Inter nat ional Jo urnal for N umerical M etho ds in Engineer ing ,1989,28:2695-2707.[2]　闵卫东,唐泽圣.二维任意域内点集的Delaunay 三角

W eido ng ,

T ang

Zesheng .

T he

D elav na y

tr iang ulatio n of a po int set w ithin an arbit rar y 2D domain [J].Chinese Jo ur nal of Computers,1995,18(5):357-364.(in Chinese)

[3]　周晓云,刘慎权.实现约束D elaunay 三角剖分的健壮

Journal o f Co mputer s ,1996,19(8):615-624.(in

Chinese)

[4]　周培德.平面线段集三角剖分的算法[J].计算机工程

Zhou P eide .A lg or ithms for the tr iangulatio n of plane line-segment stes [J ].

Computer Eng ineer ing &

Science ,2003,25(1):20-22.(in Chinese )

[5]　周培德.计算几何[M ].北京:清华大学出版社,2000.

Zhou P eide .Computatio nal geo metr y [M ].Beijing :T sing hua U niver sity P ress,2000.(in Chinese)[6]　周培德.算法设计与分析[M ].北京:机械工业出版

Zhou Peide .T he desig n and analysis o f alg or ithms

[M ].Beijing :China M achine Pr ess,1992.(in

Chinese )

132