平面多边形的广义梯形分解算法

摘要：

针对机器刺绣和平面型腔行切加工对图形分解的要求,定义了广义梯形的概念,提出了广义梯形分解平面多边形的算法.广义梯形结合了梯形的定义和单调链的思想,广义梯形分解算法以对顶点的分类为基础,借鉴文献(Lorenzetto G P,Datta A,Thomas R C.A fast trapezoidation technique for planar polygons.Computers & Graphics,2002,26(2):281～289)的快速梯形分解框架,通过扫描线方法将平面多边形分解为广义梯形.该算法能够分解内嵌多个环的复杂多边形,分析及测试表明,其时间复杂度为O(nlogn).

关键词：广义梯形、扫描线、单调链、平面型腔行切加工、计算几何

所属期刊栏目：17

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

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

页数：共6页

页码：2636-2641