algorithm-of-findpath

  绣花问题是连续型的填充，在不同区域的缝制过程中，缝针不能提针，因此不能用一般的离散型区 域填充方法处理。本文运用几何计算和图论理论提出了一个绣花缝针轨迹自动生成算法：先对轮廓走向进行 定义，通过轮廓铅垂方向的局部极值点的分割线将图案从上向下进行分割，采用交点的特征值比较彻底的解 决了分割时的重点问题，将图案区域准确的划分成缝针能一次完成的若干个节点。在此基础上根据节点的邻 接关系建立节点的邻接“图”，通过图论中半哈密尔顿路径或深度遍历方法找到节点的遍历（缝制）序列和每 个节点的缝制方向，最后可对设定的起点、终点和缝针间隔的条件自动提供缝针的走向轨迹。(In the process of embroidering, needle can not hang up for changing to a different area. Therefore, Embroider problem could be abstract as a continuous area-filling work. Considering disperse area-filling methods can not process this problem well. Based on geometry computing and graph theory, an algorithm of finding path of embroidering needle are proposed in this paper. First, 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 was 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 was 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 a defined start-point, end-point)