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

[Dale]

Вот примерно так:

1. Секущая a не находит пересечений с контуром - не красим.
2. Секущая b сталкивается с контуром в точке 6. Точка имеет верхнего соседа (5) и не имеет нижнего, поэтому запоминаем "верхний" и идем дальше в поисках нижнего соседа.
3. Проходим точки 7-10, нижний сосед так и не найден. В следующей точке покидаем контур, так ничего и не покрасив (касание границы).
4. Секущая c сталкивается с контуром в точке 5, которая имеет верхнего соседа (4) и нижнего (6). Фиксируем факт пересечения контура снаружи внутрь, включаем триггер закраски.
5. Продолжая сканирование, красим точки внутренней области контура между точками 5 и 11.
6. Секущая сталкивается с контуром в точке 11, которая имеет верхнего соседа (12) и нижнего (10). Фиксируем факт пересечения контура изнутри наружу, выключаем триггер закраски.
7. Остальные секущие ничем принципиально не отличаются от c, за исключением последней, которая пройдет через макушку окружности. Последняя будет подобна секущей b с точностью до осевой симметрии и не будет иметь верхнего соседа.

[Dale]

Dale, подвох в отрезке прямой.

Все, понял идею. Я этот отрезок принял за секущую, а не часть фигуры на экране.

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

[RXL]

Dale, по сути, если трассировать контуры, то алгоритм переходит в нечто, описанное мною выше (пост 42). Там линейная заливка, как у тебя, рекурсия (точнее - итераций по очереди заданий на заливку) не велика, а объем запоминаемых данных на итерацию - всего 4 величины (координаты начальной точки, направление и длина - можно упаковаться в 3-4 байта, в зависимости от размеров растрового буфера).

Кстати, граждане, а почему мы забываем об этом самом растровом буфере? История учит, что какая-то его часть не является существенной (например, строка состояния или панель инструментов - их можно перерисовать после) и эту память можно использовать как внешний буфер. Скажем, при распространенном формате для сотовых - экранчике 240х320, если забрать под буфер восемь строк, то получится аж 1920 пикселей - это, в зависимости от формата пикселя, 240-960-1920-3840 байт! Куда больше 128 стандартных для 8051!

[Sla]

Немного в сторону от алгоритма.

Offtopic:

SP в х51 - восьмибитный. Доступ только к внутренней памяти.
И растет он вверх.
Поэтому stackoverflow - стандартная ошибка.

Поставлю в угол.

[Dale]

Кстати, граждане, а почему мы забываем об этом самом растровом буфере?

Ни в коем случае не забываем. Я как раз и строю алгоритм с его максимальным использованием. Без него даже поле 100*100 точек с 256 градациями серого не поместится в ОЗУ старшей модели МК. Суть в том и состоит, чтобы сканировать буфер экрана.

[Dale]

Немного в сторону от алгоритма.

Offtopic:

SP в х51 - восьмибитный. Доступ только к внутренней памяти.
И растет он вверх.
Поэтому stackoverflow - стандартная ошибка.

Поставлю в угол.

Весьма ценное дополнение. Получается, даже наличие в лучшем случае 8К ОЗУ, что само по себе немного, погоды не сделает. Не говоря уже о подключении внешней памяти.

[RXL]

Слав, стек, в нашем случае - лишь структура, а не SP (особенно если перейти с рекурсии на итерации). Т.ч. его можно организовать и во внешней памяти, хотя доступ к ней не так удобен и на порядок медленнее из-за частых перезагрузок адресного регистра. В минимуме мы имеет порядка 80-100 байт для выполнения задачи. В более прогрессивном процессоре - килобайта полтора.

[Алексей++]

интересно, а можно ли контролировать заполнение стека таким образом, что вот как только он собрался переполнится, заменяем один из его элементов новой точкой, и продолжаем работать с извлечённой. Или так не всегда возможно ?

[RXL]

Кстати, граждане, а почему мы забываем об этом самом растровом буфере?

Ни в коем случае не забываем. Я как раз и строю алгоритм с его максимальным использованием. Без него даже поле 100*100 точек с 256 градациями серого не поместится в ОЗУ старшей модели МК. Суть в том и состоит, чтобы сканировать буфер экрана.

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

Леш, возьми кольцевой буфер. Когда из него нечего удалить, но и добавить тоже некуда, то что делать?..

[Sla]

Алексей1153++, заполнение стека можно контролировать.

[Dale]

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

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

2. Компилятор С (полагаю, что программа будет писаться именно на нем) обучен передавать агрументы подпрограмм через стек и в стеке же создавать локальные автоматические переменные. Теоретически можно и то, и другое организовать в нашем самодельном стеке. Но мне сильно сдается, что выглядеть это будет, мягко говоря, не слишком эстетично.

[Алексей++]

Леш, возьми кольцевой буфер. Когда из него нечего удалить, но и добавить тоже некуда, то что делать?..

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

[goodking]

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

[Dale]

goodking, а можно картинку, как они выглядят? Хотя бы схематично.

[Sla]

Offtopic:

Я думал, что топикстартер уже потерялся

Поставлю в угол.

goodking, а ты здесь был?

[RXL]

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

[Dimka]

Поиск замкнутых контуров - тоже ёмкая по памяти задача

[Dale]

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

[goodking]

Так, вот приблизительно где-то так оно должно выглядеть, только ч.б

[goodking]

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

дело в том, что я понятия не имел как это делается, ну и решил идти от простого к сложному =)

[Алексей++]

тут вообще ничего заливать не надо

[Dimka]

Да, при рисовании гистограмм алгоритм заливки не нужен

[RXL]

Dale, все же, если есть желание и время, попробуй реализовать свой алгоритм на Си - интересно все таки.

[goodking]

Извиняюсь =). Тогда уж посоветуйте, как нужно делать!

[Dale]

дело в том, что я понятия не имел как это делается, ну и решил идти от простого к сложному =)

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

[Dale]

RXL, можно бы попробовать, только не ручаюсь, что уж очень оперативно управлюсь.

Сначала было подумал, что напряжно будет рисовать средствами чистого С под MS Windows, а потом прикинул, что можно и буквочками в текстовом файле порисовать, нам же не красоты нужны, а саму идею проверить...

[Sla]

Как что делать? Рисовать.
Рисовать гистограмму прямыми отрезками.
У тебя ЧБ (2цвета) или 16/256 gray?

[goodking]

Как что делать? Рисовать.
Рисовать гистограмму прямыми отрезками.
У тебя ЧБ (2цвета) или 16/256 gray?

чб

[RXL]

goodking, для каждой точки гистограммы (x, y) рисовать вертикальные линии от (x, 0) до (x, y).

[Sla]

я подозреваю, что у "дисплея" есть встроенная функция рисования прямых.

С другой стороны если, например гистограмма рисуется в реальном времени, и нет времени на прорисовку отрезков, то заполнение проводить уже "постфактум".

Подозреваю, что просмотр "спектра" происходит в ручном режиме, т.е. есть время на прорисовку.