-
题名平面线段集三角剖分的算法
被引量:3
- 1
-
-
作者
周培德
-
机构
北京理工大学计算机科学与工程系
-
出处
《计算机工程与科学》
CSCD
2003年第1期20-22,共3页
-
文摘
本文提出了计算平面线段集三角剖分的两种算法。第一个算法是利用平面扫描的思想,当扫描线达到事件点时,处理事件点,即将事件点与已被扫描的某些点连接,这样便将已扫描的区域三角剖分。当扫描线达到最左边的事件点时,处理该事件点,就完成了平面线段集的三角剖分。第二个算法基于逐层计算凸壳,并将凸壳改变为多边形,这样便形成嵌套的多边形层,这些多边形覆盖线段集凸壳内的区域,然后三角剖分每个多边形,即完成平面线段集的三角剖分。两个算法的时间复杂性分别为O(nlogn)、O(mnlogn),其中n为线段集中线段的数目,m为凸壳的层数。
-
关键词
平面线段集
三角剖分
算法
凸壳
时间复杂性
计算几何
-
Keywords
line-segment set
triangulation
plane sweep
convex hull
algorithm
time complexity
-
分类号
O18
[理学—基础数学]
TP301.6
[自动化与计算机技术—计算机系统结构]
-