Адаптация заполнения линии сканирования для обнаружения отдельных объектов

Идея заливки сканлайном заключается в следующем.

1. вам дана начальная точка (seed) (x, y)
2. идите влево до тех пор, пока пиксель (x-1, y) не будет заполнен или вы не дойдете до x = 0
3. x, которого вы достигли, будет началом строки сканирования; оставьте два флага «искать пещеры наверху» и «искать пещеры внизу», оба инициализированы в true
4. this is the begin of scanline loop. Check the pixel above (x, y-1) if it's to be filled and now considering the look-above flag and the pixel there are 4 cases:
   • if "look above" is true and the pixel is to be filled then you found a "new cavern", store (x, y-1) in the "to-do-list" and mark "look above" as false
   • если «смотреть выше» ложно и пиксель НЕ должен быть заполнен, то текущая пещера заполнена, и вам нужно искать другую, поэтому просто отметьте «смотреть_выше» как истину.
   • в других случаях (смотрите выше верно и пиксель не должен быть заполнен или взгляд выше ложно и пиксель должен быть заполнен) вы просто ничего не делаете
5. Повторите те же рассуждения с флагом «смотреть ниже» и цветом пикселя (x, y+1).
6. закрасьте пиксель (x, y) и перейдите к (x+1, y), повторяя с (5), если только пиксель, к которому вы перемещаетесь, не будет окрашен.
7. если есть что-то в «списке дел», выберите это и вернитесь к (1), используя координаты, которые вы нашли в списке дел, как (x, y)

Это версия для заливки с 4 связями. Для 8-связной заливки вам также необходимо проверить наличие каверн в точках (x-1, y-1) и (x-1, y+1) при запуске строки сканирования, а также вам необходимо проверить наличие каверн (x+1, y -1) и (x+1, y+1) в конце строки развертки (если соответствующие флаги истинны).

При перемещении по строке сканирования вы хотите добавить зеленые точки на картинке в свой список дел:

Обратите внимание, что количество семян не будет «минимальным» (например, первые два «вышеуказанных семени» в примере окажутся в одной и той же пещере, и поэтому действительно нужен только один из них). Тем не менее объем стека, необходимый для их хранения, обычно будет намного меньше, чем объем, необходимый для попиксельного рекурсивного подхода.

Другой возможный подход к ограничению объема необходимой памяти — использование алгоритма рисования границы:

1. Вы помещаете начальное семя (x, y) в список current_active и рисуете его
2. Инициализировать список next_active, чтобы он был пустым
3. для каждого пикселя в списке current_active проверьте наличие соседей, которые нужно закрасить: когда вы найдете один, закрасьте его и добавьте в список next_active
4. когда вы закончите, установите список current_active в список next_active и повторите с 2, если список не был пустым

Вы можете увидеть пример двух алгоритмов в действии в в этом видео.