大家好。我真的很难理清楚这个问题的逻辑,并希望你们能帮助我。在我继续之前,我想让你知道,我是一名业余程序员,一个初学者,没有任何正式的计算机科学培训,所以请见谅。:D 此外,我正在使用Python,但我可以使用Java或类似的语言。
不管怎样,我想实现区域生长算法并用于一个简单的绘画机器人。以下是关于区域生长的文章:http://en.wikipedia.org/wiki/Region_growing
按照我的设想,描绘图像应符合以下标准:
图像最多为3英寸乘3英寸,颜色深度任意
图像是一个黑色连续形状,背景为白色
形状可以位于背景的任何位置。
我考虑了以下解决方案。虽然某些方案在某种程度上有些作用,但每种方案都存在明显的缺陷,无论从性能还是可行性上(至少对我来说似乎不可行)。此外,因为这是一个绘画机器人,需要用一根连续的线来完成绘制。这并不意味着我不能回头走,它只消除了多个起始点(种子)的可能性。
考虑过的方法:
随机漫步:
用随机漫步来解决这个问题是我的第一反应。我想,实现这个目标的随机漫步程序可能看起来像这样:
伪代码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轴上移动,直到遇到白色像素。从这里,它将向上移动一个像素,然后沿着x轴向左移动,直到达到白色像素。如果它上面的像素也是白色的,就回溯到x轴上找到它上面的黑色像素。
进一步检查后,发现这种方法存在一些主要缺点。当面对这样的形状时:
结果看起来像这样:
即使我告诉它在一段时间后开始向下扫描,中间的腿部仍将被忽略。
4/8 连通邻域:
http://en.wikipedia.org/wiki/8-connected_neighborhood
这种方法对我来说似乎是最强大和有效的,但在这一点上,我无法完全理解它,也无法想出如何实现它,而不会潜在地留下一些遗漏的区域。
在每个单元格中,我将查看相邻的黑色单元格,设计一些排序方法以确定首先访问哪一个,访问所有单元格,然后重复此过程,直到覆盖所有单元格。
我能看到的问题是首先处理完成这项任务所需的数据结构,以及仅仅弄清楚背后的逻辑。
这些是我能想到的最佳解决方案。感谢您花费时间阅读这篇文章,虽然有点长,但我认为我应该尽可能明确。非常感谢任何建议...谢谢!
编辑:
我还研究了迷宫生成和解决算法,但不确定如何在这里实现。我对迷宫解决算法的理解是它们依赖迷宫通道宽度相等。当然,我可能错了。