BitNeBolt
@BitNeBolt

Почему так долго выполняется обход в глубину?

Хочу сделать заливку на изображении, как в пейнте. Чтобы закрашивались все пиксели такого же цвета, как на выбранном (пока что сравниваю только один канал). На изображении размером 30*30 все работает хорошо.
Исходник
5f326c5d2c0a2370318763.png
Результат
5f326c738b6d6390838985.png


Но как только я хочу сделать тоже самое с картинкой размером 480*740, то процесс выполняется очень долго. Я проверил скорость выполнения, она постоянная, каждая вершина обрабатывается одинаковое количество времени.

Вот сам обход, без рекурсии:
Код

def dfs_not_recursion(self):        
        while (self.stack != []):            
            peak_vertex = self.stack.pop()
                      
            if (peak_vertex is not None):
                if (not self.is_visited_boolean(peak_vertex)):
                    self.visited_boolean[peak_vertex.y][peak_vertex.x] = True
                    
                    if (self.img[peak_vertex.y][peak_vertex.x][0] == self.start_vertex.color[0]):
                        self.img_draw[peak_vertex.y][peak_vertex.x] = self.GREEN

                        neighbours = peak_vertex.get_neighbours(self.img)

                        for i in neighbours:
                            self.stack.append(i)



Изображение img - исходник, img_draw - то, на котором рисовать.

Почему в пэйнте обработка большого изображения занимает миллисекунды, а здесь - минуты?
  • Вопрос задан
  • 111 просмотров
Решения вопроса 2
tumbler
@tumbler Куратор тега Python
бекенд-разработчик на python
Просто в пейнте используется эффективный алгоритм закраски, а не обход в глубину.

self.visited_boolean[peak_vertex.y][peak_vertex.x]
Вот это вообще очень долго, тут должна быть работа с сырыми строками изображения
Ответ написан
BitNeBolt
@BitNeBolt Автор вопроса
Списки сильно замедляют. Нужно использовать set().
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы