c# - 在 C# 中找到一条路径来填充图像的所有阴影区域

Question

我有一张黑白(二进制)图像。它包含一组被白色包围的黑色 Blob 。我正在尝试编写一个 C# 程序，它将找到一条穿过所有阴影区域的单一路径，同时尽可能多地留下白色区域。这与为任何给定层寻找 3D 打印机的工具头路径非常相似；它需要填充实体部分，而只有在需要到达另一个单独的 blob 时才会进入空白区域。

例如，这是我创建的测试图像，其中包括我面临的大部分挑战(为简单起见，只有两个 Blob ):

我想找到一条穿过所有黑色区域的路径，同时只穿过白色区域一次以在两个形状(它们最近的地方)之间跳跃。我还希望路径尽可能短。

我的程序是用 C# 编写的，到目前为止我已经在使用 AForge 进行图像处理，所以我已经可以访问它了。

到目前为止，我得到的最接近的是类似洪水填充的算法。它会从一个角落开始，找到最近的像素(首先是水平的，然后是垂直的)，以继续路径。但这些路径并不总是通向所有地方，交叉通常会形成一条漫长且基本上无关的路径。我还尝试追踪边缘并向内移动，但当 Blob 具有非直线路径时，它仍然不能很好地工作。搜索也没有找到太多；我尝试搜索与 3D 打印算法、洪水填充等相关的内容，但搜索结果并不多。

那么，我应该如何解决这个问题？

Answer 1

1. 填充 Blob

   • 它们只是填充的多边形
   • 将它们转换成一组封闭的凸多边形
   • 或对其进行三角测量
   • 然后渲染成closed polygon filling + triangle/convex polygon rasterisation
   • 展位使用相同的光栅化
   • 所以你会得到一组水平/垂直线(取决于你如何编码)
   • 所以只需将它们连接起来形成一条多段线
   • 还有其他方法可以填充这些区域，但这是最简单且容易出错的方法

2. Blob 之间的运动

   • 这确实是 NP 完全的 TSP(参见 mcdowella 的回答)
   • 将所有闭合多边形作为单独的 blob 处理
   • 使用启发式方法(紧密连接 blob)
   • 限制移动长度作为解决标准