一种基于曲面片的三维地理实体自动构建方法

摘要

本发明提供一种基于曲面片的三维地理实体自动构建方法，包括初次基于给定的平面片集合搜索曲面片，翻转曲面片中不相容平面片，再次基于给定的平面片集合搜索曲面片，得到合格的曲面片集合；然后搜索洞、各洞的所有曲线、搜索各曲线相应的曲线节点、搜索无穷远体的边界上的任意一个曲面片、搜索无穷远体的边界，最后得到最小体集合。本发明首次提供了基于曲面片的三维地理实体自动构建方法，填补了现有技术的空白。

说明书

技术领域

本发明涉及地理空间数据组织与建模的技术领域，尤其是涉及一种基于曲面片的三维实 体拓扑自动构建方法。

背景技术

ISO 19107‘Spatial Schema’,GML3,CityGML中给予了嵌入于三维空间中的“实体(Solid)” 的定义，其在ISO 19107‘Spatial Scheme’中称GM_Solid或TP_Solid(ISO(2003).ISO/TC211, ISO International Standard 19107:2003,Geographic Information–Spatial Schema)，其在GML3 中称为gml::Solid(Protele,C.(2007).OpenGIS Geography Markup Language(GML)Encoding  Standard,Copyright,Open Geospatial Consortium Inc.,v3.2.1)，其在CityGML中称为 Solid(Groger,G.,Kolbe,T.H.,Nagel,C.,Hafele,K.H.(2012).OGC City Geography Markup  Language(CityGML)Encoding Standard,Open Geospatial Consortium Inc.,v2.0)。以上三者在本 质上相同。额外的，Arens和Stoter等提出了一种针对三维实体(3D Solid)的定义，特别的， 该三维实体往往用于三维地籍领域中简单三维宗地的定义(Arens,C.A.(2003).Maintaining  Reality:Modelling 3D Spatial Objects in a Geo-DBMS using a 3D Primitive[D].Msc.Thesis,Delft  University of Technology,the Netherlands；Arens,C.,Stoter,J.,van Oosterom,P.(2005).Modelling 3D Spatial Objects in a Geo-DBMS using a 3DPrimitive.Computers&Geosciences,vol.31,no.2, pp.165-177)。

尽管如此，它们都没有说明这些嵌入于三维空间中的“3维实体”最初如何获得。其中，针 对形状规则的棱柱状三维实体，当前更多的是采用拔高方法生成。具体的，

(1)最为典型的是Ledoux等提出了通过拔高(extrusion)方式由二维平面图生成“三维规则建筑 体”的方法(Ledoux,H.,Meijers,M.(2011).Topologically Consistent 3D City Models Obtained by  Extrusion.International Journal of Geographical Information Science,vol.25,no.4,pp.557-574； Ledoux,H.,Meijers,M.(2009).Extruding Footprints to Create Topologically Consistent 3D City  Models.Urban and Regional Data Management,UDMS Annual,pp.39-48.)

(2)此外，还有Geotz和Zipf等通过拔高方式基于平面地图OpenStreetMap生成CityGML中 LOD 1建筑体的方法(Over,M.,Schilling,A.,Neubauer,S.,Zipf,A.(2010).Generating Web-based 3D City Models from OpenStreetMap:The Current Situtation in Germany.Computers, Environment and Urban Systems,vol.34,no.6,pp.496-507.)

(3)还有Verbree和Germs等提出基于二维平面视图(2D Plan View)和高程信息生成三维模型视 图(3D Model View)的方法，而三维世界视图(3D World View)仅仅是在三维模型视图上粘贴影像 等纹理信息从而增强了真实感(Germs,R.Van,M.G.,Verbree,E.,Frederik,W.J.(1999).A  Multi-view VR Interface for 3D GIS.Computers&Graphics,vol.23,no.4,pp.497-506.)

在以上三类情况中，三维实体必须是形状规则的棱柱状实体，即要求拔高产生的三维实 体的侧面必须垂直于底面。然而，拔高方法有局限，因为并不是所有客观现实中的三维实体 都是形状规则的棱柱状实体，如地籍管理领域中的三维产权体可能是各种形状的(郭仁忠,应 申.(2010).三维地籍形态分析与数据表达[J].中国土地科学,24(12):45-51；应申,郭仁忠,李霖 等.(2014).三维地籍[M],科学出版社,北京:303p.)，可能侧面垂直于地面，也可能侧面不垂直。 尽管如此，每个三维产权体都是封闭实体，也都是有效的产权实体。故而，已经提出了一种 基于离散的二维平面片实现三维产权体的拓扑自动构建的方法(郭仁忠,应申,李霖.(2012).基 于面片集合的三维地籍产权体的拓扑自动构建[J].测绘学报,41(4):620-626；Ying,S.,Guo, R.Z.,Li,L.,van Oosterom,P.,Stoter,J.(2014).Construction of 3D Volumetric Objects for a 3D  Cadastral System.Transactions in GIS,22p；李霖,赵志刚,郭仁忠,贺彪.(2012).空间体对象间三 维拓扑构建研究[J].武汉大学学报(信息科学版),37(6):719-723.)，在地质领域中三维地质体 块的构建思想也与上类似(安聪荣,刘展,王心众.(2012).基于层面结构的地址块体拓扑关系的 自动构建[J].测绘学报,41(1):147-151.)。

尽管如此，许多问题有待深入思考，典型的包括：构成三维产权体的构造基元除了可以 是二维平面片，是否还可以是其它类型的构造基元么？事实上，该猜想是成立的。换言之，针 对三维实体的构建(三维产权体是一种类型的三维实体)，除了可以采用二维平面片实现拓扑 自动构建之外，还可以通过其它类型的基元实现，比如二维曲面片。

为了便于直观阐述，这里借鉴平面多边形实现自动构建方法的研究现状。

平面多边形是一种2维基元，而2维基元应当由1维构造基元自动构建。因此，构建2 维多边形的1维基元可以1维的边，也可以是1维的链。1维边描述了一段笔直形态的1维 基元，而1维链描述了一段弯曲形态的1维基元，1维链可看作1维边的集合。如何通过1 维边或链实现2维多边形拓扑自动构建的研究相对成熟(陈春,张树文,徐桂芬.(1996).GIS中 多边形图拓扑信息生成的数学基础[J].测绘学报,25(4):266-271；)，之后也会详述。

借鉴以上思想，3维实体是一种3维基元，而3维基元应当由2维构造基元自动构建。因 此，构建3维实体的2维基元可以是2维的平面片，也可以是2维的曲面片。2维平面片描 述了一块平坦形态的2维基元，而2维曲面片描述了一块弯曲形态的2维基元，2维曲面片 可看作2维平面片的集合。如何通过2维平面片或曲面片实现3维实体拓扑自动构建的研究 并不多，几乎都集中于通过2维平面片构体(如上所述)，只有很少研究关于如何通过2维曲 面片构体。根据作者目前搜索与见识，只有(Yu,C.B.,Ying,S.,He,B.,Zhao,Z.G.(2012).An  Automatic Sorting Approach of Surface Bundle based on the Shared Space Curve,International  Conference on GeoInformatics 2012,6p)有所论述。

此外值得注意的是，在基于平面片构建三维产权体的过程中，基于共享直线段的平面片 束排序(简称平面束排序)是关键环节。针对平面片束排序，讨论已经较多，同样也已实现， 具体如以上文献所述。相应的，在基于曲面片构建三维产权体的过程中，基于共享曲线的曲 面片束排序(简称曲面束排序)应该同样是关键环节。针对曲面束排序，当前讨论非常少， 甚至(Yu,C.B.,Ying,S.,He,B.,Zhao,Z.G.(2012).An Automatic Sorting Approach of Surface  Bundle based on the Shared Space Curve,International Conference on GeoInformatics 2012,6p)也 只是给予基于共享曲线的曲面束排序的原理性解释，并没有真正实现。

以上问题可以进一步归纳，包括：

(1)针对“通过曲面片构建三维实体”涉及概念中的“曲面片”，该如何具体定义？

(2)针对“通过曲面片构建三维实体”操作过程中的“曲面束排序”，该如何具体实现？

故而，以下首先回顾二维空间中2维多边形自动构建的研究现状；再分别分析计算机辅 助设计(CAD,Computer-aided Design)、拓扑学(Topology)、地理信息系统(GIS,Geography  Information System)中针对曲面的研究现状；之后，基于以上提出本发明中对于曲面片及相 关概念(包括曲线、洞、曲线节点等)的定义，并重点分析如何判断曲面片之间相容性。最 后，给予基于曲面片实现3维实体拓扑自动构建的算法流程的具体阐述。

1.二维空间中多边形自动构建(基于边/链)的研究现状

以下为方便阐述，针对2维多边形的拓扑自动构建，简称“构面任务”；针对3维实体的拓 扑自动构建，简称“构体任务”。在构面时，二维实体(如多边形)由一维基元(如边、链) 拓扑自动构建生成。针对“边”，在不同文献和标准中基本描述一致。最为典型的是“双重独立 地图编码”(DIME,Dual Independent Map Encoding)(Peucker,T.K.,Chrisman,N.(1975). Cartographic Data Structures.The American Cartographer,vol.2,no.1,pp.55-69)结构中对于“边” 的描述—即由起始节点和终止节点封闭的直线段(如附图1(a)所示)。

针对构面任务，当前国内外文献研究集中于通过“边”拓扑自动构建多边形，包括：

(1)经典的左转(右转)算法(杜清运.(1989).地图数据库中多边形数据的自动组织[J].测绘学报, 18(3):204-212；蒋波涛.(2008).插件式GIS应用框架的设计与实现_基于c#和ArcGIS Engine 9.2[M].电子工业出版社)；

(2)Qi算法(齐华,刘文熙.(1996).建立结点上弧-弧拓扑关系的Qi算法[J].测绘学报,25(3): 233-235；齐华.(1997).自动建立多边形拓扑关系算法步骤的优化与改进[J].测绘学报,26(3): 254-260)；

(3)方位角算法(闫浩文,杨维芳,陈全功,梁天刚.(2000).基于方位角计算的拓扑多边形自动构建 快速算法[J].中国图象图形学报,5A(7):563-567；闫浩文,祝方雄.(2001).拓扑多边形自动构建 的一种快速算法[J].浙江测绘,(2):1-10；闫浩文,王家耀.(2009).地图群(组)目标描述与自动综 合[M].科学出版社)；

(4)类方位角算法(刘刚,李永树.(2011).构建结点上弧-弧拓扑关系的类方位角算法[J].测绘科 学,36(6):49-51)；

(5)矢量外积法(高云琼,徐建刚,唐文武.(2002).同一结点上弧-弧拓扑关系生成的新算法[J].计 算机应用研究,19(4):58-59；齐华,李德仁,朱庆.(2003).确定射线空间相邻关系的两个非角度算 法的时间复杂度分析[J].武汉大学学报(信息科学版),28(5):611-614)；

其中，国外针对各种二维数据结构，包括DIME,TIGER(Topologically-Integrated  Geographic Encoding and Rererencing),TIGRIS(Topologically Integrated Geographic Information  Systems)等的“多边形化(Polygonization)”基本都是左转(右转)算法的不同描述(Hodgeson, M.E.(1985).Constructing Shaded Maps with the DIME Topological Structure:An Alternative to the  Polygon Approach.Proceedings of Auto-Carto,vol.7,pp.275-282；Hodgson,M.E.,Barrett,A.L., Plews,R.W.(1989).Cartographic Data Capture using CAD.Auto-Carto:Proceedings of the  International Conference on Computer-Assisted Cartography.American Congress on Surveying  and Mapping,vol.9,pp.357-366；Visvalingam,M.,Wade,P.,Kirby,G.H.(1986).Extraction of Area  Topology from Line Geometry.Proceedings of Auto-Carto London,vol.1,pp.156-165；Meixler,D., Saalfeld,A.(1987).Polygonization and Topological Editing at the Bureau of the Census.Proceedings  of Auto-Carto 8,pp.249-257.)。

针对以上各种构面方法(包括左转方法、Qi算法、方位角方法、类方位角方法、矢量外 积法)，关注点在于：针对共享于同一结点的直线段束，从作为输入数据的直线段矢量集合(一 种比率尺度数据)推导出直线段束的排序结果(一种定序尺度数据)”所采用的方法不同。其 中，左转方法采用直接计算夹角数值大小，Qi算法中采用将Qi算子替代传统arctan函数， 矢量外积法中采用矢量外积排序弧段从而构建二叉排序树(最终排序结果可以通过中序遍历 该二叉树获得)等。

以上为通过边拓扑自动构建面的国内外研究现状。

针对“链”，在不同文献和标准中有着不同的描述与表达，包括在ISO 19107‘Spatial  Schema’,GML3,CityGML，以及相关标准中都自己的定义(Albrecht,J.(1999).Geospatial  Information Stardards:A Comparative Study of Approaches in the Standardisation of Geospatial  Information.Computers&Geosicences,vol.25,no.1,pp.9-24；Peuquet,D.J.(1984).A Concept  Framework and Comparison of Spatial Data Models.Cartographica:The International Journal of  Geographical Information and Geovisualization,vol.21,no.4,pp.66-113；罗芳,艾廷华,王洪.(2004). 闭合坐标链多边形数据的拓扑关系快速构建[J].武汉大学学报(信息科学版),29(6):558-561； 郭仁忠.(2001).空间分析[M])。

尽管针对“链”没有统一定义，从大多情况下将“链”描述为边与边首尾相接形成的1维流形， 不能确定的是构成链的边集合具体包含多少边。换言之，链可以仅仅由1条边构成(如附图 1(b)所示)，也可以由2条边依次首尾相接而成(如附图1(c)所示)，也可以由3条边依次首尾 相接而成(如附图1(d)所示)，也可以由最多N条边依次首尾相接而成(如附图1(e)所示)， 甚至以上依次收尾相接的N条边呈现封闭环(如附图1(f)所示)。

目前，很少有通过“链”拓扑自动构建多边形的研究。本发明认为，用于构面任务的、最为 一般化的“链”定义应该与“多边形转换器(POLYVRT,Polygon Convertor)”结构中对于“链”的定 义保持一致，详见(Peuquet,D.J.(1984).A Concept Framework and Comparison of Spatial Data  Models.Cartographica:The International Journal of Geographical Information and  Geovisualization,vol.21,no.4,pp.66-113.)。其中的链包括如下特征：换言之，只有线与线相交 了才打断，其中位于两个打断交叉点之间的、连续的一整段边都称为链。若没有打断情况发 生，当前连续的一段边集合即一条链，极致情况下首尾相接封闭一个多边形的所有边即一条 链(事实上是闭合链)。

类似POLYVRT中对于链的定义，还见于保持拓扑一致(topologically-consistent)或称拓扑 安全(topologically-safe)制图综合所采用的数据结构中(Meijers,M.(2011).Simulteneous& Topologically-safe Line Simplification for a Variable-scale Planar Partition.Advancing  GeoInformation Science for a Changing World,Springer Berlin Heidelberg,pp.337-358.)，其中定 义的链也具备类似特征。

总计而言，DIME和POLYVRT都是制图学中的经典数据结构，前者以“边”作为基本单位， 后者以“链”作为基本单位，同时“链”是描述了对于“边”的聚合程度。该思想应该同样应用于 平面片以及可作为平面片聚合的曲面片的定义之中。

2.计算机辅助设计、拓扑学、地理信息系统中对于曲面的定义

针对曲线曲面的建模、表达、可视化的研究众多，其中最为典型的是在计算机辅助设计 (CAD)、拓扑学、地理信息系统(GIS)中对于它们的定义。

2.1计算机辅助设计(CAD)中对于曲面的定义

ISO 19107‘Spatial Schema’和GML3中针对曲线曲面的定义是一致的，其中前者对于曲线 曲面指定了抽象的规范，后者可以看作是这些抽象规范的具体实现。而CityGML中特征的空 间特性由GML3中几何模型来表达。事实上，CityGML只使用了GML3几何包的一个子集， 定义了GML3的一个侧面(Groger,G.,Plumer,L.(2012).CityGML-Interoperable Semantic 3D  City Models.ISPRS Journal of Photogrammetry and Remote Sensing,vol.71,pp.12-33.)，CityGML 中对于曲线曲面定义与ISO和GML3中一致。

更为详细的，在ISO 19107‘Spatial Schema’中涉及曲线曲面的对象，包括如下：

(1)从几何基元(geometric primitive)的角度分类，它们包括GM_Ring,GM_OrientedCurve, GM_Curve,GM_OrientedSurface,GM_Surface；

(2)从几何聚合(geometric aggregate)的角度分类，它们包括GM_MultiCurve,GM_MultiSurface；

(3)从几何复形(geometric complex)的角度分类，它们包括GM_CompositeCurve, GM_CompositeSurface；

(4)从坐标几何(coordinate geometry)的角度分类，它们包括GM_GenericCurve和它的子类 (GM_ArcString,GM_Arc,GM_Circle,GM_SplineCurve,GM_PolynomialSpline, GM_CubicSpline,等),GM_GenericSurface和它的子类(GM_ParametricCurveSurface, GM_GriddedSurface,GM_BicubicGrid,GM_Polygon,GM_Triangle,GM_Tin等)。

如上所述，CityGML定义了GML3的一个侧面，如GML3中只有gml:Polygon, gml:TexturedSurface,gml:CompositeSurface,gml:TriangulatedSurface,gml:Tin被用来表达 CityGML中的曲面(Surface)，GML3中只有gml:LineString,gml:CompositeCurve, gml:LineStrings被用来表达CityGML中的曲线(Curve)。更为重要的，CityGML相对于拓扑方 面，更为强调语义信息，包括数字地表模型，建筑物，隧道，桥梁，水体，交通对象，植被 对象，城市设施等。更为详细的，以建筑物为例，房间(Room)是针对建筑物内部自由空间建 模的语义对象，包括楼层曲面(FloorSurface),天花板曲面(CeilingSurface),内部曲面 (InteriorSurface),闭合曲面(ClosureSurface)，但以上这些房间(Room)边界的曲面对象之间的拓 扑关系正确性却并不能仅仅由CityGML得到保证。

基于ISO 19107‘Spatial Schema’和GML3，Pu等设计了自由形式(Free-form)的曲线和曲面 (如NURBS、B-Spline、Bezier曲线/曲面)，并基于Oracle Spatial设计了一个简单的原型系统， Pu等的研究重点是通过自由形式的曲线曲面实现弯曲对象的精确表达和可视化，多采用逼近 思想(Pu,S.(2004).Database Storage of 3D Freeform Curves and Surfaces.Research Project Report, TU Delft,55p；Pu,S.(2005).Managing Freeform Curves and Surfaces in a Spatial DBMS.Master’s  Thesis,TU Delft,77p；Zlatanova,S.,Pu,S.,Bronsvoort,W.F.(2006).Freefrom Curves and Surfaces  in DBMS:A Step Forward in Spatial Data Infrastructure.In:S.Nayak,S.K.Pathan and  J.K.Garg(Eds.)；Archives of ISPRS,vol.34,Part 3A,pp.407-412；Zlatanova,S.(2006).3D  Geometries in Spatial DBMS.Innovations in 3D GeoInformation Systems,Springer Berlin  Heidelberg,pp.1-14.)。这与CAD中表达曲线曲面的思想是一致的(Yamashina,H.,Fukushima, K.,Saijo,A.(1996).CAD for Free-form Surfaces.Computer Integrated Manufacturing Systems, vol.9,no.1,pp.9-18；Hoffman,C.,Hopcroft,J.(1985).Automatic Surface Generation in  Computer-aided Design.The Visual Computer,vol.1,no.2,pp.92-100.)

同时，Zlatanova等详细分析了嵌入于三维空间中的曲面(Surface)与线(Line)之间的31种 拓扑关系、曲面(Surface)与曲面(Surface)之间的38种拓扑关系、体(Body)与曲面(Surface)之间 的19种拓扑关系。这里的曲面等对象的定义符合OpenGIS标准，也即与GML3保持一致 (Zlatanova,S.(2000).3D GIS for Urban Development[D].ITC Dissertation Series,Netherlands.).

2.2拓扑学中对于曲面的定义

与CAD和GIS中不同，在拓扑学中，针对曲线曲面的研究重点在于曲线曲面的拓扑性质， 包括针对曲线的连通性的定义、闭曲面的定义、曲面是否可定向等(Hatcher,A.(2002).Algebraic  Topology[M].550p；Armstrong,M.A.(1979).Basic Topology[M].London:McGraw-Hill；尤承 业.(1997).基础拓扑学讲义[M].北京工业出版社)。特别的，在拓扑学中针对曲线的一个重要 定理称为约旦定理(Jordan Theorem)，描述了采用曲线针对二维空间给予剖分的特殊拓扑情况， 详见(周晓光.(2005).基于拓扑关系的地籍数据库增量更新方法研究[D].博士论文,中南大学； 周晓光.(2007).地籍数据库增量更新[M].测绘出版社)。

2.3地理信息系统(GIS)中对于曲面的定义

相对的，针对GIS中对于曲线曲面的研究，既着眼于曲线曲面的准确表达，也关心数据 结构的精简性与灵活性，多采用拟合方法(郭仁忠.(2001).空间分析[M],高等教育出版社；Guo, R.Z.(1998).Spatial Objects and Spatial Relationships.Geo-spatial Information Science,vol.1,no.1, pp.38-42.)，特别是采用不规则三角网(TIN,Irregular Triangle Network)或和数据高程模型(DEM, Digital Elevation Model)来表达曲面(Yang,B.S.,Shi,W.Z.,Li,Q.Q.(2005).An Integrated TIN and  Grid Method for Constructing Multi-resolution Digital Terrain Model.International Journal of  Geographical Information Science,vol.19,no.10,pp.1019-1038；Etzelmuller,B.(2000).On the  Quantification of Surface Changes using Grid-based Digital Elevation Models (DEMs).Transactions in GIS,vol.4,no.2,pp.129-143；孙敏.(2000).三维城市模型的数据建模研究 [D].博士论文,中南工业大学.)

事实上，CAD,拓扑学,GIS中对于曲线曲面的定义并不完全分隔，而是相互交叉的，特 别针对现有的各种三维空间数据模型与结构，它们广泛应用于CAD,GIS,拓扑学中(Zlatanova, S.(2000).On 3D Topological Relationships.Database and Expert Systems Applications, Proceedings of 11^th International Workshop on,IEEE,pp.913-919)。在这些三维空间数据模型与 结构中，都表达了一个概念：针对每个2维基元(如平面，曲面对象)，都存在类似“前向3 维体(Front 3D Body/Solid)”和“后向3维体(Back 3D Body/Solid)”的属性成员。具体的，包括： (1)在城市数据模型(UDM,Urban Data Model)(Coors,V.(2003).3D-GIS in Networking  Environments.Computers,Environment and Urban Systems,vol.27,no.4,pp.345-357)中,每个 Face基元包含Body_left和Body_right属性；

(2)在简化空间数据模型(SSM,Simplified Spatial Model)(Zlatanova,S.(2000).3D GIS for Urban  Development[D].Ph.D Dissertation,ITC,The Netherlands,222p)中,每个face基元包含bidleft 和bidright属性；

(3)在四面体(TEN,Tetrahedron)(Pilouk,M.,Tempfli,K.,Molennar,M.(1994).A  Tetrahedron-based 3D Vector Data Model for Geo-information.In:Molenaar,M.(Eds.),Advanced  Geographic Data Modelling.Sylvia De Hoop,Geodesy Press,pp.129-140)中,每个Triangle基元 包含left_tet1和right_tet2属性；

(4)在似三棱柱(GTP,Generalized Tri-Prism)(Wu,L.X.(2004).Topological Relations Embodied in  a Generalized Tri-prism(GTP)Model for a 3D Geoscience,Modelling System.Computers& Geosciences,vol.30,no.4,pp.405-418)中,每个TIN-face基元包含Upper-GTP和Lower-GTP属 性且每个side-face基元包含two GTPs属性；

(5)在类三棱柱(QTPV,Quasi Tri-prism Volume)(Gong,J.Y.,Cheng,P.G.,Wnag,Y.D.(2004). Three-dimensional Modelling and Application in Geological Exploration Engineering.Computers &Geosciences,vol.30,no.4,pp.391-404)中,每个Triangle基元和SideQuadrangle基元都分别包 含PosiQTPV和NegaQTPV属性；

类似的情况还包括(Zhang,L.Q.,Yang,C.J.,Tong,X.H.,Rui,X.P.(2007).Visualization of  Large Spatial Data in Network Environment.Computers&Geosciences,vol.33,no.9, pp.1130-1139；Rahman,A.A.,Pilouk,M.,Zlatanova,S.(2001).The 3D GIS Software  Development_Global Efforts from Researchers and Vendors.GeoInformation Science Journal, vol.1,no.13,pp.1-13)。区别在于，当前这些模型与结构中，针对构造“前向3维体”和“后向3 维体”的2维基元定义不同，尤其是2维曲面对象的定义有所不同。

2.4顾及曲面的拓扑一致性的研究现状

无论曲线曲面如何定义，针对实体构建的有效性(包括几何一致性和拓扑一致性，尤其 是拓扑一致性)，总需要一定手段去验证。尽管如此，目前相关研究并不多(刘雄伟,彭维.(2000). 边界表示得拓扑与几何一致性[J].华侨大学学报(自然科学版),21(1):51-56；Sakkalis,T.,Shen, G.,Patrikalakis,N.M.(2000).Representational Validity of Boundary Representation Models. Computer-Aided Design,vol.32,pp.719-726.)。

其中，欧拉公式是验证一致性的常见且有效手段，尤其是结合拓扑学理论(Armstrong, M.A.(1983).Basic Topology[M].UTM,Springer,first edition)。基于欧拉公式与流形拓扑学原理， Groger和Plumer等针对三维建模领域(尤其是三维城市建模)中发生实体本身更新、实体间 分割、实体间合并(伴随产生穿洞)情况时，如何保证对象(包括曲面对象)的有效性，展 开一系列研究，提出了“几何-拓扑一致性(Geometrical-topological Consistency)维护原则”，详 见(Groger G.,Plumer L.(2011).How to Achieve Consistency for 3D City Models.GeoInformatica, vol.15,no.1,pp.137-165；Groger G.,Plumer L.(2005)How to Get 3-D for the Price of 2-D_Topology and Consistency of 3-D Urban GIS.GeoInformatica,vol.9,no.2,pp.139-158； Groger,G.,Plumer,L.(2012).Provably Correct and Complete Transaction Rules for Updating 3D  City Models.GeoInformatica,vol.16,no.1,pp.131-164；Groger,G.,Plumer,L.(2012).Transactions  Rules for Updating Surfaces in 3D GIS.ISPRS Journal of Photogrammetry and Remote Sensing, vol.69,pp.134-145.)。本发明在给予实体构建的有效性验证时也是借助欧拉公式，之后详述。

本发明建立于“面向地籍的三维数据模型”之上。该模型的概念模型设计包含三层，即几何 层、拓扑层、实体层，如附图2所示。其中，几何层包含点、弧段、多边形等对象；拓扑层 包含节点、边、平面片、三维实体(Body)对象；实体层包括界址点、界址线、界址面、二维 产权体、二维宗地、三维产权体、三维建筑空间、三维法律空间等。其中，节点、边、环、 平面片、三维实体(Body)这几个概念及相互之间拓扑关系已经得到详细阐述，详见(Guo,R.Z., Yu,C.B.,He,B.,Zhao,Z.G.,Li,L.,Ying,S.(2012).Logical Design and Implementation of the Data  Model for 3D Cadastre in China.3^rd International Workshop on 3D Cadastre:Developments and  Practice,Shenzhen,China,pp.113-136；赵志刚.(2012).三维地籍空间数据拓扑构建、维护及应用 研究[D].博士论文，武汉大学,191p)，尽管如此，它们仅仅局限于与“平面片”相关的基元定 义部分，完全没有涉及“曲面片”相关的基元定义部分。而“面向地籍的三维数据模型”也包含 了曲面的概念(如附图2中虚线框所围)，以上文献并没有给予与曲面相关概念(包括曲面片、 曲面片包含的曲线、曲线包含的曲线端点)等的详细定义与阐述。

在这里，将其中节点、边、环、平面片、三维实体(Body)这5种基元形成的三维数据模型 称为“基于平面片的三维数据模型”；同时，针对涉及曲面的基元，包括曲面片、洞、曲线、 曲线节点、三维实体(Body)的额外补充信息，将这几类基元形成的三维数据模型称为“基于曲 面片的三维数据模型”。“基于平面片的三维数据模型”与“基于曲面片的三维数据模型”共同组 成了“面向地籍的三维数据模型”(也称“完全的三维数据模型”)。本发明的阐述重点为“基于 曲面片的三维数据模型”，并将“基于曲面片的三维数据模型”与“基于平面片的三维数据模型” 给予比较，同时针对已经提出的基于共享曲线的曲面束排序理论给予真正实现进而实现曲面 构体(Yu,C.B.,Ying,S.,He,B.,Zhao,Z.G.(2012).An Automatic Sorting Approach of Surface  Bundle based on the Shared Space Curve,GeoInformatics 2012,6p)。

发明内容

本发明的目的在于针对现有不足，提出基于曲面片的三维实体拓扑自动构建方法。

为达到上述目的，本发明提供的技术方案为一种基于曲面片的三维地理实体自动构建方 法，包括以下步骤，

步骤1，初次基于给定的平面片集合搜索曲面片，搜索方式包括执行以下子步骤，

步骤1.1，针对给定的平面片集合中的每个平面片，标记为“未使用”；

步骤1.2，创建一个新的曲面片对象和当前平面片集合，内容分别为空；针对当前平面片集合 进行初始化，包括随机选择给定的平面片集合中的1个平面片；

步骤1.3，针对当前平面片集合中的每个平面片，将其加入步骤1.2中创建的新曲面片对象， 并标记该平面片为“已使用”；

步骤1.4，针对当前平面片集合，创建推进平面片集合；

步骤1.5，针对当前平面片集合中的每个平面片的每条边，在给定的平面片集合中剩余未使用 的平面片中计算该边的所有相接平面片，筛选出那些只有1个相接平面片的情况，并将这些 唯一相接平面片加入推进平面片集合中；

步骤1.6，清空当前平面片集合，将推进平面片集合作为新的当前平面片集合；之后，清空推 进平面片集合；

步骤1.7，返回步骤1.3，基于当前新的当前平面片集合，重复步骤1.3-1.7，直至计算得到的 推进平面片集合为空，进入步骤1.8；此时，以上曲面片的所有构造平面片都搜索完毕；

步骤1.8，返回步骤1.2，基于重新初始化的当前平面片集合，重复步骤1.2-1.8，直至平面片 集合中每个平面片都被“已使用”；此时，所有曲面片的所有构造平面片都搜索完毕；

步骤2，翻转曲面片中不相容平面片，包括对步骤1所得各曲面片分别进行以下操作，

对当前操作的曲面片，从步骤1所得初步搜索的构造平面片集合中随机选择1个平面片 作为标准平面片初始化当前平面片集合，计算标准平面片的所有边，去除边界边，剩余的作 为前推进边集合；然后执行以下子步骤，

步骤2.1，根据当前平面片集合(strip_facets)和当前推进边集合(strip_edges)寻找相接平面片集 合(next_strip_facets)；

步骤2.2，计算下一批推进边集合(next_strip_edges)，实现方式为，设相接平面片集合包含的 所有边形成一个集合，称所有边集合(all_edges)，从所有边集合中取出当前推进边集合 (strip_edges)、公共边集合(common_edges)、边界边集合(boundary_edges)，得到下一批推进边 集合(next_strip_edges)；

步骤2.3，针对相接平面片集合(next_strip_facets)中的每一个平面片，从当前平面片集合 (strip_facets)中取邻接的任意一个平面片，判断两者的相容性，若两者相容则不处理前者，若 两者不相容则翻转前者；

步骤2.4，清空当前平面片集合(strip_facets)，把相接平面片集合(next_strip_facets)作为新的当 前平面片集合；之后，清空相接平面片集合；

步骤2.5，清空当前推进边集合(strip_edges)，把下一批推进边集合(next_strip_edges)作为新的 当前推进边集合；之后，清空下一批推进边集合；

步骤2.6，返回步骤2.1，根据当前平面片集合(strip_facets)和当前推进边集合(strip_edges)，重 复步骤2.1-2.6，直至计算得到的下一批推进边集合为空；

步骤3，根据步骤2的翻转结果，再次基于给定的平面片集合搜索曲面片，得到曲面片 集合，搜索过程方式与步骤1的搜索方式一致；

步骤4，搜索洞，包括对步骤3所得每个曲面片分别执行以下子步骤，

步骤4.1，针对曲面片的边缘边集合中的每条边缘边，标记其为“未使用”；

步骤4.2，创建一个新的洞对象，内容为空；

步骤4.3，创建当前边集合，初始化为边缘边集合中的任意一条“未使用”的边缘边；

步骤4.4，针对当前边集合中的每条当前边，将其加入以上步骤4.2建立的洞对象，并将该边 标记为“已使用”；针对当前边集合，创建对应的邻接边集合，初始化内容为空；

步骤4.5，针对当前边集合中的每条当前边，寻找其邻接边如下，

针对每条当前边的起始节点，寻找所有相接边，如果存在包含于曲面片的边缘边集合的相接 边，将其加入邻接边集合；

针对每条当前边的终止节点，寻找所有相接边，如果存在包含于曲面片的边缘边集合的相接 边，将其加入邻接边集合；

步骤4.6，清空当前边集合，将邻接边集合作为新的当前边集合；之后，清空邻接边集合；

步骤4.7，返回步骤4.4，基于新的当前边集合，重复步骤4.4-步骤4.7，直至寻找得到的邻接 边集合为空，进入步骤4.8；此时，以上洞中所有边都搜索完毕，得到当前洞的构造边集合； 步骤4.8，返回步骤4.2，重复步骤4.2-4.8，创建新的洞对象并进行搜索，直至以上曲面片的 边缘边集合中每条边缘边都“已使用”；此时，以上曲面片中所有洞都搜索完毕，形成该曲面 片的构造洞集合；

步骤5，搜索曲面片集合包含的各洞的所有曲线；

步骤6，搜索各曲线相应的曲线节点；

步骤7，搜索无穷远体的边界上的任意一个曲面片，通过基于步骤3所得曲面片集合寻 找外轮廓体的边界上任意一个曲面片实行，包括以下子步骤，

步骤7.1，创建一个结果曲面片，其内容为空；

步骤7.2，创建一个结果平面片，其内容为空；

步骤7.3，计算给定平面片集合的最小外接盒；计算该最小外接盒的最大Z值，简称最大Z 值；

步骤7.4，创建一个相接平面片集合，其内容为空；

步骤7.5，针对给定平面片集合中的每个平面片的每个顶点，比较该顶点的Z值与最大Z值： 若相等，则将该平面片加入以上相接平面片集合中；否则，不做任何处理；

步骤7.6，针对以上相接平面片集合，如果存在所有顶点Z值都等于最大Z值的平面片，将 该平面片标记为平行平面片，并转入步骤7.7；如果不存在，则转入步骤7.8；

步骤7.7，比较平行平面片的法向量与三维矢量(0,0,1)的夹角大小，并在以下处理后转入步 骤7.10；

若两者夹角为0，则将该平面片标记为结果平面片，且结果平面片的方向为1；

若两者夹角为180，则将该平面片标记为结果平面片，且结果平面片的方向为2；

步骤7.8，针对相接平面片集合中的每个平面片，计算法向量与三维矢量(0,0,1)的夹角，该 夹角记为“原始夹角”；比较该原始夹角与90并如下处理，

若原始夹角处于(0,90)，则不进行操作；

若原始夹角处于(90,180)，则将180减去原始夹角；

将处理后的夹角标记为“处理夹角”，并进入步骤7.9；

步骤7.9，针对相接平面片集合中的每个平面片，选择其“处理夹角”最小的平面片并标记为结 果平面片；同时，根据结果平面片的“原始夹角”计算结果平面片的方向如下，

若原始夹角处于(0,90)，则结果平面片的方向记为1；

若原始夹角处于(90,180)，则结果平面片的方向为2；

步骤7.10，找到结果平面片所在的曲面片，该曲面片为结果曲面片；同时，将结果平面片的 方向作为结果曲面片的方向；

步骤7.11，所得结果曲面片为外轮廓体边界上的一个曲面片，返回结果曲面片；

步骤8，搜索无穷远体的边界，通过基于步骤3所得曲面片集合搜索外轮廓体实行，包 括以下子步骤，

步骤8.1，采用步骤7所得边界上的任意一个曲面片，记为外轮廓任意曲面片；

步骤8.2，创建外轮廓体对象和当前曲面片集合，内容分别为空，初始化当前曲面片集合包括 之前所得的外轮廓任意曲面片；

步骤8.3，针对当前曲面片集合中的每个曲面片，分别读取此时曲面片的方向，将曲面片以及 此时曲面片的方向加入外轮廓体对象中，同时对曲面片此时方向对应的侧面作标记如下，

若此时曲面片的方向为1，表明搜索前向无穷远体，则该曲面片的背面标记为”已使用”；

若此时曲面片的方向为2，表明搜索后向无穷远体，则该曲面片的正面标记为”已使用”；

步骤8.4，针对当前曲面片集合，创建对应的推进曲面片集合，其初始化内容为空；

步骤8.5，针对当前曲面片集合中的每个曲面片的每条曲线，分别计算最邻近曲面片和相应方 向

步骤8.6，针对以上得到的每个最邻近曲面片及相应方向，若在步骤8.2创建的外轮廓体对象 外轮廓体中不存在，则加入以上推进曲面片集合；若存在则不做处理；

步骤8.7，清空当前曲面片集合，将推进曲面片集合作为新的当前曲面片集合；之后，清空推 进曲面片集合；

步骤8.8，返回步骤8.3，基于新的当前曲面片集合重复步骤8.3-8.8，直至得到的推进曲面片 集合为空；此时，以上无穷远体的边界搜索完毕；

步骤9，针对步骤3所得曲面片集合搜索最小体集合，包括以下子步骤，

步骤9.1，针对曲面片集合中每个曲面片，对其正面和背面都标记”未使用”；

步骤9.2，根据步骤8所得无穷远体的边界更新相应曲面片的标记，边界上的每一个曲面片， 有一侧”已使用”；

步骤9.3，创建一个新的最小体对象和当前曲面片集合，其内容分别为空，初始化当前曲面片 集合；

步骤9.4，针对当前曲面片集合中的每个曲面片，读取此时曲面片的方向，并将该曲面片以及 此时曲面片的方向加入以上最小体中，同时将该曲面片此时方向对应的侧面作标记如下，

若此时曲面片的方向为1，表明搜索后向体，则该曲面片的正面标记为”已使用”；

若此时曲面片的方向为2，表明搜索前向体，则该曲面片的背面标记为”已使用”；

步骤9.5，针对当前曲面片集合，创建推进曲面片集合，其内容为空；

步骤9.6，针对当前曲面片集合中的每个曲面片的每条构造曲线，计算最邻近曲面片及相应方 向；

步骤9.7，对于以上得到的每个最邻近曲面片及相应方向，若在步骤9.3创建的新的最小体对 象中不存在，则加入以上推进曲面片集合；若存在则不做处理；

步骤9.8，清空当前曲面片集合，将推进曲面片集合作为新的当前曲面片集合；之后，清空推 进曲面片集合；

步骤9.9，返回步骤9.4，基于新的当前曲面片集合重复步骤9.4-步骤9.9，直至计算得到的推 进曲面片集合为空；此时，以上最小体的所有构造曲面片都搜索完毕，进入步骤9.10；

步骤9.10，返回步骤9.3，创建一个新的最小体对象，重复步骤9.3-步骤9.10，直至给定曲面 片集合中的每个曲面片都被“已使用”2次；此时，所有最小体都搜索完毕。

而且，步骤5中，针对细分后曲线执行以下子步骤，

步骤a.1，从步骤3所得曲面片集合中取一个曲面片为当前处理的曲面片；

步骤a.2，从曲面片的构造洞集合中取一个洞为当前处理的洞；

步骤a.3，针对当前洞的构造边集合中的每条边，标记为“未使用”；

步骤a.4，建立一个哈希表，用于存储当前洞中每条边，及其隶属曲面片集合；其中，当前洞 中每条边作为哈希表中”键”，该边的隶属曲面片集合作为哈希表该”键”的”值”；

步骤a.5，建立一个新的曲线对象，其内容为空；

步骤a.6，创建当前边集合，初始化内容为当前洞中任意一条“未使用”的边；同时，标记该边 为标准边(standard edge)，该边的隶属曲面片集合称为标准隶属曲面片集合；

步骤a.7，针对当前边集合中每条当前边，标记其为”已使用”，并加入本次执行步骤a.5建立 的曲线对象中；对于当前边集合，创建相应的邻接边集合，内容为空；

步骤a.8，针对当前边集合中每条当前边，寻找其所有邻接边，加入邻接边集合；

步骤a.9，清空当前边集合，用邻接边集合替代作为新的当前边集合；之后，清空邻接边集合；

步骤a.10，返回步骤a.6，基于新的当前边集合重复步骤a.6-步骤a.10，直至寻找得到的邻接 边集合为空；此时，针对曲面片的构造洞集合中的一个洞的所有边搜索完毕；

步骤a.11，针对本次执行步骤a.5建立的曲线对象的“隶属曲面片集合”属性，采用标准隶属曲 面片集合赋值；

步骤a.12，本次执行步骤a.5建立的曲线对象真正构造完毕；

步骤a.13，返回步骤a.5重新建立新的曲线对象，重复步骤a.5-a.13，直至该洞的构造边集合 中每条边都”已使用”；此时，以上洞中所有曲线都搜索完毕，进入步骤a.14；

步骤a.14，返回步骤a.2，取下一个洞作为新的当前洞，重复步骤a.2-a.14；直到当前处理的 曲面片的所有洞的所有曲线都搜索完毕，进入步骤a.15；

步骤a.15，返回步骤a.1，取下一个曲面片为当前处理的曲面片，重复步骤a.1-a.15；直到所 有曲面片的所有洞的所有曲线都搜索完毕。

或者，针对未细分曲线执行以下子步骤，

步骤b.1，从曲面片集合中取一个曲面片作为当前处理的曲面片；

步骤b.2，从当前处理的曲面片的构造洞集合中取一个洞为当前洞；

步骤b.3，针对当前洞的构造边集合中的每条边，标记为“未使用”；

步骤b.4，建立一个哈希表，用于存储当前洞中每条构造边，以及该边的隶属曲面片集合；其 中，当前洞中每条边作为哈希表的“键”，该边的隶属曲面片集合作为哈希表中该“键”的“值”；

步骤b.5，建立一个新的曲线对象，其内容为空；

步骤b.6，从当前洞的构造边集合中，选择任意1条“未使用”的边，将其加入以上曲线，并将 其标记“已使用”；同时，标记该边为标准边(standard edge)，该边的隶属曲面片集合称为标准 隶属曲面片集合；

步骤b.7，从当前洞的构造边集合中，继续寻找“未使用”且具有标准隶属曲面片集合的一条边， 标记这样的边为相似边(similar edge)，将相似边加入以上曲线；

步骤b.8，返回步骤b.7找下一条相似边，直至不存在相似边；此时，以上曲线的所有边都搜 索完毕；

步骤b.9，将标准隶属曲面片集合赋予本次执行步骤b.5建立的曲线对象的隶属曲面片集合；

步骤b.10，本次执行步骤b.5建立的曲线对象曲线构造完毕；

步骤b.11，返回步骤b.5重新建立新的曲线对象，重复步骤b.5-b.11，直至当前洞的构造边集 合中每条边都“已使用”；直到当前洞中所有曲线都搜索完毕，进入步骤b.12；

步骤b.12，返回步骤b.2，取下一个洞作为新的当前洞，重复步骤b.2-b.12；直到当前曲面片 的所有洞的所有曲线都搜索完毕，进入步骤b.13；

步骤b.13，返回步骤b.1，取下一个曲面片作为当前处理的曲面片，重复步骤b.1-b.13；此时， 所有曲面片的所有洞的所有曲线都搜索完毕。

而且，往曲线中每次增加一条构造边，就更新曲线的曲线节点，包括以下子步骤，

(1)从曲面片集合中取一个曲面片作为当前处理的曲面片；

(2)从当前处理的曲面片的构造洞集合中取一个洞作为当前洞；

(3)从当前洞的构造曲线集合中取一条曲线为当前曲线；

(4)比较当前曲线的构造边集合与构造节点集合的大小，

若相同，则标记该条曲线为“闭合曲线”；

(ii)若不同，则标记该条曲线为“不闭合曲线”；

(5)进一步处理当前曲线，

(i)若当前曲线是“闭合曲线”，则选择当前曲线的构造节点集合中任意一个节点，将其同时作 为当前曲线的曲线起始节点和曲线终止节点，并跳入步骤(9)；

(ii)若当前曲线是“不闭合曲线”，则创建内部节点集合，其内容为空，进入步骤(6)；

(6)取当前曲线的构造节点集合中的一个节点，判断在当前曲线的构造边集合中，是否存在2 条不同的构造边，且该节点是这2条边的公共节点，

(i)若存在，则将该节点加入内部节点集合；

(ii)若不存在，则不做任何处理；

(7)返回步骤(9)取当前曲线的构造节点集合中的下一个节点，重复步骤(6)-(7)，直至搜索出以 上曲线的完整的内部节点集合，进入步骤(8)；

(8)针对当前曲线的构造节点集合，去除内部节点集合，剩余的为当前曲线的外部节点集合， 包括当前曲线的曲线起始节点和终止节点；

(9)当前曲线的曲线节点搜索完毕；

(10)返回步骤(3)，从当前洞的构造曲线集合中取下一条曲线为当前曲线，重复步骤(3)-(10)； 直到当前洞的所有曲线的曲线节点都搜索完毕，进入步骤(11)；

(11)返回步骤(2)，取下一个洞作为当前洞，重复步骤(2)-(11)；直到当前曲面片的所有洞的所 有曲线的曲线节点都搜索完毕，进入步骤(12)；

(12)返回步骤(1)，取下一个曲面片作为当前处理的曲面片，重复步骤(1)-(12)，直到所有曲面 片的所有洞的所有曲线的曲线节点都搜索完毕。

本发明与现有技术相比具有以下优点：

本发明阐述了通过2维基元自动构建3维实体的本质，这里的2维基元不再局限于现有 的2维平面片，这里的2维基元被定义为2维曲面片，而2维平面片是2维曲面片的特殊例 子。现有技术中，2维平面片总是可定向的，即用于构体的平面片总是“合格”的；2维曲面片 远比2维平面片结构复杂，2维曲面片的可定向判断也更为复杂，本发明详细阐述了如何构 造“合格”的2维曲面片(包括其包含的洞、曲线、曲线节点的正确定义)；同时，基于“合格” 的2维曲面片，进一步实现了基于共享曲线的曲面片束排序，从而自动构建3维实体。对于 已有技术中仅有“基于共享直线段的平面片束排序”的现状，首次提供了基于曲面片的三维地 理实体自动构建方法，填补了现有技术的空白。

附图说明

图1为现有技术中边与链的定义示意图；

图2为面向地籍的三维空间数据模型(现有技术包含平面片相关部分，本发明包含曲面 片相关部分)的概念模型设计示意图；

图3为现有技术中二维单纯形(2-simplex)之间以及平面片(Facet)之间的相容性示意图；

图4为本发明实施例的二维单纯复形(2-simplicial complex)之间以及曲面片(Surface)之间 的相容性示意图；

图5为本发明实施例的面向地籍的三维空间数据模型(包含平面片和曲面片)的表结构 设计示意图；

图6为本发明实施例的相接平面片寻找方式示意图；

图7为本发明实施例的往曲线中动态添加边的情况分类示意图；

图8为本发明实施例的渐进式更新曲线端点的示例图；

图9为本发明实施例方法应用的案例a中初次寻找曲面片过程示意图；

图10为本发明实施例方法应用的案例b中初次寻找曲面片过程示意图；

图11为本发明实施例方法应用的案例c中翻转曲面片中不相容平面片过程示意图；

图12为本发明实施例方法应用的案例c中翻转曲面片中不相容平面片过程的对应统计数 据展示图；

图13为本发明实施例方法应用的案例d中翻转曲面片中不相容平面片过程示意图；

图14为本发明实施例方法应用的案例d中翻转曲面片中不相容平面片过程的对应统计数 据展示图。

具体实施方式

本发明阐述的是一种基于曲面片的三维实体拓扑自动构建方法。本发明是对“一种地理空 间实体构建方法及系统”(该专利已经授权)的继承与发展。在“一种地理空间实体构建方法 及系统”中，阐述了一种基于统一逻辑的实体构建思想，该思想可以具体应用于通过1维边/ 链拓扑自动构建2维多边形、通过2维平面片拓扑自动构建3维体，前者简称“基于边/链构 面方法”，后者简称“基于平面片构体方法”。针对后者“基于平面片构体方法”，尽管提出可以 实现三维实体的拓扑自动构建，但并没有从根本上解决如何通过2维基元实现三维实体的拓 扑自动构建(如上所述简称“构体任务”)。换言之，“一种地理空间实体构建方法及系统”的侧 重点在于构面与构体的逻辑统一性。

而本发明对于“通过2维基元实现3维实体自动构建”给予进一步深入研究。具体的，本发 明中提出的曲面片是更具备一般意义的2维基元，平面片是曲面片的特例；本发明所述“基于 二维曲面片构建三维实体”方法是更具备一般意义的通过2维基元构建3维实体的方法，“基 于二维平面片构建三维实体”是“基于二维曲面片构建三维实体”的特例。

针对构体任务而言，判断二维基元之间的相容性(coherence)非常重要。平面片之间的相容 性判断相对简单，曲面片之间的相容性判断相对复杂。具体的，平面片相容性指平面片法向 量的一致性(即是否位于平面片同一侧)。更为具体的，可借助拓扑学相关概念来解释，如附 图3所示，其中(a)部分表示两个2维单纯形的方向(orientation of 2-simplex)，(b)部分表 示两个相容的2维单纯形(two coherent 2-simplex)，(c)部分表示两个不相容的2维单纯形(two  uncoherent 2-simplex)，(d)部分表示两个相容的平面片(two coherent facets)。在拓扑学中，采 用v2v0v1来表达2维单纯形(2-simplex)的方向。2-simplex作为一种特殊的平面片(Facet)，它 的任意两个顶点作偶数次置换(displace，拓扑学中称偶置换)，2-simplex的方向不变。如附 图3(a)中的v2v0v1,v0v1v2,v1v2v0都是左侧2-simplex的方向，分别为原始的方向、第一次置 换的方向(the first time)、第二次置换的方向(the second time)；而右侧2-simplex的方向是 v0v2v1，无论多少次偶置换，都无法形成左侧2-simplex的方向。2-simplex的边界是边，两个 邻接的2-simplex具有唯一的公共边，判断该公共边在这两个2-simplex中的走向：若走向相 反，则称这两个2-simplex相容，如附图3(b)所示；若走向相同，则称这两个2-simplex不相 容，如附图3(c)所示。平面片是二维非单纯复形(non 2-simplicial complex)的一种，其不满足偶 置换特征，但是同样可借助其边界的方向来判断平面片的相容性：平面片的边界是边，两个 邻接平面片可能存在多处公共边，任意选取其中一处公共边，判断该公共边在这两个平面片 中的走向：若走向相反，则称这两个平面片相容，如附图3(d)所示；若走向相同，则称它们 不相容。

在拓扑学中，二维单纯复形(2-simplicial complex)也称为组合曲面(简称ComSurface)，如 下判断组合曲面是否可定向：在该组合曲面中，判断任意两个相邻2-simplex(即三角形)是 否相容(该方法已如上所述)：若相容，则该组合曲面可定向；否则，该组合曲面不可定向。 只有针对可定向的组合曲面，才能进一步判断组合曲面之间的相容性。更为具体的，针对两 个可定向的组合曲面，它们之间的关系可能相容可能不相容，但沿着公共交线(1-simplex的 集合)发生的相容情况一定是统一的。故而，可选取公共交线中的任意一处一维单纯形 1-simplex，判断两个邻接2-simplex是否相容：若这两个2-simplex相容，则代表两个组合曲 面相容；若这两个2-simplex不相容，则代表两个组合曲面不相容。如附图4(a)所示，黑色弯 曲环状箭头表示2-simplex中边的环绕方向，标记1,2,3,4为两个组合曲面的公共交线，左边的 组合曲面由14个2-simplex构成，且其中任意两个相邻2-simplex相容，故而该组合曲面可定 向；右边的组合曲面由13个2-simplex构成，且其中任意两个2-simplex相容，故而该组合曲 面可定向。左边和右边的组合曲面沿着公共交线一致保持不相容，故而两个组合曲面不相容。

以上阐述了二维单纯形(2-simplex)之间、平面片(Facet)之间、组合曲面(ComSurface)之间 如何判断相容性。针对本发明所述的曲面片，其由平面片构成；平面片比二维单纯形复杂， 曲面片比组合曲面片复杂，借鉴以上思想。如下判断曲面片之间相容性：

在曲面片中，任意两个相邻平面片如果相容，则该曲面片可定向；否则，该曲面片不可 定向。可定向的曲面片也称合格的曲面片。同样的，针对两个可定向的曲面片，它们之间可 能相容可能不相容，但不会沿着公共交线(边的集合)发生既相容又不相容的情况。同样的， 可选取公共交线中任意一处边，判断两个邻接平面片是否相容：若这两个平面片相容，则代 表两个曲面片相容；若这两个平面片不相容，则代表两个曲面片不相容。如附图4(b)所示， 总共存在3个曲面片，左边曲面片由平面片F4和F5构成，且F4和F5相容，故左边曲面片 可定向；右边曲面片由平面片F2和F3构成，且F2和F3相容，故右边曲面片可定向；中间 曲面片仅由平面片F1构成，该曲面片总是可定向。左边和右边曲面片沿着公共交线(标记1) 一直保持不相容，故这两个曲面片不相容；左边和中间曲面片沿着公共交线(标记2)一致保持 相容，故这两个曲面片相容；中间和右边曲面片沿着公共交线(标记为3)一致保持不相容，故 这两个曲面片不相容。值得注意的是，左边与右边曲面片的公共交线(标记为1)是一条多部件 曲线，其所有连通分支保持了一致的相容性。

由上可见，相容性可概括如下：针对两个可定向曲面，判断两者分别包含的2维基元中 边环绕方向(顺时针或逆时针)是否一致。

总结而言，比较基于平面片构体与基于曲面片构体，两者在原理上相似，包括：(1)平面 片中构造边的环绕顺序并不重要，即构体时平面片的构造边可以无序；重要的是，根据当前 平面片及其方向，能够找到正确的最邻近平面片，进而递归链接所有相关最邻近平面片从而 封闭最小体。(2)类似的，曲面片中边缘曲线的环绕顺序并不重要，即构体时曲面片的边缘曲 线可以无序；重要的是，根据当前曲面片及其方向，能够找到正确的最邻近曲面片，进而递 归连接所有相关最邻近曲面片从而封闭最小体。

尽管如此，较之基于平面片构体，基于曲面片构体更复杂，即平面片是一类特殊的曲面 片，它只包含一个面片成员，所以不存在平面片本身不可定向，即平面片总是可定向(合格)； 相反的，曲面片往往包含多个面片成员，无论是由2-simplex构成的组合曲面，还是由多个平 面片构成的曲面片，都需要考虑弯曲面片本身是否可定向(是否合格)。总结而言，本文所提 出的曲面片是一种用于构体任务的通用曲面片，用于构造曲面片的平面片可退化为二维单纯 形，而本文提出的曲面片可退化为拓扑学中的组合曲面。

遵从以上相容性判断原理，构造彼此之间相容的曲面片，作为下一步构体操作的输入条 件。这称为第一阶段。完成以上操作，则给予构体操作的输入曲面片都是合格的，具体构体 步骤可以参照“一种地理空间实体构建方法及系统”专利中所述如下归纳：从初始曲面片出发， 通过曲面片排序找到最邻近曲面片，如此迭代直至封闭三维实体。这称为第二阶段。

无论是第一阶段还是第二阶段，涉及的基元之间拓扑关系非常重要。针对“完全的三维数 据模型”(由“基于平面片的三维数据模型”和“基于曲面片的三维数据模型”共同构成)中的各 类基元，可以按照基元的维数分类：0维基元包括节点、曲线节点；1维基元包括边、曲线、 环、洞；2维基元包括平面片、曲面片；3维基元包括体。其中，真正描述几何信息的基元只 有节点和曲线节点。其余基元都主要用于描述拓扑信息，称拓扑基元，包括：

(i)拓扑基元对于同维基元的引用。两者往往体现聚合关系，如环和边，洞和曲线；

(ii)拓扑基元对于低维基元的引用。两者往往体现相接关系，如边和节点，曲线和曲线节点；

(iii)拓扑基元对于高维基元的引用。两者往往体现相接关系，如曲线的隶属曲面片集合，它们 往往由(i)和(ii)衍生而来。

针对以上(i)与(ii)中基元之间的引用，采用如下规则命名：(1)以Ref1_开头命名，当基元 被边引用；(2)以Ref2_开头命名，当基元被曲线引用；(3)以Ref3_开头命名，当基元被环引 用；(4)以Ref4_开头命名，当基元被洞引用；(5)以Ref5_开头命名，当基元被平面片引用；(6) 以Ref6_开头命名，当基元被曲面片引用；(7)以Ref7_开头命名，当基元被体引用。

特别的，针对Ref1(边对节点的引用)、Ref3a(环对于边的引用)、Ref5a(平面片对于环的引 用)这3条引用，是用于构体任务的最初始条件，称“初始引用集合”。还有，针对Ref2a(曲线 对于边的引用)、Ref2b(曲线对于曲线节点的引用)、Ref4a(洞对于曲线的引用)、Ref6a(曲面片 对于平面片的引用)、Ref6b(曲面片对于洞的引用)、Ref7a(体对于曲面片的引用)这6条引用关 系，都是后者描述前者的本质特征(包括内部和外部信息)，称为“特征引用集合”。“初始引用 集合”与“特征引用集合”共同构成“最简引用集合”，也称“原子引用集合”，其中每项称“最简引 用”或“原子引用”。

进一步的，更多引用关系可由“原子引用”互相组合获得，这样的引用称“详细引用”，这样 的组合方式称“推导路径”。所有的“详细引用”形成“详细引用集合”，包括：Ref7b(体对于洞的 引用)；Ref7c(体对于曲线的引用)；Ref7d(体对于曲线中边的引用)；Ref7e(体对于曲线中所有 点的引用)；Ref7f(体对于曲线中曲线节点的引用)；Ref7g(体对于所有平面片的引用)；Ref7h(体 对于所有环的引用)；Ref7i(体对于所有边的引用)；Ref7j(体对于所有节点的引用)；Ref6c(曲 面片对于曲线的引用)；Ref6d(曲面片对于曲线中边的引用)；Ref6e(曲面片对于曲线中所有点 的引用)；Ref6f(曲面片对于曲线中曲线节点的引用)；Ref6g(曲面片对于所有环的引用)； Ref6h(曲面片对于所有边的引用)；Ref6i(曲面片对于所有节点的引用)；Ref5b(平面片对于边 的引用)；Ref5c(平面片对于节点的引用)；Ref4b(洞对于曲线中边的引用)；Ref4c(洞对于曲线 中所有点的引用)；Ref4d(洞对于曲线中曲线节点的引用)；Ref4e(洞对于所有边的引用)； Ref4f(洞对于所有节点的引用)；Ref3b(环对于所有节点的引用)；Ref2c(曲线对于所有节点的 引用)。

针对具体推导过程，“推导路径”是无向的，它只表示“详细引用”由哪些“原子引用”构成。 针对同一条“详细引用”，其“推导路径”可能具有多条。定义由“详细引用”得到“原子引用”组合 的过程，称“正向路径”；定义由“原子路径”组合得到“详细引用”的过程，称“逆向路径”。“正 向路径”和“逆向路径”的定义是为了帮助获取“推导路径”。针对每条“详细引用”，以下给出了 其中1条“正向路径”：

Ref7b＝Ref7a+Ref6b

Ref7c＝Ref7b+Ref4a＝(Ref7a+Ref6b)+Ref4a

Ref7d＝Ref7c+Ref2a＝(Ref7a+Ref6b+Ref4a)+Ref2a

Ref7e＝Ref7d+Ref1＝(Ref7a+Ref6b+Ref4a+Ref2a)+Ref1

Ref7f＝Ref7c+Ref2b＝(Ref7a+Ref6b+Ref4a)+Ref2b

Ref7g＝Ref7a+Ref6a

Ref7h＝Ref7g+Ref5a＝(Ref7a+Ref6a)+Ref5a

Ref7i＝Ref7h+Ref3a＝(Ref7a+Ref6a+Ref5a)+Ref3a

Ref7j＝Ref7i+Ref1＝(Ref7a+Ref6a+Ref5a+Ref3a)+Ref1

Ref6c＝Ref6b+Ref4a

Ref6d＝Ref6c+Ref2a＝(Ref6b+Ref4a)+Ref2a

Ref6e＝Ref6d+Ref1＝(Ref6b+Ref4a+Ref2a)+Ref1

Ref6f＝Ref6c+Ref2b＝(Ref6b+Ref4a)+Ref2b

Ref6g＝Ref6a+Ref5a

Ref6h＝Ref6g+Ref3a＝(Ref6a+Ref5a)+Ref3a

Ref6i＝Ref6h+Ref1＝(Ref6a+Ref5a+Ref3a)+Ref1

Ref5b＝Ref5a+Ref3a

Ref5c＝Ref5b+Ref1＝(Ref5a+Ref3a)+Ref1

Ref4b＝Ref4a+Ref2a

Ref4e＝Ref4b＝Ref4a+Ref2a

Ref4f＝Ref4c＝Ref4b+Ref1＝(Ref4a+Ref2a)+Ref1

Ref4d＝Ref4a+Ref2b

Ref3b＝Ref3a+Ref1

Ref2c＝Ref2a+Ref1

在确定“正向路径”之后，“逆向路径”也随之确定，“推导路径”可以通过“逆向路径”中各个 “原子引用”之间的组合获得。例如，以Ref7e为例，

其正向路径为Ref7e＝Ref7d+Ref1＝(Ref7a+Ref6b+Ref4a+Ref2a)+Ref1

其逆向路径为Ref7a+Ref6b+Ref4a+Ref2a+Ref1＝Ref7e

其推导路径有多条，包括：

(Ref7a+Ref6b+Ref4a+Ref2a)+Ref1＝Ref7d+Ref1＝Ref7e或

(Ref7a+Ref6b+Ref4a)+(Ref2a+Ref1)＝Ref7c+Ref2c＝Ref7e或

(Ref7a+Ref6b)+(Ref4a+Ref2a+Ref1)＝Ref7b+Ref4c＝Ref7e或

Ref7a+(Ref6b+Ref4a+Ref2a+Ref1)＝Ref7a+Ref6i＝Ref7e或

Ref7a+(Ref6b+Ref4a+Ref2a)+Ref1＝Ref7a+Ref6h+Ref1＝Ref7e

尽管如此，“详细引用”包括哪些“原子引用”才是研究重点，因为“原子引用”与“数据库中 范式设计”息息相关(即以上引用的细分对应数据库中关系模式的细分，严格的范式设计能够 避免数据库中插入、修改、删除引起的各种异常)。此外，值得注意的包括：

(i)对于环的引用(即Ref7h,Ref6g)：环是一类1维基元，它应有自己的唯一标志码。但在这里， 认为环与平面片的生存周期一致(即平面片不存在了，其构造环也不存在了，不同于平面片 消失但构造边仍然存在)，所以可以不显式存储环对象。尽管如此，针对环的信息，隐含在“平 面片对于边的引用”和“平面片只有唯一外环和0至多个内环的约束”中。

(ii)对于曲线节点的引用(即Ref7f,Ref6f,Ref4d)：曲线可能是多部件曲线，所以可能有多对曲 线节点，同样没有显式存储曲线节点，而是通过内存分析获得。曲线节点定义后面详述。

总结而言，针对第一阶段，主要完成Ref2a、Ref2b、Ref4a、Ref6a、Ref6b这些引用的构 造；针对第二阶段，主要完成Ref7a该引用的构造。这两个阶段共同组成了“基于曲面片实现 三维实体的拓扑自动构建”。

本发明技术方案可采用计算机软件方式支持自动运行流程。以下结合实施例详细说明本 发明技术方案。

为了方便与曲面片等对象对比，首先回顾“基于平面片的三维数据模型”中基元定义：

(1)节点(Point)：节点是嵌入在三维空间中的一类0维基元，它记录了X,Y,Z坐标。Point在数 据库中一般也记为Node，Point在欧拉公式中一般也记为Vertex。

(2)边(Edge)：边是嵌入在三维空间中的一类1维基元，它是由起始节点和终止节点封闭的一 条有向直线段。边的物理方向由起始节点指向终止节点。边的起始节点和终止节点不能够是 同一个点。边通常也记为弧度。边同胚于1维流形。

(3)环(Ring)：环是嵌入在三维空间中的一类1维基元，它由至少3条边封闭而成。这些边形 成一个集合，称为环的构造边集合(R.edges)。包含于这些边中的所有节点，称环的构造节点 集合(R.vertices)。环是1维基元，边是1维基元，且环是边的聚合。环是封闭的，即构成环的 第一条边和最后一条边具有公共节点。尽管以上没有显式约束环的所有边必须位于同一个平 面上，但直接引用环对象的只有平面片对象，而平面上所有点在同一个平面上，所以默认环 的所有构造边位于同一个平面上。环通常也记为循环(Loop)或圈(Cycle)。

(4)平面片(Facet)：平面片是嵌入于三维空间中的一类2维基元，它是由唯一外环、0至多个 内环封闭而成的区域。平面片的边界是环。平面片的唯一外环上的边和所有内环上的边共同 形成一个集合，该集合称为平面片的构造边集合(F.edges)。以上边中包含的所有节点，称平 面片的构造节点集合(F.vertices)。一个平面片包含至少3条构造边。平面片是相对简单多边形， 可以是凸的，可以是凹的。当一个平面片只由3条边构成时，平面片退化为三角形。值得注 意的是，不允许平面片的内环与外环接触，如果两者接触，则原来的内环和唯一外环消失， 产生新的基元。平面片同胚于2维流形，而环不一定同胚于1维流形。

平面片具有法向量(normal vector)。在平面片的任意一个环内，其构造边排列是有序的， 即构造边集合有一定的走向(trend)，即前一条边与后一条边一定有公共节点；同时，每条边 本身有物理方向，即从边的起始节点指向边的终止节点。但在同一个环内，并不是所有边的 方向都一致，也即前一条边的终止节点与后一条边的起始节点并不一定是同一个点。因此， 需要一个统一规则来决定平面片的法向量，通常采用右手定则(即四指方向为平面片中唯一 外环中边的环绕方向，大拇指方向为法向量方向)。进一步的，当平面片的唯一外环的边集合 确定后，该边集合的环绕方向就与每条边的本身方向作比较，如果一样则该条边标记“+”，否 则该边标记“-”。任一平面片都具有两侧。因为每个平面片都有一个所在超平面片，该超平面 将三维空间分为两部分，一般把平面片法向量所在的一侧称为正面，把异于平面片法向量所 在的一侧称为背面。

(5)体(Body)：体是嵌入三维空间中的一类3维基元，它由至少4个平面片封闭。体的边界是 平面片，它们形成一个集合，称体的构造平面片集合(B.facets)。体内不存在其它基元，也称 最小体。一个平面片的法向量(normal vector)只有一个，具有客观的计算数值。与此不同，一 个平面片的方向(dir)是主观定义的，而且认为有两个，即后向(标记为“1”)和前向(标记为“2”)。 其中，针对某个平面片而言，当该平面片的法向量指向某个体的外部时，此时的平面片(注 意：不用“该平面片”，而用“此时的平面片”)称为前向平面片(即使用了平面片的正面)，该体 称为后向体；当该平面片的法向量指向某个体的内部时，此时的平面片(注意：不用“该平面 片”，而用“此时的平面片”)称为后向平面片(即使用了平面片的背面)，该体称为前向体。体 可以是凸的，可以是凹的，可以有亏格(也称穿洞)。体通常也记为Solid。

此外，本发明重点阐述的“基于曲面的三维数据模型”中包含的各类基元，定义如下：

(6)曲面片(Surface)：在三维空间中引入一类新的2维基元，其类似于平面片，称为曲面片。 在拓扑学中，二维流形即称曲面，如平环、Mobius环等；其中，没有边界点的、紧致的、连 通的曲面称为闭曲面。尽管如此，拓扑学中更注重曲面的边界信息，很少讲曲面给予具体表 达与实现。本发明提出的“曲面片”满足以上拓扑学中对于曲面的定义，同时附加以下额外约 束：由所有的一致(consistent)平面片(facet)构成的单连通分支，称为曲面片(Surface)。“一致” 体现在平面片集合具有一致的前向体与后向体；“所有”体现在该连通分支中包含所有的一致 平面片；之所以称”单连通分支”，是因为由所有的一致平面片构成的集合可能具有多个连通 分支，此时有如下选择：(i)将所有连通分支定义为一个曲面片；(ii)将每个连通分支定义为一 个曲面片。考虑到曲面片的方向(dir)，在这里只选择定义(ii)(即定义(i)中各个连通分支的dir 可能不一致，而定义(ii)曲面片由于只是单个连通分支故而可设置一致)。

当一个曲面片只由1个平面片构成时，该平面片的法向量就是该曲面片的法向量。但大 多数情况下，一个曲面片由多个平面片构成，此时曲面片不存在法向量。在此，称曲面片没 有法向量，这是更为严格的约束，并不影响结果。任意一个曲面片都具有两侧，尽管曲面片 没有法向量，但仍然可以区分两侧。构成曲面片的所有平面片会构成一个组合超平面片，该 组合超平面将三维空间分成两部分。因为定义曲面片时指出构成该曲面片的所有平面片具有 一致的前向体(与后向体)，故而所有的平面片法向量只会统一位于其中一侧，一般把法向量 所在的一侧称为曲面片的正面，把另一侧称为曲面片的背面。这样的曲面片也即合格的曲面 片(如上所述)。

针对曲面片包含的成员，可总结如下：

(i)曲面片的构造平面片集合(S.facets)：曲面片所有平面片形成的集合。

(ii)曲面片的构造边集合(S.edges)：以上所有平面片上的边形成的集合。

(iii)曲面片的边缘平面片集合(S.borderFacets)：由一类平面片形成的集合，称为该曲面片的边 缘平面片集合，该集合中的每个平面片既隶属于曲面片的构造平面片集合，又包含该曲面片 的至少一条边缘边。

(iv)曲面片的边缘曲线集合(S.borderCurves)：一个曲面片的所有洞包含的曲线，称为该曲面片 的边缘曲线集合。当曲面片是闭曲面片时，不存在洞，所以不存在边缘曲线。

(v)曲面片的边缘边集合(S.borderEdges)：在一个曲面片的所有构造边中，那些有2个以上相 接平面片的边形成一个集合，称为该曲面片的边缘边集合。当曲面片是闭曲面片时，不存在 边缘边。曲面片边缘边集合的作用：构造该曲面片的洞。曲面片边缘边集合等价于该曲面片 的所有洞的所有构造曲线的所有构造边形成的集合。

(vi)曲面片的边缘节点集合(S.borderVertices)：一个曲面片的所有边缘边包含的所有节点形成 一个集合，称为该曲面片的边缘节点集合。当曲面片是闭曲面片时，不存在边缘节点。

(7)洞(Hole)：在三维空间中引入一类新的1维基元，其类似于环，称为洞。洞是曲面片的边 界，好比环是平面片的边界。一个洞由至少1条曲线封闭而成，这些曲线称为洞的构造曲线 集合(H.curves)。洞是封闭的，即若洞由多条曲线构成，第一条曲线与最后一条曲线必然有公 共节点；若一个洞只由1条曲线(该条曲线由至少3条边构成)封闭，则该条曲线一定是闭 曲线。洞可以看作是边的集合，这些边称洞的构造边集合(H.edges)。与环类似的，洞也允许 发生自接触。洞不一定同胚于1维流形。

(8)曲线(Curve)：在三维空间中引入一类新的1维基元，它类似于边，称为曲线。在洞中，具 有相同隶属曲面片集合的所有边形成一个集合，称为曲线。“隶属曲面片集合”指的是洞中的 边同时隶属于多个曲面片，这些曲面片形成一个集合，称为该边的隶属曲面片集合。“所有” 体现在该集合是隶属曲面片集合相同的边的最大集合。曲线中每条边的隶属曲面片集合相同， 因此边的隶属曲面片集合也称曲线的隶属曲面片集合(C.belongSurfaces)。曲线包含的所有边 形成一个集合，称该曲线的构造边集合(C.edges)。这些边上所有节点构成的集合，称曲线的 构造节点集合(C.vertices)。曲线是1维基元，边是1维基元，且曲线是边的聚合。若一条曲 线由至少3条边封闭形成一个洞，此时的曲线称为闭曲线(简写为cC,closed Curve)。直观地 看，只有曲面片与曲面片相交时，才会有新曲线产生。曲线同胚于1维流形。

一条曲线不一定是直接连通的，即一条曲线可能存在多个连通分支。针对具有多个连通 分支的一条曲线，存在如下两种方法约束：(1)不对该曲线细分，即将具有多个连通分支的一 条曲线认为只是1条曲线，简称多部件曲线；该曲线存在多对首末曲线节点。(2)对该曲线细 分，即将每个连通分支作为一条曲线；如此保证每条曲线都是直接连通的；这样的每条曲线 只有1对曲线节点，其中一个节点称曲线起始节点(C.beginCurveEnd)，另一个节点称曲线终 止节点(C.terminateCurveEnd)。换言之，细分后的曲线较之细分前的曲线，多了如下额外约束： 将曲线所在洞的边依次相连，形成一条路径，沿着该路径，同一曲线内部不能够存在其它曲 线。在这里，默认选择第二种曲线定义(即细分后的曲线)。以上两种定义的具体构造方法之 后都详述。

若一条曲线只有1条边构成，该边的物理方向即该曲线的物理方向；但大多数情况下， 一条曲线由多条边构成，此时认为该曲线不具有物理方向。以下统称曲线不具备物理方向， 如此约束更为严格，但不影响结果。在曲面片的任意一个洞内，曲线排列有一定走向，即前 一条曲线与后一条曲线一定有公共节点。尽管如此，在同一个洞内，两条相邻曲线并不一定 首尾相接，即公共节点可能既是前一条的起始节点也是后一条的起始节点。在大多数情况下， 在同一个洞内所有构造曲线并不一定位于同一平面上(当该曲面片只包含一个平面片时，则 该曲面片的洞的所有构造曲线一定位于同一平面)。

(9)曲线节点(Curve End)：在三维空间中引入一类新的0维基元，其类似于三维点(3D Point)， 称曲线节点。曲线节点是曲线的边界，好比节点是边的边界。若未给予曲线细分，则1条多 部件曲线存在多对曲线节点；若给予曲线细分，则1条曲线只存在1对曲线节点。当曲线只 有1条边构成时，该条边的起始节点就是该曲线的起始节点，该条边的终止节点就是曲线的 终止节点。当曲线是闭曲线时，曲线的起始节点和终止节点是同一个节点，它可以是闭曲线 上任意一个构造节点。

(10)体(Body)的补充信息：体由至少4个平面片封闭而成，此时体的边界是平面片。同样的， 可以认为体由至少1个曲面片封闭而成，此时体的边界是曲面片。一个曲面片并不存在客观 的法向量(normal vector)。尽管如此，主观认为曲面片的方向(dir)仍然存在，而且认为方向有 两个，即后向(标记为“1”)和前向(标记为“2”)。其中，针对某曲面片而言，当该曲面片中任意 一个构造平面片的法向量指向某体的体外时，此时的曲面片(注意：用“此时的曲面片”，而 非“该曲面片”)称为前向曲面片(即使用了曲面片的正面)，该体称为后向体；当该曲面片中 的任意一个构造平面片的法向量指向某体的体内时，此时的曲面片称为后向曲面片(即使用 了曲面片的背面)，该体称为前向体。之所以认为曲面片的方向有两个，是因为：一个曲面片 既是体A的前向曲面片，也是体B的后向曲面片，体A与体B通过该曲面片邻接。

事实上，第一阶段涉及的引用已经包含于上述定义之中。附图5给出了基于关系模式的“面 向地籍的三维空间数据模型(同时包含了平面片部分和曲面片部分)”的表结构设计，其中虚 线左侧为平面片相关部分，为现有技术已经提供的；虚线右侧为曲面片相关部分，为本发明 中提

如附图5所示，在左侧(平面片相关部分)中，几何信息表(Table GEOM_NODE,缩写为 GN)中NODE_ID(NID),X_COORD(X),Y_COORD(Y),Z_COORD(Z)分别代表节 点的唯一标志码、节点X坐标、节点Y坐标、节点Z坐标；边与节点的拓扑信息表(Table  TOPO_EDGE_NODE,缩写为TEN)中EDGE_ID(EID),BEGIN_NODE_ID(BN), END_NODE_ID(EN)分别代表边的唯一标志码、起始节点的唯一标志码、终止节点的唯一 标志码；平面片与外环中边的拓扑信息表(Table TOPO_FACET_OUTER_EDGE,缩写为TFOE) 中FACET_ID(FID),OUTER_LOOP_EDGE(OLE)分别代表平面片的唯一标志码、外环中 边的唯一标志码；平面片与边的拓扑信息表(Table TOPO_FACET_EDGE,缩写为TFE)中 FACET_ID(FID),FACET_EDGE_ID(FE),NEXT_EDGE_ID(FNE)分别代表平面片的唯 一标志码、平面片中前一条边的唯一标志码、平面片中下一条边的唯一标志码。

如附图5所示，在右侧(曲面片相关部分)中，曲线与起始边的拓扑信息表(Table  TOPO_CURVE_BEGIN_EDGE,缩写为TCBE)中CURVE_ID(CID),BEGIN_EDGE_ID(CBE) 分别代表曲线的唯一标志码、曲线中起始边的唯一标志码；曲线与边的拓扑信息表(Table  TOPO_CURVE_EDGE,缩写为TCE)中CURVE_ID(CID),CURVE_EDGE_ID(CE), NEXT_EDGE_ID(CNE)分别代表曲线的唯一标志码、曲线中前一条边的唯一标志码、曲线 中下一条边的唯一标志码；洞与起始曲线的拓扑信息表(Table TOPO_HOLE_BEGIN_CURVE, 缩写为THBC)中HOLE_ID(HID),BEGIN_CURVE_ID(HBC)分别代表洞的唯一标志码、 洞中起始曲线的唯一标志码；洞与曲线的拓扑信息表(Table TOPO_HOLE_CURVE,缩写为THC) 中HOLE_ID(HID),HOLE_CURVE_ID(HC),NEXT_CURVE_ID(HNC)分别代表洞的 唯一标志码、洞中前一条曲线的唯一标志码、洞中下一条曲线的唯一标志码；曲面片与平面 片的拓扑信息表(Table TOPO_SURFACE_FACET,缩写为TSF)中SURFACE_ID(SID), FACET_ID(FID)分别代表曲面片的唯一标志码、平面片的唯一标志码；曲面片与洞的拓扑 信息表(Table TOPO_SURFACE_HOLE,缩写TSH)中SURFACE_ID(SIF),HOLE_ID(HID) 分别代表曲面片的唯一标志码、洞的唯一标志码；体与曲面片的拓扑信息表(Table  TOPO_BODY_SURFACE,缩写为TBS)中SURFACE_ID(SID),SURFACE_FRONT_BODY(SFB), SURFACE_BACK_BODY(SBB)分别代表曲面片的唯一标志码、前向体的唯一标志码、后向体 的唯一标志码；体的几何信息表(Table GEOM_BODY,缩写为GB)中BODY_ID(BID),VOLUME, XMIN,YMIN,ZMIN,XMAX,YMAX,ZMAX分别代表体的唯一标志码、体积、X最小值、Y 最小值、Z最小值、X最大值、Y最大值、Z最大值。

此外，Table META_INFO为元数据信息表，描述了以上所有表中的元数据信息，其中 TABLE_Name(缩写为TN),MAX_ID(MID)分别代表基元类型、每种类型基元的唯一标志码的 起始数值。更为具体的，节点(NODE)的唯一标志码以100,0000起始；边(EDGE)的唯一标志 码以300,0000起始；平面片(FACET)的唯一标志码以400,0000起始；曲线(CURVE)的唯一标 志码以500,0000起始；洞(HOLE)的唯一标志码以700,0000起始；曲面片(SURFACE)的唯一 标志码以800,0000起始；体(BODY)的唯一标志码以900,0000起始。

图5中，PK代表主键(即Primary Key的缩写)，NOT NULL代表非空(即不能取空值)、 NUMBER代表数值类型。

实施例中，针对基于曲面片实现三维实体的拓扑自动构建，总共分为9个大步骤，具体 包括：步骤1.初次搜索曲面片(完成引用Ref6a和Ref6b)、步骤2.翻转曲面片中不相容平面 片(完善引用Ref6a)、步骤3.再次搜索曲面片(完善引用Ref6a)、步骤4.搜索曲面片包含的 洞(简称搜索洞，完成引用Ref4a)、步骤5.搜索洞包含的曲线(简称搜索曲线，完成引用Ref2a)、 步骤6.搜索曲线包含的曲线节点(简称搜索曲线节点，完成引用Ref2b)、步骤7.搜索无穷远 体的边界上的任意一个曲面片、步骤8.搜索无穷远体的边界、步骤9.搜索最小体集合。其中， 步骤1-6共同完成构体任务涉及的所有基元(包含曲面片、洞、曲线、曲线节点)的自动构 造，等价于第一阶段；而步骤7-9通过以上搜索得到的基元共同完成构体的具体操作(共同 完成引用Ref7a)，等价于第二阶段。最后，可以实现给予构体的有效性验证。实施例中各大 步骤，具体实现如下：

步骤1.初次搜索曲面片

基于给定的平面片集合寻找曲面片是一个任务，已知数据包括：(1)给定的平面片集合， (2)平面片集合中每个平面片的法向量，(3)平面片集合中每个平面片的所有拓扑和几何信息 (平面片和环的拓扑信息，环与边的拓扑信息，边与节点的拓扑信息，节点的几何信息)。未 知数据包括：(1)每个曲面片信息，(2)曲面片集合(即存在多少曲面片)。具体算法流程如下：

(1)针对给定的平面片集合中的每个平面片，标记为“未使用”；

(2)创建一个新的曲面片对象和当前平面片集合，内容分别为空；针对当前平面片集合进行初 始化；

(3)针对当前平面片集合中的每个平面片，将其加入(2)中创建的新曲面片对象，并标记该平面 片为“已使用”；

(4)针对当前平面片集合，创建推进平面片集合；

(5)针对当前平面片集合中的每个平面片的每条边，在给定的平面片集合中剩余未使用的平面 片中计算该边的所有相接平面片，筛选出那些只有1个相接平面片(除当前平面片本身以外) 的情况，并将这些唯一相接平面片加入推进平面片集合中；

(6)清空当前平面片集合，将推进平面片集合作为新的当前平面片集合；之后，清空推进平面 片集合；

(7)返回(3)，基于当前新的当前平面片集合，重复步骤(3)-(7)，直至计算得到的推进平面片集 合为空，进入(8)；此时，以上曲面片的所有构造平面片都搜索完毕；

(8)返回(2)，基于重新初始化的当前平面片集合，重复步骤(2)-(8)，直至平面片集合中每个平 面片都被“已使用”；此时，所有曲面片的所有构造平面片都搜索完毕，结束步骤1。

值得注意的是，每次进入(3)时，给定的平面片集合都会更新。尽管如此，无论如何更新， 其中的平面片始终可以分为如下两类：(i)usedE(即标记为“已使用”的平面片)；(ii)unusedE(即 标记为“未使用”的平面片)。即更新内容为平面片的标记。同时，每次进入(2)针对当前平面片 集合需要初始化时，只随机选择给定的平面片集合中的1个平面片用于初始化，该平面片称 为起始平面片(beginE)。beginE必须是unusedE。之后每次迭代(即在(7)之后返回重复步骤 (3)-(7))时，当前平面片集合的大小一般都大于1。

更为详细的，在步骤1(初次搜索曲面片)，针对从当前平面片寻找推进平面片的过程， 可以具体采用现有计算几何算法中常用的广度优先遍历(BFS,Breadth-first Search)或深度优先 遍历(DFS,Depth-first Search)策略。本发明后面所述的具体实施案例采用深度优先遍历(DFS) 策略。

步骤2.翻转曲面片中不相容平面片

翻转曲面片中的不相容平面片，其算法流程如下：

(1)根据当前平面片集合(strip_facets)和当前推进边集合(strip_edges)寻找相接平面片集合 (next_strip_facets)，具体如下：针对相接于当前推进边集合(strip_edges)的所有平面片，去除 当前平面片集合(strip_facets)，剩余的即相接平面片集合(next_strip_facets)。

(2)计算下一批推进边集合(next_strip_edges)。其中，相接平面片集合包含的所有边，形成一个 集合，称所有边集合(all_edges)。所有边集合由当前推进边集合(strip_edges)、公共边集合 (common_edges)、边界边集合(boundary_edges)、下一批推进边集合(next_strip_edges)共同组成。 具体的，计算下一批推进边集合分为如下小步骤：

(i)首先，从所有边集合(all_edges)中去除当前推进边集合(strip_edges)；

(ii)之后，在剩余的所有边集合中寻找公共边集合(common_edges)，每条公共边是当前平面片 集合(strip_facets)中任意两个不同平面片的公共边。找到公共边集合(common_edges)后，从剩 余的所有边集合中去除公共边集合；

(iii)在剩余的所有边集合中寻找边界边集合(boundary_edges)，每条边界边包含于相接平面片 集合，又隶属于以上曲面片的边缘边集合(S.borderEdges)。找到边界边集合(boundary_edges) 后，从剩余的所有边集合中去除边界边集合(boundary_edges)。

此时，剩余的所有边集合就是下一批推进边集合(next_strip_edges)。

(3)针对相接平面片集合(next_strip_facets)中的每一个平面片，在当前平面片集合(strip_facets) 中计算与其邻接的任意一个平面片，判断两者的相容性：

(i)若两者相容，则不处理前者；

(ii)若两者不相容，则翻转前者；

值得注意的是，翻转操作只是改变平面片中边的排列顺序(即从任一指定视角望去，该 平面片的所有构造边的环绕顺序由逆时针转换为顺时针，或者由顺时针转换为逆时针)，而每 条边的本身性质(包括边的节点、边的物理方向)都未改变。处理完毕后，能够保证相接平 面片集合中任意两个存在邻接情况的平面片都相容。

(4)清空当前平面片集合(strip_facets)，把相接平面片集合(next_strip_facets)作为新的当前平面 片集合。之后，清空相接平面片集合。

(5)清空当前推进边集合(strip_edges)，把下一批推进边集合(next_strip_edges)作为新的当前推 进边集合。之后，清空下一批推进边集合。

(6)返回(1)，根据当前平面片集合(strip_facets)和当前推进边集合(strip_edges)，重复步骤(1)-(6)， 直至计算得到的下一批推进边集合为空。此时，该曲面片是“合格”的，即该曲面片上任意两 个邻接的平面片都相容。

值得注意的是，第一次进入步骤(1)时，只从该曲面片的步骤1所得初步搜索的构造平面 片集合中随机选择1个平面片初始化当前平面片集合，该平面片称为该曲面片的标准平面片 (sF)。标准平面片的作用：作为之后该曲面片上其余平面片是否应该翻转的比较依据。

第一次迭代时，当前平面片集合(first_strip_facets)只包含标准平面片：

first_strip_facets＝sF(a random facet in the Surface)

此时，可能存在边界边(first_boundary_edges)，但一定不存在公共边集合，也不存在前一 批推进边集合。计算标准平面片的所有边，去除边界边，剩余的即当前推进边集合：

first_strip_edges＝all_edges in first_strip_facets–first_boundary_edges

更为详细的，在步骤2的(2)中，针对从当前平面片寻找相接平面片的过程，可以具体采 用广度优先遍历(BFS)或深度优先遍历(DFS)。本发明后面所述的具体实施案例采用广度优先 遍历(BFS)策略。在这里，阐述其中采用广度优先遍历(BFS)策略实现步骤2的原理，如附图6 所示。在附图6中，原始数据为一个已经搜索得到的曲面片，该曲面片由多个平面片构成呈 现蜂窝状，每个平面片是六边形。当前平面片集合(strip_facets)由填充左斜线面块表示，当前 推进边集合(strip_edges)由标记为1的线条表示，公共边集合(common_edges)由标记为2的线 条表示，边界边集合(boundary_edges)由标记为3的线条表示，下一批推进边集合 (next_strip_edges)由标记为4的线条表示，相接平面片集合(next_strip_facets)由填充右斜线面 块表示。每次迭代中，当前平面片集合(strip_facets)和相接平面片(next_strip_facets)都在空间 形态上呈现条带波纹状。迭代过程即用不断更新的相接平面片代替为新的当前平面片集合从 而实现波纹依次扩散的过程。迭代初始时，起始(标准)平面片(first_strip_fact)选取最右 下角平面片(标记为f的面块)，此标准平面片包含起始边界边集合(first_boundary_edges，由标 记为fb的线条表示)；针对标准平面片包含的所有边，去除以上边界边集合，剩余的即起始推 进边集合(first_strip_edges，由标记为f的线条表示)。

步骤3.再次搜索曲面片

之所以需要再次寻找曲面片，是因为在经历了步骤2之后，翻转后的平面片与翻转前的 平面片已经不是同一个平面片对象，此时需要清空每个曲面片的所有内部成员，同时往曲面 片中填充相容的构造平面片集合，才能保证曲面片对于平面片的正确引用。

此处的已知数据为：(1)给定的平面片集合；(2)平面片集合中每个平面片的法向量；(3)平 面片集合中每个平面片的所有拓扑和几何信息(平面片和环的拓扑信息、环与边的拓扑信息、 边与节点的拓扑信息、节点的几何信息)。其中，此处与步骤1(初次搜索曲面片)相比，已 知数据(1)和(3)相同，已知数据(2)不同。

针对再次寻找曲面片的具体算法流程，与步骤1(初次搜索曲面片)的相同，得到后续使 用的曲面片集合。

步骤4.搜索洞

搜索曲面片中洞的过程等价于寻找曲面片边缘边集合中连通分支的过程，即曲面片中的 每个洞都构成一个连通分支，洞与洞非直接连通。对步骤3所得每个曲面片分别执行具体算 法流程如下：

(1)针对曲面片的边缘边集合中的每条边缘边，标记其为“未使用”；

(2)创建一个新的洞对象，其内容为空；

(3)创建当前边集合，其初始化内容为边缘边集合中的任意一条“未使用”的边缘边；

(4)针对当前边集合中的每条当前边，将其加入以上(2)建立的洞对象，并将该边标记为“已使 用”；针对当前边集合，创建对应的邻接边集合，其初始化内容为空；

(5)针对当前边集合中的每条当前边，寻找其邻接边：

(i)针对每条当前边的起始节点，寻找其所有相接边(除当前边自身以外)，如果存在包含于曲 面片的边缘边集合的相接边，将其加入邻接边集合；

(ii)针对每条当前边的终止节点，寻找其所有相接边(除当前边自身以外)，如果存在包含于 曲面片的边缘边集合的相接边，将其加入邻接边集合；

(6)清空当前边集合，将邻接边集合作为新的当前边集合；之后，清空邻接边集合；

(7)返回(4)，基于新的当前边集合，重复步骤(4)-(7)，直至寻找得到的邻接边集合为空，进入 (4)；此时，以上洞中所有边都搜索完毕得到当前洞的构造边集合；

(8)返回(2)，重复步骤(2)-(8)，创建新的洞对象并进行搜索，直至以上曲面片的边缘边集合中 每条边缘边都“已使用”；此时，以上曲面片中所有洞都搜索完毕，形成该曲面片的构造洞集 合。

步骤5.搜索曲线

如上所述，曲线定义分两种，即细分后曲线、未细分曲线，需分别进行处理。

针对曲面片集合包含的所有洞的所有曲线(细分后曲线)，具体算法流程如下：

(1)从步骤3所得曲面片集合中取一个曲面片为当前处理的曲面片；

(2)从曲面片的构造洞集合中取一个洞为当前处理的洞；

(3)针对当前洞的构造边集合中的每条边，标记为“未使用”；

(4)建立一个哈希表，用于存储当前洞中每条边，及其隶属曲面片集合；其中，当前洞中每条 边作为哈希表中”键”，该边的隶属曲面片集合作为哈希表该”键”的”值”；

(5)建立一个新的曲线对象，其内容为空；

(6)创建当前边集合，初始化内容为当前洞中任意一条“未使用”的边；同时，标记该边为标准 边(standard edge)，该边的隶属曲面片集合称为标准隶属曲面片集合(即标准边代入哈希表得 到)；

(7)针对当前边集合中每条当前边，标记其为”已使用”，并加入本次执行(5)建立的曲线对象中； 对于当前边集合，创建相应的邻接边集合，内容为空；

(8)针对当前边集合中每条当前边，寻找其所有邻接边，加入邻接边集合；

(i)针对当前边的起始节点，寻找属于该洞的构造边集合、具有标准隶属曲面片集合的所有相 接边；从中筛选只有2条相接边的情况，其中1条是当前边本身，另外1条称真正相接边， 并将真正相接边加入相接边集合；

(ii)针对当前边的终止节点，寻找属于该洞的构造边集合、具有标准隶属曲面片集合的所有相 接边；从中筛选只有2条相接边的情况，其中1条是当前边本身，另外1条称真正相接边， 并将真正相接边加入相接边集合；

(9)清空当前边集合，用邻接边集合替代作为新的当前边集合；之后，清空邻接边集合；

(10)返回(6)，基于新的当前边集合重复步骤(6)-(10)，直至寻找得到的邻接边集合为空；此 时，针对曲面片的构造洞集合中的一个洞的所有边搜索完毕；

(11)针对本次执行(5)建立的曲线对象的“隶属曲面片集合”属性，采用标准隶属曲面片集合赋 值；

(12)本次执行(5)建立的曲线对象真正构造完毕；

(13)返回步骤(5)重新建立新的曲线对象，重复步骤(5)-(13)，直至该洞的构造边集合中每条边 都”已使用”；此时，以上洞中所有曲线都搜索完毕，进入(14)；

(14)返回步骤(2)，取下一个洞作为新的当前洞，重复步骤(2)-(14)；直到当前处理的曲面片的 所有洞的所有曲线都搜索完毕，进入(15)；

(15)返回步骤(1)，取下一个曲面片为当前处理的曲面片，重复步骤(1)-(15)；直到所有曲面片 的所有洞的所有曲线都搜索完毕，结束步骤5。

针对曲面片集合包含的所有洞的所有曲线(未细分曲线)，具体算法流程如下：

(1)从曲面片集合中取一个曲面片作为当前处理的曲面片；

(2)从当前处理的曲面片的构造洞集合中取一个洞为当前洞；

(3)针对当前洞的构造边集合中的每条边，标记为“未使用”；

(4)建立一个哈希表，用于存储当前洞中每条构造边，以及该边的隶属曲面片集合；其中，当 前洞中每条边作为哈希表的“键”，该边的隶属曲面片集合作为哈希表中该“键”的“值”；

(5)建立一个新的曲线对象，其内容为空；

(6)从当前洞的构造边集合中，选择任意1条“未使用”的边，将其加入以上曲线，并将其标记“已 使用”；同时，标记该边为标准边(standard edge)，该边的隶属曲面片集合称为标准隶属曲面 片集合(即标准边代入哈希表得到)；

(7)从当前洞的构造边集合中，继续寻找“未使用”、具有标准隶属曲面片集合的一条边，标记 这样的边为相似边(similar edge)，将相似边加入以上曲线；

(8)返回步骤(7)找下一条相似边，直至不存在相似边；此时，以上曲线的所有边都搜索完毕；

(9)将标准隶属曲面片集合赋予本次执行(5)建立的曲线对象的隶属曲面片集合；

(10)本次执行(5)建立的曲线对象曲线构造完毕；

(11)返回步骤(5)重新建立新的曲线对象，重复步骤(5)-(11)，直至当前洞的构造边集合中每 条边都“已使用”；直到当前洞中所有曲线都搜索完毕，进入(12)；

(12)返回步骤(2)，取下一个洞作为新的当前洞，重复步骤(2)-(12)；直到当前曲面片的所有 洞的所有曲线都搜索完毕，进入(13)；

(13)返回步骤(1)，取下一个曲面片作为当前处理的曲面片，重复步骤(1)-(13)；此时，所有 曲面片的所有洞的所有曲线都搜索完毕，结束步骤5。

步骤6.搜索曲线节点

针对每条曲线，除了要寻找其构造边外，还要搜索出曲线节点。可在不同阶段进行：

(a)在曲线的所有构造边搜索完毕时统一搜索，只搜索一次；即在步骤5之后执行步骤6搜索 曲线节点；

(b)往曲线中每次增加一条构造边，就渐进式更新曲线的曲线节点。考虑到动态更新的情况， 也可以采用这种方式。在执行步骤5获取构造边的同时搜索曲线节点。

以上第一种方法是一种静态方法，以上第二种方法是一种动态方法。这两种方法的搜索 结果相同(即最终搜到得到的曲线节点是相同的)，利用的都是边与边之间的连通性特征，区 别在于前者直接体现最终搜索结果，后者详细体现了搜索过程。在这里，为详细体现整个搜 索过程，本发明采用第二种方法，其实例如附图8所示。其中，在大多数情况下，形成不闭 合曲线，如附图8中状态status1-status5所示；也有可能形成闭合曲线，如附图8中状态status6 所示。

总结而言，每次增加一条边，对原有边与节点的影响总共可能形成三种情况，如附图7 所示，即Case1(增加单独边)、Case2(追加边)、Case3(增加连通边)。其中，eNum是原边集中 包含的边个数，vNum是原边集中包含的节点个数，n是插入前准备新增边的个数。在这里， 以插入后事实上新增的边数与新增的节点数的极限比较来描述：

Case1(增加单独边)

其中n与eNum和vNum无关，即之后每次增加一条单独边，事实上 只新增1条边和2个节点，并不依赖于原先的边集合，极限Limit趋近于0.5，如附图7所示；

Case2(追加边)

其中n与eNum和vNum无关，即之后在原来基础上每追加一条边，事 实上只新增1条边和1个节点，并不依赖于原先的边集合，极限Limit趋近于1，如附图7所 示；

Case3(增加连通边)

其中n与eNum和vNum有关，即之后每次要 增加一条边，需要依赖于原先的边集合。换言之，原来的边集合中要提供足够多的非连通边。 所以每次增加1条连通边(即增加0个顶点、1条边)时，需要提供相应的连通分支(即增 加2个节点和1条边)，最终极限Limit趋近于1，如附图7所示。

基于以上原理，针对动态更新所有曲线包含的曲线节点，具体算法流程如下：

(1)从曲面片集合中取一个曲面片作为当前处理的曲面片；

(2)从当前处理的曲面片的构造洞集合中取一个洞作为当前洞；

(3)从当前洞的构造曲线集合中取一条曲线为当前曲线；

(4)比较当前曲线的构造边集合与构造节点集合的大小：

(i)若相同，则标记该条曲线为“闭合曲线”；

(ii)若不同，则标记该条曲线为“不闭合曲线”；

(5)进一步处理当前曲线：

(i)若当前曲线是“闭合曲线”，则选择当前曲线的构造节点集合中任意一个节点，将其同时作 为当前曲线的曲线起始节点和曲线终止节点，并跳入步骤(9)；

(ii)若当前曲线是“不闭合曲线”，则创建内部节点集合，其内容为空，进入步骤(6)；

(6)取当前曲线的构造节点集合中的一个节点，如下判断：判断在当前曲线的构造边集合中， 是否存在2条不同的构造边，且该节点是这2条边的公共节点：

(i)若存在，则将该节点加入内部节点集合；

(ii)若不存在，则不做任何处理；

(7)返回(6)取当前曲线的构造节点集合中的下一个节点，重复步骤(6)-(7)，直至搜索出以上曲 线的完整的内部节点集合，进入(8)；

(8)针对当前曲线的构造节点集合，去除内部节点集合，剩余的即当前曲线的外部节点集合(即 当前曲线的曲线起始节点和终止节点)；

(9)当前曲线的曲线节点搜索完毕；

(10)返回(3)，从当前洞的构造曲线集合中取下一条曲线为当前曲线，重复步骤(3)-(10)；直到 当前洞的所有曲线的曲线节点都搜索完毕，进入(11)；

(11)返回步骤(2)，取下一个洞作为当前洞，重复步骤(2)-(11)；直到当前曲面片的所有洞的 所有曲线的曲线节点都搜索完毕；进入(12)；

(12)返回步骤(1)，取下一个曲面片作为当前处理的曲面片，重复步骤(1)-(12)；直到所有曲面 片的所有洞的所有曲线的曲线节点都搜索完毕，结束步骤6。

在附图8给出的渐进式更新曲线节点的示例中，最终形成一条闭合曲线。该示例包含6 个状态，即status1至status6，各状态提供了相应新增边数(new inserted edges)、原有边数(old  edges)、所有节点数(all_vertices)、内部节点数(inner_vertices)、外部节点数(outer_vertices)、 比例(ratio＝all_edges/all_vertices)、连通分支数(connected components)。在status1中，新增边 情况属于Case1(增加单独边)，即实际新增1条边和2个节点，共有外部节点2个，存在连通 分支1个；在status2中，新增边情况属于Case2(追加边)，即实际只新增1条边和1个节点， 共有外部节点2个，存在连通分支1个；在status3中，新增边情况属于Case1(增加单独边)， 即实际新增1条边和2个节点，共有外部节点4个，存在连通分支2个；在status4中，新增 边情况属于Case3(增加连通边)，即实际只新增边1条和0个节点，共有外部节点2个，存在 连通分支1个；在status5中，新增边情况属于Case2(追加边)，即实际只新增1条边和1个 节点，共有外部节点2个，存在连通分支1个；在status6中，新增边情况属于Case3(增加连 通边)，即实际只新增1条边和0个节点，共有外部节点0个，存在1个连通分支(形成一条 闭合曲线)。

步骤7.搜索无穷远体的边界上的任意一个曲面片

单个连通分支内所有最小体共同形成一个较大的体，称为外轮廓体。在三维空间中去除 那些常规认知的、具备有限体积的最小体之后，剩余的三维空间称为无穷远体。无穷远体可 以看作外轮廓体在三维空间的补集。无穷远体的边界(由构造曲面片组成)与相应外轮廓体 的边界(由构造曲面片组成)相同。因此，以上等价于基于步骤3所得曲面片集合寻找外轮 廓体的边界上任意一个曲面片。具体算法流程如下：

(1)创建一个结果曲面片，其内容为空；

(2)创建一个结果平面片，其内容为空；

(3)计算给定平面片集合的最小外接盒；计算该最小外接盒的最大Z值，简称最大Z值；

(4)创建一个相接平面片集合，其内容为空；

(5)针对给定平面片集合中的每个平面片的每个顶点，比较该顶点的Z值与最大Z值：若相等， 则将该平面片加入以上相接平面片集合中；否则，不做任何处理；

(6)针对以上相接平面片集合，如果存在所有顶点Z值都等于最大Z值的平面片，将该平面片 标记为平行平面片，并转入步骤(7)；如果不存在，则转入步骤(8)；

(7)比较平行平面片的法向量与三维矢量(0,0,1)的夹角大小，并在以下处理后转入步骤(10)；

(i)若两者夹角为0，则将该平面片标记为结果平面片，且结果平面片的方向为1；

(ii)若两者夹角为180，则将该平面片标记为结果平面片，且结果平面片的方向为2；

(8)针对相接平面片集合中的每个平面片，计算其法向量与三维矢量(0,0,1)的夹角，该夹角记 为“原始夹角”；比较该原始夹角与90并如下处理：

(i)若原始夹角处于(0,90)，则不进行操作；

(ii)若原始夹角处于(90,180)，则将180减去原始夹角；

将以上处理后的夹角标记为“处理夹角”，并进入步骤(9)；

(9)针对相接平面片集合中的每个平面片，选择其“处理夹角”最小的那个平面片，将该平面片 标记为结果平面片；同时，根据结果平面片的“原始夹角”计算结果平面片的方向如下，

(i)若原始夹角处于(0,90)，则结果平面片的方向记为1；

(ii)若原始夹角处于(90,180)，则结果平面片的方向为2；

(10)找到结果平面片所在的曲面片，该曲面片即为结果曲面片；同时，将结果平面片的方向 作为结果曲面片的方向；

(11)所得结果曲面片为外轮廓体边界上的一个曲面片，返回结果曲面片。

值得注意的是，相接平面片集合不一定取相接于具备最大Z值的顶点的所有平面片，也 可以取相接于最小Z值(或最小X值、最小Y值、最大X值、最大Y值)顶点的所有平面 片，并相应改动后续步骤，都属于本发明的等同替换方案，在本发明的保护方案内。

步骤8.搜索无穷远体的边界

无穷远体的边界(由构造曲面片组成)与相应的外轮廓体的边界(由构造曲面片组成) 相等。因此，以上等价于基于步骤3所得曲面片集合搜索外轮廓体。具体算法流程如下：

(1)采用步骤7所得结果(搜索边界上的任意一个曲面片)，记为外轮廓任意曲面片；

(2)创建外轮廓体对象和当前曲面片集合，其内容分别为空，初始化当前曲面片集合包括之前 所得的外轮廓任意曲面片；

(3)针对当前曲面片集合中的每个曲面片，分别读取此时曲面片的方向，将曲面片以及此时曲 面片的方向加入外轮廓体对象中，同时对曲面片此时方向对应的侧面作标记：

(i)若此时曲面片的方向为1(即表明搜索前向无穷远体)，则该曲面片的背面标记为”已使用”；

(ii)若此时曲面片的方向为2(即表明搜索后向无穷远体)，则该曲面片的正面标记为”已使用”；

(4)针对当前曲面片集合，创建对应的推进曲面片集合，其初始化内容为空；

(5)针对当前曲面片集合中的每个曲面片的每条曲线，计算如下两份数据：

(a)最邻近曲面片

与该曲线相接的、同样用于构造外轮廓体的曲面片，称为最邻近曲面片；与该曲线相接 的所有曲面片形成一个集合，称为相接曲面片束；最邻近曲面片总是存在于相接曲面片束； 最邻近曲面片的计算结果，与当前曲面片有关，与当前曲面片的方向有关；具体如下，

(i)若当前曲面片的方向为1(即表明搜索前向无穷远体)，则在相接曲面片束中，顺着当前曲面 片的正面望去，寻找与当前曲面片沿着以上曲线夹角最小的那个曲面片，此时该曲面片是最 邻近曲面片；

(ii)若当前曲面片的方向为2(即表明搜索后向无穷远体)，则在相接曲面片束中，顺着当前曲面 片的正面望去，寻找与当前曲面片沿着以上曲线夹角最大的那个曲面片，此时该曲面片是最 邻近曲面片；

(b)最邻近曲面片的方向

当最邻近曲面片与当前曲面片相容，则对最邻近曲面片赋予与当前曲面片一样的方向； 若不相容，则对最邻近曲面片赋予与当前曲面片不同的方向；具体如下：

(i)若当前曲面片方向为1，且当前曲面片与最邻近曲面片相容，则最邻近曲面片方向为1；

(ii)若当前曲面片方向为1，且当前曲面片与最邻近曲面片不容，则最邻近曲面片方向为2；

(iii)若当前曲面片方向为2，且当前曲面片与最邻近曲面片相容，则最邻近曲面片方向为2；

(iv)若当前曲面片方向为2，且当前曲面片与最邻近曲面片不容，则最邻近曲面片方向为1；

(6)针对以上得到的每个对子(即最邻近曲面片，及其方向)，若其在(2)创建的外轮廓体对象外 轮廓体中不存在，则加入以上推进曲面片集合；若存在则不做处理；

(7)清空当前曲面片集合，将推进曲面片集合作为新的当前曲面片集合；之后，清空推进曲面 片集合；

(8)返回(3)，基于新的当前曲面片集合重复步骤(3)-(8)，直至得到的推进曲面片集合为空；此 时，以上无穷远体的边界搜索完毕。

值得注意的是，当前曲面片集合初始化时只有外轮廓任意曲面片。搜索无穷远体的具体 过程可以采用广度优先遍历策略(BFS)或深度优先遍历策略(DFS)，两者区别在于当前曲面片 集合与推进曲面片集合的设置不同。

步骤9.搜索最小体集合

针对步骤3(再次搜索曲面片)获得的曲面片集合，搜索最小体集合，其算法流程如下：

(1)针对曲面片集合中每个曲面片，对其正面和背面都标记”未使用”；

(2)如上所述，采用步骤8的结果(搜索无穷远体的边界)；步骤8搜索后，针对该边界上的 每一个曲面片，有一侧”已使用”，按此更新对曲面片集合中相应曲面片的标记；

(3)创建一个新的最小体对象和当前曲面片集合，其内容分别为空，初始化当前曲面片集合；

(4)针对当前曲面片集合中的每个曲面片，读取此时曲面片的方向，并将该曲面片以及此时曲 面片的方向加入以上最小体中，同时将该曲面片此时方向对应的侧面作标记：

(i)若此时曲面片的方向为1(即表明搜索后向体)，则该曲面片的正面标记为”已使用”；

(ii)若此时曲面片的方向为2(即表明搜索前向体)，则该曲面片的背面标记为”已使用”；

可见，搜索最小体集合时“标记侧面”与搜索无穷远体边界时“标记侧面”方法相反；

(5)针对当前曲面片集合，创建推进曲面片集合，其内容为空；

(6)针对当前曲面片集合中的每个曲面片的每条构造曲线，计算如下两份数据：

(a)最邻近曲面片

与以上曲线相接的、同样用于构造该最小体的曲面片，称为最邻近曲面片；与该曲线相 接的所有曲面片形成一个集合，称相接曲面片束；最邻近曲面片总是存在于相接曲面片束； 最邻近曲面片的计算结果，与当前曲面片有关，与当前曲面片的方向有关；具体如下，

(i)若当前曲面片的方向为1(即表明搜索后向体)，则在相接曲面片束中，顺着当前曲面片的正 面望去，寻找与当前曲面片沿着以上曲线夹角最大的那个曲面片，此时其是最邻近曲面片；

(ii)若当前曲面片的方向为2(即表明搜索前向体)，则在相接曲面片束中，顺着当前曲面片的正 面望去，寻找与当前曲面片沿着以上曲线夹角最小的那个曲面片，此时其是最邻近曲面片；

由此可见，搜索最小体集合时“计算最邻近曲面片”与搜索无穷远体边界时“计算最邻近曲 面片”方法相反；

(b)最邻近曲面片的方向

当最邻近曲面片与当前曲面片相容，则对最邻近曲面片赋予与当前曲面片一样的方向； 若不相容，则对最邻近曲面片赋予与当前曲面片不同的方向；具体如下：

(i)若当前曲面片方向为1，且当前曲面片与最邻近曲面片相容，则最邻近曲面片方向为1；

(ii)若当前曲面片方向为1，且当前曲面片与最邻近曲面片不容，则最邻近曲面片方向为2；

(iii)若当前曲面片方向为2，且当前曲面片与最邻近曲面片相容，则最邻近曲面片方向为2；

(iv)若当前曲面片方向为2，且当前曲面片与最邻近曲面片不容，则最邻近曲面片方位为1；

由此可见，搜索最小体集合时“计算最邻近曲面片的方向”与搜索无穷远体边界时“计算最 邻近曲面片的方向”方法相反；

(7)对于以上得到的每个对子(即最邻近曲面片，及其方向)，若该对子在(3)创建的新的最小 体对象中不存在，则加入以上推进曲面片集合；若存在则不做处理；

(8)清空当前曲面片集合，将推进曲面片集合作为新的当前曲面片集合；之后，清空推进曲面 片集合；

(9)返回(4)，基于新的当前曲面片集合重复步骤(4)-(9)，直至计算得到的推进曲面片集合为空； 此时，以上最小体的所有构造曲面片都搜索完毕，进入(10)；

(10)返回(3)，创建一个新的最小体对象，重复步骤(3)-(10)，直至给定曲面片集合中的每个曲 面片都被“已使用”2次；此时，所有最小体都搜索完毕；

值得注意的是，每次进入步骤(3)时，给定曲面片集合都会更新，其始终包含如下三类：

(i)0-usedS(即正面“未使用”并且背面“未使用”)；

(ii)1-usedS(即正面“已使用”但背面“未使用”，或者正面“未使用”但背面“已使用”)；

(iii)2-usedS(即正面“已使用”且背面“已使用”)；

此时，只选择给定曲面片集合中1个曲面片用于初始化当前曲面片集合，该曲面片称起 始曲面片(begins,the begin Surface)。起始曲面片可以是0-usedS，也可以是1-usedS，但不能是 2-usedS。同时，起始曲面片的方向如下设置：

(i)若起始曲面片是0-usedS，则起始曲面片的方向可以是1也可以使2(即可以先搜索后向体， 也可以先搜索前向体)；

(ii)若起始曲面片是1-usedS，且该曲面片不属于外轮廓体的边界，则起始曲面片的方向选取尚 未使用过的方向(即若已使用过方向1，则选择方向2；若已使用过方向2，则选择方向1)；

(iii)若起始曲面片是1-usedS，且该曲面片属于外轮廓体的边界，则起始曲面片的方向选取之 前使用过的方向(即若已使用过方向1，则选择方向1；若已使用过方向2，则选择方向2)。

为便于证明本发明的技术效果，进行基于曲面片构造体的有效性验证如下：

拓扑学中已涉及讨论曲面的Euler示性数，即讨论的是闭曲面单纯剖分后对应图形(组合 曲面)的Euler示性数。更为具体的，Euler示性数为弧段节点个数(cE)减去弧段个数(C)加上 剖分后的平面片个数(F)(因为每个剖分后的平面片同胚于圆盘)。尽管如此，以上并没有揭 示三维空间剖分时的拓扑不变性，更为具体的，其局限性如下：

(1)其讨论的是拓扑学中的曲面的Euler示性数，本质上仍然是2维空间的，即揭示的只是二 维空间的剖分情况，而非三维空间的(即欧拉公式中并未引入Body对象)；

(2)在实现闭曲面单纯剖分过程(即寻找闭曲面的有效多个闭圆盘覆盖)中，不允许圆盘之间 构成环形区域，凡是整个落在别的圆盘内部的圆盘一律舍弃(即不允许圆环)。换言之，两个 圆盘的边界必须相交。要找到满足以上情况的闭圆盘的圆盘覆盖，需要保证乔丹曲线定理 (Jordan Curve Theorem)的一个比较强的变体，这在现实世界中往往要求过于苛刻，因为现实 中经常存在曲面与曲面相交于一个闭合回路(即只有1个公共平面片的相邻立方体)。

在此，我们提出一个扩展的欧拉公式，如下

Eu(Object)＝[cE–C(sub)+S-B]-cC＝CC

其中，Eu(Object)代表对象的欧拉示性数，cE代表曲线节点(Curve Ends)个数，C(sub)代表 细分后曲线(Curves after Subdivision)个数，S代表曲面片(Surfaces)个数，B代表最终构造的三 维实体(Bodies)个数，cC代表闭合曲线(closed Curves)个数，CC代表连通分支(Connected  Components)个数。针对该扩展的欧拉公式，其适合于：(1)以上提及的没有嵌入圆盘(即没有 闭合曲线,no closed Curve)的所有情况(闭曲面除外)；(2)存在圆盘时的大部分情况。

同时，可以从另外角度验证曲面片构体的有效性。我们如下处理：将每个平面片(Facet) 给予三角剖分，如以平面片的唯一外环与所有内环作为约束边进行约束Delaunay三角化(CDT) (以下简称三角化)，使每个剖分后的平面片是2维单纯复形。针对同一个体对象，其三角剖 分前与剖分后，通过以上步骤搜索到的曲面片、洞、曲线、闭合曲面、曲线节点应该一致。 具体包括： (1a)Surface Set Size(before CDT)与Surface Set Size(after CDT)相同 即三角化前的曲面片集合的大小与三角化后的曲面片集合的大小相同 (1b)Each Surface(before CDT)与Each Surface(after CDT)一致 即三角化前的每个曲面片与三角化后的每个曲面片一致 (“一致”体现在： Holes of the Surface(before CDT)与Holes of the Surface(after CDT)相同 即三角化前曲面片包含的洞集合与三角化后曲面片包含的洞集合相同 CDT(Facets of the Surface(before CDT))与Facets of the Surface(after CDT)相同) 即曲面片包含的平面片集合三角化后的面片集合与三角化后曲面片包含的平面片集合相同 (2a)Hole Set Size(before CDT)与Hole Set Size(after CDT)相同 即三角化前洞集合的大小与三角化后洞集合的大小相同 (2b)Each Hole(before CDT)与Each Hole(after CDT)相同 即三角化前每个洞与三角化后每个洞相同 (3a)Curve Set Size(before CDT)与Curve Set Size(after CDT)相同 即三角化前曲线集合的大小与三角化后曲线集合的大小相同 (3b)Each Curve(before CDT)与Each Curve(after CDT)相同 即三角化前每条曲线与三角化后每条曲线相同 (4a)Closed Curve Set Size(before CDT)与Closed Curve Set Size(afterCDT)相同 即三角化前闭合曲线集合的大小与三角化后闭合曲线集合的大小相同 (4b)Each Closed Curve(before CDT)与Each Closed Curve(after CDT)相同 即三角化前每条闭合曲线与三角化后每条闭合曲线相同 (5a)Curve End Set Size(before CDT)与Curve End Set Size(after CDT)相同 即三角化前曲线节点集合的大小与三角化后曲线节点集合的大小相同 (5b)Each Curve End(before CDT)与Each Curve End(after CDT)相同 即三角化后每个曲线节点与三角化后每个曲线节点相同

设基于平面片寻体后，搜索出来的体记为Body1，其中，基于三角剖分前的平面片搜索出 来的体记为Body1(before CDT)；基于三角剖分后的平面片搜索出来的体记为Body1(after  CDT)。满足如下情况(其已反映在已授权的“一种地理空间实体构建方法及系统”中)： (6a)Body1 Set Size(before CDT)与Body1Set Size(after CDT)相同 即三角化前通过平面片搜到体集合的大小与三角化后通过平面片搜到体集合的大小相同 (6b)Each Body1(before CDT)与Each Body1(after CDT)一致 即三角化前通过平面片搜到的每个体与三角化后通过平面片搜到的每个体一致 (“一致”体现在： CDT(Facets of Body1(before CDT))与Facets of Body1(after CDT)相同 即通过平面片搜到体包含的平面片集合三角化后的面片集合与 通过三角化后的平面片搜到的体包含的面片集合相同)

设基于曲面片寻体后，搜索出来的体记为Body2，其中，基于三维剖分前的平面片，先搜 索出曲面曲线，再搜索出来的体记为Body2(before CDT)；基于三角剖分后的平面片，先搜索 出曲面曲线，再搜索出来的体记为Body2(after CDT)。额外满足如下情况 (7a)Body2Set Size(before CDT)与Body2Set Size(after CDT)相同 即三角化前通过曲面片搜到的体集合大小与 三角化后通过曲面片搜到的体集合大小相同 (7b)Each Body2(before CDT)与Each Body2(after CDT)一致 即三角化前通过曲面片搜到的每个体与 三角化后通过曲面片搜到的每个体一致 (“一致”体现在： $\mathrm{CDT}\left({\Sigma }_{i=0}^n\mathrm{Facets}\left(\mathrm{Surface}\left(i\right)\mathrm{ofBody}2\left(\mathrm{beforeCDT}\right)\right)\right)$与 相同 即通过曲面片搜到的体包含的曲面片中包含的平面片集合给予三角化后的面片集合与 三角化后通过曲面片搜到的体包含的曲面片中包含的平面片集合相同) (8a)Body1Set Size(before CDT)与Body2Set Size(before CDT)相同 即三角化前通过平面片搜到的体集合大小与 三角化前通过曲面片搜到的体集合大小相同 (8b)Each Body1(before CDT)与Each Body2(before CDT)一致 即三角化前通过平面片搜到的每个体与 三角化前通过曲面片搜到的每个体一致 (“一致”体现在： Facets of Body1(before CDT)与