机械臂绘画栅格图像无重叠矩形笔触生成算法选型咨询

优先选融合了单颜色区域提取优化逻辑的改进版边缘导向填充方案（即方法3+方法2的组合逻辑），方法1、方法4不建议使用。

各候选方案的实际问题 #

• 方法1：全图随机生成矩形的计算效率极低，绝大多数随机采样的矩形会落在异色区域、空白区域或者已填充区域，大尺寸矩形阶段的有效留存率通常不到1%，哪怕生成10万个随机矩形，整体区域覆盖率也很难超过30%，完全没必要浪费算力在无效采样上。
• 方法2：本质是性能优化手段，不能作为独立的填充算法使用。如果只靠单颜色区域内随机放矩形，生成的笔触和区域轮廓、纹理走向完全不匹配，后期小尺寸补漏阶段会产生大量短笔触，机械臂抬笔、移动的空跑时间会暴涨。
• 方法4：点绘方案的笔触总量是矩形笔触的15~20倍，整体绘画时长会拉长到完全不可接受的程度，直接排除即可。

可直接落地的实现流程 #

我之前给CNC绘画设备写过同类路径生成逻辑，这套流程跑下来笔触重叠率可以控制在0.1%以下，完全满足所有约束要求：

1. 预处理环节
   • 先做颜色量化，把输入栅格图的所有像素映射到实际使用的颜料色值集合，按颜色拆分独立图层，每个图层只保留对应颜色的像素；再对每个颜色图层做连通域分析，拆分出同色的不连通区块，直接解决向日葵花瓣这类独立同色区域的处理问题。
   • 对每个同色连通域做边缘检测，计算每个边缘像素的梯度方向，这个方向就是大尺寸矩形笔触的优先排布方向。
   • 初始化一个和原图同尺寸的二值覆盖蒙版，初始值全为0，专门用来标记已经被笔触覆盖的像素。新矩形的合法性判断直接通过这个蒙版做：只有当矩形覆盖范围内的蒙版值全为0、且矩形内95%以上像素属于当前同色区域时，才允许保留这个矩形；矩形保留后，立刻把它覆盖区域的蒙版值全部设为1，从校验逻辑上彻底杜绝笔触重叠。
2. 分层填充环节
   • 按使用的最宽笔触尺寸设置初始矩形长度（一般设为笔触宽度的8~10倍即可），优先沿着之前计算好的边缘梯度方向放置矩形，每成功放置一个就更新覆盖蒙版。
   • 单轮大尺寸矩形放置完成后，把矩形长度按20%的比例缩小，重复放置流程，直到矩形长度降到和笔触宽度一致。
   • 填充顺序按「同色优先、大区域优先」排序：填完一个颜色的所有连通域再换下一个颜色，单个颜色内先填面积大的连通域再填小的，尽可能保证同色笔触连续绘制，减少换颜料、洗笔的次数。
3. 补漏环节
   • 遍历覆盖蒙版，找到所有还没被笔触覆盖的同色像素点，用最小尺寸的正方形笔触（长宽等于笔触宽度）沿像素聚集方向补全即可。

实用优化技巧 #

• 矩形校验不要用逐像素遍历的方式，提前给覆盖蒙版、颜色图层做积分图预处理，矩形区域的重叠占比、同色占比都可以通过积分图在O(1)时间内算出，整体填充速度能提升两个数量级。
• 单个连通域内的笔触可以用最近邻算法排序，把空间上相邻的笔触排到连续的绘制序列里，减少机械臂空跑的距离。
• 误差阈值不要设成全局固定值：轮廓边缘区域的误差阈值设小一点，保证轮廓清晰；内部平涂区域的误差阈值设大一点，尽可能多用大尺寸笔触，减少碎笔触数量。

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