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

Algorithm for Triangulation of Planar Scattered Point-line Set

作　　者：周培德[1] 

机构地区：[1]北京理工大学计算机系,北京100081

出　　处：《计算机辅助设计与图形学学报》2003年第9期1141-1144,共4页Journal of Computer-Aided Design & Computer Graphics

摘　　要：利用平面扫描的思想 ,即利用从右到左移动的 y 轴扫描点线集 当扫描线达到某个给定点或给定线段端点时 ,将该点或端点与其上下相邻线段端点连接 新连线与已三角剖分的边只能在其端点处相交 该算法的时间复杂性为O(NlogN) 。Using the y-axis to sweep across the point-line set from right to left, when it reaches a certain given point or endpoint of the given line segment, connect that point with the next endpoint of neighboring line located above or below it and hitting the moving y-axis first. The newly constructed line shouldn't intercept the existing edges of finished triangulation other than at their endpoint. Time complexity of the algorithm is O(N?logN), where N is the sum of given points and endpoints of given lines.

关 键 词：平面散乱点线集 三角剖分 算法 计算几何 时间复杂性 

分 类 号：O18[理学—数学]