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

摘要

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