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

Incremental delaunay algorithm based on signed volume

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

Traditional incremental algorithm for Delaunay needs to locate inserted point globally,or to calculate facet s normal vector;therefore,it is less efficient.This paper presented an incremental insertion algorithm for Delaunay Triangulation based on signed volume.It designed the data structure briefly,and determined the direction of new inserted point by the sign of signed volume of tetrahedral,then searched the center tetrahedral including the new inserted point in its interior,completing point location loca...