[1]刘建新 卢新明 岳昊.简单多边形快速Delaunay三角剖分算法[J].计算机技术与发展,2006,(07):126-128.
　LIU Jian-xin,LU Xin-ming,YUE Hao.Fast Algorithm for Delaunay Triangulation of Simple Polygon Based on Maximum Triangle Weights[J].,2006,(07):126-128.
点击复制

简单多边形快速Delaunay三角剖分算法()
分享到：

《计算机技术与发展》[ISSN:1006-6977/CN:61-1281/TN]

卷:
期数:
2006年07期
页码:
126-128
栏目:
智能、算法、系统工程
出版日期:
1900-01-01

文章信息/Info

Title:
Fast Algorithm for Delaunay Triangulation of Simple Polygon Based on Maximum Triangle Weights
文章编号:
1673-629X（2006）07-0126-03
作者:
刘建新 卢新明 岳昊
山东科技大学信息科学与工程学院
Author(s):
LIU Jian-xin;  LU Xin-ming;  YUE Hao
Sch. of Info. Sci. and Eng., Shandong Univ. of Sci. and Techn
关键词:
多边形; 三角形权值; Delaunay三角剖分; 时间复杂度; 计算几何
Keywords:
polygon;  triangle weights;  Delaunay triangulation;  time complexity;  computational geometry
分类号:
O18 TP301.6
文献标志码:
A
摘要:
简单多边形的Delaunay三角剖分，在计算机图形学及地学问题三维建模领域有着广泛的应用。文中在借鉴他人的基础上，提出了一种时间复杂度为O（mn）的基于三角形权值最大的简单多边形Delaunay三角剖分算法。三角剖分结果中的三角形形态达到了最优或次优，并进行了理论上的严格证明，对算法的时间复杂度进行了分析，并给出了一个实例。实验结果表明，该方法对于随机生成的简单多边形域三角化速度快，平均计算时间呈近似线性
Abstract:
The Delaunay triangulation of simple polygon, being basic methods of calculating geometry, has been widely applied to computer graphies,3D geographic modeling. This paper presents a fast algorithm for Delaunay triangulation of simple polygon based on maximum triangle weights referring to others. The state of triangle is best or better in the result of triangulation. The correemess and efficiency of the algorithm are confirmed strictly and the algorithm＇s time complexity is illustrated. Finally an example is given. The tested analysis shows that for simple polygonal domains randomly generated, the algorithm is efficient in computation and has an almost linear in running time

相似文献/References:

[1]徐巍 陈东方.基于有向边的Java手机多边形算法研究[J].计算机技术与发展,2008,(08):105.
　XU Wei,CHEN Dong-fang.Research of Polygon on Java Phone Based on Directed Line[J].,2008,(07):105.
[2]魏胜利,李 源.基于交点有序化的简单多边形布尔运算[J].计算机技术与发展,2019,29(08):81.[doi:10. 3969 / j. issn. 1673-629X. 2019. 08. 016]
　WEI Sheng-li,LI Yuan.A Simple Polygon Boolean Operation Based on Sorted Intersection Points[J].,2019,29(07):81.[doi:10. 3969 / j. issn. 1673-629X. 2019. 08. 016]

备注/Memo

备注/Memo:
刘建新（1980-），男，山东聊城人，硕士研究生，研究方向为计算机图形学卢新明，教授，博士生导师，主要从事CAD图形图像的研究以及软件研发与产品设计工作
更新日期/Last Update: 1900-01-01