我已经走到了死胡同,在过度(和不成功)的Googling搜索之后,我需要帮助。
我正在构建一个简单的PyQt4小部件,它位于一个由60x80个正方形组成的网格中,每个正方形都初始化为None
。如果用户点击该框,它会根据左键单击的次数改变颜色,由下面的列表定义:
self.COLORS=[
(0, 0, 255), #WATER
(255, 210, 128), #SAND
(0, 128, 0), #GREEN
(255, 255, 0), #YELLOW
(255, 165, 0), #ORANGE
(255, 0, 0) #RED
]
如果用户右键单击,它会使用常见的递归泛洪填充算法来泛洪填充一个区域。这对于很小的空间非常有效,但是如果空间足够大,程序会失败,并出现错误Fatal Python error: Cannot recover from stack overflow.
我不知道如何解决这个问题,也许是泛洪填充不是递归的?
所有正方形和后续颜色代码都存储在self.cells
中,因此通过设置self.cells[(y,x)]=1
可以将单元格(y,x)
设置为Sand
颜色。
下面是完整的程序。
import sys
from PyQt4 import QtGui, QtCore
class Example(QtGui.QWidget):
def __init__(self, cell_size=10, swidth=800, sheight=600):
QtGui.QWidget.__init__(self)
self.resize(swidth,sheight)
self.cell_size = cell_size
self.height = sheight
self.width = swidth
self.columns = self.width // self.cell_size
self.rows = self.height // self.cell_size
self.COLORS=[
(0, 0, 255), #WATER
(255, 210, 128), #SAND
(0, 128, 0), #GREEN
(255, 255, 0), #YELLOW
(255, 165, 0), #ORANGE
(255, 0, 0) #RED
]
self.cells = {(x,y):None for x in range(1,self.columns+1) for y in range(1,self.rows+1)}
def translate(self,pixel_x, pixel_y):
"Translate pixel coordinates (pixel_x,pixel_y), into grid coordinates"
x = pixel_x * self.columns // self.width + 1
y = pixel_y * self.rows // self.height + 1
return x,y
def check_cell(self,x,y):
if self.cells[(x,y)] <= 0:
self.cells[(x,y)]=0
elif self.cells[(x,y)] >= len(self.COLORS)-1:
self.cells[(x,y)]=len(self.COLORS)-1
else:
pass
def draw_cell(self, qp, col, row):
x1,y1 = (col-1) * self.cell_size, (row-1) * self.cell_size
x2,y2 = (col-1) * self.cell_size + self.cell_size, (row-1) * self.cell_size + self.cell_size
qp.drawRect(x1, y1, x2-x1, y2-y1)
def color_cell(self, qp, col, row):
qp.setBrush(QtGui.QColor(*self.COLORS[self.cells[(col,row)]]))
self.draw_cell(qp, col, row)
def draw_grid(self, qp):
qp.setPen(QtGui.QColor(128,128,128)) # gray
# Horizontal lines
for i in range(self.rows):
qp.drawLine(0, i * self.cell_size, self.width, i * self.cell_size)
# Vertical lines
for j in range(self.columns):
qp.drawLine(j * self.cell_size, 0, j * self.cell_size, self.height)
def set_all(self, type):
self.cells = {(x,y):type for x in range(1,self.columns+1) for y in range(1,self.rows+1)}
self.repaint()
def fill(self, x, y, type):
print(x,y)
if x < 1 or x >= self.columns+1 or y < 1 or y >= self.rows+1:
return
if self.cells[(x,y)] != None:
return
self.cells[(x,y)] = type
self.repaint()
self.fill(x+1, y, type)
self.fill(x-1, y, type)
self.fill(x, y+1, type)
self.fill(x, y-1, type)
def paintEvent(self, e):
qp = QtGui.QPainter()
qp.begin(self)
self.draw_grid(qp)
for row in range(1, self.rows+1):
for col in range(1, self.columns+1):
if self.cells[(col,row)] != None:
self.color_cell(qp, col, row)
qp.end()
def drawPoints(self, qp):
size = self.size()
for i in range(1000):
x = random.randint(1, size.width()-1)
y = random.randint(1, size.height()-1)
qp.drawPoint(x, y)
def mousePressEvent(self, e):
x,y = self.translate(e.pos().x(),e.pos().y())
if e.button() == QtCore.Qt.LeftButton:
if self.cells[(x,y)] == None:
self.cells[(x,y)]=0
else:
self.cells[(x,y)]+=1
self.check_cell(x,y)
elif e.button() == QtCore.Qt.RightButton:
self.fill(x,y,0)
'''
if self.cells[(x,y)] == None:
self.cells[(x,y)]=0
else:
self.cells[(x,y)]-=1
self.check_cell(x,y)
'''
else: pass
self.repaint()
def save(self):
return self.cells
def open(self, new_cells):
self.cells=new_cells
self.repaint()
def main():
app = QtGui.QApplication(sys.argv)
ex = Example()
ex.show()
sys.exit(app.exec_())
if __name__ == '__main__':
main()
有没有人可以帮助诊断问题,或者指出解决问题的方向?
发布于 2016-12-05 05:14:16
您使用的是基于堆栈的森林火灾算法,众所周知,它会消耗大量堆栈,因此最好避免使用它。
我对避免递归的建议:alternate forest fire algorithm
我甚至用你的类对象实现了它。用一些ASCII-art和你的实际代码测试它,即使在大的区域上也能很好地工作:
def fill(self, x, y, t):
if self.cells[(x,y)] == None: # cannot use not: there are 0 values
to_fill = [(x,y)]
while to_fill:
# pick a point from the queue
x,y = to_fill.pop()
# change color if possible
self.cells[(x,y)] = t
# now the neighbours x,y +- 1
for delta_x in range(-1,2):
xdx = x+delta_x
if xdx > 0 and xdx < self.columns+1:
for delta_y in range(-1,2):
ydy = y+delta_y
# avoid diagonals
if (delta_x == 0) ^ (delta_y == 0):
if ydy > 0 and ydy < self.rows+1:
# valid x+delta_x,y+delta_y
# push in queue if no color
if self.cells[(xdx,ydy)] == None:
to_fill.append((xdx,ydy))
self.repaint()
当你通过一个点时,它会检查是否必须填充。如果必须填充,则将其插入队列并运行循环。
循环只是从队列中弹出一项,更改其颜色,并尝试对其邻居执行相同的操作:如果仍然在图片中(x,y边界检查),而不是对角线,并且没有在邻居上定义颜色,则只需在队列中插入coord。
当处理完所有项目时,循环停止:一段时间后,要么到达边缘,要么只遇到填充点,因此不会有额外的点排队。
这种方法只依赖于可用内存,而不依赖堆栈。
证明它是有效的:成功地填充了一个巨大的蓝色区域,没有堆栈溢出。
https://stackoverflow.com/questions/40963288
复制相似问题