Incremental delaunay algorithm based on signed volume
基于符号体积值的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 locally. Furthermore, it applied the sign of signed volume of tetrahedral to the visibility test of facets. For degenerative situation, the perturbation to point set's coordinates was executed to enhance the robustness. Experiment shows that the incremental algorithm for Delaunay Triangulation based on signed volume works more efficiently and needs less computation than traditional algorithm.