平面点线集三角剖分的扫描算法
Sweeping Algorithm for Triangulation of Plane Point-Line Set作者机构:北京理工大学信息科学技术学院计算机科学工程系北京100081
出 版 物:《北京理工大学学报》 (Transactions of Beijing Institute of Technology)
年 卷 期:2004年第24卷第2期
页 面:129-132页
核心收录:
学科分类:0810[工学-信息与通信工程] 08[工学] 0805[工学-材料科学与工程(可授工学、理学学位)] 0812[工学-计算机科学与技术(可授工学、理学学位)] 081202[工学-计算机软件与理论]
摘 要:提出计算平面点线集三角剖分的一种算法.该算法是利用平面扫描的思想,当扫描线达到事件点时,处理事件点,即将事件点与已被扫描的某些点连接,这样便将已扫描的区域三角剖分.当扫描线达到最左边的事件点时,处理该事件点,就完成了平面点线集的三角剖分.证明了算法的时间复杂性为O(NlbN),其中N是点线集中点的数目与线段端点数之和.