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

摘要

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