Кратък урок за алгоритъма Flood Fill
АлгоритъмътFlood Fill се използва за замяна на стойности в дадена граница. Този алгоритъм може да бъде програмиран по различни начини, но обичайният метод използва рекурсия за сравняване на стари и нови стойности.
Докато Flood Fill може да бъде написан на всеки език за програмиране, следващият пример използва Python за простота.
Ако искате да преминете направо към кода, примерът е достъпен в моя GitHub.
Алгоритъмът за запълване на наводнения е обяснен
Преди да започнем да програмираме запълването на наводнението, нека отделим малко време, за да опишем накратко как работи.
Ако някога сте използвали програма за рисуване или рисуване преди, има вероятност тя да е имала инструмент за кофа за рисуване или нещо подобно. Този инструмент позволява на потребителя да запълни област с даден цвят. Обикновено потребителите могат да начертаят затворена граница и да запълнят тази форма с даден цвят.
Следващият пример, създаден в GIMP, показва какво имам предвид.
Познатият инструмент за кофа за рисуване е реализация на алгоритъма за запълване на наводнение. Този алгоритъм започва с начална точка, предоставена от щракване на мишката на потребителя. Оттам нататък алгоритъмът търси всеки съседен пиксел, променяйки цвета му, докато не стигне до границата.
Познатият инструмент за кофа за рисуване е реализация на алгоритъма за запълване на наводнение. Този алгоритъм започва с начална точка, предоставена от щракване на мишката на потребителя. Оттам нататък алгоритъмът търси всеки съседен пиксел, променяйки цвета му, докато не стигне до границата.
Разбиване на проблема
В примера с кофата за боядисване се рисуват само пикселите, които са в рамките на границата. Тези извън кръга остават недокоснати.
Процесът в две стъпки може да се обобщи, както следва:
- Избор на отправна точка
- Проверете всеки съсед, докато не се натъкнем на граница
Получаване на 2D
Ще започнем упражнението, като създадем двуизмерен масив. Този 2D масив може да представлява много неща, включително пикселите в изображение или клетките в симулация. Засега ще използваме само прости цифри.
Ще използваме числото 0, за да представим празно пространство, и числото 1, за да представим запълнено пространство.
# we'll need a 2D array to practice on
field = [
[0,0,0,0,0,0,0],
[0,1,0,0,0,0,0],
[0,1,1,0,0,0,0],
[0,0,0,0,0,1,0],
[0,0,0,0,1,1,0],
]
След това ще ни трябва начин да видим масива. Ще напишем функция, която преминава през масива и показва съдържанието в конзолата.
def print_field():
# this function will print the contents of the array
for y in range(len(field)):
for x in range(len(field[0])):
# value by column and row
print(field[y][x], end=' ')
if x == len(field[0])-1:
# print a new line at the end of each row
print('\n')
Стартирането на програмата ще ни покаже полето в конзолата.
Изход
0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 0
Наводняване на полето
Нашата реализация на flood fill ще използва рекурсивен алгоритъм. Започвайки с начална точка, ще проверяваме всяка съседна точка, докато не се натъкнем на граница, или границата на полето, или стойност, която не съответства на старата стойност.
Ако текущото местоположение в полето отговаря на старата стойност, ще я заменим с новата. След това ще изпълним функцията на всеки от четирите възможни съседа на текущата позиция.
def flood_fill(x ,y, old, new):
# we need the x and y of the start position, the old value,
# and the new value
# the flood fill has 4 parts
# firstly, make sure the x and y are inbounds
if x < 0 or x >= len(field[0]) or y < 0 or y >= len(field):
return
# secondly, check if the current position equals the old value
if field[y][x] != old:
return
# thirdly, set the current position to the new value
field[y][x] = new
# fourthly, attempt to fill the neighboring positions
flood_fill(x+1, y, old, new)
flood_fill(x-1, y, old, new)
flood_fill(x, y+1, old, new)
flood_fill(x, y-1, old, new)
Когато функцията е завършена, можем да изпълним нашия код и да видим дали работи. Ще стартираме print_field() два пъти, веднъж преди запълването на потока и отново след това. По този начин можем да го видим в действие.
Ще използваме точка (0,0) като начална точка. Старата стойност ще бъде числото 0. Ще използваме числото 3 за новата стойност.
if __name__ == "__main__":
# print field before the flood fill
print_field()
flood_fill(0, 0, 0, 3)
print("Doing flood fill with '3'")
#print the field after the flood fill
print_field()
Стартирайте програмата от конзолата...
python3 flood_fill.py
Изход
0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 0 Doing flood fill with '3' 3 3 3 3 3 3 3 3 1 3 3 3 3 3 3 1 1 3 3 3 3 3 3 3 3 3 1 3 3 3 3 3 1 1 3
Работи! Всички 0 бяха заменени с 3. А сега си представете, ако това бяха цветове вместо числа. Ето как правите инструмент за кофа за боя.
Заключение
Надявам се, че този кратък урок ви е харесал. Алгоритъмът за запълване на наводнения има всякакви приложения и уменията, използвани за създаването му, са безценни.
Ако искате да научите повече за Python и компютърното програмиране, моля, разгледайте някои от другите ми статии:
- „Квадратни танци в Python: Експеримент в клетъчни автомати“
- Сортиране на пиксели в Python
- „Нека изградим генератор на произволни символи в Python“
Повече съдържание в plainenglish.io. Регистрирайте се за нашия безплатен седмичен бюлетин тук.
