logo标签列表

泛洪填充算法用于定义凸多边形区域。

algorithmmath
4
我希望尝试创建一种洪水填充算法，但是这种算法会将空间分成凸多边形区域。
就我的应用程序拥有的数据而言，它只有一个正方形网格，在每个正方形中都包含与基本方向相邻正方形的连接。如果一个正方形被阻塞或以某种方式无效，则我正在测试的正方形在该方向上将没有连接。下面的屏幕截图说明了我的意思，其中黑色正方形是无效的，并代表对象的边界：

enter image description here

我现在想做的是尝试设计一种算法，使我可以将每个网格方块标记为属于凸多边形区域，最好只有尽可能少的区域（即偏爱较大的凸多边形区域而不是许多小碎片）。类似下面这样，每种颜色代表不同的凸多边形区域：

enter image description here

这个问题是否有已知的算法？我查看了一些泛洪填充算法，但似乎没有一个能够形成这样的凸多边形。

谢谢！

4
  1. 这些区域实际上并不是凸的。所有那些锯齿状的边界立刻就打破了凸性。你需要更精确地定义（伪）凸性。例如，非常不清楚为什么小的洋红色三角形不能是绿色的。
  2. 你的第二张图片清楚地表明贪婪算法行不通：如果你切掉蓝色三角形的南部，就可以将黄色和绿色的形状连接起来。
 - user58697
@user58697 是的，你说得对，我没有完全正确地解释情况。锯齿状边缘是可以的：我将使用另一个算法从中创建直线。所谓“凸出”，是指“如果你通过边缘体素的中心画一条线，则为凸出”。我手工绘制了上面的图像，以说明我要做的事情，因此在制作时可能会应用自己的偏见，这就解释了洋红色三角形（你说得对，可能只是绿色的一部分）。我不是要创建与上面完全相同的图像：我想创建能够产生类似结果的东西。 - Neoptolemus
这看起来像是你正在尝试构建某种Voronoi图。 - Stef
你的黑色矩形中的线条是否保证始终呈45度角，就像这个例子一样？如果是这样的话，这可能会使问题变得更容易解决。 - Stef
@Stef 不，黑色形状将是完全任意的。它们可以是任何形状（包括非凸形状）。你说得对，沃罗诺伊图在某种程度上类似于我想要实现的内容。挑战在于黑色形状是静态的，不会“反弹”，而且我没有一组点来扩展，所以我需要一种方法来防止扩展泛滥到角落里。 - Neoptolemus
1
相关: 如何让三角形网格转换为凸多边形。建议: (1) 将黑色形状外的区域进行三角剖分; (2) 应用相关问题答案中建议的算法，将三角形合并成更大的凸多边形。 - Stef
1个回答
0
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接