基于庞卡莱代数的TEN三维GIS模型研究
2017-02-09马玉梅
马玉梅，马 超
(1.新疆维吾尔自治区第二测绘院，新疆 乌鲁木齐 830002;2.东北师范大学 地理科学学院，吉林 长春 130024)
基于庞卡莱代数的TEN三维GIS模型研究
马玉梅1，马 超2
(1.新疆维吾尔自治区第二测绘院，新疆 乌鲁木齐 830002;2.东北师范大学 地理科学学院，吉林 长春 130024)
不规则四面体网具有结构简单、易于扩展的特性。借助于庞卡莱代数，应用边界表示理论重新描述了TEN模型。与传统几何结构模型相比，这种模型具有表达简单、易于计算的特点。同时，提出基于庞卡莱代数的TEN合并和删除运算以及拓扑一致性检查。在VC++环境下，对TEN模型的合并和删除运算进行编程与实现。实验表明，基于庞卡莱代数的TEN模型可以有效建立动态实体模型，能够实时建立拓扑关系，适合于表达不规则矿体等动态变化的三维实体。
庞卡莱代数；三维地理信息系统；不规则四面体格网；拓扑一致性；边界表达法
当前的GIS三维模型多是依赖现有的三维软件进行建模[1-2]，这种方法虽然快速有效，但在导入三维GIS软件中进行空间分析会受到一定程度限制，原因是对模型的数据结构一无所知，导致三维模型只能进行可视化表达，无法进行自定义分析。因此，这种模型并非真正意义上的三维模型，真正的GIS三维模型必须是从底层开发的模型。由于模型应用目的不同，各国学者也提出相应的三维模型，例如，我国学者吴立新提出的面模型、体模型和混合模型[3]；Abdul-Rahman提出的三维阵列模型、八叉树模型、构造性实体几何模型和三维TIN模型[4]；此外，还有WANG YANBING提出的地理模型、地质模型、集成模型[5]。无论三维模型如何分类，都不可能完美解决地学GIS中的所有问题，因此试图建立一种万能模型是不可行的，模型应该是与应用要求相匹配。虽然不规则四面体网(irregular tetrahedral network，TEN)已被广泛建模，其拓扑结构也被多次表达[6]，但建模没有统一的定论，建立的模型缺乏动态编辑，一致性检验缺乏，因此，本文基于庞卡莱代数(Poincaré algebra)提出了三维GIS中的TEN的建模方法及其拓扑一致性检查要求，并实现了TEN的合并、删除运算及DBMS连接。
1 庞卡莱TEN模型
1.1 拓扑结构
1.2 边界表示
如式(1)所示，TEN可用向量形式描述各个维度单纯形，0维单纯形表示为S0=
(1)
根据庞卡莱对边界的定义[8]，TEN的边界可用代数和形式进行描述，如果n维单纯形Sn的边界用∂Sn表示，那么∂Sn的表达为
(2)
2 庞卡莱TEN运算
基于庞卡莱代数的3D TEN明显特点是TEN可以实时动态更新，空间实体由有限个TEN组成，在某些TEN发生诸如合并、删除变化后，庞卡莱代数运算可以重建每次变化的拓扑关系，这与以往单纯的基于几何的TEN模型是完全不同的。基于庞卡莱代数的TEN拓扑检查伴随着实体的存在而存在，这种检查体现了构成实体的各个TEN与实体的拓扑统一。
2.1 TEN合并与删除
正如前述，TEN实体动态变化主要是合并和删除，式(2)描述了庞卡莱代数的and运算和subtraction(合并与删除计算)，合并的实质是去除公共边或公共面的问题，三维计算结果为n胞元复合体。图1表示相邻边和公共面的合并计算，应用式(2)计算结果如图1所示。
图1 TEN二、三维单纯形的合并计算
删除是合并的逆运算，如果隐式保留合并计算前各要素的指针，删除计算是可以实现的，而且是可逆的。但如果对未进行合并运算的TEN进行删除运算，则必须对TEN进行空间三角剖分，此时删除运算变得复杂多变。根据九交模型，对TEN的结点、边、三角形和四面体进行建模，可得到16种拓扑关系，去除6种不存在和无意义的关系，可得到如下10种拓扑关系：
1)一个结点与已有TEN的某结点重合，另一结点在各TEN的公共边，这时各个TEN被一分为二。
2)一个结点与已知点重合，另一点在公共三角形面上，这时每个TEN被一分为三。
3)一个结点与已知点重合，另一点在某TEN内部，单个TEN被一分为四。
4)起始结点在边界三角形上，终结点在边上。
5)起始结点在三角形上，终结点在TEN内。
6)起始结点、终结点均在三角形上。
7)起始结点在三角形上，终结点在边上。
8)约束边被相交三角形分成两段。
9)第二结点插入三角形面。
10)第二结点被插入到三角形某边。
图2展示了a，b，c 3种关系，上述10种关系的实质是采用约束线对TEN进行分割，然后生成子TEN，其特点是线的两个端点与TEN的某一要素层级相交，这种设计的目的是为了避免复杂的空间剖分，使删除计算变得复杂。
图2 TEN删除计算的10种情形
上述的各种情形，在TEN结构设计中必须体现，即TEN的结构设计必须考虑两个条件，第一TEN结构必须要体现自身点、边、三角形、四面体结构；第二是必须满足TEN的拓扑关系计算，这样才能实现TEN的动态编辑，因此，TEN结构的拓扑关系特别重要，它是删除、合并计算的基础。
2.2 TEN拓扑结构检查
TEN的构成可以基于点、线或面，由于基于点描述最简单，因而被各种建模软件广泛采用。点构成规则主要检验点的重合性和共面性，如果TEN空间4点仅有2点重合，TEN退化为三角形，如果3、4个点重合，则TEN退化为边与点，因此不存在共面点是TEN的构成规则。满足点的构成规则条件下，应用欧拉公式(式(3))对TEN进行拓扑结构检验。
(3)
2.3 TEN复合体的一致性检验
复合体一致检查主要包括连续性检查、完整性检查与表面(内、外表面)一致性检查，3项检查遵从由前到后的顺序。连续性检查是检验相连TEN的连接关系，连接规则可自定义，这里规定以三角形相连的TEN是合法的，这个连接规则已在TEN的数据结构中予以体现。完整性检查则是应用式(4)对TEN复合体进行整体检查，在式(4)中，L为几何体的环数，分为外环与内环，S为壳数，G为穿过几何体的洞数，这项检查需要设计“洞”、“壳”、“环”的判断算法，实现比较麻烦。
(4)
3 TEN建模实验
3.1 TEN的合并与删除
在VC++环境下，对TEN的合并和删除操作进行了实验，其中创建TEN采用的是种子生成算法，设计了Ten类对TEN的创建进行了实现，为了便于实验进行，这里设计了and()函数，将3个TEN合并为一个TEN，并保留合并结点(图3(a))，用以保证TEN的逆操作。根据前文所述，TEN的数据结构既顾及到自身结构，又顾及到拓扑要求，TEN的结构部分代码如下:
Class Ten
{
long CTenID;//TEN的ID;用于索引
Carray
Attribute_OF_Ten attibute;//TEN的几何与非几何属性
long Belong_Which; //TEN属于哪个多胞元复合体
bool Is_ConstructTop()；//拓扑结构是否建立
bool Is_Ten_Deleted;//TEN是否被删除
bool Is_Checked;//拓扑结构检查是否进行
bool Is_ContainStraint;//是否包含拓扑约束
};
在删除时计算设计了subtraction()函数，其运算过程是：先选择剖分点，然后生成分割线，最后将TEN分割为若干子TEN，剔除相应的子TEN，完成删除操作(图3(b))。为了实现TEN复合体的一致性检验，这里设计并实现了TEN复合体的结构，以满足拓扑检查，TEN复合体结构部分代码如下:
Class CmBody
{
long ID_OF_CompoundBody;//复合体的标识号
Carray
Ten_CompoundBody_Attribute RWB ;//复合体的属性
Carray Adjacent_CompoundBody; //相邻的TEN复合体
bool Is_Deleted;//是否被合并
bool HasHoles;//是否有洞
bool HasIslands;//是否有岛
bool HasShells;//是否有壳
bool IsConsistencyChecked;//是否进行过拓扑一致性检查
};
在VC++环境中，程序完成了TEN的生成、合并与删除每次操作前后，调用了 Is_Checked()函数和IsConsistencyChecked()函数进行了TEN自身拓扑结构检查和TEN复合体的一致性检验。IsConsistencyChecked()函数运行时，调用了HasIslands()、HasShells()、HasHoles()3个函数，分别完成了岛、壳、洞的判断，使拓扑一致性检查得以实现。
图3 TEN的合并与删除
3.2 DBMS连接
TEN由点、线、面、体4个抽象要素构成，由于客观实体比较复杂，因此构成实体的TEN数量较多，因此TEN所连接的属性表众多，这是TEN模型的一个缺点。如果TEN中单纯形Sn的属性为A(Sn)，则属性类型集合A(Tn)如式(5)所示；如果结点、边、三角形、四面体的属性数分别为m，n，u，v，则TEN的总的属性数的保留公式如式(6)所示[9]。
(5)
SUMTEN=4m+6n+4u+v.
(6)
如图4(a)所示，房屋模型用FDS(Formal Data Structure)表达时[10]，由1个体、7个面、15个边、10个点构成，其属性表数为要素个数33个，而用TEN表达，则由8个体、24个面、25个边、10个点构成，属性数为8×1+4×24+6×25+4×10=294个，可见属性表数较多，因此，需要充分考虑TEN各级要素的属性信息，包括图形属性和非图形属性信息。
在Ten类中，变量CTenID标识了TEN的ID，且此ID是以TEN结点编码为索引进行遍历的，由于三维模型总存在拓扑操作，因此TEN也不断变化，以TEN结点编码为索引可以随拓扑关系变化而变化，因此TEN的几何信息查询易于实现。TEN的基本操作诸如距离查询、体积计算、线的可视性分析等均易于实现，其它复杂分析诸如缓冲区分析和叠加分析，也是易于实现的。TEN查询一般分为几何信息查询和非几何信息查询，非几何查询需要建立DBMS，使之与几何信息通过表ID进行连接，并进行修改与存储，最后实现查询分析。
在研究中，对房屋模型进行三维莫顿码编码[11]，即对构成房屋的各个TEN结点进行编码，编码时采用的顺序为x1y1z1x2y2z2x3y3z3x4y4z4，例如，最底端代码(100000000600100600100608)表示顶点坐标为(10,00,00)，(00,06,00)，(10,06,08)的TEN编码，最后形成的编码如图4(b)左端所示。三维莫顿码是信息查询分析的索引基础，与TEN的ID进行了绑定。当TEN与外部DBMS进行链接，首先搜索TEN的ID，搜索到TEN的几何信息表，再通过ID与外部DBMS关联。图5(a)展示房屋模型P面信息查询时几何属性表与DBMS连接的信息；图5(b)左侧为几何属性表，右侧为DBMS属性信息。
图4 房屋TEN模型属性表数
图5 TEN模型的DBMS查询
4 结 论
以庞卡莱代数为基础的三维GIS模型易于表达实体的动态变化，能完美支持合并和删除运算，并且可以实时进行拓扑一致性检查。基于庞卡莱的边界表达法，本文在VC++环境中设计了TEN拓扑结构和TEN复合体结构，并实现了TEN模型的合并与删除操作。实验证明，基于庞卡莱代数的TEN拓扑关系易于建立，所生成的不规则四面体网适宜于表达不规则实体，如不规则矿体等。同时，基于庞卡莱代数的TEN创建、合并和删除均易于实现，也易于进行拓扑一致性检查与DBMS连接。后续的研究应集中于TEN表的数据冗余去除与可视化表达，使三维GIS模型既结构简单，又具有良好的可视性与空间分析能力。
[1] 马威,李崇贵,林宏波. 基于ArcGIS的矿区三维可视化技术研究[J].矿山测量,2014(2):30-33.
[2] 孙华芬,侯克鹏,郭延辉. 基于SQL Server平台复杂地质体FLAC3d模型的构建[J].辽宁工程技术大学学报(自然科学版),2012,31(4):500-503.
[3] 吴立新，史文中．地理信息系统原理与算法[M]．北京：科学出版社，2003．
[4] ABDUL-RAHMAN A，PILOUS M.Spatial Data Modelling for 3D GIS[M].New York:Springer Berlin Heidelberg New York,2008.2-3.
[5] WANG Yanbing, WU Lixin, SHI Wenzhong, et al.ON 3D GIS SPATIAL MODELING[A].ISPRS Workshop on Updating Geo-spatial Databases with Imagery & The 5th ISPRS Workshop on DMGISs[C].2007:237-240.
[6] 孙敏,薛勇,马蔼乃,等.基于四面体格网的3维复杂地质体重构[J].测绘学报,2002, 31(4):361-365.
[7] 程朋根,文红.三维空间数据建模及算法[M].北京:国防工业出版社,2011:25-32.
[8] GEOGHEGAN R. Topological Methods in Group Theory[M].New York:Springer Science Business Media, 2008:353-362.
[9] 刘艳,武广臣.基于庞加莱代数的3D TEN模型及其拓扑关系建立研究[J].测绘科学,2014,39(4):17-19.
[10] ZLATANOVAL S,RAHMAN A A,SHI Wenzhong.TOPOLOGY FOR 3D SPATIAL OBJECTS[J].Geoinformation Science Journal,2003, 3(1):56-65.
[11] WU Lixin, SHI Wenzhong. GTP-based Integral Real-3D Spatial Model for Engineering Excavation GIS (E2GIS)[J].Geo-Spatial Information Science,2004,7(2):123-128.
[责任编辑：刘文霞]
Research on TEN 3D GIS model based on Poincaré algebra
MA Yumei1,MA Chao2
(1.The Second Surveying and Mapping Institute of Xinjiang Uygur Autonomous Region，Urumqi 830002,China;2.School of Geography,Northeast Norma University,Changchun 130024,China)
Irregular tetrahedral network has the characteristics of simple structure, easy to expand. By means of Poincare algebra,TEN model is proposed by using boundary representation theory in this paper.Compared with the traditional geometric structure model, this model has the characteristics of simple expression and simplified calculation.At the same time, merge and delete operations as well as topology consistency checking are proposed based on Poincare algebra TEN.In the VC++ environment,the merge and delete operations are programed and then implemented.Experimental results show that ten model based on Poincare algebra can effectively establish a dynamic entity model,and it also can establish real-time topological relations,which is suitable for 3D entity such as irregular ore body that changes every time.
Poincaré algebra; 3D GIS;irregular tetrahedral network; topological consistency; boundary expression
引用著录：马玉梅，马超.基于庞卡莱代数的TEN三维GIS模型研究[J].测绘工程，2017，26(5)：62-66.
10.19349/j.cnki.issn1006-7949.2017.05.013
2016-04-30
马玉梅(1983-)，女，工程师，硕士.
P208
A
1006-7949(2017)05-0062-05
