结晶生长法生成高阶Voronoi图

"这篇文章是2014年发表在《河北师范大学学报/自然科学版》上的科研论文，由周恩辉和刘淑娟合著。研究主要关注高阶Voronoi图的生成方法，通过结晶生长策略来构建这些图。文章讨论了4连通模板和8连通模板在结晶过程中的应用，以及如何根据不同的距离度量（如城区距离、棋盘距离和欧氏距离）生成各种类型的高阶Voronoi图。该研究受到河北省高等学校科学技术研究项目的资助。" Voronoi图，又称Voronoi分解或Dirichlet分区，是计算几何的一个基础概念。它将平面分割成多个区域，每个区域包含了空间中一个特定点集（称为生成元）的所有点，这些点到相应生成元的距离比到其他任何生成元都近。在经典Voronoi图中，距离通常是欧氏距离。然而，高阶Voronoi图是这一理论的扩展，允许使用更复杂的距离度量，例如考虑了多维空间、不规则形状的生成元或者非欧几里得几何环境。 本文提出了一种基于结晶生长的方法来生成高阶Voronoi图。结晶生长是一种模拟自然过程的算法，常用于图像处理和计算机图形学中，以创建复杂且自相似的结构。在该方法中，以生成元作为生长起点，采用4连通或8连通的邻接规则来逐步扩展区域，4连通意味着只考虑上下左右相邻，而8连通则包括对角线上的相邻。通过交替使用这两种模板，可以实现更复杂的边界形成。在结晶生长完成后，根据预先设定的距离度量（如城区距离，棋盘距离或欧氏距离），对不同区域进行进一步的处理，从而得到所需的高阶Voronoi图。 城区距离通常用于模拟城市环境，其中相邻街区的连接性可能不同于简单的欧氏距离；棋盘距离则适用于棋盘状网格结构，其中相邻格子之间的距离是1；而欧氏距离是最常见的距离度量，适用于平滑连续的空间。这些不同距离度量的选择为适应不同应用场景提供了灵活性，使得高阶Voronoi图在地理信息系统、物理模拟、网络设计、图像分割等领域有广泛的应用价值。 这篇论文提供了一种创新的、基于结晶生长的高阶Voronoi图生成技术，这不仅扩展了计算几何的研究领域，也为实际问题的解决提供了新的工具。通过调整生长规则和距离度量，该方法可以灵活地构造出符合特定需求的Voronoi图，对于理解和应用高阶Voronoi图的理论和实践具有重要意义。