部分泛洪填充

Question

我正在编写一个基于沃罗诺伊图的世界生成器，其中我区分了像山脉、湖泊、森林和海洋这样的地理特征。

每个特征都被赋予一个ID，以便可以标识和引用。我使用洪水填充算法来确定单元格属于哪个特征。

我已经意识到几个类似的情况，我想将一个特征分成多个较小的特征。最直接的例子是两片连接着的大森林之间的一条狭长的森林带。从现实角度来看，应该将其视为两个森林，通过狭窄的森林带隔开，但是我的填充算法会直接穿过并将一切都标记为一个大型森林。

我希望最终能够将它们标记为“西百亩森林”和“东百亩森林”，让它们知道它们来自同一连续的森林体。我查找了部分洪水填充逻辑，但由于缺乏相关术语而陷入了困境。

如果你想看看我正在使用的代码： https://github.com/olinkirkland/map

- Olin Kirkland

Answer 1

您通常会使用一个形态学开运算见维基百科定义，它是一种形态学腐蚀后紧跟着一个膨胀。如果您想象一下在黑色背景上的白色前景对象，则腐蚀将侵蚀（咬掉）物体的边缘，而膨胀将再次扩展/加粗边缘-从而消除小条带和窄连接。

您可以使用Python的Scikit-Image模块或Python或C++中的OpenCV进行此操作。我选择只在终端中使用命令行来执行此操作，这里使用的是安装在大多数Linux发行版上并可用于macOS和Windows的ImageMagick。

因此，使用此地图图像：

我将其加载后反转/否定它以使森林变白，然后应用我提到的形态学开运算，最后再次反转并保存：

magick convert map.png -negate -morphology open disk:5 -negate result.png 

- Mark Setchell

---

请注意，如果您省略两个“-negate”运算符并将“open”替换为“close”，则其效果相同。 - Mark Setchell

请注意，这里有Anthony Thyssen的出色形态学介绍... https://www.imagemagick.org/Usage/morphology/ - Mark Setchell

我不确定如何将这个逻辑应用到构成我的地图的沃罗诺伊多边形上。 - Olin Kirkland

嗯，我们似乎遇到了一些僵局，恐怕我在你的代码中没有看到任何像图像或Numpy数组之类的东西，也没有任何我能够识别或处理的东西 - 我甚至不知道 .as 或 .swc 文件是什么。我担心我们只能把我的答案留作理论练习，无法实现。很抱歉，我们的世界相距太远 :-( - Mark Setchell

没问题！.as 文件非常类似于 .js 文件，它是一个 Actionscript 文件。我真的很喜欢这个问题上各种不同的解答方式，因为它展示了完全不同的解决问题的方法。我尽可能地尝试保持到 Voronoi 图上，这样我以后可以完全访问点和它们的属性（标记森林边缘、空旷地带等）。 - Olin Kirkland

实际上，这与我的答案基本相同，只是我的方法使用模糊和应用阈值来代替逐个处理像素。 - Alfe

Answer 2

找到连通区域后，您可以使用右手法则（https://en.wikipedia.org/wiki/Maze_solving_algorithm#Wall_follower）沿着内部轮廓进行跟踪。

因此，要找到适合作为分割点的单像素路径，可以查找在该内部路径中被访问两次（每个方向一次）的像素。如果在分割点两侧的路径长度足够长，则可以在该像素处将区域分成两个，并尝试使用较小的区域再次进行操作。

如果要找到宽度超过一个像素的分割点，或者确保两侧的森林足够“肥”，建议使用基于像素的方法将其与其他方法相结合：

1. 使用BFS删除距边界小于w的像素。

2. 查找每个剩余的连通区域。每个区域都将是森林的“中心”。

3. 检查每个中心，确保其距离边缘足够远，以成为森林的中心。

4. 将删除的像素添加回去，并将其连接到最近的中心。

- Matt Timmermans

---

一个非常长而窄的森林（1像素宽）怎么样？它会被标记为“分裂”吗？ - Olin Kirkland

是的，我猜想这些东西极不可能从你的生成算法中产生，但如果你需要检查，可以在两侧进行BFS以确保有一些像素与边界足够远。如果您想找到超过2个像素厚度的切割点，也可以从边界开始使用BFS。 - Matt Timmermans

当你这样做时，这个答案开始看起来像其他的答案。我会进行编辑。 - Matt Timmermans

我将使用这种方法，但是使用voronoi点而不是像素。 - Olin Kirkland

Answer 3

您可以使用图像处理技术中的一种方法，即模糊和应用50％的阈值。 这样，细连接和尖锐的峰值会减少，而特征通常会变得更圆润，而对象的整体大小不应在一个特定方向上发生改变。 当重复应用该过程时，以下是过程效果的图像：

通过模糊和应用阈值将森林分开

顶部的图像表示原始情况，其中有两个森林通过一个细长的走廊相连。 逐步进行的处理将消除走廊。

您可以调整此过程中的某些参数，例如模糊半径和步数，以便根据需要进行微调。

- Alfe

---

我非常喜欢这种方法，因为它非常直接，但我不知道如何将其应用于我的沃罗诺伊多边形。整个过程需要在多边形级别上应用，而模糊更多是一种视觉解决方案。我可以将其作为叠加层进行处理，并重新应用森林到仅位于其下面的点，但我正在寻找一种不依赖于绘图就能实现的解决方案。 - Olin Kirkland

您还可以通过分割三角形并使得结果更小的三角形混合其邻居的颜色来模糊三角网格（请参见 https://i.imgur.com/6L6iT1M.png 以获取示例，按照从左上到左下，然后从中上到中下，最后从右上到右下的顺序阅读），但如果您认为这对您的情况不可行，我也能理解。 - Alfe