学位论文 > 优秀研究生学位论文题录展示

简单多边形构造方法研究

作　者: 马永卓
导　师: 周之平
学　校: 南昌航空大学
专　业: 计算机技术
关键词: 简单多边形 相交边 Voronoi图 最近邻集
分类号: TP391.7
类　型: 硕士论文
年　份: 2013年
下　载: 16次
引　用: 0次
阅　读: 论文下载
 

内容摘要


平面多边形是由二维空间中一组有序排列的不共线点连接成的封闭区域，它是许多真实物体外形的一种方便而又准确的描述工具，并且在计算机上容易实现。多边形可分为简单多边形和非简单多边形，简单多边形指的是非相邻边不相交且封闭几何内部不存在环路的多边形，其在计算机图形学、图形图像处理、实体造型等领域有着广泛应用，如符号识别、地理信息系统、地理信息传感器网络等。因此，设计一种效率较高且满足实际需要的简单多边形构造算法是非常必要的。目前，已有的构造算法可分为离散点集构造法和线段集构造法。离散点集构造法主要包括二分排序法、坐标平移判断角法、重心方位角法、凸壳构造法和可视区法等。本文在现有简单多边形构造方法的研究基础上，提出一种基于线段集相交测试的构造法，利用改进的平面扫描线算法检测相交边，然后交换相交边的端点构造新的非相交边，逐步更新多边形成简单多边形，该算法能够在初始解较差、多边形存在自相交边的情况下，构造简单多边形。此外，本文针对基于线段相交测试的构造方法时间复杂度较高且路径折线较多的情况，提出了一种基于Voronoi图（V图）的增量式构造算法，首先构造顶点集的V图，根据Voronoi区确定顶点的邻近关系集，减少搜索范围提高算法效率，然后对顶点集进行区域划分，随机选取四个点构造初始多边形，最后结合顶点的邻近关系，按周长增加最小原则依次插入各区域的点，进而构造简单多边形。该算法的时间复杂度为O[n log(n)]。为了验证算法的性能，与bayg29、 ch31的TSP问题进行求解比较。实验结果表明，基于V图的增量式构造算法所生成的简单多边形的周长与TSP最小周长相差甚微，但是算法的效率有较大的提高，表明算法的可行性。

全文目录


摘要  4-5
ABSTRACT  5-9
第1章 绪论  9-15
  1.1 研究的背景及意义  9
  1.2 国内外研究现状  9-12
    1.2.1 离散点集构造法  10-12
    1.2.2 线段集构造法  12
  1.3 本论文研究的主要内容  12-13
  1.4 本文的组织和结构  13-14
  1.5 本章小结  14-15
第2章 简单多边形构造的相关理论基础  15-26
  2.1 简单多边形构造问题  15
  2.2 计算几何基本问题  15-19
    2.2.1 计算几何  15-16
    2.2.2 相关专业术语及其定义  16-19
  2.3 典型基础算法  19-25
    2.3.1 线段求交算法  19-22
    2.3.2 Voronoi 图构造算法  22-24
    2.3.3 Voronoi 图的应用  24-25
  2.4 本章小结  25-26
第3章 基于线段集相交测试的离散点集简单多边形构造方法  26-38
  3.1 简单多边形构造问题描述  26-27
    3.1.1 多边形构造问题  26
    3.1.2 数据结构  26-27
  3.2 基于线段集相交测试的构造算法  27-36
    3.2.1 线段端点预排序  27-28
    3.2.2 平面扫描线法判断相交线段及交点  28-31
    3.2.3 交点处理规则  31-33
    3.2.4 更新多边形  33-34
    3.2.5 算法求解步骤及流程图  34
    3.2.6 算法求解步骤及流程图  34-36
  3.3 算法分析及实验结果  36-37
    3.3.1 算法分析  36
    3.3.2 仿真结果  36-37
  3.4 本章小结  37-38
第4章 基于 VORONOI 图的近邻搜索构造算法  38-50
  4.1 概述  38
  4.2 问题描述  38-39
    4.2.1 简单多边形定义  38-39
    4.2.2 数据结构  39
  4.3 基于 V 图的增量式构造算法  39-47
    4.3.1 初始点的选取  39-40
    4.3.2 邻域的构造与最近邻的选取  40-42
    4.3.3 最少插入原则  42-44
    4.3.4 “孤立点”的处理  44
    4.3.5 算法求解步骤及流程图  44-45
    4.3.6 算法求解步骤及流程图  45-47
  4.4 算法分析及实验结果  47-49
    4.4.1 算法分析  47
    4.4.2 仿真结果  47-49
  4.5 本章小结  49-50
第5章 总结与展望  50-51
  5.1 总结  50
  5.2 展望  50-51
参考文献  51-53
攻读硕士期间发表论文情况  53-54
致谢  54-55

相似论文

  1. 基于密度的局部离群点挖掘算法研究,TP311.13
  2. 基于模型预测控制的足球机器人轨迹跟踪控制研究,TP242.62
  3. 统筹城乡建设用地布局研究,F301
  4. 距离邻近与自然邻近典型聚类方法比较,P208
  5. 基于无线传感器网络的覆盖与连通问题的研究,TN929.5
  6. 空间复杂区域间拓扑关系研究,P208
  7. 加权Voronoi图矢量生成算法研究及其实现,P208
  8. 简单多边形内LR可视问题的求解算法研究,TP301.6
  9. 简单多边形中两个守卫的min-sum算法研究,O18
  10. Delaunay 三角剖分算法研究,TP301.6
  11. 动态大地测量数据融合有关问题研究,P22
  12. 面向航迹规划的电子沙盘技术研究,P208
  13. 基于GIS的山东半岛城市群空间布局研究,P208
  14. 基于GIS的森林可视化与空间结构分析技术研究,S712
  15. 计算几何中LR可视化问题研究,TP391.41
  16. 简单多边形内Euclidean最短路径问题算法研究,O224
  17. 电信IP决策支持系统中聚类算法的应用与研究,TN915
  18. MEMS-DMs（微机电系统变形反射镜）中的有限元分析,TH703
  19. 区位分析中的若干可计算模型研究,P208
  20. 应用Delaunay三角网进行城市居民地和路网自动综合理论和方法研究,P208
  21. 基于模拟退火算法的地图点状要素注记配置研究,P283

中图分类: > 工业技术 > 自动化技术、计算机技术 > 计算技术、计算机技术 > 计算机的应用 > 信息处理（信息加工） > 机器辅助技术
© 2012 www.xueweilunwen.com