圆弧和直线段组成的封闭曲线凸凹性快速判定

摘要：

首先通过构造一中介凸多边形求出封闭曲线的方向,然后根据封闭曲线方向确定顶点及圆弧的凸凹性,进而确定封闭曲线的凸凹性.文中算法快速稳定,其时间复杂度为O(n),计算量最多为15n+33k+25次判断、12n-6k+14次乘除法、10n+16k+21次加减法、2次求正余弦和k次开方运算,其中n为封闭曲线顶点和圆弧圆心的个数、k为圆弧个数.

关键词：圆弧、多边形、封闭曲线、封闭曲线方向、凸凹性

所属期刊栏目：16

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

资助基金：国家自然科学基金60374053

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

页数：共7页

页码：1146-1152