朱洪军，张 亚，2

(1.浙江工业职业技术学院数控学院，浙江绍兴 312000;2.浙江大学机械工程系，杭州 310027)

基于位置有效性检测的环形刀路偏置算法研究

朱洪军1，张 亚1，2

(1.浙江工业职业技术学院数控学院，浙江绍兴 312000;2.浙江大学机械工程系，杭州 310027)

数控加工的层切法中经常会用到环形刀路。在环形刀路生成过程中，关键算法是多边形的偏置算法。在偏置过程中，偏置曲线上可能会产生局部问题，比如局部尖角、无效环等。这些局部问题必须消除，否则得到的环形刀路将无法使用。论文提出一种基于顶点位置有效性检测的多边形偏置算法。通过实例测试，表明该算法能够很好地消除在偏置过程中产生的局部问题，保证环形刀路的准确有效。

环形刀路;多边形偏置;位置有效性

0 引言

对于现代化的产品来说，其外形设计中大量使用自由曲线和自由曲面，用传统的机械加工方法相当困难［1］。产品的粗加工是加工过程的一个重要环节，其目的是快速切除工件毛坯上的大部分多余材料，大约70%的原材料由粗加工过程切除，大量的加工时间消耗在粗加工过程中。因而，开发出快速、高效的加工刀路生成算法，对于缩短加工周期、提高加工效率具有重要的实际意义。目前，应用层切法进行数控粗加工在国内已引起了广泛的研究［2-4］。但是，生成环形刀路有一个主要障碍，就是多边形的偏置问题。文献中对多边形偏置问题的解决方法主要可分为以下三种:Voronoi图法、边平移法、角平分线法。

Voronoi图最早由Persson［5］引进到刀具路径生成领域。这种方法能够很好地处理由直线和圆弧构成的轮廓的偏置问题。Held［6］继续发展了Persson的理论，使Voronoi图能够处理带小岛的轮廓偏置问题。虽然Voronoi图一直被认为是一种高效的、鲁棒性好的算法，但是它在计算接近圆弧半径区域的偏置时却容易出错［7-9］。基于边平移的方法由以下三步构成:①多边形每条边在沿着垂直于该边的方向上平移给定的偏置距离;②相邻两条偏置边之间如果不相交则用半径大小等于偏置距离的圆弧衔接，如果相交则以交点为节点修剪两相邻偏置边;③检测偏置多边形上所有的自相交环并移除这些自相交环。Choi等学者［8，10］基于边偏置方法提出了著名的PWID算法。在偏置过程中产生所有的局部或全局无效环都可以用PWID测试方法消除。在角平分线的方法中，初始偏置曲线在原始曲线每个顶点的角平分线上取点连接而成。在初始偏置曲线上，可能存在局部问题，比如局部尖角、无效环等。Kim等学者［11-12］通过检测偏置边的方向有效性来消除局部问题。对一条偏置边，如果它的方向和它的原始多边形上对应边方向相反的话，那么它是方向无效的;反之则是方向有效的。Lee等学者［7］在检查偏置边方向有效的基础上，又提出了检查偏置边位置有效性。对一条偏置边，如果它的两个端点都在偏置区域里面，那么它是位置有效的;反之则是位置无效的。

本文在Lee等方法的基础上，提出基于偏置顶点位置有效性的方法来检测并消除局部问题。其中，初始偏置曲线用基于顶点偏置的方法获得，然后标记出位置无效点两侧的前置有效点和后置有效点。在此基础上，通过文中提出的4个步骤移除期间所有的位置有效点，很好地消除了刀具在偏移过程中产生的局部问题。

1 初始偏置曲线生成

本文中，初始偏置曲线是通过角平分线生成的。如图 1 所示，点 Pi－1，Pi，Pi+1是原始曲线上 3 个连续点，向量 ei－1和 ei分别是向量 PiPi－1和 PiPi+1的单位向量，R是给定的偏置距离，点Oi是点Pi对应的偏置点，θi是角Pi－1PiPi+1的大小。图1a所示是当0＜θi＜π的情况，而图1b是当的情况。结合图1中的两种情况，偏置点Oi可由以下公式(1)计算得到:

图1 基于角平分线的顶点偏置

公式(1)并没有包含θi=π的情况，这是因为在计算初始偏置曲线之前，首先要对原始曲线的每对相邻边进行检查，如果存在相邻边所夹的角是平角，表明这两条相邻边在同一直线上，则删除两相邻边的中间的顶点。对原始曲线的所有顶点按公式(1)计算出相应的偏置点，然后将这些偏置点依次连接起来，便能得到初始偏置曲线，如图2a所示。在图2a中，位于外部的曲线是原始曲线，位于内部的曲线是初始偏置曲线。

2 偏置顶点位置有效性检测

在如图2所示的初始偏置曲线上，存在局部尖角和无效环。这些局部问题是由位置无效的偏置顶点引起的。如图3所示，对于一个偏置顶点O，如果O位于偏置区域里面，那么定义O为位置无效的偏置顶点;否则定义O为位置无效的偏置顶点。对图(3)中的四个偏置点 Oi－1，Oi，Oi+1，Oi+2中，按照上面的定义，可知Oi和Oi+1为位置无效的偏置点，而Oi－1和Oi+2为位置有效的偏置点。

图2 初始偏置曲线生成

图3 原始曲线的偏置区域

检测一个偏置顶点O是否在偏置区域里面需要计算该点到原始曲线的最近距离。如果最近距离小于或大于给定的偏置距离，那么这个偏置顶点就在偏置区域里面，从而判断该点为位置无效的偏置顶点;如果最近距离恰好等于偏置距离，则可以判断该点为位置有效的偏置顶点。原始曲线可以看成是由一系列线段按顺序拼接而成的，所以要计算某个偏置顶点到原始曲线的距离，只需要遍历计算该点到组成原始曲线所有的线段的距离并且从中找出最小值即可。计算点到线段的距离时需要注意的是，如图4所示，假设PjPj+1是原始曲线上的其中一条线段，Pa，Pb，Pc同一平面上的三个点，由图可见，Pa在PjPj+1投影不在线段PjPj+1上但在Pj的左边，这种情况下Pa到线段PjPj+1的距离为PaPj的长度;同理Pc到线段PjPj+1的距离就是PcPj+1的长度;Pb在PjPj+1投影在线段PjPj+1上，这种情况下Pb到线段PjPj+1的距离就是PbP'b的长度。

图4 计算点到线段的距离

3 局部问题移除

局部问题是由位置无效的偏置顶点引起的。在处理这些位置无效的偏置顶点之前，首先需要定位它们前面和后面的位置有效点。实际上，位置无效点有时可能是单个出现的，如图2a中的O2;或者有时可能连续出现，如图2a 中的点列 O4，O5，O6，O7，O8或O11，O12，O13。无论是那种情况，记录下位置无效点序列之前的一个前置有效点和之后的一个后置有效点，分别表示为Ob和Of。显然，在Ob和Of之间的所有点都是位置无效点。如图2a所示，对偏置顶点O2来说，它的前置有效点是O1，它的后置有效点是 O3。对顶点序列 O4，O5，O6，O7，O8来说，它们的前置有效点是O3，他们的后置有效点是O9。具体查找前置有效点和后置有效点的方法可按流程图5来实现。在图5中，b和f分别是输出的前置有效点和后置有效点的在偏置曲线中的点序。

图5 标记前置有效点和后置有效点流程图

对一个局部问题来说，已经确定了前置有效点Ob和后置有效点Of，那么也可以将Ob附近两条前置线段Ob－1Ob和ObOb+1以及Of附近两条后置线段Of－1Of和OfOf+1。移除局部问题具体包含以下四个步骤。

步骤1:计算 ObOb+1和 Of－1Of的交点 PI，检测 PI是否是位置有效点。如果PI是位置有效点的话，那么从偏置曲线中移除点列Ob+1至Of－2，并且令Of－1=PI;如果PI是一个位置无效点的话，那么跳至步骤2。

步骤 2:计算 Ob－1Ob和 Of－1Of的交点 PI，检测 PI是否是位置有效点。如果PI是位置有效点的话，那么从偏置曲线中移除点列Ob+1至Of－2，并且令Of－1=PI;如果PI是一个位置无效点的话，那么跳至步骤3。

步骤3:计算 ObOb+1和 OfOf+1的交点 PI，检测 PI是否是位置有效点。如果PI是位置有效点的话，那么从偏置曲线中移除点列Ob+1至Of－2，并且令Of－1=PI;如果PI是一个位置无效点的话，那么跳至步骤4。

步骤4:计算 Ob－1Ob和 OfOf+1的交点 PI，从偏置曲线中移除点列 ObOb+1至 Of－2，并且令 Of－1=PI。

如图 2a 所示，对于点列 O4，O5，O6，O7，O8来说，它们的前置点和后置点分别是O3和O9。从上述步骤1开始，首先计算O3O4和O8O9的交点PI。因为PI是位置有效点，所以直接移除无效点 O4，O5，O6，O7，并且使O8=PI。这样就可以消除由点列O4，O5，O6，O7，O8引起的局部问题。对点列 O11，O12，O13来说，也只需要上述步骤1就能消除局部问题。而对位置无效点O2来说，它的前置点和后置点分别是O1和O3。从步骤1开始，首先计算O1O2和O2O3的交点PI。显然，在此例中，交点PI和O2重合，而O2是位置无效点，所以跳至步骤2，重新计算O0O1和O2O3的交点PI。此时PI是一个位置有效点，直接令O2=PI。这样由点O2带来的局部尖角问题也能消除了。

值得注意的是，每次消除一个局部问题的时候，在偏置曲线上点的序号会发生一次更新。当初始偏置曲线上所有的点都遍历过一遍时，就能移除所有的局部问题。图2b显示了移除所有局部问题的偏置曲线。

4 实例测试

本文提出的算法用C++语言编程实现并且测试了一些例子。图6为其中两个例子。图6a为图2中图形的连续偏置，图6b为一个“黑桃”形状的连续偏置。从这两张图中，我们可以看出文中提出的方法能够很好的处理偏置过程中局部问题。与Lee等人的算法进行比较可以发现，Lee等人的算法不仅需要考虑偏置线段的位置有效性还需考虑其方向有效性，而本文算法只需要考虑偏置点的位置有效性，算法结构和步骤更加简单，计算时间更快。

图6 文中提出的算法的两个实例

5 总结

本文提出了数控粗加工层切法的一种新的偏置算法，该方法可以对偏置顶点的位置有效性进行检测。初始偏置曲线通过角平分线的方法获得。在初始偏置曲线上，可能存在局部问题，如局部尖角、局部无用环等。这些局部问题通过检测偏置曲线上顶点的位置有效性来消除。对偏置顶点来说，如果该点位于偏置区域里面，那么这些点被定义为位置无效点。通过图5中的流程图标记出 位置无效点两侧的前置有效点和后置有效点。在此基础上，通过文中提出的4个步骤移除期间所有的位置有效点。该方法可以消除层切法数控加工过程中环形刀路的局部问题，保证环形刀路准确有效。

［1］张永超，于洋，赵嫚嫚.加工中直线插补刀路的误差评估修正研究［J］.组合机床与自动化加工技术，2011(6):61－64.

［2］刘伟军，张嘉易.计算机集成制造系统［J］.层切法模具粗加工中自适应刀轨规划方法，2005(9):1296－1300.

［3］庄海军，周儒荣，安鲁陵，等.实体模型的三轴数控粗加工刀轨生成算法［J］.计算机辅助设计与图形学学报，2003，15(1):81 －84.

［4］李学艺，王小椿，陈松，等.离散数据复杂曲面的粗加工［J］.计算机辅助设计与图形学学报，2003，15(3):338－342.

［5］ Persson H:NC machining of arbitrarily shaped pockets.Computer-Aided Design，1978，10(3):169 －174.

［6］Held M，Lukács G，Andor L:Pocketmachining based on contour-parallel tool paths generated by means of proximity maps.Computer-Aided Design，1994，26(3):189 －203.

［7］Lee C-S，Phan T-T，Kim D-S:2D curve offsetalgorithm for pockets with islands using a vertex offset.International Journal of Precision Engineering and Manufacturing，2009，10(2):127－135.

［8］ Choi BK，Park SC:A pair-wise offset algorithm for 2D point-sequence curve.Computer-Aided Design，1999，31(12):735－745.

［9］Dragomatz D，Mann S:A classified bibliography of literature on NC milling path generation.Computer-Aided Design，1997，29(3):239 －247.

［10］Park SC，Choi BK:Uncut free pocketing tool-paths generation using pair-wise offset algorithm.Computer-Aided Design，2001，33(10):739 －746.

［11］Kim H-C，Lee S-G，Yang M-Y:A new offset algorithm for closed 2D lines with Islands.International Journal of Advanced Manufacturing Technology，2006，29(Compendex):1169－1177.

［12］Kim H-C:Tool path generation for contour parallelmilling with incomplete mesh model.The International Journal of Advanced Manufacturing Technology，2010，48(5):443 －454.

(编辑 李秀敏)

Research on the Counter Parallel Tool Path O ffset Algorithm based on Position Validity Checking

ZHU Hong-jun1，ZHANG Ya1，2
(1.School of NC，Zhejiang Industry Polytechnic College，Shaoxing Zhejiang 312000，China;2.Department of Mechanical Engineering，Zhejiang University，Hangzhou 310027，China)

Counter parallel tool path plays an important role in CNC machining process.Initial offset curve is obtained by vertex offset via bisector.in the generation of counter parallel tool path，the key algorithm is polygon offset algorithm.On the initial offset curve，local problems，like invalid loops or sharp anglesmay exist.These local problems should be removed.Otherw ise，counter parallel tool path w ill not be able to use.A new polygon offset algorithm for Point-sequence curve offset based on the effectiveness of the vertex position detection is proposed.The algorithm has been programmed and tested，the results shows that the algorithm can deal wellw ith the local problems in point sequence offset.

counter parallel tool path;polygon offset;position validity

TH16;TG65

A

1001－2265(2013)03－0093－03

2012－10－23;

2012－11－28

朱洪军(1979—)，男，浙江上虞人，浙江工业职业技术学院数控学院讲师，硕士，研究方向为数控技术等，(E－mail)48653963@qq.com。