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

L1=[(x3-x2)(y3-y2)-(x-x2)(y-y2)] AL2=[(x1-x3)(y1-y3)-(x-x3)(y-y3)] AL3=[(x2-x1)(y2-y1)-(x-x1)(y-y1)

]A

L1=(x3-x2)(y3-y2)-(x-x2)(y-y2)

(2)

212　点在三角形中的判断

参看图3,并设在三角形顶点逆时针排列,则当P在三角形中时,必有其所有的面积坐标大于零,即

L1

>0;L2>0;L3>0　　而若P不在三角形中,则至少一个面积坐标小于零。如图4所示,P在三角形之外,且为V2V3的外侧,则有

L1<0;L2>0;L3>0

(3)　L2=(x1-x3)(y1-y3)-(x-x3)(y-y3)

L3=(x2-x1)(y2-y1)-(x-x1)(y-y1　　另外,该算法还取决于初始三角形的位置,这可通过建立三角形索引来解决。

3　动态三角形拓扑关系的创建与维护

事实上,无论是构网过程中,还是在以后的应用中,三角形拓扑关系都扮演着相当重要的角色,而在构网过程中,要解决的问题是如何动态地创建和更新维护三角形的拓扑关系。

以下为叙述方便,给出几个定义及约定。

定义一:三角形数据结构定义如下(仅为本文定义)

　　typedefstructtagT{longA[3:三角形顶点按逆时针排列,三角形边的

　图3　三角形面积坐标　　　　　图4　P　　事实上,向。,利用面积坐标的这一特性,。图5。

0、1、2,即V[0]V[1]为第0号边,V[1]V[2]为第1号边,V[2]V[3]为第2号边,并边号可循环,即当边号i=i-1≤0时,i=2,当i=i+1≥2时,i=0。

约定二:三角形表示方法,任意三角形i,其三顶点表示为i.V[j](j=0,1,2),相邻三角形为i.A[j](j=0,1,2)。

定义二:基三角形,当插入一点P时,包含P的三角形为基三角形,用bt表示。

定义三:分裂三角形,由P点与基三角形顶点

图5　点在三角形中查找

连接而成的三角形,用st表示。

定义四:拓扑三角形,任意三角形三条边的相邻三个三角形为该三角形的拓扑三角形,用tt表示。

以上三种三角形存在着如下的数量关系:当P点落在三角形中时,基三角形数=1,分裂三角形数=3,基三角形的拓扑三角形数=3;当P落在三角形某一边上时,基三角形数=2,分裂三角形数=4,基三角形的拓扑三角形数=3或4。图6表示了上述三种三角形。

约定三:对分裂三角形进行编号和组成时,由基三角形的第一顶点开始,按逆时针方向进行,并依次称为第一、第二、第三分裂三角形。

定义五:第四顶点,任何一分裂三角形与其拓扑三角形组成具有公共边的四边形,在拓扑三角形中除公共边顶点之外的另一顶点,用Q表示,当前插

设初始三角形号为△1,计算P在△1的面积坐标,其符号情况为(上标为三角形号):

L1<0;L2>0;L3>0

1

1

1

　　取小于零的面积坐标对应边(图中为23边)的邻面三角形△2,则有

L>0;L<0;L>0

21

22

23

　　计算P在△5中的面积坐标

L>0;L>0;L>0

51

52

53

　　即P的三个面积坐标值都大于零,故P在△5中。

实际工作中,仅关心的是面积坐标的正负情况,故当三角形顶点以逆时针方向排列时,式(2)的分母

A恒大于零,因而式(2)可简化为