填充凸形的有效方法

Question

说我有一个封闭的形状，如下图所示，我有边缘像素。什么是最有效的方式来填充形状，即把像素“开”里面的造型，如果：

1）我所有的边缘像素

2）我最边缘的像素，而不是全部（如图所示）。

Answer 1

这一切都取决于情况。

如果你手动创建帧缓冲区（基本上使用一个字节数组或类似的东西），你必须迭代你想改变的所有像素。因此，例如，开始于一个行的最左边缘：上排

跳转一个正确的形状的

• 查找开始并接通像素，直到发现行形状的第二端部（或行结束）
• 继续对下一行

这当然只有当你拥有所有边缘像素的工作。看看Marching Squares，可以得到一些帮助。

而且请更具体。 “最有效的方式来填充形状”取决于很多你根本渲染库的，如果它是光栅图形等等...

编辑 注意，该算法的速度要快得多，如果你能生成边缘像素，那么不需要寻找边缘的开始。

Answer 2

之前，您可以填写的东西，你需要确定确切的边界，在这种情况下，将构成识别圈内部。

之后，你可以检查每个像素的圆周围的一个框，如果它实际上在它。由于您必须对圆内的每个像素执行一些操作，并且圆中像素的数量与边界正方形的像素数成线性关系（假设对于某个常量，边界正方形的边具有长度“半径*常量”），则此操作应该接近最佳。

Answer 3

1. 如果单词“里面”的话，边界中的中断将破坏意义。
2. 像人类视网膜一样的神经网络在进行这种处理时非常高效。
3. 在计算机上，您需要花时间来定义“内部”的含义。差距有多大？如何扭曲的边界？
4. 模拟一个很大的圆形虫子弹回“内部”周围 - 太大而不能穿过间隙但小于边界的最小曲率半径?????

Answer 4

标准flood fill算法将是一个凸形相当有效，并且将处理的情况下，形状较不凸起的比你的预期。不幸的是它需要一个不间断的轮廓。

Answer 5

构造凸包并添加缺失的像素。然后使用扫描线算法填充多边形。