基于符号体积值的Delaunay逐点插入法

摘要：

传统Delaunay逐点插入法需在全局范围内进行点定位操作,或涉及到面的法向量计算,效率较低.提出一种基于符号体积值的Delaunay逐点插入法.设计简要的数据结构,利用四面体带符号体积值的符号,判断新插入点所在方位,逐步搜索将该新插入点包含在其内部的中心四面体,完成局部范围的点定位;进一步利用体积值符号进行Delaunay空洞可视面测试;对多点共面或共球的退化情况,将点坐标加以细微扰动,提高算法健壮性.实验结果表明,基于符号体积值的Delaunay逐点插入法的点定位操作效率较高,计算量相对减少.

关键词：Delaunay逐点插入法、Delaunay三角剖分、带符号体积值、点定位、散乱点

所属期刊栏目：29

分类号：TP391(计算技术、计算机技术)

资助基金：广东省自然科学基金资助项目5001835

在线出版日期：2009-04-01（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：459-461,464