Delaunay三角剖分算法优化的实现.pdfVIP

总第 234期 计算机与数字工程 Vo1．37No．4 2009年第 4期 Computer DigitalEngineering 34 Delaunay三角剖分算法优化的实现 申利 民 (广州铁路职业技术学院 广州 510430) 摘 要 文章分析 Delaunay三角剖分算法各种优缺点，提 出了具体 的优化思想 。详细介绍了Delaunay三角剖分算法 优化 的设计步骤及实现的具体流程 。通过 VisualStudio．Net中的 c++编程验证了算法的有效性 ，并对该算法的时间复杂 度进行 了分析。 关键词 Delaunay三角剖分 数据结构 算法 图像处理 中图分类号 TP301．6 Algorithm Optimization and ImplementationofDelaunay Triangulation ofThreeDimensional (GuangzhouInstituteofRailwayTechnology，Guangzhou 510430) Abstract Strengthsand weaknessesofvarietiesDelaunay triangulation algorithm arepointed outin thepaper， whichputforwardspecificideastoimprovethealgorithm ．ThedesignstepsandspecificprocessimplementationofDelau- naytriangulationareemphasizedondetail．Effectivenessofthealgorithm isverifiedbyVisualStudio．NetandTimecorn— plexityofthealgorithm isanalysizedin theexperiment． Keywords Delaunaytriangulation，datastructure，algorithm ，imageprocessing ClassNumber TP301．6 Sloan算法 运行效率较高 ，但该算法只用于处理 1 引言 平面点集 ，且程序 比较复杂 ，后 Huang和 ShihE。对 三维空间点集 的Delaunay三角剖分广泛应用 Sloan算法进行了改进 ；GuibasI3提 出著名的支持 于有限元分析和物体三维数字化等方面及图像重 点定位查询 的数据结构 ，即DAG(directedacyclic 构 ，是这些领域 中的一项相当重要 的预处理技术 。 graph)，有向无环图，此算法能实现对点定位的几 在进行的亚微米光 电器件的计算机模拟研究中，三 何搜索的时间复杂度达到 0(1ogn)，但 因为图的记 维 Poisson方程的精确数值求解是一个极 为关键 录 占用了大量的内存，且算法不够简洁，I．Kolingerov~ 的问题 。所 以开发编程实现简单，执行速度较快的 和~alik 对该法进行改进 ，降低了所需的 内存及 Delaunay剖分在研究中具有十分重要意义。 提高了执行 的速度 ；M．Zadravec算法 利用行步 2 Delaunay三角剖分算法的研究 法寻找距离新加入点最近的点，实现对插入点的定 Dela