区域生长算法

Question

大家好。我真的很难弄清楚这个逻辑，希望你能帮助我。在继续之前，我只想让您知道我是业余程序员，并且是初学者，没有接受过任何形式的正式计算机科学培训，所以请耐心等待。 :D 另外，我正在使用 Python，但我可以使用 Java 或类似的东西。

无论如何，我正在寻求实现一个区域增长以在基本的 Drawbot 中使用。 这是一篇关于区域增长的文章：http://en.wikipedia.org/wiki/Region_forming

按照我的设想，绘制所依据的图像将满足以下标准：

• 在任意颜色深度下图像的尺寸最多为 3x3 英寸

• 图像将是白色背景上的黑色连续形状

• 该形状可以位于背景上的任何位置。

我考虑了以下解决方案来解决这个问题。虽然有些方法在一定程度上有效，但每种方法在性能或可行性方面都存在一些相当大的缺陷（至少对我来说它们似乎不可行）。此外，由于这是一个绘图机器人，因此需要使用一条连续线来完成。但这并不意味着我不能回溯，它只是消除了多个起点（种子）的可能性。

考虑的方法：

随机游走：

用随机游走解决这个问题是我的第一直觉。我想，完成此任务的随机游走程序看起来像这样：

伪 python...

Cells To Visit = Number of Black Cells
Cells Visited = 0
MarkColor = red
While Cells Visited < Cells To Visit:
    if currentcell is black:
        Mark Current Cell As Visited #change pixel to red
        Cells Visited +=1
    neighbors = Get_Adjacent_Cells() #returns cells either black or red
    next cell = random.choose(neighbors)
    currentCell = next cell

虽然我认为这是可行的，但在我看来，它非常无效，并且不能保证良好的结果，但实际上是为了完成某件事我可能最终会尝试这个...我的伪代码中的逻辑是否模糊正确？

扫描模式：

对我来说，这种方法似乎是最容易实现的。我的想法是，我可以选择形状的一个极端处的起点（例如最低的最左边的点）。从那里开始，它将向右绘制，仅在 x 轴上移动，直到遇到白色像素。从这里开始，它将在 y 轴上向上移动一个像素，然后在 x 轴上向左移动，直到到达白色像素。如果其正上方的像素恰好是白色，则在 x 轴上回溯，直到找到其上方的黑色像素。

经进一步检验，该方法存在一些重大缺陷。 当面对这样的形状时：

结果将如下所示：

即使我告诉它在一段时间后开始向下扫动，中间的腿仍然会被忽略。

4/8 互联邻居：

http://en.wikipedia.org/wiki/8-connected_neighborhood< /a>

在我看来，这种方法是最强大和最有效的，但目前我无法完全弄清楚它，也无法想到如何在不留下一些可能被忽视的区域的情况

下 实现它对于每个单元格，我都会查看相邻的黑色单元格，设计某种方法来对我应该首先访问的单元格进行排序，访问所有单元格，然后重复该过程，直到覆盖所有单元格。

我在这里看到的问题首先是处理完成此任务所需的数据结构，并且只是弄清楚其背后的逻辑。

---

这些是我能想到的最好的解决方案。 感谢您花时间阅读本文，我意识到它很长，但我认为我应该尽可能明确。任何和所有建议将不胜感激...谢谢！

编辑：

我还研究了迷宫生成和求解算法，但不确定如何在这里实现。我对迷宫求解算法的理解是，它们依赖于迷宫通道的宽度相等。我当然可能是错的。

Answer 1

基本区域增长，在伪代码中看起来像这样：

seed_point // starting point
visited // boolean array/matrix, same size as image
point_queue // empty queue

point_queue.enqueue( seed_point )
visited( seed_point ) = true

while( point_queue is not empty ) {
    this_point = point_queue.dequeue()
    for each neighbour of this_point {
        if not visited( neighbour ) and neighbour is black/red/whatever
            point_queue.enqueue( neighbour )
            visited( neighbour ) = true
    }
}

// we are done. the "visited" matrix tells
// us which pixels are in the region

我不明白你提到的排名在哪里。我错过了什么吗？

Answer 2

我对这个很长的问题感到困惑。

您确定您不只是尝试进行洪水填充吗？

Answer 3

这是一个关于编写递归迷宫求解器的非常好的小截屏视频： http://thinkcode.tv/catalog/amazing -python/

我认为它可能会给你一些关于你试图解决的问题的想法。

另外，这是我在观看截屏视频后编写的一个递归迷宫解决小脚本 http://pastie.org/1854582 。等宽的通道不是必需的，唯一需要的是开放空间、墙壁和某种结束条件，在这种情况下，找到迷宫的尽头。

如果您不想递归，您可以做的另一件事是使用“回溯”方法。您可以在此页面上看到一个用于随机生成迷宫的小示例：
http://weblog.jamisbuck.org/2011/2/7 /maze- Generation-algorithm-recap（页面上的第一个示例）。

这听起来相关吗？如果是，请告诉我您是否希望我更详细地解释任何内容。

编辑：

这似乎是关于在 python 中进行洪水填充的非常好的讨论 http:// www.daniweb.com/software-development/python/threads/148874

Answer 4

一种可以帮助解决一些迷宫问题的简单技术，即将一只手放在墙上，可能会有所帮助。

但请注意，如果您选择随机起点，则您可能会选择一个点，无论您从那里开始以哪种方式行驶，都会封锁一部分。也就是说，如果你从沙漏形状的中间开始，你只能填充一半。