我有一个问题，我需要定义一个具有最少数量的顶点的多边形，该多边形与不透明的图像中的每个像素相交或包含每个像素（令 N 为图像中的像素数）。我唯一的假设是图像的边界（孔）内不能包含透明像素，并且至少有两个像素是不透明的。举个例子，假设我有以下图像：
我对算法的想法是：
1) 确定边缘像素。
这是通过迭代每个像素并确定是否有任何邻居（左、上、右、下四个像素中）是否为空来在 O(N) 时间内完成的。存储像素以及哪些邻居是不透明的，通过线性索引将其键入像素数组中。设有P个边缘像素，如下图橙色所示。
2) 获取边缘像素的邻接列表。
这是通过选择边缘像素之一并基于空邻居选择方向来在 O(P) 时间内完成的。例如，如果一个像素有一个底部和右侧的邻居，那么下一个像素将是右上角的像素，或者是紧邻右侧的像素。从剩余边缘像素的字典中选择下一个边缘像素。将该像素附加到列表中，直到算法返回到起始像素。下面的示例图像中有 27 个边缘像素（有些边缘像素不止一次）。
3）画一个迷宫，所有的边都必须位于其间。
这是通过迭代邻接列表并向那些没有邻居的像素上的所有边缘添加边缘来在 O(P) 时间内完成的。此外，根据到下一个边缘像素的方向将边缘添加到形状的内部。如果像素表示单个像素宽度的半岛，则将内边缘添加到边缘的中间而不是像素顶点。迷宫的内部以红色显示。请注意，迷宫边界是步骤 2 中找到的所有边缘像素的超集。
4) 找到一个多边形几乎最小不接触迷宫边界的边缘。
这是我需要帮助的部分。有没有人建议您如何从步骤 #3 转向如下所示的解决方案？
我没有图像处理背景，但我遇到了Ramer-Douglas-Peucker 算法 https://en.wikipedia.org/wiki/Ramer%E2%80%93Douglas%E2%80%93Peucker_algorithm昨天，我认为这可能会有所帮助。
从我对维基百科文章的快速扫描来看，它减少了曲线中的点数，因此我将在每条线上运行此算法，其中线的点是您拥有的端点and还将线穿过的正方形的边界设置为点。
我在这张图片中标出了两条可以运行算法的线，我认为它会起作用。
如何找到每一行以及何时停止 - 不是 100% 确定，但我希望这有用。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
