10

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

任何人，我都希望实现一个区域增长，以便在基本的 Drawbot 中使用。这是一篇关于区域增长的文章：http ://en.wikipedia.org/wiki/Region_growth

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

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

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

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

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

考虑的方法：

随机游走：

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

伪蟒蛇...

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 轴上回溯，直到找到其上方的黑色像素。

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

图1

结果将如下所示：

图2

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

4/8 连通社区：

http://en.wikipedia.org/wiki/8-connected_neighborhood

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

在每个单元格中，我都会查看相邻的黑色单元格，设计一些方法来排列我应该首先访问哪个单元格，访问所有单元格，然后重复该过程直到所有单元格都被覆盖。

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

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

编辑：

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

4

4 回答 4

5

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

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

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

于 2011-05-01T21:01:41.750 回答
2

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

你确定你不只是试图做一个洪水填充？

于 2011-05-01T23:23:58.273 回答
1

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

但是请注意，如果您选择了一个随机的起点，您可能会选择一个点，无论您从那里走哪条路，都会挡住一部分。即，如果您从沙漏形状的中间开始，您将只能填充一半。

于 2011-05-01T20:51:17.040 回答
1

这是一个关于编写递归迷宫求解器的非常好的小截屏视频：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

于 2011-05-01T21:32:17.323 回答