【作者】 李楠；

【导师】 蒋波；

【作者基本信息】 大连海事大学 ， 计算机科学与技术， 2019， 硕士

【摘要】 本文针对平面上不相交线段集的最小边界长凸包问题进行研究,目标是要找到一个包含或者经过每条给定线段的最小边界长凸包。该问题的研究,不仅具有较大的理论价值,而且也有很大的实际应用价值。因为它有助于求解机器人行进路线、最优物流配送路线、机械零件的切割等一类实际应用问题。本文首先论述了 TSP、WRP以及Rubber-band算法等相关知识概念以及现有相关研究成果。然后在此基础上,深入研究与分析了与本文研究问题相关的研究,指出了现有研究结果所存在的不足,即算法时间复杂度较高等。为改进已有相关算法的不足,本文通过分析线段与凸多边形的位置关系等要素,设计出了一个求解平面内给定的不相交线段集的最小边界长凸包问题的优化算法,将计算最小边界长凸包分为两个主要过程.:一是求出包含所有线段的凸包;二是收缩所得到的凸包且同时保证没有任何一条线段会完全位于凸包的外部,从而求出一个具有最小边界长的凸包。通过上述两个过程的有机融合,本文设计出了一个O(n4)的求解算法,优化了求解该问题的现有算法。更多还原

【Abstract】 In this paper,we research on a solution of finding a minimum convex hull for disjoint segments given in the plane.Our purpose is to obtain a shortest perimeter that contain or partly contain these segments.This problem not only has significant theoretical value,but also has more important practical application value.Because it is helpful to solve practical application problems such as walking route of robot,optimal distribution route of logistics planning and cutting machine components.This paper firstly gives a discussion of the TSP,WRP,Rubber-band algorithm and other relevant research results.Then on the basis of existing research results,research and analysis the problem about minimum boundary convex hull of given disjoint segments.And it points out that the problems existing in previous research,for example,high time complexity.In order to solve these problems,this paper presents an algorithm which the complexity is in O(n4)through the analysis of the position of segment and convex polygon and other geometric elements.This algorithm can be divided into two main processes.Firstly,find the convex hull of containing all the segments with the Graham Scan Algorithm.Secondly,contract the convex hull and make sure no segment is completely outside the convex hull to obtain a convex hull with a minimum boundary through the organic integration of the algorithm.更多还原