三角网表达及求交是三维表面模型建模的基础，也是地质工程、科学可视化以及模型分析的关键算法之一^{[1, 2]}。GIS研究对象向三维以及时空维的扩展，不仅导致了数据量的激增^[3]，也导致了对象表达结构的复杂性。GIS对象表达结构的复杂性，不仅使得在空间关系计算过程中对象类型及求交条件判断模式的复杂，也增加了对诸如空间、边界等复杂的空间约束^[4]判断的难度，因而极大地影响了现有矢量GIS的效率。伴随着GIS研究对象向三维以及时空维的扩展，三角网求交的复杂度也随之增加。在三维动态场景中，三角网中对象的维度、形态和结构均存在显著的变化^[5]。基于欧氏几何或计算几何发展而来的三角网求交算法需要对其相对位置关系进行预判断，且在处理不同维度三角网时，需要对线、面进行分别处理，导致了其对动态变化的三角网求交支撑不足^{[6, 7]}。以文献^[8]算法为代表的标量法在平面距离计算及交线位置判断上的计算相对复杂，在大规模环境中时间耗费较多。文献^[9]的矢量法利用行列式符号的几何意义来判断三角形的关系而后求交，计算过程中必须根据相关情况进行复杂的判断，导致程序结构复杂，适应性不强。

几何代数是以代数语言进行几何对象表达、构造与运算的数学系统，被认为是有效连接几何与代数，实现几何计算的数学语言^[10]。共形几何代数(conformal geometric algebra，CGA)基于协变视角引入了基准原点和无穷远点，使得分别基于外积和内积的形体表达和几何度量都具有明确的几何意义^[11]。通过定义几何代数运算空间，可实现高维空间中不依赖于坐标的几何计算，前期研究表明几何代数可用于多维空间对象的统一表达、建模与复杂对象间的空间关系分析^{[12, 13, 14]}，且基于其设计的算法具有较强的高维拓展性^[15]。本文针对三角网求交中三角形空间关系判定及点、线、面等不同几何对象统一求交问题，从代数表达与关系运算相结合的角度，基于几何代数中交并关系运算的meet算子构建空间关系判断算子，为三角网表达结构的动态构建及各维度组分的统一求解提供基础，进而实现多维统一三角网求交的几何代数算法。

基于内积和外积进行代数空间构造及几何对象表达，基于几何代数多重向量(multivector)可实现多维几何对象的整合表达。在几何代数中，基于外积表达的几何对象维度与Grassmann维度具有一致性，可以实现不同维度对象的构造与相互转化^[10]。多重向量则为不同类型、不同维度几何对象的描述和存储提供了高维可拓展性。几何代数自身的坐标无关性与维度无关性使其所表达的几何特征是几何对象自身内蕴的几何特征，计算获得的几何关系也是各几何对象间不依赖坐标的相对关系^{[11, 16]}。这为几何对象的自适应表达、关系判断与关系计算提供了有利前提。CGA表达中包含有如方向、位置、值大小等几何语义信息，可通过直观的算子运算直接判断对象间相离、相交、包含等拓扑关系。表 1给出了CGA中常用blade的分类及其所包含的几何特征及其计算方法^[15]。

表 1 blade分类及其几何特征 Tab. 1 Blades and their geometric characteristics

blade分类	例子	标准形式X	方向关系	位置关系	距离关系
rounds	点、圆环、球面、点对		-(e∞」X)∧e∞
flats	线、平面	X=e0∧A′k∧e∞	e∞」X		none
tangent blades	切向量	X=e0A′k	-(e∞」X)∧e∞	e∞」X	0
direction blades	方向向量	X=A′ke∞	X	none	none
注：A′k为欧氏表达；」为左缩进运算；为grade involution运算，且有=(－1)kXk

表选项

根据CGA中blade的表达，并结合前期研究中所构造的基于CGA的三维空间数据模型^[12]，可以构造三角网的表达模式如图 1所示。首先构建多重向量集合MV_i。在MV_i集合中任意一个对象均为构成该三角网的特定三角形T_i，采用外积构造点、线、面对象，并利用其边界范围将其约束为点、线段与三角形。利用CGA中几何对象维度与Grassmann维度的一致性，实现点、线段与三角形的层次组织。在三角网的表达中，点、线段与三角形均用blade表达，且依据其层次关系组合形成最终的三角网多重向量表达。不仅在维度结构上具有简明性，也为三角网的统一表达与空间关系计算提供了独立、完备的数据组织与数据结构基础。

几何代数算子的多维统一性使其可以直接用于处理多维对象，而无需根据对象维度进行分别处理^[17]，从而可构建简明、清晰、多维统一的三角网快速求交算法。基于CGA几何对象表达的多维统一性和meet算子构建三角网自适应求交算法(图 1)，通过对表征两三角网的多重向量直接应用meet算子实现对多重向量中所包含的各几何对象的分别求交。对于基本几何对象间交并关系的求解，如点、线、平面、圆环、球面等一般blade，可直接基于meet算子进行运算；对于求解含固定边界几何对象间交并关系，如多边形、多面体对象，除了先基于meet算子进行求交判断外，还需借助对象表达中所蕴含的丰富的几何属性特征，并定义一系列具有统一结构的关系判断算子，去除无效结果。最后将meet求解结果重新投影回欧氏空间，可设计相应的语法解析器对运算结果加以解析，并转换成对应几何对象，形成三角网求交的最终算法流程。

图 1 基于几何代数三角网求交流程 Fig. 1 Calculation flow of triangulation intersection based on geometric algebra

图选项

不同几何对象的相交关系会随着对象类型和位置关系的变化而变化。传统欧氏几何中需要对不同维度对象各种相交情况分别进行处理，导致时变对象的求交计算较为复杂，对动态空间关系计算的支撑不足。在几何代数中，不同几何对象间所共有的最大子空间可以通过meet算子获得。由于meet运算的多维统一性，使其可以同时处理点、线、面以及其他各类blade表达的几何对象间的相交运算^[17]。meet运算的结果为多重向量，且其运算结果的几何对象类型仅与参与meet运算的几何对象相关，而与维度和坐标系统无关。meet算子计算结果所具有的自适应性，有助于实现利用单一算子实现不同几何对象相交关系的统一求解。

给定任意两blade A和B，两者间的meet运算M=A∩B满足下式

点击浏览公式

点击浏览公式

点击浏览公式

表 2 基于meet算子的基本几何对象相交关系求解 Tab. 2 The solutions of intersection relations among basic geometric objects based on meet operators

对象 A和B	meet 求解公式	相交关系
		两直线相交 两直线不相交
		直线与平面交于一点 直线在平面上 直线与平面不相交
		平面与平面相交 两平面平行

表选项

meet算子对于求解A=a₁∧a₂∧…∧a_k形式的blade之间的交集简单有效，但对于由多个blade的加和构成的k-blade间的meet运算，需要基于join(并)和meet的关系对其进行拆分和变换^{[10, 19]}。鉴于meet运算的可拆分性，可以通过将blade对象分解成线性无关的几个支撑向量以简化运算。对于k-blade B，其因子分解就是要找到k个线性不相关的支撑向量f_i，使得B=βf₁∧f₂∧…∧f_k。使用投影算子q_i=(p_i」B^-1)」B搜寻B中k个相互独立的分解因子。设计meet算子快速求解算法，其基本流程为：

(1) 先将“测试向量”p_i投影到二维平面B上；

(2) 用p_i」B^-1计算出p_i在B中投影的正交补余；

(3) 据公式q_i=(p_i」B^-1)」B求解p_i」B^-1顺时针旋转90度的正交投影，q_i即为所求支撑向量；

(4) 循环直至找到k个支撑向量。

由于对象分解过程具有可加和性和可逆性，且分解得到的q_i线性不相关，可用于对象间meet的快速运算。为快速求得meet算子结果的维度，可引入delta积运算，其几何意义为两对象间的并集减交集^{[19, 20]}，存在

点击浏览公式

给定初始交积M=1、并积J=I_n，对于k-bladeA与B，计算其delta积在空间I_AB中的补集S=(AΔB)^*，并将S分解为线性无关的k个部分S_i；对于每个S_i计算其投影p_i，如果p_i非零，则通过M=M∧p_i扩充meet，直到M的维度与所求得meet的维度相等。

在复杂三角网对象求交中，对象间空间关系判断是进行求交对象筛选和处理的基础。在三角形求交过程中，主要需考虑不同线段、线段与三角形以及点与三角形之间的关系判断。为此，基于三角形及其相关几何对象的CGA表达，通过构造相应的判断算子进行上述对象的空间关系判断。其计算过程如图 2所示。

图 2 线段、三角形、点的位置关系判断 Fig. 2 Location relations judgment between segments,triangles and points

图选项

计算线段R₁及其端点p₁与线段R₂两端点所构成向量间的外积2-blade B₁=v₃∧v₁、B₂=v₃∧v₂，同理可求得由线段R₂及R₁端点所构成向量间外积B₃、B₄。构建平面上线段关系判断算子：O_seg－seg=(dir(B₁)==dir(B₂))‖(dir(B₃)==dir(B₄))，当O_seg－seg为true时，线段不交，否则线段相交。

构建由线段R的顶点q₁到三角形的三个顶点所构成向量的外积3-blade Tr₁=v₁∧v₂∧v₃，同理可得到由顶点q₂与三角形顶点所构成向量的外积Tr₂。构建线段与三角形的关系判断算子：O_seg－tri=(dir(Tr₁)==dir(Tr₂))，当O_seg－tri为true时，二者不交，否则线段与三角形相交。

构建由三角形各顶点指向待求点的向量，按一定的方向计算三角形边同各向量的外积：B₁=v₁₂∧v₁₀、B₂=v₂₃∧v₂₀、B₃=v₃₁∧v₃₀。构建点与三角形的关系判断算子：O_pt－tri=(dir(B₁)≥0&&dir(B₂)≥0&&dir(B₃)≥0)，当O_pt－tri为true时，点在三角形内部或边界，否则点在三角形外部。

不失一般性，据文献^[17]构建的基于几何代数的对象表达模型，给定两三角形T₁、T₂，其共形几何代数表达为

点击浏览公式

上述三角形的多重向量表达中，已同时包含有各三角形中线段和面对象的几何代数表达，其meet的求解过程为

点击浏览公式

点击浏览公式

基于上述形式化表达，利用三角形求交的空间关系判定方法，构造相应的判定算子对其空间关系进行判定，进而获得三角形在共面、异面等情况下，其中各要素的相交情况，然后将求交结果逆向回溯，由交点构建线段，即为所求交线结果。

其算法流程如图 3所示。首先利用meet算子进行三角形所在平面间相交关系的预判断，即M=(T₁∩T₂)。由于当M²＜0时，T₁与T₂不交，因此，可筛选出所有M²＜0(即不满足相交条件)的三角形，对所有可能满足相交条件的三角形进行空间关系的判断。构造由三角形T₁任一顶点A₁、B₁、C₁到三角形T₂顶点A₂、B₂、C₂所构成向量的外积3-blade Vol=A₂∧B₂∧C₂值是否为零，筛选出共面相交的情况。对于异面相交的三角形，计算三角形各边与另一三角形平面的meet。共面相交的三角形，则需要遍历计算两三角形边与边的meet，并通过交点、交线与三角形空间位置关系判断算子筛选出落在三角形内部或边界上的对象。

图 3 三角形求交流程示意 Fig. 3 The triangle intersection process

图选项

对上述算法流程的求解步骤为：

输入：待求交的两三角网T₁、T₂。

输出：两三角网交线、交点等几何对象V_out。

(1) 对T₁、T₂进行几何代数编码，形成多重向量表达MV_T1、MV_T2；

(2) 顺序提取MV_T1、MV_T2中三角形Π₁、Π₂，对其所在平面求meet，并进行三角形相交与共面的判断；

(3) 对Π₁、Π₂中各边求交，判断其相交情况；

(4) 对所求交点、交线与三角形关系进行判断，当交点、交线在三角形内时，保留结果；

(5) 依次遍历三角网中各三角形，直至所有三角形求交完成；

(6) 解析计算结果，转化为对应欧氏几何对象输出或可视化。

以南极冰盖时空演化^[21]的三维表面模型求交为例进行算法验证，选用33800Ka BP、33550Ka BP、33400Ka BP、33300Ka BP、33200Ka BP 5个时间节点的南极冰盖三角网曲面模拟数据作为案例数据，数据结点及三角网个数信息见表 3。利用几何代数对三角形的统一表达与运算，结合相关的运算与判断算子，设计三角网求交的数据存储结构和算法。首先对三角网格曲面数据进行共形空间转换与维度映射，实现三角格网的几何代数表达与存储；然后利用空间三角形的几何代数求交方法，基于meet算子和关系判断算子O_seg－seg、O_seg－tri、O_pt－tri进行相交结果的筛选与位置关系判断，并获取相应的交点与交线段，最后求得两个时期冰盖表面的曲面交线。结果显示本文算法提取出的交线能够清晰反映某一时刻冰盖曲面相对原始冰盖变化的空间结构与位置，可为地质地形建模与分析提供可行的思路与方法(图 4)。

图 4 本文算法求得的南极冰盖表面三角网交线结果 Fig. 4 The triangulation intersection of Antarctic ice sheet based on CGA algorithm

图选项

对上述三角网交线结果进行分析易知其中含有大量的重复交线，这些冗余交线会影响后期交线拓扑的构造效率。冗余交线主要产生于如下3种情况：① 退化交线(交点)，例如当一三角形顶点与另一三角形相切(接)时，交线段退化为交点，此交点必为其邻接三角形交线的顶点；② 切交线，例如当三角形一边切另一三角形面时，该三角形的邻接三角形必求解出相同的切交线；③ 接交线，例如当两个三角形的边部分或整体重合时，该求解结果将会在其邻接三角形中重复出现。情况①中的点由于不参与拓扑构建可直接删除，情况②与情况③中需要保留一条交线用于构造交线拓扑。基于上述考虑，可分别为线线关系判断算子O_seg-seg和线面关系判断算子O_seg－tri添加判断条件B_i==0,i=1,…,4和O_seg－segi==true,i=1,2,3，标记出线线相接和线面相接的情况，对退化交线加以筛除，式中B_i为线段端点构成的2-blade，seg_i指代三角形tri的第i条边。

分别运用MÖller标量法、Guigue&Devillers矢量法和本文算法(CGA算法)按时间序对上述三角网数据两两求交，统计出交线数目及各算法运行时间，对本文算法的准确性和效率加以验证。最终交线的统计结果如表 4所示。由于基于CGA的三角形求交算法去除了一定量的冗余交线，其求得的交线总数均小于另两算法，减去冗余交线后，三算法求得的有效交线数目一致，表明了本算法求解结果的准确性与有效性。从计算效率上看(图 5)，本方法较MÖller算法略快，但慢于Guigue&Devillers算法。其主要原因在于，本文实现的CGA算法是将几何对象由三维欧氏空间投影到五维空间后，使用数值运算而非逻辑位运算进行几何代数计算的求解，导致了内积、外积以及meet算子等基本几何代数运算仍然依赖于加、减、乘、除等数值运算。通过基于逻辑位运算优化的几何代数引擎的利用^[22]，可进一步大幅提升运算效率。而几何代数对象表达与运算的统一性，及其算法的结构简明性与自适应性，也为基于几何代数的并行计算方法提供了便利^[23]。

图 5 三角形求交算法效率对比 Fig. 5 Efficiency comparisons of the three triangulation intersection algorithms

图选项

三角形是三角网格曲面、四面体格网、单纯形剖分等三维矢量模型构建的基本单元，三角形求交运算是上述模型空间拓扑关系运算的基础。空间对象的相交、距离关系的判断是空间拓扑分析的基础，几何代数通过定义相应的运算空间实现多维对象的统一表达与计算。本文利用几何代数多维统一表达与运算的优势，设计了三角形等基本对象的统一表达；基于meet算子维度统一与对象无关特性，构建统一的三角形求交运算流程；并设计相应的关系判断算子实现计算过程中对象的筛选与判断。

在三角形的求交过程中存在三角形退化为线段、三角形相接、三角形相切等多种临界与奇异情况，在所选的两类传统对比算法中，均存在人为设定的相交准则，使得计算流程存在一定的定制化，而对不同维度、不同对象缺乏自适应性。本文算法基于统一的多重向量表达及灵活的关系判断算子可根据应用需要合理配制相交准则，对动态场景下的时变对象间相交关系的计算具有更强的自适应性。基于南极冰盖曲面网格数据的案例表明，本文提出的基于几何代数的三角形快速求交方法，可有效支撑三角网的求交运算，且逻辑结构清晰，运算简洁高效，可为其他复杂几何对象间建模表达与空间分析统一求解提供借鉴。

支持复杂对象与现象的动态化表达、建模与模拟是GIS发展的必然趋势^[24]。建立几何—拓扑—语义一致的且可有效支撑地学分析的地理格网与空间分析模型是实现上述目标的重要途径^[25]。基于几何代数的三角网参数化表达在融入对象的几何、拓扑特征的同时可直接支撑几何运算，并具有对象和维度的自适应性。除meet算子外，大部分的几何代数算子均具有类似的多维统一和自适应特性，因此，基于几何代数算子设计对象和维度无关的空间关系计算算法，将可为多维统一分析与计算提供了新的理论与方法参考。未来主要的研究拓展包括：① 研究可支撑复杂对象的几何代数表达方法，实现地理场景中不规则边界形体数据的语义结构与拓扑特性分析；② 基于几何代数算法流程的一致性与逻辑结构的简洁性，构建并行化分析算法以支撑大规模复杂场景及海量数据分析；③ 将算法向复杂、高维对象扩展，设计几何与语义统一的空间关系计算算法，建立具有以维度融合为特征的GIS空间分析体系。