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

Question

[BitNeBolt]

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

Исходник

Результат

Но как только я хочу сделать тоже самое с картинкой размером 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 - то, на котором рисовать.

Почему в пэйнте обработка большого изображения занимает миллисекунды, а здесь - минуты?

Comments

[twobomb]

А get_neighbours где?

[noremorse_ru]

Какая-то страшилка, честно говоря, с проверками явно перемудрил, но... что мешает асинхронно менять цвет?

[Александр Скуснов]

Может, поменять Питон на C++?

Answer 1

[Сергей Тихонов]

Просто в пейнте используется эффективный алгоритм закраски, а не обход в глубину.

self.visited_boolean[peak_vertex.y][peak_vertex.x]
Вот это вообще очень долго, тут должна быть работа с сырыми строками изображения

Comments

[twobomb]

А еще пейнт не на питоне написан.

[BitNeBolt]

Сергей Тихонов, я сделал заливку как промежуточный шаг. Главная идея - находить единое пятно (объект) одного цвета на изображении. Подойдет ли поиск в глубину в таком случае?

Про заливку есть хорошая статья на Хабре: https://habr.com/ru/post/116374/

[Сергей Тихонов]

Возьмите OpenCV, там вместо велосипедов годные плоскогубцы с пассатижами есть.

Answer 2

[BitNeBolt]

Списки сильно замедляют. Нужно использовать set().