Пред.
След.
Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике ДЛЯ СТУДЕНТОВ И ШКОЛЬНИКОВ ЕСТЬ
ZADANIA.TO
8.2. ЗАПОЛНЕНИЕ ОБЛАСТИ МЕЖДУ СТОРОНАМИ МНОГОУГОЛЬНИКАЗаполнение области между сторонами многоугольника (методом многоугольника) называют также заполнением области на основе преобразования развертки, хотя иногда эти термины употребляются и в другом смысле. Стороны многоугольника (границы) упорядочиваются и помечаются таким образом, чтобы обеспечивалось сохранение всей топологической информации. Затем с помощью простого однопроходового алгоритма проводится проверка на четность и собственно процедура заполнения не требует произвольного доступа к пикселам. Ее с равным успехом можно выполнить как на растровых, так и на векторных графических устройствах. Особенно удобно ее использовать при решении таких прикладных задач, в которых один и тот же контур воспроизводится многократно (например, при фотонаборе), поскольку предварительная сортировка и разметка, требующие значительных затрат вычислительных ресурсов, должны выполняться лишь один раз. Исходными данными для нас служит последовательность сторон (границ) многоугольника, аппроксимирующего контур. Для каждой стороны заданы координаты
Рис. 8.2. Заполнение области внутри границ: каждый горизонтальный слой содержит четное число границ и внутренняя часть области заключена между первой и второй, третьей и четвертой и т. д. границами через точку Границы, прошедшие сортировку, заносятся в список очередности; для заполнения области используется текущий список, содержащий границы, находящиеся в каждом слое. Начальным значением у в этой процедуре является максимальное и она продолжается вплоть до достижения минимального значения у. В списке очередности предусмотрены метки, позволяющие задавать следующие условия. а. Число границ, подлежащих передаче в текущий список: б. Следует ли обращаться к следующей паре границ до окон чания работы с текущей парой. Эта ситуация возникает в случае, когда прямая, проходящая через максимум, пересекает одну из текущих границ. в. Следует ли по достижении конца текущей границы прекра тить обращение, поскольку он соответствует минимуму по оси у. Для примера, приведенного на рис. 8.2, процедура выглядит следующим образом. Сначала считывается первая пара границ В табл. 8 1 приведен список очередности для примера на рис. 8.2. Нижние индексы соответствуют обозначениям точек на рисунке. Значения, помещенные в столбце «Метка Таблица 8.1. (см. скан) Описание границ для контура, приведенного на ряс. 8.2 списка очередности в текущий список (число 2 означает, что должны быть перенесены текущая и очередная границы, а число 1 означает перенос только текущей границы). Метка (б) указывает значения у, при которых в текущий описок должна заноситься новая пара границ. Метка (в) указывает число новых границ, к которым должно быть выполнено обращение по окончании работы с текущей границей. Алгоритм 8.1. Заполнение области между сторонами многоугольника Обозначения. Каждая сторона многоугольника задается координатами у их своей наивысшей концевой точки, за исключением случая, когда сторона расположена горизонтально. При этом берутся координаты х, у ее левой концевой точки. (см. скан) (см. скан) Совершенно очевидно, что в табл. 8.1 содержится избыточная информация. Так, вполне можно обойтись почти без всех значений Описанный алгоритм не различает контуры отверстий и внешние контуры; его применение не ограничивается односвязными областями. Данный алгоритм обеспечивает правильное заполнение групп областей при условии совместной сортировки их контуров (в частности, обеспечивает заполнение контура буквы Описанный алгоритм не рассчитан на случай, когда частями контура служат горизонтальные прямые, однако его нетрудно модифицировать таким образом, чтобы он выполнял правильную обработку подобных контуров (см. задачу 8.1).
|
1 |
Оглавление
|