Интернет магазин китайских планшетных компьютеров

Компьютеры - Заливка - Метод заливки, реализуемый в ограниченном объёме памяти

Есть метод, практически не использующий дополнительной памяти для связных по 4 направлениям областей. Таким же методом возможно искать выход из лабиринта. Представьте себе маляра, который красит область так, чтобы не оказаться зажатым окрашенной частью в углу. Начальные границы - это четыре пикселя, которые маляр рассматривает, чтобы выбрать одно из возможных действий. Основные возможные состояния:

1. Все 4 граничных пикселя окрашены.
2. Три граничных пикселя окрашены.
3. Два граничных пикселя окрашены.
4. Один граничный пиксель окрашен.
5. Ни один из граничных пикселе не окрашен.

При продолжении границы используется метод правой руки. Маляр обходит область, держа правую руку на «стене» и продвигается, не отрывая руки.

В случае 1 маляр окрашивает пиксель, на котором стоял, и улетает.

В случае 2 существует путь из области наружу. Маляр красит пиксель, на котором стоял, и движется по этому пути.

В случае 3 два граничных пикселя создают полосу, которая, если мы покрасим текущий пиксель, может отрезать нас от всего, что находится по её другую сторону. Нужно закрепить "стрелку", указывающую, где мы сейчас и куда смотрим, чтобы, если мы когда-то вернёмся на этот пиксель, мы могли её увидеть. Если такая стрелка уже нарисована, мы её сохраняем и движемся дальше по правилу правой руки.

Стрелка на первой двухпиксельной границе фиксирует, где маляр начал работу и куда оттуда пошёл. Если маляр встречает ту же метку, двигаясь в том же направлении, то он понимает, что красить этот квадрат, двигаясь в этом направлении, безопасно: пиксели на другой стороне по какому-то пока не известному пути будут доступны для окраски в будущем. Метка снимается, и её можно поставить где-то ещё.

Если же маляр встречает стрелку, указывающую не туда, куда он идёт, значит, он прошёл каким-то путём, возвратившим его к метке. Эту петлю надо исключить. Метка убирается, а маляр движется в указанном ею направлении, руководствуясь правилом левой руки. Так он идёт, пока не попадёт на пересечение. Не отрывая левой руки, маляр ищет простой проход. Найдя его, он красит этот пиксель; петля разрывается, и можно продолжать алгоритм.

В случае 4 мы должны проверить противоположные связные по 8 направлениям углы на то, окрашены они или нет. Если хотя бы один из этих двух углов окрашен, получается пересечение многих путей, которое мы окрасить не сможем. Если оба пусты, можем окрасить текущий пиксель и следовать дальше по правилу правой руки.

Алгоритм даёт выигрыш в памяти за счёт проигрыша по времени. Для областей простой формы он весьма эффективен, но в более сложных случаях много времени тратится на то, чтобы отследить границы области и убедиться, что всё можно окрасить.

Первая коммерческая реализация этого алгоритма появилась в 1981 г. на системе Vicom Image Processing, выпущенной Vicom Systems, Inc. Также в этой системе присутствовал и классический рекурсивный алгоритм.