圆角化的图形区域直骨架及其算法

Rounded Straight Skeleton and its Implementation

在直骨架定义的基础上提出了一种新的图形区域骨架,它仅包含直线边,在结构上比基于Voronoi图的圆骨架更简单,在区域形状描述上比直骨架更接近圆骨架;还提出了一种计算该骨架的算法,在原有直骨架算法的基础上加入了一个对边界凸点的圆角化的预处理过程,并且对实际计算中的特殊碰撞问题进行了处理,以提高计算的鲁棒性.实验结果表明了文中算法的鲁棒性和有效性.

A novel type of skeleton for polygonal figures is introduced and discussed. The new skeleton is based on the straight skeleton, but it is more precise than the straight skeleton in shape description because the strictly-parallel wave front of the straight skeleton is replaced by a rounded one which is close to that of the medial axis. Moreover, it is simpler than the medial axis in structure because it is only composed of linear segments and one kind of elements. The algorithm for this new type of skeleton is also presented. A preprocessing module which converts a reflex vertex into several vertices is added into the original straight skeleton algorithm. These vertices have the same position as the reflex vertex, but they have different propagation directions which make them form an arc after some distance. The special collision problem is taken into account to improve the robustness also. Experiments show that the algorithm is robust and efficient.