Быстрый способ получить ограничивающий прямоугольник заливки

Question

Мне нужно выполнить заливку области изображения.Однако на самом деле мне не нужно полученное изображение, мне нужно знать только наименьший прямоугольник, содержащий все пиксели, которые будут изменены заливкой.

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

Пример ввода и вывода (требуется только красный прямоугольник):

Пример входного изображения.Красная точка - начальный пиксель.Область, которую нужно заполнить, - это голубой Z-тетромино, содержащий точку http://www.finnw.me.uk/ffinput.png Пример выборки. Только позиция / ширина / высота красного прямоугольника имеет значение http://www.finnw.me.uk/ffoutput.png

---

Редактировать: Пример # 2 с островами:
Пример ввода с островами http://www.finnw.me.uk/ffinput2.png Пример вывода http://www.finnw.me.uk/ffoutput2.png

Пример # 3:
Пример ложного острова http://www.finnw.me.uk/ffinput3.png

---

Редактировать

Извините, изображения были потеряны в результате сбоя жесткого диска. Когда я впервые опубликовал это, SO не сделалхост-образы, поэтому я хранил их на своем собственном сервере.

Answer 1

В основном вам нужно определить самые большие X, самые большие Y, самые маленькие X и самые маленькие Y

Найдите правый нижний угол реального края:

Вы можете сделать это, пройдя как можно дальше вправо + вниз внутри вашего цвета.

Когда вы больше не можете идти направо + вниз, тогда вам нужно проверить, чтобы убедиться, что вы не застряли в углу острова. Чтобы проверить это, вам нужно проследить по всему краю в поисках шанса пройти вправо + вниз. Вы можете отслеживать (наибольшийX, наибольший, наименьший, наименьший) каждый раз, когда это происходит, если у вас действительно есть реальное преимущество.

Если у вас действительно есть остров, вы в конечном итоге найдете место, следующее за краем, которое вы можете пройти вправо + вниз.

Если у вас нет возможности пройти еще вправо + вниз, и вы достигнете своей начальной точки, тогда у вас будет реальное преимущество. И вы вычислили свои (самый большойX, самый большойY, самый маленькийX и самый маленькийY).

Answer 2

Один из возможных способов - пройти как можно дальше (влево, вверх, вниз, вправо) от начальной точки, а затем следовать по краю по часовой стрелке или против часовой стрелки, пока не вернетесь к своей первой точке. Следите за минимальными (X, y) и максимальными (X, Y) при прохождении края.

Это должно позволить вам смотреть на меньшее количество пикселей, если у вас нет довольно странных форм для заполнения.