34　　　　　　　　　　　　　　　中　国　公　路　学　报　　　　　　　　　　　　　　2000年

当P落在某一三角形的边上时,基三角形为

bt1、bt2,增加两临时记录tmp1和tmp2来记录bt1和

则第一、第二分裂三角形编号为bt1、bt2信息(图8)。

第四分裂三角形编号为nt+1、bt2,第三、nt+2,依约定三,则可组成分裂三角形及其拓扑三角形如表2

所示。

图6　三种三角形定义

入点用P表示。

311　插点时拓扑组成与更新

设已存在的三角网中的三角形数为nt,则在当前三角网中插入一点P时,无论P是落在三角形中还是落在三角形边上(区域边界除外),三角形数目总是增加两个,因而分裂三角形及其拓扑组成有如下规律:

当P落在三角形中时,

设基三角形号为bt(图7),另增加一临时记录tmp,用以记录基三角形bt未修改前的信息。把第一分裂三角形st1编号为原基三角形号bt,第二、第三分裂三角形st2、st3编号为nt+1、nt+2,依约定三和图7,其拓扑三角形如表1所示。

图8　P表2V]

112=bt2st3=nt+1st4=nt+2

p1.V[0]tmp1.V[1]tmp2.V[0]tmp2.V[1]

V[1]tmp1.V[1]tmp1.V[2]tmp2.V[1]tmp2.V[2]

V[2]PPPP

A[0]tmp1.A[0]tmp1.A[1]tmp2.A[0]tmp2.A[1]

A[1]A[2]bt2nt+1nt+2bt1

nt+2bt1bt2nt+1

拓扑组成

　　原基三角形的拓扑三角形的拓扑信息修改同点在三角形中。

312　LOP过程中的拓扑更新

如图9所示,以第一分裂三角形为例说明该过程。按311中所述,st1、st2结构如表3所示,设立临时变量tmp1和tmp2用以记录优化前st1、tt1的信息。经过LOP优化后,st1、tt1的结构组成如表4所示。

表3　优化前st1与st2的结构

三角形编号

st1tt1

V[0]

图7　P点落在三角形中

表1　分裂三角形和拓扑三角形的组成

三角形编号

V[0]

st1=btst2=nt+1st3=nt+2

tmp.V[0]tmp.V[1]tmp.V[2]

V[1]tmp.V[1]tmp.V[2]tmp.V[0]

V[2]PPP

A[0]tmp.A[0]tmp.A[1]tmp.A[2]

A[1]A[2]nt+2nt+1nt+2bt

btnt+1

顶点组成拓扑组成

顶点组成

V[1]

V[2]P

A[0]tt1at1

拓扑组成

A[1]st2st1

A[2]st3at2

24

33

2

　　最后修改原基三角形的拓扑三角形的拓扑信息。由于此时原基三角形信息已改变,故有关原基三角形信息应由变量tmp中取得,修改方法为:

若(tmp.A[0]).A[j]=bt,则(tmp.A[0]).A[j]=bt.(j=0,1,2);

若(tmp.A[1]).A[j]=bt,则(tmp.A[1]).A[j]=nt+1.(j=0,1,2);

若(tmp.A[2]).A[j]=bt,则(tmp.A[2]).A[j]=nt+2.(j=0,1,2)。

表4　优化后st1与tt1的结构

三角形编号

st1tt1

V[0]

顶点组成

V[1]

V[2]P

A[0]at1st1

拓扑组成

A[1]st2st3

A[2]tt1at2

44

3

P

2

　　下面由表3和表4的演变过程来分析其拓扑变化规律。

在LOP优化前后,三角形顶点变化及拓扑变化