基于增量式生成Voronoi图的算法探究及实现  

作　　者：李伏龙 

机构地区：[1]武汉工程大学

出　　处：《数字技术与应用》2024年第11期170-172,共3页Digital Technology & Application

摘　　要：在计算几何中,Voronoi图是一种重要的结构,在机械工程、图形学、机器人、地理信息系统等领域发挥着重要的作用。该算法基于增量式算法生成Voronoi图,在构建点、线段的Voronoi图的基础上,引入了构建圆弧集的Voronoi图的实现,并且使用KDTree、邻接链表、半边数据结构和优先队列四种主要的数据结构,可以提高构建Voronoi图的效率。支持圆弧集的Voronoi图在CAD/CAM中对于加工复杂曲线和圆弧形状的重要性显而易见,这种图形表示方法不仅能够准确建模包含圆弧元素的复杂几何形状,而且在多个制造领域中具有深远的影响。在数控机床加工中,它为路径规划和切削优化提供了有力的工具,并通过最优化刀具路径减少切削时间,提高加工效率,同时支持圆弧集的Voronoi图的引入,使CAD/CAM系统能够更好地应对复杂几何形状的设计和制造挑战,进而提高了整个制造过程的效率和精度。

关 键 词：CAD/CAM系统 VORONOI图 半边数据结构 增量式算法 图形表示 优先队列 图形学 地理信息系统 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]