首页
学习
活动
专区
工具
TVP
发布
社区首页 >问答首页 >致命的Python错误:无法从堆栈溢出中恢复。在泛洪填充期间

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

Stack Overflow用户
提问于 2016-12-05 04:29:20
回答 1查看 16.3K关注 0票数 8

我已经走到了死胡同,在过度(和不成功)的Googling搜索之后,我需要帮助。

我正在构建一个简单的PyQt4小部件,它位于一个由60x80个正方形组成的网格中,每个正方形都初始化为None。如果用户点击该框,它会根据左键单击的次数改变颜色,由下面的列表定义:

代码语言:javascript
复制
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颜色。

下面是完整的程序。

代码语言:javascript
复制
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()

有没有人可以帮助诊断问题,或者指出解决问题的方向?

EN

回答 1

Stack Overflow用户

回答已采纳

发布于 2016-12-05 05:14:16

您使用的是基于堆栈的森林火灾算法,众所周知,它会消耗大量堆栈,因此最好避免使用它。

我对避免递归的建议:alternate forest fire algorithm

我甚至用你的类对象实现了它。用一些ASCII-art和你的实际代码测试它,即使在大的区域上也能很好地工作:

代码语言:javascript
复制
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。

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

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

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

票数 14
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/40963288

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档