10,6. Манипулирование символически-определенными областями Практические упражнения
10.6.1. Вывести списки Выведите все списки «таблицы формы» для каждой из следующих пиксельных карт: О стрелка курсора на рис. 1.26; О пиксельная карта счастливой физиономии на рис. 1.20.
10.6.2. Определение структур данных
Определите подходящие типы для составляющих структуры данных, необходимых для представления в виде «формы».
Естественно определять область посредством задания ее границы, которая обычно описывается контуром некоторого типа. Существует несколько способов описания контура. Вот некоторые полезные способы. О С помощью математической формулы. Формула (х - 122)2 + (у- 36)2 = 25 определяет, например, круговой контур диаметром 10 пикселов. Язык PostScript (см. приложение Г) позволяет строить
в буфере кадров очень сложные контуры.
О С помощью множества точек. Последовательность расположения пикселов (г,,?/,), (х ,у2),…, (хп, уп) определяет контур из ломаных линий; если эта ломаная замкнутая ((*,, у{) = (хп, yj), то она определяет полигон. В разделе 10.7 «Заполнение полигонально-определенных областей» рассматриваются методы заполнения полигонов.
О С помощью последовательности смежных пикселов. Мы уже видели, что гранично-определенная пиксельная область задается с помощью совокупности пикселов некоторого «граничного» цвета. Область имеет наиболее приемлемый вид, если все ее граничные пикселы образуют связный замкнутый контур. Этот контур можно сохранить в буфере кадров как целиком, так и в виде списка расположения пикселов, например, (23,47), (24,46), (24,45),…, < много других значений >,…, (22,46), (23,47). Если каждая пара последовательных пикселов является 4-связиой, то такой контур называется «4-связным» («4-connected»); аналогично описывается «8-связный» контур. (Вопрос. Определяет ли 8-связный граничный контур 4-связную область?) Одним из наиболее эффективных способов представления контура из смежных пикселов является метод цепного кода (chain code) [Freeman, 67]. Контур задается своим стартовым пикселом, скажем, (34,57), и последовательностью «перемещений» от пиксела к пикселу типа: «вверх, направо, вниз, налево…». Совокупность допустимых перемещений может кодироваться различными способами. На рис. 10.27 приведены два варианта. В первом из них, показанном на рис. 10.27, а, допускаются четыре направления «по странам света», причем каждому из этих направлений поставлена в соответствие цифра от 0 до 3. Таким образом, последовательность шагов задает 4-связный контур. На рисунке контур А задан последовательностью с началом в нижнем левом углу. Данный контур оказался замкнутым, однако это не обязательно. (Какие ограничения накладываются на цифры «0», «1», «2», «3» для замкнутого контура?) Следует отметить, что в силу использования только четырех направлений каждое из них может быть представлено всего двумя битами.