Computer Engineering and Applications ›› 2015, Vol. 51 ›› Issue (18): 180-185.

Previous Articles     Next Articles

Algorithm on generation of spiral filling path for planar contour

LIN Zhongwei, HUANG Changbiao, WANG Zehao   

  1. Xiamen Key Laboratory of Digital Vision Measurement, Huaqiao University, Xiamen, Fujian 361021, China
  • Online:2015-09-15 Published:2015-10-13



  1. 华侨大学 数字化视觉测量厦门市重点实验室,福建 厦门 361021

Abstract: It is a complex and cumbersome step to fill the planar contour area in the domain of rapid prototyping and CNC. In order to sublate the characteristic of the vertex offset and segment-offset, an algorithm on hybrid offsetting of vertex and segment is proposed. It is a method of adopting segment-offset at convex point, and uses vertex offset or insert segments at concave point. To reduce the number of interruptions, a spiral path is generated by generating diagonal curve between the similar offset curves. After classifying similar offset curves, the curve with more vertices in every two adjacent offset curves is referred to as the main polygon. By means of the K-D tree created from the vertices in the other curve, the closed vertex is searched for the vertex of the main polygon. Then the points of the diagonal curve are computed by the two closed vertices. The spiral paths are obtained by connecting these points successively.

Key words: Rapid Prototyping(RP), Computer Numerical Control(CNC), hybrid offset, spiral path

摘要: 在快速成型和数控领域中对平面轮廓区域的填充是比较繁琐复杂的步骤。为充分扬弃顶点偏置和线段偏置的优缺点,提出了顶点线段混合偏置算法,即在凹点处采用线段偏置,而在凸点处则采用顶点偏置或插入线段方式;为优化起落刀次数,提出用对角曲线连接偏置曲线形成螺旋轨迹的算法,即在归类相同的相邻两条偏置曲线中,以顶点较多的作为主偏置曲线,利用K-D树在相邻多边形查找主偏置曲线每个顶点的最近点,依次求出对角曲线的离散点并且连接获得螺旋轨迹。

关键词: 快速成型, 数控加工, 混合偏置, 螺旋轨迹