МАНИПУЛИРОВАНИЕ СИМВОЛИЧЕСКИ-ОПРЕДЕЛЕННЫМИ ОБЛАСТЯМИ
Алгоритмы заливки и серийного закрашивания читают буфер кадров пиксел за пикселом с целью определения их цвета и таким образом "пробираются ощупью" через область. Можно предположить, что алгоритм закраски был бы намного эффективнее, если бы он имел "высокоуровневое" символическое описание области, а ему приходится перечислять пиксел за пикселом. Поэтому давайте рассмотрим несколько способов символического описания области, каждый из которых обладает своими достоинствами и недостатками.
Чаще всего в графике используется метод описания области как внутренней части некоторого полигона, и такой подход разработан в деталях. Упомянутые методы подразделяют на два класса: первый представляет область в виде набора прямоугольников, а второй задает область с помощью контура (path), определяющего границу этой области.
1. Области, описываемые прямоугольниками
2. Области, заданные контуром
Естественно определять область посредством задания ее границы, которая описывается контуром некоторого типа. Существует несколько способов описания контура:
- С помощью математической формулы.
Например, (х-122)2+(y-36)2=25 определяет круговой контур диаметром 10 пикселов.
- С помощью множества точек. Последовательность расположения пикселов (x1, y1), (x2, y2),… (xn, yn) определяет контур из ломаных линий, если эта ломаная замкнутая ((x1, y1) = (xn, yn)), то она определяет полигон.
- С помощью последовательности смежных пикселов. Мы уже видели, что гранично-определенная пиксельная область задается с помощью совокупности пикселов некоторого граничного цвета. Область имеет наиболее приемлемый вид, если все ее граничные пикселы, образуют связанный замкнутый контур. Этот контур можно сохранить в буфере кадров как целиком, так и в виде списка расположения пикселов. Если каждая пара последовательных пикселов является 4-связанной, то такой контур называется "4-связанным", аналогично описывается "8-связанный" контур.
Одним из наиболее эффективных способов представления контура из смежных пикселов является метод цепного кода. Контур задается своим стартовым пикселом и последовательностью перемещений от пиксела к пикселу типа вверх, направо, вниз налево. Совокупность допустимых перемещений может кодироваться различными способами. В первом из них допускается четыре направления по сторонам света, причем каждому из направлений поставлена в соответствие цифра от 0 до 3. Таким образом, последовательность шагов задает 4-связанный контур. Следует отметить, что в силу использования только четырех направлений каждое из них может быть представлено всего двумя битами. В втором варианте кодирования допускаются восемь направлений и поэтому могут быть представлены 8-связанные контуры. Цифра 1 обозначает, что следующий пиксел маршрута, находится на единицу вверх и на единицу вправо, аналогичные комбинации получаются и для остальных трех диагональных направлений. Цепные коды напоминают относительное рисование (черепашью графику), отличие состоит в том, что здесь перемещение происходит только на один пиксел. Возможная структура данных для хранения контура: первые два элемента задают стартовый пиксел, далее идет количество шагов и список самих шагов. Цепные коды могут обеспечивать очень компактное представление для контуров и областей определенного вида.
Вопрос: Сколько бит на один шаг потребуется для кода с восьмью направлениями? (3).
Кроме того, при таком способе легко решаются следующие стандартные задачи:
- Перемещение контура – необходимо поменять стартовый пиксел.
- Масштабирование контура с масштабным множителем k – повторите каждый символ k раз.
- Поворот контура на 90 градусов против часовой стрелки – в случае цепного кода с 4 направлениями – необходимо увеличить на единицу цифру от 0 до 2 каждого шага, а цифру 3 заменить на 0. Для кода с восьмью направлениями к каждому шагу следует добавлять
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.