用c++实现Delaunay三角剖分

约束Delaunay四面体剖分作者：张娟来源：《无线互联科技》2017年第12期摘要：文章研究了约束Delaunay四面体网格生成算法，引入了优化的网格算法，提高了四面体剖分单元的质量；重点研究了指定区域的边界边与边界面的一致性这两个Delaunay三角化算法迫切需要解决的关键性问题。

结果表明，文章提出的约束Delaunay三角化算法适用性、效率及网格单元质量等方面都得到了提高，且该算法易于实现。

关键词：约束Delaunay三角化；网格算法；四面体剖分有限元方法是一种解决复杂工程实际问题的有效手段，基于三维实体四面体剖分相对于二维领域的复杂性，Delaunay算法的研究成果还不够完善。

目前Delaunay三角化方法仍具有算法速度慢、稳定性不良、适用范围有限、网格质量较差等和其他三维区域四面体剖分算法一样普遍存在的问题。

Delaunay准则是保证优化的网格结构的前提，由于目前现有的算法都无法较好地保证Delaunay准则，因此导致网格质量无法保证，造成狭长三角形单元的出现，致使误差超出范围，造成算法不稳定性。

而需要解决的最关键的三维Delaunay三角化方法的问题就是指定区域的边界边、边界面的一致性问题。

为了保证指定区域边界的一致性，保证边界边、边界面在Delaunay三角化中的存在性，必须要进行边界的恢复。

1 Delaunay四面体剖分的基本理论—边界一致设Σ是一个三围区域W边界的离散化-曲面网格。

边界一致的问题是要求生成一个符合Σ的四面体网格T，即Σ是一个由Γ元素组成的组合体。

T中可以有额外的点（Steiner点），但是这种点的数目应该被限制得越少越好，这个问题对很多应用软件来说是最基本的。

在三维中，解决这个问题面临很多困难，有一些简单的多面体如果没有Steiner点（40个），就不能被四面体剖分。

判定一个非凸多面体不存在Steiner点能否进行四面体剖分，是NP（NP-complete）问题，Chazelle认为对一个简单的多面体进行四面体剖分可能需要很多Steiner点。

CGAL功能⼤纲Computational Geometry Algorithms Library，CGAL，计算⼏何算法库。

使⽤C++语⾔编写的，提供⾼效、可控的算法库。

⼴泛应⽤于计算⼏何相关领域，如地理信息系统、计算机图形学、计算机辅助设计、信息可视化系统、⽣物医学等。

CGAL，提供了计算⼏何相关的数据结构和算法，如：（1）三⾓剖分。

2D约束三⾓剖分，2D和3D Delaunay三⾓剖分；（2）Voronoi图。

2D和3D的点，2D加权Voronoi图，分割Voronoi图等；（3）多边形。

布尔运算、偏移、直⾻架等；（4）多⾯体。

布尔运算、2D流型结构、闭合体；（5）曲线（6）⽹格⽣成。

2D Delaunay⽹格⽣成和3D Surface和体积⽹格⽣成；（7）⼏何处理。

表⾯⽹格（Surface Mesh）简化，细分和参数化等；（8）凸壳算法。

适⽤于2D、3D以及dD；（9）搜索结构。

近邻搜索，kd树等；（10）插值（11）形状分析（12）拟合（13）距离算术与代数Arithmetic and Algebra主要提供了计算⼏何⽤到的数学基础：数据类型、多项式、数据结构与算法代数基础Algebraic Foundations这个包从概念、类和函数的⾓度定义了代数对CGAL的意义。

数据类型Number Types这个包为第三⽅数据类型库提供数据类型概念以及数据类型类和包装器类。

模运算Modular Arithmetic这个包提供了有限域的算法。

所提供的⼯具对于基于模块化算法的过滤器和基于余数的算法尤其有⽤。

多项式Polynomial这个包介绍了单变量多项式和多变量多项式的概念。

虽然这个概念是为任意数量的变量编写的，但是对于这个概念的特定模型，变量的数量被认为是固定的。

代数框架Algebraic Kernel解多项式的实解是⼀个应⽤范围很⼴的基本问题。

这个包的⽬标是提供最先进算法的⿊盒实现，以逼近或近似的求解出单变量多项式和双变量多项式的真实根。

基于最小正切值的约束Delaunay三角剖分卢扣;李明峰;管莉莉;陈春晖【摘要】以TIN生长算法和分治算法的思想为基础,提出一种改进的构建约束Delaunay三角网(CDT)的算法.该算法在生长算法和分治算法思想的基础上,以约束边为基边分别向两侧重新构网.以基边与离散点形成的三角形的最小正切值为判断条件确定基点,实现对约束边影响域的三角剖分.实验对比表明该算法减少了搜索基点的时间,提高了构网速度.因此得到最小正切算法优于传统算法的结论.【期刊名称】《南京工业大学学报（自然科学版）》【年(卷),期】2010(032)005【总页数】4页(P96-99)【关键词】约束Delaunay三角网;基边;基点;最小正切值【作者】卢扣;李明峰;管莉莉;陈春晖【作者单位】南京工业大学,土木工程学院,江苏,南京,210009;南京工业大学,土木工程学院,江苏,南京,210009;南京工业大学,土木工程学院,江苏,南京,210009;南京工业大学,土木工程学院,江苏,南京,210009【正文语种】中文【中图分类】TP317不规则三角网 (TI N)具有数据精度高、可局部加密等特点,是数字高程模型的基本形式,在三维可视化、地形分析等领域中有着广泛的应用.在建立TI N的过程中,利用离散点构建 TI N时,不仅对三角形的形状有要求,而且对离散数据自身也有特殊的要求[1].例如,某些点的连线 (跨河大桥、地理边界、断裂线、结构线、河流等)对TI N网的局部合理性有决定性的影响.此时需要考虑对这些离散点加以某种强制约束,使得构成的 TI N符合实际情况,并提高TI N的质量.因此如何在无约束数据的三角网中嵌入约束线段成为研究热点[2].目前,构建约束 Delaunay三角网的方法大致可分为约束图法、分割 -合并算法、加密算法、Shell三角化算法和两步法[3].其中,最具代表性的为两步法.两步法的实质是:首先对约束数据集建立非约束(初始三角网)D-TI N,然后在其中嵌入约束线段并调整初始D-TI N,使得约束线段可见并满足Delaunay三角网的性质[4].Bernal算法是典型的两步法,该算法的基本原理为:先不考虑约束条件构建初始 D-TI N;然后检测约束边所经过的所有三角形,从约束边的起点开始,按照一定规则逐步交换对角线,最终使起始点与目标点相连.该算法的关键是从起始点出发,对遇到的每条对角线进行可交换性判断.可交换则交换,不可交换则判断下一条.第一轮交换结束后,开始下一轮,直到所有约束边均作为三角形边加入到 TI N网中[1].但该算法存在不能动态扩充点集,并且执行效率较低等缺点.因此,笔者在使用生长算法和分治算法的基础上,在建网开始阶段选择以约束边为起始边,基于最小正切值的比较选择三角形的第三点,分别向约束边两侧重新构网,减少三角形第三点的查询时间,以提高算法效率.在向标准的Delaunay三角网中加入约束边后,新的三角网则不再严格满足Delaunay三角网的空外接圆和最小内角和最大这两个性质,只有在网内那些不含约束边的三角形中这两个性质才得到保留.嵌入约束边后的三角网 (约束 Delaunay三角网,简写为 CDT),具有以下性质.设约束Delaunay三角网T(V∶L),V为离散点的集,L为约束边的集合.1)可见性设 Pi、Pj∈V,如果 Pi、Pj的连线不与约束Delaunay三角网中任何三角形边(顶点除外)及L中的任何一条约束边相交,则可称 Pi、Pj是可见的.2)空外接圆性质若三角形 t的三条边不为约束边,则 t为Delaunay三角形,当且仅当 t的外接圆中不含其他 T中三角形的顶点且 t的三顶点是相互可见时,则可称三角形 t满足空外接圆性质.3)最大最小角性质如果两相邻的三角形 t1、t2具有相同的公共边 d且 d∉L,当由t1、t2组成的四边形交换对角线后,其最小内角变成最大时,则称这两个三角形满足最大最小角性质.4)局部优化性质对于三角网 T中的任意三角形 t,如果其三边都不是约束边,则它一定满足空外接圆性质和最大最小角性质,则此三角形满足局部优化性质[5].2.1 算法的基本思想设需要嵌入的约束线段为P1P2P3…Pn(n>2).首先,将约束线段的端点P1P2P3…Pn 加入到离散点集中,构建初始Delaunay三角网.然后,将约束边 PiPj嵌入初始Delaunay三角网中,对初始 Delaunay三角网进行局部调整使之满足约束边 PiPj的均可见性以及三角网的最小角度之和最大,如图 1所示.1)设约束边为 PiPj,删除初始三角网中与约束边 PiPj相交的边,得到一多边形W={Pi、A、B、…、Pj、…、Pi}为空腔多边形[6],约束边 PiPj将多边形W分成了WL和WR两个部分,且WL和WR也是简单多变形,如图 2所示.2)运用最小正切法对WL和WR分别进行三角剖分.3)若Pn∈W,且 Pn与约束边 PiPj所形成的三角形的正数最小正切值和约束边 PiPj 与其他离散点所形成三角形的正数最小正切值相比最大,则该三角形一定满足可见性及最小角之和最大的性质.综上所述,分别对约束线段两侧的空腔多边形WL和WR进行三角剖分,就可实现将约束线段 PiPj嵌入到初始三角网中.2.2 算法步骤1)构建初始Delaunay三角网.初始三角剖分网可利用现存的任一 Delaunay三角剖分算法进行实现,如图 3所示.2)嵌入约束线段 PiPj并删除与约束线段相交的边,形成空腔多边形.连接点 Pi、Pj 并删除与 PiPj相交的线段 BD、CD、AD、AE形便成空腔多边形PiCBAPjEDPi,如图 2所示.3)存储,将空腔多边形在约束线段 PiPj两侧的点分别存入WL和WR两个点集合之中.4)确定起始边,令约束边 PiPj为起始边,连接起始边与相邻的点形成三角形如图 4所示.若连接成的三角形中包含有其他离散点,则该三角形不满足空外接圆性质[7],则不用考虑.5)计算△PiEPj和△PiDPj各角度的正切值,并取出每个三角形的正数最小正切值,即∠DPjPi和∠EPiPj的正切值 (正切值为负数的角度为钝角不可能为最小角).根据正切函数的单调性可知,当-90°<x<90°时,正切值越大,角度越大.因为三角形的最小角小于90°,故正切值最大的角度也应该最大.根据三角网的最大最小角原则[8],可知该三角形即为满足条件的 Delaunay三角形.在本例中∠DPjPi>∠EPiPj,因此ΔPjDPi为满足条件的Delaunay三角形,D为基点,如图 5所示.6)以生成的三角形的边 DPj为起始边通过最小正切算法进行三角剖分.7)约束边右侧的多边形剖分完后,通过最小正切算法对约束边 PiPj左侧多边形进行三角剖分.可得约束Delaunay三角网,如图 6所示.2.3 实例分析在执行效率方面,在最不利的情况下,对角线交换法的边交换次数为 O(n2)[9-10].其中,n为约束边影响域中离散点的个数.基于最小正切值的约束Delaunay三角剖分算法判断次数为 n2-1/4(离散点以约束边为边界均匀分布),n2-3n+2/2(离散点位于约束边的同一侧).由此可见,在建网过程中,此算法减少了搜索基点的时间和三角网局部重建的时间.为验证算法的执行效率和效果,笔者在Visual Studio 2005中实现了最小正切算法和对角线交换法,利用4组不同的数据对最小正切算法和交换对角线算法在相同的计算机环境下进行实验对比.表 1为几组不同点数及约束边数构建三角网所需时间的比较.由表 1可见该算法逻辑清晰、思维严谨、思路简易,且具有较高的执行效率.图7和图 8为本算法的执行效果图.其中,图 7为初始Delaunay三角网,图 8为加入 5条约束边并使用本算法进行剖分后的约束Delaunay三角网.以 TI N生长算法和分治算法的思想为基础,提出基于最小正切值的约束 Delaunay 三角剖分算法.该算法以基边与离散点形成的三角形的最小角的正切值为判断条件来确定基点,实现对约束边的影响域进行三角剖分.在嵌入约束线段的过程中,首先将约束线段影响域中的离散点的数据进行分块存储,在进行三角剖分的过程中只需要在约束边所在的空腔多边形的端点中选择起始点,缩短了搜索基点和三角网局部重新构建的时间,从而快速准确地将初始Delaunay三角网转换成约束 Delaunay三角网.【相关文献】[1] 史文中,吴立新,李清泉,等.三维空间信息系统模型与算法[M].北京:电子工业出版社,2007.[2] 刘学军,龚健雅.约束数据域的Delaunay三角剖分与修改算法[J].测绘学报,2001,30(1):82-88. Liu Xuejun,Gong Jianya.Delaunay triangulation of constrained Data Se[J].Acta Geodaetica et Cartographica Sinica,2001,30 (1):82-88.[3] 邓曙光,刘刚,邹帆.约束数据域 Delaunay算法详述及进展[J].沈阳航空工业学院学报,2005,22(5):79-80. Deng Shuguang,Liu Gang,Zhou Fan.Dilation and evolution of constrained data region Delaunay algorithm[J].Journal of Shenyang Institute of Aeronautcal Engineering,2005,22(5):79 -80.[4] 任振娜,李斌兵,周浩,等.一次性生成约束 Delaunay三角网算法的编程与实现[J].测绘工程,2006,15(1):54-58. Ren Zhenna,Li Binbing,Zhou Hao,et al.The program and achievement of the constrained Delaunay triangulation using once for all generation[J].Engineering ofSurveying and Mapping, 2006,15(1):54-58.[5] 宋占峰,詹振炎,蒲浩.Delaunay三角剖分中嵌入约束边的局部调整算法[J].西南交通大学学报,2002,37(4):399-403. Song Zhanfeng,Zhan Zhenyan,Pu Hao.A local adjustment algorithm for inserting constrained segments in Delaunay triangulation[J]. Journal of Southwest JiaotongUniversity,2002,37(4):399-403.[6] 刘少华.约束数据域Delaunay三角剖分算法研究与应用[J].计算机应用研究,2004,26(3):26-28. Liu Shaohua.A study on algorithm of Delaunay triangulation for the constrained data set and application[J].Application Research of Computers,2004,26(3):26-28.[7] 宋晓宇,戚爱伟,王永会.基于分治策略的快速构建Delaunay三角网算法 [J].沈阳建筑大学学报:自然科学版,2007, 23(5):862-865. Song Xiaoyu,Qi Aiwei,Wang Yonghui.A fast construction algorithm ofDelaunay triangulation based on divide and conquer[J]. Journal of Shenyang Jianzhu University:Natural Science Edition, 2007,23(5):862-865.[8] 熊斌,蒲浩,宋占峰.基于二叉排序树的约束 Delaunay三角网局部调整算法.[J].重庆交通大学学报:自然科学版,2008, 27(2):327-332. XiongBin,Pu Hao,Song Zhanfeng.Local adjustment algorithm for constructing constrained Delaunay triangulation based on binary sorttree[J].Journal of Chongqing Jiaotong University:Natural Science Edition,2008,27(2):327-332.[9] 刘永和,王润怀,齐永安.一种非凸包边界约束不规则三角网生成算法[J].测绘科学,2008,33(3):79-81. Liu Yonghe,Wang Runhuai,Qi Yongan.An algorithm for irregular triangulated networks restricted by non-convex border[J]. Science of Surveying andMapping,2008,33(3):79-81.[10] 宋晓宇,戚爱伟,王永会,等.基于最大外接圆的约束 Delaunay三角剖分算法 [J].沈阳建筑大学学报:自然科学版, 2008,24(6):1095-1098. Song Xiaoyu,QiAiwei,Wang Yonghui,etal.Constrained Delaunay triangulation division algorithm based on maximal circumcircl [J].Journal of Shenyang Jianzhu University:Natural Science E-dition,2008,24(6):1095-1098.。

基于Delaunay三角网格剖分算法在三维造型中的研究作者：王牌来源：《科学与财富》2014年第06期摘要：在对三维图像进行有限元数值模拟解析时，为了对连续的计算区域进行数值计算，达到模拟仿真的效果，必须先对三维图像进行网格剖分。

Delaunay三角网格剖分算法是生成网格的一种有效方法。

本文介绍了Delaunay三角网格剖分算法，以及在约束条件下的网格细分，最后给出了该算法在三维实体造型中的应用。

关键词：三角剖分；网格生成；网格细分Abstract： In the simulation analysis of the 3D finite element numerical， in order to carry out the numerical calculation for the calculation of continuous area， achieve the simulation results， we must first on the 3D mesh. Delaunay triangulation algorithm is an effective method to generate mesh. This paper introduces the Delaunay triangulation algorithm， and in the condition of mesh subdivision， finally the application of the algorithm in 3D solid modeling are given in this paper.Keywords： triangulation，mesh generation，mesh subdivision1、引言网格生成是有限元模拟计算的先决条件，有限元计算的效率和精确度在很大程度上受生成的网格质量的影响。

cgal tin约束三角形边长
CGAL（Computational Geometry Algorithms Library）是一个用C++编写的计算几何算法库，它提供了许多用于解决计算几何问题的工具和算法。

在CGAL中，可以使用TIN（三角形不规则网格）来表示地形表面。

TIN约束是指在构建TIN时，对三角形边长进行约束，使得生成的三角形网格满足一定的边长要求。

要在CGAL中对TIN的三角形边长进行约束，首先需要构建一个TIN数据结构，然后可以通过设置约束条件来控制三角形的边长。

在CGAL中，可以使用Delaunay三角剖分算法来构建TIN，并且可以通过设置边长约束条件来控制生成的三角形的大小。

具体来说，可以通过设置三角形的最小和最大边长来约束三角形的大小。

通过调整这些约束条件，可以控制生成的TIN中三角形的大小和形状，从而满足具体的应用需求。

另外，CGAL还提供了丰富的文档和示例，可以帮助开发者更好地理解如何使用TIN约束来控制三角形的边长。

开发者可以参考CGAL的官方文档和示例代码来学习如何使用TIN约束功能。

总之，在CGAL中，可以通过设置TIN约束来控制三角形的边长，从而实现对生成的三角形网格的精细化控制。

希望这些信息能够帮
助你更好地理解如何在CGAL中进行TIN约束三角形边长的操作。

Python实现DelaunayTriangulationDelaunay三角剖分是一种广泛用于计算机图形学、地理信息系统和计算几何等领域的技术。

它将一组离散点集划分成一组互不重叠的三角形，同时满足一定的性质。

在Python中实现Delaunay三角剖分可以使用几何库scipy和matplotlib。

Scipy库中的Delaunay函数可以实现Delaunay三角剖分，而matplotlib库可以用于可视化结果。

下面是一个简单的例子，展示了如何使用Python实现Delaunay三角剖分：```pythonimport numpy as npimport matplotlib.pyplot as pltfrom scipy.spatial import Delaunay#生成随机点points = np.random.rand(30, 2)# 执行Delaunay三角剖分tri = Delaunay(points)# 绘制Delaunay三角剖分结果plt.triplot(points[:,0], points[:,1], tri.simplices)plt.plot(points[:,0], points[:,1], 'o')plt.show```在这个例子中，我们首先生成了30个随机点，然后使用Delaunay函数执行Delaunay三角剖分，并传入这些点作为参数。

最后，使用matplotlib库的triplot函数绘制Delaunay三角剖分结果，然后再绘制原始点。

这段代码可以生成一个简单的Delaunay三角剖分示意图，并且可以通过调整点的数量或位置来实现不同的效果。

实际应用中，Delaunay三角剖分常用于三维地理信息系统中的高程插值、人脸识别中的特征点定位、计算几何中的最近邻等领域。

此外，还可以使用其他几何库，如CGAL和OpenCV等库，来实现更复杂的Delaunay三角剖分算法。

第43卷第2期物探化探计算技术Vol.43No.2 2021年3月COMPUTING TECHNIQUES FOR GEOPHYSIC A L AND GEOCHEMIC A L EXPLORATION Mar.2021文章编号：1001-1749(2021)02-025605基于Delaunay三角剖分的二维交互建模研究杨强（中国石化石油物探技术研究院，南京211103）摘要：准确合理的地质模型是地震正演模拟的基础。

简单的层状结构建模方法无法描述复杂的地质模型的拓扑结构，基于块体的地质建模方法可以描述断层、尖灭、透镜体等多种复杂地质结构，但建模方法实现比较难。

这里提出了一种解决方案，该方法基于Delaunay的地质建模方法，采用带约束的Delaunay三角剖分对复杂模型三角化，在此基础上，以原始线段为索引对剖分结果进行递归查找，形成多边形拓扑结构图和封闭多边形组，再对封闭多边形进行网格化。

通过理论和实际模型，验证了本方法的可行性。

关键词：地震正演；建模；Delaunay三角剖分中图分类号：TP391.41文献标志码：A 0引言地震勘探中，正演模拟不但在地震数据采集中得到应用，在地震资料处理和地震资料解释中也是重要的验证技术手段，是进行地震反演的基础。

而正演模拟的基础就是需要准确且合理的地质模型，因此建模是地震正演的重要基础。

传统上地质模型都沿用Cenveny提出的模型结构，即所谓层状结构模型。

它要求每一个分界面都必须从模型体的左边界贯穿到模型体的右边界，分界面按顺序由上到下依序排列，不得交叉。

对于逆断层、尖灭、透镜体等复杂地层情况，只能人为地简化模型,从而满足层状模型。

在实际的地球物理勘探中，层状结构模型有两个严重不足：①在采集、处理、解释各阶段的模型大都有逆断层、尖灭、透镜体等复杂地质元素，层状结DOI：10.3969/j.issn.1001-1749.2021.02.16构模型无法准确描述复杂的地质拓扑结构，从而无法得到网格化模型;②处理中的叠前深度偏移速度建模以及地震解释构造建模等，都要求能够交互修改模型，交互编辑中的层位修改及移动必须遵循层状规则，这对交互式复杂建模而言很困难，也不便利。

基于约束Delaunay三角剖分进行数模建摘要分析了各种三角网生成算法，选定逐点插入算法进行三角构网，并对该算法进行了优化处理。

在数据点集不变的情况下，提出了交换对角线的算法以进行数字地面模型的建构，使得数模成果真实地反映了地面情况。

关键词数字地面模型Delaunay 三角网约束边嵌入算法1 前言数字地面模型（Digital Terrain Modal，简称DTM）是地表勘测成果的数字化表现形式，它广泛应用于公路勘测设计一体化、地理信息系统等领域中。

其主要实现形式是不规则三角网（Triangulation Irregular Net，简称TIN）。

Delaunay三角网〔1〕具有空外接圆，以及最小角最大的性质，可最大限度的保证网中三角形满足近似等边（角）性，避免了过于狭长和尖锐的三角形的出现，是公认的最优三角网。

鉴于此，对二维域内点集进行Delaunay三角剖分是当今流行的TIN构网技术。

本文主要介绍了用逐点插入算法来生成Delaunay三角网，并讨论了如何在不改变点集的情况下实现约束边的嵌入，这符合数据采集及数模生成的规则，可以方便地处理地表上的陡坎线、断裂线等，真实地反映地表情况。

2 建立无约束三角网关于Delaunay三角网的生成算法，已经有了二十多年的研究，现在已趋于成熟，其主流算法有三种：分割－归并法，逐点插入法，三角网生长法。

其中三角网生长法已不常见，分割－归并法和逐点插入法各有优缺点，分治算法由于递归执行，因而需要较大的内存空间，消耗系统资源，但时间复杂度要好。

逐点插入法实现简单，占用内存较小，其时间复杂度差一些，但可以从数据的组织和管理上采用新方法，使之在时间和空间上达到最佳，并且逐点插入是一种动态剖分方法，有利于以后对DTM的维护和更新，是一种较好的构建DTM的剖分方法。

综合分析各算法，本文采用逐点插入法进行构网，分析了该算法中制约运行速度的因素，在数三角网拓扑关系、三角形的查找、LOP算法（Local Optimization Procedure）等方面进行了优化处理，使之有了较高的执行效率。

一种基于约束三角网的道路中心线的提取方法李功权;蔡祥云【摘要】鉴于道路中心线应用的广泛性,研究了基于约束Delaunay三角网的道路中心线的提取算法.以道路边界线作为约束线,采用Delaunay方法构建三角网.通过确定相邻三角形的类型,把获取的节点分为3类,其对应道路网络中的十字路、T型路和环岛路,对其分别进行优化处理,从而形成道路的中心线.在给出详细的算法步骤的同时,并用C#语言实现该算法.实测数据应用分析表明,该算法生成的道路中心线符合原道路多边形的形态,保持了原图形的拓扑特征.【期刊名称】《长江大学学报（自然版）理工卷》【年(卷),期】2013(010)002【总页数】4页(P47-50)【关键词】道路中心线;约束Delaunay三角网;道路网络模型【作者】李功权;蔡祥云【作者单位】长江大学地球科学学院,湖北武汉430100【正文语种】中文【中图分类】TP391.4根据道路中心线建立的道路网络模型，充分利用了GIS的网络分析功能，在交通管理和汽车导航中有着广泛的应用。

道路中心线的数据一般无法直接得到，在道路规划设计中可能使用的是道路两边的边界线，城市土地管理部门可能有各个地块的边界信息，这就需要从这些数据中提取道路中心线，而不是去实地人工采集。

如果把需要求取道路中心线的区域看作一个多边形，不是道路的相关空间信息作为约束信息，道路中心线的求取问题就可以转化为多边形骨架线的求取。

所谓骨架线，就是用与原形状连通性和拓扑结构相一致的细曲线作为原对象的一种抽象表示，多边形骨架线的本质是对多边形形状的抽象描述，它反映了多边形的延伸方向和形状特征[1-3]。

在GIS中，面状地理空间对象的分析等很多空间操作都需要提取骨架线[4-6]。

多边形骨架线提取的关键是搜寻多边形内部到边界线上的等距离点集，本质上属于空间邻近分析问题。

一般的骨架线的提取算法有：①数学形态学提取骨架线，这种方法本质是矢量化方法；②最大内切圆盘法，最大圆盘完全落于目标图像内，并且至少有2点与目标边界相切。

第３８卷第６期 计算机应用与软件Ｖｏｌ ３８Ｎｏ．６２０２１年６月 ＣｏｍｐｕｔｅｒＡｐｐｌｉｃａｔｉｏｎｓａｎｄＳｏｆｔｗａｒｅＪｕｎ．２０２１适用于电磁场有限元计算的网格剖分算法章春锋　汪　伟　吴天纬　安斯光（中国计量大学机电工程学院　浙江杭州３１００１６）收稿日期：２０１９－１０－１８。

浙江省自然科学基金项目（ＬＹ１９Ｅ０７０００３）；国家自然科学基金项目（６１７０１４６７）。

章春锋，硕士生，主研领域：电磁场有限元剖分与数值计算。

汪伟，教授。

吴天纬，硕士生。

安斯光，副教授。

摘　要 网格剖分是有限元法的关键，其剖分得到的网格质量决定了有限元法计算结果的准确性。

提出基于Ｐｅｒｓｓｏｎ Ｓｔｒａｎｇ算法生成非结构化三角形网格的新算法。

通过分析Ｌａｐｌａｃｉａｎ平滑函数作用原理，提出新的平滑函数来减少迭代次数；提出一种在优化设计过程中无重构变形方法，通过定义边界网格框架利用坐标映射技术可以快速推导出网格；通过设置质量评估来解决不可终止性的可能和过度迭代，加入边界节点筛选功能，并对剖分得到的三角元进行有限元逆序编号处理。

将该算法与Ｐｅｒｓｓｏｎ Ｓｔｒａｎｇ算法进行剖分效果对比，验证该算法应用于电磁场领域的有效性。

关键词 网格剖分　平滑函数　坐标映射　有限元　电磁场中图分类号　ＴＰ３ 文献标志码　Ａ ＤＯＩ：１０．３９６９／ｊ．ｉｓｓｎ．１０００ ３８６ｘ．２０２１．０６．０３５ＭＥＳＨＧＥＮＥＲＡＴＩＯＮＡＬＧＯＲＩＴＨＭＦＯＲＦＩＮＩＴＥＥＬＥＭＥＮＴＣＡＬＣＵＬＡＴＩＯＮＯＦＥＬＥＣＴＲＯＭＡＧＮＥＴＩＣＦＩＥＬＤＺｈａｎｇＣｈｕｎｆｅｎｇ　ＷａｎｇＷｅｉ　ＷｕＴｉａｎｗｅｉ　ＡｎＳｉｇｕａｎｇ（ＣｏｌｌｅｇｅｏｆＭｅｃｈａｎｉｃａｌａｎｄＥｌｅｃｔｒｉｃａｌＥｎｇｉｎｅｅｒｉｎｇ，ＣｈｉｎａＪｉｌｉａｎｇＵｎｉｖｅｒｓｉｔｙ，Ｈａｎｇｚｈｏｕ３１００１６，Ｚｈｅｊｉａｎｇ，Ｃｈｉｎａ）Ａｂｓｔｒａｃｔ Ｍｅｓｈｇｅｎｅｒａｔｉｏｎｉｓｔｈｅｋｅｙｏｆｔｈｅｆｉｎｉｔｅｅｌｅｍｅｎｔｍｅｔｈｏｄ．Ｔｈｅｑｕａｌｉｔｙｏｆｔｈｅｍｅｓｈｇｅｎｅｒａｔｅｄｂｙｔｈｅｍｅｓｈｇｅｎｅｒａｔｉｏｎｄｅｔｅｒｍｉｎｅｓｔｈｅａｃｃｕｒａｃｙｏｆｔｈｅｒｅｓｕｌｔｓｏｆｔｈｅｆｉｎｉｔｅｅｌｅｍｅｎｔｍｅｔｈｏｄ．ＡｎｅｗｕｎｓｔｒｕｃｔｕｒｅｄｔｒｉａｎｇｌｅｍｅｓｈｇｅｎｅｒａｔｉｏｎａｌｇｏｒｉｔｈｍｂａｓｅｄｏｎＰｅｒｓｓｏｎ Ｓｔｒａｎｇａｌｇｏｒｉｔｈｍｉｓｐｒｏｐｏｓｅｄ．ＢｙａｎａｌｙｚｉｎｇｔｈｅｐｒｉｎｃｉｐｌｅｏｆＬａｐｌａｃｉａｎｓｍｏｏｔｈｉｎｇｆｕｎｃｔｉｏｎ，ａｎｅｗｓｍｏｏｔｈｉｎｇｆｕｎｃｔｉｏｎｗａｓｐｒｏｐｏｓｅｄｔｏｒｅｄｕｃｅｔｈｅｎｕｍｂｅｒｏｆｉｔｅｒａｔｉｏｎｓ；ａｎｏｎｒｅｃｏｎｓｔｒｕｃｔｉｏｎｄｅｆｏｒｍａｔｉｏｎｍｅｔｈｏｄｗａｓｐｒｏｐｏｓｅｄｉｎｔｈｅｐｒｏｃｅｓｓｏｆｏｐｔｉｍｉｚａｔｉｏｎｄｅｓｉｇｎ，ｗｈｉｃｈｃａｎｑｕｉｃｋｌｙｄｅｄｕｃｅｔｈｅｇｒｉｄｂｙｄｅｆｉｎｉｎｇｔｈｅｂｏｕｎｄａｒｙｇｒｉｄｆｒａｍｅｗｏｒｋａｎｄｕｓｉｎｇｔｈｅｃｏｏｒｄｉｎａｔｅｍａｐｐｉｎｇｔｅｃｈｎｏｌｏｇｙ；ｔｈｅｐｏｓｓｉｂｉｌｉｔｙｏｆｎｏｎｔｅｒｍｉｎａｔｉｏｎａｎｄｏｖｅｒｉｔｅｒａｔｉｏｎｃａｎｂｅｓｏｌｖｅｄｂｙｓｅｔｔｉｎｇｔｈｅｑｕａｌｉｔｙｅｖａｌｕａｔｉｏｎ，ａｎｄｎｏｄｅｆｉｌｔｅｒｉｎｇｆｕｎｃｔｉｏｎｗａｓａｄｄｅｄｔｏｔｈｅｂｏｕｎｄａｒｙ，ａｎｄｔｈｅｔｒｉｇｏｎｏｍｅｔｒｉｃｅｌｅｍｅｎｔｓｏｂｔａｉｎｅｄｂｙｓｕｂｄｉｖｉｓｉｏｎｗｅｒｅｎｕｍｂｅｒｅｄｉｎｒｅｖｅｒｓｅｏｒｄｅｒｂｙｆｉｎｉｔｅｅｌｅｍｅｎｔｍｅｔｈｏｄ．ＣｏｍｐａｒｅｄｗｉｔｈｔｈｅＰｅｒｓｓｏｎ Ｓｔｒａｎｇａｌｇｏｒｉｔｈｍ，ｔｈｉｓａｌｇｏｒｉｔｈｍｉｓｐｒｏｖｅｄｔｏｂｅｍｏｒｅｅｆｆｅｃｔｉｖｅｉｎｅｌｅｃｔｒｏｍａｇｎｅｔｉｃｆｉｅｌｄ．Ｋｅｙｗｏｒｄｓ Ｍｅｓｈｇｅｎｅｒａｔｉｏｎ　Ｓｍｏｏｔｈｉｎｇｆｕｎｃｔｉｏｎ　Ｃｏｏｒｄｉｎａｔｅｍａｐｐｉｎｇ　Ｆｉｎｉｔｅｅｌｅｍｅｎｔ　Ｅｌｅｃｔｒｏｍａｇｎｅｔｉｃｆｉｅｌｄ０　引　言优异的适应场域边界几何形状以及媒介物理性质变异的能力，使有限元法成为各类电磁场、电磁波工程问题定量分析和优化设计的主导数值计算方法之一［１］。

python中scipy库delaunay的simplices用法全文共四篇示例，供读者参考第一篇示例：Scipy库是一个强大的Python科学计算工具箱，其中包含了许多实用的工具和算法。

其中的delaunay模块是用来进行Delaunay三角剖分的工具，它可以将给定的点集进行三角形网格化，从而用于空间插值、地理信息系统、有限元分析等领域。

在scipy库中，delaunay模块中的simplices属性是一个用于存储Delaunay三角形网格中每个三角形顶点索引的属性。

利用这个属性，我们可以很方便地获取Delaunay三角形网格中每个三角形的顶点索引，从而进行进一步的计算和分析。

我们需要导入scipy库和相关的模块：```pythonimport numpy as npfrom scipy.spatial import Delaunay```接着，我们可以生成一个随机的二维点集，并利用Delaunay函数进行Delaunay三角剖分：现在，我们可以通过simplices属性获取Delaunay三角形网格中每个三角形的顶点索引：输出结果类似如下：```[[0 1 3][1 2 3][1 4 5][1 3 4][0 3 6][2 7 3][1 5 8][4 3 7][8 6 0][7 3 5][6 3 8][3 7 5]]```每一行表示一个三角形，其中的三个数字分别代表该三角形的三个顶点在原始点集中的索引。

通过这些顶点索引，我们可以进一步计算三角形的边长、面积、周长等属性，或者对Delaunay三角形网格进行可视化展示。

除了simplices属性之外，Delaunay对象还提供了许多其他有用的属性和方法，比如`vertex_neighbor_vertices`方法可以用来获取每个点的相邻点的索引列表，`find_simplex`方法可以用来查找给定点所在的三角形索引等等。

这些属性和方法可以帮助我们更好地理解和利用Delaunay三角剖分的结果。

基于Delaunay三角剖分的测头半径补偿算法赵小军【摘要】一个更加科学、合理的半径补偿算法可以有效提高逆向工程的精确度,本文首先对现有的补偿算法进行了介绍,并对其中存在的问题进行了简要分析,然后通过Delaunay三角剖分思想提出了一种基于Delaunay三角剖分的侧头半径补偿算法,并对其中边界点的处成立、三角部分的优化原则等进行了探讨,并以某增压器叶轮叶面为例,对其应用效果进行了说明.【期刊名称】《制造业自动化》【年(卷),期】2011(033)014【总页数】4页(P73-76)【关键词】Delaunay三角剖分;半径补偿;误差消除【作者】赵小军【作者单位】九江学院,数控技术与应用实验室,九江,332005【正文语种】中文【中图分类】TH1230 引言三坐标测量机以其优异的智能化程度和测量精确度被广泛的应用于制造业的质量控制、产品检测和计算机辅助设计当中。

在对自由曲面进行测量时，需要用到三坐标测量机的球形测头，但是测头自身也是有一定的体积的，因此测量结果实际上是与被测量曲面距离为r（测头半径）的包络面，所以，为了得到所需要的测量数据，就必须求出由测头圆心部位轨面所形成的包络面，也就是所谓的测头半径补偿。

在一些对精度要求较高的测量工作中，无法忽略测头半径对测量数据所造成的影响，这样，就需要一个科学的半径补偿算法来对测头半径所产生的误差进行消除。

1 常用的半径补偿算法1.1 二维补偿法二维补偿法的操作方法比较简单，使用范围需也相对较广，该方法在测量时会把测量点与测头半径之间的关系转化为二维情况，现阶段比较常用的二维测量法有三点共圆法和测量方向补偿法。

1.2 三维补偿法在对一些形状规则的表面（如二次曲面、平面等）进行测量时，二维补偿是比较精确的，而在对一些形状较为复杂的曲面（如增加器叶轮叶面）进行测量时，测点位置的曲面法向适量则往往与上述补偿方向分别位于不同的平面内，如果继续使用二维补偿势必会出现误差，所以，在这种情况下就需要采用三维补偿法来进行有关计算。

Delaunay三角剖分插值算法在MT成图中的应用杨利容;简兴祥【摘要】研究并实现了一种基于Delaunay三角剖分的二维快速插值算法,并将其应用于大地电磁(MT)二维反演实时成像网格化处理中.实际资料试算结果表明,该算法具有稳定、插值效果好以及易于模拟地形数据等优点,能满足MT反演结果实时成图的要求.%A rapid two-dimensional linear interpolation algorithm based on the Delaunay triangula-tion for magnetotelluric (MT) inversion process is researched and implemented, and is applied to the data griding in real-time imaging of MT inversion. The result of using the algorithm in true case shows that the algorithm is stable, fast with good interpolation effect, and is easy for simulating topographical data. It can meet the needs of real-time imaging in MT inversion.【期刊名称】《地震工程学报》【年(卷),期】2012(034)001【总页数】4页(P14-17)【关键词】大地电磁二维反演;Delaunay三角剖分;网格化处理;插值算法【作者】杨利容;简兴祥【作者单位】成都理工大学,四川成都610059;四川省核工业地质局,四川成都610021;成都理工大学,四川成都610059【正文语种】中文【中图分类】P631.3+250 引言在大地电磁（MT）反演迭代过程中，需要实时生成多种图件提供给反演解释人员，以动态了解反演拟合的情况，如反演结果二维等值线图、反射系数二维等值线图、实测数据二维等值线图以及当前模型正演的拟合结果二维等值线图等。