绣花缝针轨迹问题

运用几何计算和图论理论提出了一个绣花缝针轨迹自动生成算法：先对轮廓走向进行定义，通过轮廓铅垂方向的局部极值点的分割线将图案从上向下进行分割，采用交点的特征值比较彻底地解决了分割时的重点问题，将图案区域准确地划分成缝针能一次完成的若干个节点，在此基础上根据节点的邻接关系建立节点的邻接“图”，通过图论中半哈密尔顿路径或深度遍历方法找到节点的遍历(缝制)序列和每个节点的缝制方向，最后可对设定的起点、终点和缝针间隔的条件自动提供缝针的走向轨迹。

An Algorithm of Finding Path of Embroider Suture Needle

Based on geometry computing and graph theory, an algorithm of finding path of embroidering needle is proposed in this paper. Firstly, outline orientations are defined. And finding all local extreme points of inner outline on their gravitational orientation to build sectioning lines so as to divide the picture. By using intersection point character the overlap point problem is solved perfectly. Therefore, the picture is divided into some nodes which can be finished alone. Then, based on connections of these nodes, an adjacency graph of nodes is built. Using half Hamilton path or depth first search method, both embroidering sequence and direction of these nodes could be got from the graph. Finally, from defined start point, end point and needle spacing, a path of embroidering needle can be generated automatically.