algorithm - 确定解迷宫所需的最小线段数

Question

我遇到一个问题，我需要定义一个多边形，该多边形具有最少数量的顶点，该多边形与不透明的图像中的每个像素相交或包含每个像素(令 N 为图像中的像素数)。我唯一的假设是图像不能在其边界(孔)内包含透明像素，并且至少有两个像素是不透明的。例如，假设我有以下图片:

我对算法的想法是:

1) 确定边缘像素。
这是在 O(N) 时间内完成的，方法是遍历每个像素，并确定是否有任何邻居(在上面剩下的四个像素中) 、右边和下面)是空的。存储像素和哪些邻居是不透明的，通过线性索引键控到像素数组中。假设有P个边缘像素，如下图橙色所示。

2) 获取边缘像素的邻接列表。
这是在 O(P) 时间内完成的，方法是选择一个边缘像素，并根据空邻居选择方向.例如，如果一个像素有一个底部和右侧的邻居，那么下一个像素将是右上角的像素，或者是紧靠右边的像素。从剩余边缘像素的字典中选择下一个边缘像素。将该像素追加到列表中，直到算法返回到起始像素。下面的示例图像中有 27 个边缘像素(有些边缘像素不止一次)。

3) 画一个所有边都必须位于其间的迷宫。
这是在 O(P) 时间内完成的，方法是遍历邻接表，并在那些没有邻居的像素。此外，根据到下一个边缘像素的方向，将边缘添加到形状的内部。如果像素表示一个具有单个像素宽度的半岛，则将内边缘添加到边缘的中间而不是像素顶点。迷宫的内部以红色显示。请注意，迷宫边界是第 2 步中找到的所有边缘像素的超集。

4) 找到一个边缘几乎最小且不接触迷宫边界的多边形。
这是我需要帮助的部分。有没有人建议您如何从第 3 步转到以下解决方案？

Answer 1

我没有图像处理背景，但我遇到了 Ramer–Douglas–Peucker algorithm昨天，我认为这可能会有所帮助。

根据我对维基百科文章的快速浏览，它减少了曲线中的点数，因此我会在每条线上运行该算法，其中线的点是您拥有的端点和 还将线穿过的正方形边界设置为点。

我在这张图片中标出了两行，你可以在上面运行算法，我认为它会起作用。

如何找到每一行以及何时停止 - 不是 100% 确定，但我希望这有用。