平面散乱点线集三角剖分的算法

摘要：

利用平面扫描的思想,即利用从右到左移动的y-轴扫描点线集.当扫描线达到某个给定点或给定线段端点时,将该点或端点与其上下相邻线段端点连接.新连线与已三角剖分的边只能在其端点处相交.该算法的时间复杂性为O(N logN),其中N是点线集中点的数目与线段端点数之和.

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

所属期刊栏目：15

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

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

页数：共4页

页码：1141-1144