8.2. ЗАПОЛНЕНИЕ ОБЛАСТИ МЕЖДУ СТОРОНАМИ МНОГОУГОЛЬНИКА

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

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

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

Рис. 8.2. Заполнение области внутри границ: каждый горизонтальный слой содержит четное число границ и внутренняя часть области заключена между первой и второй, третьей и четвертой и т. д. границами

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

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

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

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

в. Следует ли по достижении конца текущей границы прекра тить обращение, поскольку он соответствует минимуму по оси у.

Для примера, приведенного на рис. 8.2, процедура выглядит следующим образом. Сначала считывается первая пара границ и и соответствующее значение — значение любого максимума в этом слое Область, заключенная между границами, в которой значения превышают значение заполняется (область и производится обращение к следующей паре границ и Теперь мы располагаем текущим списком, содержащим четыре границы; области, заключенные между первой и второй, третьей и четвертой границами, заполнены. Поскольку максимумы точно определены, контроль точности здесь не вызывает затруднений в отличие от контроля четности в процедуре заполнения области на основе анализа значений пикселов (см. разд. 8.3). По окончании работы с некоторой границей из списка, сформированного в результате сортировки, выбирается следующая граница и вводится в текущий список. Однако необходимо выделить случай одновременного окончания двух границ и когда не нужно вводить в текущий список новые объекты. Этот случай должен быть выделен соответствующей меткой.

В табл. 8 1 приведен список очередности для примера на рис. 8.2. Нижние индексы соответствуют обозначениям точек на рисунке. Значения, помещенные в столбце «Метка указывают число границ, подлежащих одновременному переносу из

Таблица 8.1. (см. скан) Описание границ для контура, приведенного на ряс. 8.2

списка очередности в текущий список (число 2 означает, что должны быть перенесены текущая и очередная границы, а число 1 означает перенос только текущей границы). Метка (б) указывает значения у, при которых в текущий описок должна заноситься новая пара границ. Метка (в) указывает число новых границ, к которым должно быть выполнено обращение по окончании работы с текущей границей.

Алгоритм 8.1. Заполнение области между сторонами многоугольника

Обозначения. Каждая сторона многоугольника задается координатами у их своей наивысшей концевой точки, за исключением случая, когда сторона расположена горизонтально. При этом берутся координаты х, у ее левой концевой точки. — разности значений координат второй концевой точки прямой и точки, выбранной для задания прямой. Нижний индекс характеризует исходную индексацию сторон многоугольника. Метки сторон имеют те же значения, что и метки в табл. 8.1.

(см. скан)

(см. скан)

Совершенно очевидно, что в табл. 8.1 содержится избыточная информация. Так, вполне можно обойтись почти без всех значений (см. задачу 8.2). Мы не затрагиваем здесь проблему кодирования, чтобы не запутывать простой по существу алгоритм. Детальное изложение процедуры заполнения дается в виде алгоритма 8.1. Сортировку, предусмотренную шагом 1, можно выполнять с помощью любого из многочисленных алгоритмов, описанных в литературе. Способ, применяемый для разрешения проблемы равенства, гарантирует размещение в соседних позициях сторон, точка соприкосновения которых образует максимум, причем первой из них идет сторона с положительным угловым коэффициентом. На шаге 2 отыскиваются максимумы. Поскольку значение у, поставленное в соответствие каждой границе, представляет собой большую координату концевой точки, равенство значений у для двух смежных границ означает наличие максимума. Специфика правила, используемого для разрешения проблемы равенства значений координат при сортировке, позволяет с помощью несложного геометрического доказательства показать, что проверка значений координат х не требуется. Шаги алгоритма 1—4 отводятся на формирование списка очередности и для каждого контура выполняются только один раз. На шагах алгоритма 5— 9 происходит собственное заполнение.

Описанный алгоритм не различает контуры отверстий и внешние контуры; его применение не ограничивается односвязными областями. Данный алгоритм обеспечивает правильное заполнение групп областей при условии совместной сортировки их контуров (в частности, обеспечивает заполнение контура буквы

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