论文部分内容阅读
二维曲线的求交是CAD&CG中的一个基本问题,论文提出了一种由圆弧和直线段组成的二维曲线快速求交方法。首先选择一个最优方向,根据最优方向把封闭曲线分割为一系列单调链,然后通过拓展Bentley-Ottman的扫描线算法对单调链进行求交。算法时间复杂度为O((n+k)logm),其中n为顶点个数,k为交点的个数,m为划分的单调链的个数。