ISSNi000—0054清华大学学报(自然科学版)2014年第54卷第12期可JTsinghuaUniv(Sei&Techno1)，2014，Vo1．54，No．12不规则三角网中约束线嵌入郑辑涛。，张涛，何红红，朱纪洪(1．清华大学计算机科学与技术系，北京100084；2．空军装备研究院航空气象防化研究所，北京100085)摘要：该文针对有约束情况下的不规则三角网重建，分析了约束线影响域的各种典型情况，在此基础上提出了一种约束线嵌入方法。该方法首先搜索约束线影响域，提取影响域的边界，根据凹凸性判断找到影响域边界上的凸角，并在凸角处生成新的三角形，通过对影响域的重剖分完成约束线的嵌入。同时给出了详细算法流程并进行了实验，结果表明：该算法鲁棒稳定，能够实现各种复杂约束情况下的不规则三角网重建。关键词：不规则三角网；约束线；嵌入；凹凸性中图分类号：TP391文献标志码：A文章编号：1000—0054(2014)12-1555-05EmbeddingofaconstrainedlineintoatriangulatedirregularnetworkZHENGJitao～．ZHANGTao，HEHonghong，ZHUJihong(1．DepartmentofComputerScienceandTechno】ogy，TsinghuaUniversity，Beijing100084，China；2．AviationMeteorologicalandChemicalDefenseInstitute，AirForceEquipmentResearchAcademe，Beijing100085，China)Abstract：Thereconstructingoftriangulatedirregularnetworkswithconstrainedlinesisanalyzedforallkindsofinfluencedomains．Aconstrainedlinesembeddingmethodisgiventhatfirstcheckstheinfluencedomainofeveryconstrained1ineandthenextractstheinfluencedomainboundary．Thesystemthenevaluatestheconvexanglesontheboundaryaccordingtotheconcave—convexpropertyandgeneratesanewtriangleateveryconvexangletoembedtheconstrainedlinesbyagainpartitioningtheinfluencedomain．Testsshowthatthealgorithmisstableandrobustandcansuccessfullyreconstructtriangulatedirregularnetworkwithcomplexconstrainedlines．Keywords：triangularirregularnetwork；constrainedline；embedding；concave—convex重建不规则三角网是地理信息系统、虚拟现实、地学分析和逆向工程中的热点问题。实际情况下多数地貌特征如等高线、山谷线和山脊线等需要用约束线来表达，约束条件下建立不规则三角网可以在9／201555—1559较小的实测数据前提下提高建模的精度。目前，关于约束条件下不规则三角网的重建通常有2类方法：第一类是在建立三角网的同时考虑约束条件的影响口≈]，这种方法时间效率较低，实际中已很少使用；第二类是两步法l_3，第一步是在不考虑约束条件的情况下建立不规则三角网，第二步再把约束线强行嵌入到三角网中，这种方法不仅可以充分利用点云重构三角网的研究成果，而且由于时间效率高而受到研究者的普遍关注。两步法的关键在于约束线的嵌入。文[4]提出了影响域的概念，同时提出了适用于四边形影响域的“四边形对角线交换”算法；文[5]提出了一种“(+2)边形对角线交换”算法，解决了影响域为任意多边形情形下的约束线嵌入问题，但由于该算法需要将影响域分为2个多边形后分别剖分，其中还要比较点到直线的距离，因而程序实现工作量较大，时间效率低。文[6]提出了“轨迹生成”法，该算法从约束线的一端出发，对影响域中的所有对角线依次进行交换，直到约束线嵌入为止。实际上是对“四边形对角线交换”算法的重复调用，因而程序实现简单明了。但该算法也有其局限性，当影响域为凹多边形时可能会失效。在任意影响域中强行嵌入约束线是否一定能够通过多次对角线交换来实现也没有给出严格证明。文[7]基于强可交换对角线的思想给出了肯定的证明，认为影响域中的每个三角形至少有一条边在影响域的边界上，称为该三角形的交换边，并且除首末2个三角形外，每个三角形有且只有1条交换边。文[8]提出了“插入一交换”法，在凸多边形时进行交换，在凹多边收稿日期：基金项目：作者简介：通信作者：2O14—05—07国家自然科学基金资助项目(61104082)郑辑涛(1975～)，男(汉)，河北，博士研究生朱纪洪，教授，E-mail：jhzhu@mail．tsinghua．edu．cn清华大学学报(自然科学版)形时...
