摘要
二维曲线的求交是CAD&CG中的一个基本问题,论文提出了一种由圆弧和直线段组成的二维曲线快速求交方法。首先选择一个最优方向,根据最优方向把封闭曲线分割为一系列单调链,然后通过拓展Bentley-Ottman的扫描线算法对单调链进行求交。算法时间复杂度为O((n+k)logm),其中n为顶点个数,k为交点的个数,m为划分的单调链的个数。
To find intersections among 2D-curve is a basic problem in CAD/CG.This paper presents a fast approach to compute the intersections of arbitrary curve which contains line-segment and circular.Firstly,we should find an optimal direction to minimize the number of monotone chains,then find all the intersection among these monotone chains by ex tending the Bentley-ottmann＇s sweep line algorithm.Time complexity is O（（n＋k）logm）,where n is the number of vertexs of 2D-curve,k is the number of intersections,m is the number of monotone chains.
出处
《计算机工程与应用》
CSCD
北大核心
2006年第14期69-71,85,共4页
Computer Engineering and Applications
基金
河南省教育厅自然科学基金资助项目(编号:200410465201
200510465002)
关键词
二维曲线
圆弧
单调链
求交
扫描线
2D-curve, circular, monotone chains, intersection, sweep line
