平面线段集三角剖分的算法

• 作者: 周培德
• 来源期刊: 计算机工程与科学
• 学科: 工学
• 关键词: 线段集 三角剖分 平面扫描 凸壳 算法 时间复杂性
• 年，卷（期）: 2003,（1）
• 所属期刊栏目: 算法研究
• 页码范围: 20-22
• 页数: 3页
• 分类号: TP301.6
• 字数: 3862字
• 语种: 中文
• DOI: 10.3969/j.issn.1007-130X.2003.01.006

摘要

本文提出了计算平面线段集三角剖分的两种算法.第一个算法是利用平面扫描的思想,当扫描线达到事件点时,处理事件点,即将事件点与已被扫描的某些点连接,这样便将已扫描的区域三角剖分.当扫描线达到最左边的事件点时,处理该事件点, 就完成了平面线段集的三角剖分.第二个算法基于逐层计算凸壳,并将凸壳改变为多边形, 这样便形成嵌套的多边形层,这些多边形覆盖线段集凸壳内的区域,然后三角剖分每个多边形,即完成平面线段集的三角剖分.两个算法的时间复杂性分别为O(nlogn)、 O(mnlogn),其中n为线段集中线段的数目,m为凸壳的层数.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	周培德	北京理工大学计算机科学与工程系	28	414	12.0	20.0