确定任意多边形中轴的算法

提出确定凸多边形中轴和任意简单多边形中轴两个算法,其基本思想是利用与多边形两条边或三条边等距离的点的轨迹。算法的时间复杂性均为线性的,优于Ｌｅｅ算法（１９８２年）和Ａｇｇａｒｗａｌ算法（１９８９年）。与Ｃｈｉｎ等人提出的算法（１９９９年）具有相同的时间复杂性的阶,但思想方法完全不同,并且产生的结果也不相同,该算法获得直线段树,更有利于应用。

An Algorithm for Determining the Medial Axis of an Arbitrary Simple Polygon

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.