限定Voronoi网格剖分的理论及应用研究
2010-9
蔡强 北京邮电大学出版社 (2010-09出版)
蔡强
139
网格生成技术是研究如何将给定的空间离散为简单几何单元的方法。Voronoi图是一种常用的非结构网格形式，它可以很好地逼近边界，描述结构复杂的空间。还由于其具有数学基础好，对网格的局部控制能力强等优良特性，近年来受到了众多领域的研究人员的关注，在科学计算可视化、石油地质勘探、地理信息系统、气候的变迁、蛛网蜂巢的结构、生物外观轮廓线及中轴、通信基础设施的架设和覆盖、物流供应链监控、医学图像处理等领域有着明显的应用前景。本书全面系统地介绍了限定Voronoi网格及限定Delaunay三角剖分的相关概念及技术，给出了边界边、边界面在限定Voronoi剖分中存在的条件。使用带权Voronoi网格剖分得到了边界一致的复杂限定条件下的网格。带权的Voronoi图是普通Voronoi图的推广。本书采用带权的Delal]nay三角化做为解决限定VorOnoi剖分的基础，仔细设计了若干种算法，所得到的V0ronoi网格具有同Delaunay三角网格相似的优良性质。本书还对曲面和黎曼流形Delaunay剖分进行了探讨。本书包括9章，内容安排如下：第1章概述了Voronoi图的历史及研究应用现状，指出Voronoi图是当今许多学科研究的基础。指出其研究中存在的问题，引出了本文的研究目的、内容及意义。第2章讲述了Voronoi图的基础知识，介绍了其相关的基本概念和基本性质，还介绍了其基本生成方法。第3章先进行了二维限定Voronoi图生成的限定条件的规范化研究，给出了三种新的控制准则，实现了二维限定Voronoi图的生成。对二维限定Voronoi网格进行质量控制和尺度控制，给出了各自的控制准则和相应的算法。第4章研究重叠域和内部狭长区域等复杂限定条件的Voronoi网格剖分问题。第5章，实现了PLC限定条件下的三维限定Voronoi图生成。该算法还实现了对网格的质量和尺度的控制。第6章对曲面限定Delaunay三角化技术进行了研究。第7章给出黎曼流形上的限定Voronoi剖分算法。第8章讨论了图形平台的框架结构。第9章，给出了限定Voronoi图在实际领域中的应用。
《限定Voronoi网格剖分的理论及应用研究》全面介绍了限定voronoi图的概念、生成技术。采用灵活性更好的带权delaunay三角／四面体削分来解决二维／三维限定voronoi网格剖分的问题，所得到的限定voronoi网格具有同限定delaunay三角网格相似的优良性质。建立起了二维／三维限定voronoi的质量和尺度评价准则，设计了二维／三维限定voronoi网格的质量和尺度控制的算法。最后，给出了限定voronoi网格剖分的一些应用实例。 《限定Voronoi网格剖分的理论及应用研究》可供计算几何、地理信息系统、机器人、通信、石油地质勘探及其相关领域的科研人员及高等学校相关专业师生参考使用。
第1章 绪论 1.1 引言 1.2 voronoi图基本概念 1.3 voronoi图的推广 1.3.1 距离的推广 1.3.2 生长元的推广 1.3.3 移动点的voronoi图 1.3.4 poisson voronoi图 1.4 voronoi图生成技术 1.5 voronoi图的国内研究现状 1.6 限定voronoi图的生成 1.7 本书的研究目的、内容及意义 1.8 本书的组织 第2章 限定voronoi剖分相关基本概念、理论 2.1 delaunay三角化 2.1.1 delaunay三角化的特性 2.1.2 经典的delaunay三角化算法 2.2 带权的delaunay三角化和带权的voronoi图 2.3 限定delaunay三角剖分 2.3.1 平面限定delaunay三角化 2.3.2 曲面限定delaunay三角化 2.4 限定voronoi图 2.4.1 二维／三维限定条件 2.4.2 限定voronoi图的生成 第3章 二维限定voronoi网格的研究 3.1 平面限定voronoi网格生成算法 3.1.1 控制圆算法 3.1.2 二维voronoi细化算法——矩形控制带算法 3.1.3 二维voronoi细化算法的改进算法——梯形检测带算法 3.2 二维网格单元质量和尺度控制技术 3.2.1 网格单元质量、尺度的评价标准 3.2.2 控制算法的预处理 3.2.3 voronoi网格的尺寸控制 3.2.4 voronoi网格的质量控制 3.2.5 算法实例 第4章 重叠域条件下的限定voronoi网格生成 4.1 引言 4.2 复杂限定条件下的delaunay三角剖分 4.2.1 内部复杂限定条件 4.2.2 重叠域限定条件 4.2.3 复杂限定条件下限定delaunay三角剖分解决思路 4.2.4 复杂限定条件下的delaunay三角剖分算法 4.3 复杂限定条件下限定voronoi图的生成 4.3.1 算法思路 4.3.2 算法描述 4.3.3 算法的效率 4.4 算法使用的新的数据结构 第5章 三维限定voronoi网格生成的研究 5.1 三维限定voronoi网格的限定条件 5.2 三维限定voronoi网格生成算法 5.2.1 阶段性算法 5.2.2 改进性算法 5.3 三维限定voronoi网格生成实例 第6章 曲面限定delaunay三角化的研究 6.1 算法思路 6.2 算法关键问题 6.3 算法描述 6.4 曲面限定delaunay三角化实例 第7章 黎曼流形上的voronoi剖分的研究 7.1 黎曼流形的基础知识 7.1.1 微分流形与黎曼流形的基本概念 7.1.2 黎曼流形下的delaunay三角化和voronoi图 7.2 存在性研究 7.2.1 存在性 7.2.2 一些性质 7.3 生成算法研究 7.4 基于坐标卡的生成算法 7.4.1 建立坐标卡 7.4.2 生成网格 7.5 黎曼流形的voronoi剖分实例 第8章 算法平台的研究 8.1 系统的实现方案 8.1.1 glview——具有opengl绘图功能的mfcview 8.1.2 glview中opengl环境的保护 8.1.3 glrc的维护 8.2 实例 第9章 限定voronoi剖分技术的应用 9.1 pebi网格生成 9.1.1 pebi网格应用背景 9.1.2 pebi网格模块 9.1.3 pebi网格生成研究现状 9.1.4 pebi网格生成实例 9.2 机器人路径规划 9.2.1 引言 9.2.2 gvg生成研究现状 9.2.3 本章算法 9.2.4 算法实例 9.3 移动通信 9.3.1 引言 9.3.2 小区覆盖问题 参考文献
插图：本书针对限定Voronoi图存在的一些研究热点问题展开研究。针对现存的Voronoi图生成算法中针对限定条件而存在的问题和局限，本书的研究目的是：对任意的输入的限定条件进行规范化，研究完成满足实际应用需求的边界一致的健壮快速的限定’Voronoi图生成算法。主要针对任意限定条件的Voronoi图生成技术目前相关文献成果很少的情况。本书中关于任意限定的二维限定Voronoi图生成的研究成果，解决了对于任意给定的限定条件生成限定Voronoi图的问题。经过仔细的理论研究，本书先后引入了控制圆、矩形检测带、等腰梯形检测带等概念，解决了对限定条件的限制；通过引入桥边和相交环线的概念，提出了区域子分和联动剖分算法，从而将研究引向重叠域情况，实现了重叠域的限定三角网格剖分，进而实现了重叠域的限定Voronoi剖分，同时，该算法还可以很好地控制内部狭长区域附近Voronoi网格的大小，避免生成太小的网格。该算法的研究成果可以很好解决地质建模中的一个难题——逆断层的网格剖分。另外，本书对二维限定Voronoi图中Voronoi多边形的质量控制和尺度控制进行了深人研究，提出了各自的控制准则和相应的算法。
《限定Voronoi网格剖分的理论及应用研究》可供计算几何、地理信息系统、机器人、通信、石油地质勘探及其相关领域的科研人员及高等学校相关专业师生参考使用。
