致命的Python错误:无法从堆栈溢出中恢复.在洪水填充期间

Question

我走到了尽头,经过过度(不成功)谷歌搜索后,我需要帮助.

我正在构建一个简单的PyQt4 Widget,它位于一个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()

任何人都可以帮助诊断问题或者指出解决问题的方向吗？如果我没有详细解释某些内容,请告诉我,我会解决这个问题.

谢谢大家!

Answer 1

您正在使用基于堆栈的森林火灾算法,已知会吃掉大量堆栈,因此最好避免使用它.

我建议避免递归:替代森林火灾算法

我甚至使用你的类对象实现它.使用一些ASCII艺术和您的实际代码进行测试,即使在大区域也能正常工作:

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插入队列中.

处理完所有项目后循环停止:一段时间后,您要么到达边缘,要么只遇到填充点,因此没有额外的点排队.

这种方法只依赖于可用内存,而不是堆栈.

证明它有效:成功填充了一个没有堆栈溢出的巨大蓝色区域.