自由边界平面连通域Voronoi图生成算法研究

"自由边界平面连通域的Voronoi图生成方法研究" 本文主要探讨了一种在自由边界平面连通域中生成Voronoi图的新方法，该方法旨在简化传统算法的复杂性，提高效率，扩大Voronoi图的应用范围。Voronoi图是一种在几何学和计算机科学中广泛应用的图形，它将平面分割成多个区域，每个区域包含了与特定点（种子点）最近的所有点。在很多领域，如地理信息系统、计算机图形学、数据挖掘等，Voronoi图都有重要应用。 传统的Voronoi图生成算法，如分治法，通常在处理复杂边界条件时面临挑战，这限制了它们在自由边界情况下的使用。为此，作者基于凸多边形的轴算法提出了新的解决方案。新方法首先计算相邻边界元素的平分线，这些平分线是连接两个边界点并将其一分为二的直线。然后，通过找到相邻平分线的交点，选择距离最近的交点来扩展Voronoi图的边缘。这一过程持续进行，直到所有边界点都被包含在内，最终构建出完整的平面单连通域Voronoi图。 此外，针对多连通域的情况，文中还介绍了一种内外边界的Voronoi图合并算法。在多连通域中，可能存在内部区域和外部区域，这些区域的Voronoi图需要有效地整合在一起，以保持整个图的一致性和完整性。合并算法解决了这一问题，确保了不同连通部分的Voronoi图能够正确地连接和对齐。 此研究的贡献在于提供了一种更适应自由边界条件的Voronoi图生成策略，这对于处理具有不规则形状或复杂边界的连通域尤其有价值。通过减少算法的复杂度和提高效率，该方法有望促进Voronoi图在各种工程设计和分析中的应用，比如在城市规划中的设施分布分析、机器人路径规划、结构优化等领域。 关键词：平面连通域；多边形轴算法；平分线；Voronoi图 分类号：TP391.72 文献标识码：A 文章编号：1006-754X(2004)01-0006-05 该论文深入研究了在自由边界条件下生成平面连通域Voronoi图的方法，提出了一种基于平分线和凸多边形轴算法的新技术，对于理解和优化复杂环境下的Voronoi图生成具有重要意义。