Адаптиране на запълването на линията на сканиране за откриване на отделни обекти

Идеята за запълване на сканиращата линия е следната

1. дадена ви е началната точка (семе) (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
   • ако "look above" е невярно и пикселът НЕ трябва да се запълва, тогава текущата пещера е завършена и трябва да потърсите друга, така че просто маркирайте "look_above" като true
   • в други случаи (поглед отгоре е вярно и пикселът не трябва да се запълва или поглед отгоре е невярно и пикселът трябва да се запълва) просто не правите нищо
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, освен ако списъкът не е празен

Можете да видите пример за двата алгоритъма в действие в този видеоклип.