平面上几何物体序列遍历算法的优化研究

发布时间：2018-03-19 22:32

本文选题：计算几何　切入点：几何物体序列　出处：《大连海事大学》2016年博士论文　论文类型：学位论文

【摘要】：平面上几何物体序列遍历问题是计算几何学研究领域的核心问题,它不仅涉及可视性识别、最短路径计算、算法设计与优化等基础理论问题,而且也是机器人运动规划、无人机控制等一类实际应用问题的抽象模型,研究这些问题的简单、高效、实用的求解方法,不仅具有理论意义,而且也有很大的实际应用价值。针对几何物体序列遍历问题的研究,虽然已经取得了一些成果,但这些成果一般还存在着数据结构复杂、迭代计算次数多,以及相交点处理时的算法退化等问题,围绕这些问题,本文展开求解算法的优化研究。首先针对不相交线段序列遍历问题的算法优化进行了研究。针对Rubber-band算法在求解该遍历问题时所存在的重复迭代计算等缺陷,采用凸链分解与组合优化技术以及二分检索树存储结构,提出了D(n3襼2n)时间复杂度的优化算法,降低了现有求解算法的时间复杂度,并构造测试数据对改进前后的求解算法做了运行时间性能对比分析。其次,针对可相交线段序列遍历问题,提出了跨线段处理技术,有效地解决了Rubber-band算法不能处理线段相交点的问题,并通过交换相邻线段访问顺序获得了更为精确的最短遍历路径,设计出了D(n~2)时间复杂度的优化算法。在此基础上,针对直线序列遍历问题,采用构造扩大凸多边形的方法,将直线序列遍历问题转化为在凸多边形中求解可相交线段的最短路径遍历问题,设计出了D(n~2)时间复杂度的最优遍历算法,并证明其为求解直线遍历问题的算法时间复杂度下界。最后,针对不相交凸多边形序列遍历问题,分析了凸多边形序列的几何特征,提出了正向划分多边形与逆向定位访问边的组合技术以及最短路径图结构,设计出了O(kn)时间复杂度的最优求解算法。本文深入地研究了平面上几何物体序列的遍历问题,有效地解决了该领域研究中存在的一些问题,所提出的求解算法是到目前为止的最优解决方案,这些方法将有助于巡视员最短路径问题、机器人运动规划等实际应用问题的求解。同时,本文也提出了该研究领域有待进一步研究的问题。
[Abstract]:The ergodic problem of geometric object sequences on the plane is the core problem in the field of computational geometry. It not only involves the basic theoretical problems such as visibility recognition, shortest path calculation, algorithm design and optimization, but also the robot motion planning. Abstract model of UAV control and other practical application problems. It is not only of theoretical significance to study the simple, efficient and practical solving methods of these problems. The research on the ergodic problem of geometric object sequences has made some achievements, but these results generally still have complex data structure and many iterations. And the degradation of the algorithm when dealing with intersection points, and so on. In this paper, the optimization of the solution algorithm is studied. Firstly, the optimization of the traversal problem of disjoint segments is studied. The shortcomings of the Rubber-band algorithm in solving the traversal problem are discussed, such as repeated iterative computation, and so on. By using convex chain decomposition and combinatorial optimization techniques and binary retrieval tree storage structure, an optimization algorithm for time complexity is proposed, which reduces the time complexity of existing algorithms. The performance of the improved algorithm is compared and analyzed by constructing the test data. Secondly, for the traversal problem of intersectable line segments, a cross-segment processing technique is proposed. The problem that the Rubber-band algorithm can not deal with the intersection points of line segments is effectively solved, and the shortest traversal path is obtained by exchanging the access order of adjacent segments, and an optimized algorithm of time complexity is designed. In order to solve the problem of linear sequence traversal, the problem of linear sequence traversal is transformed into the shortest path traversal problem of intersectable line segments in convex polygons by using the method of constructing extended convex polygons. An optimal ergodic algorithm with DX 2) time complexity is designed and proved to be the lower bound of the time complexity of the algorithm for solving the linear traversal problem. Finally, the geometric characteristics of convex polygon sequences are analyzed for the traversal problem of disjoint convex polygon sequences. In this paper, the combination technique of forward partitioning polygon and converse location access edge and the structure of shortest path graph are proposed. An optimal algorithm for solving the time complexity of Oknn is designed. In this paper, the ergodic problem of geometric object sequences on the plane is studied in depth. Some problems in this field are solved effectively. The proposed algorithms are the optimal solutions up to now. These methods will be helpful to the shortest path problem of the inspector. The problem of robot motion planning and other practical applications is solved. At the same time, the problems that need to be further studied in this research field are also presented in this paper.
【学位授予单位】：大连海事大学
【学位级别】：博士
【学位授予年份】：2016
【分类号】：O182.1

【参考文献】