алгоритм закрашивания произвольной области

[Dale]

А в чем преимущество рекурсивного алгоритма в сравнении с самым простым - двигаться по растру, допустим, слева направо и сверху вниз, и при каждом нечетном пересечении контура включать закраску, а при четном - снова выключать? Вычислительные затраты мизерные, расход памяти тоже минимальный.

[Алексей++]

Dimka, шаг 1 - ну надо же было с чего-то начинать , поскольку инициализация - это поклажа затравочной точки в стек.

По твоим словам точки проверяются после входа в функцию, а я предлагаю проверять до входа, чтобы уменьшить нагрузку на стек (4 точки вокруг проверяются до засовывания в стек)

Dale, а контур может быть не единственным на экране, этож ещё надо определить, к какому контуру относится точка, если бегать таким образом

[Dimka]

По твоим словам точки проверяются после входа в функцию, а я предлагаю проверять до входа, чтобы уменьшить нагрузку на стек (4 точки вокруг проверяются до засовывания в стек)

А нет никакой нагрузки на стек со стороны уже закрашенных точек. В стеке всегда остаются только незакрашенные точки.

[Dale]

Dale, а контур может быть не единственным на экране, этож ещё надо определить, к какому контуру относится точка, если бегать таким образом

Для данного алгоритма количество контуров не имеет значения. Мы двигаемся вдоль строки от границы битовой карты(предполагаем, что контур целиком лежит внутри границ битовой карты). Пересекая контур в первый раз, мы считаем, что вошли внутрь области, и начинаем красить точки, пока вновь не пересечем контур. Тогда считаем, что вышли наружу, и перестаем красить, двигаясь дальше в том же направлении. Если опять пересекли, снова начинаем красить, и так до самой границы битовой карты. Затем переходим на следующую строку, и в том же духе.

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

Нам остается лишь сканировать битовую карту, как луч по экрану ЭЛТ, и аккуратно отличать пересечения от касаний, чтобы не сбиться с триггером "внутри/снаружи". Алгоритм должен получиться достаточно компактным, т.к. в каждый момент времени мы рассматриваем лишь ближайшую окрестность текущей точки и не тратим память на хранение удаленных точек, которые никак не влияют на закраску текущей. Затраты памяти - несколько переменных, время выполнения должно быть пропорционально площади битовой карты, глубина столь дефицитного для МК стека минимальная.

[Kivals]

Вад, с диагонялми стремно:

Код:

.......................
...*************....... - Вот здесь ...
...*............*...... - ... и здесь ...
...*.............*..... - ... и здесь можем вылезти за контур
...*..............*....
...*..............*....
...*..............*....
...*..............*....
...*..............*....
...*..............*....
...****************....
.......................

Хотя если контур - это двойная линия то тогда вопросов нет

[Kivals]

...аккуратно отличать пересечения от касаний...

Dale, ИМХО тот еще вопрос. Вот такой вот контур:

Код:

..................
.......*..........
......**..........
....**.*..........
.***...**********.
.*..............*.
.****************.
..................

В самой верхней точке - как определить что это касание?
Через строку - пересекаем 3 точки контура, значит закрасится за областью?

[Dale]

Kivals, мне кажется, решение должно выглядеть так. Для каждой точки определяем ближайшую окрестность:

Код:

1 2 3
4 * 5
6 7 8

Точки 1, 2, 3 - "верхние" соседи, точки 6, 7, 8 - "нижние", 4 и 5 - "боковые". Пересечение засчитываем лишь в том случае, если точка имеет и верхних, и нижних соседей. В противном случае считаем касанием и не переключаем триггер закраски.

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

Попробуем применить к нашему случаю.

1.

Dale, ИМХО тот еще вопрос. Вот такой вот контур:
...
В самой верхней точке - как определить что это касание?

Код:

.....
..0..
.**..

(я заменил текущую точку на 0, чтобы ее выделить)

Видим, что соседи текущей точки - только нижние, поэтому распознаем ее как касание.

2.

Через строку - пересекаем 3 точки контура, значит закрасится за областью?

Код:

....**
..0*.*
**...*

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

[Dale]

Кстати, между делом как-то прошляпили довольно важный вопрос: как отличить замкнутый контур от ломаной или кривой, которые в принципе тоже вполне могли бы присутствовать на битовой карте? Если по условию задачи их заведомо нет, то и хорошо. А вот если они могут быть наряду с контурами, то мы там такого накрасим своими алгоритмами...

Впрочем, предлагаю вернуться к этому вопросу после того, как окончательно разберемся с алгоритмом закраски замкнутых контуров, чтобы не было путаницы. Или, возможно, обсудить алгоритм распознавания  замкнутых контуров на битовой карте в отдельной теме.

[Dimka]

Да, со сканированием прямоугольной области есть всякие проблемы. И дело не только в касании, но ещё и в том, что сам контур может находиться в составе другой более сложной фигуры, и в область сканирования могут попадать торчащие из контура лучи (как контур буквы А) и находящиеся внутри контура перемычки (как контур буквы Ф).

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

Код: (Ruby)

def flood_p(b, x0, y0, s, m)
  p = Array.new
  p.push [x0, y0] if b[y0][x0] == s
  while not p.empty?
    x, y = p.pop
    b[y][x] = m
    p.push [x, y - 1] if y - 1 >= 0 and b[y - 1][x] == s
    p.push [x, y + 1] if y + 1 < b.length and b[y + 1][x] == s
    p.push [x - 1, y] if x - 1 >= 0 and b[y][x - 1] == s
    p.push [x + 1, y] if x + 1 < b[y].length and b[y][x + 1] == s
  end
end

Но вообще есть более экономный по расходу памяти метод, нежели вышеупомянутый. От начальной точки красить линию вверх и вниз, либо влево и вправо до границы. При этом смотреть на точки в соседних линиях на наличие границы или закраски и запоминать результат. Как только (для каждой стороны отдельно) результат меняется с "нельзя красить" на "можно красить" - запоминать эту точку в стеке. Этим методом в стек попадают не все окружающие точки, а лишь по одной точке на каждый сектор в линии, отделённый от других секторов границами. И ко всему прочему, каждая точка проверяется максимум 3 раза, а не 4. Реализация:

Код: (Ruby)

def flood_l(b, x0, y0, s, m)
  p = Array.new
  p.push [x0, y0]
  while not p.empty?
    x1, y = p.pop
    c = [false, false, false, false]
    x = x1
    while x >= 0 and b[y][x] == s
      b[y][x] = m
      c[1] = c[0]
      c[0] = b[y - 1][x] == s if y - 1 >= 0
      p.push [x, y - 1] if c[0] and not c[1]
      c[3] = c[2]
      c[2] = b[y + 1][x] == s if y + 1 < b.length
      p.push [x, y + 1] if c[2] and not c[3]
      x -= 1
    end
    c = [false, false, false, false]
    x = x1 + 1
    while x < b[y].length and b[y][x] == s
      b[y][x] = m
      c[1] = c[0]
      c[0] = b[y - 1][x] == s if y - 1 >= 0
      p.push [x, y - 1] if c[0] and not c[1]
      c[3] = c[2]
      c[2] = b[y + 1][x] == s if y + 1 < b.length
      p.push [x, y + 1] if c[2] and not c[3]
      x += 1
    end
  end
end

P.S. В примерах b - массив массивов, из него читают, в него же и пишут.

[Алексей++]

Dale, смотри такой рисунок (пересечение серых линий - точка начала заливки). Закрасит ли твой алгоритм правильно ? Даже если начинать сканирование не от края монитора, а от точки

Dimka, вот, к примеру, я провёл из места начала заливки линии. Получилась закрытая область A - туда попадём по твоему алгоритму ?

[Dimka]

Вот тесты моего алгоритма (начало всегда от середины фигуры):

Код:

Before:
*** *** ***
* *** *** *
*         *
* *** *** *
*** *** ***
After:
*** *** ***
*#***#***#*
*#########*
*#***#***#*
*** *** ***
Before:
**** ****
 *  *  * 
  *   *  
 *  *  * 
**** ****
After:
**** ****
 *##*##* 
  *###*  
 *##*##* 
**** ****

[Алексей++]

Dimka, это я не к тому, что я сомневаюсь, но я как-то придумывал похожий метод, и на чём-то споткнулся, так и не доделал )) Надо будет сделать тестилку, если время появится

[RXL]

Вот такое предложение: из точки провести ось (пусть будет вертикальная) и заливать линиями, перпендикулярными этой оси, от точки на оси до первой точки границы. После надо проверить границы получившейся заливки - нет ли граничащей с ней не залитой области и провести в таких местах новые оси и сделать аналогичную, но вертикальную заливку. И так до полного пропадения пустых областей.

[Dimka]

RXL, ну примерно так и работает алгоритм с линиями. Например, если делать заливку от твоей вертикальной линии вправо (светло-зелёная область) до границ, в какой-то момент на какой-то строке (вдоль горизонтальной линии над концом нижнего выреза фигуры) случится переход закраска-граница-закраска - это и есть триггер для запоминания точки, принадлежащей нижнему (зелёному) треугольнику. Затем рекурсивный запуск алгоритма от этой точки приведёт к заливке этого нижнего треугольника.

[RXL]

И глубина рекурсии на много порядков меньше, чем при волновом методе. Наверно на некоторых фигурах они почти сравняются (например, узкий прямоугольник, повернутый на 45 градусов).
Думаю, что для снижения ресурсоемкости следует найденные ветвления помещать в очередь и выполнять только после завершения заливки текущей области.

Нашел минус: заливка не проникает по диагонали. Некоторое неудобство при заливке сложных фигур.

X X X X X
X * * X X
X X X   X
X X X X X

Если не ошибаюсь, у волнового метода та же болезнь.
С другой стороны, это правильно - иначе границы должны будут быть сплошными.

[Dale]

Dale, смотри такой рисунок (пересечение серых линий - точка начала заливки). Закрасит ли твой алгоритм правильно ? Даже если начинать сканирование не от края монитора, а от точки

Если начинать заливку не с края битовой карты, а с произвольной точки, то возникает такая сложность - неизвестно, лежит ли данная начальная точка внутри контура или снаружи. На решение этой проблемы понадобятся дополнительные вычислительные затраты, которые совершенно не нужны, если начать с края. А главное - непонятно, зачем исусственно создавать эту сложность.

[RXL]

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

А вообще, думаю, что надо отталкиваться от практической задачи.
Для чего нужна заливка? Как правило - рендеринг из векторного формата. Соответственно, точку может задать человек, подготавливающий векторный файл. Он же может учесть особенности построения, когда какие-то области полигона не удастся залить от одной точки - поставит вторую и т.д. точки для заливки.

[Алексей++]

Нашел минус: заливка не проникает по диагонали.

дык, это не минус, это правильно ) А вот если в A* (волновой алгоритм, гда новые точки смотрятся по звёздочке вокруг) не сделать проверку на такой диагональный перескок, то заливка будет "протекать". Короче, зависит от задачи

Если начинать заливку не с края битовой карты, а с произвольной точки, то возникает такая сложность - неизвестно, лежит ли данная начальная точка внутри контура или снаружи. На решение этой проблемы понадобятся дополнительные вычислительные затраты, которые совершенно не нужны, если начать с края. А главное - непонятно, зачем исусственно создавать эту сложность.

Почему бы такой сложности вдруг не появиться естественным путём? допустим, разрабатывается девайс "a la Paint" для детей. Там можно рисовать пером и заливать произвольные области из произвольной точки.

[Dale]

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

Вспоминаем условие задачи:

Посоветуйте, как лучше закрашивать область ограниченную фигурой произвольной формы на графическом ЖКИ.

Нет полигонов, нет часовой стрелки... Есть лишь битовая карта, считываемая из памяти индикатора. Конечно, теоретически можно соединить соседние точки отрезками и получить полигон. Но опять же вспоминаем условие задачи: к индикатору подключен микроконтроллер с архитектурой x51. Автор не указал конкретную модель, но в самых навороченных из них, насколько мне известно, объем оперативной памяти не превышает 8К.

Если бы речь изначально шла о полигонах, к тому же ориентированных заранее известным образом, то и решение было бы другим. А тут изначально векторная(пардон, поторопился) растровая задача, которая должна быть решена весьма экономными средствами.

[Dale]

Почему бы такой сложности вдруг не появиться естественным путём? допустим, разрабатывается девайс "a la Paint" для детей. Там можно рисовать пером и заливать произвольные области из произвольной точки.

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

Можно представить алгоритм и еще проще - провести координатные оси через начальную точку внутри контура. Тогда получаем четыре квадранта, подобные с точностью до осевой симметрии относительно координатных осей. Красим первый слева-направо-снизу-вверх, а потом и остальные симметрично.

[RXL]

Dale, к 8051 можно подключить и внешнюю память - 64кБ, за вычетом IO. А со страничным принципом можно иметь еще больше памяти данных. В общем-то что рассказывать - думаю и сам все это знаешь.

Вопрос в другом - для чего заливать и что заливать? Плясать надо от печки.

[Dale]

RXL, при умении и желании к x51 можно подключить даже современный видеоакселератор с аппаратной заливкой замкнутых областей текстурами, благо они (акселераторы) это уже давно умеют. Скорость будет бешеная. Другое дело - согласен ли инициатор темы на такие затраты? Тем более что очень сомневаюсь, что заливка областей - основное назначение его прибора.

А главное - зачем наращивать память, если ее хватает на основные функции прибора? Только для того, чтобы аппаратно поддержать накладные расходы на рекурсивные выкрутасы, необходимость которых неочевидна? Если предложенный растровый алгоритм с учетом его ограничений устроит автора, для его реализации потребуется всего несколько переменных и чуть стека для вызова пары-тройки функций. Чаще всего такие ресурсы можно найти в готовом проекте без наращивания аппаратных средств, переразводки печатной платы и прочих прелестей.

[RXL]

Dale, может я чего-то не понял, но из прочитанного вижу, что твой алгоритм будет работать только в определенных условиях и не универсален. Пусть он прост и быстр, но что толку, если результат не предсказуем.
По этому я и поставил вопрос в постах 50 и 46 - для чего все это нужно? Ведь зная специфику легче искать пути оптимизации.

[Dale]

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

Можно конкретный пример условий, при которых он непредсказуем? Если можно, с примером поведения рекурсивного варианта при тех же условиях.

[RXL]

Dale, на картинке пример фигуры, на которой, как мне видится, твой алгоритм даст сбой. Традиционный тут подход не сбойнет.
Хочешь, поставь начальную точку внутрь фигуры или снаружи...

[Алексей++]

Можно конкретный пример условий, при которых он непредсказуем?

кстати, интересно, как себя поведёт алгоритм, если он наткнётся на отдельно стоящую точку (ведь это как бы контур размером  1*1 пиксел)

[Dale]

RXL, я правильно понял, что контур имеет вид обычной окружности? Или не заметил какого-то подвоха?

Алексей1153++, с отдельной точкой как раз минимум проблем - у нее нет ни верхних, ни нижних соседей, наличие которых необходимо для работы алгоритма. Растровый сканер просто переползет через нее и отправится дальше.

[Алексей++]

Dale, так а как же смена чётности областей, ведь точка поменяет чётность, будет сбой. И Рома (RXL), я полагаю, про то же самое спрашивает - линия поменяет чётность, нарушив закраску

[RXL]

Dale, подвох в отрезке прямой. Окружность, в целях проверки, можно вообще исключить (хотя это будет не совсем честно - другие алгоритмы тут зальют весь буфер).
Очень хотелось бы увидеть, как твой алгоритм поймет, что это не граница контура, который надо залить, без рекурсии и т.п. затратных на память алгоритмов.

[Dale]

Алексей1153++, мы меняем четность только в точках, которые имеют соседей и сверху, и снизу. Одиноко стоящие точки на триггер не повлияют. Я сейчас попробую набросать наглядную картинку, а то на словах как-то сумбурно получается объяснить идею.