%0 Journal Article
%T Incremental delaunay algorithm based on signed volume<br>基于符号体积值的Delaunay逐点插入法
%A LIN Yi-xin
%A LIU Dong-feng
%A <br>林奕新
%A 刘东峰
%J 计算机应用
%D 2009
%I 
%X 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.
%K incremental algorithm for delaunay
%K delaunay triangulation
%K signed volume
%K point location
%K scattered points<br>Delaunay逐点插入法
%K Delaunay三角剖分
%K 带符号体积值
%K 点定位
%K 散乱点
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=831E194C147C78FAAFCC50BC7ADD1732&aid=2793CBE388E96EF57FD568EC084A67CD&yid=DE12191FBD62783C&vid=771469D9D58C34FF&iid=0B39A22176CE99FB&sid=3389C664025A98F9&eid=FCACFF68346F8D4F&journal_id=1001-9081&journal_name=计算机应用&referenced_num=0&reference_num=9