平面上不相交线段集的最小边界长凸包求解研究

发布时间：2022-12-23 00:02

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

【文章页数】：63 页

【学位级别】：硕士

【文章目录】：
摘要
Abstract
1 绪论
    1.1 研究背景与意义
    1.2 国内外研究现状
    1.3 研究内容
    1.4 论文的组织结构
    1.5 本章小结
2 相关基础知识与算法
    2.1 基础知识概念
        2.1.1 计算几何学的相关概念
        2.1.2 相关基本概念及定义
        2.1.3 平面上不相交线段集的遍历问题
    2.2 几个经典算法及其性能分析
        2.2.1 Graham Scan算法
        2.2.2 线段与凸多边形位置关系的判断算法
        2.2.3 Rubber-band算法
        2.2.4 局部路径收缩及优化技术
    2.3 本章小结
3 最小边界长凸包的构造方法
    3.1 问题及求解方法概述
    3.2 包含所有线段端点的凸包构造
    3.3 最小边界长凸包的构造过程
        3.3.1 凸包C_0的构造及其特征分析
        3.3.2 凸包边界的收缩方法
    3.4 本章小结
4 算法设计及其分析
    4.1 CHSP算法设计
    4.2 算法的性能分析
    4.3 算法实验结果与分析
        4.3.1 测试数据的生成
        4.3.2 运行结果分析
    4.4 本章小结
结论
参考文献
致谢
作者简历及攻读硕士学位期间的科研成果


【参考文献】：
期刊论文
[1]密集障碍物环境下基于凸包和微粒群优化的机器人路径规划[J]. 巩敦卫,耿娜,张勇.  控制理论与应用. 2012(05)
[2]多边形的简单性、方向及内外点的判别算法[J]. 王志强,肖立瑾,洪嘉振.  计算机学报. 1998(02)



本文编号：3724306