平面点线集三角剖分的扫描算法

摘要：

提出计算平面点线集三角剖分的一种算法.该算法是利用平面扫描的思想,当扫描线达到事件点时,处理事件点,即将事件点与已被扫描的某些点连接,这样便将已扫描的区域三角剖分.当扫描线达到最左边的事件点时,处理该事件点,就完成了平面点线集的三角剖分.证明了算法的时间复杂性为O(NlbN),其中N是点线集中点的数目与线段端点数之和.

关键词：散乱点线集、三角剖分、平面扫描、算法、时间复杂性

所属期刊栏目：24

分类号：TP301.6(计算技术、计算机技术)

在线出版日期：2004-03-26（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：129-132