NURBS曲线的多尺度Voronoi图及其若干应用研究

Voronoi diagrams are important geometry data structures in Computational Geometry(CG). Voronoi diagrams, visibility computation and path planning are very important research topics in CG. While the curved polygon are widely used in architectural design, robotics, virtual reality, mechanical design and geometric modeling, little attention has been paid to the research on curved polygon based problems of CG. Also the algorithms of CG are designed without integral consideration...In this project, we will study how to create the multi-resolution Voronoi diagram of a polygon with holes and NURBS curve boundaries, based on which, the efficient algorithms of computing the visibility region of a point, weak visibility region of a NURBS curve, exact visibility region of a moving point, shortest skeleton path and C-free path of two points in the polygon are also studied. These data structure and algorithms collaborate with each other so that they cost less space and time...An open source Software Development Kits will be developed, which will be intergraded into the systems "the Design and Roaming Platform for Virtual Museum". And they also can be applied into the fields of Geometry Modeling, Machine Engineering, GIS, Robotics and so on.

Voronoi图是离散计算几何的一种重要几何结构，其和可见性、路径规划都是计算几何的几大重要研究内容之一。目前，尽管曲线多边形在建筑设计、机器人、虚拟现实、机械加工、几何建模等领域中的应用越来越多，但对基于曲线多边形的计算几何问题的研究还比较少，在设计各算法时也缺少整体考虑。..为此，本项目研究以NURBS曲线为边界的复杂多边形（含"洞"）的多尺度Voronoi图的构造方法，并研究基于该Voronoi图的点的可见性、NURBS曲线的弱可见性、移动点的可见性，和任意两点间的最短骨架路径、C-free最短路径等系列有效算法，实现数据结构和各算法之间的紧密结合和协同，从整体上既节约空间，又节省计算时间，初步形成一个理论体系，并研发一个开源的几何工具包，集成应用到虚拟博物馆等虚拟场景的设计与漫游系统中。..项目理论成果也可用于几何建模、机械工程、模式识别以及机器人等领域。

课题组重点研究了NURBS曲线的性质和参数化优化问题，各类的曲线的Voronoi图构造、可见性、路径计算等问题，开展了基础理论研究和科学应用研究，研发了基于Voronoi图的几何工具包，并研发了虚拟博物馆等三维虚拟场景的设计与漫游系统、无线传感器部署平台、移动虚拟现实等系统，进行系统验证，并扩展应用到移动虚拟现实应用中：提出了针对流线曲线簇的重心Voronoi图的构造方法、随机大数据的曲线多边形Voronoi图生成算法，基于多边形的可见Voronoi图的空间覆盖算法，基于曲线多边形的层次Voronoi图的可见性与路径计算方法，自由曲线路径的弱可见算法，一种称为Variational Circular Treemaps 的层次化数据交互可视化方法与多层次Voronoi图的数据可视化与检索方法、基于Voronoi图的泊松圆盘采样算法、自由曲线C1连续参数优化算法等基础算法，以及虚拟博物馆等三维虚拟场景的设计与漫游系统、无线传感器部署平台、移动虚拟现实系统等集成验证系统。课题共发表学术论文20篇，其中：学术期刊论文12篇，学术会议论文8篇，SCI收录 6篇，EI收录11篇；出版《Voronoi图及其应用》专著1部。申请发明专利 11项，其中授权5项，1个美国发明专利申请；获得软件著作权2个；培养博士后1人，博士研究生2人，硕士研究生9人。参加国际国内会议9次。课题组按计划完成了课题计划目标。