简单多边形的动态Delaunay三角剖分算法  

Algorithm for dynamic delaunay triangulation of simple polygon

作　　者：罗小华[1] 付文超[1] 管培祥[1] 张传林[1] 

机构地区：[1]暨南大学信息科学技术学院,广东广州510632

出　　处：《暨南大学学报（自然科学与医学版）》2011年第1期26-30,35,共6页Journal of Jinan University(Natural Science & Medicine Edition)

基　　金：国家自然科学基金天元基金项目(10926141);广东省科技计划项目(2009B01080030)

摘　　要：提出了一种简单多边形的动态Delaunay三角剖分算法,其时间复杂度为O(n).从理论上证明了算法的正确性,并利用Python语言开发了一款动态Delaunay三角网生成软件,最后通过大量数据测试了该软件的健壮性并得到实例证实.A simple dynamic polygon triangulation algorithm is proposed,its time complexity is O（n）.The correctness of the algorithm is proved,and a dynamic triangular mesh generation software is developed.Finally it tested the robustness of the software through a large number of data.

关 键 词：简单多边形 DELAUNAY三角网 空外接圆 PYTHON语言 

分 类 号：TP391.4[自动化与计算机技术—计算机应用技术]