| 主权项 |
一种闭合路径的搜索方法，用于搜索一条恰经过每个被检测物一次的闭合路径，其特征在于包含：步骤一、将被检测物构成的点集确定为目标点集；步骤二、搜索目标点集的最外层凸包和次外层凸包；步骤三、合并最外层凸包和次外层凸包，以得到最终的最外层闭合路径，具体包含：a)搜索一点P以得到最外层闭合路径和重新确定的次外层凸包：在最外层凸包上搜索一边t1t2，在次外层凸包上搜索一点P，其中点P位于两条分别经过点t1和点t2且垂直于边t1t2的平行线之间，且与最外层凸包上的其余边以及次外层凸包上的其余点相比，点P到边t1t2的距离最短；如果点P到边t1t2的距离小于边t1t2的长度的一半，则将点P纳入边t1t2，得到一最外层闭合路径；以得到的最外层闭合路径所包围的点为搜索范围进行凸包搜索，将搜索到的凸包作为重新确定的次外层凸包；b)对得到的最外层闭合路径和重新确定的次外层凸包执行步骤a)，并重复同样的过程，直至在重新确定的次外层凸包上搜索不到符合条件的点P或无法形成次外层凸包为止，得到最终的最外层闭合路径；步骤四、将最终的最外层闭合路径所包围的点确定为目标点集，执行步骤二～三，得到最终的次外层闭合路径；重复同样的过程，得到一组最终的闭合路径，且该组最终的闭合路径由外到内依次嵌套；步骤五、将该组最终的闭合路径连成一条闭合路径，方法如下：i)在最内层闭合路径上选择两个相邻点A和B，在次内层闭合路径上选择两个相邻点a和b，分别连接，得到线段Aa和Bb，如果用线段Aa和Bb的总长度减去线段AB和ab的总长度得到的差值在所有可选择 的连接中是最小的，则保留线段Aa和Bb，删除线段AB，删除线段ab，以将最内层闭合路径纳入到次内层闭合路径中；ii)重复执行步骤i)，直至将次外层闭合路径纳入到最外层闭合路径中，即该组最终的闭合路径被连成了一条闭合路径；其中，在搜索目标点集的最外层凸包和次外层凸包时，当目标点集中的点的个数小于3时，根据距离最短原则将目标点集中的点纳入与其相邻的闭合路径，以形成最终的最内层闭合路径，并执行步骤五；其中距离最短原则为判断一点到包围该点的多边形的各条边的距离，将该点纳入使该距离最短的边。 |
