平面区域三角化的快速算法

摘要：

对于含内环的平面区域三角化问题,一般应先消除内环,将平面区域转化为平面多边形,再进行多边形的三角化.提出一种平面区域三角化算法,通过对平面区域结点和边进行分类,不需插入新的结点,即可将平面区域转化为单调多边形,并给出单调多边形在O(N)时间开销下的三角化算法,从而大大提高了平面区域三角化的总体速度.

关键词：平面区域、单调多边形、三角化

所属期刊栏目：15

分类号：TP391.72(计算技术、计算机技术)

资助基金：教育部高校骨干教师资助计划教技司[2000]65号

在线出版日期：2004-01-08（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：233-238