求生成带障碍边界的Voronoi图的高效实现方案

需求概述 #

• 基于图像分割得到的种子点生成Voronoi图
• 栅格空间内存在“障碍墙”像素，要求障碍墙作为空间边界，墙两侧区域互不连通，Voronoi细胞的生长需受障碍墙阻挡

当前方案与痛点 #

• 现有实现：采用类元胞自动机的暴力生长方式，轮流遍历每个种子点逐步扩展细胞范围
• 核心问题：栅格规模扩大时，算法效率急剧下降，扩展性极差

优化方案（基于Jump Flooding Algorithm的改造） #

Jump Flooding Algorithm虽无法生成完美Voronoi图，但近似结果可满足当前应用场景需求，计划对其做两处关键修改：

• 障碍墙像素跳过逻辑：若当前处理像素为障碍墙颜色，直接跳过重着色操作，避免对障碍区域进行无效处理
• A优化距离计算：在dist()距离检查环节引入A算法，让算法能够识别人工障碍墙，基于连通空间计算实际可达距离，确保Voronoi细胞的扩展符合障碍阻挡后的空间逻辑

内容的提问来源于stack exchange，提问作者Scott