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

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