第2期　　　　　　　　刘学军,等:三角网数字地面模型快速构建算法研究　　　　　　　　　　　　35

处的拓扑三角形拓扑关系。依312节方法有:

如果(tm

p1.A[is-1]).A[j]=tt1,(j=0,1,2),则

(tmp1.A[is-1]).A[j]=st1.;

如果(tmp2.A[it-1]).A[j]=st1,(j=0,1,2),则

(tmp2.A[it-1]).A[j]=tt1.

图9　LOP拓扑更新过程

与公共边在两三角形中的位置序号密切相关。为此,首先求出公共边23在st1、tt1中的位置序号,设为is及it,本例中is=0,it=1;由于边的位置序号由0开始,故其值也可看作是顶点数组V或拓扑数组A的下标。

31211　三角形组成

若以公共边位置序号作为顶点数组V的下标,则交换后三角形顶点变化正好处于该下标处。对分裂三角形st1,是用第四顶点Q(4)值交换is位置的原有值,即st1.V[is]=Q。而拓扑三角形tt1则是用加入点P取代位置it的原有值,即tt1.V[it]=P。31212　拓扑变化

若把公共边位置序号kA的下标,k-1和k处,4　空外接圆检测公式(数值计算问题)

在Delaunay三角网中,每一个三角形都要经过空外接圆检测。在算法中,这一过程是恒定的,它具有累计性。当数据较大,它在整个程序执行中所占用的CPU时间不容忽视。目前常见的做法是计算分裂三角形的外接圆圆心及半径,然后利用第四顶点到圆心距离和外接圆的半径关系进行判定。这一过程中要多次执行三角函数、开方、除法、平方等运算,,则是比较低的。。

,设分裂三角形st为△V1V2V3,其V2V3P,第四顶点为P。点P与△V1V2V3外接圆关系为

分裂三角形0)

st1.A[is-]st1.A[2]=tt1

st1.A[is]=at1=tmp2.A[it-

1]

　　拓扑三角形tt1(it=1)

tt1.A[it-1]=st1

tt1.A[it]=tmp1.A[is-

1]=st3

图10　空外接圆的简化处理

31213　拓扑三角形的拓扑变化

>0

-=0Β′

<0

表5列出了LOP前后st1、tt1拓扑三角形的拓扑信息变化情况。

表5　st1与tt1拓扑三角形的拓扑信息变化

LOP前

A[0]

st1.A[0]=tt1st1.A[1]=st2st1.A[2]=st3tt1.A[0]=at1tt1.A[1]=st1tt1.A[2]=at2

at1tt2A[1]st1st3st2st2

A[2]at2st1tt3

A[0]tst1tt2(P在圆外)(P在圆上)(P在圆内)

LOP后

A[1]st3st3st2st2

A[2]at2st1tt3

　　考虑Β′=Β,由于Β′+Α=180°,Β′=180°-Α

故有　-tgΑ=tgΒ

则有空外接圆检测函数f

>1　(P在圆外)

f=-tgΑ tg=1　(P在圆上)

<1　(P在圆内)

…

tt1tt1

…

st3

…

tt1tt1

…

st3

…………

　　依表中的变化不难看出,拓扑三角形的拓扑信

息变化之处也是在公共边k的前一位置和本身处。由于本身处的两个三角形即为LOP三角形,其相应拓扑关系在LOP时已改变,故仅要改变的是k-1

　　由三角函数关系和图10不难看出f的坐标公式

(4)f=-(△x13△x12-△y13△y12)(△yp3△xp2-△xp3△yp2)

△xab=xa-xb;△yab=ya-yb　(a=1,2,3,p;b=1,2,3,p)

上式f的执行效率比计算圆半径、圆心坐标及距离的效率高得多。