自适应平面区域几何划分算法研究

摘要

平面区域几何划分应用广泛，是多个领域的基础研究对象。平面区域几何划分的过程就是多次进行单个多边形自动构建的过程，传统算法主要有两种，一种是基于矢量图形的多边形自动构建，这种方法输出数据精确但是由于搜索范围过广，无法短时间提取单个多边形的边界，特别是增删改操作耗费时间较多，另一种是基于栅格图像的多边形自动构建，这种方法实时效果较好但是会在矢量栅格化中产生数据质量问题，输出数据不够准确。 从矢量与栅格结合的角度出发，利用两者的优点找出结合点，建立矢量与栅格结合的平面区域几何划分算法，算法较好解决了多边形的自动生成。主要研究内容包括： 1.平面区域几何划分算法的建立。通过栅格填充形成的区域边界得出多边形的边界线段集，再利用该线段集进行线段追踪构建多边形。利用矢量法保持数据精度，利用栅格法缩小搜索范围，结合两者优点建立矢量与栅格结合的平面区域几何划分算法，完成多边形的自动生成。 2.平面区域几何划分算法的自适应性提升。针对微小多边形、栅格填充“死角”或“死区”多边形和带连续多岛屿多边形等特殊情况，通过建立交点交线表、岛屿嵌套信息等多种策略完善矢量与栅格结合的平面区域几何划分算法，提升算法的自适应性，使其能自适应区分和处理普通多边形与特殊多边形，同时能自适应处理局部单个多边形构建和全局平面区域几何划分。 3.平面区域几何划分算法的并行加速。为了加快平面区域几何划分算法的计算速度，将采用“分块驱动”策略，针对自适应平面区域几何划分算法的特点，提出一种分块与无缝拼接算法，在块分割后先将子块几何划分，再进行多边形无缝拼接，利用分割时建立的顶点多边形包含关系表对多边形进行配对和拼接，块间利用CPU并行加速。 将通过多组实验检测算法是否能自适应处理并正确生成多种特殊多边形以及多边形间的嵌套关系，最后分析比较算法的执行时间。

目录

声明

第一章 绪论

1.1 课题背景及意义

1.2 国内外研究现状

1.2.1 矢量数据栅格化技术

1.2.2 栅格数据矢量化技术

1.2.3 多边形拓扑关系自动构建技术

1.2.4 数据划分与拼接技术

1.3 存在的问题

1.4 研究内容

1.5 论文组织

第二章 几何划分的多边形自动构建

2.1 引言

2.2 矢量栅格转换方法

2.2.1 矢量数据栅格化

2.2.2 栅格数据矢量化

2.3 基于矢量图形的多边形自动构建

2.4 基于栅格图像的多边形自动构建

2.5 小结

第三章 自适应平面区域几何划分算法

3.1 引言

3.2 矢量与栅格结合的平面区域几何划分算法

3.2.1 单个多边形自动构建

3.2.2 平面区域几何划分

3.3 特殊多边形的自适应处理

3.3.1 栅格填充“死区”多边形处理

3.3.2 微小多边形处理

3.3.3 带连续多岛屿多边形处理

3.4 自适应平面区域几何划分算法流程图

3.5 算法正确性证明

3.6 小结

第四章 几何划分的分块与拼接处理

4.1 引言

4.2 分块与无缝拼接算法

4.2.1 分块处理

4.2.2 无缝拼接处理

4.3 无效拼接的删除

4.3.1 无效拼接的产生

4.3.2 无效拼接多边形处理

4.4 分块与拼接处理实例

4.5 小结

第五章 实验结果与比较分析

5.1 软硬件开发环境

5.2 实验过程及结果分析

5.2.1 计算机随机数据实验

5.2.2 油藏数据实验

5.3 算法时间对比与分析

5.4 小结

总结与展望

参考文献

攻读硕士学位期间取得的学术成果

致谢