摘要
提出确定凸多边形中轴和任意简单多边形中轴两个算法 .其基本思想是利用与多边形两条边或三条边等距离的点的轨迹 .算法的时间复杂性均为线性的 ,优于 L ee算法( 1982年 )和 Aggarwal算法 ( 1989年 ) .与 Chin等人提出的算法 ( 1999年 )具有相同的时间复杂性的阶 ,但思想方法完全不同 ,并且产生的结果也不相同 ,该算法获得直线段树 。
Two algorithms are presented for determining the medial axes of a convex polygon and an arbitrary simple polygon. Its basic idea is to use the locus of the points, which are equidistant from two or three sides of a polygon. Both the algorithms can be constructed in O(n) time. They are better than Lee's(1982) and Aggarwal's algorithms(1989). They have the same orders of time complexity as the algorithm presented by Chin et al(1999), but their methods are quite different, and the obtained results are different, either. The algorithms obtain the trees of straight segments, it is beneficial to applications.
出处
《北京理工大学学报》
EI
CAS
CSCD
2000年第6期708-711,共4页
Transactions of Beijing Institute of Technology
关键词
多边形
中轴
算法
polygon
medial axis
algorithm
