摘要
提出计算平面点线集三角剖分的一种算法.该算法是利用平面扫描的思想,当扫描线达到事件点时,处理事件点,即将事件点与已被扫描的某些点连接,这样便将已扫描的区域三角剖分.当扫描线达到最左边的事件点时,处理该事件点,就完成了平面点线集的三角剖分.证明了算法的时间复杂性为O(NlbN),其中N是点线集中点的数目与线段端点数之和.
Sweeping algorithm is presented for the triangulation of plane point-line set. The algorithm makes use of the idea of plane sweeping. When the sweep-line reaches it, the event-point will be dealt with, viz., the event-point is connected with some points swept and thus the swept regions are triangulated. When the sweep-line reaches the leftmost event-point, the point will be dealt with, and the triangulation of the plane point-line set is accomplished. It is proved in detail that the time complexities of the algorithm is O(NlbN), where N is the sum of the number of points and the number of line-segment endpoints within the point-line set.
出处
《北京理工大学学报》
EI
CAS
CSCD
北大核心
2004年第2期129-132,共4页
Transactions of Beijing Institute of Technology
关键词
散乱点线集
三角剖分
平面扫描
算法
时间复杂性
debunching point-line set
triangulation
plane sweep
algorithm
time complexity
